王家荣-运筹学习题解答

1、电话营销专家王家荣 整理 电话营销培训 XinXin100.COM 欢迎交流附录一 习题解答Appendix 1 Solutions of Exercises第一章 线性规划一、 以下集合中，哪些是凸集，哪些不是凸集？（1） (x1,x2)| x1+x21 是凸集（2） (x1,x2,x3)| x1+x21,x1-x32 是凸集（3） (x1,x2)| x1-x2=0 是凸集（4） (x1,x2,x3)| x1x2,x1+x2+x36 是凸集（5） (x1,x2)| x1=1,|x2|4 是凸集（6） (x1,x2,x3)| x3=|x2|, x14不是凸集二、 求出以下不等式组所定义的多面体

2、的所有极点。（1）x1+x2+x35-x1+x2+2x36x1,x2,x30解：引进松弛变量x4，x50x1+x2+x3+x4=5-x1+x2+2x3+x5=6x1,x2,x3x4,x50令 ，在A矩阵中，一共有10个行列式不等于0的方阵，即10个基。，相应的基础解是X1=（x1，x2，x3，x4，x5）=（-1/2，11/2，0，0，0）X2=（x1，x2，x3，x4，x5）=（4/3，0，11/3，0，0）X3=（x1，x2，x3，x4，x5）=（-6，0，0，11，0）X4=（x1，x2，x3，x4，x5）=（5，0，0，0，11）X5=（x1，x2，x3，x4，x5）=（0，4，1，0

3、，0）X6=（x1，x2，x3，x4，x5）=（0，5，0，-1，0）X7=（x1，x2，x3，x4，x5）=（0，5，0，0，1）X8=（x1，x2，x3，x4，x5）=（0，0，3，2，0）X9=（x1，x2，x3，x4，x5）=（0，0，5，0，-4）X10=（x1，x2，x3，x4，x5）=（0，0，0，5，6）其中B2、B4、B5、B7、B8、B10是可行基，相应的基础可行解为：X2=（x1，x2，x3，x4，x5）=（4/3，11/3，0，0，0）X4=（x1，x2，x3，x4，x5）=（5，0，0，0，11）X5=（x1，x2，x3，x4，x5）=（0，4，1，0，0）X7=（x

4、1，x2，x3，x4，x5）=（0，5，0，0，1）X8=（x1，x2，x3，x4，x5）=（0，0，3，2，0）X10=（x1，x2，x3，x4，x5）=（0，0，0，5，6）原问题的极点是：X2=（x1，x2，x3）=（4/3，11/3，0）X4=（x1，x2，x3）=（5，0，0）X5=（x1，x2，x3）=（0，4，1）X7=（x1，x2，x3）=（0，5，0）X8=（x1，x2，x3）=（0，0，3）X10=（x1，x2，x3）=（0，0，0）（2）x1+x2+x31-x1+2x24x1,x2,x30解：引进松弛变量x4，x50x1+x2+x3+x4=1-x1+2x2+x5=4x1,

5、x2,x3x4,x50令 ，A矩阵中共有9个基。x1、x2为基变量，得到：x1+x2=1-x1+2x2=4求解这个方程组，得到x1=-2/3，x2=5/3；（x1,x2,x3,x4,x5）=（-2/3,5/3,0,0,0）x1、x3为基变量，得到：x1+x3=1-x1=4求解这个方程组，得到x1=-4，x3=5；（x1,x2,x3,x4,x5）=（-4,0,5,0,0）x1、x4为基变量，得到：x1+x4=1-x1=4求解这个方程组，得到x1=-4，x4=5；（x1,x2,x3,x4,x5）=（-4,0,0,5,0）x1、x5为基变量，得到：x1=1-x1+x5=4求解这个方程组，得到x1=1

6、，x2=5；（x1,x2,x3,x4,x5）=（1,0,0,0,5）x2、x3为基变量，得到：x2+x3=12x2=4求解这个方程组，得到x2=2，x3=-1；（x1,x2,x3,x4,x5）=（0,2,-1,0,0）x1、x4为基变量，得到：x2+x4=12x2=4求解这个方程组，得到x2=2，x4=-1；（x1,x2,x3,x4,x5）=（0,2,0,-1,0）x2、x5为基变量，得到：x2=12x2+x5=4求解这个方程组，得到x1=1，x5=2；（x1,x2,x3,x4,x5）=（0,1,0,0,2）x3、x5为基变量，得到：x3=1x5=4求解这个方程组，得到x3=1，x5=4；（x

