第二章 对偶理论PPT讲稿.ppt
第二章 对偶理论第1页，共28页，编辑于2022年，星期二原始问题min z=CTXs.t.AXbX 0对偶问题Maxw=bTys.t.ATyCy0minbACTCATbTmaxmnmn一、对偶的定义一、对偶的定义第2页，共28页，编辑于2022年，星期二对偶的定义对偶的定义当原问题为求极小值时，对偶问题为求极大值。原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问题决策变量的符号决定所对应对偶问题的约束方程的匹配形式。第3页，共28页，编辑于2022年，星期二原始问题（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 第4页，共28页，编辑于2022年，星期二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-3y2+2y3-y4-1y10,y2,y30,y40=unr=x10 x20 x3:unrq原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。q原始问题变量的性质影响对偶问题约束条件的性质，用表示原始问题约束条件的性质影响对偶问题变量的性质，用表示第5页，共28页，编辑于2022年，星期二对偶问题的解p84当原始问题有最优解时，对偶问题也有最优解，而且两者相等；原问题的最优解和对偶问题的最优解构成互补松弛关系；原问题最优表中松弛变量的检验数的反号就是对偶问题的最优解；对偶问题最优表中松弛变量的检验数的反号就是原问题的最优解。第6页，共28页，编辑于2022年，星期二1、对偶的对偶就是原始问题max z=-CTXs.t.-AX-bX 0Minw=-bTys.t.-ATy-Cy0maxw=bTys.t.ATyCy0min z=CTXs.t.AXb X 0对偶的定义对偶的定义二、对偶问题的性质二、对偶问题的性质第7页，共28页，编辑于2022年，星期二2、可行解的目标函数值之间的关系设XF、yF分别是原始问题和对偶问题的可行解z=CTXFyTAXFyTb=w3、最优解的目标函数值之间的关系设Xo、yo分别是原始问题和对偶问题的最优解z=CTXo=yoTAXo=yoTb=w第8页，共28页，编辑于2022年，星期二4、原始问题和对偶问题最优解之间的互补松弛关系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第9页，共28页，编辑于2022年，星期二min z=CTXs.t.AX-u=bX,u 0maxw=bTys.t.ATy+v=Cy,v0XTv=0yTu=0mn=yvATICn=Au-IbnmmX原始问题和对偶问题变量、松弛变量的维数原始问题和对偶问题变量、松弛变量的维数第10页，共28页，编辑于2022年，星期二y1yiymvm+1vm+jvn+mx1xjxnun+1un+iun+m对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjvm+j=0yiun+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0第11页，共28页，编辑于2022年，星期二1、单纯形表最优基必须同时满足两个条件右端列中的所有i0可行性条件全部检验数j0最优性条件（1）（2）三、对偶单纯形法三、对偶单纯形法第12页，共28页，编辑于2022年，星期二单纯形法的迭代过程单纯形法的迭代过程i0j0i0j0i0j0对偶单纯形法的迭代过程对偶单纯形法的迭代过程i0j0第13页，共28页，编辑于2022年，星期二2 2、对偶单纯形法、对偶单纯形法 例题例题1 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第14页，共28页，编辑于2022年，星期二 对偶单纯形法对偶单纯形法2建立该问题的初始单纯形表y1y2y3s1s2右端-15-5-11000s1-3-2-210-5s2-5-1-201-4由表知1的两个基变量均取负值,故它不是可行基,从而不能从1出发应用单纯形法。但由于表(I)中所有j0,我们目的是要保证全部检验数始终为非正的前提下,逐步使全部基变量取的值0,为此要按以下方法换基.(I)第15页，共28页，编辑于2022年，星期二对偶单纯形法对偶单纯形法3出基变量确定出基变量确定：可选任何一个取负值的基变量（通常选：可选任何一个取负值的基变量（通常选 取值最小的一个）为出基变量取值最小的一个）为出基变量入基变量的确定入基变量的确定：考虑出基变量行中那些取负值的：考虑出基变量行中那些取负值的ijij,对每个这样的对每个这样的ijij,作比式作比式j j/a aijij令：令：=min=minj j/a aijija aijij0=0=s s/a aisis则取则取x xs s为入基变量。为入基变量。(I)y1y2y3s1s2右端-15-5-11000s1-3-2-210-5s2-5-1-201-4第16页，共28页，编辑于2022年，星期二然后进行单纯形迭代,得表（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 第17页，共28页，编辑于2022年，星期二q对偶单纯形法对偶单纯形法对偶单纯形法用来求解最优性条件满足，可行性条件不满足的问题。对偶单纯形法的步骤Step0：从一个最优性条件满足，可行性条件不满足的解出发，确定基变量、非基变量，列出单纯形表，转Step1。Step1：如果右边常数全为非负，得到最优解，算法终止。否则，选择右边常数为负数，绝对值最大的基变量离基，转Step2。Step2：在离基变量行中，选择系数为负数并且和目标函数行的比值最小的元素作为主元，确定进基变量。Step3：对单纯形表进行行变换，使主元为1，主元所在列的其他元素为0，转Step1。第18页，共28页，编辑于2022年，星期二1、原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）四、对偶的经济解释四、对偶的经济解释第19页，共28页，编辑于2022年，星期二2、对偶问题资源限量（吨）资源价格（元/吨）总租金（元）对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格（ShadowPrice）原始和对偶问题都取得最优解时，最大利润maxz=minw第20页，共28页，编辑于2022年，星期二3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0第21页，共28页，编辑于2022年，星期二4、互补松弛关系的经济解释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（机会成本等于利润）第22页，共28页，编辑于2022年，星期二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.0400利润4.03.05.0第23页，共28页，编辑于2022年，星期二引进松弛变量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第24页，共28页，编辑于2022年，星期二得到最优解：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第25页，共28页，编辑于2022年，星期二这个问题的对偶问题是：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 第26页，共28页，编辑于2022年，星期二利用互补松弛关系，得到：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（万元/件）第27页，共28页，编辑于2022年，星期二产品产品编号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第28页，共28页，编辑于2022年，星期二
