运筹学课后习题答案

1、第一章线性规划由图可得：最优解为2、用图解法求解线性规划：Min z=2xi +X21、一洛 +4x2 兰24% +x2 工85兰捲10X2 一0解：由图可得：最优解 x=1.6,y=6.43用图解法求解线性规划:Max z=5x1+6x22为一x2色2 -2x1 +3x2 兰 2xi, x2 0解:2xi-x2=O-xi+3x2=2z=5x：+6x2由图可得：最优解 Max z=5x 1+6x2, Max z= +:4用图解法求解线性规划：Maxz = 2x1 +X25x1 兰 156xi + 2x2 2 24X+x2 0Xi + x2 = 5Xi = 3由图可得：最大值12, 所以1a =

2、 3、x2=2max Z = 8.5. maxZ = 2 3x2% +2x2 兰 84x 164x2 胡2Xj _0,j =1,22.6将线性规划模型化成标准形式:Min z=xi -2x 2+3x3Xj +x2 +x3 兰7Xi -X2 +X3 3 2_3片 +x2 +2x3 = -5x 0, X20, X3无约束,其中解：令 Z =-Z,引进松弛变量 X4 _ 0，弓I入剩余变量X5 _ 0,并令 X3=X3 -x 3X3_0,x 3- 0Max z =-x i+2x2-3x 3 +3x3捲 +x2 +x3x3 +& =7X1 _X2 +X3X3_Xs =2一3为 +X2 +2x3 = -

3、5* Z0,x2 0,x3它0,x3它0,x4 AO, x5 王07将线性规划模型化为标准形式Min Z =x1 + 2X2+3X3-2% + x2 + x3 兰 93为 +x2 +2x3 K44Xi 2x? 3X3 = 6Xi 0, X2 KO, X3无约束-解：令Z = -z，引进松弛变量X4亠0,引进剩余变量X5亠0,得到一下等价的标准形式。-2为 + x2 + x3 + & = 9一3为 + x2 + 2x3 - x5 = 44xi -2x2 -3x3 = -6Xi 0,-X 3X2 = -X 2X3=X3Z = -min Z = -x i-2x 2- 3x3-2片 _ x2 + x3

4、 _ x3 + & = 9 _3% -x2 +2（x3 _x3 ）-x5 =44% +2x2 3（x3 x； ）= 68.maxZ=3x 1 - 3x2 4x33X|4x2 5x3 x4 = 406x1 4x2 3x3 x5 =66Xj 兰0,j =1,2,3,4,5Cj334000 iCBXBbx1x2x3x4x50X4403451080X5606430120cj334004x383/54/511/5040/30x54221/58/50-3/5160/7c j3/5-1/50-4/504x3204/714/35-1/73x11018/2101/75/21c j0-3/70-31/35-1/7

5、最优解为(10,0,2,0,0 )，目标函数maxZ=389用单纯形法求解线性规划问题:Max Z =70x i +120X29xi +4x2 兰 360*4% +6x2 兰 2003x1 +10x2 300解:Max Z =70xi+120x29xi +4x2 +X3 =3604x1 6x2 X4 二 2003x10x2 x5 = 300单纯形表如下cjclc2cBkBbxlx2x3x4x50x3360941000k4300460100x5300310001Oj0701200x32407. 8010-0. 40202,2001-0. 6120x2300. 31000, 1Oj36003400

6、0-120x3169. 09001-1.60. 9970xl9. 091000. 45-0. 28120x227.27010-0,140. 18Oj2903. 7000-14.1-14Max Z =3908.lO.max Z = 4x1 3x22x, +2 x2 兰 30005x| +2.5x2 兰4000x1 0,j =1,2,3, 4,5Cj430000 iCBXBbx1x2x3x4x50X330002210015000X4400052.50108000X550010001500Cj-Zj43000G =c1 -z =4-(0 2 0 5 0 1)=4-2 =c2 Z2 =3(0 2+0

7、2.5+0 0) = 3 检验数0,max(；一，二2) =max(4,3) =4,.对应的x1为换入变量./ 漏=锂0,4000,500=500x5为换出变量.V 251minCj430000 iCBXBbx1x2x3x4x50X320000210-20X4150002.501-50X150010001Cj-Zj0000-4-非基变量检验数 乞0,得到最优解：X1 =500,X2 =0,X3 = 2000,X4 =1500必=0,目标函数的 maxZ=41-乙=4-(0 2 0 5 0 1)=4 500 3 0 = 2000.11.解：（1）引入松弛变量 X4, X5, X6,将原问题标准化

