运筹学第二章作业的参考答案

1、第二章作业的参考答案P73 4、将下面的线性规划问题化成标准形式maxx1x22x3s.t.x12x23x3 62x1x2x3 30 x1 31 x2 6解：将 max 化为 min ， x3用 x4 x5代替，则minx1 x2 2(x4 x5 )s.t. x1 2x2 3(x4 x5) 6 2x1 x2 (x4 x5 ) 3 0 x1 31 x2 6 x4 ,x5 0令 x2 x2 1 ，则minx1 x212(x4 x5)s.t.x12(x21)3(x4 x5) 62x1(x21)(x4 x5) 30x1 30x2 7x4,x5 0将线性不等式化成线性等式，则可得原问题的标准形式1min

2、x1 x2 2x4 2x5 1s.t. x12x23x43x5 x6 42x1x2x4x5 x7 4x1x83x2x97x1,x2,x4,x5,x6,x7,x8,x9P73 5、用图解法求解下列线性规划问题： 比较准确地画出可行区域； minx1 2x2 x3到可行区域的4边x界1 上；3x2 8x3x6 10 得出x j结论0。, j 1, ,6解：先将方程组中基变量 x2, x3 , x6的系数向量化成单位向量xj 0, j 1,6利用线性方程组的典式，把x2,x3用 x1 , x 4 , x 5表示，再带入目标函数，则可得原问题相应于基 B (A2 ,A3,A6 ) 的典式513min1

3、x1x4x541248511s.t.x1x3x4x541248511x1x2x521452572 x14x44x5 x6xj 0,j1,65339minx1 2x2x3511s.t.x1x3 x4x55413 2 485112 x1x2x5453257x14x4x5 x639214 5 65minz2x1 x2 x3s.t.3x1x2 x3 60x1x2 2x3 10(1)x1x2 x3 20xj0, j 1, 2,3解：将此问题化成标准形式P75 16、用单纯形法求解下列线性规划问题：注（零行元素的获得） ： 先将目标函数化成求 最小值的形式， 再把所 有变量移到等式左边， 常数移到等式右边

4、。 则minz2x1x2x3s.t.3x1x2x3x460x1x22x3x510x1x2x3x6 20xj 0, j 1, 2, 3, 4,5,6以 x1以 x2 为得xz5所以最优x64为-35。x1注：用单步骤x6x4、将 、找 、写 成典式；、判x4数向量x1某个x2x1x2x3 x4 x5 x6RHS21-1 0 0 003 x11 x21 1 0 0 x3 x4 x5 x6R6H0S10-31-250 -120-1201014-1501 -03 102301-12 0 1 01002-3 0 -1 110以 x4,x5,x6 为基变量，可得第一张单纯形表为z解为 xx1 x2x3x4

5、x5x6RHS注 意单纯 形表进基变量，的注格：x进基变量，要用记要为式离用！基记轴：元要标记单 x6 为离基变量旋转 纯形表的左边，用（进15基, 5变, 0量）T代，最替优值纯形法求离解基线变性规量划问题的问题化成标准形式；出初始解；出第一张单纯形表，并化1 1 30 0 02 2 2-1-2-3510定和迭代。判定： <1> 最优解（检验1212150 ）； <2> 问题无界非 基变 量 xk 的检验 数且 xk 在典式中的系数向量 Ak 0 ） 迭代步骤：<1> 确定进基变量 xk （检验数向量 T 中最 大的正分量）；<2> 确定转轴元

6、 ark （进基变量所在的这一 列中的 正分量与右端向量中 对应元素比值 最小 的）；<3> 确定离基变量 xr （转轴元所在的这一 行对应的基变量）；-1，并以 x5,x2,x1,x7 为基变量可得其单纯形表为x1x2x3x4x5x6x7RHSz-11-10-1100x500301106x2012-100010x110000-100x700100116x1x2x3x4x5x6x7RHSz0001010-4x500301106x2012-100010x110000-100x700100116将第 0 行 由 于 x4x 4 在的检验数典式中的系的元素化为检验数可41注：必须先将线

