苏大张芳华运筹学课件第二章对偶理论.ppt

《苏大张芳华运筹学课件第二章对偶理论.ppt》由会员分享，可在线阅读，更多相关《苏大张芳华运筹学课件第二章对偶理论.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 对偶线性规划对偶的定义对偶问题的性质对偶单纯形法对偶的经济解释灵敏度分析原始问题min z=CTXs.t.AXbX 0对偶问题Maxw=bTys.t.ATyCy0minb ACTC ATbTmaxmnmn一、对偶的定义对偶的定义 当原问题为求极小值时，对偶问题为求极大值。原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问题

2、决策变量的符号决定所对应对偶问题的约束方程的匹配形式。原始问题（prime)与对偶问题之间的关系 极小化问题（min)极大化问题（max)变量 Xj 0 约束 aijwj bi Xj:unr aijwj=bi Xj 0 aijwj bi 约束 aijxj bi 变量 wj 0 aijxj=bi wj:unr aijxj bi wj 0 q对偶问题的形成minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1

3、-3y2+2y3-y4-1y10,y2,y30,y40=unr=x10 x20 x3:unrq原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。q原始问题变量的性质影响对偶问题约束条件的性质，用表示原始问题约束条件的性质影响对偶问题变量的性质，用表示对偶问题的解p84 当原始问题有最优解时，对偶问题也有最优解，而且两者相等；原问题的最优解和对偶问题的最优解构成互补松弛关系；原问题最优表中松弛变量的检验数的反号就是对偶问题的最优解；对偶问题最优表中松弛变量的检验数的反号就是原问题的最优解。1、对偶的对偶就是原始问题max z=-C

4、TXs.t.-AX-bX 0Minw=-bTys.t.-ATy-Cy0maxw=bTys.t.ATyCy0min z=CTXs.t.AXb X 0对偶的定义对偶的定义二、对偶问题的性质2、可行解的目标函数值之间的关系设XF、yF分别是原始问题和对偶问题的可行解z=CTXFyTAXFyTb=w3、最优解的目标函数值之间的关系设Xo、yo分别是原始问题和对偶问题的最优解z=CTXo=yoTAXo=yoTb=w4、原始问题和对偶问题最优解之间的互补松弛关系minz=CTXs.t.AX-u=bX,u0maxw=bTys.t.ATy+v=Cy,v0minz=CTXs.t.AXbX0maxw=bTys.t

5、.ATyCy0对偶引进松弛变量引进松弛变量XTv=0yTu=0互补松弛关系X，uy，vmin z=CTXs.t.AX-u=bX,u 0maxw=bTys.t.ATy+v=Cy,v0XTv=0yTu=0m n=yvATIC n=Au-Ibn mmX原始问题和对偶问题变量、松弛变量的维数y1yiymvm+1vm+jvn+mx1xjxnun+1un+iun+m对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjvm+j=0 yiun+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于01、单纯形表最优基必须同时满足两个条件右端列中的所有i0可行性条件

6、全部检验数j0最优性条件（1）（2）三、对偶单纯形法单纯形法的迭代过程i0j0i0j0i0j0对偶单纯形法的迭代过程i0j02、对偶单纯形法 例题1min=15y1+5y2+11y3s.t.3y1+2y2+2y355y1+y2+2y34y1，y2，y30解:将每个不等式两边乘以-1,再引入松驰变量S1和S2,则上述问题化为:直接写成标准式时有-S1和-S2,则无法有初始基,因此乘个-1min=15y1+5y2+11y3s.t.-3y1-2y2-2y3+S1=-5-5y1-y2-2y3+S2=-4y1，y2，y3,S1,S2,0 对偶单纯形法2建立该问题的初始单纯形表 y1y2y3s1s2右端-

7、15-5-110 0 0s1-3-2-2 1 0-5s2-5-1-2 0 1-4由表知1的两个基变量均取负值,故它不是可行基,从而不能从1出发应用单纯形法。但由于表(I)中所有j0,我们目的是要保证全部检验数始终为非正的前提下,逐步使全部基变量取的值0,为此要按以下方法换基.(I)对偶单纯形法3出基变量确定：可选任何一个取负值的基变量（通常选 取值最小的一个）为出基变量入基变量的确定：考虑出基变量行中那些取负值的ij,对每个这样的ij,作比式j/aij令：=minj/aijaij0=s/ais则取xs为入基变量。(I)y1y2y3s1s2右端-15-5-110 0 0s1-3-2-2 1 0-

