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

1、运筹学基础及应用习题解答习题一1.1P46S %)，此时目标函数值z = 3。(b)用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。1.2(a)约束方程组的系数矩阵基基解是否基可行解基基解是否基可行解X 2wX 6piP 2P 301637-6000否piP 2P 40100700是piP 2P 50300720是目标函数值1031236300 .A =81-402030000-LP1 P 2 P 6-40002144否乌P3P 40 0 - 2800否P1P3P500|080是3乌P3P 610 - 2003否P1 P 4P 50 00350是0乌 P 4P 6-00- 2 0

2、1544否最优解 x =(0,10,0,7,0,0 M(b)约束方程组的系数矩阵基基解是否基可行解目标函数值xxX3xp1P 21旦004否p1P 320110是43555p1P 4-30011否P 2P 30220是5P 2P 40- 202否P 3P 40011是511T最优解x = ,0, ,055)1.3(a)(1)图解法3x+ 4 x=9小如(3)12的解x =1,5 x1+ 2 x2=82 J最优解即为s.t. 0，0 = min ，一=新的单纯形表为c j 10500c B基 b尤1x 2尤3x 45x32210 x1101141410-177cj - zj00-奏1414时2

3、0，表明已找到问题最优解 =1，凡=235 %= 0, x4 = 35 %= 0, x4 = 0。最大值二*=-(1)图解法最优解即为J最优解即为J6 x + 2 x1xI 1=24的解X = =5(2)单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式max z = 2 x + x + 0 x + 0 x + 0 x5 x2+ x3 = 15s.t. )，(a)在约束条件中添加松弛变量或剩余变量，且令x 2 = X 2 - x 2(2 Z 0, x 2一x3 = x3, z = z该问题转化为max z = 3xi x2 + x； 一 2x3 + 0 x4 + 0 x52X + 3

4、x 2 3x 2 + 4 x 3 + x 4 = 12s.t. 4 x1 + x 2 x 2 2 x3 x 5 s.t. 01 2 2 3 45其约束系数矩阵为233410 IA =411201:311300 J在A中人为地添加两列单位向量P7,P8(23341000 )41120110331130001)令 max z = 3x x + x 2 x + 0 x + 0 x Mx Mx12234567得初始单纯形表c j 3-11-200-M-Mc基b尤1x 2x 2x；x 4尤5x 6尤70 x1223-341000Mx 6841-1-20-110Mx 763-11-30001 TOC o

5、1-5 h z c. - z.-3 + 7M -1 1 - 2 - 5M 0 - M00(b)在约束条件中添加松弛变量或剩余变量，且令X = X - r (r 0,X 0) z = z3333，max zmax z = -3x 5x + x 一 x、+ 0 x + 0 x123345x + 2 x + x x x 612334t2x + x - 3x 一 3x” + x = 16x + x + 5 x 一 5x = 101233x , x ,x, x”, x ,x 0 123345其约束系数矩阵为12 1 -1 -1 0)A =213 -3 0 -1 TOC o 1-5 h z 1 1 5 -

6、5 00 J在A中人为地添加两列单位向量P7, P12 1 -1 -10 10、213-301 00115-500 01J令 max z = -3 x - 5 x + x - x + 0 x + 0 x - Mx - Mx12334567得初始单纯形表c j -3-51-100 -M - MCB基bxxxx xxxx12334567-Mx660 x16-Mx71021-1-101013-30100115-50001cj zj-3 + 2M 5 + 3M 1+6M -1-6M -M 0001.7(a)解1：大M法 TOC o 1-5 h z 在上述线性规划问题中分别减去剩余变量x ,x ,x ,

7、再加上人工变量x ,x ,x ,得68579max z = 2 x 一 x + 2 x + 0 x 一 Mx + 0 x 一 Mx + 0 x 一 Mx123456789x + x + x - x + x = 6 TOC o 1-5 h z 23452 x + x x + x = 2s,t,1367x x x + x = 02389x , x , x , x , x , x , x , x , x 0123456789其中M是一个任意大的正数。据此可列出单纯形表c j 2 120 M 0 M 0 M9i匕基 bxxxxxxxxx123456789M x 6M x 2M x90111110000