7、，性并方且程组和目标再用单纯形方法开始判定、迭代！<4> 迭代计算 （利用初等行变换， 将转轴元变为 1，转轴元所在的这一列 其它元素 全部 变为 0）；<5> 用进基变量xk 代替离基变量xr 。min zx1x2 x3 x5x6s.t.3x3x5 x66x22x3 x4103)x1x60x3x6 x76xj0,j 1,2,3,4,5,6,7解：在第三个等式两端同乘以A4 （0, 1, 0,0）T 0 ，所以问题无界。P75 17、用两阶段法求解下列线性规划问题：min z2x13x2x2s.t. 2x1 x1 x1 ,x2 0解：将此问题化为标准形式2)4x2231

8、9min z 2x1 4x2s.t. 2x1 3x2 x32x1 x2x43x1 ,x2,x3,x4 0添加人工变量 x5 , x6得到辅助问题min g x5 x6s.t. 2x1 3x2 x3x52x1 x2 x4x63x1 ,x2,x3,x4,x5,x60以 x5,x6 为基变量，可得辅助问题的单纯形表为把 g 所 在的这一行的元素化成检验数 x1 x2 x3 x4 x5x6 RHSz-2-400000g0000-1-10x52-3-10102x6-110-1013以 x1 为所以，辅最优值为没有可行（4）-2-400000Sx11-2x 2-1 x3-1x40x5 0x6RH20-37

9、-1 -1001 00111-01120 2-121031110012221110-114222z g xz5 xg6x1x6x1g解。变 助x2 x3 x4 x5 x6 RHS 进基变注：必须先将线 量， x5 为离基变量旋转得 性问方题程的组和最目优标解 函数（1,化0,成0,0典,0式,4，）T ，才4可 以0 。开因此始，原判问题定、迭代！max z2x14x25x36x4s.t. x14x22x38x42x12x23x34x41x1 ,x2,x3,x40解：将此问题化成标准形式min z2x14x25x36x4s.t. x14x22x38x42x12x23x34x41x1 ,x2,x