8、5s2-5-1-2 0 1-4然后进行单纯形迭代,得表（II）(III)-15/20-6-5/2 0 25/2y23/2 1 1-1/2 0 5/2s2-7/2 0-1-1/2 1-3/2(II)0 0-27/7-10/7-15/7 110/7y20 1 4/7-5/7 3/7 13/7y11 0 2/7 1/7-2/7 3/7 得最优解：y1=3/7,y2=13/7,y3=s1=s2=0 q对偶单纯形法对偶单纯形法用来求解最优性条件满足，可行性条件不满足的问题。对偶单纯形法的步骤Step0：从一个最优性条件满足，可行性条件不满足的解出发，确定基变量、非基变量，列出单纯形表，转Step1。St

9、ep1：如果右边常数全为非负，得到最优解，算法终止。否则，选择右边常数为负数，绝对值最大的基变量离基，转Step2。Step2：在离基变量行中，选择系数为负数并且和目标函数行的比值最小的元素作为主元，确定进基变量。Step3：对单纯形表进行行变换，使主元为1，主元所在列的其他元素为0，转Step1。1、原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）四、对偶的经济解释2、对偶问题资源限量（吨）资源价格（元/吨）总租金（元）对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为

10、m种资源的影子价格（ShadowPrice）原始和对偶问题都取得最优解时，最大利润maxz=minw3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于04、互补松弛关系的经济解释wixn+i=0如果wi0，则xn+i=0如果xn+i0，则wi=0边际利润大于0的资源，在最优生产计划条件下没有剩余wm+jxj=0如果wm+j0，则xj=0如果xj0，则wm+j=0最优生产计划条件下有剩余的资源，其边际利润等于0差额成本大于0（机会成本大于利润）的产品，不安排生产安排生产的产品，差额成本等于0

11、（机会成本等于利润）maxz=4x1+3x2+5x3s.t.2x1+x2+3x3200 x1+2x2+2x33503x1+4x2+x32202x1+3x2+2x3400 x1，x2，x30产品1 产品2 产品3资源限量资源1 2.0 1.0 3.0 200资源2 1.0 2.0 2.0 350资源3 3.0 4.0 1.0 220资源4 2.0 3.0 2.0 400利润4.0 3.0 5.0引进松弛变量x4,x5,x6，x70,得到：max z=4x1+3x2+5x3 s.t.2x1+x2+3x3+x4=200 x1+2x2+2x3+x5=350 3x1+4x2+x3+x6=220 2x1+

12、3x2+2x3+x7=400 xi0得到最优解：X1=0,x2=460/11=41.82,x3=580/11(件），最大利润z=389.09(万元），可以得到资源的剩余量：X4=200-(2x1+x2+3x3)=0(t)X5=350-(x1+2x2+2x3)=1770/11=160.9(t)X6=220-(3x1+4x2+x3)=0X7=400-(2x1+3x2+2x3)=1860/11=169.9 这个问题的对偶问题是：Min y=200w1+350w2+220w3+400w4 S.t 2w1+w2+3w3+2w4-w5=4 w1+2w2+4w3+3w4 w6=3 3w1+2w2+w3+2w

13、4-w7=5 wi0 利用互补松弛关系，得到：W1=17/11,w2=0,w3=4/11,w4=0,w5=2/11 即四种资源的影子价格为：W1=17/11,w2=0,w3=4/11,w4=0 由此可以计算出三种产品的机会成本：产品1：2w1+w2+3w3+2w4=4.18（万元/件）产品2：w1+2w2+4w3+3w4=3.0（万元/件）产品3：3w1+2w2+w3+2w4=5.0（万元/件）产品产品编号1 2 3资源利润（元/件）4.0 3.0 5.0产量（件）0 41.8 52.7机会成本(元/件)4.18 3.0 5.0限量（吨）占用（吨）剩余（吨）影子价格（元/吨）差额成本(元/件)0.18 0 0资源资源1 2.0 1.0 3.0 200 200 0 17/11资源2 1.0 2.0 2.0 350 189.1 160.9 0资源3 3.0 4.0 1.0 220 220 0 4/11资源4 2.0 3.0 2.0 400 230.1 169.9 0