运筹学作业的参考答案

1、第二章作业的参考答案P734、将下面的线性规划问题化成标准形式maxx1-x22x3s.t.x1-2x2+3x3之62x1x2-x3M30Mxim3-1Mx2M6解：将max化为min,x3用x4一x5代替，则min-x1x2-2(x4-x5)s.t.x1-2x23(x4-x5)-62x1x2-(x4-x5)£30Hx1M3_1mx2M6乂4?5-0令x2=x2+1,贝umin-x1x2-1-2(x4-x5)s.t.x1-2(x2-1)3(x4-x5)-62x1(x2一1)一(x4一x5),30Mx1M30Mx2M7x4,x5-0将线性不等式化成线性等式，则可得原问题的标准形式min

2、-x1x2-2x42x5-1s.t.x1-2x23x4-3x5-x6=42x1x2-x4x5x7=4xix8=3x2x9=7xi,x2,x4,x5,x6,x7,x8,x9-0P735、用图解法求解下列线性规划问题:数）沿它的负法线方向（-1,-3）T移动到可行区域的边界上。于是交点（12,8）,就是该问题的最优解，其最优值为36。注：用图解法求解线性规划问题的步骤比较准确地画出可行区域；确定等值线及其法线方向；由max或min确定等值线的移动方向，并将其移动到可行区域的边界上；得出结论。minx1-2x2x3Is.t.3x1-x2+2x3+x4=7- 2x14x2x5=12- 4x13x28x

3、3x6=10xj-0,j=1,6解：先将方程组中基变量乂2,乂3,乂6的系数向量化成单位向量minst.x1-2x2x354x11一2x125一万Xixj-0,F2x3j=1,12x4-4x418x514x57-4x5=5=3X6=-39,6利用线性方程组的典式，把x2,乂3用x1,x4,x5表示，再带入目标函数，则可得原问题相应于基B=(A2,A3A)的典式mins.t.d51314x12x48x554X1X32x41x8x525X2-4x4lx4x57一X545二5二3x6-39Xj-0,j=1,6mins.t.z=-2x1-x2x33x1x2x360x1-x22x3m10Xix2-x3m

4、20Xj-0,j解：将此问题化成标准形式minz=-2x1-x2st.3x1+x2+x3x1-x22x3X1X2-X3=1,2,3X3X4X5=60=10X6=20Xj-0,j=1,2,3,4,5,6以X4,X5,X6为基变量，可得第一张单纯形表为21-10000311100601-120101011-100120XizX4X5进基变量,X6以X1为X2X3X4X5X6RHS注（零行元素的获得）：先将目标函数化成求最小值的形式，再把所有变量移到等式左边,常数移到等式右边。则变量前的系数为零行对应的元素。注意单纯形表的格式!注：要用记号把转得XRHS以x2为得所以最优优值为ZX4XiX203-5

5、0-20-2004-51-30301-120101002-30-1110zX4XiX6X1X2X3x4X5X1X2X3X4X5注：要记住在单纯形表的左边，用进基变量代替离基变量进基变量，X6为离基变量旋转X6RHS-1-1-32°22011-1-2-32-12-3510155.*T解为X=(15,5,0)，最-35。注：用单纯形法求解线性规划问题的步骤I、将问题化成标准形式；H、找出初始解；田、写出第一张单纯形表，并化成典式；IV、判定和迭代。判定：1最优解（检验数向量自W0）；2问题无界（某个非基变量Xk的检验数0,且Xk在典式中的系数向量&40）迭代步骤：1确定进基变量X

6、k（检验数向量,T中最大的正分量）；2确定转轴元3rk（进基变量所在的这一列中的正分量与右端向量中对应元素比值最小的）；<3>确定离基变量xr（转轴元所在的这一行对应的基变量）；<4>迭代计算（利用初等行变换,其它元素全部变为0）；将转轴元变为1,转轴元所在的这一列<5>用进基变量Xk代替离基变量Xrminz=x1-x2x3x5-x6s.t.3x3x5x6=6x22x3-x4=10(3)-xx6=0x3x6x7=6xj-0,j=1,2,3,4,5,6,7解：在第三个等式两端同乘以-1,并以x5,x2,x1,x7为基变量可得其单纯形表为将第0行zxx2xi头7

