运筹学PPT对偶理论(-Duality--Theory-)

运筹学(OperationsResearch)管理工程系核心课程Chapter2对偶理论(DualityTheory)线性规划的对偶模型对偶性质对偶问题的经济解释－影子价格对偶单纯形法灵敏度分析参数线性规划本章主要内容：Page3线性规划的对偶模型设某工厂生产两种产品甲和乙，生产中需4种设备按A，B，C，D顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表：产品数据表设备产品ABCD产品利润（元／件）甲21402乙22043设备可利用机时数（时）1281612问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？1.对偶问题的现实来源Page4线性规划的对偶模型解：设甲、乙型产品各生产x1及x2件，则数学模型为：0,124164821222.32max2121212121xxxxxxxxtsxxz反过来问：若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么４种机器的机时如何定价才是最佳决策？Page5线性规划的对偶模型在市场竞争的时代，厂长的最佳决策显然应符合两条：（1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。（2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。设A、B、C、D设备的机时价分别为y1、y2、y3、y4，则新的线性规划数学模型为：0,,,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyyPage6线性规划的对偶模型把同种问题的两种提法所获得的数学模型用表2表示，将会发现一个有趣的现象。原问题与对偶问题对比表A（y1）B（y2）C（y3）D（y4）甲（x1）21402乙（x2）220431281612minωmaxzPage7线性规划的对偶模型2.原问题与对偶问题的对应关系0,124164821222.32max2121212121xxxxxxxxtsxxz0,,,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy原问题（对偶问题）对偶问题（原问题）Page8线性规划的对偶模型（1）对称形式特点：目标函数求极大值时，所有约束条件为≤号，变量非负;目标函数求极小值时，所有约束条件为≥号，变量非负.0XbAXCXmaxZ：P0YCYATTbYWDTmin:已知P，写出DPage9线性规划的对偶模型例2.1写出线性规划问题的对偶问题0,,5643732532432max321321321321321xxxxxxxxxxxxxxxZ解：首先将原问题变形为对称形式0,,5643732532432max32132132132321xxxxxxxxxxxxxxxZPage10线性规划的对偶模型0,,4675343232532min321321321321321yyyyyyyyyyyyyyyW对偶问题：Page11原问题－对偶问题关系例：maxz=c1x1+c2x2+c3x3s.t.a11x1+a12x2+a13x3≤b1a21x1+a22x2+a23x3＝b2a31x1+a32x2+a33x3≥b3x1≥0，x2≤0，x3无约束maxz=c1x1+c2x2+c3x3s.t.a11x1+a12x2+a13x3≤b1a21x1+a22x2+a23x3≤b2-a21x1-a22x2-a23x3≤-b2-a31x1-a32x2-a33x3≤-b3x1≥0，x2≤0，x3无约束转化成Maxz=CXAX≤bX≥0令x2=-x2’x3=x3’-x3’’maxz=c1x1-c2x2’+c3x3’-c3x3’’s.t.a11x1-a12x2’+a13x3’-a13x3’’≤b1a21x1-a22x2’+a23x3’–a23x3’’≤b2-a21x1+a22x2’-a23x3’+a23x3’’≤-b2-a31x1+a32x2’-a33x3’+a33x3’’≤-b3x1x2’x3’x3’’≥0a21x1+a22x2+a23x3≥b2Page12对偶问题minω＝b1y1+b2y2’-b2y2’’-b3y3’s.t.a11y1+a21y2’–a21y2’’-a31y3’≥c1-a12y1-a22y2’+a22y2’’+a32y3’≥-c2a13y1+a23y2’–a23y2’’-a33y3’≥c3-a13y1-a23y2’+a23y2’’+a33y3’≥-c3yj≥0，j＝1…3令y2=y2’-y2’’y3=-y3’minω＝b1y1+b2y2+b3y3s.t.a11y1+a21y2+a31y3≥c1-a12y1-a22y2-a32y3≥-c2a13y1+a23y2+a33y3≥c3-a13y1-a23y2-a33y3≥-c3y1≥0，y2无约束，y3≤0a13y1+a23y2+a33y3=c3a12y1+a22y2+a32y3≤c2maxz=c1x1-c2x2’+c3x3’-c3x3’’s.t.a11x1-a12x2’+a13x3’-a13x3’’≤b1a21x1-a22x2’+a23x3’–a23x3’’≤b2-a21x1+a22x2’-a23x3’+a23x3’’≤-b2-a31x1+a32x2’-a33x3’+a33x3’’≤-b3x1x2’x3’x3’’≥0Page13线性规划的对偶模型(2)非对称型对偶问题若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。也可直接按教材表2-2中的对应关系写出非对称形式的对偶问题。Page14线性规划的对偶模型原问题（或对偶问题）对偶问题（或原问题）约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项目标函数max目标函数min约束条件m个m个变量≤≥0≥≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=Page15线性规划的对偶模型例2.2写出下列线性规划问题的对偶问题.无约束4321432142143214321,0,,0643247235234532maxxxxxxxxxxxxxxxxxxxxZ解：原问题的对偶问题为无约束32132131321321321,0,01725433322234645minyyyyyyyyyyyyyyyyyWPage16对偶性质性质1对称性定理：对偶问题的对偶是原问题minW=Ybs.t.YA≥CY≥0maxZ=CXs.t.AX≤bX≥0Page17对偶性质性质2弱对偶原理(弱对偶性)：设和分别是问题(P)和(D)的可行解，则必有0X0YnjmiiijjbyxcbYCX1100即：推论1:原问题任一可行解的目标函数值是其对偶问题目标函数值的下届；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。推论2:在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。Page18对偶性质推论3：在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行（如D），则该可行的问题目标函数值无界。性质3最优性定理：如果是原问题的可行解，是其对偶问题的可行解，并且:0X0Ywz:00＝即BYCX则是原问题的最优解，是其对偶问题的最优解。0X0YPage19对偶性质性质4强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。Xˆ还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。性质5互补松弛性：、为原问题、对偶问题最优解，若对应某行约束条件的对偶变量≠0，则该约束条件取严格等式；若约束条件取严格不等式，则对应的对偶变量＝0。YˆPage20对偶性质性质5的应用：利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。Page21对偶性质例2.4已知线性规划3,2,1,0162210243max321321321jxxxxxxxxxxzj的最优解是X＊=(6,2,0)T,求其对偶问题的最优解Y＊。解：写出原问题的对偶问题，即0,1422321610min2121212121yyyyyyyyyyw0,,,,1422321610min5432152142132121yyyyyyyyyyyyyyyyw标准化Page22对偶性质设对偶问题最优解为Y＊＝(y1，y2),由互补松弛性定理可知，X＊和Y＊满足：00ssXYXY即：0),)(,(0),,)(,,(5421321543TTxxyyxxxyyy因为X1≠0，X2≠0，所以对偶问题的第一、二个约束的松弛变量等于零，即y3＝0，y4＝0，带入方程中：422322121yyyy解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为：Y＊=(1,1)，最优值w=26。Page23对偶性质例2.5已知线性规划无约束＝321321321321,0,06422minxxxxxxxxxxxxz的对偶问题的最优解为Y＊=(0,-2)，求原问题的最优解。解:对偶问题是021264max2121212121yyyyyyyyyyw无约，＝标准化0,,0,21264max43212142132121yyyyyyyyyyyyyyw无约＝Page24对偶性质设对偶问题最优解为X＊＝(x1，x2，x3)T,由互补松弛性定理可知，X＊和Y＊满足：0),)(,(0),,)(,,(5421321543TTxxyyxxxyyy将Y＊带入由方程可知，y3＝y5＝0，y4＝1。∵y2=-2≠0∴x5＝0又∵y4=1≠0∴x2＝0将x2，x5分别带入原问题约束方程中，得：643131xxxx解方程组得：x1=-5,x3=-1,所以原问题的最优解为X＊=(-5,0,-1)，最优值z=-12Page25对偶性质例2.3分别求解下列2个互为对偶关系的线性规划问题052426155.2max5214213221jxxxxxxxxxtsxxz012526.52415min5321432321iyyyyyyyytsyyyw分别用单纯形法求解上述2个规划问题，得到最终单纯形表如下表：Page26对偶性质XBb原问题的变量原问题的松弛变量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2000－1/4－1/2jXBb对偶问题的变量对偶问题的剩余变量y1y2y3y4y5y21/4-4/510-1/41/4y31/215/2011/2-3/215/2007/23/2j原问题最优表对偶问题最优表Page27对偶性质原问题最终表的检验数行的相反数对应对偶问题的基解。若检验数均≤0，则其相反数为对偶问题的基可行解。原问题的松弛变量（初始基可行解）检验数的相反数为对偶问题决策变量的解。原问题的决策变量中检验数的相反数为对偶问题剩余变量的解。Page28对偶问题的经济解释－影子价格1.影子价格的数学分析：0D0minmaxYCYAXbAXPYbWCXZ定义：在一对