管理运筹学讲义第3章对偶规划.ppt

《管理运筹学讲义第3章对偶规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、管理运筹学-管理科学方法中山大学南方学院工商管理系演讲：王甜源2第3章对偶规划Subtitle学习要点理解线性规划问题的对偶问题构建线性规划问题的对偶模型正确理解对偶规划的基本性质掌握影子价值的涵义及其应用资源总存量和分配量增减决策3设某工厂生产两种产品甲和乙，生产中需4种设备按A，B，C，D顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表：产品数据表设备产品ABCD产品利润（元／件）甲21402乙22043设备可利用机时数（时）1281612问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得

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

3、4，则新的线性规划数学模型为：第一节对偶规划的数学模型6把同种问题的两种提法所获得的数学模型用表2表示，将会发现一个有趣的现象。原问题与对偶问题对比表A（y1）B（y2）C（y3）D（y4）甲（x1）21402乙（x2）220431281612minωmaxz第一节对偶规划的数学模型72.原问题与对偶问题的对应关系原问题（对偶问题）对偶问题（原问题）第一节对偶规划的数学模型8生产计划问题例.某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在设备A、B加工，最后都需在设备C上装配。经测算得到相关数据如表所示。应如何制定生产计划，使总利

4、润为最大。据市场分析，单位甲乙产品的销售价格分别为73和75元，试确定获利最大的产品生产计划。产品设备工时消耗甲乙工时成本元/h生产能力hABC200234201510161032第一节对偶规划的数学模型一、对偶问题的提出9第一节线性规划的一般模型(1)决策变量：设x1为甲产品的产量，x2为乙产品的产量。(2)约束条件：生产受设备能力制约，能力需求不能突破有效供给量。设备A的约束条件表达为2x1≤16同理，设备B的加工能力约束条件表达为2x2≤10设备C的装配能力也有限，其约束条件为3x1+4x2≤32(3)目标函数：目标是企业利润最大化

5、maxZ=3x1+5x2(4)非负约束：甲乙产品的产量为非负x1≥0，x2≥0综上的LP模型：10第一节对偶规划的数学模型若该厂的产品平销，现有另一企业想租赁其设备。厂方为了在谈判时心中有数，需掌握设备台时费用的最低价码，以便衡量对方出价，对出租与否做出抉择。在这个问题上厂长面临着两种选择：自行生产或出租设备。首先要弄清两个问题：①合理安排生产能取得多大利润?②为保持利润水平不降低，资源转让的最低价格是多少？问题①的最优解：x1=4，x2=5，Z*=37。一、对偶问题的提出11第一节对偶规划的数学模型一、对偶问题的提出出让定价假设出让A、

6、B、C设备所得利润分别为y1、y2、y3原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有2y1+0y2+3y3≥3同理，对乙产品而言，则有0y1+2y2+4y3≥5设备台时出让的价格（希望出让的价格最少值以获得市场优势）min16y1+10y2+32y3显然还有y1，y2，y3≥012第一节对偶规划的数学模型一、对偶问题的提出例1的对偶问题的数学模型对偶问题的最优解：y1=0，y2=1/2，y3=1，W*=37两个问题的目标函数值相等并非偶然前者称为线性规划原问题，则后者为对偶问题，反之亦然。

7、对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。min=16y1+10y2+32y32y1+0y2+3y3≥30y1+2y2+4y3≥5y1，y2，y3≥0S.t.maxZ=3x1+5x22x1≤162x2≤103x1+4x2≤32x1,x2≥0S.t.13（1）对称形式特点：目标函数求极大值时，所有约束条件为≤号，变量非负;目标函数求极小值时，所有约束条件为≥号，变量非负.已知P，写出D第一节对偶规划的数学模型14例2.1写出线性规划问题的对偶问题解：首先将原问题变形为对称形式第一节对偶规划的数学模型15第一节

8、对偶规划的数学模型16(2)非对称型对偶问题若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。第一节对偶规划的数学模型17原问题（或对偶问题）对偶问题（或原问题）约束条件右端项目标