8、20100110002 10000 1160c - z.2 M 3M 1 2 + M M0 M 0 M 0M x 6M x 21 x 0103/211001/ 2 1/220100 110001 1/ 200001/2 1/242c - z.cm八 5M3m八u 八 M 1 13M2 M 0+ M0 M 0-+2222 22M x 32 x 21 x 1400 113/2 3/2 1/ 2 1/2201001100110001/2 1/2 1/ 2 1/ 23/4c - z ./iMu八八,八3M + 3 5M 3 M 1 1 3M4 M + 500M01 Irl 1 JUJirlU22222

9、 x 3/42 x 7/2 1 x2 7/41001/ 41/ 43/8 3/81/ 81/80011/21/21/41/41/41/40101/41/41/81/8 3/83/8c - z .000 5/4 M 5 3/8 3 M 9 9 M4888由单纯形表计算结果可以看出，。4 0且a44 000010101J0c 基 bxxxxxxxxxib1234567891 x 6111-110000651 x - 2-20100-110071 x 002-10000-1109c - z1- 3-1101010j j1 x 6103/2-11001/ 2 -1/241 x 2-20100-1100

10、270 x 001-1/ 20000-1/2 -1/22c - z10- 5/210-10-13j j221 x 3400-113/2 -3/2 1/ 2 -1/23/40 x 2-20100-110030 x 1-11000-1/2 1/2-1/ 2 1/ 22c - z000010101j j2 x 3/4100-1/ 41/ 43/8 -3/8 1/ 8 -1/812 x 7/2001-1/2 1/2-1/4 1/4 1/4 -1/43-1 x 7/4010-1/4 1/4 -1/8 1/8 -3/8 3/82c - z000010101j j“,3 7 7 .第一阶段求得的最优解x*

11、=（4，i，2,o,o,o,o,o,o）t,目标函数的最优值。* =。377因人工变量X X X 0，所以X *=（,二,。,0,0,0,。,0） T是原线性规划问题的基可5794 4 2行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题 的目标函数的系数，进行第二阶段的运算，见下表。c -2-1200000.c基bxxxxxx2x3/4100-1/43/8-1/82x17/2001-1/2-1/41/4-1x：7/4010-1/4-1/8-3/8c - z.0005/4 - 3/8 - 9/8由表中计算结果可以看出， 4 。且也 0J123)，所以原线性规划问题

12、有无界解。(b)解1：大M法 TOC o 1-5 h z 在上述线性规划问题中分别减去剩余变量X ,x ,x ,再加上人工变量x ,x ,x ,得 468579min z = 2x + 3x + x + 0 x + 0 x + Mx - Mx1234567x + 4 x + 2 x 一 x + x = 8123463x + 2x - x + x = 6j 1x , x , x , x , x , x , x , x , x 0123456789其中M是一个任意大的正数。据此可列出单纯形表c jT2-120-M0-M0- M9c基bxxxxxxxMx8142-10102Mx63200-1013c

13、 一2 - 4 M3 - 6 M1 - 2 MMM003x21/411/2-1/401/408Mx7225/20-11/2-1-1/214/5c 一z.5 - 5 m4 20M - 2_1M2M3M _ 32403xx9/5013/5-3/101/103/10 -1/1024/510-2/51/5-2/5-1/52/5c 一0001/21/2M -1/2M -1/24 9由单纯形表计算结果可以看出，最优解X*= (-,-,0,0,0,0,0) t，目标函数的最优解值z* = 2 x 4 + 3 x 9 = 7X存在非基变量检验数 = 0，故该线性规划问题有无穷多最优解。553解2：两阶段法。现

14、在上述线性规划问题的约束条件中分别减去剩余变量X , X ,再加上人工变量X , X ,得第 4567一阶段的数学模型min w = X6 + X7x + 4 x + 2 x - x + x = 8123463x + 2x - x + x = 6j 1X , X , X , X , X , X , X , X , X 0123456789据此可列出单纯形表c JT00000110c b基 bXXXXXXX1x 8142-1010216x 63200-1013c - z.-4-6-211000 x 2x 21/411/2-1/401/40815/20-11/2-1-1/214/5c - z .-

