运筹学(第五版)习题(答案)

1、运筹学习题答案第一章(39页)1.1 用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最 优解、无界解还是无可行解。(1) max z =x1 x25x1+10x2 <50x1 + x2 . 1x2 _4x1 , x2 至 0(2) min z= x1 +1.5 x2x1 +3x2 -3x1 +x2 -2x1 , x2 之 0(3) max z=2x1 +2x2x1 - x2 -1-0.5 x1 +x2 -2x1 , x2 之 0(4) max z=x1+x2x1 - x2 -03x1 - x2 _-3x1 , x2 主 0解：(1)(图略)有唯一可行解，max z=14

2、(2)(图略)有唯一可行解，min z=9/4(3)(图略)无界解(4)(图略)无可行解1.2 将下列线性规划问题变换成标准型，并列出初始单纯形表。资料(1) min z=-3 x1+4x2-2 x3+5x44 x1 - x2 +2 x3 - x4 =-2x1 +x2 +3x3- x4 M14-2 x1 +3x2 - x3 +2x4 -2x1 , x2, x3 >0, x4无约束(2) max s = zk .Pkn mZk - c aik。 i =1 k 4m'、-xk = -1。= 1,n) k 4xik 之0 (i=1 n; k=1,m)(1)解：设 z=- z , x4

3、= x5 - x6,x5, x6 _ 0标准型：Max z =3x1 -4 x2 +2x3-5( x5 - x6)+0 x7+0x8-Mx9-Mx105. t .-4 x1 +x2 -2 x3 + x5 - x6 + x10=2x1 + x2 +3 x3 - x5 + x6 + x7 =14-2 x1 +3 x2 - x3 +2x5 -2 x6- x8 + x9 =2Xi , x2, x3, x5, x6, x7, x8, x9 , Xio -0初始单纯形表：cj T3-42-5500-M-M0iCBXBbXiX2X3xX6X7xxX10-Mx102-41-21-1000120X714113-

4、11100014-Mx2-23-12-20-1102/3-F z4M3-6M |4M-42-3M J3M-55-3M0-M00(2)解：加入人工变量x1, x2 , x3，xn，得:n mMax s=(1/ pk) £ Z £ik xk-Mx1-Mx2-.-M xn i 4 k 4s.t.mx +£ xik =1 (i=1,2,3,n)k=4xk 之0, xi >0, (i=1,2,3- n; k=1,2 .,m)M是任意正整数初始单纯形表：Cj-M-M-M加/ / Pka12/ Pkalm/ Pkani/Pkan2/ Pkamn,0iCBXBbxx2xnx

5、11x12x1mxn1xn2xnm-Mx110011000-MX210100000-Mxn1001000111-snM000a14 +M/ pk*呵4M/ P<a/Pk+MKM%也1.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标函数，确定最优解。(1) max z=2x1+3x2+4x3+7x42x1+3x2 - x3-4 x4=8x -2 x2 +6x37 x4=-3x1 , x2 , X3 , X4 一0(2)max z=5 x1 -2 x2 +3x3-6 x4x1 +2 x2 +3 x3 +4x4 =72 x1 + x2 + x3 +2 x4

6、=3x1 x2 x3 x4 ,0(1)解：系数矩阵A是：2 3-1l _2 6 _7 _令 A=(Pi, P2, E, P4)P与P2线形无关，以(Pi, P2)为基，X, x2为基变量。有 2 x1 +3x2=8+x3 +4x4x1 -2 x2 =-3-6 x3 +7 x4令非基变量x3 , x4 =0解得：x1=1; x2 =2基解X(1)= (1, 2, 0, 0)T为可行解z1 =8同理，以(R, E)为基，基解*出=(45/13, 0,-14/13 , 0)T是非可行解；以(R, R)为基，基解 X=(34/5, 0, 0, 7/5 )T 是可行解，Z3=117/5;以(F2, E)

