运筹学 (第三版) 第2章 对偶理论 《运筹学》教材编写组编写 和 灵敏度分析 第3节 对偶问题 的提出 钱颂迪制作 清华大学出版社
运筹学 (第三版) 《运筹学》教材编写组 编写 清华大学出版社 第2章 对偶理论 和 灵敏度分析 第3节 对偶问题 的提出 钱颂迪制作
第2章对偶理论和灵敏度分析 第3节对偶问题的提出
第2章 对偶理论和灵敏度分析 第3节 对偶问题的提出
第3节对偶问题的提出 ·对偶是什么:对同一事物(或问 题),从不同的角度(或立场) 提出对立的两种不同的表述
第3节 对偶问题的提出 • 对偶是什么:对同一事物(或问 题),从不同的角度(或立场) 提出对立的两种不同的表述
例如 在平面内,矩形的面积与其周长之间 的关系,有两种不同的表述方法。 (1)周长一定,面积最大的矩形是 正方形。 ·(2)面积一定,周长最短的矩形是 正方形
例如 在平面内,矩形的面积与其周长之间 的关系,有两种不同的表述方法。 • (1)周长一定,面积最大的矩形是 正方形。 • (2)面积一定,周长最短的矩形是 正方形
这是互为对偶关系的表述 这种表述有利于加深对事物的认 和理解。 线性规划问题也有对偶关系
这是互为对偶关系的表述。 • 这种表述有利于加深对事物的认 识和理解。 • 线性规划问题也有对偶关系
第1章例1的不同表述 现从另一角度来讨论这个问题 假设该工厂的决策者决定不生产产品I、Ⅱ,而 将其所有资源出租或外售。这时工厂的决策者就 要考虑给每种资源如何定价的问题。设用y1,y2 y3分别表示出租单位设备台时的租金和出让单位 原材料A,B的附加额。他在做定价决策时,做 如下比较:若用1个单位设备台时和4个单位原 料A可以生产一件产品I,可获利2元,那么生 产每件产品I的设备台时和原材料出租或出让的 所有收入应不低于生产一件产品I的利润,这就 有y1+4y2>2
第1章例1的不同表述 • 现从另一角度来讨论这个问题。 假设该工厂的决策者决定不生产产品Ⅰ、Ⅱ,而 将其所有资源出租或外售。这时工厂的决策者就 要考虑给每种资源如何定价的问题。设用y1,y2, y3分别表示出租单位设备台时的租金和出让单位 原材料A,B的附加额。他在做定价决策时,做 如下比较:若用1个单位设备台时和4个单位原材 料A可以生产一件产品Ⅰ,可获利2元,那么生 产每件产品Ⅰ的设备台时和原材料出租或出让的 所有收入应不低于生产一件产品Ⅰ的利润,这就 有 y1+4y2 ≥2
同理将生产每件产品Ⅱ的设备台 时和原材料出租或出让的所有收 入应不低于生产一件产品Ⅱ的利 润,这就有 2y1+4y33
• 同理将生产每件产品Ⅱ的设备台 时和原材料出租或出让的所有收 入应不低于生产一件产品Ⅱ的利 润,这就有 2y1 +4y3 ≥3
把工厂所有设备台时和资源都出租或出 让,其收入为 G=8y1+16y2+12
• 把工厂所有设备台时和资源都出租或出 让,其收入为 ω=8y1 +16y2 +12y3
从工厂的决策者来看当然O愈大愈 好;但受到接受方的制约,从接受 者来看他的支付愈少愈好,所以工 的决策者只能在满足大于等于所 有产品的利润条件下,提出一个尽 可能低的出租或出让价格,才能实 现其原意,为此需解如下的线性规 划问题
• 从工厂的决策者来看当然ω愈大愈 好;但受到接受方的制约,从接受 者来看他的支付愈少愈好,所以工 厂的决策者只能在满足大于等于所 有产品的利润条件下,提出一个尽 可能低的出租或出让价格,才能实 现其原意,为此需解如下的线性规 划问题
称这个线性规划问题为例1线性规划 问题(这里称原问题)的对偶问题。 °mino=8y1+16y2+12y3 y1+4y ≥2 +4y2≥3 ≥0,i=1,2,3 (2-8
称这个线性规划问题为例1线性规划 问题(这里称原问题)的对偶问题。 • min ω=8y1 +16y2 +12y3 • y1 +4y2 ≥2 • 2y1 +4y3≥3 • yi≥0,i=1,2,3 (2-8)