中南民族大学：《运筹学》第二章 对偶问题（叶娟）

对偶问题 对偶规划 2对偶问题的基本性质 3对偶问题的解 4影子价格 5对偶单纯形法

1 对偶问题 1 对偶规划 2 对偶问题的基本性质 3 对偶问题的解 4 影子价格 5 对偶单纯形法

1对偶规划

2 1 对偶规划

对偶问题的提出 例1、生产组织与计划问题 A B 可用资源 煤 劳动力 130 222 30 60 仓库 24 单位利润 4050 A,B各生产多少,可获最大利润?

3 对偶问题的提出 例1、生产组织与计划问题 A, B各生产多少, 可获最大利润? 可用资源 煤 劳动力 仓库 A B 1 2 3 2 0 2 单位利润 40 50 30 60 24

目标函数MaxZ=40x1+50x2 x+2x,≤30 3x1+2x,≤60 约束条件 2x,≤24 x1.x2≥0 如果因为某种原因,不愿意自己生产,而希 望通过将现有资源承接对外加工来获得收益,那 么应如何确定各资源的使用价格?

4 Max Z= 40x1 +50x2 x1 + 2x2  30 3x1 + 2x2  60 2x2  24 x1， x2  0 s.t 目标函数 约束条件 如果因为某种原因，不愿意自己生产，而希 望通过将现有资源承接对外加工来获得收益，那 么应如何确定各资源的使用价格？

Max z=40x,+50x 所得不得低于生产 xn+2x,≤30 的获利 2要使对方能够接受 3x,+2x2≤60 2x,≤24 调三种资源的使用单价分别为y,y2,y xx2≥0 生产单位产品A的资源消耗所得不少于单位产品A的获利 y+32≥40 生产单位产品B的资源消耗所得不少于单位产品B的获利 2y1+2y2+2y3≥50

5 Max Z= 40x1 +50x2 x1 + 2x2  30 3x1 + 2x2  60 2x2  24 x1， x2  0 s.t 目标函数 约束条件 两个原则 1. 所得不得低于生产 的获利 2. 要使对方能够接受 设三种资源的使用单价分别为 y1 , y2 , y3 y1 y2 y3 生产单位产品A的资源消耗所得不少于单位产品A的获利 生产单位产品B的资源消耗所得不少于单位产品B的获利 y1 +3 y2  40 2y1 + 2 y2 + 2y3  50

通过使用所有资源对外加工所获得的收益 W=30n+60y2+24y3 根据原则2,对方能够接受的价格显然是越低越好,因此 问题可归结为以下数学模型: MinW=30y1+60y2+24y3 y1+3y2 ≥40 st〈2y1+2y2+2y3≥50 y1,y2,y3≥0 原线性规划问题称为 此问题为 y1,y2,y3称为

6 通过使用所有资源对外加工所获得的收益 W = 30y1 + 60 y2 + 24y3 根据原则2 ，对方能够接受的价格显然是越低越好，因此 此问题可归结为以下数学模型： Min W = 30y1 + 60 y2 + 24y3 y1 + 3y2  40 2y1 + 2 y2 + 2y3  50 y1 , y2 , y3  0 s.t 目标函数 约束条件 原线性规划问题称为原问题，此问题为对偶问题， y1 , y2 , y3 称为影子价格

例2原间题(P) 实际意义 max Z=4x,+3x 资源分配问题:3 x1<6 种有限的资源生产 2种产晶,决策变 2xn<8 量为2种产晶的产 st 2x1+3x<18 量,目标函数决策 变量系数为2种产 x1,x2 品获得的单位利润, 目标为利润最大化

7 例2 原问题（P） 1 2 1 2 1 2 1 2 max 4 3 6 2 8 . . 2 3 18 , 0 Z x x x x s t x x x x = +       +      实际意义 资源分配问题：3 种有限的资源生产 2种产品，决策变 量为2种产品的产 量，目标函数决策 变量系数为2种产 品获得的单位利润， 目标为利润最大化

对偶间题(D) min w=611+812+18y3 +2y3≥4 maxZ=4x,+3x s.12y2+3y32≥3 11≤6 11,y2,y3≥0 2x<8 st 2x,+3x<18 x,x2≥0

8 对偶问题（D） 1 2 3 1 3 2 3 1 2 3 min 6 8 18 2 4 . . 2 3 3 , , 0 w y y y y y s t y y y y y = + +  +    +     1 2 1 2 1 2 1 2 max 4 3 6 2 8 . . 2 3 18 , 0 Z x x x x s t x x x x = +       +     

对偶问题实际意义 假定管理决策者从另一个角度来讨论这 个问题,不考虑自己生产甲、乙两种产品 去盈利,而是将现有资源标价出售,试间 决策者应该怎样给资源定一个合理的价格?

9 假定管理决策者从另一个角度来讨论这 个问题，不考虑自己生产甲、乙两种产品 去盈利，而是将现有资源标价出售，试问： 决策者应该怎样给资源定一个合理的价格？ 对偶问题实际意义

1,y2 设2y分别表示三种资源的 单位售价 决策者应该考虑卖掉资源的收 入不能低于用资源安排生产的获利

10 设 分别表示三种资源的 单位售价 决策者应该考虑卖掉资源的收 入不能低于用资源安排生产的获利 1 2 3 y y y , , 1 2 3 y y y ,