《运筹学教程》第三章习题答案

1.影子价格是根据资源在生产中作出的贡献而做的估价。它是一种边际价格，其值相当于在资源得到最有效利用的生产条件下，资源每变化一个单位时目标函数的增量变化。又称效率价格。影子价格是指社会处于某种最优状态下，能够反映社会劳动消耗、资源稀缺程度和最终产品需求状况的价格，是社会对货物真实价值的度量。只有在完善的市场条件下才会出现，然而这种完善的市场条件是不存在的，因此现成的影子价格也是不存在的。市场价格是物品和服务在市场上销售的实际价格，是由供求关系决定的。2.证明：当原问题约束条件右端变为bi′时，原问题变为：

maxz=∑CiXjs.t.

∑aijXi≤bi′(i=1,2,3,……,m)Xj≥0

(j=1,2,3,……,n)对偶问题为：

minp=∑bi′yis.t.

∑aijyi≥Ciyi≥0(i=1,2,3,……,m)(j=1,2,3,……,n)设，当bi变为bi′原问题有最优解（X1′X2′X3′……Xn-1′Xn′）时，对偶问题的最优解为（y1′y2′y3′……yn-1′yn′）,则有：又因为当原问题有最优解时，对偶问题也有最优解，且相等，则有：所以3（1）.minp=6y12y2s.t.

-y12y2≥-33y13y2≥4y1,y2≥0(2)解：令X2=X2′-X2〞，X4=X4′-X4〞，X2′，X2〞，X4′，X4〞≥0，原式化为：maxz=2X12X2′-2X2〞-5X32X4′-2X4〞s.t.

2X1-X2′X2〞3X33X4′-3X4〞≤-5-2X1X2′-X2〞-3X3-3X4′3X4〞≤5-6X1-5X2′5X2〞X3-5X4′5X4〞≤-610X1-9X2′9X2〞6X34X4′-4X4〞≤12X1,X2′，X2〞，X3,X4′，X4〞≥0则对偶规划为：.minp=-5y1′5y1〞-6y212y3s.t.

2y1′-2y1〞-6y210y3≥2-y1′y1〞-5y2-9y3≥2y1′-y1〞5y29y3≥-23y1′-3y1〞y26y3≥-53y1′-3y1〞-5y24y3≥2-3y1′3y1〞5y2-4y3≥-2即：minp=-5y1′5y1〞-6y212y3s.t.

2y1′-2y1〞-6y210y3≥2-y1′y1〞-5y2-9y3=23y1′-3y1〞y26y3≥-53y1′-3y1〞5y24y3=2令y1〞-y1′=y1，得：minp=5y1-6y212y3s.t.

