运筹学基础及应用第四版胡运权主编课后练习答案.

1、习题一 P46该问题有无穷多最优解，即满足运筹学基础及应用习题解答-1 .一一一.，4X1 +6X2 =6且0 <X2 <-的所有(X1,X2 ),此时目标函数值z =3 o(b)X2品用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。1.2(a)约束方程组的系数矩阵12 3 63 0 0A =8 1 -4 0 2 0(3 000 0 -1基基解是否基可行解目标函数值X1X2X3X4X5X6P1 P2 P3c167ccc否0- -00036P1 P2 P40100700是10P1 P2 P57是30300-02piP2P674_40002iT否PiP3P4005一280

2、0否PiP3P50032080是3PiP3P6i0i2003否PiP4P5000350是0PiP4P65400-20i54否最优解 X ='0,10,0,7,0,0 T(b)约束方程组的系数矩阵A 2 3 4、<21 2 !基基解是否基可行解目标函数值XiX2X3X4Pi P2ii否-4002Pi P32ii是43-00555Pi P4iii否'0036P2 P3cicc是50-202P2 P4i否0 一 022P3P400 i i是5最优解x = ,0, ,0 155) °1.3(a)(1)图解法最优解即为严+4x2 =9的解x =(1,-；,最大值z=35

3、5xi 2x2 =822(2)单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式max z =10x1 5x2 0x3 0x43xi +4x2 +x3 =9st. 5x1 +2x2 +x4 =8则P3,P4组成一个基。令均=x2 =0得基可行解x=(0,0,9,8),由此列出初始单纯形表cj T10500cB 基 bx1x2x3x40 x3934100x48520110500cj -zjcr1 ><T2 。 0 =min |8 9 一,一'、.8二5 3,5 5cj T10500CB 基 bx1x2x3x4c210 x30闵135!55“82110x110555c

4、j -zj010-2CT2 >0 , 6 =min8314、万 2 2新的单纯形表为cjT10500cB基bx1x2x3x45x232015143一?410x11101_2 7cjZj0051425743523仃1,仃2 <0,表明已找到问题取优解xi =1, x2 =- , x3=0, x4=0。取大值 z2(b)最优解即为W的解x=(H),最大值z/(2)单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式max z =2x1 x2 0x3 0x4 0x55x2 x3 =15 st.6x1 2x2 x4 =24xi x2 x5 = 5则P3, P4, P5组成一个基。令

5、 xi =x2 =0得基可行解x = (0,0,15,24,5 ),由此列出初始单纯形表cj T21000cB基bX1X2X3X4X50X315051000X424620100X5511001cj-zj21000。1仃2。m m min( L,24 "6q1j1= 4cjT21000cB基bX1X2X3X4X50X315051002X4411301600X510：2113 J0_161cj-zj0130130。2>0,6= min,15, 152。2 J2新的单纯形表为cjT21000cB基bX1X2X3X4X50X315200154_152711xX4100-22423130

6、X5010242cj -zi11000 _T423,仃2 <0,表明已找到问题最优解Xi = 1 , X2 =215X3 = 一2/古 *17值z =2(a)在约束条件中添加松弛变量或剩余变量，"'''且令 X2 =X2 -X2（X2 之 0,X2 之 0）1.6X3 =%，Z' = -Z该问题转化为 . 一 '''_ 'maX z' - -3xi -X2 rz -2X3 0x4 Fx5匚 ，一_"，.'， 一2x1 +3x2 -3x2 +4x3 +x4 =12.''

7、9; _ '-4 X1 X2 - X2 - 2 X3 - X5 =8st.I3x1 -x2 , x2 -3x3 =6'''X1,X2, X2, X3,X4, X5 -0其约束系数矩阵为23-3410 "A = 4 112 013-11300,在A中人为地添加两列单位向量p ,P8,23-341000”4 112011031130001,令 max z' =-3x1 - x2 x2 -2x3 0x4 0x5 -Mx6 -Mx7得初始单纯形表Cj T与-11-200-MMCB基bXi'X2''X2'X3X4X5X6X

8、70X41223-341000HMX6841-1-20-110HMX763-11-30001Cj Zj-43+7M -1 1 -2 -5M 0 -M 00z' = -z . ' " ' 八 " 一(b)在约束条件中添加松弛变量或剩余变量，且令X3= X3- X3(X3> 0,X3 >0)该问题转化为'''max z':-3x1 -5x2 x3 - x3 0x4 0x5x1 2x2x3 - x3 x4 =6st.2 x1 "，x 2 - 3x3 - 3 x3 1' x§ -16&#

9、39;x1 +x2 +5x3 -5x3 =10'x1, x2, x3, x3, x4, x 至 0其约束系数矩阵为121-1-10、A= 213-30-1口15-500 ,在A中人为地添加两列单位向量P ,P812 1 -1 -10 10、213-3010011 5-50001,'''令 max z' = -3x1 -5x2 x3 -x3 0x4 0x5 -Mx6 -Mx7得初始单纯形表CjT-3-51-100 -M -MCb基 bx1*2x；IF x3x4x5x6x7_Mx66121-1-10100*516213-30100-MX710115-5000

10、1cj -zj-3 2M 5 3M 1+6M -1-6M -M 0001.7(a)解1:大M法在上述线性规划问题中分别减去剩余变量x4, x6, x8,再加上人工变量x5, x7 ,x9,得max z = 2x1 -x2 2x3 0x4 - Mx5 0x6 - Mx7 0x8 - Mx9x1 x2 x3 - x4 x5 = 6s,t,-2Xi ', X3 - X6 'X7 - 22 X2 _ X3 - Xg . X9 - 0Xi,X2,X3,X4,X5,X6,X7,X8,X9 ,0其中M是一个任意大的正数。据此可列出单纯形表cj T2-120-M0-M0-M9icb基bX1X2

11、X3X4X5X6X7X8X9-MX56111-1100006-MX7-2-20100-1100-MX9002-10000-110Cj -Z2 -M3M -12 + M-M0-M0-M0-MX56103/2-11001/ 2-1/ 24-MX72-20100-110021X2001-1/20000-1/ 2-1/ 2cj -zj2-M05M上322M0-M0M 1万21上3M2 2-MX53400-113/2-3/21/ 2-1/ 23/42X322010011001X2111000-1/ 21/ 2-1/21/ 2cj -zj4M +500_ M03M十3-5M -3 M -1 1-3M222

12、22X13/4100-1/ 41/ 43/8-3/81/8-1/82X37/2001-1/ 21/2-1/41/ 41/ 41/ 4_1X27/4010-1/ 41/4-1/81/8-3/83/8cj -zj000 5/4 -n” 5-M 4-3/831VA-9-M - 88-M 8由单纯形表计算结果可以看出，。4 A0且ai4 <0(i =1,2,3),所以该线性规划问题有无界解解2：两阶段法。现在上述线性规划问题的约束条件中分别减去剩余变量x4,x6, x8，再加上人工变量X5,X7,X9，得第一阶段的数学模型据此可列出单纯形表cj T0000101019iCb基 bX1X2X3X4

13、X5X6X7X8X91 X5 61 X7 -21 X9 0111-110000-20100-110002-10000-1160cj -Zj1-3-11010101 X5 61 x7 20 X2 0103/2-11001/ 2 -1/ 2-20100-110001-1/20000-1/ 2 -1/ 242cj -zj13105/210-10-221 X5 30 X3 20 X2 1400-113/2 -3/2 1/ 2 -1/ 2-20100-1100-11000-1/ 2 1/ 2-1/2 1/ 23/4cj -zj0000101012 X1 3/42 x3 7/2-1 x2 7/4100-1

14、/ 41/ 43/8-3/81/8-1/8001-1/ 21/2-1/41/ 41/ 4-1/ 4010-1/ 41/4-1/81/8-3/83/8cj -zj0000101013 7 7t*第一阶段求得的最优解 X =(一,一,一,0,0,0,0,0,0) T,目标函数的最优值 8 =0。 4 4 2一 、一3- 7 7 7t因人工变量X5=x7=x9=0,所以X -(-,-,- ,0,0,0,0,0,0)是原线性规划问题的基可4 4 2行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。cj -zj2-1200006

15、cb基 bX1X2X3X4X6X82x1 3/4100-1/43/8-1/82X3 7/2001-1/2-1/ 41/4-1x2 7/4010-1/4-1/8-3/8cj _Zj0005/4-3/8 -9/8由表中计算结果可以看出，仃4 >0且ai4 <0(i =1,2,3),所以原线性规划问题有无界解。(b)解1 ：大M法在上述线性规划问题中分别减去剩余变量x4, x6,x8,再加上人工变量x5, x7 ,x9,得min z = 2x1 3x2 x3 0x4 0x5 Mx6 - Mx7x1 +4x2 +2x3 -x4 +x6 =8st3x1 2x2 - x5 x7 = 6，“2，

16、乂3，乂4，%?6?7?8，% -0其中M是一个任意大的正数。据此可列出单纯形表cj t2-120-M0-M0-M9iCb基 bXix2x3x4x5x6x7Mx6 8Mx7 6142-10103200-10123cj -zj2-4M 3-6M 1-2MMM003 x2 2M x7 21/411/2-1/401/405/20-11/2-1-1/2184/5cj -zj551V，八 1V,13 1M- 3M 3 cM 0 MM 042242243 x2 9/52 x 4/5013/5-3/101 /10 3/10 -1/1010-2/51/5-2/5 -1/52/5cj -zj0001/ 21 /

17、2 M -1/2 M -1/24 9由单纯形表计算结果可以看出，最优解 X 1：4,-,0,0,0,0,0) T,目标函数的最优解值5 5*49 z =2父一+3父一=7。X存在非基变量检验数 仃3 = 0 ,故该线性规划问题有无穷多最优解。55解2:两阶段法。现在上述线性规划问题的约束条件中分别减去剩余变量X4, X5,再加上人工变量 X6, X7,得第一阶段的数学模型 min = x6 x7x1 +4x2 +2x3 -x4 +x6 =8st3x1 2x2 -x5 x7 = 6x1,x2,x3,x4,x5,x6,x7,x8,x9 ,0据此可列出单纯形表cj T00000119icb基bx1又

18、2x3x4x5x6X71x8142-101021x763200-1013cj-zj-4-6-211000x221/411 /2-1/401/4081x725/20-11/2-1-1/214/5cj_zj-5/201-1/213/200x29/5013/5-3/101/103/10-1/100x14/510-2/51/5-2/5-1/52/5cj-zj00000114 9t*第一阶段求得的最优解X (-,-,0,0,0,0,0)，目标函数的最优值 8=0。5 5一,一、I4 9因人工变量x6 = x7 = 0 ,所以(一- 00000) T是原线性规划问题的基可行解。于是可 5 5以进行第二阶段

19、运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。cj -zj23100cb基 bX1X2X3X4X53 X2 9/52 x1 4/5013/5-3/101/1010-2/51/5-2/5cj -zj0001/21/24 9由单纯形表计算结果可以看出，最优解 X 4,-,0,0,0,0,0) T,目标函数的最优解值 5 5*49 z =2M+3M=7。由于存在非基变量检验数仃3 = 0 ,故该线性规划问题有无穷多最优55解。1.8表 1-23x1xx3x4x5x4624-210X1-13201cj -Zj3-1200表 1-24x1x2x3x4

