运筹学第二章作业参考答案(DOC)

1、运筹学第二章作业的参照答案.(DOC)运筹学第二章作业的参照答案.(DOC)20/20运筹学第二章作业的参照答案.(DOC)第二章作业的参照答案P734、将下面的线性规划问题化成标准形式maxx1x22x3s.t.x12x23x362x1x2x330 x131x26解：将max化为min，x3用x4x5代替，则minx1x22(x4x5)s.t.x12x23(x4x5)62x1x2(x4x5)30 x13x26x4,x50令x2x21，则minx1x212(x4x5)s.t.x12(x21)3(x4x5)62x1(x21)(x4x5)30 x130 x27x4,x50将线性不等式化成线性等式，

2、则可得原问题的标准形式1minx1x22x42x51s.t.x12x23x43x5x642x1x2x4x5x74x1x83x2x97x1,x2,x4,x5,x6,x7,x8,x90P735、用图解法求解下列线性规划问题：X2minx13x2法线方向s.t.x1x220等值线6x18（1）12x22o1220X1图2.1解：图2.1的阴影部分为此问题的可行地域。将目标函数的等值线x13x2c（c为常数）沿它的负法线方向（TT1，3）移动到可行地域的边界上。于是交点（12，8）就是该问题的最优解，其最优值为36。注：用图解法求解线性规划问题的步骤比较正确地画出可行地域；确定等值线及其法线方向；由m

3、ax或min确定等值线的移动方向，并将其移动到可行地域的边界上；得出结论。2P7412、对于下面的线性规划问题，以B(A2,A3,A6)为基写出对应的典式。minx12x2x3s.t.3x1x22x3x472x14x2x5124x13x28x3x610 xj0,j1,6解：先将方程组中基变量x2,x3,x6的系数向量化成单位向量minx12x2x3s.t.5x1x31x41x554281x1x21x532425x14x47x5x63924xj0,j1,6利用线性方程组的典式，把x2,x3用x1,x4,x5表示，再带入目标函数，则可得原问题相应于基B(A2,A3,A6)的典式min15x1x3x

4、412485s.t.5xx1x1x541324851xx1x32124525x4x7xx39214456xj0,j1,63P7516、用单纯形法求解下列线性规划问题：minz2x1x2x3s.t.3x1x2x360 x1x22x310(1)x1x2x320 xj0,j1,2,3注（零行元素的获得）：解：将此问题化成标准形式minz2x1x2x3先将目标函数化成求s.t.3x1x2x3x460最小值的形式，再把所x1x22x3x510有变量移到等式左边，x1x2x3x620 xj0,j1,2,3,4,5,6常数移到等式右边。则以x4,x5,x6为基变量，可得第一张单纯形表为变量前的系数为零行对应

5、的元素。x1x2x3x4x5x6RHSz21-10000注意单纯形表x431110060的格式！x51-1201010注：要用记号把x611-100120转轴元标出来以x1为进基变量，x5为离基变量旋转得4以x2为得所以最优优值为x1x2x3x4x5x6z03-50-20 x404-51-30 x11-12010 x602-30-11x1x2x3x4x5z0010122x40011-1x11010122x20130122RHS注：要记住在单-20纯形表的左边，30用进基变量代替离基变量10进基变量，x6为离基变量旋转10 x6RHS3-352-210115215解为x*(15,5,0)T，最2

6、-35。注：用单纯形法求解线性规划问题的步骤、将问题化成标准形式；、找出初始解；、写出第一张单纯形表，并化成典式；、判断和迭代。判断：最优解（查验数向量0）；问题无界（某个非基变量xk的查验数k0，且x在典式中的系数向量A0）kk迭代步骤：确定进基变量xk（查验数向量T中最大的正分量）；确定转轴元ark（进基变量所在的这一列中的正分量与右端向量中对应元素比值最小的）；5确定离基变量xr（转轴元所在的这一行对应的基变量）；迭代计算（利用初等行变换，将转轴元变为1，转轴元所在的这一列其余元素全部变为0）；用进基变量xk代替离基变量xr。minzx1x2x3x5x6s.t.3x3x5x66x22x3

