第二章作业的参考答案73P 4、将下面的线性规划问题化成标准形式⎪⎪⎪⎩⎪⎪⎪⎨⎧≤≤-≤≤≤-+≥+-+-613032632..2max 21321321321x x x x x x x x t s x x x解：将max 化为 min ，3x 用54x x -代替，则⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥≤≤-≤≤≤--+≥-+---+-0,61303)(26)(32..)(2min 5421542154215421x x x x x x x x x x x x t s x x x x令122+='x x ，则⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥≤'≤≤≤≤---'+≥-+-'----'+-0,70303)()1(26)(3)1(2..)(21min 5421542154215421x x x x x x x x x x x x t s x x x x将线性不等式化成线性等式，则可得原问题的标准形式⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥'=+'=+=++-'+=--+'--+-'+-0,,,,,,,73424332..122min 98765421928175421654215421x 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 x73P 5、用图解法求解下列线性规划问题：（1）⎪⎪⎩⎪⎪⎨⎧≥≤≤≥++212620..3min212121x x x x t s x x解：图2.1的阴影部分为此问题的可行区域。

将目标函数的等值线c x x =+213（c 为常数）沿它的负法线方向T），（31--移动到可行区域的边界上。

于是交点T），（812就是该问题的最优解，其最优值为36。

74P 12、对于下面的线性规划问题，以),,(632A A A B =为基写出对应的典式。

⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=+++-=++-=++-+-6,,1,010 83412 427 23..2min 63215214321321 j x x x x x x x x x x x x t s x x x j 解：先将方程组中基变量632,,x x x 的系数向量化成单位向量⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧=≥-=+---=++-=++++-6,,1,039 47 4 2253 41 21581 21 45..2min 65415215431321 j x x x x x x x x x x x x t s x x x j 利用线性方程组的典式，把32,x x 用541,,x x x 表示，再带入目标函数，则可得原问题相应于基),,(632A A A B =的典式⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎨⎧=≥-=+---=++-=++++---6,,1,039 47 4 2253 41 21581 21 45..8321451min 65415215431541 j x x x x x x x x x x x x t s x x x j75P 16、用单纯形法求解下列线性规划问题：(1)⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤-+≤+-≤+++--=3,2,1,020102603..2min 321321321321j x x x x x x x x x x t s x x x z j解：将此问题化成标准形式⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=+-+=++-=++++--=6,5,4,3,2,1,020102603..2min 632153214321321j x x x x x x x x x x x x x t s x x x z j以654,,x x x 为基变量，可得第一张单纯形表为以1x 为以2x 为进基变量，6x 为离基变量旋转得 解为Tx )0,5,15(*=，最所以最优优值为-35。

注：用单纯形法求解线性规划问题的步骤 Ⅰ、将问题化成标准形式； Ⅱ、找出初始解；Ⅲ、写出第一张单纯形表，并化成典式； Ⅳ、判定和迭代。

① 判定：<1> 最优解（检验数向量0≤ξ）；<2> 问题无界（某个非基变量k x 的检验数0>k ξ，且k x 在典式中的系数向量0≤k A ）② 迭代步骤： <1> 确定进基变量k x （检验数向量T ζ中最大的正分量）；<2> 确定转轴元 rk a （进基变量所在的这一列中的正分量与右端向量中对应元素比值最小的）；1x 2x 3x4x 5x 6x RHSz 4x1x 2x<3> 确定离基变量r x （转轴元所在的这一行对应的基变量）；<4> 迭代计算（利用初等行变换，将转轴元变为1，转轴元所在的这一列其它元素全部变为0）；<5> 用进基变量k x 代替离基变量 r x 。

（3）⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥=++=+-=-+=++-++-=7,6,5,4,3,2,1,06 0 10 2 6 3 ..min 7636143265365321j x x x x x x x x x x x x t s x x x x x z j解：在第三个等式两端同乘以-1，并以7125,,,x x x x 为基变量可得其单纯形表为将第0行的元素化为检验数可得1x2x 3x 4x 5x 6x 7x RHS z 5x 2x1x7x由于4x 的检验数014>=ξ，并且4x 在典式中的系数向量0)0,0,1,0(4≤-=T A ，所以问题无界。

75P 17、用两阶段法求解下列线性规划问题：（2）⎪⎪⎩⎪⎪⎨⎧≥≥+-≥-+=0,3232..42min 21212121x x x x x x t s x x z解：将此问题化为标准形式⎪⎪⎩⎪⎪⎨⎧≥=-+-=--+=0,,,3 2 32..42min 432142132121x x x x x x x x x x t s x x z 添加人工变量65,x x 得到辅助问题z5x 2x1x7x⎪⎪⎩⎪⎪⎨⎧≥=+-+-=+--+=0,,,,,3 2 32..min 6543216421532165x x x x x x x x x x x x x x t s x x g 以65,x x 为基变量，可得辅助问题的单纯形表为把g所在的这一行的元素化成检验数以1x 为进基变量，5为离基变量旋转得1x 2x 3x 4x 5x6x RHS z g5x 6x所以，辅助问题的最优解为Tx )4,0,0,0,0,1(*=，其最优值为04*>=g 。

因此，原问题没有可行解。

（4）⎪⎪⎩⎪⎪⎨⎧≥=+++-=+-+-+-=0,,,14 322 8 24 ..6542max 4321432143214321x x x x x x x x x x x x t s x x x x z解：将此问题化成标准形式⎪⎪⎩⎪⎪⎨⎧≥=+++-=+-++-+-=0,,,14 322 8 24 ..6542min 4321432143214321x x x x x x x x x x x x t s x x x x z添加人工变量65,x x 得到辅助问题1x2x3x4x 5x6x RHS zg1x6x⎪⎪⎩⎪⎪⎨⎧≥=++++-=++-++=0,,,,,1 4 322 8 24 ..min 654321643215432165x x x x x x x x x x x x x x x x t s x x g 以65,x x 为基变量，可得辅助问题的单纯形表为把g所在的这一行的元素化成检验数以4x 为进基变量，5x为离基变量旋转得1x2x 3x 4x 5x 6x RHS zg5x 6x以3x 为进基变量，6x 为离基变量旋转得所以，辅助问题的最优解为T x )0,0,41,0,0,0(='，其最优值为0='g 。

因此，原问题的初始解为T x )41,0,0,0(0=，其第一张单纯形表为以1x 为进基变量，4x 为离基变量旋转得1x2x 3x 4x 5x6x RHSzg4x3x问题的最优解为T x)0,3,0,8(*=，最优因此，原值为31。

76P 18、写出下列线性规划问题的对偶规划：⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤++=++≥++++=为自由变量321321321321321,0,5533622432..42min x x x x x x x x x x x x t s x x x z解：先将此问题化成一般形式⎪⎪⎪⎩⎪⎪⎪⎨⎧≥-≥---=++≥++++=为自由变量321321321321321,0,5533622432..42min x x x x x x x x x x x x t s x x x z所以，其对偶规划为⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=-+≤-+≤-+-+为自由变量231321321321321,0,4564233122..532max ωωωωωωωωωωωωωωωt s1x2x3x 4x RHSz1x 3x77P 20、给定线性规划问题⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=+≤++=0,,3215 2..min 321322131x x x x x x x t s x x z记为（P ）（1）用单纯形算法解P; （2）写出P 的对偶问题D;（3）写出P 的互补松紧条件,并利用它们解对偶D;解：(1) 把问题（P ）化为标准形式⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=+=+++=0,,,32152..min 43213242131x x x x x x x x x t s x x z以31,x x 为基变量，可得到其单纯形表为:把第0行化成检验行，得1x2x 3x 4x RHS z 1x 3x以2x 为进基变量，1x为离基变量，旋转得根据最优化准则知，问题（P ）的最优解为T x )47,25,0(*=, 最优值为 47.(2) 将问题（P ）化为一般形式⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=+-≥--+=0,, 321 52.. min 32123212131x x x x x x x t s x x z ωω因此其对偶问题（D ）为⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤≤+-≤-+-0102121..35max 1221121ωωωωωωωt s(3) 由问题（P ）的最优解为Tx )47,25,0(*=以及互补松紧性定律可得1x2x 3x 4x RHSz 2x3x⎪⎩⎪⎨⎧==+-1212221ωωω解得411=ω ，12=ω. 所以，对偶问题（D ）的最优解为T )1,41(*=ω，最优值为473521=+-ωω.77P 22、用对偶单纯形法解下列问题.（1）⎪⎪⎩⎪⎪⎨⎧=≥≥+-≥++++=.3,2,1,043232..432min 321321321i x x x x x x x t s x x x z i解：引入剩余变量将原问题标准化⎪⎪⎩⎪⎪⎨⎧=≥=-+-=-++++=.5,4,3,2,1,043232..432min 53214321321i x x x x x x x x x t s x x x z i再将约束条件两边同时乘以1-得⎪⎪⎩⎪⎪⎨⎧=≥-=+-+--=+---++=.5,4,3,2,1,043232..432min 53214321321i x x x x x x x x x t s x x x z i以54,x x 为基变量，可得其单纯形表为以5x 为离基变量，1x为进基变量，旋转得为离基变量，2x 为进基变量，旋转以4x 得根据最优化准则知，原问题的最优解为T x )0,52,511(*=, 最优值为528.注：用对偶单纯形方法求解线性规划问题的步骤： Ⅰ、将问题化成标准形式； Ⅱ、找出初始解；Ⅲ、写出第一张单纯形表，并化成典式； Ⅳ、判定和迭代。