7、1,x2,x3,x4,x5）=（0,0,1,0,4）x4、x5为基变量，得到：x4=1x5=4求解这个方程组，得到x4=1，x5=4；（x1,x2,x3,x4,x5）=（0,0,0,1,4）其中的基础可行解有：（x1,x2,x3,x4,x5）=（1,0,0,0,5）（x1,x2,x3,x4,x5）=（0,1,0,0,2）（x1,x2,x3,x4,x5）=（0,0,1,0,4）（x1,x2,x3,x4,x5）=（0,0,0,1,4）原问题的极点是：（x1,x2,x3）=（1,0,0）（x1,x2,x3）=（0,1,0）（x1,x2,x3）=（0,0,1）（x1,x2,x3）=（0,0,0）三、

8、用图解法求解以下线性规划问题：（1）maxz=x1+3x2s.t.x1+x210-2x1+2x212x1 7x1,x20 x2 10 (2,8) 6 x1 -6 0 7 10最优解为（x1,x2）=（2,8），max z=26(2)minz=x1-3x2s.t.2x1-x2£4x1+x2³3x2£5x1£4x1,x2³0 x2 5 3 x1 0 2 3 4最优解为 （x1，x2）=（0，5），min z=-15（3）maxz=x1+2x2s.t.x1-x2£1x1+2x2£4x1£3x1,x2³0 x2

9、2 x1 0 1 2 3 4多个最优解，两个最优极点为（x1，x2）=（2，1），和(x1，x2)=(0，2)，max z=4（4）minz=x1+3x2s.t.x1+2x2³42x1+x2³4x1,x2³0 x2 x1=0 4 x4=0 2 x3=0 x2=0 x1 0 2 4 最优解为（x1，x2）=（4，0），min z=4四、maxz=2x1+x2-x3s.t.x1+x2+2x3£6x1+4x2-x3£4x1,x2,x3³0（1）B1不是可行基，不是基础可行解。（2）B2是可行基，是基础可行解，目标函数值为：（3）B3是基础可

10、行解，是基础可行解，目标函数值为：（4）B4不是可行基，不是基础可行解。（5）B5是可行基，是基础可行解，目标函数值为：（6）B6是可行基，是基础可行解，目标函数值为：（7）B7不是可行基，不是基础可行解。（8）B8不是可行基，不是基础可行解。（9）B9是可行基，是基础可行解，目标函数值为：（10）B10是基础可行解，目标函数值为：在可行基B2、B3、B5、B6、B9、B10中，最优基为B2，最优解为：是基础可行解，目标函数值为：五、对于以下约束（1）(1)x1+2x2£6x1-x2£4x2£2x1,x2³0（1） 画出该可行域，并求出各极点的坐标（2）

11、 从原点开始，从一个基础可行解移到下一个“相邻的”基础可行解，指出每一次叠代，哪个变量进基，哪个变量离基。(1)x1+2x2+x3=6x1-x2+x4=4x2+x5=2x1,x2,x3,x4,x5³0 x2 3 x3=0 2 C(2,2) x5=0 D(0,2) B(14/3,2/3) 0 x2=0 4 O(0,0) A(4,0) x1=0 x4=0 -4(2)O®AA®BB®CC®DD®O进基变量x1x2x4x3x5离基变量x4x3x5x1x2六、 用单纯形原理求解以下线性规划问题maxz=3x1+2x22x1-3x2£3

12、-x1+x2£5x1,x2³0minz=-3x1-2x22x1-3x2+x3=3-x1+x2+x4=5x1,x2,x3,x4³0第一次叠代取B=a3，a4，基变量为x3，x4，非基变量为x1，x2=0。将基变量和目标函数用非基变量表示：z= -3x1-2x2x3=3-2x1+3x2+x4=5+x1-x2选取x1进基，当x1=3/2时，x3=0离基，新的基变量为x1=3/2，x4=13/2，非基变量为x2，x3=0，目标函数值为z=-9/2。第二次叠代将基变量和目标函数用非基变量表示：2x1=3+3x2-x3-x1+x4=5-x2将第一个约束中的基变量x1的系数变成

13、1，x1=3/2+3/2x2-1/2x3-x1+x4=5-x2消去第二个约束中的基变量x1x1=3/2+3/2x2-1/2x3+x4=13/2+1/2x2-1/2x3将基变量x1代入目标函数z=-3x1-2x2=-3(3/2+3/2x2-1/2x3)-2x2=-9/2-13/3x2+3/2x3 选取x2进基，当x2增加时，基变量x1和x4随之增加，目标函数z无下界，即z无上界。七、 将问题转变为极小化，引进松弛变量x3，线性规划问题成为minz=-x1+2x2s.t.3x1+4x2=122x1-x2+x3=12x1,x2,x30选取x1、x3为基变量，列出单纯形表zx1x2x3RHSz11-2

