《第二章 对偶理论精选文档.ppt》由会员分享，可在线阅读，更多相关《第二章 对偶理论精选文档.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章 对偶理论本讲稿第一页，共二十八页原始问题min z=CTXs.t.AXbX 0对偶问题Maxw=bTys.t.ATyCy0minbACTCATbTmaxmnmn一、对偶的定义一、对偶的定义本讲稿第二页，共二十八页对偶的定义对偶的定义当原问题为求极小值时，对偶问题为求极大值。原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问
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+2
3、y3+y42-y1+2y2+y3+3y442y1-3y2+2y3-y4-1y10,y2,y30,y40=unr=x10 x20 x3:unrq原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。q原始问题变量的性质影响对偶问题约束条件的性质，用表示原始问题约束条件的性质影响对偶问题变量的性质，用表示本讲稿第五页，共二十八页对偶问题的解p84当原始问题有最优解时，对偶问题也有最优解，而且两者相等；原问题的最优解和对偶问题的最优解构成互补松弛关系；原问题最优表中松弛变量的检验数的反号就是对偶问题的最优解；对偶问题最优表中松弛变量的检验
4、数的反号就是原问题的最优解。本讲稿第六页，共二十八页1、对偶的对偶就是原始问题max z=-CTXs.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=w本讲稿第八页，共二十八页4、原始问题和对偶问题最优解之间
5、的互补松弛关系minz=CTXs.t.AX-u=bX,u0maxw=bTys.t.ATy+v=Cy,v0minz=CTXs.t.AXbX0maxw=bTys.t.ATyCy0对偶引进松弛变量引进松弛变量XTv=0yTu=0互补松弛关系互补松弛关系X，uy，v本讲稿第九页，共二十八页min z=CTXs.t.AX-u=bX,u 0maxw=bTys.t.ATy+v=Cy,v0XTv=0yTu=0mn=yvATICn=Au-IbnmmX原始问题和对偶问题变量、松弛变量的维数原始问题和对偶问题变量、松弛变量的维数本讲稿第十页，共二十八页y1yiymvm+1vm+jvn+mx1xjxnun+1un+i
6、un+m对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjvm+j=0yiun+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0本讲稿第十一页，共二十八页1、单纯形表最优基必须同时满足两个条件右端列中的所有i0可行性条件全部检验数j0最优性条件（1）（2）三、对偶单纯形法三、对偶单纯形法本讲稿第十二页，共二十八页单纯形法的迭代过程单纯形法的迭代过程i0j0i0j0i0j0对偶单纯形法的迭代过程对偶单纯形法的迭代过程i0j0本讲稿第十三页，共二十八页2 2、对偶单纯形法、对偶单纯形法 例题例题1 1min=15y1+5y2+11y3s.t.
7、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右端-15-5-11000s1-3-2-210-5s2-5-1-201-4由表知1的两个基变量均取负值,故它不是可行基,从而不能从1出发应用单纯形法。但由于表(
8、I)中所有j0,我们目的是要保证全部检验数始终为非正的前提下,逐步使全部基变量取的值0,为此要按以下方法换基.(I)本讲稿第十五页，共二十八页对偶单纯形法对偶单纯形法3出基变量确定出基变量确定：可选任何一个取负值的基变量（通常选：可选任何一个取负值的基变量（通常选 取值最小的一个）为出基变量取值最小的一个）为出基变量入基变量的确定入基变量的确定：考虑出基变量行中那些取负值的：考虑出基变量行中那些取负值的ijij,对每个这样的对每个这样的ijij,作比式作比式j j/a aijij令：令：=min=minj j/a aijija aijij0=0=s s/a aisis则取则取x xs s为入基
9、变量。为入基变量。(I)y1y2y3s1s2右端-15-5-11000s1-3-2-210-5s2-5-1-201-4本讲稿第十六页，共二十八页然后进行单纯形迭代,得表（II）(III)-15/20-6-5/2025/2y23/211-1/205/2s2-7/20-1-1/21-3/2(II)00-27/7-10/7-15/7110/7y2014/7-5/73/713/7y1102/71/7-2/73/7 得最优解：y1=3/7,y2=13/7,y3=s1=s2=0 本讲稿第十七页，共二十八页q对偶单纯形法对偶单纯形法对偶单纯形法用来求解最优性条件满足，可行性条件不满足的问题。对偶单纯形法的步
10、骤Step0：从一个最优性条件满足，可行性条件不满足的解出发，确定基变量、非基变量，列出单纯形表，转Step1。Step1：如果右边常数全为非负，得到最优解，算法终止。否则，选择右边常数为负数，绝对值最大的基变量离基，转Step2。Step2：在离基变量行中，选择系数为负数并且和目标函数行的比值最小的元素作为主元，确定进基变量。Step3：对单纯形表进行行变换，使主元为1，主元所在列的其他元素为0，转Step1。本讲稿第十八页，共二十八页1、原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（
11、吨）四、对偶的经济解释四、对偶的经济解释本讲稿第十九页，共二十八页2、对偶问题资源限量（吨）资源价格（元/吨）总租金（元）对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格（ShadowPrice）原始和对偶问题都取得最优解时，最大利润maxz=minw本讲稿第二十页，共二十八页3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0本讲稿第二十一页，共二十八页4、互补松弛关系的经济解释wixn+i=0如果wi0，则xn+i=0如果xn+i0，则wi=0边际利润
12、大于0的资源，在最优生产计划条件下没有剩余wm+jxj=0如果wm+j0，则xj=0如果xj0，则wm+j=0最优生产计划条件下有剩余的资源，其边际利润等于0差额成本大于0（机会成本大于利润）的产品，不安排生产安排生产的产品，差额成本等于0（机会成本等于利润）本讲稿第二十二页，共二十八页maxz=4x1+3x2+5x3s.t.2x1+x2+3x3200 x1+2x2+2x33503x1+4x2+x32202x1+3x2+2x3400 x1，x2，x30产品1产品2产品3资源限量资源12.01.03.0200资源21.02.02.0350资源33.04.01.0220资源42.03.02.040
13、0利润4.03.05.0本讲稿第二十三页，共二十八页引进松弛变量x4,x5,x6，x70,得到：max z=4x1+3x2+5x3s.t.2x1+x2+3x3+x4 =200 x1+2x2+2x3 +x5 =350 3x1+4x2+x3 +x6 =220 2x1+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-
14、(3x1+4x2+x3)=0X7=400-(2x1+3x2+2x3)=1860/11=169.9本讲稿第二十五页，共二十八页这个问题的对偶问题是：Min y=200w1+350w2+220w3+400w4S.t 2w1+w2+3w3+2w4-w5 =4 w1+2w2+4w3+3w4 w6 =3 3w1+2w2+w3+2w4 -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+
15、3w3+2w4=4.18（万元/件）产品2：w1+2w2+4w3+3w4 =3.0（万元/件）产品3：3w1+2w2+w3+2w4 =5.0（万元/件）本讲稿第二十七页，共二十八页产品产品编号123资源利润（元/件）4.03.05.0产量（件）041.852.7机会成本(元/件)4.183.05.0限量（吨）占用（吨）剩余（吨）影子价格（元/吨）差额成本(元/件)0.1800资源资源12.01.03.0200200017/11资源21.02.02.0350189.1160.90资源33.04.01.022022004/11资源42.03.02.0400230.1169.90本讲稿第二十八页，共二十八页