8、，得max Z=10Xi+6X2+4X3X 计 +X3+X=100*10 X 计 4%+5X3+Xs=600一 2 X1+2+6X3+X5=300%,X 2,X3,X 4,X5,X6 0得到初始单纯形表:C1064000CBXbbX1X2X3X4XsX600X41001111001000X56001045010600X6300226001150cz1064000(2)其中 p 1 =C1-Z1=10-( OX 1+0X 10+0 X 2) =10,同理求得其他根据p max =max10,6,4=10,对应的X1为换入变量，计算0得到,0 min =min100/1,600/10,300/2=

9、60,X5为换出变量，进行旋转运算。（3）重复（2）过程得到如下迭代过程C1064000CBXbbX1X2X3X4XsX600X44003/51/21-1/100200/310X16012/51/201/1001500X618006/5501/51150C-乙02-10-106X2200/3015/65/3-1/60200/310X1100/3101/6-2/31/601500X6100004-201150C-Zj00-8/3-10/3-2/30p j w 0，迭代已得到最优解，X*= (100/3 , 200/3 , 0, 0, 0, 100)Z =10 X 100/3+6 X 200/3+

10、4 X 0 =2200/3。12解：(1)引入松弛变量 X3, X4, X5将原问题标准化，得max Z=2Xi+X2 5X2+Xb=15 0得到初始单纯形表:C21000CBXbbX1X2X3X4X500X31505100-0X4246201040X55110015CZ21000(2) 其中 p 1 =Ci-Zi=2- (0X 1+0X 10+0X 2) =2,同理求得其他 根据p max =max2,1,0=2,对应的X为换入变量，计算B得到，0 min =min-,24/6,5/1=4, X4为换出变量，进行旋转运算。(3) 重复(2)过程得到如下迭代过程C106400CBXbbX1X2

11、X3X4X500X3150510032X1411/301/60120X5102/30-1/613/2C-乙01/30-1/300X315/20015/4-15/22X117/21001/4-1/21X23/2010-1/43/2C-Zj000-1/4-1/2p j w 0，迭代已得到最优解，X*= (7/2 , 3/2 , 0, 0, 0)Z =2 X 7/2+3/2 =17/213解：引入松弛变量 X3、X4,约束条件化成等式，将原问题进行标准化，得：Max Z=2.5Xi+Xz3X1+5X2+X3 =155X 计2X2 +X 4=10X1,X2,Xs,X4 0(1 )确定初始可行基为单位矩

12、阵I = P 3,P4,基变量为X3,X4,X5,非基变量为X1,X2 ,则有:Max Z=2.5X 1+3X2X3=15-3X1-5X2s.t X4=10-5X1-2X2Xi 0, j=1 , 2, 3, 4Cj2.5100CBXBbX1x2x3x4a0x315351050x41052 012Cj _Zj2.5100将题求解过程列成单纯形表格形式，表1由上述可得，将x1替换为&表2，单纯形迭代过程Cj2.5100CBXbbxX2X3x4e0x39019/51-3/545/192.5x212/501/55Cj _Zj0000.5非基变量检验数C3 =0,二4 = -?得到该线性规划另一最优解,

13、* 20x =( W45忌，0,0)，Z=5,由表2可得，将x,替换为X3Cj2.5100CBXbbX1X2X3X4Q45531X201219191920252.5x.101919191Cj-Zj000-2表3最终单纯形表该线性规划具有无穷多个解14.用单纯形法求解线性规划问题:max z = 2xi x， 5x2 兰 156xi + 2x2 兰 24 s.t.| x1 X2 _ 5xi _ 0, X2 _ 0解:(1)将原问题转化为标准形式，得max z = 2xi X2 0x3 0x4 0x55X2 + X3=156xi+2x2+X4=24s.t.xiX2X5 = 5xi _ 0, X2