14、00x1034012x302-1112消去基变量x1在目标函数和第二个约束条件中的系数zx1x2x3RHSz10-10/30-4x1014/304x300-11/314得到最优解，最优解为x1=4，x2=0，x3=4，min z=-4，max z=4。八、用单纯形表求解以下线性规划问题（1）maxz=x1-2x2+x3s.t.x1+x2+x3122x1+x2-x36-x1+3x29x1,x2,x30解：标准化，将目标函数转变成极小化，引进松弛变量x4,x5,x6³0,得到：minz=-x1+2x2-x3s.t.x1+x2+x3+x4=122x1+x2-x3+x5= 6-x1+3x2+

15、x6= 9x1,x2,x3,x4,x5,x60列出初始单纯形表zx1x2x3x4x5x6RHSz11-210000x401111001212/1x5021-10106-x60-1300019-选取x3为进基变量，确定x4为离基变量zx1x2x3x4x5x6RHSz10-30-100-12x301111001212/1x503201101818/3x60-1300019-得到最优解（x1, x2, x3, x4, x5, x6）=（0, 0, 12, 0, 18, 9），min z=-12，max z=12由于其中非基变量x1在目标函数中的系数为0，x1进基，x5离基，可以得到另一最优解：zx1

16、x2x3x4x5x6RHSz10-30-100-12x3001/312/3-1/306x1012/301/31/306x60011/301/31/3115新的最优解为（x1,x2,x3,x4,x5,x6）=（6, 0, 6, 0, 0, 15），min z=-12，max z=12原问题最优解的全体为：，（0l1），都有max z=12（2）minz=-2x1-x2+3x3-5x4s.t.x1+2x2+4x3-x462x1+3x2-x3+x412x1+x3+x4 4x1,x2,x3,x40引进松弛变量x5，x6，x7³0，得到minz=-2x1-x2+3x3-5x4s.t.x1+2x

17、2+4x3-x4+x5= 62x1+3x2-x3+x4+x6=12x1+x3+x4+x7= 4x1,x2,x3,x4,x5,x6,x70初始单纯形表为zx1x2x3x4x5x6x7RHSz121-350000x50124-11006-x6023-110101212/1x70101100144/1x4进基，x7离基zx1x2x3x4x5x6x7RHSz1-31-8000-5-20x5022501011010/2x6013-2001-188/3x4010110014-x2进基，x6离基zx1x2x3x4x5x6x7RHSz1-10/31-22/300-1/3-14/3-68/3x504/3019/

18、301-2/35/314/3x201/31-2/3001/3-1/38/3x4010110014最优解为：(x1, x2, x3, x4, x5, x6, x7)=(0, 8/3, 0, 4, 14/3, 0, 0)，min z=-68/3（3）minz=3x1-x2s.t.-x1-3x2-3-2x1+3x2-62x1+x2 84x1-x216x1,x20将第一、第二个约束条件两边同乘以-1；引进松弛变量x3，x4，x5，x60，得到minz=3x1-x2s.t.x1+3x2+x3= 32x1-3x2+x4= 62x1+x2+x5= 84x1-x2+x6=16x1,x2,x3,x4,x5,x6

19、0初始单纯形表为：zx1x2x3x4x5x6RHSz1-3100000x3013100033/3x402-301006-x5021001088/1x604-1000116-x2进基，x3离基，zx1x2x3x4x5x6RHSz1-10/30-1/3000-1x201/311/30001x403011009x505/30-1/30107x6013/301/300117最优解为：（x1, x2, x3, x4, x5, x6）=（0, 1, 0, 9, 7, 17），min z=-1用两阶段法求解以下线性规划问题（1）maxz=x1+3x2+4x3s.t.3x1+2x213x2+3x3172x1+

20、x2+x3=13x1,x2,x30解：将目标函数转化成极小化，引进松弛变量x4，x5，x60，得到minz=-x1-3x2-4x3s.t.3x1+2x2+x4=13x2+3x3+x5=172x1+x2+x3=13x1,x2,x3,x4,x5,0引进人工变量x6³0，构造辅助问题：minz=x6s.t.3x1+2x2+x4=13x2+3x3+x5=172x1+x2+x3+x6=13x1,x2,x3,x4,x5,x60列出辅助问题的系数矩阵表：zx1x2x3x4x5x6RHSz100000-10x4032010013x5001301017x6021100113消去基变量x6在目标函数中的