7、为基，基解 X(4) = (0, 45/16, 7/16, 0)T 是可行解，z4 =163/16;以(P2, P4)为基，基解 X(5)= (0, 68/29, 0, -7/29 )T 是非可行解；以(P4, E)为基，基解 X(6)= (0, 0,-68/31 , -45/31 )T 是非可行解；最大值为 Z3 =117/5;最优解 X(3) = (34/5 , 0, 0, 7/5 )T。(2)解：系数矩阵A是：12 3 4匕 1 1 2.令 A=(Pi, P2, E, P4)P, P2线性无关，以(Pi, P2)为基，有：x1 +2x2 =7-3 x3 -4 x42 x1 + x2 =3

8、- x3 -2 x4令 x3 , x4 =0 得x1=-1/3, x2=11/3基解 X(1)= (-1/3 ,11/3, 0, 0)T 为非可行解;同理，以(R, E)为基，基解*出=(2/5, 0, 11/5, 0)T是可行解Z2=43/5;以(R,R)为基，基解X(3)=(-1/3 ,0,0, 11/6 )T是非可行解；以(P2,E)为基，基解X(4)=(0, 2,1,0)T 是可行解，Z4=-1 ;以(P4,E)为基，基解X(6)=(0, 0,1,1)T是 4=-3;最大值为z2=43/5;最优解为*出=(2/5, 0, 11/5, 0)T。1.4分别用图解法和单纯形法求解下列线性规划

9、问题，并指出单纯形迭代每一步相当于图形的哪一点。(1) max z=2x1 +x23 x1 +5x2 至 156 x1 +2x2 <24x1 , x2 2 0(2) max z=2x1 +5x2x1 E42x2 <123x1 +2x2 <18x，x2 0解：（图略）（1） max z=33/4最优解是（15/4,3/4）单纯形法：标准型是 max z=2 x1 + x2 +0 x3 +0 x45 .t. 3x1 +5x2 +x3 =156 x1 +2 x2 + x4 =24xi, x2, x3, x4 0单纯形表计算：Cj2100.CBXBbXiX2X3X40x3153510

10、50x42462014-z021000x33041-1/23/42Xi411/301/612-z-801/30-1/31X23/4011/4-1/82Xi15/410-1/125/24-z-33/400-1/12-7/24解为：(15/4, 3/4, 0, 0 )TMax z=33/4迭代第一步表示原点；第二步代表 C点(4, 0, 3, 0)T ;第三步代表B点(15/4, 3/4, 0, 0 )T o(2)解：(图略)Max z=34 此时坐标点为(2, 6)单纯形法，标准型是：Max z=2x1 +5x2 +0x3 +0x4+0x5s.t.x1 +x3 =42 x2 + x4=123 x

11、1+2x2+x5=18xi, x2, x3, x4, x5 _0(表略)最优解 X= (2, 6, 2, 0, 0 )TMax z=34迭代第一步得X(1)= (0, 0, 4, 12, 18)T表示原点，迭代第二步得X=(0, 6,1.1 0, 6)T ,第三步迭代得到最优解的点。1.5 以1.4题(1)为例，具体说明当目标函数中变量的系数怎样变动时，满足 约束条件的可行域的每一个顶点，都可能使得目标函数值达到最优。解：目标函数： max z=c1 x1 + c2 x2(1)当G#。时x2=- (c1/a) x1+z/c2其中，k=-C|/c2kAB =-3/5 , kBc =-3kvkBc

12、 时，c1, c2 同号。当C2标0时，目标函数在C点有最大值当。2Y0时，目标函数在原点最大值。kBCYkYkAB 时，C1, c2 同号。当c2 A0,目标函数在B点有最大值；当C2<0,目标函数在原点最大值。kAB Yk Y0 时，c1, c2 同号。当C2标。时，目标函数在A点有最大值当C2Y0时，目标函数在原点最大值。k A0 时，c1 , c2 异号。当c2A0, c1 Y0时，目标函数在A点有最大值；当c2Y0, c1 A0时，目标函数在C点最大值。k= kAB 时，c1, c2 同号当。2M0时，目标函数在AB线断上任一点有最大值当。2Y0,目标函数在原点最大值。k= k