15、5/201-1/213/200 x 9/5013/5-3/101/103/10-1/1002X1 4/510-2/51/5-2/5-1/52/5c - z.0000011一，4 9 八第一阶段求得的最优解X *= (5,5,0,0,0,0,0) t,目标函数的最优值w * = 0。49因人工变量气=X7 = 0，所以官50,0,0,0,0) E原线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的 系数，进行第二阶段的运算，见下表。c -z.231000.c基bXXXXX3XX9/5013/5-3/101/1024/510-2/51/5

16、-2/5c.-0001/21/24 9由单纯形表计算结果可以看出，最优解X*=（5,5，0,0,0,0,0） t，目标函数的最优解值z* = 2 x 4 + 3 x 9 = 7。由于存在非基变量检验数。3 = 0，故该线性规划问题有无穷多最优553解。1.8表 1-23表 1-241.100 x 6891541/1500-215-451c .-z j111500-1715-450尤1x 2x 3x 4x 5x 65x 250/4101015/418/41-10414x36241001-6415414/413xi89/41100-2/41-12411541c .-z j000-45/41-24/

17、41-1141最后一个表为所求。习题二P762.1写出对偶问题(a)mins.t.z - 2 x1 + 2 x2 + 4 x3x1 + 3x2 + 4x3 22x + x + 3x + y 3 0,尤3无约束对偶问题为:maxs.t.w = 2 y + 3 y 2 + 5 y 3 yi +2y2 * y3 23y, + y2 + 4y3 0, y2 31234xi + 7 x2 + 3x3 0, x3 6i232 yi-y 2 + 3 y 3 3、y无约束,y2 02.2(a)错误。原问题存在可行解，对偶问题可能存在可行解，也可能无可行解。(b)错误。线性规划的对偶问题无可行解，则原问题可能无

18、可行解，也可能为无界解。错误。正确。2.6对偶单纯形法 (a)mins.t.z = 4 x +12 x +18 xmins.t.xi+ 3x3 3 5x , x , x 0i123解：先将问题改写为求目标函数极大化，并化为标准形式max z =一4 x -12 x -18 x + 0 x + 0 x12345-xi- 3了3 + x4s.t.-2x -2xx oG = 1, ,5)l i= -3+ x 5 = -5c j -4-12-1800cB 基 b尤1x 2尤3x 4尤50 x 4- 30 x5- 5-10- 31001一 2- 201cj - zj-4-12-18000 x 4- 3-

19、10-310-12 x220110- 2cj - zj-40- 60- 6-18x31101-1033-12 x 22-1101-1332cj - zj-200- 2- 6列单纯形表，用对偶单纯形法求解，步骤如下八、，（3T ，一 最优解为x = 0,1,， 目标值z = 39。I 2）(b)mins.t.z = 5 x1 + 2 x 2 + 4 工3Ml + x 2 + 2 匚 46 工1 + 3x 2x , x , x1233+ 5x 1030解：先将问题改写为求目标函数极大化，并化为标准形式max z = -5x】-2x-4x3 + 0 x4s.t. 123一 3x1 - 七 - 2x3

20、 + x4-6x -3x -5xx加=2,.顼i+ 0 x5= -4+x5= -10列单纯形表，用对偶单纯形法求解-5 2 400CB基bX1X 2X3X 4X50X 4一 4-3-1-2100X5-10-6L 3-501c .-z.-5-2-4000X 4_2-1011- 3- 2X 2102150_1c .-z.-10_20_2-4X3- 2301-31-2X 20-3105-2c .-z.100-20最优解为X =(0,0,2#,目标值Z = 8。2.8将该问题化为标准形式：max z = 2X1 一 x 2 + x3 + 0 x 4 + 0X5X1 +X 2 +X 3+X 4 = 6s

21、.t. 一 x + 2 x + x = 4x0=1, 5 5)s.t.l i用单纯形表求解cjT2-1100C B基bXX 2X 3X 4X50X6111100X54-12001c .- z.2-11000 = 6c B基bXX 2X 3X 4X52X6111100X51003111c .- z.0-3-1-20由于Q 0，所以已找到最优解X * =(6,0,0,0,10),目标函数值z * = 12 j(a)令目标函数max z = (2 + 入)x +(-1+入)x + (1+X ) x11223322 -人1 0，从而人2 1表中解为最优的条件：气-3 0 ,从而而2 3（3）令气=0，

