运筹学课后习题答案

第一章线性规划1、由图可得：最优解为2、用图解法求解线性规划：Minz=2x1+x201058244212121xxxxxx解：由图可得：最优解x=1.6,y=6.43用图解法求解线性规划：Maxz=5x1+6x20,23222212121xxxxxx解：由图可得：最优解Maxz=5x1+6x2,Maxz=+4用图解法求解线性规划：Maxz=2x1+x20,5242261552121211xxxxxxx由图可得：最大值35121xxx，所以2321xxmaxZ=8.1212125.max23284164120,1,2maxZ.jZxxxxxxxj如图所示，在（4，2）这一点达到最大值为26将线性规划模型化成标准形式：Minz=x1-2x2+3x3无约束321321321321,0,052327xxxxxxxxxxxx解：令Z’=-Z,引进松弛变量x40，引入剩余变量x50，并令x3=x3’-x3’’,其中x3’0,x3’’0Maxz’=-x1+2x2-3x3’+3x3’’0,0,0'',0',0,05232'''7'''5433213215332143321xxxxxxxxxxxxxxxxxxx7将线性规划模型化为标准形式MinZ=x1+2x2+3x3无约束，321321321321,00632442392-xxxxxxxxxxxx解：令Z’=-z，引进松弛变量x40,引进剩余变量x50,得到一下等价的标准形式。,0,,,0632442392-542132153214321xxxxxxxxxxxxxxxx2’=-x2x3=x3’-x3’’Z’=-minZ=-x1-2x2-3x3632442392-''3'3215''33'214''3'3'21xxxxxxxxxxxxxx123123412358.maxZ=3x3434540643660,1,2,3,4,5jxxxxxxxxxxxjCj33400θiCBXBbx1x2x3x4x50X4403451080X5606430120σj334004x383/54/511/5040/30x54221/58/50-3/5160/7σj3/5-1/50-4/504x3204/714/35-1/73x11018/2101/75/21σj0-3/70-31/35-1/710,2,max.最优解为（0，0,0），目标函数Z=389用单纯形法求解线性规划问题：MaxZ=70x1+120x23001032006436049212121xxxxxx解：MaxZ=70x1+120x23001032006436049521421321xxxxxxxxx单纯形表如下MaxZ=3908.1212121123453451231241510.max432+2300052.54000500,0,,(,,0)22300052.5+40005000,1,2,3,4,5jZxxxxxxxxxxxxxxxxxxxxxxxxj解：引入松弛变量Cj43000θiCBXBbx1x2x3x4x50X330002210015000X4400052.50108000X5500[1]0001500Cj-Zj43000111222121min5min4(020501)43(02+02.5+00)3,)max(4,3)4,30004000500,,500,251czczxx检验数0,max(对应的为换入变量.为换出变量.Cj43000θiCBXBbx1x2x3x4x50X320000210-20X4150002.501-50X150010001Cj-Zj0000-4123451110500,0,2000,1500,0,4(020501)4500302000.xxxxcz非基变量检验数，得到最优解：x目标函数的maxZ=411.解：（1）引入松弛变量X4，X5，X6，将原问题标准化，得maxZ=10X1+6X2+4X3X1+X2+X3+X4=10010X1+4X2+5X3+X5=6002X1+2X2+6X3+X6=300X1,X2,X3,X4,X5,X6≥0得到初始单纯形表：Cj1064000CBXBbX1X2X3X4X5X6θ000X4X5X61006003001[10]214215610001000110060150Cj-Zj1064000（2）其中ρ1=C1-Z1=10-（0×1+0×10+0×2）=10，同理求得其他根据ρmax=max{10,6,4}=10,对应的X1为换入变量，计算θ得到，θmin=min{100/1,600/10,300/2}=60,X5为换出变量，进行旋转运算。（3）重复（2）过程得到如下迭代过程Cj1064000CBXBbX1X2X3X4X5X6θ0100X4X1X64060180010[3/5]2/56/51/21/25100-1/101/101/5001200/3150150Cj-Zj02-10-106100X2X1X6200/3100/31000101005/61/645/3-2/3-2-1/61/60001200/3150150Cj-Zj00-8/3-10/3-2/30ρj≤0，迭代已得到最优解，X*=（100/3，200/3，0，0，0，100）T，Z*=10×100/3+6×200/3+4×0=2200/3。12解：（1）引入松弛变量X3，X4，X5将原问题标准化，得maxZ=2X1+X25X2+X3=156X1+2X2+X4=24X1+2X2+X5=5X1,X2,X3,X4,X5≥0得到初始单纯形表：Cj21000CBXBbX1X2X3X4X5θ000X3X4X5152450[6]1521100010001-45Cj-Zj21000（2）其中ρ1=C1-Z1=2-（0×1+0×10+0×2）=2，同理求得其他根据ρmax=max{2,1,0}=2,对应的X1为换入变量，计算θ得到，θmin=min{-,24/6,5/1}=4,X4为换出变量，进行旋转运算。（3）重复（2）过程得到如下迭代过程Cj106400CBXBbX1X2X3X4X5θ020X3X1X5154101051/3[2/3]10001/6-1/60013123/2Cj-Zj01/30-1/30021X3X1X215/217/23/20100011005/41/4-1/4-15/2-1/23/2Cj-Zj000-1/4-1/2ρj≤0，迭代已得到最优解，X*=（7/2，3/2，0，0，0）T，Z*=2×7/2+3/2=17/2。13解：引入松弛变量X3、X4，约束条件化成等式，将原问题进行标准化，得：MaxZ=2.5X1+X23X1+5X2+X3=155X1+2X2+X4=10X1,X2,X3,X4≥0（1）确定初始可行基为单位矩阵I=[P3，P4]，基变量为X3，X4，X5，非基变量为X1，X2，则有：MaxZ=2.5X1+3X2X3=15-3X1-5X2s.tX4=10-5X1-2X2Xi≥0，j=1，2，3，4将题求解过程列成单纯形表格形式，表1由上述可得，将1x替换为4x表2，单纯形迭代过程jC2.5100BCBXb1x2x3x4x03x1504x103510520152jjcz2.5100jC2.5100BCBXb1x2x3x4x03x92.51x2019/51-3/512/501/545/195由表2可得，将2x替换为3x表3最终单纯形表非基变量检验数3=0,4=1-2，得到该线性规划另一最优解，*x=（2019，4519，0,0）,*z=5，该线性规划具有无穷多个解14.用单纯形法求解线性规划问题：0052426155..2max212121221xxxxxxxtsxxz，解：（1）将原问题转化为标准形式，得jjcz0000.5jC2.5100BCBXb1x2x3x4x12x45192.51x2019015193-19102-19519jjcz0001-20,0,0,0,052426155..0002max543215214213254321xxxxxxxxxxxxxtsxxxxxz（2）建立单纯性，并进行迭代运算（3）得到最优解X*=(195,65,9,0,0)T，Z*=44515.用单纯形法求解线性规划问题：Cj21000θC8XBbX1X2X3X4X50X31505100－0X424[6]101040X55110015Cj-Zj210000X3150510032X1411/601/60240X510[5/6]0-1/616/5Cj-Zj02/30-1/300X390011-62X119/51001/5-1/51X26/5010-1/56/5Cj-Zj000-1/5-4/50，042222-..max2121212121xxxxxxxxtsxxz解：（1）将原问题转化为标准形式，得0,0,0,0,042222..000max5432152142132154321xxxxxxxxxxxxxxtsxxxxxz（2）建立单纯性，并进行迭代运算本例第二个单纯形表中，非基变量X2对应的检验数σ0，并且对应的变量系数ai，20（i=1，2，3），根据无界解判定定理，该线性规划问题有无界解（或无最优解）。如果从方程角度看，第二个表格还原线性方程Cj21000θC8XBbX1X2X3X4X50X32[1]1210020X42-21010-0X54-11001-Cj-Zj110001X121-21000X460-32100X560-1101Cj-Zj03-100662322-..2-3max53243232121xxxxxxxxxtsxxz也即：6-62-3-22.325324321xxxxxxxxx令3x=0，则66322.252421xxxxxx此时，若2x进基，则1x，4x，5x会和基变量2x同时增加，同时目标函数值无限增长，所以本题无解。16解：（1）引入松弛变量X3，X4，X5将原问题标准化，得maxZ=2X1+4X2+0X3+0X4+0X5X1+2X2+X3=8X1+X4=4X2+X5=3X1,X2,X3,X4,X5≥0（1）得到初始单纯形表：Cj24000CBXBbX1X2X3X4X5θ000X3X4X584311020[1]1000100014-3Cj-Zj24000（2）重复（1）过程得到如下迭代过程Cj106400CBXBbX1X2X3X4X5θ004X3X4X2243[1]1000110001000124-Cj-Zj2000-4204X1X4X22231000011-10010001Cj-Zj00-200ρ5=0，ρ30，因此有无穷多解，其中一个解为X1=2X2=3maxZ=1617、Maxz=3x1+5x2Maxz=3x1+5x2x1+x3=4x1≤4标准化并且引入松弛变量2x2+x4=122x2≤123x1+2x2+x5=183x1+2x2≤18x1，x2，x3，x4，x5≥0x1≥0x2