13、BC 时，, c2 同号。当。2：-0时，目标函数在BC线断上任一点有最大值当c2 Y0时，目标函数在原点最大值。k=0 时，c1=0当c2标0时，目标函数在A点有最大值当c2Y0,目标函数在OC线断上任一点有最大值(2)当 c2=0 时，max z= c1 x1gA。时，目标函数在C点有最大值c1 Y0时，目标函数在。峨断上任一点有最大值c1=0时，在可行域任何一点取最大值。1.6 分别用单纯形法中的大M法和两阶段法求解下列线性问题，并指出属于哪类 解。(1) max z=2x1 +3x2-5 x3x1 + x2 + x3 -152 x1 -5 x2 + x3 三 24x1 , x2 &qu

14、ot;(2) min z=2x1+3x2 + x3x1 +4x2+2x3 _8 3x1 +2x2 -6Xi , X2, x3 ' 0(3) max z=10x1+15x2+12x35x1 +3x2 + x3 至9-5 x1 +6x2 +15x3 .152x1 +x2 + x3 -5x1，x2, x3 之 0(4) max z=2x1 - x2 +2x3x1 +x2 +x3 -6-2 x1 +x3 -22x2- x3 -0X , x2, x3 >0解：(1)解法一：大M法化为标准型：Max z=2x1 +3x2 -5 x3-Mx4 +0x5 -M %s.t.x1+x2+x3+x4

15、=72 x1 -5 x2 + x3- x5 + x6=10x1, x2, x3, x5, x4, x6至0 M是任意大整数。单纯形表：cj23-5-M0-MeiCBXbbx又2X3x4x5x6-Mx471111007-M%102-510-115-z17M3M+23-4M2M-50-M0-Mx4207/21/211/2-1/24/72xi51-5/21/20-1/21/2-z2M-100(7/2)M+80.5M-600.5M+1-1.5M-13X24/7011/72/71/7-1/72xi45/7106/75/7-1/71/7-z-102/700-50/7-M-16/7-1/7-M+1/7最优解

16、是：X= (45/7 , 4/7 , 0, 0, 0 )T目标函数最优值 max z=102/7有唯一最优解。解法二：第一阶段数学模型为 min w= X4+ X6S.t.x1 + x2+ x3 + x4 =72 x1-5 x2+ x3- x5 + x6=10x1，x2, x3, x4,x5, x6 >0(单纯形表略)最优解X= (45/7 , 4/7 , 0, 0, 0 )T目标函数最优值 min w=0 第二阶段单纯形表为：cj23-50CbXbbx1x2x3xs3X24/7011/71/72x145/7106/7-1/7-z-102/700-50/7-1/7最优解是X= (45/7

17、, 4/7, 0, 0, 0 )TMax z=102/7(2)解法一：大M法z'=-z 有 max z'=-min (- z) =-min z化成标准形：Max z =-2 x1-3 x2- x3+0x4+0x5-Mx6-Mx7S.T.x1+4 x2+2 x3 - x4 + x6 =43 x1 +2 x2- x5 + x7 =6xi, x2, x3, x4, x5, 4, x7 之0(单纯性表计算略)线性规划最优解X= (4/5, 9/5, 0, 0, 0 , 0)T目标函数最优值min z=7非基变量x3的检验数=0,所以有无穷多最优解。两阶段法：第一阶段最优解X= (4/5

18、, 9/5 , 0, 0, 0, 0 )T是基本可行解，min w=0第二阶段最优解(4/5 , 9/5 , 0, 0, 0, 0 )T min z=7非基变量*3的检验数仃3=。，所以有无穷多最优解。(3)解：大M法加入人工变量，化成标准型：Max z=10 x1+15 x2+12 x3 +0 x4+0 x5+0 x6-M x7s.t. 5x1+3 x2+ x3 + x4=9-5x1+6 x2+15 x3 + x5=152x1+ x2 + x3 - x6 + x7 =5Xi, x2, x3, x4, x5, x6,x7 -0单纯形表计算略当所有非基变量为负数，人工变量 X7=0.5,所以原问

19、题无可行解两阶段法（略）（4）解法一：大M法单纯形法，（表略）非基变量X4的检验数大于零，此线性规划问题有无界解两阶段法略1.7求下述线性规划问题目标函数 z的上界和下界；Max z= c1x1 +c2x2aiiXi ai2X2 -bia2iXi 822X2 b2其中：i Mg M3,4 Me2 M6,8 Mb1M i2 , i0 Mb2 M i4 , i Ma11M3,2 Ma12 M5 ,2 <a21 <4 , 4 <a22 <6解：求Z的上界MaX z=3X1 +6x2s.t. -x1 +2 x2 <122 x1 +4x2414x2, x1 >0加入松