22、将气反映到最终单纯形表中c jT2-11 +人00CB基bxxxxx2x611110 x1003111c j-zj0-3气-1-20表中解为最优的条件：:3-1 0，从而气 1(b)令线性规划问题为max z = 2 x - x + xx + x + x 6 + 人s.t.x + 2 x oG = 1, 3)5i(1)先分析的变化睥=B -iAb = f1I1h1 1使问题最优基不变的条件是b使问题最优基不变的条件是b* + Ab*从而X1 66 + X1、 0110 + X )1(6 、 (2)同理有 I 10 + x l 0,从而 X 2 10*2(c)由于x*= (6,0,0,0,10)

23、代入-x1 + 2 x3 =-6 V 2，所以将约束条件减去剩余变量后的方；程 x + 2 x x=62直接反映到最终单纯形表中cjT2-11000Cb基bxxxxxx2x61111000 x100311100 x-210-2001c .z.0-3-1-200对表中系数矩阵进行初等变换，得cjT2-11000Cb基bxxxxxx2x61111000 x100311100 x-80-1-3-101c .-zj0-3-1-200cjT2-11000c基b%B1234562%1031230%0130%2230830231%0%0%1/301851cz.000jj333因此增加约束条件后，新的最优解为

24、气=10， %=3， x5=22，最优值为 282.12(a)线性规划问题max z = 3x1 + %2 + 4%36%1 + 3%2 + 5%3 45 s.t. 3%1 + 4%2 + 5%3 0单纯形法求解c B基 b%1% 2% 3% 4%50% 4450%5306351034日01c . - z .314000% 4154%36h -101 13101555c . - z .3 旦 004555%15%331101 1333011-1-551_3最优解为 X，X2,七)关，0，3)， 目标值z = 27。(a)设产品A的利润为3 +人，线性规划问题变为max zmax z =G +

25、&1 +x 26x1 + 3x2 + 5x3 45s.t. 3x1 + 4x2 + 5x3 0单纯形法求解基b尤1x 2x 3x 4尤5x4563510 x53034kJ01c . 一zj3 +人1400 x 415bJ-101-1尤363410ic . 一zj3 + A1100_4x151-30i-:x 33011-52c . 一zj0-2 + f01 X-5 - 33 X一一 + 5 3为保持最优计划不变，应使-2 + -，-1 -1人，-3 +1人都小于等于0，解得-3 X 9。35 35 355(b)线性规划问题变为max z = 3x1 + x2 + 4x3 + 3x46x1 + 3

26、x2 + 5x3 + 8x4 45s.t. 3x1 + 4x2 + 5x3 + 2x4 s.t. 0单纯形法求解c基b尤1x 2xx 4尤5x 60尤54563fe8100 x63034201c .- z.3143000 x 4153-1061-14x3634120c .- z.311070_43尤151-30123- 34x33011_4-52c .- z.0 -205-!_30 x 452-*016-*4x352131510-土c .- z.- w291500- 土_12一 30此时最优解为(x1, x2, x3 )=(0,0,5),目标值z = 20，小于原最优值，因此该种产品不值得 生

27、产。(c)设购买材料数量为y，则规划问题变为max z = 3x1 + x2 + 4x3 一 0.4y6x1 + 3x2 + 5X3 45s.t. 3x1 + 4x2 + 5x3 一 y 0I 1, 2, 3J单纯形法求解c B基b尤1x 2x 3yx 4尤50 x5456350100 x630345-101c .-z.314_2000 x 415b-1011-14尤36341- 505c .-z.311020_43尤151-i011-3此时最优解为(x1,x2,x3,y)=(0,0,9,15),目标值z = 30，大于原最优值，因此应该购进原 材料扩大生产，以购材料15单位为宜。第三章3.1

28、 表 3.36产地 销地、B1B2B3B4产量A198121318A21010121424A38911126A41010111212销量614355用vogel法求解得XB1B2B3B4A A1144A224A360A411用位势法检验，把上表中有数字的地方换成运价B1B2B3B4UiA18138A2128A38117A411127Vj1045令 v1=1则 u1+v2=8所以u3=7u1+v4=13v3=4u2+v3=12u4=7u3+v1=8v5=8u3+v3=11u2=8u4+v3=11v2=0u4+v4=12得检验数表B1B2B3B4A100A2121A320A423表中所有的数字均大于等于零，故所求方案为最优方案3.3解：