20、x5x1312-11/20X510511/21cj -zj075-3201.10354000x1x2x3x4x5x65 x28/32/31013000x514/34,305】-23100x6 2935/304-2301cj -zj-13045 300x1x2x3x4x5x65 x28/32/3101 3004x3 14.15-4/1501-2/151500x689/154115 00-2/15-4,51Cj -zj11/1500-17/15-450x1x2x3x4x5x65x250/410101541841_1Q'414x362/41001-6415414413x1 8941100-2

21、/41-12 411541cj _zj000-4541-2441-1141最后一个表为所求。习题二 P76(a)min z =2x1 2x2 4x3xi +3x2 +4x3 22st2x1 +x2 +3x3 +y4 <3x1 -4x2 3x3 =5x1,x2之0, 十无约束(b)max z =5x1，6x2，3x3,|_ x1 _2x2 .2x3 =5一x1 +5x2 -x3 之 3st. '±±-4x1 +7x2 +3x3 E8M无约束，x2之0,x3 <02.22.1写出对偶问题max w =2y1 3y2 5y3/ y1 +2y2 +y3 <

22、2对偶问题为：3y1 +y2+4y3 <2st.4y1 3y2 3y3 =4y1之0,y2 <0, y3无约束min w =5y1 -3y2 8y3'y1-y2+4y3=5对偶问题为：2y1 +5y2 +7y3之6s.t.| 2y1 - y2 3y3 一 3y1 无约束，y2 <0,y3 -0(a)错误。原问题存在可行解，对偶问题可能存在可行解，也可能无可行解。(b)错误。线性规划的对偶问题无可行解，则原问题可能无可行解，也可能为无界解。(c)错误。(d)正确。2.6对偶单纯形法(a)min z =4x1 12x2 18x3x1+3x3 之3st.2x2 +2x3 之

