《运筹学教程》第三章习题答案1.影子价格是根据资源在生产中作出的贡献而做的估价。

它是一种边际价格，其值相当于在资源得到最有效利用的生产条件下，资源每变化一个单位时目标函数的增量变化。

又称效率价格。

影子价格是指社会处于某种最优状态下，能够反映社会劳动消耗、资源稀缺程度和最终产品需求状况的价格，是社会对货物真实价值的度量。

只有在完善的市场条件下才会出现，然而这种完善的市场条件是不存在的，因此现成的影子价格也是不存在的。

市场价格是物品和服务在市场上销售的实际价格，是由供求关系决定的。

2.证明：当原问题约束条件右端变为b i′时，原问题变为： maxz=∑C i X js.t. ∑a ij X i≤b i′(i=1,2,3,……,m)X j≥0 (j=1,2,3,……,n)对偶问题为： minp=∑b i′y is.t. ∑a ij y i≥C iy i≥0(i=1,2,3,……,m) (j=1,2,3,……,n) 设，当b i变为b i′原问题有最优解（X1′X2′X3′……X n-1′X n′）时，对偶问题的最优解为（y1′y2′y3′……y n-1′y n′）,则有：又因为当原问题有最优解时，对偶问题也有最优解，且相等，则有：所以3（1）.minp=6y1 + 2y2s.t. -y1+2y2≥-33y1+3y2≥4y1,y2≥0(2)解：令X2=X2′-X2〞，X4= X4′-X4〞，X2′，X2〞，X4′，X4〞≥0 ，原式化为：maxz=2X1 +2X2′-2X2〞-5X3 +2X4′-2X4〞s.t. 2X1 -X2′+X2〞+3X3 +3X4′-3X4〞≤-5-2X1 +X2′-X2〞-3X3 -3X4′+3X4〞≤5-6X1 -5X2′+5X2〞+X3 -5X4′+5X4〞≤-610X1 -9X2′+9X2〞+6X3 +4X4′-4X4〞≤12X1, X2′，X2〞，X3, X4′，X4〞≥0则对偶规划为：.minp= -5y1′+ 5y1〞-6y2 + 12y3s.t. 2y1′-2y1〞-6y2 + 10y3≥2-y1′+y1〞-5y2 -9y3≥2y1′-y1〞+5y2 + 9y3≥-23y1′-3y1〞+y2 + 6y3≥-53y1′-3y1〞-5y2 + 4y3≥2-3y1′+3y1〞+5y2 -4y3≥-2即：minp= -5y1′+ 5y1〞-6y2 + 12y3s.t. 2y1′-2y1〞-6y2 + 10y3≥2-y1′+y1〞-5y2 -9y3=23y1′-3y1〞+y2 + 6y3≥-53y1′-3y1〞+5y2 + 4y3=2令 y1〞- y1′= y1，得：minp= 5y1 -6y2 + 12y3s.t. -2y1-6y2 + 10y3≥2y1-5y2 -9y3=2-3y1+y2 + 6y3≥-5-3y1-5y2 + 4y3=24、试用对偶理论讨论下列原问题与他们的对偶问题是否有最优解。

(1)12123123123max35..232 248 ,,0z x xs t x x xx x xx x x=+⎫⎪-++≤⎪⎬-+-≤⎪⎪≥⎭解：其对偶问题为：1212121212min28 ..223 345,0p y y s t y yy yy yy y=+⎫⎪--≥⎪⎪+≥⎬⎪-≥⎪≥⎪⎭由图中可知，对偶问题无解，根据对偶理论，原问题也无解。

（2）12312312123min 225..322626,,0f x x x s t x x x x x x x x =-++⎫⎪-+≥-⎪⎬+=⎪⎪≥⎭解：其对偶问题为：121212112max 66..32222250,z y y s t y y y y y y y =-+⎫⎪+≤-⎪⎪-+≤⎬⎪≤⎪⎪≥⎭无约束从图中可知，当（12,y y ）=（0，-2）时，目标函数有最优值，*z =-12，根据对偶理论，原问题最优值与对偶问题相同，为*f =-12。

5.考虑如下线性规划1234141223341234min 23578..65,,,0f x x x x x x x x s t x x x x x x x x =++++≥⎧⎪+≥⎪⎪+≥⎨⎪+≥⎪⎪≥⎩（1）写出对偶线性规划；（2）用单纯形法解对偶规划，并在最优表中给出原规划的最优解；（3）说明这样做比直接求解原规划的好处。

解：（1）对偶线性规划为：1234122334141234max 786523..15,,,0z y y y y y y y y s t y y y y y y y y =++++≤⎧⎪+≤⎪⎪+≤⎨⎪+≤⎪⎪≥⎩（2）将原规划的对偶规划化为标准形式：1234125236347148128min 786523..15,0p y y y y y y y y y y s t y y y y y y y y y =----++=⎧⎪++=⎪⎪++=⎨⎪++=⎪⎪≥⎩得到其初始单纯形表，经过两次旋转运算后得到最优表，最优解为****1234(,,,)0y y y y =（,2,1,0），最优值为*22p =-，因此原规划的最优解为*8X =（,0,6,0），最优值为*f 22=。