21、系数，并开始单纯形叠代：zx1x2x3x4x5x6RHSz121100013x403201001313/3x5001301017-x602110011313/2x1进基，x4离基，zx1x2x3x4x5x6RHSz10-1/31-2/30013/3x1012/301/30013/3-x500130101717/3x600-1/31-2/30113/313/3x3进基，x6离基，zx1x2x3x4x5x6RHSz100000-10x1012/301/30013/3x500202104x300-1/31-2/30113/3辅助问题已经获得最优解，且min z=0，因而可以转入第二阶段，其系数矩阵表

22、为：zx1x2x3x4x5RHSz1134000x1012/301/3013/3x50020214x300-1/31-2/3013/3消去基变量x1，x3在目标函数中的系数：zx1x2x3x4x5RHSz1011/307/30-65/3x1012/301/3013/313/2x500202144/2x300-1/31-2/3013/3-x2进基，x5离基zx1x2x3x4x5RHSz1000-4/3-11/6-29x10100-1/3-1/33x2001021/22x30001-1/31/65得到原问题的最优解：（x1, x2, x3）=（3, 2, 5），min z=-29，max z=29

23、（2）maxz=2x1-x2+x3s.t.x1+x2-2x384x1-x2+x322x1+3x2-x34x1,x2,x30解：将问题化为标准化形式：minz=-2x1+x2-x3s.t.x1+x2-2x3+x4= 84x1-x2+x3+x5= 22x1+3x2-x3-x6= 4x1,x2,x3,x4,x5,x60引进人工变量x70，构造辅助问题：minz=x7s.t.x1+x2-2x3+x4=84x1-x2+x3+x5=22x1+3x2-x3-x6+x7=4x1,x2,x3,x4,x5,x6,x70辅助问题的系数矩阵为：zx1x2x3x4x5x6x7RHSz1000000-10x4011-21

24、0008x504-1101002x7023-100-114消去基变量x7在目标函数中的系数zx1x2x3x4x5x6x7RHSz123-100-104x4011-2100088/1x504-1101002-x7023-100-1144/3x2进基，x7离基，zx1x2x3x4x5x6x7RHSz1000000-10x401/30-5/3101/3-1/320/3x5014/302/301-1/3-1/310/3x202/31-1/300-1/31/34/3得到辅助问题的最优解，且min z=0，转入第二阶段。建立系数矩阵表：zx1x2x3x4x5x6RHSz12-110000x401/30-5

25、/3101/320/3x5014/302/301-1/310/3x202/31-1/300-1/34/3消去基变量x2在目标函数中的系数，得到zx1x2x3x4x5x6RHSz18/302/300-1/34/3x401/30-5/3101/320/3-x5014/302/301-1/310/310/2x202/31-1/300-1/34/3-x3进基，x5离基zx1x2x3x4x5x6RHSz1-2000-10-2x40120015/2-1/215x3070103/2-1/25x2031001/2-1/23原问题的最优解为：（x1, x2, x3, x4, x5, x6）=（0, 3, 5,

26、15, 0, 0），min z=-2，max z=2。（3）minz=x1+3x2-x3s.t.x1+x2+x33-x1+2x22-x1+5x2+x34x1,x2,x30解：引进松弛变量x4，x5，x60，得到minz=x1+3x2-x3s.t.x1+x2+x3-x4=3-x1+2x2-x5=2-x1+5x2+x3+x6=4x1,x2,x3,x4,x5,x60引进人工变量x7，x80，构造辅助问题minz=x7+x8s.t.x1+x2+x3-x4+x7=3-x1+2x2-x5+x8=2-x1+5x2+x3+x6=4x1,x2,x3,x4,x5,x6,x7,x8³0列出辅助问题系数矩阵

27、表zx1x2x3x4x5x6x7x8RHSz1000000-1-10x70111-100103x80-1200-10012x60-151001004消去基变量x7，x8在目标函数中的系数，得到zx1x2x3x4x5x6x7x8RHSz1031-1-10005x70111-1001033/1x80-1200-10012-x60-1510010044/1x3进基，x6离基，zx1x2x3x4x5x6x7x8RHSz1-1200-10-102x30111-1001033/1x80-1200-100122/2x60-240101-1011/4x2进基，x6离基zx1x2x3x4x5x6x7x8RHSz

