第二章补充作业习题：用大M 法和两阶段法求解下面LP 问题：⎪⎪⎩⎪⎪⎨⎧≥≥+-≥-+=0,3232s.t.42min 21212121x x x x x x x x z解： 标准化为⎪⎪⎩⎪⎪⎨⎧≥=-+-=----=0,,,3232s.t.42max 432142132121x x x x x x x x x x x x z（1）大M 法引入人工变量65,x x ，得到下面的LP 问题⎪⎪⎪⎪⎨⎧=≥=+-+-=+------=6,,1,03232s.t.42max 642153216521 j x x x x x x x x x Mx Mx x x z j因为人工变量6x 为4>0，所以原问题没有可行解。

（2）两阶段法：增加人工变量65,x x ，得到辅助LP 问题⎪⎪⎩⎪⎪⎨⎧=≥=+-+-=+----=6,,1,03232s.t.max 6421532165 j x x x x x x x x x x x g j初始表因为辅助LP 问题的最优值为4>0，所以原问题没有可行解。

习2.1 解：设1x 为每天生产甲产品的数量，2x 为每天生产乙产品的数量，则数学模型为,5183202..200300max 211212121≥≤≤+≤++=x x x x x x x t s x x z最优解为：()TX 4.8,2.3*=，最优值为：z = 2640。

（1）最优解为：()TX 5.0,5.1*=，最优值为：z = 4.5。

（2）无可行解有无穷多最优解，其中一个为：TX⎪⎭⎫⎝⎛=0,310*1，另一个为：()TX10,0*2=，最优值为：z = 20。

（4）无界解解：A B 资源限额 会议室 1 1 5 桌子 3 2 12 货架 3 6 18 工资2522设1x 为雇佣A 的天数，2x 为雇佣B 的天数，则数学模型为,186312235..2225min 2121212121≥≥+≥+≥++=x x x x x x x x t s x x z最优解为：()TX3,2*=，最优值为：z = 116。

即雇佣A2天，雇佣B3天，共花费116元。

2.4解：m=2，n=5。

约束方程组的系数矩阵为：()54321,,,,1162001411P P P P P A =⎪⎪⎭⎫ ⎝⎛-=，易见()⎪⎪⎭⎫⎝⎛=1001,51P P 是一个基。

令非基变量0,,432=x x x ，由方程组可解出61=x ，85=x ，因此得到基解()()TX8,0,0,0,60=，也是基可行解。

其对应的典式为：,, 86264..325min 51432543214321≥=-++=++++++=x x x x x x x x x x t s x x x x z另外()⎪⎪⎭⎫ ⎝⎛=2011,21P P 也是一个基。

令非基变量0,,543=x x x ，由方程组可解出21=x ，42=x ，因此得到基解()()TX 0,0,0,4,21=，也是基可行解。