14、_ 0, X3 _ 0, X4 _ 0, X5 _ 0(2)建立单纯性，并进行迭代运算G210000C8XbXX2X3X4X50X31505100一0X424101040X55110015C-Zj210000X3150510032X411/601/60240X5105/60-1/616/5C-乙02/30-1/300X390011-62X19/51001/5-1/51Xa6/5010-1/56/5Cj-Zj000-1/5-4/5(3)得到最优解 x*=(199 , 5 ,9 ,0 ,0)T，z*=4415.用单纯形法求解线性规划问题:maxz = xi X2xi -2X2 兰 2,_ 2xi

15、+ X2 兰 2 st.-xiX2 空 4xi _ 0, X2 _ 0解：(i)将原问题转化为标准形式，得maxz = Xi X20x30x40x5xi 2x2 + X3=2,2xi ；：; x2x4=2st.-XiX2X5= 4Xi _ 0, X2_ 0, X3_ 0, X4_ 0, X5_ 0(2)建立单纯性，并进行迭代运算C2i0000C8XbXiX2X3X4X50X2ii2i0020X42-2i0i0-0X54-ii00i-C-乙1i000iX2i-2i000X460-32i00X560-ii0iC-乙03-i00本例第二个单纯形表中，非基变量 X对应的检验数d 一0,并且对应的变量系

16、数 ai,2 0(1)得到初始单纯形表:C24000CBXbbX1X2XX4X500X381210040X4410010-0X53010013C-Zj24000(2)重复(1)过程得到如下迭代过程C106400CBXbbXX2XbX4X500X321010020X441001044X2301001-C-Zj2000-42X12101000X4200-1104X2301001Cj-Zj00-200P 5 = 0 , p 3 0Max z=3x1+5x2x1 w 4标准化并且引入松弛变量2x2 w12、3x1+2x2 w18x1 0 x2 0Cj35000CbXbbX1X2X3X4X500X341

17、0100/0X4120【2】01060X518320019d j350000X34101005X260101/200X56300-11d j000-5/20非基变量（T j w 0,得到最优解，其中 x仁0, x2=6, x3=4.x4=0 , x5=6最优解 Max Z=3*0+5*6=30其中，有非基变量d仁0,所以有无穷多个解18、解：化为标准形式：MaxZ =-5X1-2X2-4X33X1+X2+2X3-X4=46X1+3X2+5X3-X5=10X1,x2,x3,x4,x5=0增加人工变量x6,x7,得到：MaxZ =-5X1-2X2-4X3-MX6-MX73X1+X2+2X3-X4+

18、X6=46X1+3X2+5X3-X5+X7=10X1,x2,x3,x4,x5=0大M法求解过程如下：cj-5-2-400-M-M0 iCBXBbX1X2X3X4X5X6X7-MX64312-10104/3-MX7106350-1015/3cj-zj-5+9M-2+4M-4+7M-M-M00-5X14/311/32/3-1/301/30-MX720112-1-211cj-zj0-1/3+M-2/3+M-5/3+2M-M5/3-3M0-5X15/311/25/60-1/601/610/30X4101/21/21-1/2-11/22cj-zj01/21/60-5/6-M5/6-M-5X12/3101

19、/3-11/31-1/3-2X220112-1-21cj-zj00-1/3-1-1/31-M1/3-M最优解为 X1*=2/3,X2*=2,X3*=0最优目标函数值 min Z=22/319、解:化为标准形式：maxZ=-540x1-450x2-720x33x1+5x2+9x3-x4=709x1+5x2+3x3-x5=30X1,x2,x3,x4,x5=0增加人工变量x6,x7,得到：maxZ=-540x1-450x2-720x3-Mx6-Mx73x1+5x2+9x3-x4+x6=709x1+5x2+3x3-x5+x7=30X1,x2,x3,x4,x5=0大M法求解过程如下：cj-540-450