7、xix2x3乂4x5x6x7RHS-11001106000100-1000116-11-100030012-110000010的元素化为检验数可得注：必须先将线性方程组和目标函数化成典式，再用单纯形方法开始判定、迭代!由于x4X4在XiX2X3X4X5XX7RHS0001010-400301106012-10001010000-10000100116zX5X2XiX7的检验数%=1a0,并且典式中的系数向量TA4=(0,1,0,0)<0,所以问题无界。P7517、用两阶段法求解下列线性规划问题：minz=2x4x2Is.t.2x1-3x2-2(2) X1X2-3x1,x2-0解：将此问题

8、化为标准形式minz=2x14x2Is.t.2x1-3x2-x3=2-x1x2-X4=3Xi,X2,X3,X4之0添加人工变量X5,X6得到辅助问题ming=X5%s.t.2x1-3x2-x3-X1x2一x4xi,x2,x3,x4,x5,x6乂5,乂6为基变量，可得辅助问题的单纯形表为x1为x6xX5RHS-2-4000000000-1-102-3-10102-110-1013%在的这一行的元素化成检验数zgx1x2x3x4乂2x3x4x5x6RHSz-2-400000g1-2-1-1005乂52-3-10102x6-110-1013xiX6=3注：必须先将线性方程组和目标函数化成典式,才可以

9、开始判定、迭代!进基变量，x5为变量旋转得所以，辅0-7-10102-i-i-i0-104222-3-ii10012220-i-i-1i14222X2XX3zgXiX6助问题的最优解为X=(1,0,0,0,0,4)t,其*最优值为g=4>0。因此，原问题没有可行解。maXz=2X1-4x25x3-6X4s.t.X1+4x2-2x3+8x4=2Xi2X23X34x4=1Xi,X2,X3,X4上0解：将此问题化成标准形式minz=-2x14x2-5x36x4s.t.X1+4x2-2x3+8x4=2-X12x23x34x4=1Xi区名区-0添加人工变量X5,X6得到辅助问题ming二X5X6s

10、.t.x14x2-2x38x4x5=2-x12x23x34x4x6=1x,x2,x3,x4,x5,x6-0xRHS以乂5,乂6为基变量，可得辅助问题的单纯形表为2-45-60000000-1-1014-28102-1234011xix2x3x4乂5zgx%在的这一行的元素化成检验数xRHS以x4为2-45-60000611200314-28102-1234011xix2x3x4x5zg乂5%进基变量,x5为离基变量旋转得11-1X4以X3为转得所以，辅其最优值为gX4X6-32-32-1进基变量,X6为离基变量旋65-10016-719816320000-1-101101322-3010831

11、3216-1184140X2X3X4X1X5X6RHSzgX4X3助问题的最优解为1Tx'=(0,0,0；0,0)T,401Tg=0。因此，原问题的初始解为x=(0,0,0,一),其第一张单纯形表为4X2X3X4RHSZX4X36516132-100一301008进基变量,X4为离基变量旋转得因此，原0-660-130-311160320611283X3X4RHSzXiX3问题的最优解为(8,0,3,0)t,最优102注：要先将问题化成一般形式，再按规则写出它的对偶问题。要记住判定对偶变量是自由变量还是非负变量值为31。?618、写出下列线性规划问题的对偶规划：minz=X12x24x

12、3s.t.2x1+3x2+4x3>22x1x26x3=3X1+3x2+5x3w5X1,x2一0,x3为自由变量解：先将此问题化成一般形式minz=X1+2x2+4x3s.t.2x1+3x2+4x3之22x1x26x3=3_Xi-3X2_5X3-_5X1,x20,x3为自由变量所以，其对偶规划为max2132-53s.t.281+2切2一缶3w1312-33-24«1+6切25切3=4I238。3之0,。2为自由变量P7720、给定线性规划问题mins.t.z=X1X3x12x2三512X2X3=3Xi,X2,记为(P)(1)用单纯形算法解P；(2)写出P的对偶问题D;(3)写出