20、弛变量，化成标准型，用单纯形法解的，最优解X= (0, 7/2 , 5, 0 )T目标函数上界为z=21存在非基变量检验数等于零，所以有无穷多最优解。求z的下界线性规划模型：Max Z= x1 +4 x2s.t. 3 x1+5x2M84 x1+6x2 <10X2, Xi - 0加入松弛变量，化成标准型，解得:最优解为X= (0, 8/5 , 0, 1/5 )T目标函数下界是z=32/51.8表1-6是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，a1, a2, a3, d, c1, C2为待定常数，试说明这些常数分别取何值时，以 下结论成立。(1)表中解为唯一最优解；(2)表

21、中解为最优解，但存在无穷多最优解；(3)该线性规划问题具有无界解；(4)表中解非最优，对解改进，换入变量为为,换出变量为X6基bX1X2X3X4XX6X3 d4a10a20X4 2-1-301-10X 3a3-500-41cj -zjc1c200-30解：(1)有唯一最优解时，d>0, QY。，c2Y0(2)存在无穷多最优解时，d>0, c1 <0, C2=0 或 d0, c1=0, c2<0.(3)有无界解时，d>0, c1 <0, a”0且 010(4)此时,有 d>0, c产 0 并且 c1 至 c2, a3>0, 3/a3Yd/41.9某

22、昼夜服务的公交线路每天个时间段内所需司机和乘务员人数如下:班次时间所需人数16点到10点160210点到14点70314点到18点160418点到22点50522点至IJ 2点12062点到6点30设司机和乘务人员分别在各时间区段一开始时上班，并连续上班8小时，问该公 交线路至少配备多少司机和乘务人员。列出线型规划模型。解：设Xk （k=1, 2, 3, 4, 5, 6）为Xk个司机和乘务人员第k班次开始上班建立模型：Min z= x1 + x2 + x3 + x4 + x5 + x6s.t.X1 + X6 -60x1 + x2 -70x2+x3 -60x3+x4 -50x4+x5 -20x5

23、+x6 30xi, x2, x3, x4, x5, x6 -01.10某糖果公司厂用原料 A、R C加工成三种不同牌号的糖果甲乙丙，已知各 种糖果中AB*量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位 加工费用及售价如表所示：原料甲乙丙原料 成本（元/ 千克）每月 限制用量 （千克）A之60%至15%：22000BI"2500C<20%<60%<50%11200加工费0.50.40.3售价3.42.852.25问该厂每月应当生产这三种牌号糖果各多少千克，使得获利最大？建立数学模 型。解:解：设 ,x2,x3是甲糖果中的A,B,C成分，x,，x5,x6是乙糖

24、果的A,8, C成分，xy, x8,刈是丙糖果的A, B, C成分。线性规划模型：Maxz=0.9 x1 +1.4 x2 +1.9 x3 +0.45 x4 +0.95 x5+1.45 x6 -0.05 x7 +0.45 x8 +0.95 x9s.t. -0.4X1+0.6 x2+0.6 x3 M 0- 0.2Xi-0.2 X2+0.8 X3 <0- 0.85X4+0.15 x5+0.15 x6 <0- 0.6X4-0.6 X5+0.4 x6 <0- 0.7x7 -0.5 x8 +0.5 x9 <0Xi + X4+X7 <2000x2 + x5+X8 <250

25、0x3+x6+X9 < 1200Xi,X2,X3,X4,X5,X6,X7,X8,X9-01.11某厂生产三种产品I、口、III 。每种产品经过AB两道加工程序，该 厂有两种设备能完成A工序，他们以A, A2表示；有三种设备完成B工序，分别 为巳，B2, &产品I可以在AB任何一种设备上加工，产品 口可以在任何规 格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品III只能在A2 , 区上加工。已知条件如下表，要求安排最优生产计划，使该厂利润最大化。设备产品设备启效台 时满负荷时的 设备费用IIIIIIA5106000300A2791210000321B168400025