20、-72000-M-M0 iCBXBbX1X2X3X4X5X6X7-MX670359-101070/3-MX730(9)530-10130/9cj-zj12M-54010M-45012M-72-M-M000-MX660010/3(8)-11/31-1/32.5-540X110/315/91/30-1/901/910cj-zj0-150+10M/38M-540MM/3-600-M/3+60-720X315/205/121-1/81/241/8-1/2418-540Xi5/61(5/12)01/24-1/8-1/241/82cj-zj01250135/-475/12135/2-M75/2-M2-72

21、0X320/3-1011/61/61/6-1/6-450X2212/5101/10-3/10-1/103/10-360-450-7207515-75-155700-18000-75-1575-M15-M最优解为 X*=（0,2,20/3,0,0）最优目标函数值 min Z=570020解：先将其化成标准形式，有max z =- 3 x1+X3+OX4+OX5广X1 + X2 + X3+X4 =4(a)-2x1+ x2 - x3-X5=1( b)3X2 +X3=9( c)X1，X2，X3，X4，X5 色 0这种情况可以添壬加两列单位向量F6，H ,连同约束条件中的向量P4构成单位矩阵P4 P 6

22、 P 71 0 00 1 0J_r0 0 1P6, P7是人为添加上去的，它相当于在上述问题的约束条件（b）中添加变量x6，约束条件（c）中添加变量x7，这两个变量相应称为人工变量。由于约束条件（b）（ c）在添加人工变量前已是等式，为使这些等式得到满足，因此在最优解中人工变量取值必须为零。为此，令目标函数 中人工变量的系数为任意大的负数，用“-M”代表。添加人工变量后数学模型变为max z = -3 Xi+X3+O X4+OX5 - M - Mx?X1+ x2 + x3 + x4=43-2X! + X2- X3X5+X6 =1X2+X3X7=9Xi ,X2 ,X3 , X4 ,X ,X6 ,

23、X7 _ 0得到初始可行解 X 0 =(0,0,0,4,0,1 ,9)，并列出初始单纯形表。在单纯形法迭代运算中,可当作一个数学符号一起参加运算。检验数中含 M符号的，当M的系数为正时，该检验数为正;当M的系数为负时，该检验数为负。求解过程见下表c j-30100-M-MCb基bXX2X3X4X 5X6X70X441111000-MX61-MX79-21-10-1100310001Cj -乙-2M-34M 10-M000X4330211-100X21-21-10-110-MX760403-31Cj-Zj6M-304M+103M-4M00X400001-1/2-1/2-1/20X23-3X110

24、11/30001/3102/301/2-1/21/6Cj -乙00303/2-M-3/2-M+1/20X400001-1/21/2-1/20X25/2-1/2100-1/41/41/41X33/23/20103/4-3/41/4Cj-Zj-9/2000-3/4-M+3/4 -M-1/4最优解为(0, 5/2，3/2)21、解：将原问题转化为标准型Maxz=3x1+2x22x1+x2+x3=2s.t. 3x1+4x2-x4=12Xi0, i=1,2,3,4然后添加人工变量x5，将原线性规划问题变为Maxz=3x1+2x2-Mx52xl+x2+x3=2s.t. %x1+4x2-x4+x5=12Xi

25、 0, i=1,2,3,4,5取基变量为x3,x5,建立单纯形表，迭代过程如下:Cj3200-M0 iCbXbBX1X2X3X4X50X32211002-MX512340-113Cj-zj3+3M2+4M0-M0Cj3200-M0 iCbXbBX1X2X3X4X50X2221100-MX54-50-4-11Cj-zj3-5M0-4M-M0在单纯形表中，非基变量的检验值都是小于0,而人工变量仍不为 0,则该线性规划无最优解。22、解：假设甲、乙俩种产品产量分别为x1、x2，产品售后的最大利润为 z,则根据题意可建立以下线性规划模型:Max=70x1+120x29x1x2w 360s.t. ”x1

