第一章线性规划1、由图可得：最优解为2、用图解法求解线性规划：Min z=2x1+x2⎪⎪⎩⎪⎪⎨⎧≥≤≤≥+≤+-1058244212121xxxxxx解：由图可得：最优解x=1.6,y=6.4Max z=5x 1+6x 2⎪⎩⎪⎨⎧≥≤+-≥-0,23222212121x x x x x x解：由图可得：最优解Max z=5x 1+6x 2, Max z= +∞Maxz = 2x 1 +x 2⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤0,5242261552121211x x x x x x x由图可得：最大值⎪⎩⎪⎨⎧==+35121x x x ， 所以⎪⎩⎪⎨⎧==2321x xmax Z = 8.1212125.max 23284164120,1,2maxZ .jZ x x x x x x x j =+⎧+≤⎪≤⎪⎨≤⎪⎪≥=⎩如图所示，在（4，2）这一点达到最大值为26将线性规划模型化成标准形式：Min z=x 1-2x 2+3x 3⎪⎪⎩⎪⎪⎨⎧≥≥-=++-≥+-≤++无约束321321321321,0,052327x x x x x x x x x x x x解：令Z ’=-Z,引进松弛变量x 4≥0，引入剩余变量x 5≥0，并令x 3=x 3’-x 3’’,其中x 3’≥0,x 3’’≥0Max z ’=-x 1+2x 2-3x 3’+3x 3’’⎪⎪⎩⎪⎪⎨⎧≥≥≥≥≥≥-=++-=--+-=+-++0,0,0'',0',0,05232'''7'''5433213215332143321x x x x x x x x x x x x x x x x x x x7将线性规划模型化为标准形式Min Z =x 1+2x 2+3x 3⎪⎪⎩⎪⎪⎨⎧≥≤-=--≥++-≤++无约束，321321321321,00632442392-x x x x x x x x x x x x解：令Z’ = -z ，引进松弛变量x 4≥0,引进剩余变量x 5≥0,得到一下等价的标准形式。

⎪⎪⎩⎪⎪⎨⎧≥≤-=--=-++-=+++,0,,,0632442392-542132153214321x x x x x x x x x x x x x x xx 2’=-x 2 x 3=x 3’-x 3’’ Z’ = -min Z = -x 1-2x 2-3x 3()()⎪⎩⎪⎨⎧-=--+=--+--=+-+-632442392-''3'3215''33'214''3'3'21x x x x x x x x x x x x x x123123412358.maxZ=3x 3434540643660,1,2,3,4,5j x x x x x x x x x x x j ++⎧+++=⎪+++=⎨⎪≥=⎩10,2,max .∴最优解为（0，0,0），目标函数Z=389用单纯形法求解线性规划问题：Max Z =70x 1+120x 2⎪⎩⎪⎨⎧≤+≤+≤+3001032006436049212121x x x x x x解： Max Z =70x 1+120x 2⎪⎩⎪⎨⎧=++=++=++3001032006436049521421321x x x x x x x x x单纯形表如下Max Z =3908.1212121123453451231241510.max 432+230005 2.54000500,0,,(,,0)2230005 2.5+40005000,1,2,3,4,5jZ x x x x x x x x x x x x x x x x x x x x x x x x j =+⎧≤⎪+≤⎪⎨≤⎪⎪≥⎩≥⎧++=⎪+=⎪⎨+=⎪⎪≥=解：引入松弛变量111222121min 5min 4(020501)43(02+0 2.5+00)3,)max(4,3)4,30004000500,,500,251c z c z x x σσσσθ=-=-⨯+⨯+⨯==-=-⨯⨯⨯===∴⎛⎫==∴ ⎪⎝⎭检验数>0,max(对应的为换入变量.为换出变量.123451110500,0,2000,1500,0,4(020501)4500302000.x x x x c z σ≤∴=====∴=-=-⨯+⨯+⨯=⨯+⨯=非基变量检验数，得到最优解：x 目标函数的maxZ=4max Z=10X1+6X2+4X3X1+X2+X3+X4=10010 X1+4X2+5X3+X5=6002 X1+2X2+6X3+X6=300X1,X2,X3,X4,X5,X6≥0得到初始单纯形表：（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）过程得到如下迭代过程ρj≤0，迭代已得到最优解，X*=（100/3，200/3，0，0，0，100）T，Z* =10×100/3+6×200/3+4×0 =2200/3。

max Z=2X1+X25X2+X3=15X1+2X2+ X5=5X1,X2,X3,X4,X5≥0得到初始单纯形表：（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）过程得到如下迭代过程ρj≤0，迭代已得到最优解，X*=（7/2，3/2，0，0，0）T，Z* =2×7/2+3/2 =17/2。

13解：引入松弛变量X 3、X 4，约束条件化成等式，将原问题进行标准化，得： Max Z=2.5X 1+X 23X 1+5X 2+X 3 =15 5X 1+2X 2 +X 4=10 1,X 2,X 3,X 4≥0（1） 确定初始可行基为单位矩阵I=[P 3，P 4]，基变量为X 3，X 4，X 5，非基变量为X 1，X 2，则有：Max Z=2.5X 1+3X 2 X 3=15-3X 1-5X 2 s.t X 4=10-5X 1-2X 2 Xi ≥0，j=1，2，3，4将题求解过程列成单纯形表格形式，表1由上述可得，将替换为表2，单纯形迭代过程1x 4x由表2可得，将替换为表3 最终单纯形表非基变量检验数3σ=0,4σ=1-2，得到该线性规划另一最优解，*x =（2019，4519，0,0）,*z =5， 该线性规划具有无穷多个解14.用单纯形法求解线性规划问题：⎪⎪⎩⎪⎪⎨⎧≥≥≤+≤+≤+=005 2426155..2max 212121221x x x x x x x t s x x z ， 解：（1）将原问题转化为标准形式，得2x 3x⎪⎪⎩⎪⎪⎨⎧≥≥≥≥≥=++=++=+++++=0,0 ,0 ,0 ,0524 2615 5..0002max 543215214213254321x x x x x x x x x x x x x t s x x x x x z（2）建立单纯性，并进行迭代运算（3）得到最优解X*=(195 ,65 ,9 ,0 ,0 )T，Z*=44515.用单纯形法求解线性规划问题：⎪⎪⎩⎪⎪⎨⎧≥≥≤+-≤+-≤+=0，04 2222 - .. max 2121212121x x x x x x x x t s x x z解：（1）将原问题转化为标准形式，得⎪⎪⎩⎪⎪⎨⎧≥≥≥≥≥=++-=++-=+-++++=0 ,0 ,0 ,0 ,04 222 2 ..000max 5432152142132154321x x x x x x x x x x x x x x t s x x x x x z（2）建立单纯性，并进行迭代运算本例第二个单纯形表中，非基变量X 2对应的检验数σ 0，并且对应的变量系数a i ，2≤0（i=1，2，3），根据无界解判定定理，该线性规划问题有无界解（或无最优解）。

如果从方程角度看，第二个表格还原线性方程⎪⎩⎪⎨⎧=++-=++-=++=6 62322 - ..2-3 max 53243232121x x x x x x x x x t s x x z也即：⎪⎩⎪⎨⎧+=+=+=6- 62-3-2 2 .325324321x x x x x x x x x 令3x =0，则⎪⎩⎪⎨⎧+=+=+=6 632 2 .252421x x x x x x 此时，若2x 进基，则1x ，4x ，5x 会和基变量2x 同时增加，同时目标函数值无限增长，所以本题无解。

16解：（1）引入松弛变量X 3，X 4，X 5将原问题标准化，得max Z=2X 1+4X 2+0X 3+0X 4+0X 5 X 1+2X 2+X 3=8 X 1+X 4=4 X 2+X 5=3X 1,X 2,X 3,X 4,X 5≥0 （1）得到初始单纯形表：（2）重复（1）过程得到如下迭代过程ρ5 = 0，ρ3 < 0，因此有无穷多解，其中一个解为X1=2 X2=3 max Z = 16 17、Max z=3x1+5x2 Max z=3x1+5x2x1+ x3=4 x1 ≤4 标准化并且引入松弛变量2x2+ x4=12 2x2≤12 3x1+2x2+ x5=18 3x1+2x2≤18 x1，x2，x3，x4，x5≥0x1≥0 x2≥0非基变量σj≤0，得到最优解，其中x1=0，x2=6，x3=4.x4=0，x5=6 最优解Max Z=3*0+5*6=30其中，有非基变量σ1=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+X6=46X1+3X2+5X3-X5+X7=10X1,x2,x3,x4,x5>=0大M法求解过程如下：最优解为X1*=2/3,X2*=2,X3*=0最优目标函数值minZ=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-Mx7 3x1+5x2+9x3-x4+x6=709x1+5x2+3x3-x5+x7=30X1,x2,x3,x4,x5>=0大M法求解过程如下：最优解为X*=(0,2,20/3,0,0) 最优目标函数值minZ=570020解：先将其化成标准形式，有max z = −31x + 3x +04x +05x 1x +2x +3x +4x =4 （a ） -21x +2x -3x -5x =1 （b ） 32x +3x =9 （c ） 1x ，2x ，3x ，4x ，5x 0这种情况可以添加两列单位向量6P ，P 7 ，连同约束条件中的向量P 4构成单位矩阵 P 4 P 6 P 71 0 00 1 0 0 0 1P 6，P 7是人为添加上去的，它相当于在上述问题的约束条件（b ）中添加变量6x ，约束条件（c ）中添加变量7x ，这两个变量相应称为人工变量。