26、0B24117000783B374000200原料费0.250.350.5单价1.252.002.8解:产品1,设A, A2完成A工序的产品”, X2件；B工序时，B,B2, 以完成 B工序的X3, X4, X5件，产品口，设A, A2完成A工序的产品X6 , X7件；B工序 时，B1完成B的产品为X8件；产品111, A2完成A工序的“件，B2完成B工序 的“件；X1 + X2= X3+ X4+ X5建立数学模型：MaX z=(1.25-0.25)*(X1+ x2 )+(2-0.35)*(X6 + X7 )+(2.8-0.5)X9 -(5X1+10 x6 )300/6000-(7x2+9 x

27、7+12 X9 )321/10000-(6 x3+8 x8 )250/4000-(4X4+11 X9 )783/7000-7 X5 *200/4000 s.t5 X1+10 x6 与 60007 x2+9 x7+12 X9 < 100006 x3+8 x8 <40004 x4+11 x9 < 70007 X5 <4000X1 + X2 =X3+ X4+ X5X6 +X7= X8X7 X8 x9Xi, X2, X3, X4, X5, X6,-0最优解为 X= (1200, 230, 0, 859, 571, 0, 500, 500, 324 )T最优值1147.试题：1.

28、 (2005年华南理工大学)设某种动物每天至少需要700克蛋白质、30克矿物 质、100毫克维生素。现有5种饲料可供选择，每种饲料每公斤营养成分的含量及单价 如下表所小：试建立既满足动物生长需要，又使费用最省的选用饲料方案的线性规划模 型。表1 1饲料蛋白质（克）矿物质（克）维生素（量克）价格（元/公 斤）1310.50.2220.510.7310.20.20.446220.35180.50.80.8解题分析：这是一道较简单的数学规划模型问题，根据题意写出约束即可解题过程：min z =0.2x1 0.7x2 0.4x3 0.3x4 0.8x53xi +2x2 +X3 +6x4 +18x5 &

29、gt;700x1 +0.5x2 +0.2x3 +2x4 +0.5x5 >30 st «0.5x1 x2 0.2x3 2x4 0.8x5 -100xi,x2,x3,x4,x5 -0第二章(67页)2.1 用改进单纯形法求解以下线性规划问题。(1) Max z=6x1-2 x2+3x32x1- x2+3x3 _2x1 +4x3 -4X, x2, x3 至 0(2) min z=2 x1 + x23x1 + x2=34x1+3x2 -6x1+2x2 <3x1, x2 -0解：(1)先化成标准型：Max z=6 x1 -2 x2+3x3+0x4+0x5s.t. 2x1-x2+2x

30、3 + x4=2Xi +4x3+x5=4xi, x2, x3, x4,x5 -0令 Bo= ( P4,P5)Xbo= (x4, x5 )T , Cbo =(0,0)No=(P1, P2,E)=2、4.)X N0 = ( xi , x2 , x3 )TCn0=(6,-2,3)，B0i<0非基变量的检验数二一n0=Cn0-Cb0 Bo N0=Cn0 =(6,-2,3)因为xi的检验数等于6,是最大值，所以，xi为换入变量,Q 3B 0 b0 =由日规则得： u=iBJ0Pi/2】3*4为换出变量Bi=(P4,P5) 二,X & = ( xi, x5 ) , Cb =(6,。).Ni=

31、( P4,P2, E),Cni =(0 ,Bi0.5 00.5 b,bi =r包非基变量的检验数因为x2的检验数为1,是正的最大数。所以x2为换入变量;B 0 P2 =-0.50.5由日规则得:=6所以X5是换出变量''2 1)、，, T民=(Pi ,P2)=,xb2 =(x1,X2) ,Cb2=(6,-2).J 0JN2=( P4,P5,P3),XN2=(X4,X5,X3)TCn2=(0, 0, 3), B2-= 0 1 , b2= 4<-1 2 J 6非基变量的检验数 仃n2= (-2, -2, -9)非基变量的检验数均为负数，愿问题已达最优解。取优斛X=即：X= (

32、4,6,0 )T目标函数最优值 max z=12(2)解:Min z=2 x1 + x2+0x3 +MX4 +MX5 +0x6S.T.3x1 + x2+x4 =3 4 x1+3x2- x3 + x5=6x1 +2x2+ x6 =3X, X2, X3, X4, X5,X6 -0M是任意大的正数。(非基变量检验数计算省略)原问题最优解是X= (0.6, 1.2, 0)目标函数最优值：z=12/52.2已知某线性规划问题，用单纯形法计算得到的中间某两步的加算表见表，试将空白处数字填上。cj354000CbXbbX1X2X3X4X5X65X28/32/3101/3000X514/3-4/305-2/3