26、+6x2w 2003x1+10x2 w 300Xi0, i=1,223 .解：设甲、乙产品的生产数量应为x1、x2，则x1、x2 _0,设z是产品售后的总利润，贝Vmax z =70%120x2s.t9xH4x2 3604x1 +6x2 2003) +10% 兰300为，x2 Z 024.解：设甲、乙两种产品的生产数量为x1, x2,设z为产品售后总利润，则 max z=4x1 3x2s.t.2& +2x2 30005X1 +2.5X2 兰4000|X1 兰 500X1,X2 兰025.设X1、X2、X3分别为产品 A、B、C的产量，则数学模型为max Z =10x1 14x2 12x31.5

27、x1 +1.2x2 + 4x3 兰 25003X1 +1.6X2 +1.2X3 兰 1400150 兰 X1 兰 250*260 兰 X2 兰 310120 兰 X3 兰 130X1, X2, X3 K 026设xi，x2分别为产品A B的产量，x3为副产品C的销售量，X4为副产品C的销毁量, 有X3+X4 = 2x2, Z为总利润，则数学模型为maxZ =3xi 7x2 2X3-X4x1 +2x2 兰112x3x2 兰 17I-2X2 X3 X4 = 0X3 w 13Xj 0,j =123,427.设生产四种产品分别为X1,X2XX4,则应满足的目标函数为max=2X+3X2+X+X4满足的

28、约束条件为f 0.5X 1+3X2+Xb+0.5X4 18002X1+Xz+Xb+ X4 28000.5X1+0.5X2+Xb+X4 18003X计 Xa+2+3X4 1000匕2600X3 500X4 40028. 设X1=A出售的数量，X2=A在第二车间加工后的出售数量,X 3=B的出售数量，X4=B在第三车间加工后的出售数量，X 5=第一车间所用的原料数量目标函数为 maxZ=8X+9.5X2+7X+8Xi 2.75X5满足的约束条件为 X 5 1000003X2+2X+1.5X5 029, 解：现在我们对本问题定义三种不同形式的决策变量，从而从不同的途径来构建模型（1）设工厂第j季度生

29、产产品Xj吨首先，考虑约束条件：第一季度末工厂需交货20吨，故应有x1=20;第一季度末交货后积余（X1-20 ）吨；第二季度末工厂需交货20吨，故应有 x1-20+x2=20 ;类似地，应有XX2-40，x3_30 ；第四季度末供货后工厂不能积压产品，故应有X! x2 x 70 x4 =10 ；又考虑到工厂每个季度的生产能力，故应有0 _ Xj _ aj 其次，考虑目标函数：第一季度工厂的生产费用为15.0为，第二季度工厂生产的费用包括生产费用14x2及积压产品的存贮费 0.2（花-20）；类似地，第三季度费用为15.3x3 - 0.2（x1 x2 -40），第四季度费用为 14.8x4 0

30、.2（x1 x2 x 70）.工厂一年的费 用即为这四个季度费用之和.整理后，得下列线性规划模型：minz = 15.6捲 14.4x2 15.5x3 14.8x4-26s.t.x1 x2- 40% +x2 +x370w % +x2 +x3 +x4 =80.20 兰 兰30, 0Wx2 兰40, 0 兰 x3W20, 0 兰 x4 兰 10.（2） 设第j季度工厂生产的产品为 xj吨，第j季度初存贮的产品为yj吨（显然， = 0）.因为每季度初的存贮量为上季度存贮量、生产量之和与上季度的需求量之差，又考虑到第四季 度末存贮量为零，故有：X -20*2，y2 X2 -20 = y3，y3 X3

31、-30*4， y4 X4 二10 ；同时，每季度的生产量不能超过生产能力：xj aj ；而工厂四个季度的总费用由每季的生产费用与存贮费用组成，于是得线性规划：min 15.0x1 0.2y2 14x2 0.2y3 15.3x3 0.2y4 14.8x4 s.t.Xjy2 = 20y2 +X2 - y3 =20丫3 十 X3 y4 = 30y4 *X4 =100兰捲兰300兰X2兰400兰x3兰200兰X4兰10 yj -0， j =2，3，4.(3) 设第i季度生产而用于第j季度末交货的产品数量为 为j吨.根据合同要求，必须有：X11 =20，X13 X23 X33 = 30，X12 X22