7、x410（3）x1x60 x3x6x76xj0,j1,2,3,4,5,6,7解：在第三个等式两端同乘以-1，并以x5,x2,x1,x7为基变量可得其单纯形表为x1x2x3x4x5x6x7RHSz-11-10-1100 x500301106x2012-100010注：必须先将线性方程组和目标函数化成典式，再用单纯形方法开始判断、迭代！x110000-100将第0行x700100116的元素化为查验数可得6x1x2x3x4x5x6x7RHSz0001010-4x500301106x2012-100010 x110000-100 x700100116由于x4410，并且的查验数x4在典式中的系数向量

8、A4(0,1,0,0)T0，所以问题无界。P7517、用两阶段法求解下列线性规划问题：minz2x14x2s.t.2x13x22（2）x1x23x1,x20解：将此问题化为标准形式minz2x14x2s.t.2x13x2x32x1x2x43x1,x2,x3,x40增添人工变量x5,x6获得辅助问题7mingx5x6s.t.2x13x2x3x52x1x2x4x63x1,x2,x3,x4,x5,x60以x5,x6为基变量，可得辅助问题的单纯形表为x1x2x3x4x5x6RHSz-2-400000g0000-1-10 x52-3-10102x6把g所-110-1013在的这一行的元素化成查验数x1x

9、2x3x4x5x6RHS注：必须先将线z性方程组和目标-2-400000g1-2-1-1005函数化成典式，x52-3-10102才可以开始判x6-110-1013定、迭代！以x1为进基变量，x5为离基变量旋转得8x1x2x3x4x5x6RHSz0-7-1010211310101222x6011-1114222所以，辅助问题的最优解为x*(1,0,0,0,0,4)T，其最优值为g*40。因此，原问题没有可行解。maxz2x14x25x36x4s.t.x14x22x38x42（4）x12x23x34x41x1,x2,x3,x40解：将此问题化成标准形式minz2x14x

10、25x36x4s.t.x14x22x38x42x12x23x34x41x1,x2,x3,x40增添人工变量x5,x6获得辅助问题9mingx5x6s.t.x14x22x38x4x52x12x23x34x4x61x1,x2,x3,x4,x5,x60以x5,x6为基变量，可得辅助问题的单纯形表为x1x2x3x4x5x6RHSz2-45-6000g0000-1-10 x514-28102x6-1234011把g所在的这一行的元素化成查验数x1x2x3x4x5x6RHSz2-45-6000g06112003x514-28102x6-1234011以x4为进基变量，x5为离基变量旋转得10zgx4以x3

11、为x6转得zgx4所以，辅x1x2x3x4x5x6RHS11-1703034242304030022111110182484304011022x1x2x3x4x5x6RHS651973-1008161620000-1-10110131132232164进基变量，x6为离基变量旋助问题的最优解为x3其最优值为g31110(0,0,0,1004,0,0)T88x，40。因此，原问题的初始解为x0(0,0,0,1)T，其第一张单纯形表为4x1x2x3x4RHS65-1003z216x411011322430100 x38以x1为进基变量，x4为离基变量旋转得11x1x2x3x4RHSz0-660-1

12、30-31x11160328x3061123因此，原问题的最优解为x*(8,0,3,0)T，最优值为31。P7618、写出下列线性规划问题的对偶规划：minzx12x24x3s.t.2x13x24x322x1x26x33x13x25x35x1,x20,x3为自由变量解：先将此问题化成一般形式minzx12x24x3s.t.2x13x24x322x1x26x33x13x25x35x1,x20,x3为自由变量所以，其对偶规划为max213253s.t.21223131233241625341,30,2为自由变量123注：要先将问题化成一般形式，再按规则写出它的对偶问题。要记住判断对偶变量是自由变量

