运筹学电子教案-LP对偶理论.ppt

《运筹学电子教案-LP对偶理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？且看下面详解……线性规划LinearProgramming（LP）对偶基本理论对偶问题？......1唉!我想租您的木工和油漆工一用。咋样？价格嘛……好说，肯定不会让您兄弟吃亏讪。引例——俩家具制造商间的对话：线性规划LinearProgramming（LP）对偶基本理论王老板做家具赚了大钱，可惜我老李有高科

2、技产品，却苦于没有足够的木工和油漆工咋办？只有租咯。Hi：王老板，听说近来家具生意好惨了，也帮帮兄弟我哦!家具生意还真赚钱，但是现在的手机生意这么好，不如干脆把我的木工和油漆工租给他，又能收租金又可做生意。价格嘛……好商量，好商量。只是…...王老板李老板2王老板的家具生产模型：x1、x2是椅、桌生产量。Z是家具销售总收入（总利润）。maxZ=50x1+30x2s.t.4x1+3x2≤1202x1+x2≤50x1，x2≥0原始线性规划问题，记为（P）线性规划LinearProgramming（LP）对偶基本理论王老板的资源出租模型：y1、y2单

3、位木、漆工出租价格。W是资源出租租金总收入。minW=120y1+50y2s.t.4y1+2y2≥503y1+y2≥30y1，y2≥0对偶线性规划问题，记为（D）3线性规划LinearProgramming（LP）对偶基本理论王老板按（D）的解y1、y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。按时下最流行的一个词，叫什么来着————双赢4原始（对偶）——对偶（原始）关系表线性规划LinearProgramming（LP）对

4、偶基本理论原问题（对偶问题）对偶问题（原问题）目标函数类型max变量个数与约束条件个数的对应关系目标函数系数与右边项的对应关系原问题变量类型与对偶问题约束条件类型的对应关系原问题约束条件类型与对偶问题变量类型的对应关系min≥0变量类型≤0无限制约束条件个数m变量个数n右边项的系数对应目标函数系数目标函数各变量系数对应约束条件右边项的系数约束条件个数m变量个数n≥约束条件类型≤=≥约束条件类型≤=≤0变量类型≥0无限制5对偶理论基本定理：1、对称性定理2、弱对偶定理3、强对偶定理原问题与对偶问题解的对应关系表线性规划LinearProgramm

5、ing（LP）对偶基本理论问题与解的状态无界解对偶问题有最优解无可行解一定有最优解无界解无可行解原问题可能不可能不可能不可能不可能不可能可能可能6对偶问题解的经济解释——影子价格我们已经明白原始线性规划与对偶线性规划之间形式上的对偶以及他们的解之间的关系，那么对偶问题的解除了前面引例中提到的租金这种经济含义外其深刻的经济含义是什么呢？对偶问题解的经济含义分析：从单纯形法的矩阵描述中，目标函数取值Z=CBB-1，和检验数CN-CBB-1N中都有乘子Y=CBB-1。设B是{maxZ=CX

6、AX≤b，X≥0}的最优基矩阵，由强对偶定理知Z*=CX*=

7、CBB-1b=Y*b=W*由此线性规划LinearProgramming（LP）对偶基本理论Z*bZ*bi（Y*b）bi=CBB-1=Y*或==yi*7对偶问题解的经济含义：由上面分析——对偶问题解中变量yi*的经济含义是在其他条件不变的情况下，单位第i种“资源”变化所引起的目标函数最优值的变化。所以，yi*描述了原始线性规划问题达到最优时（各种“资源”都处于最优的配置时），第i种“资源”的某种“价值”，故称其为第i种“资源”的影子价格。下面图解阐述影子价格的直观含义：采用单纯形法求解得（P）的最优解、最优基矩阵如下线性规划Line

8、arProgramming（LP）对偶基本理论（P）的最优解为X*=（15，20，0，0）TB=（p2，p1）=3412（D）的最优解为Y*=CBB-1=（5，15）CB=（C2，C1）=（30，50）B-1=1-2-1/23/28王老板的家具生产模型的图解：线性规划LinearProgramming（LP）对偶基本理论x1x24x1+3x2=1202x1+x2=50L0：50x1+30x2D可行域1350=50x1+30x2（15，20）（P）maxZ=50x1+30x2s.t.4x1+3x2≤1202x1+x2≤50x1，x2≥09影子价格

9、的直观含义：线性规划LinearProgramming（LP）对偶基本理论x1x24x1+3x2=1202x1+x2=50L0：50x1+30x2D可