1、运筹学教程第三章习题答案1. 影子价格是根据资源在生产中作出的贡献而做的估价。它是一种边际价格，其值相当于在资源得到最有效利用的生产条件下，资源每变化一个单位时目标函数的增量变化。又称效率价格。影 子 价 格 是 指 社 会 处 于 某 种 最 优 状 态 下 ， 能 够 反 映 社 会 劳 动 消 耗 、 资 源 稀缺 程 度 和 最 终 产 品 需 求 状 况 的 价 格 ， 是 社 会 对 货 物 真 实 价 值 的 度 量 。只 有 在 完 善 的 市 场 条 件 下 才 会 出 现 ， 然 而 这 种 完 善 的 市 场 条 件 是 不 存 在的 ， 因 此 现 成 的 影 子 价
2、格 也 是 不 存 在 的 。 市 场 价 格 是 物 品 和 服 务 在 市 场上 销 售 的 实 际 价 格 ， 是 由 供 求 关 系 决 定 的 。2.证明：当原问题约束条件右端变为 bi时，原问题变为： maxz=C iXj s.t. a ijXib i(i=1,2,3,m)Xj0 (j=1,2,3,n)对偶问题为： minp=b iy is.t. a ij yiC iyi0(i=1,2,3,m) (j=1,2,3,n)设，当 bi变为 bi原问题有最优解（X 1X 2X 3X n-1X n）时，对偶问题的最优解为（y 1y 2y 3y n-1y n）,则有： 又因为当原问题有最优解
3、时，对偶问题也有最优解，且相等，则有： 所以3（1）.minp=6y 1 + 2y2s.t. -y1+2y2-33y1+3y24y1,y20(2)解：令 X2=X2-X 2，X 4= X4-X 4，X 2，X 2，X4，X 40 ，原式化为：maxz=2X1 +2X2-2X 2-5X 3 +2X4-2X 4s.t. 2X1 -X2+X 2+3X 3 +3X4-3X 4-5-2X1 +X2-X 2-3X 3 -3X4+3X 45-6X1 -5X2+5X 2+X 3 -5X4+5X 4-610X1 -9X2+9X 2+6X 3 +4X4-4X 412X1, X2，X 2，X 3, X4，X 40则
4、对偶规划为：.minp= -5y1 + 5y1-6y 2 + 12y3s.t. 2y1 -2y1-6y 2 + 10y32-y1 +y1-5y 2 -9y32y1 -y1+5y 2 + 9y3-23y1 -3y1+y 2 + 6y3-53y1 -3y1-5y 2 + 4y32-3y1 +3y1+5y 2 -4y3-2即： minp= -5y1 + 5y1-6y 2 + 12y3s.t. 2y1 -2y1-6y 2 + 10y32-y1 +y1-5y 2 -9y3=23y1 -3y1+y 2 + 6y3-53y1 -3y1+5y 2 + 4y3=2令 y 1 - y1= y 1，得：minp=
5、5y1 -6y2 + 12y3s.t. -2y1-6y2 + 10y32y1-5y2 -9y3=2-3y1+y2 + 6y3-5-3y1-5y2 + 4y3=24、试用对偶理论讨论下列原问题与他们的对偶问题是否有最优解。(1) 123123max5.8,0zxst解：其对偶问题为：1212in8.3450,pysty=312y=012y=51234y由图中可知，对偶问题无解，根据对偶理论，原问题也无解。（2）123123min5.6,0fxst解：其对偶问题为：122112ax6.50,zysty无 约 束125y123y12y从图中可知，当（ ）=（0，-2）时，目标函数有最优值， =-12
6、，根据12,y *z对偶理论，原问题最优值与对偶问题相同，为 =-12。*f5.考虑如下线性规划 12344123412min578.65,0fxxstx（1）写出对偶线性规划；（2）用单纯形法解对偶规划，并在最优表中给出原规划的最优解；（3）说明这样做比直接求解原规划的好处。解：（1）对偶线性规划为： 1234234123max7865.5,0zyysty（2）将原规划的对偶规划化为标准形式： 1234253647182min8.,0pyysty得到其初始单纯形表，经过两次旋转运算后得到最优表，最优解为，最优值为 ，因此原规划的最优解为*1234(,)y（ ,1） *2p，最优值为 。8X（
7、 06） *f（3）这样做的好处是不用引入人工变量，对偶规划中的约束条件均为非大于号，可以直接运用单纯形法。基础变量 y1 y2 y3 y4 y5 y6 y7 y8 常数项y5 1 1 0 0 1 0 0 0 2y6 0 1 1 0 0 1 0 0 3y7 0 0 1 1 0 0 1 0 1y8 1 0 0 1 0 0 0 1 5-p -7 -8 -6 -5 0 0 0 0 0y2 1 1 0 0 1 0 0 0 2y6 -1 0 1 0 -1 1 0 0 1y7 0 0 1 1 0 0 1 0 1y8 1 0 0 1 0 0 0 1 5-p 1 0 -6 -5 8 0 0 0 16y2 1
8、1 0 0 1 0 0 0 2y6 -1 0 0 -1 -1 1 -1 0 0y3 0 0 1 1 0 0 1 0 1y8 1 0 0 1 0 0 0 1 5-p 1 0 0 1 8 0 6 0 226、用对偶单纯形方法，求解下面问题。（1）minf=5 X 1+3 X2+4 X32 X1+3 X2+2 X364 X1+3 X2+5 X310X1 ，X 2 ，X 30（2）maxZ= -X1-3 X2-3 X32 X1-3 X2+ X34X1+2 X2+2 X382 X2- X32X1 ，X 2 ，X 30解：（1）先将此问题化成下列形式：maxZ=-5 X1-3 X2-4 X3-2 X1-3
9、 X2-2 X3+X4=-6-4 X1-3 X2-5 X3+ X5=-10Xi0（i =1,2,3,4,5）建立此问题的初始单纯形表并进行运算如下：Cj -5 -4 -3 0 0CB XB b X1 X2 X3 X4 X50 X4 -6 -2 -3 -2 1 00 X5 -10 -4 -3 -5 0 1j-5 -4 -3 0 05/4 1 4/5Cj -5 -4 -3 0 0CB XB b X1 X2 X3 X4 X50 X4 -2 -2/5 -9/5 0 1 -2/5-4 X3 2 5/4 3/5 1 0 -1/5j-9/5 -3/5 0 0 -4/59/2 1/3 1/2Cj -5 -4
10、-3 0 0CB XB b X1 X2 X3 X4 X5-3 X2 10/9 2/9 1 0 -5/9 2/9-4 X3 4/3 2/3 0 1 1/3 -1/3j-5/3 0 0 -1/3 -2/3原问题的对偶规划问题为：MaxP=6Y1+Y22Y1+4Y253Y1+3Y232Y1+5Y24Y1 ，Y 20最终表中 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) 先将此问
11、题化成下列形式：maxZ=-X1-3X2-2X3-2 X1+3 X2-X3+X4=-4X1+2X2+2 X3+ X5=82 X2-X3+X6=2Xi0（i =1,2,3,4,5,6）建立此问题的初始单纯形表并进行运算如下：Cj -1 -3 -2 0 0 0CB XB b X1 X2 X3 X4 X5 X60 X4 -4 -2 3 -1 1 0 00 X5 8 1 2 2 0 1 00 X6 2 0 2 -1 0 0 1j-1 -3 -2 0 0 01/2 2Cj -1 -3 -2 0 0 0CB XB b X1 X2 X3 X4 X5 X6-1 X1 2 1 -3/2 1/2 -1/2 0 0
12、0 X5 6 0 7/2 3/2 1/2 1 00 X6 2 0 2 -1 0 0 1j0 -9/2 -3/2 -1/2 0 0原问题的对偶规划问题为：MinP=-4Y1+8 Y2+2Y3-2 Y1+ Y2-13 Y1+2 Y2+2Y3-3-Y1+2 Y2- Y3-2Y1 ，Y 2 ，Y 30最终表中 b 列数字全为非负，检验数全为非正，所以得出原问题最优解与最优值分别为：X*=（2，0，0） TZ*=-12=-2对偶问题的最优解与最优值分别为：Y*=（1/2，0,0） TP*=-4（1/2）=-2 = Z*7已知线性规划问题： 1234523451max00219. 7(,)jzxxstx写
13、出其对偶问题，并求一个对偶问题的可行解。解：其对偶问题为121212in9043.50,pysty在可行域中任取可行解： 。*125y8、考虑下面线性规划maxZ=2X1+3X22 X1+2X2+X3 =12X1+2X2 + X4=84X1 +X5=164X2 +X6=12Xj0，j =1,2,6其最优单纯形表如表 3-7 所示，试分析如下问题：（1） 当 C2=5 时，求新最优解。（2） 当 b3=4 时，求新最优解。（3） 增加一个约束 2X1 +2.4X212，对最优解有何影响。表 3-7基变量 X1 X2 X3 X4 X5 X6X3 0 0 0 1 -1 -1/4 0X1 4 1 0 0 0 1/4 0X6 4 0 0 0 -2 1/2 1X2 2 0 1 0 1/2 -1/8 0j-14 0 0 0 -3/2 -1/8 0解：由最优单纯形表所示结果及灵敏度变动思想求解最优解不变的 C2变动范围：
