第6节对偶单纯形法

第3章对偶理论和灵敏度分析对偶问题的经济解释对偶单纯形法教学目的正确理解单纯形表和对偶的关系。教学要求掌握：影子价格、对偶单纯形法，从一个对偶可行，原始不可行的解出发求出最优解。了解：单纯形表和对偶的关系，能根据单纯形表求出对偶问题的解。教学重难点重点：影子价格、对偶单纯形法难点：影子价格、对偶单纯形法教学方法启发式教学教学提纲对偶问题的经济解释对偶单纯形法第5节对偶问题的经济解释——影子价格引言：在单纯形法的每步迭代中，目标函数取值z=CBB-1b，和检验数Cr-CB-1N中都有乘子Y=CB-1，那么Y的经济意义是什么？设B是｛maxz=CXIAX<b,X>0｝的最优基，由Yb=-CB-ib(2-12)式可知Bz*=CB-1b=Y*b.对z求偏导数，得dz* —-b=CB-1=Y*由上式可知，变量j*的经济意义是在其他条件不变的情况下，单位资源变化所引起的目i标函的最优值的变化。j*=1.5,j*=0.125,j*=0.1 2 3这说明是其他条件不变的情况下，若设备增加一台时，该厂按最优计划安排生产可多获利1.5元；原材料A增加1kg，可多获利0.125元；原材料B增加1kg，对获利无影响。从图2-1可看到，设备增加一台时，代表该约束条件的直线由①移至①'，相应的最优解由(4,2)变为(4,2.5)，目标函数z=2X4+3X2.5=15.5，即比原来的增大1.5。又若原材料A增加1kg时，代表该约束方程的直线由②移至②'，相应的最优解从(4,2)变为(4.25,1.875)，目标函数z=2X4.25+3X1.875=14.125。比原来的增加0.125。原材料B增加1kg时，该约束方程的直线由③移至③'，这时的最优解不变。图2-1

B(4,2.5)C(4.25,1.875)A(4,2)；B(4,2.5)C(4.25,1.875)A(4,2)；y*的值代表对第i种资源的估价-影子价格。i这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为‘影子价格”。在该厂现有资源和现有生产方案的条件下，设备的每小时租费为1.5元，1kg原材料A的出让费为除成本外再附加0.125元，1kg原材料B可按原成本出让，这时该厂的收入与自己组织生产时获利相等。影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。第6节 对偶单纯形法前节讲到原问题与对偶问题的解之间的对应关系时指出：在单纯形表中进行迭代时，在力列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，根据性质(2)、(3)可知，已得到最优解。即原问题与对偶问题都是最优解。根据对偶问题的对称性可以这样考虑：若保持对偶问题的解是基可行解，即%-CB-1P<0，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。其优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。方法如下：设原问题 maxz=CXAX=bX>0又设B是一个基。不失一般性，令B=(P,P，…,P),它对应的变量为X=(x,x，…,x)1 2 m B1 2 m当非基变量都为零时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，设(B-1b)1<0，并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持可行解，它的各分量是对应基变量气,x2，...,x的检验数是b=c一z=c一CB-1P=0,i=1,2,…，miiiiBj对应非基变量x^...,七的检验数是b=c一z=c一CB-1P<0,j=m+1,…，njjjjBj每次迭代是将基变量中的负分量x［取出，去替换非基变量中的x.，经基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近。当原问题得到可行解时，便得到了最优解。对偶单纯形法的计算步骤如下：⑴根据线性规划问题，列出初始单纯形表。

检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。确定换出变量按min{(8-ib)1(B-ib)<0}=(B-ib)对应的基变量x为换出变量i i l i确定换入变量在单纯形表中检查%所在行的各系数"F,...,心。若所有七20，则无可行解，停止计算。若存在七<0(T2,...,n)，计算aijc-z—k kaikc-aijc-z—k kaikaij按9规则所对应的列的非基变量气为换入变量，这样才能保持得到的对偶问题解仍为可行解。以a为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。lk重复步骤(1)〜(4)。例6用对偶单纯形法求解2x-x+3x>4

x,x,x>0解先将此问题化成下列形式，以便得到对偶问题的初始可行基maxz=-2x-3x-4x1 2 3-x-2x-x+x=-3

-2x+x-3x+x=-4x>0，jT'2'-'5例6的初始单纯形表，见表2-6。C—-2-3-400CBXBbx1x2x3x4x50x4-3-1-2-1100x5-4[-2]1-301c.z.-2-3-400从表2-6看到，检验数行对应的对偶问题的解是可行解。因力列数字为负，故需进行迭代运算。换出变量的确定：按上述对偶单纯形法计算步骤⑵，即按min{(8-ib).I(B-ib).<0}=(B-ib)〔对应的基变量、为换出变量。计算min(-3,-4)=-4故七为换出变量。换入变量的确定：按上述对偶单纯形法计算步骤(3)，即在单纯形表中检查xl所在行的各系数ai<0(j=1,2,,乃)。若所有侦i>0，则无可行解，停止计算。9=min]-2，-,W卜己=1"-2 -3)-2计算故x[为换入变量。换入、换出变量的所在列、行的交叉处'、-2〃为主元素。按单纯形法计算步骤进行迭代，得表2-7。c—-2-3-400CBXBbx1x2x3x4x50-2x4x1-1201[-5/2]-1/21/23/210-1/2-1/2c.z.0-4-101由表2-7看出，对偶问题仍是可行解，而b列中仍有负分量。故重复上述迭代步骤，得表2-8。c—-2-3-400CBXBbx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/2-1/5-2/5cz00-3/5-8/5-1/5表2-8中，b列数字全为非负，检验数全为非正，故问题的最优解为X*=(1,%,2号,0,0,0)t若对应两个约束条件的对偶变量分别为七,*，则对偶问题的最优解为V*一fa；*v* 8 1，)Y-('y2)-V5V5)从以上求解过程可以看到对偶单纯形法有以下优点：初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。教学小结在正确理解原问题与对偶问题关系的基础上，理解影子价格的含义，掌握对偶单纯形法。教学参考书基本教材：《运筹学》；钱颂迪，郭耀煌