（3）这样做的好处是不用引入人工变量，对偶规划中的约束条件均为非大于号，可以直接6、用对偶单纯形方法，求解下面问题。

（1）minf=5 X1+3 X2+4 X32 X1+3 X2+2 X3≥64 X1+3 X2+5 X3≥10X1 ，X2，X3≥0（2）maxZ= -X1-3 X2-3 X32 X1-3 X2+ X3≥4X1+2 X2+2 X3≤82 X2- X3≤2X1 ，X2，X3≥0解：（1）先将此问题化成下列形式：maxZ=-5 X1-3 X2-4 X3-2 X1-3 X2-2 X3+X4=-6-4 X1-3 X2-5 X3+ X5=-10X i≥0（i =1,2,3,4,5）建立此问题的初始单纯形表并进行运算如下：原问题的对偶规划问题为：MaxP=6Y1+Y22Y1+4Y2≤53Y1+3Y2≤32Y1+5Y2≤4Y1，Y2≥0最终表中b列数字全为非负，检验数全为非正，所以得出原问题最优解与最优值分别为：X*=（0，10/9，4/3）Tf*=3×（10/9）+4×（4/3）=26/3对偶问题的最优解与最优值分别为：Y*=（1/3，2/3）TP*=6×（1/3）+10×（2/3）=26/3= f*(2) 先将此问题化成下列形式：maxZ=-X1-3X2-2X3-2 X1+3 X2-X3+X4=-4X1+2X2+2 X3+ X5=82 X2-X3+X6=2X i≥0（i =1,2,3,4,5,6）建立此问题的初始单纯形表并进行运算如下：原问题的对偶规划问题为：MinP=-4Y 1+8 Y 2+2Y 3 -2 Y 1+ Y 2≥-13 Y 1+2 Y 2+2Y 3≥-3 -Y 1+2 Y 2- Y 3≥-2 Y 1 ，Y 2 ，Y 3≥0最终表中b列数字全为非负，检验数全为非正，所以得出原问题最优解与最优值分别为：X*=（2，0，0）T Z*=-1×2=-2对偶问题的最优解与最优值分别为：Y*=（1/2，0,0）TP*=-4×（1/2）=-2= Z*7．已知线性规划问题：123451234512345max 102420202523519..243270(1,25)jz x x x x x x x x x x s t x x x x x x j =++++⎧++++≤⎪++++≤⎨⎪≥=⎩写出其对偶问题，并求一个对偶问题的可行解。

解：其对偶问题为12121212121212min 1972104242320..32205250,0p y y y y y y y y s t y y y y y y =++≥⎧⎪+≥⎪⎪+≥⎪⎨+≥⎪⎪+≥⎪≥≥⎪⎩在可行域中任取可行解：**125,5y y ==。

8、考虑下面线性规划maxZ=2X 1+3X 22 X 1+2X 2+X3 =12 X 1+2X 2 + X 4=8 4X 1 +X 5=16 4X 2 +X 6=12X j ≥0，j =1,2,…,6其最优单纯形表如表3-7所示，试分析如下问题： （1） 当C 2=5时，求新最优解。

（2） 当b 3=4时，求新最优解。

（3） 增加一个约束2X 1 +2.4X 2≤12，对最优解有何影响。

解：由最优单纯形表所示结果及灵敏度变动思想求解最优解不变的C 2变动范围： （-3/2）/（1/3）≤△C 2≤（-1/8）/（-1/8） -3≤△C 2≤1即0≤C2≤4而题设条件为：新C2=5，超出变动范围，故最优解发生变动，需重新求解。

C2值发生变动后，影响σj的值，故新的σj值分别为：σ4=（-3/2）-(1/2)×（5-3）=-5/2σ5=（-1/8）-(-1/8)×（5-3）=1/8继续上述最优单纯形表的计算：新最优解和最优值分别为：X*=（2，3）TZ*=2×2+5×3=19（2）由最优单纯形表所示结果及灵敏度变动思想求解最优解不变的b3变动范围：（-4）/（1/2）≤△b3≤0/（-1/4）-8≤△b3≤0即8≤b3≤16而题设条件为：新b3=4，超出变动范围，故最优解发生变动，需重新求解。

b3发生变动后1 -1 -1/4 0 0 30 0 1/4 0 0 -3△b3’=B-1b= 0 -2 1/2 1 -12 = -60 1/2 -1/8 0 0 3/20 3 34 -3 1b3’= b+△b3’= 4 + -6 = -22 3/2 7/2继续上述最优单纯形表的计算：新最优解和最优值分别为：X*=（1，3）TZ*=2×1+3×3=11(3)加入新的约束条件2X1 +2.4X2≤12，将其变为下列形式：2X1 +2.4X2+ X7≤12 X7≥0加入新约束条件后继续上述最优单纯形表的计算：新最优解和最优值分别为：X*=（3，5/2）TZ*=2×3+3×(5/2)=27/29.（1）'3312y y = （2）影子价格不变。