23、5Jx1 , x2 , X3 0解：先将问题改写为求目标函数极大化，并化为标准形式max z' - -4x1 -12x2 -18x3 - 0x4 0x5x1-3x3 +x4=-3st. J2x2 -2x3+x5 =5xi _0 i =1, " ,5列单纯形表，用对偶单纯形法求解，步骤如下Cj T-4-12-1800Cb 基 bx1x2x3x4x50 x4-30x5-5103100L2 201cj zj-4-12-18000x4-3-101-3 10-512x2一210110-2cj _zj-40-60-618 x3111010333-12x2一2111一 10332cj -z

24、j-20026最优解为x = 0,1, ,目标值z =39。,2(b)min z =5x1 2x2 - 4x33x1 +x2 +2x3 之4st. 6x1 +3x2 +5x3 之10x1, x2 , x3 -0解：先将问题改写为求目标函数极大化，并化为标准形式max z' - -5x1 -2x2 -4x3 0x4 0x5-3x1 - x2 -2x3 +x4=Tst. J-6x1 -3x2 -5 x3+x5 =T0xi -0i =11,5列单纯形表，用对偶单纯形法求解Cj T-5-2-400cB 基 bxix2x3x4x50x4。0 x5-1041210_6_501cj _zj-5240

25、0c-20x4-3-10.1-1 1-3 3_|3o102 x23215033cj -zj2210033-4X32301-31-2x204105-2cj -zj100-20最优解为x =(0,0,2 T ,目标值z=8 o2.8将该问题化为标准形式：max z =2x1 -x2 x3 0x4 0x5 xi - x2 ' x3 ' x4 =6st.x1 2x2 x5 =4xi _0 i =1, 一5用单纯形表求解cj t2-1100cB基bx1x2x3x4x50x46111100x54-12001cj-Zj2-11001-6cB基bx1x2x3x4x52x16111100x510

26、03111cjF0-3-1-20由于5 <0,所以已找到最优解 X =(6,0,0,0,10),目标函数值z =12(a)令目标函数max z = (2 +兀)x1 +(-1+ %) x2 +(1+%) x3(1)令，电=h =0 ,将兀反映到最终单纯形表中cj T2 十五100Cb 基 bX1X2X3X4X52十九人 611110X51003111cj -zj0 -3- Z, -1-%-2-九 0表中解为最优的条件：-3-W0, -1-%E0, 2-11 E0,从而以之1(2)令，力=一-3 =。，将%反映到最终单纯形表中cj T2 -1+%100Cb 基 bX1X2X3X4X52X1

27、6111100X51003111cj -Zj0 Z2 - 3-1-20表中解为最优的条件：% - 3 E 0 ,从而九2 M 3%-1 W0,从而'31(3)令1 -1 =% = 0 ,将%反映到最终单纯形表中cj t2-11 + %00cB基bX1X2X3X4X52X16111100X51003111cj-Zj0-3力-3 -1-20表中解为最优的条件:(b)令线性规划问题为max z = 2x1 x2 x3J_Xlx2x3 _ 64st. « -x1 +2x2 <4 十、x >0(i =1,3)(1)先分析的变化b ：= B° b 二使问题最优基不变

28、的条件是b：b =(2)同理有U0 + %(c)由于x* =(6,0,0,0,10)代入-x1 +2x3 = -6 <2 ,所以将约束条件减去剩余变量后的方程x1 +2x3 -x6 =2直接反映到最终单纯形表中cj T2-11000Cb基bx1x2x3x4x5x62x161111000x5100311100*6-210-2001cj_Zj0-3-1-200对表中系数矩阵进行初等变换，得cj T2-11000cB基bx1x2x3x4x5x62x161111000x5100311100x6-80-1-3-101cj -zj0-3-1-20010xi =1，38 x3=322一，x5 =一,取

29、优值为53283cj T2-ii000CB基bxi*2x3x4x5*62xi%1%0%0%0x5%0%0%i%0*6%0%i%0_i385icjZj000333因此增加约束条件后，新的最优解为2.12(a)线性规划问题max z =3x1 x2 4x36x1 3x2 5x3 <45 st. 3xi 4x2 5x3 <30xi, x2, x3 :0单纯形法求解cB基bxix2x3x4x50x445635i00x5303450icj一Zj3i4000x4I53】-i0i-14x363545i0i5cj-Zj35_ii500_453xi5ii30i3134x330ii_i525ccc13

30、c j _zj0-20-255最优解为(X1,X2,X3卜(5,0,3),目标值z=27。(a)设产品A的利润为3+丸，线性规划问题变为max z = 3：!；，/. x1 x2 4x36x1 +3x2 +5x3 <45st. 3x1 +4x2 +5x3 <30x1，x2,x3 ,0单纯形法求解基 bxix2x3x4xx44563510x 3034501Cj -Zj3+尢1400x4153】-101-1x3634101555cj -zj3 一114-+Z00555xi511110333x 30111255cj -zj0-2十自01人,3十大35 35 3为保持最优计划不变，应使2十

31、九，3十二人都小于等于0,解得3ele9。35 35 355(b)线性规划问题变为max z =3xi x2 4x3 3x46x1 +3x2 +5x3 +8x4 <45s.t.3x1 +4x2 +5x3 +2x4 <30 x1,x2,x3,x4 -0单纯形法求解cB基bx1x2x3x4x5x0x5456358100x630345】201cjzj3143000x4153】-1061-14x3634120155553110704Cjzj55553x151102113334x33412011555113cj_zj0-20555511110x4:01一:226664x35213101851

32、51515cj129717_zj0010153030此时最优解为(X1,X2,X3 )=(0,0,5 ),目标值z= 20,小于原最优值，因此该种产品 不值得 生产。(c)设购买材料数量为 y ,则规划问题变为max z =3xi -X2 -4x3 -0.4y6- 6x1 - 3x2 - 5x3 <45st.3x1 4x2 5x3 y _30x1,x2, x3 , y _0单纯形法求解cB基bx1x2x3yx4x0x5456350100x630345-101cj"zj31425000x4153】-1011-14x363545115015cj.Zj351150250453x151

33、_130口13j13_134X330112-51飞25Cjzj0-20151飞3飞0y153-1011-14X39653510150cjZj359-5002一52-5此时最优解为(xi,X2,X3,y)=(0,0,9,15 ),目标值z=30,大于原最优值，因此 材料扩大生产，以购材料15单位为宜。应该购进原第三章3.1 表 3.36地 销地B1B2B3B4A198121318A21010121424A38911126A41010111212销量614355用vogel法求解得AB1B2B3B4A1144A224A360A411用位势法检验，把上表中有数字的地方换成运价sB1B2B3B4UiA18138A2128A38117A411127Vj1045令 v1=1则 u1+v2=8所以u3=7u1+v4=13v3=4u2+v3=12u4