33、100X620/35/304-2/301cj- zj-1/304-5/300.X215/418/41-10/41X3-6/415/414/41Xi-2/41-12/4115/41cj- zj解:cj354000CbX BbX1X2X3X4X5X65X28/30X514/30X620/3cj - zj.5X280/4101015/414X350/41001-6/413X144/41100-2/41cj - zj000-45/412.3写出下列线性规划问题的对偶问题。(1) min z= 2 x1+2 x2+4 x32x1 +3 x2 +5 x3 _23 x1 + x2 +7 x3 < 3x

34、1+4 x2+6 x3 4 5xi , x2, x3 01 1)解：对偶问题是：Max w=2yi-3 y2 -5 ys.t.2 y1 -3 y2 - y3 -23 yi - y2 -4 y3 - 25 y1-7 y2-6 y3 ,4yi, y2, y3 -0(2)max z= x1 +2x2+3 x3+4 x4-x1 + x2 - x3 -3 x4 =5 6x1 +7x2 +3x3 -5 x4 -8 12x1-9 x2-9 x3+9x4 <20x1, x2 之0; x3 <0; x4 无约束解：对偶问题：Min w=5 y1+8 y3 +20 y4S.t. -y1 +6 y3 +

35、12 y4 - 1y#7y3-9 y4 -2-y1+3y3-9 y4 <3-3y5 y3 +9 y4 =4y1无约束，y3 <0; y420m n(3) min z= * ij1n工 Xij =ai i=1,，m j im工 Xij =bj j=1,n i 4Xij -0解： mn对偶问题：max w= " ai yi +x bj ym j i 1j 1s.t.yi + ym j 三 Cj'yi , ym+ 无约束 i=1,2,.m; j=1,2,.nnMax z=" cjj j 1nZ aijXj Wb , i=1,.，m1Mmj 1 n'、&

36、#39;aijXj =b , i= m1 1,m1 - 2,., m j 1Xj 20,当 j=1 , . , n) <nXj 无约束，当 j= n1 +1,., n解：m ''Min w=二 bj yii 1s.t.m ''Z a/i - Cj j=1,2,3 nii 1m工 ajyi - Cj j= n1+1, n1 +2, .n i 1 ''yi -0 i=1,2 . m1 ''V 无约束，i= mi+1, mi+2.m2.4 判断下列说法是否正确，并说明为什么.(1)如线性规划问题的原文题存在可行解，则其对偶问题也一

37、定存在可行 解。(2)如线性规划的对偶问题无可行解，则原问题也一定无可行解。(3)如果线性规划问题的原问题和对偶问题都具有可行解，则该线性规划问题一定有有限最优解。(1)错误，原问题有可行解，对偶问题可能存在可行解，也可能不存在;(2)错误，对偶问题没有可行解，原问题可能有可行解也可能有无界解； (3)错误，原问题和对偶问题都有可行解，则可能有有限最优解也可能 有无界解；2.5 设线性规划问题1是： nMax z1 =" cjxj j 1 na ajxj Wb , i=1 , 2 , m j 1xj -0, j =1,2.,n* * ， （y1,，ym）是其对偶问题的最优解又设线性规

38、划问题2是nMax z2 二1 cjxjjTnZ aijxj bi + ki , i=1 , 2 , mj 1xj - 0, j = 1,2.,n其中ki是给定的常数，求证:m * max z2 至 max z1 + “ ki yii 1解：证明：把原问题用矩阵表示：Max z1=CXs.t. AX <bX -0b二 ( b , b2 bm )T设 可行解为Xi,对偶问题白最优解Y1 = ( yi, y2ym )已知Max z2 =CXs.t. AX 三 b+kX -0k= ( ki, k2. km )T设可行解为X2,对偶问题最优解是丫2,对偶问题是，Min w=Y(b+k)S.t.