-2y1-6y210y3≥2y1-5y2-9y3=2-3y1y26y3≥-5-3y1-5y24y3=24、试用对偶理论讨论下列原问题与他们的对偶问题是否有最优解。(1)解：其对偶问题为：由图中可知，对偶问题无解，根据对偶理论，原问题也无解。（2）解：其对偶问题为：从图中可知，当（）=（0，-2）时，目标函数有最优值，=-12，根据对偶理论，原问题最优值与对偶问题相同，为=-12。5.考虑如下线性规划（1）写出对偶线性规划；（2）用单纯形法解对偶规划，并在最优表中给出原规划的最优解；（3）说明这样做比直接求解原规划的好处。解：（1）对偶线性规划为：（2）将原规划的对偶规划化为标准形式：得到其初始单纯形表，经过两次旋转运算后得到最优表，最优解为，最优值为，因此原规划的最优解为，最优值为。（3）这样做的好处是不用引入人工变量，对偶规划中的约束条件均为非大于号，可以直接运用单纯形法。基础变量y1y2y3y4y5y6y7y8常数项y5110010002y6011001003y7001100101y8100100015-p-7-8-6-500000y2110010002y6-1010-11001y7001100101y8100100015-p10-6-5800016y2110010002y6-100-1-11-100y3001100101y8100100015-p10018060226、用对偶单纯形方法，求解下面问题。（1）minf=5X13X24X32X13X22X3≥64X13X25X3≥10X1，X2，X3≥0（2）maxZ=-X1-3X2-3X32X1-3X2X3≥4X12X22X3≤82X2-X3≤2X1，X2，X3≥0解：（1）先将此问题化成下列形式：maxZ=-5X1-3X2-4X3-2X1-3X2-2X3X4=-6-4X1-3X2-5X3X5=-10Xi≥0（i=1,2,3,4,5）建立此问题的初始单纯形表并进行运算如下：Cj-5-4-300CBXBbX1X2X3X4X50X4-6-2-3-2100X5-10-4-3-501-5-4-3005/414/5Cj-5-4-300CBXBbX1X2X3X4X50X4-2-2/5-9/501-2/5-4X325/43/510-1/5-9/5-3/500-4/59/21/31/2Cj-5-4-300CBXBbX1X2X3X4X5-3X210/92/910-5/92/9-4X34/32/3011/3-1/3-5/300-1/3-2/3原问题的对偶规划问题为：MaxP=6Y1Y22Y14Y2≤53Y13Y2≤32Y15Y2≤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-2X13X2-X3X4=-4X12X22X3X5=82X2-X3X6=2Xi≥0（i=1,2,3,4,5,6）建立此问题的初始单纯形表并进行运算如下：Cj-1-3-2000CBXBbX1X2X3X4X5X60X4-4-23-11000X581220100X6202-1001-1-3-20001/22Cj-1-3-2000CBXBbX1X2X3X4X5X6-1X121-3/21/2-1/2000X5607/23/21/2100X6202-10010-9/2-3/2-1/200原问题的对偶规划问题为：MinP=-4Y18Y22Y3-2Y1Y2≥-13Y12Y22Y3≥-3-Y12Y2-Y3≥-2Y1，Y2，Y3≥0最终表中b列数字全为非负，检验数全为非正，所以得出原问题最优解与最优值分别为：X*=（2，0，0）TZ*=-1×2=-2对偶问题的最优解与最优值分别为：Y*=（1/2，0,0）TP*=-4×（1/2）=-2=Z*7．已知线性规划问题：写出其对偶问题，并求一个对偶问题的可行解。解：其对偶问题为在可行域中任取可行解：。8、考虑下面线性规划maxZ=2X13X22X12X2X3=12X12X2X4=84X1X5=164X2X6=12Xj≥0，j=1,2,…,6其最优单纯形表如表3-7所示，试分析如下问题：（1）当C2=5时，求新最优解。（2）当b3=4时，求新最优解。（3）增加一个约束2X12.4X2≤12，对最优解有何影响。表3-7基变量X1X2X3X4X5X6X30001-1-1/40X1410001/40X64000-21/21X220101/2-1/80-14000-3/2-1/80解：由最优单纯形表所示结果及灵敏度变动思想求解最优解不变的C2变动范围：（-3/2）/（1/3）≤△C2≤（-1/8）/（-1/8）-3≤△C2≤1即0≤C2≤4而题设条件为：新C2=5，超出变动范围，故最优解发生变动，需重新求解。C2值发生变动后，影响的值，故新的值分别为：=（-3/2）-(1/2)×（5-3）=-5/2=（-1/8）-(-1/8)×（5-3）=1/8继续上述最优单纯形表的计算：Cj250000CBXBbX1X2X3X4X5X60X30001-1-1/402X1410001/40160X64000-21/2185X220101/2-1/80000-5/21/80Cj250000CBXBbX1X2X3X4X5X60X32001-201/22X1210010-1/20X58000-4125X23010001/4000-20-1/4新最优解和最优值分别为：X*=（2，3）TZ*=2×25×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/2

0

3

34

-3

1b3’=b△b3’=

4

-6

=

-22

3/2

7/2继续上述最优单纯形表的计算：Cj230000CBXBbX1X2X3X4X5X60X33001-1-1/402X1110001/400X6-2000-21/213X27/20101/2-1/80000-3/2-1/803/4Cj230000CBXBbX1X2X3X4X5X60X340010-1/2-1/22X1110001/400X410001-1/4-1/23X23010001/40000-1/2-3/4新最优解和最优值分别为：X*=（1，3）TZ*=2×13×3=11(3)加入新的约束条件2X12.4X2≤12，将其变为下列形式：2X12.4X2X7≤12

X7≥0加入新约束条件后继续上述最优单纯形表的计算：Cj2300000CBXBbX1X2X3X4X5X6X70X30001-1-1/4002X1410001/4000X64000-21/2103X220101/2-1/8000X71222.400001000-3/2-1/800Cj2300000CBXBbX1X2X3X4X5X6X70X30001-1-1/4002X1410001/4000X64000