13、P的互补松紧条件，并利用它们解对偶D;解：(1)把问题(P)化为标准形式minz=X1X3s.t.X12x2x4=51 QX2X3=32Xi,X2,X3,X4-0以Xi,X3为基变量，可得到其单纯形表为：XiX2X3X4RHSzXiX3-10-10012015把第0行化成检验行，得以x2为进基变量,X2X3X1为离基变量，旋转得根据最优_5_14004741101221140144|72|5X4RHSzX2X3化准则知，问题（P）的最优解为*57TX=(0,),取优值为24（2）将问题（P）化为一般形式minz=Xi+X3s.t.X1-2x2-54 1*_ox2*x3=3X1,X2,X3-0因

14、此其对偶问题(D)为max-5®1+3切25 .t.一01M1一1,一-21-2-022E1®1至0J571（3）由问题（P）的最优解为x一（0，二，一）以及互补松紧性定律可得241解得01=,82=1.所以，对偶问题（4，一，.=，*1T一，-，D）的最优解为切=（,1）,最优值为47-51.i3._,2-.4P7722、用对偶单纯形法解下列问题minz=2x13x24x3st.x12x2x3-3（1）2x1-x23x3-4X-0,i=1,2,3.解：引入剩余变量将原问题标准化minz=2x13x24x3js.t.x1+2x2+x3-x4=32x1-x23x3-x5=4为

15、-0,i=1,2,3,4,5.再将约束条件两边同时乘以-1得minz=2x13x24x3st.-x1-2x2-x3x4=-3-2x1x2-3x3x5=4X-0,i=1,2,3,4,5.以x4,x5为基变量，可得其单纯形表为注：若问题存在一个基本解，并且该解的检验数向量小于等于零，则可使用对偶单纯形方法。特别地，要将问题典式化X5X4根据最-2-3-400X4X5X4Xi-1-2-110-2J1-301XiX2-4-3-4X3X4X5RHS-10-1-1为离基变量，X1为进基变量，旋转得为离基变量，X2为进基变量，旋转981nn一一一一一28005555/2/112015555271一11105

16、555zX2优化准则知，原问题的最优解为*XXX2X3X4X5RHS228（一,一,0）,取优值为一555注：用对偶单纯形方法求解线性规划问题的步骤I、将问题化成标准形式；n、找出初始解；出、写出第一张单纯形表，并化成典式；W、判定和迭代。判定：i最优解（右端向量b之0）；2没有可行解（某个br0,并且在典式中br所在的这一行内没有负分量）迭代步骤:< 1>确定离基变量xr（右端向量最小的负分量）T< 2>确定转轴元ark（离基变量所在的这一行中的负分量与一中对应元素比值最小的）< 3>确定进基变量xk（转轴元所在的这一列对应的非基变量）<4>迭

17、代计算（利用初等行变换，将转轴元变为1,转轴元所在的这一列其它元素全部变为0）;<5>用进基变量Xk代替离基变量minz=3x12x2s.t.x1x2x3一x1x3-(2)x2x-x3xi0,i=1,2,3.解：先将原问题标准化min3x12x2x3s.t.x2x3x4x1x3X5x2x3x6xi-0,i=1,2,3,4,5,6.在第2、3个等式的两端同乘以-1,并以x4,x5,x6为基变量，可得其单纯形表为X5-3-2-100001111006回01010-40-11001-3zX4X5X6离基变量，X1为进基变量，旋转X2X3X4X5X24RHSXiX2X3X4X5X6RHSX

18、6量，X2-2-40-3012X4XiX6为进基变量，旋转得2110-10-101001-3X4XiX2所以，原问题没有可行解。（X4所在行）F7823、考虑第20题中的线T规划（P）,利用问题（P）XiX2X3X4X5X6RHS00-60-3-218-1-1-1-1-1的最优单纯形表继续求解下列问5（1）a由1变为；4解：因为只有非基变量X1的价值系数G由1变为-5,故只需要在问题（P）的最优单纯4一，一.55形表中，把X1的检验数按如下规则改变：+（gc1）=+（1（）=1,得到44新问题的单纯形表如下以Xi为根据最解为X2X3XiX2X3X4RHS50-204_13412010110253X2X4RHSZX1X35进基变量,注：要先写出变化规则，再由原问题的最优单纯形表得到新问题的单纯形表。X2为离基变量，旋转得优化准则知，修改后的