39、YA -CY -0因为其是最优解，所以Y2 (b+k) <Yi (b+k)X2是目标函数z2的可行解，AX2 <b+k ； Y2AX2 <Y2 (b+k)原问题和对偶问题的最优函数值相等，所以不等式成立，证毕。2.6已知线性规划问题Max z= c1x1 c2x2 c3x3pi ja21 1xi+ FI + 产 _a22 _a23 Jxj -0, j =i,5用单纯形法求解，得到最终单纯形表如表所示，要求：(1) 求an ,ai2 ,ai3 ，a21，a22，a23,b1,b2 的值;(2)求GO。的值;XBbx1x2x3x4x5x33/21011/2-1/2又221/210

40、-12c zcjzj-3000-4解：(1)初始单纯形表的增广矩阵是:Ci21a12a13a22a231 0 b10 1 b2最终单纯形表的增广矩阵为1.521010.5-0.5C2 = |0.5 10-12C2是G作初等变换得来的，将C2作初等变换，使得C2的第四列和第五列的矩阵成为C2的单位矩阵。有:a11 =9/2 ;a12=1;a13=4;a21 =5/2 ；a22=1；a23 =2；b =9; b2=5由检验计算得：G =-3;5 = 0=02.7已知线性规划问题Max z=2 x1 + x2+5 x3+6 x4s.t. 2 x1 + x3 + x4 三 82 x1+2 x2+x3+

41、2x4 - 12xj >0, j=1,4.一 、 、_., 、 . * * 、 .对偶变重yi, y2 ,其对偶问题的取优斛是y1二4, y2=1,就应用对偶问题 的性质，求原问题的最优解。解：对偶问题是：Min w=8 y1 +12 y2s.t. 2 y1+2y2 _22 y2 -1yi + y2 -5yi+2 y2 -6yi, y2 - 0互补松弛性可知，如 寅，Y?是原问题和对偶问题的可行解，那么，Y?Xs=0 和YS父=0,当且仅当父，Y?是最优解。设X,Y是原问题和对偶问题的可行解，Ys= " y4 , %, y6)有：X一 一YXS =0;且 YSX=0x5 = x