28、1000-1/2-1-1/2-1/203/2x103/200-5/40-1/45/4011/4x80000-1/2-1-1/21/213/2x30-1/2101/401/4-1/401/4得到辅助问题的最优解，但min z=3/2>0，因此原问题无可行解。第二章 对偶和灵敏度分析一、 写出以下问题的对偶问题（1）maxz=-x1+2x2s.t.3x1+4x2122x1-x22x1,x20对偶问题为miny=12w1+2w2s.t.3w1+2w2-14w1-w2 2w10w20(2)minz=2x1+3x2+5x3+6x4s.t.x1+2x2+3x3+x42-2x1-x2-x3+3x4-3

29、x1,x2,x3,x40对偶问题为maxy=2w1-3w2s.t.w1-2w222w1-w233w1-w25w1+3w26w10w20(3)minz=2x1+3x2-5x3s.t.x1+x2-x3+x452x1+x34x2+x3+x4=6x10x20x30x4:unr对偶问题为maxy=5w1+4w2+6w3s.t.w1+2w22w1+w33-w1+w2+w3-5w1+w3=0w10w20w3:unr二、 设原始问题为maxz=2x1+3x2s.t.x1+x24x23x1,x20(1) 写出对偶问题对偶问题为miny=4w1+3w2s.t.w12w1+w23w1,w20(2) 图解法求原始问题

30、的基础可行解 x2 C(0,3) B(1,3) x1 O(0,0) A(4,0)O点：x1=0，x2=0，x3=4，x4=3，z=0A点：x1=4，x2=0，x3=0，x4=3，z=8B点：x1=1，x2=3，x3=0，x4=0，z=11，最优解C点：x1=0，x2=3，x3=1，x4=0，z=9对偶问题的图解 w2 B(2,1) A(3,0) w1A点：w1=3，w2=0，w3=1，w4=0，y=12B点：w1=2，w2=1，w3=0，w4=0，y=11，最优解（3）原始问题的最优解：x1=1，x2=3，x3=0，x4=0，z=11显然满足原始可行条件；对偶问题的最优解：w1=2，w2=1，

31、w3=0，w4=0，y=11显然满足对偶可行条件；x1w3=0，x2w4=0，x3w1=0，x4w2=0满足互补松弛条件。三、zx1x2x3x4x5RHSz10-40-4-2-40x3001/211/205/2x101-1/20-1/61/35/2恢复初始单纯形表，x4进基，x3离基zx1x2x3x4x5RHSz10080-2-20x40012105x101-1/31/301/310/3x5进基，x1离基zx1x2x3x4x5RHSz16-210000x40012105x503-110110原始问题为minz=-6x1+2x2-10x3s.t.x2+2x3 53x1-x2+x310x1,x2,

32、x30对偶问题为maxy=5w1+10w2s.t.3w2 -6w1-w2 22w1+w2-10w10w20(2) 从原始问题的最优单纯形表得到对偶问题的最优解为w1= -4，w2= -2，w3=0，w4=4，w5=0四、 对于以下线性规划问题maxz=2x1+3x2+6x3s.t.x1+x2+x310x1-x2+3x36x1,x2,x30(1) 对偶问题为miny=10w1+6w2s.t.w1+w22w1-w23w1+3w26w1,w20(2) 原始问题引进松弛变量x4、x5 maxz=2x1+3x2+6x3s.t.x1+x2+x3+x4=10x1-x2+3x3+x5=6x1,x2,x3,x4

33、,x50B1是原始可行基，但不是对偶可行基；B2既不是原始可行基，也不是对偶可行基；B3是原始可行基，但不是对偶可行基；B4既不是原始可行基，也不是对偶可行基；B5既是原始可行基，也是对偶可行基，因此是原始问题的最优基。B6B10计算略。（3） 原始问题的最优解为：x1=0，x2=6，x3=4，x4=0，x5=0，max z=42对偶问题的最优解为：w1=15/4，w2=3/4，w3=5/2，w4=0，w5=0，min y=42容易看出，原始问题的最优解与对偶问题的最优解满足互补松弛关系。五、 对于以下问题maxz=4x1+6x2-x3s.t.x1+x2+2x36x1+4x2-x34x1,x2,x30(1) 写出对偶问题miny=6w1+4w2s.t.w1+w24w1+4w262w1-w3-1w1,w20(2) 用单纯形表求解zx1x2x3x4x5RHSz1-4-61000w1=0，w2=0x40112106w3=-4，w4=-6，w5=1x5014-1014不满足对偶可行条件x1进基，x5离基zx1x2x3x4x5RHSz1010-30416w1=0，w2=4x4