13、仍是非负变量12P7720、给定线性规划问题minzx1x3s.t.x12x251x2x332x1,x2,x30记为（P）1）用单纯形算法解P;2）写出P的对偶问题D;3）写出P的互补松紧条件,并利用它们解对偶D;解：(1)把问题（P）化为标准形式minzx1x3s.t.x12x2x451x2x332x1,x2,x3,x40以x1,x3为基变量，可获得其单纯形表为:x1x2x3x4RHSz-10-100 x112015x3011032把第0行化成查验行，得13x1x2x3x4RHSz050182x112015x301103进基变量，x1为离基变量，旋转得以x2为2x1x2x3x4RHS5z40

14、0 x21102根据最优1x3401将问题（P）化为一般形式1744152217化准则知，问题（P）的最优解为4(0,5,7)T,最优值为74x*.244minzx1x3s.t.x12x2511x2x3322x1,x2,x30因此其对偶问题（D）为max5132s.t.112101222110(3)由问题（P）的最优解为x*(0,5,7)T以及互补松紧性定律可得24142101221解得11，21.所以，对偶问题（D）的最优解为*(1,1)T，最优值为4745132.4P7722、用对偶单纯形法解下列问题.minz2x13x24x3s.t.x12x2x33（1）2x1x23x34xi0,i1,

15、2,3.解：引入节余变量将原问题标准化minz2x13x24x3s.t.x12x2x3x432x1x23x3x54xi0,i1,2,3,4,5.再将拘束条件两边同时乘以1得minz2x13x24x3s.t.x12x2x3x432x1x23x3x54xi0,i1,2,3,4,5.以x4,x5为基变量，可得其单纯形表为注：若问题存在一个基本解，并且该解的查验数向量小于等于零，则可使用对偶单纯形方法。特别地，要将问题典式化15x1x2x3x4x5RHSz-2-3-4000 x4-1-2-110-3以x5x5-21-301-4为离基变量，x1为进基变量，旋转得x1x2x3x4x5RHSz0-4-10-

16、14x45110212-12以x4x1131为离基变量，x2为进基变量，旋转102222得x1x2x3x4x5RHSz00981285555x21212015555根据最x171211优化准则知，原问题的最优解为105555(11,2,0)T,最优值为28x*.555注：用对偶单纯形方法求解线性规划问题的步骤：、将问题化成标准形式；、找出初始解；、写出第一张单纯形表，并化成典式；、判断和迭代。判断：最优解（右端向量b0）；没有可行解（某个br0，并且在典式中br所在的这一行内没有负分量）16迭代步骤：确定离基变量xr（右端向量最小的负分量）arkT确定转轴元（离基变量所在的这一行中的负分量与中

17、对应元素比值最小的）确定进基变量xk（转轴元所在的这一列对应的非基变量）迭代计算（利用初等行变换，将转轴元变为1，转轴元所在的这一列其余元素全部变为0）；用进基变量xk代替离基变量xr。minz3x12x2x3s.t.x1x2x36（2）x1x34x2x33xi0,i1,2,3.解：先将原问题标准化minz3x12x2x3s.t.x1x2x3x46x1x3x54x2x3x63xi0,i1,2,3,4,5,6.在第2、3个等式的两端同乘以-1，并以x4,x5,x6为基变量，可得其单纯形表为17x1x2x3x4x5x6RHSz-3-2-10000 x41111006x5-101010-4以x5x6

18、0-11001-3x1为进基变量，旋转为离基变量，得x1x2x3x4x5x6RHSz0-2-40-3012x40121102x110-10-104以x6为x6x1x2x3x4x5x6RHS0-11001-3离基变z量，x200-60-3-218x4为进基变量，旋转得003111-1x110-10-104x201-100-13所以，原问题没有可行解。(X4所在行)P7823、考虑第20题中的线性规划（P），利用问题（P）的最优单纯形表持续求解下列问18题.(1)c1由1变为5；4解：因为只有非基变量x1的价值系数c1由1变为5P）的最优单纯,故只需要在问题（455形表中，把x1的查验数按如下规则改变：1(c1c1)1(1()1，获得44新问题的单纯形表如下x2x3x4RHSx117z10044注：要先写出变化规则，再由原问题的最优单纯形表获得新问题的单纯形表。x211015222以x1为117进基变量，x2为离基变量，旋转得x340144x1x3x2x4RHSz25130044x112015根据最x