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

运筹学教程第三章习题答案1. 影子价格是根据资源在生产中作出的贡献而做的估价。它是一种边际价格，其值相当于在资源得到最有效利用的生产条件下，资源每变化一个单位时目标函数的增量变化。又称效率价格。影子价格是指社会处于某种最优状态下，能够反映社会劳动消耗、资源稀缺程度和最终产品需求状况的价格，是社会对货物真实价值的度量。只有在完善的市场条件下才会出现，然而这种完善的市场条件是不存在的，因此现成的影子价格也是不存在的。市场价格是物品和服务在市场上销售的实际价格，是由供求关系决定的。2.证明：当原问题约束条件右端变为bi时，原问题变为： maxz=CiXj s.t. aijXibi(i=1,2,3,m)Xj0 (j=1,2,3,n)对偶问题为： minp=biyi s.t. aij yiCi yi0(i=1,2,3,m) (j=1,2,3,n)设，当bi变为bi原问题有最优解（X1X2X3Xn-1Xn）时，对偶问题的最优解为（y1y2y3yn-1yn）,则有： 又因为当原问题有最优解时，对偶问题也有最优解，且相等，则有： 所以 3（1）.minp=6y1 + 2y2s.t. -y1+2y2-33y1+3y24y1,y20(2)解：令X2=X2-X2，X4= X4-X4，X2，X2，X4，X40 ，原式化为：maxz=2X1 +2X2-2X2-5X3 +2X4-2X4s.t. 2X1 -X2+X2+3X3 +3X4-3X4-5-2X1 +X2-X2-3X3 -3X4+3X45-6X1 -5X2+5X2+X3 -5X4+5X4-610X1 -9X2+9X2+6X3 +4X4-4X412X1, X2，X2，X3, X4，X40则对偶规划为：.minp= -5y1 + 5y1-6y2 + 12y3s.t. 2y1 -2y1-6y2 + 10y32-y1 +y1-5y2 -9y32y1 -y1+5y2 + 9y3-23y1 -3y1+y2 + 6y3-53y1 -3y1-5y2 + 4y32-3y1 +3y1+5y2 -4y3-2即： minp= -5y1 + 5y1-6y2 + 12y3s.t. 2y1 -2y1-6y2 + 10y32-y1 +y1-5y2 -9y3=23y1 -3y1+y2 + 6y3-53y1 -3y1+5y2 + 4y3=2令 y1 - y1= y1，得：minp= 5y1 -6y2 + 12y3s.t. -2y1-6y2 + 10y32y1-5y2 -9y3=2-3y1+y2 + 6y3-5 -3y1-5y2 + 4y3=24、试用对偶理论讨论下列原问题与他们的对偶问题是否有最优解。(1) 解：其对偶问题为：=3=0=5由图中可知，对偶问题无解，根据对偶理论，原问题也无解。（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=5 X1+3 X2+4 X3 2 X1+3 X2+2 X36 4 X1+3 X2+5 X310 X1 ，X2 ，X30（2）maxZ= -X1-3 X2-3 X3 2 X1-3 X2+ X34 X1+2 X2+2 X38 2 X2- X32 X1 ，X2 ，X30解：（1）先将此问题化成下列形式：maxZ=-5 X1-3 X2-4 X3-2 X1-3 X2-2 X3+X4=-6-4 X1-3 X2-5 X3+ X5=-10Xi0（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=6Y1+Y22Y1+4Y253Y1+3Y232Y1+5Y24Y1 ，Y20最终表中b列数字全为非负，检验数全为非正，所以得出原问题最优解与最优值分别为：X*=（0，10/9，4/3）T f*=3（10/9）+4（4/3）=26/3对偶问题的最优解与最优值分别为：Y*=（1/3，2/3）T P*=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=2Xi0（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=-4Y1+8 Y2+2Y3-2 Y1+ Y2-1 3 Y1+2 Y2+2Y3-3-Y1+2 Y2- Y3-2Y1 ，Y2 ，Y30最终表中b列数字全为非负，检验数全为非正，所以得出原问题最优解与最优值分别为：X*=（2，0，0）T Z*=-12=-2对偶问题的最优解与最优值分别为：Y*=（1/2，0,0）T P*=-4（1/2）=-2= Z*7已知线性规划问题：写出其对偶问题，并求一个对偶问题的可行解。解：其对偶问题为在可行域中任取可行解：。8、考虑下面线性规划maxZ=2X1+3X2 2 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基变量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） -3C21即 0C24而题设条件为： 新C2=5，超出变动范围，故最优解发生变动，需重新求解。C2值发生变动后，影响的值，故新的值分别为：=（-3/2）-(1/2)（5-3）=-5/2=（-1/8）-(-1/8)（5-3）=1/8继续上述最优单纯形表的计算：Cj250000CBXBbX1X2X3X4X5X60X30001-1-1/40 2X1410001/40160X64000-21/2185X220101/2-1/80000-5/21/80Cj250000CBXBbX1X2X3X4X5X60X32001-201/22X1210010-1/20X58000-4125X23010001/4000-20-1/4新最优解和最优值分别为：X*=（2，3）T Z*=22+53=19（2）由最优单纯形表所示结果及灵敏度变动思想求解最优解不变的b3变动范围： （-4）/（1/2）b30/（-1/4） -8b30即 8b316而题设条件为： 新b3=4，超出变动范围，故最优解发生变动，需重新求解。b3发生变动后1 -1 -1/4 0 0 30 0 1/4 0 0 -3b3=B-1b= 0 -2 1/2 1 -12 = -6 0 1/2 -1/8 0 0 3/20 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）T Z*=21+33=11(3)加入新的约束条件2X1 +2.4X212，将其变为下列形式：2X1 +2.4X2+ X712 X70加入新约束条件后继续上述最优单纯形表的计算：Cj2300000CBXBbX1X2X3X4X5X6X70X30001-1-1/40 02X1410001/4000X64000-21/2103X220101/2-1/8000X71222.400001000-3/2-1/800Cj2300000CBXBbX1X2X3X4X5X6X70X30001-1-1/40 02X1410001/4000X64000-21/2103X220