42、6=0,原问题约束条件取等号，X3=4; X4 =4最优解 X= (0, 0, 4, 4)T目标函数最优值为44。2.8试用对偶单纯形法求解下列线性规划问题。(1) min z= x1 + x22 x1 + x2 -4x1 +7x2 -7x1, x2 -0(2) min z=3 x1 +2 x2 + x3 +4x42 x1 +4 x2+5x3 +x4 -03x1- x2+7x3-2x4 _25 x1+2x2+x3+10x4 , 15x1 , x2, x3, x4 _0解：(D取w=-z,标准形式：Max w=-x1- x2+0x3+0x4s.t.- 2 x1- x2+x3=-4- x1-7 x

43、2 + x4 =-7x1 , x2 , x3 , x4 >0单纯形法求解(略)：最优解：X= (21/13 , 10/13 , 0, 0)T目标函数最优值为31/13。(2)令：w=-z,转化为标准形式：Max w=-3x1-2 x2- x3-4 x4+0x5+0x6+0x7 s.t.- 2 x1 -4 x2-5 x3- x4 +x5 =0- 3 x1 + x2-7 x3 +2x4 +x6 =-2- 5 x1 -2 x2- x3 -6 x4+x7=-15X , x2, x3, x4 , x5 , x6, x7 之 0单纯形法略原问题最优解：X= (3, 0, 0, 0, 6, 7, 0)

44、T目标函数最优值为9。2.9现有线性规划问题max z=- 5 x1+5x2+13x3-x1 + x2+3x3 -2012 x1+4x2+10x3 三 90xi , x2 , x3 之 0先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什 么变化？(1)约束条件1的右端常数20变为30(2)约束条件2的右端常数90变为70(3)目标函数中x3的系数变为8(4) x1的系数向事变为必(5) 增加一个约束条件2 x1 +3 x2+5 x3 W 50(6) 将约束条件2变为10x1+5x2+10x3 -100解：把原问题化成标准型的：Max z=-5 x1+5 x2+13 x3+0 x

45、4+0 x5s.t-x1 + x2 +3 x3+ x5 =2012 x1 +4 x2+10 x3+ x5 =90x1，x2, x3, x4 , x5 之 0单纯形法解得：最优解：X= (0, 20, 0, 0, 10)T目标函数最优值为1000非基变量x1的检验数等于0,原线性问题有无穷多最优解。(1)约束条件日的右端常数变为30有 b =B' b因止匕b' = b+&b 单纯形法解得：最优解：X= (0, 0, 9, 3, 0)T目标函数最优值为117。(2)约束条件C?右端常数变为70有 b=B.：b因此b=b-b单纯形法解得，最优解：X= (0, 5, 5, 0,

46、 0)T目标函数最优值为90。(3) X3的系数变成8, X3是非基变量，检验数小于0,所以最优解不变(4) xi的系数向量变为包%是非基变量，检验数等于-5,所以最优解不变(5)解：加入约束条件。3用对偶单纯形表计算得：X= (0, 25/2 , 5/2 , 0, 15, 0)T目标函数最优值为95。(6)改变约束条件，P3,已P5没有变化，线性规划问题的最优解不变。2.10已知某工厂计划生产I,II,III三种产品，各产品在 ABC设备上加工,数据如下表，设备代号IIIIII每月设备 后效台时A8210300B1058400C21310420单位产品利润/"322.9(1)如何充

47、分发挥设备能力，使生产盈利最大?(2)如果为了增加产量，可借用其他工厂的设备B,每月可借用60台时，租金为1.8万元，问借用是否合算？(3)若另有两种新产品IV,V,其中IV为10台时，单位产品利润2.1千 元；新产品V需用设备A为4台时，B为4台时，C为12台时，单位产品盈利1.87千元。如A,B,C设备台时不增加，分别回答这两种新产品投产在经济上是 否划算？(4)对产品工艺重新进行设计，改进结构，改进后生产每件产品 I ,需要 设备A为9台时，设备B为12台时，设备C为4台时，单位产品利润4.5千元, 问这对原计划有何影响？解：(1)设：产品三种产品的产量分别为，xi, X2, X3,建立

48、数学模型：Max z=3x1+2x2+2.9 x3s.t.8x1+2x2+10x3 <30010x1+5x2+8x3 4002x1+13x2+10x3 <420x1，x2, x3 -0把上述问题化为标准型，用单纯形法解得：最优解：X= (338/15, 116/5, 22/3, 0, 0, 0)T目标函数最优值为2029/15。(2)设备B的影子价格为4/15千元/台时，借用设备的租金为0.3千元每台时。所以，借用B设备不合算。(3)设备V,V生产的产量为x7, x8,系数向量分别为：P7 =(12,5,10)TP =(4,4,12)T检验数% =-0.06 ,所以生产IV不合算，

49、% =37/300,生产V合算。单纯形法计算得：最优解：X= (107/4, 31/2, 0, 0, 0, 0, 55/4 )T目标函数最优值为10957/80。(4)改进后，检验数。；=253/300,大于零。所以，改进技术可以带来更好的效益。2.11分析下列参数规划中当t变化时最优解的变化情况。(1) Max z(t)=(3-6t)x1+(2-2t)x2+(5-5t)x3 (t _0)s.t.x1+2x2+x3 M4303 xi +2 X3 -460x1+4x2 三420xi , x2, x3 之 0(2) Max z(t) =(7+2t) x1+(12+t)x2+(10-t) x3 (t

50、 _0)s.t.x1 + x2 + x3 至 202x1+2x2+ x3 -30xi , x2, x3 >0(3) Max z(t)=2x1 + x2 (0 4 三25)s.t.x1 Ml0+2tx1 + x2 - 25-tx2 Ml0+2tx1 , x2 之0(4) Max Z(t) =21x1+12x2+18x3+15x4 (0 -t -59) s.t.6 x1+3 x2+6 x3 +3x4 - 30+t6x1-3 x2+12x3+6x4 工78-t9x1+3x2-6 x3+9x4 - 135-2t解：(1)化成标准形式：Max z(t)=(3-6t)xi +(2-2t)X2 +(5-5t)X3+0x4+0 x5+0xQ