运筹学第二章线性规划的对偶理论.pptVIP

例已知线性规划问题x1+x2+2x3+x4+3x5≥42x1－x2+3x3+x4+x5≥3minω=2x1+3x2+5x3+2x4+3x5x1,x2,x3,x4,x5≥0其对偶问题的最优解为y1*=4/5,y2*=3/5；z=5。试用对偶理论找出原问题的最优解。解：对偶问题maxz＝4y1+3y2y1+2y2≤2①y1－y2≤3②2y1+3y2≤5③y1﹐y2≥0y1+y2≤2④3y1+y2≤3⑤C=(2,3,5,2,3)b=(4,3)T11213A=2-1311YAC确定约束条件Y=(y1,y2)原对min变≥0≤0无max约≤≥＝约≥≤＝变≥0≤0无关系表形成原对min变≥0≤0无max约≤≥＝约≥≤＝变≥0≤0无解：对偶问题maxz＝4y1+3y2y1+2y2≤2①y1－y2≤3②2y1+3y2≤5③y1﹐y2≥0y1+y2≤2④3y1+y2≤3⑤C=(2,3,5,2,3)b=(4,3)T11213A=2-1311YAC确定约束条件Y=(y1,y2)关系表形成设Xξ=(xξ1,xξ2)T，Yξ=(yξ1,yξ2,yξ3,yξ4,yξ5)把y1*=4/5,y2*=3/5代入约束条件中可得Yξ=(0,14/5,8/5,2/5,0)据互补松弛性：YξX*=0YξX*=14/5x2*+8/5x3*+2/5x4*=0所以x2*=x3*=x4*=0又因Y*Xξ=4/5xξ1+3/5xξ2=0所以xξ1=xξ2=04.3对偶问题的基本性质设Xξ=(xξ1,xξ2)T，Yξ=(yξ1,yξ2,yξ3,yξ4,yξ5)把y1*=4/5,y2*=3/5代入约束条件中可得Yξ=(0,14/5,8/5,2/5,0)据互补松弛性：YξX*=0YξX*=14/5x2*+8/5x3*+2/5x4*=0所以x2*=x3*=x4*=0又因Y*Xξ=4/5xξ1+3/5xξ2=0所以xξ1=xξ2=0因为所以x1*+x2*+2x3*+x4*+3x5*+xξ1=42x1*－x2*+3x3*+x4*+x5*+xξ2=3x1*+3x5*=42x1*+x5*=3x1*=1，x5*=1因此，原问题最优解为X*=(1，0，0，0，1)T，ω*=5。对偶问题的提出原问题与对偶问题的关系对偶问题的基本性质对偶单纯形法灵敏度分析第二章线性规划4.4对偶单纯形法1﹑对偶单纯形法与单纯形法的区别原理：由性质7可知：在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，根据性质4，5可知，已得到最优解。即原问题与对偶问题都是最优解。思路：在进行迭代时，保持对偶问题的解是基可行解，即cj－CBB-1pj≤0，而原问题通过逐步迭代，达到基可行解，这样就得到最优解。1.1对偶单纯形法的思路4.4对偶单纯形法1.2对偶单纯形法与单纯形法的区别单纯形法：在迭代中，保持b列中得到的是原问题的基可行解，逐步得到对偶问题的基可行解。对偶单纯形法：在逐步迭代中，保持检验数行cj－CBB-1pj≤0，即保持对偶问题的解是基可行解。通过迭代得到原问题的基可行解。说明：对偶单纯法是运用对偶原理求解原问题的一种方法，而不是求解对偶问题的单纯法。2﹑对偶单纯形法求解步骤2.1对偶可行的基解：设X(0)是原问题的基解，其对应的基为B，记Y=CBB-1，若Y是对偶问题的基可行解。即C－CBB-1A≤0，则称X(0)是原问题的对偶可行的基解。ξ克西ksi*第二章线性规划解：设生产x1的产品I，x2的产品II，则目标函数maxz＝2x1+3x2约束条件x1+2x2≤8