10、3,x4添加人工变量 x5 ,x6 得到辅助问题min gs.t.x1x1x54x22x2x62x3 8x43x3 4x4x1 ,x2,x3,x4,x5,x6x5,x6 为基变量，可得辅助问题的单纯形表为g所x4 为x3 为所以，辅gzxg5x65x6优值为始解为一张单纯x5x6以 x1进基量，x4为离基变 量旋转得 因此，原 问题的最 优解为x*z(8,0,3x,30，最优值 为 31。x21 -x42 x53-x64x0 x056RH0 S0 0 00-1 -102 -4 5-60 0001 64 -1218210 0023-1 24 -328401 1012-1 2 340 11RHS助

11、x1 x2 x3 x4 x5 x6在的这一行的元素化成检验数进基变量， x5 为离基变量旋转得进基变量， x6 为离基变量旋转得x1x2x3x4x5x6RHS11-1703034242330400022111110182484304011022g形表为x60 xx4651973-1001616820000-1-10x11x21x3x4RH3S1101T03 22 -660-130164T310100181603284061123x1x3x4x1x2x3 x4x5x6RHS问题的最优解为1(0,0,0,41,0,0)T，其最0 。因此，原问题的初1T(0,0,0, )T ，其第4x165x4x3

12、16132x2 x3 x4 RHS-1 0 0P76 18、写出下列线性规划问题的对偶规划：minz x1 2x2 4x3s.t.2x13x24x322x1x26x33x13x25x35x1,x2 0,x3为自由变量先将此问题化成一般形式minzx1 2x24x3s.t.2x13x24x322x1x26x33x13x25x35x1,x2 0,x3为自由变量所以，其对偶规划为max2132 5 3s.t.2122 3 13123 3 24162 5 3 4123注：要先将问题化成一般形 式，再按规则写出它的对偶 问题。要记住判定对偶变量 是自由变量还是非负变量0, 2为自由变量P77 20、给定

13、线性规划问题min z x1 x3s.t. x1 2x2x1,12x2x2,x3x3 3记为（ P）（ 1）用单纯形算法解 P;（2）写出 P 的对偶问题 D;（3）写出 P 的互补松紧条件 ,并利用它们解对偶 D;解： （1） 把问题（ P）化为标准形式minz x1 x3s.t.x1 2x2x451x2 x32 2 33x1, x2, x3 , x40以 x1,x3 为基变量，可得到其单纯形表为把第 0 行化成检验行，得x1 以 x2 为x11根据最优 z -1zxx2 x20501x3x3-1x4x40RHSRHS0(2) 将 问10x301221201 10进基变量， x1 为离基变量

14、，旋转得 化准则知，问题（P）的最优解为* 5 7 T 7x （0, , ） , 最优值为 .2 4 4题（ P）化为一般形式517004441101522210117444x1 x2 x3 x4 RHSzx2x3minzx1x3s.t.x12x2511x3 3x2222x1, x2, x30因此其对偶问题（D）为max 5 1 3 2s.t. 1 112 1 2 022110(3) 由问题( P)的最优解为 x*(0, 5, 7)T 以及互补松紧性定律可得24121 2 2 021解得11 4 ，2 1. 所以，对偶问题(D)51 3 27 .1 2 .4P7722、用对偶单纯形法解下列问题

15、minz 2x13x24x3s.t.x1 2x2x33(1)2x1 x23x34xi 0, i1, 2,3.解：引入剩余变量将原问题标准化min z2x1 3x24x3s.t. x12x2 x3x42x1x2 3x3x5xi0, i 1, 2, 3, 4,5.再将约束条件两边同时乘以1得的最优解为* 1 T(4,1) ，最优值为34注：若问题存在一个 基本解，并且该解的 检验数向量小于等于 零，则可使用对偶单 纯形方法。特别地， 要将问题典式化min z 2x1 3x2 4x3s.t.x1 2x2x3x42x1 x23x3x54xi 0, i 1, 2,3, 4,5.以 x4 , x5为基变量

16、，可得其单纯形表为以 x5x1 x2 x3 x4 x5 RHS 为离基变量， x1 为进基变量，旋转得x4根据最注：用步骤 ：-x21 -3x 2-4 x3 0 x4 0 x5 0 RHS-01 -2-4-1- 1 1 0 0 -1 -3 4-02 1 52-3 1 0 1 1 -1 224-11 1231 0222zxz4x5x4为离基变量， x2 为进基变量，旋转优化准则知，原问题的最优解为* 11 2 T 28x （ , ,0） , 最优值为 .5 5 5对偶单纯形方法求解线性规划问题的、x1x2x3x4x5RHS、98128z00、55551212x201555571211x11055

17、55、x1将问题化成标准形式；找出初始解；写出第一张单纯形表，并化成典式； 判定和迭代。判 定 ： <1> 最 优 解 （ 右 端 向 量b 0 ）； <2> 没有可行解（某个br0 ，并且在典式中 br 所在的这一行内没有负分量） 迭代步骤：<1> 确定离基变量xr （右端向量最 小 的 负 分量）T<2> 确定转轴元 ark （离 基变量所在的这一 行中的 负分量与中对应元素比值最小 的）<3> 确定进基变量 xk （转轴元所在的这一 列对应的非基变量）<4> 迭代计算 （利用初等行变换， 将转轴元变为 1，转轴元所在

18、的这一列其它元素 全 部变为 0）；<5> 用进基变量 x k 代替离基变量 x r 。minz3x12x2x3s.t.x1x2x36x1x342）x2x33xi0, i1, 2, 3.解：先将原问题标准化minz3x12x2 x3s.t.x1x2x3 x46x1x3x54x2x3x63xi0, i1, 2, 3, 4,5, 6.在第 2、 3个等式的两端同乘以 -1，并以 x4, x5, x6为基变量，可得其单纯形表为以 x5 为得以 x6 为转得 所以，原P78（P），利 求解下列（1）x1 x2 x3 x4 x5 x6离基变量， x1 为进基变量， 旋转离基变量， x2 为进基变量，旋问题没有可行解。 （X4 所在行 ）23、考