运筹学PPT对偶理论(-Duality--Theory-)课件.ppt

《运筹学PPT对偶理论(-Duality--Theory-)课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学(OperationsResearch)管理工程系核心课程Chapter2对偶理论(DualityTheory)线性规划的对偶模型对偶性质对偶问题的经济解释－影子价格对偶单纯形法灵敏度分析参数线性规划本章主要内容：线性规划的对偶模型设某工厂生产两种产品甲和乙，生产中需4种设备按A，B，C，D顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表：产品数据表设备产品ABCD产品利润（元／件）甲21402乙22043设备可利用机时数（时）1281612问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？1.对偶问题的现实来源线性

2、规划的对偶模型解：设甲、乙型产品各生产x1及x2件，则数学模型为：反过来问：若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么４种机器的机时如何定价才是最佳决策？线性规划的对偶模型在市场竞争的时代，厂长的最佳决策显然应符合两条：（1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。（2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。设A、B、C、D设备的机时价分别为y1、y2、y3、y4，则新的线性规划数学模型为：线性规划的对偶模型把同种问题的两种提法所获得的数学模型用表

3、2表示，将会发现一个有趣的现象。原问题与对偶问题对比表A（y1）B（y2）C（y3）D（y4）甲（x1）21402乙（x2）220431281612minωmaxz线性规划的对偶模型2.原问题与对偶问题的对应关系原问题（对偶问题）对偶问题（原问题）线性规划的对偶模型（1）对称形式特点：目标函数求极大值时，所有约束条件为≤号，变量非负;目标函数求极小值时，所有约束条件为≥号，变量非负.已知P，写出D线性规划的对偶模型例2.1写出线性规划问题的对偶问题解：首先将原问题变形为对称形式线性规划的对偶模型原问题－对偶问题关系例：maxz=c1x1+c2x2+c3x3s.t.a11x1+a

4、12x2+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’’≤b1a21x

5、1-a22x2’+a23x3’–a23x3’’≤b2-a21x1+a22x2’-a23x3’+a23x3’’≤-b2-a31x1+a32x2’-a33x3’+a33x3’’≤-b3x1x2’x3’x3’’≥0a21x1+a22x2+a23x3≥b2对偶问题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

6、…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’-a23

7、x3’+a23x3’’≤-b2-a31x1+a32x2’-a33x3’+a33x3’’≤-b3x1x2’x3’x3’’≥0线性规划的对偶模型(2)非对称型对偶问题若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。也可直接按教材表2-2中的对应关系写出非对称形式的对偶问题。线性规划的对偶模型原问题（或对偶问题）对偶问题（或原问题）约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项目标函数max目标函数min约束条件m个m个变量≤≥0≥≤0=无约束变量n个n个约束条件≥