运筹学第2章影子价格

5.对偶问题的经济解释----影子价格前面讲到，在单纯形法的每步迭代中，目标函数取值,和检验数中都有乘子，那么Y的经济意义是什么？bBCzB1NBCCBN11BCYB设B是的最优基，由（2.12）知由此所以变量的经济意义是在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。}0,{maxXbAXCXzbYbBCzB*1**1YBCbzB*iy由第一章例1的最终计算表（见表1-5）可见,，，。这说明是其它条件不变的情况下，若设备增加一台时，该厂按最优计划安排生产可多获利1.5元；原材料A增加1kg，可多获利0.125元；原材料B增加1kg，对获利无影响。5.1*1y125.0*2y0*3y从图2-1可看到，设备增加一台时，代表该约束条件的直线由（1）移至（1）’，相应地最优解由（4，2）变为（4，2.5），目标函数z=2*4+3*2.5=15.5即比原来的增大1.5。又若原材料A增加1kg时，代表该约束方程的直线由（2）移至（2）’，相应地最优解从（4，2）变为（4.25，1.875），目标函数z=2*4.25+3*1.875=14.125，比原来的增加0.125。原材料B增加1kg时，该约束方程的直线由（3）移至（3）’，这时的最优解不变。yi的值代表对第i种资源的估价。这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为”影子价格”。在该厂现有资源和现有生产方案的条件下，设备的每小时租费为1.5元，1kg原材料A的出让费为除成本外再附加0.125元，1kg原材料B可按原成本出让，这是该厂的收入与自己组织生产时获利相等。影子价格随具体情况而异。在完全市场经济的条件下，当某种资源的市场低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场高于企业影子价格时，则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。6对偶单纯形法前节讲到原问题与对偶问题的解之间的对应关系（性质7）时指出：在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，根据性质2、3可知，已得到最优解。即原问题与对偶问题都是最优解。根据对偶问题的对称性，也可以这样考虑：若保持对偶问题的解是基可行解，即，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。其优点是原问题的初始解不一定要是基可行解。可从非基可行解开始迭代。01jBjpBCc这方法是：设原问题又设B是一个基。不失一般性，令B=（P1，P2，…，Pm），它对应的变量为XB=(x1，x2，…，xm)CXzmaxbAX0X当非基变量都为零时，可以得到。若在中至少有一个负分量，设,并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持可行解，它的各分量是bBXB1bB10)(1ibB1.对应基变量x1，x2，…，xm的检验数是2.对应非基变量xm+1,…，xn的检验数是miPBCczciBiiii,,2,1,01nmjPBCczcjBjjjj,,1,01每次迭代是将基变量中的负分量xl取出，支替换非基变量中的xk,经基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近。当原问题得到可行解时，便得到了最优解。对偶单纯形法的计算步骤：（1）根据线性规划问题，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。（2）确定换出变量按对应的基变量xl为换出变量。liibBbBbB)(0)()(min111（3）确定换入变量在单纯形表中检查xl所在行的各系数,若所有，则无可行解，停止计算。若存在，计算按规则所对应的列的非基变量xk为换入变量，这样才能保持得到的对偶问题解仍为可行解。).,,2,1(njalj0lja),,2,1(0njaljlkkkljijjjjazcaazc0min（4）以为主无素，按原单纯形法在表中进行迭代运算，得到新的计算表。重复（1）-（4）的步骤。下面举例来说明具体算法lka例6用对偶单纯形法求解0,,43232432min321321321321xxxxxxxxxxxx解先将这问题化成下列形式，以便得到对偶问题的初始可行基5,,2,1,043232432max53214321321jxxxxxxxxxxxxzj建立这个问题的初始单纯形表，见表2-6。cj→-2-3-400CBXBbX1X2X3X4X500X4X5-3-4-1[-2]-21-1-31001cj-zj-2-3-400从表2-6看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。表2-6换出变量的确定：按上述对偶单纯形法计算步骤（2），计算min(-3,-4)=-4故X5为换出变量。换入变量的确定：按上述对偶单纯形法计算步骤（3），计算12234,,22min故x1为换入变量。换入、换出变量的所在列、行的交叉处”2”为主元素。按单纯形法计算步骤进行迭代。得表2-7。由表2-7看出，对偶问题仍是可行解，而b列中仍有负分量。故重复上述迭代步骤，得表2-8。表2-8中b列数字全为非负，检验数全为非正，故问题的最优解为若对应两个约束条件的对偶变量分别为y1和y2，则对偶问题的最优解为TX)0,0,0,5/2,5/11(*表2-7cj→-2-3-400CBXBbX1X2X3X4X50-2X4X1-1201[-5/2]-1/21/23/210-1/2-1/2cj-zj0-4-10-1表2-8cj→-2-3-400CBXBbX1X2X3X4X5-3-2X2X12/511/50110-1/57/5-2/5-1/51/5-2/5cj-zj00-3/5-8/5-1/5)5/1,5/8(),(*2*1*yyY从以上求解过程可以看到，对偶单纯形法有以下优点：（1）初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。（2）当变量多于约束条件，对这样的线性规划问题，用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成偶问题，然后用对偶单纯形法求解。（3）在灵敏度分析中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这方法在求解线性规划问题时很少单独应用。用改进单纯形法求线性规划问题)5,2,1(021222224231025432154315321ixxxxxxxxxxxxxxi54321212010208maxxxxxxS解：初始基是单位阵，基变量。相应地计算非基变量检验数，由此可确定x5为换入变量，计算),,(8760pppB),,(8760xxxXB)21,20,10,20,8(),,,,,(),0,0,0(00054321NNBCxxxxxXC)21,20,10,20,8(10000NBCCBNN对应换出变量为x6。于是得到新的基10221224110min0)()(min51051010PBPBbBiiTBxxxXpppB),,(),,,(87587511)0,20,10,20,8(),0,0,21(11NBCC102012001221101111BEB；第一步迭代。计算21,20,11,22,13001230211210121102012001)0,0,21()0,20,10,20,8(111111NBCCBNN非基变量检验数对应的换入变量为x4。5.02134min0)()(min41141111PBPBbBii计算对应的换出变量为x8TBxxxXpppB),,(),,,(47547522)0,0,10,20,8(),20,0,21(22NBCC由此得到新的基第二步迭代，计算2/1002/310001;2/12/3022EB2的逆阵2/1012/3110011020120012/1002/31000111212BEB)1,10,11,2,3(0011002112101212/1012/311001)20,0,21()0,0,10,20,8(212222NBCCBNN非基变量检验数检验数均为负数。因此得最优解为TNBbBxxxxxxxxXXX)0,0,0,0,0,2/1,2/5,10()0,(),,,,,,(),(126832147522220)2/1,2/5,10)(20,0,21(122TBbBCz居民区煤场B1B2B3现有原料（吨）A1210≥60A2024≥100每吨成品可获利润（万元）320.5160