1、运筹学教程第二章 线性规划的对偶理论与灵敏度分析运筹学教程一、对偶问题的提出一、对偶问题的提出1、 对偶思想举例对偶思想举例周长一定的矩形中，以正方形面积周长一定的矩形中，以正方形面积最大；面积一定的矩形中，以正方形最大；面积一定的矩形中，以正方形周长最小；周长最小； 第一节第一节 LP的的 对偶问题对偶问题运筹学教程对偶 理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么， 对偶问题是怎样提出的，为什么会产生这样一种问题呢？3运筹学教程线性规划的对偶理论引例
2、俩家具制造商间的对话：唉 !我想租您的木工和油漆工一用。咋样？价格嘛 好说，肯定不会让您兄弟吃亏讪。 王老板做家具赚了大钱，可惜我老李有高科技产品，却苦于没有足够的木工和油漆工咋办？只有租咯。Hi： 王老板，听说近来家具生意很好，也帮帮兄弟我哦 !家具生意还真赚钱，但是现在的手机生意这么好，不如干脆把我的木工和油漆工租给他，又能收租金又可做生意。价格嘛 好商量，好商量。只是 . 家具 -王 总 李 总桌子 椅子 能力木工 4 3 120漆工 2 1 50价格 50 30运筹学教程线性规划的对偶理论王老板的 家具生产模型 ：x1 、 x2是桌、椅生产量。Z是家具销售总收入（总利润）。max Z
3、= 50x1 + 30x2s.t. 4x1+3x2 120（ 木工） 2x1+ x2 50 （ 油漆工）x1， x2 0原始线性规划问题，记为（ P）王老板的 资源出租模型 ：y1、 y2单位木、漆工出租价格。W是资源出租租金总收入。min W =120y1 + 50y2s.t. 4y1+2y2 503y1+ y2 30y1， y2 0对偶线性规划问题，记为（ D）桌子 椅子 能力木工 4 3 120漆工 2 1 50价格 50 30运筹学教程线性规划的对偶理论王老板按（ D） 的解 y1 、 y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），
4、又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金 W最少）。按时下最流行的一个词，叫什么来着按时下最流行的一个词，叫什么来着 运筹学教程对偶问题Min w=YbT=YTbs.t. ATY CTY 0原始问题max z=CXs.t. AX bX 0maxbACCTATbTminmnmn运筹学教程2、 换个角度审视生产计划问题换个角度审视生产计划问题例 要求制定一个生产计划方案，在设备A,B和调试三种资源限制下，使得产品的总利润最大 。maxZ=2x1+x25x2156x1+2x224x1+x25x1,x20st.运筹学教程转换思路 :投资人 :如果某投资公司准备购买该工厂，它至少应付出
5、多大的代价，才能使工厂自己放弃生产产品 、 ，而将可利用的资源都出让。被兼并人 :该工厂的底线：最低可接受价格，指按这种价格转让资源比自己生产产品 、 合算的价格。设 y1,y2， y3为代表单位时间这三种资源的出让价格，为了使工厂出让资源合算，显然应该使出让原来生产一件产品 的资源所得收入不低于自己生产产品 的利润，即 0y1+6y2+1y3 2对于产品 ，同样可以建立类似的约束条件 5y1+2y2+1y31项 目 产 品 产 品 每天可用能力设备 A(h)设备 B(h)调试 工序 (h)06152115245利 润 (元 ) 2 1y1y2y3运筹学教程当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的： Zmax=Wmin显然在满足这两个约束的前提下，价格越高，该工厂越合算，但价格太高，投资人方面又不会愿意购买。因此，我们需要确定的价格是 使工厂合算的最低价格，故应建立目标函数： min w=15y1+24y2+5y3 项 目 产 品 产 品 每天可用能力设备 A(h)设备 B(h)调试 工序 (h)06152115245利 润 (元 ) 2 1