其对应的典式为：,, 42121322121..325min 51543254314321≥=+-+=-+++++=x x x x x x x x x x t s x x x x z2.5（1）令11x x '-=，444x x x ''-'=，标准化后有 ()()()()()()()()0,,,,,, 2232224143..5243max 65443216443214432154432144321≥''''=-''-'+-+'--=''-'-+-'--=+''-'-++'--''-'-+-'--='x x x x x x x x x x x x x x x x x x x x x x x x t s x x x x x z化简后有：0,,,,,, 22232224143..55243max 65443216443214432154432144321≥''''=-''-'+-+'-=''-'+-+'-=+''+'-++'''+'-+-'='x x x x x x x x x x x x x x x x x x x x x x x x t s x x x x x z（2）令z z -='，11x x '-=，标准化后有 ()()()0,,, 652..43max 43214321321321≥'-=-+-'-=++'--+-'---='x x x x x x x x x x x t s x x x z化简后有：0,,, 652..43max 43214321321321≥'=+-+'=++'-+'-='x x x x x x x x x x x t s x x x z2.6 （1）,5183202..200300max 211212121≥≤≤+≤++=x x x x x x x t s x x z→j c300 200 0 0 0B CB X b '1x2x3x4x5xi θ0 3x9 0 0 1 -2 [5] 9/5 200 2x3 0 1 0 1 -3 / 3001x5 1 0 0 0 1 5 2100-200300→j c300 200 0 0 0B CB X b '1x2x3x4x5xi θ0 5x9/5 0 0 1/5 -2/5 1 200 2x 42/5 0 1 3/5 -1/5 0 3001x16/5 1 0 -1/5 2/5 0 2640-60-80（2）解：令z z -='，标准化后有,,, 332423..max 432142132121≥=++-=-+-='x x x x x x x x x x t s x x z引入人工变量5x 后有,,,, 332423..max 543214215321521≥=++-=+-+--=x x x x x x x x x x x x t s Mx x x z因为3x 的检验数为1/3>0，但03<j a ，所以原问题无界。

2.8（1）解：标准化后有：,,,,, 84210242..224max 65432163215214321321≥=+++=++=-++++=x x x x x x x x x x x x x x x x x t s x x x z引入人工变量7x后有,,,,,,84 210242 ..224max7654321632152 17 432 17321≥= ++ += ++=+-++-++ =xxxxxxx xxxx xx xx xxxxt sMxxxx z第一个最优解为：()()TX0,0,6,4,0,0,41=由于非基变量3x 的检验数为0，以3x 入基，1x 出基，迭代得到下表第二个最优解为：()()TX0,0,10,4,8,0,02=第三个最优解为：()()()T X X X 0,0,8,4,4,0,2212121=+=（2）解：标准化后有：,,, 71052..1064max 43213214321321≥=++=-+--+='x x x x x x x x x x x t s x x x z引入人工变量65,x x 后有：,,,,, 71052..1064max 65432163215432165321≥=+++=+-+----+=x x x x x x x x x x x x x x x t s Mx Mx x x x z原问题的唯一最优解为：TX ⎪⎭⎫⎝⎛=0,0,0,0,74,745，最优值为-204/7。

（3）解：标准化后有：,,,, 5422032..45max 543213215214321321≥=-+=++=-++++=x x x x x x x x x x x x x x x t s x x x z 引入人工变量65,x x 后有：,,,,,, 5422032..45max 765432173215216432176321≥=+-+=++=+-++--++=x x x x x x x x x x x x x x x x x x x t s Mx Mx x x x z因为最优单纯形表中人工变量7x 为11>0，所以原问题无可行解。

（4）解：标准化后有：,,,,, 02226..22max 6543216325214321321≥=+-+=-+-=-++-+=x x x x x x x x x x x x x x x x t s x x x z 引入人工变量87,x x 后有：,,,,,,, 02226..22max 8765432163285217432187321≥=+-+=+-+-=+-++---+=x x x x x x x x x x x x x x x x x x x x t s Mx Mx x x x z因为非基变量4x 的检验数为5/4>0，但04<j a ，所以原问题有无界解。

（5）解,,,, 101632182..365max 543213215214321321≥=++=++=+++++=x x x x x x x x x x x x x x x t s x x x z 引入人工变量6x 后有：,,,,, 101632182..365max 654321632152143216321≥=+++=++=+++-++=x x x x x x x x x x x x x x x x x t s Mx x x x z原问题的唯一最优解为：()TX 0,0,4,4,0,6=，最优值为42。

2.9证明：()()()()()()()()()()()()()()()()是最优解。

所以显然而就是最优解，则，，若能证明而且满足约束条件个不同的最优解是X X X bb b AXXA AX z z zCXXC CX X X b AX z CX kj X b AX AX AX z CX CX CX k X X ki i i ki iki i ki i i k i i i ki i ki i ki i i ki i i j k k k 00,,1,0,,1111101010110210211≥===========≥===≥========∴∑∑∑∑∑∑∑∑∑=========ααααααααα2.12解：（1）由最终表得到TX ⎪⎭⎫ ⎝⎛=0,0,23,2,0)1(，以4x 入基，3x 出基可得到()TX 0,3,0,5,0)2(=()TTT X X X⎪⎭⎫ ⎝⎛=+⎪⎭⎫ ⎝⎛=+=0,23,43,27,00,3,0,5,0210,0,23,2,0212121)2()1()3( （2）由最优单纯形表可以知道原问题求max ，其初始基变量为54,x x ，最优基的逆阵为⎪⎪⎭⎫⎝⎛--=-2121211B。