32、二 20，X14X24X34X44 =1.又每季度生产而用于当季和以后各季交货的产品数不可能超过该季工厂的生产能力, 故应有：x11 x12x13 Xg 空 30J X22 + X23 + X24 兰 40，X33 + X34 兰 20，X44 兰 10 Cj = di 0.2(j - i)，于是，有线性规第i季度生产的用于第j季度交货的每吨产品的费用 划模型:min z =帖皿仆 +15.2x12 +15.4x13 +15.6x14+14x22 +14.2x23 +14.4x24+ 15.3x33+15.5x34+14.8x44s.t. i .30, 解 设Xjj为i#型飞机被派遣去j#工厂

33、执行任务的架数这相当于希望事件“不摧毁任何工甲方的目标是希望事件“至少摧毁一个工厂”的概率最大 厂”的概率f最小.我们有：f = (1 - 0.10)知(1 - O.2O)X12(1 _o.15)x13 (1 0.08)X21 (1 - 0.16)x22 (1 - 0.12)x23它不是线性的，为此将上式改写为z = log f = x11 log 0.9 x12 Iog0.8 x13 log 0.85 x21 Iog0.92 x22 Iog0.84 x23 log 0.88于是，模型的目标函数为0.0457x110.0969x12 0.0704x130.0362x21 0.0656x22 0

34、.0554x23关于燃料的约束条件为：2 4502Xu2 48022 57022 450丁X212 480飞222 570323xij - 48000x23 100、i壬jA经过整理，即为550x11 580x12 670x13 400x21 420x22 480x23 - 48000.飞机数量约束：33 x1j 40 , x2j 三28 j壬j弓综上所述，本问题的线性规划模型为：max z =0.0457x11 0.0969x12 0.0704x13 0.0362x21 0.0656x22 0.0554x23s.t.f 550心 +580x12 +670x13 +400x21 +420x22

35、 +480x23 兰 48000彳&+xj2+为3兰40x21 +x22 +x23 兰 28I Xj 启0， i =1, 2； j =1, 2，3.第二章线性规划1. 对偶问题和对偶变量的经济意义是什么?从经济学的角度来说，对偶变量反映的是对应的原变量的边际效应，即每增加一单位的原变量使目标函数变化的值，当原变量在目标函数取得最优解时没有用完的情况下，原变量的增加不会改变目标函数的值，此时原变量的边际效应为0,即对偶变量为0,这就是强对偶理论。2. 简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么? 计算步骤见书P-42单纯形法对偶单纯形法保证原问题是可行解的情况下向保证对偶问题是可行

36、解的情况下向原问原理对偶问题可行的方向迭代题可行的方向迭代最优解看非基变量的检验数是否都小于看对偶单纯形表的B-1b是否都大于等于判断等于零零最大一最小比值原则最小一最小比值原则最大：检验数最大的那个非基变量最小：B-1b列数字最小（负数）的那个对迭代为换入变量；应的基变量为换出变量；原则最小：B-1b/aik最小的那个对应的最小：（cj-zi）/alj最小的那个对应的非基变基变量为换出变量量为换入变量3. 什么是资源的影子价格？他和相应的市场价格之间有什么区别？对偶变量yi的意义代表在资源最优利用条件下对第i种资源的估价，这是根据资源在生产作用中做出的贡献而得到的估价，称为影子价格。市场价格

37、是指实际发生的市场交易价格，它是计量财务支出和收入的直接依据；机会 成本或支付意愿就是经济分析中的影子价格。4. 如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的 关系？（1）对偶（min型）变量的最优解等于原问题松弛变量检验数的绝对值（2 ）对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值（3 ）由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似 上述关系。（4）更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量（松弛或剩余）的检验数对应其对偶问题实变量 （对偶变量）的最优解，原问题实变量（决策变量）的 检验数对应其对偶问题虚变量（松弛或剩余变量）的最优解。5.（1） min w=30y 什80y2（2） max w=30yi+80y2+50ysyi +4y2 23yi+2y223yi+4y2 二4yi,y2 0yi-y2+4y32-3yi+5y2+2y302无限制，y3 0,j=1,2,3,4,5Cj-4-2-600CBXbbXiX2X3X4X50X4-24-2-4-8i00X5-8-4-i-40iq-