运筹学对偶理论.ppt

《运筹学对偶理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、件，则数学模型为：反过来问：若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么４种机器的机时如何定价才是最佳决策？线性规划的对偶模型在市场竞争的时代，厂长的最佳决策显然应符合两条：（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线性规划的对偶模型例.写出线性规划问题的对偶问题解：首先将原问题变形为对称形式线性规划的对偶模型线性规划的对

4、偶模型(2)非对称型对偶问题若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。也可直接写出非对称形式的对偶问题。线性规划的对偶模型原问题（或对偶问题）对偶问题（或原问题）约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项目标函数max目标函数min约束条件m个m个变量≤≥0≥≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=线性规划的对偶模型例2写出下列线性规划问题的对偶问题.解：原问题的对偶问题为资源定价问题（LP2）比较原问题（生产计划）对偶问题（资源定价）规范形式的线性规划问题原问题

5、（LP）对偶问题（DLP）规范形式最大化问题:约束条件全为型决策变量全部非负最小化问题:约束条件全为型决策变量全部非负规范形式的对偶关系原问题对偶问题目标函数:maxCX目标函数:minb´Ym个约束条件:AXbm个决策变量:Y0n个决策变量:X0n个约束条件:A´YC´原问题对偶问题非规范形式的对偶关系对非规范形式的对偶关系，只需对上述表进行相应修改即可：例如对于一个最小化问题，若某个决策变量yi0,则期对偶的约束条件为型的;若其某个约束条件是型,则其对应的对偶变量是非正的.非规范形式线性规划的对

6、偶问题1变量取值范围不符合非负要求的情况非规范形式线性规划的对偶问题2约束方程不是“≤”的情况总结约束条件对变量，变量对约束条件；正常对正常，不正常对不正常；变量正常是非负，约束条件正常看目标(max≤，min≥)。课堂作业：求解下面线性规划的对偶规划LPDLP对偶性质例3分别求解下列2个互为对偶关系的线性规划问题分别用单纯形法求解上述2个规划问题，得到最终单纯形表如下表：对偶性质XBb原问题的变量原问题的松弛变量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1

7、/43/2000－1/4－1/2XBb对偶问题的变量对偶问题的剩余变量y1y2y3y4y5y21/4-4/510-1/41/4y31/215/2011/2-3/215/2007/23/2原问题最优表对偶问题最优表对偶性质原问题与其对偶问题的变量与解的对应关系：在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。对偶性质性质1对称性定理：对偶问题的对偶是原问题minW=Ybs.t.YA≥CY≤0maxZ=CXs.t.AX≥bX≥0对偶性质性质2弱对偶原理(弱对偶性)：设和分别是问题(P

8、)和(D)的可行解，则必有推论1:原问题任一可行解的目标函数值是其对偶问题目标函数值的下届；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。推论2:在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。无界如：（原）无可行解（对）对偶性质推论3：在一对对偶问题