第二章 对偶理论与灵敏度分析

对偶理论与灵敏度分析

第二章 对偶理论与灵敏度分析对偶问题的提出 原问题与对偶问题的关系 对偶问题的基本性质 对偶问题的经济解释---影子价格 对偶单纯形法 灵敏度分析 参数线性规划

对偶理论与灵敏度分析

§2.1 对偶问题的提出 一、对偶线性规划问题【例1】 某工厂计划安排生产Ⅰ、Ⅱ两种产品，已知每种单位产品的 利润、生产单位产品所需的设备台时及A、B两种原材料的消耗、 现有原材料和设备台时的定额如下表所示：Ⅰ 设 备 1 4 0 2 原 材 料 A 原 材 料 B 每单位产品利润(万元) 每单位产品利润(万元) Ⅱ 2 0 4 3 8台时 台时 16Kg 12Kg

原问题的策略: 原问题的策略: 问应如何安排生产才能使工 厂获利最大？ 厂获利最大？

现在的策略: 现在的策略: 假设不生产Ⅰ 假设不生产Ⅰ、Ⅱ产品 ,而是计划将 现有资源出租或出售,从而获得利润, 现有资源出租或出售,从而获得利润,这 时需要考虑如何定价才合理? 时需要考虑如何定价才合理?

对偶理论与灵敏度分析

Ⅰ 设 备 1 4 0 2

Ⅱ 2 0 4 3 8台时 台时 16Kg 12Kg

原问题的模型

原 材 料 A 原 材 料 B 每单位产品利润(万元) 每单位产品利润(万元)

设x1、x2分别表示计划生产产品Ⅰ、Ⅱ的单位 数量，由题意原问题的模型为：

max f = 2x1 + 3x2 x 1 + 2x 2 ≤ 8 ≤ 16 4x 1 s . t . 4 x 2 ≤ 12 x 1, x 2 ≥ 0

工厂获得最大利润

符合资源限制

对偶理论与灵敏度分析

Ⅰ 设 备 1 4 0 2 原 材 料 A 原 材 料 B 每单位产品利润(万元) 每单位产品利润(万元)

Ⅱ 2 0 4 3 8台时 台时 16Kg 12Kg

新问题的模型

改变策略后，需要考虑如何给资源定价的问题！设y1、y2 、y3分别表示出租单位设备台时的租金和出售单位 原材料A、B的利润. 则：

y1+4y2≥2, ≥2,

2y1+4y3≥3

工厂出租设备、原材料的租金要大于生产的利润才合算。 工厂出租设备、原材料的租金要大于生产的利润才合算。 工厂把所有设备台时和资源都出租和出让，其收入为：

g = 8 y1 + 16 y2 + 12 y3要寻找使租用者支付的租金最少的策略。 要寻找使租用者支付的租金最少的策略。即求 min g

对偶理论与灵敏度分析

工厂改变策略以后的数学模型为 数学模型为： 数学模型为min g = 8y1 +16y2 +12y3用户所付租金最少

y1 + 4y 2 ≥ 2 s .t . 2y 1 + 4y 3 ≥ 3 y ≥ 0 , i = 1, 2 ,3 i

工厂获得相应利润

对偶理论与灵敏度分析

原模型和对偶模型的联系与区别

maxf = 2x1 +3x2 x1 + 2 x2 ≤ 8 4 x1 ≤ 16 s.t . 4 x2 ≤ 12 x , x ≥ 0 1 2

min g = 8 y1 + 16 y2 + 12 y3 y1 + 4y2 ≥ 2 s.t. 2y1 + 4y3 ≥ 3 y ≥ 0, i = 1,2,3 i

联系在于，它们都是关于工厂生产经营的模型,并且使用相同 的数据； 区别在于,它们所反映的实质内容是完全不同的：前者是站在 工厂经营者 经营者的立场上追求工厂的销售收入最大 销售收入

最大，而后者则是站在 经营者 销售收入最大 谈判对手的立场上寻求应付工厂租金最少 谈判对手 租金最少的策略。 租金最少

对偶理论与灵敏度分析

由以上不难得到，所谓对偶规划 对偶规划，就是与线性规划 对偶规划 原问题相对应并使用同一组数据按照特定方法形成的另 一种反映不同性质问题的线性规划模型。

对偶理论与灵敏度分析

二、对偶规划的一般数学模型对偶规划一原问题与对偶问题之间存在着严格的对应关系。如原问题如求目标函数最大化，对偶问题即求目标函数最小化；原问题目标函数的系数变 成为对偶问题的右边项，而原问题的约束的右边项则变成为对偶问题目 标函数的系数；对偶问题的系数矩阵是原问题系数矩阵的转置。原问题的一般模型可定义为： 相应的对偶问题的一般模型可定义为：

maxZ = c1 x1 + c2 x2 + ... + cn xn minS = b1 y1+b2 y2 + ...+ bm ym s.t. a11 x1 + a12 x2 + ... + a1n xn ≤ b1 s.t. a11y1 + a21y2 + ...+ am1 ym ≥ c1 a12 y1 + a22 y2 + ...+ am2 ym ≥ c2 a21 x1 + a22 x2 + ... + a2n xn ≤ b2 am1 x1 + am2 x2 + ... + amn xn ≤ bm x1 , x2 ,...,xn ≥ 0… … ….

a1n y1 + a2n y2 + ...+ amn ym ≥ cn y1, y2 ,...,ym ≥ 0

…

…

…

对偶理论与灵敏度分析

矩阵形式上述的原问题P和对偶问题 D还可以用矩阵形式写为： (P) max Z= cx (D) min S= yb s.t. Ax ≤b s.t. yA ≥ c y≥0 x ≥0 其中 y = ( y1 , y 2 ,.., y m )上述的对偶模型满足下列两个条件：(1)所有的变量都是非 负的；(2)约束条件都是同向不等式，称为对称型对偶模型 对称型对偶模型。而 对称型对偶模型 非对称型的， 在当原问题转化为标准型以后所建立的对偶模型则是非对称型的 非对称型的 这时该如何写出其相应的对偶模型？

(P) maxZ= cx s.t. Ax =b x≥0

(D) minS= yb s.t. yA≥c y为自由变量

对偶理论与灵敏度分析

§2. 2 原问题与对偶问题的对应关系当我们讨论对偶问题时必定是指一对问题，因为没有原问 题也就不可能有对偶问题。原问题和对偶问题总是相依存在的。 同时，原问题和对偶问题之间也并没有严格的界线，它们互为 对偶，谁都可以是原问题，谁也都可以是对偶问题。

对偶理论与灵敏度分析

对偶线性规划与原问题的比较: 对偶线性规划与原问题的比较max f = 2x1 + 3x2 x1 + 2 x2 ≤ 8 4 x1 ≤ 16 s.t . 4 x2 ≤ 12 x , x ≥ 0 1 2

min g = 8 y1 + 16 y2 + 12 y3 y1 + 4y2 ≥ 2 s.t. 2y1 + 4y3 ≥ 3 y ≥ 0, i = 1,2,3 i

(1) 一个问题中的约束条件个数 约束条件个数等于另一个问题的变量数 变量数。 约束条件个数 变量数 (2) 一个问题的目标函数中的系数 目标函数中的系数是另外一个问题中约束不等式 目标函数中的系数 约束不等式 的右端项。 的右端项 (3) 约束条件在一个问题是“≤”,在另一个问题是“≥”。 “ ” “ ” (4) 目标在一个问题是求

极小 求极小，在另一个问题是求极大 求极大。 求极小 求极大

下表给出了原问题模型和对偶模型的对应关系，可以看作是 一个线性规划原问题转化为对偶问题的一般规律。

对偶理论与灵敏度分析

线性规划问题对偶关系表(原问题 原问题(maxZ),注意掌握记忆规律) 原问题原问题(或对偶问题) 原问题 目标函数最大化 (maxZ) n 个变量 m 个约束 约束条件限定向量(右边项) 目标函数价值向量(系数) ≥0 ≤ 0 无限制 ≥ 约束 ≤ = 变量 对偶问题(或原问题) 对偶问题 目标函数最小化( minS) n 个约束 m 个变量 目标函数价值向量(系数) 约束条件限定向量(右边项) 约束 ≥ ≤ = ≤0 0 ≥0 无限制

变量

对偶理论与灵敏度分析

原问题(maxZ)与对偶之关系 与对偶之关系： 原问题 与对偶之关系原问题 目标函数max 目标函数 对偶问题 目标函数min 目标函数n个 约 ≥ 束 ≤ 条 = 件

n个 变 ≥ 0 量 ≤ 0 无约束

原问题(maxZ)口诀 原问题(maxZ)口诀: 变量决定约束是同号 口诀:

约 m 个 束 ≥ 条 ≤ 件 =

变 量 无约束 m个 ≤0 ≥0

原问题(maxZ)口诀 原问题(maxZ)口诀: 约束决定变量是反号 口诀:

对偶理论与灵敏度分析

线性规划问题对偶关系表(原问题 原问题(min S)注意掌握记忆规律) 原问题原问题(或对偶问题) 原问题 目标函数最小化 (minS) n 个变量 m 个约束 约束条件限定向量(右边项) 目标函数价值向量 ≥0 ≤ 0 无限制 ≥ 约束 ≤ = 变量 对偶问题(或原问题) 对偶问题 目标函数最大化( maxZ ) n 个约束 m 个变量 目标函数价值向量(系数) 约束条件限定向量 约束 ≤ ≥ = ≥ 0 ≤ 0 无限制

变量

对偶理论与灵敏度分析

原问题(minS) 与对偶之关系 与对偶之关系： 原问题原问题 目标函数min 目标函数 对偶问题 目标函数max 目标函数

n个 变 ≥ 0 量 ≤ 0 无约束 约 m 个 束 ≥ 条 ≤ 件 =

n个 约 ≤ 束 ≥ 条 = 件

原问题(minS)口诀 原问题(minS)口诀: 变量决定约束是反号 口诀:

m个 变 ≥0 量 ≤0 无约束

原问题(minS)口诀 原问题(minS)口诀: 约束决定变量是同号 口诀:

对偶理论与灵敏度分析

例1 写出下列问题的对偶问题： max Z=2x1+x2 5x2 ≤ 15  6x1 +2x2 ≤ 24  x1+x2 ≤ 5 x1 , x2 ≥ 0

原问题(或对偶问题) 原问题 目标函数最大化 (maxZ) n 个变量 m 个约束 约束条件限定向量(右边项) 目标函数价值向量(系数) ≥0 ≤ 0 无限制 ≥ 约束 ≤ =

对偶问题(或原问题) 对偶问题 目标函数最小化( minS) n 个约束 m 个变量 目标函数价值向量(系数) 约束条件限定向量(右边项) 约束 ≥ ≤ = ≤0 0 变量 ≥0 无限制

变量

变量决定约束是同号, 变量决定约束是同号,约束决

定变量是反号

解： 依线性规划问题的对偶关系，有： min w=15y1+24y2+5y3s.t.

6y2+y3 ≥ 2  5y1 +2y2 +y3 ≥1  y1 , y2 , y3 ≥ 0

(还可依对偶问题写出原问题)

对偶理论与灵敏度分析

例2 写出下列问题的对偶问题： Min S = x1 3 x2 + 4x3 2x 1 4 x2 + x3 ≤ 1 s.t.

原问题(或对偶问题) 原问题 目标函数最小化 (minS) n 个变量 m 个约束 约束条件限定向量(右边项) 目标函数价值向量 ≥0 ≤ 0 无限制

对偶问题(或原问题) 对偶问题 目标函数最大化( maxZ ) n 个约束 m 个变量 目标函数价值向量(系数) 约束条件限定向量 约束 ≤ ≥ =

变量 x1 + 3 x2 + 2x3 ≤ 4 ≥ 0 ≥ + x3 ≤ 3 -2 x1 变量 ≤ 0 约束 ≤ = 无限制 x1,x2,x3 ≥0 变量决定约束是反号, 变量决定约束是反号,约束决定变量是同号

解： 依线性规划问题的对偶关系，有： maxZ = y1 4 y 2 + 3 y3 s.t. 2y 1 y 2 2 y3 ≤ 1

4y 1+3 y 2 ≤ -3 y1 + 2 y 2 + y3 ≤ 4 y1 ≤ 0 , y2 ≤ 0 ,y3 ≤ 0 (还可依对偶问题写出原问题)

对偶理论与灵敏度分析

练习：试求下列线性规划问题的对偶问题max Z = 2 x1 + 4 x2 3x3 x1 x 2 + x3 ≤ 10 s.t. x1 + 4 x2 3x3 = 5 3x1 + 2 x2 5 x3 ≥ 8 x1 ≥ 0 , x2 ≤ 0

答案： 答案： min S = 10 y1 5 y 2 + 8 y3s.t.

y1 y 2 + 3 y3 ≥ 2 y1 + 4 y 2 + 2 y3 ≤ 4 y1 3 y 2 5 y3 = 3 y1 ≥ 0 , y3 ≤ 0

对偶理论与灵敏度分析

练习：试求下列线性规划问题的对偶问题m f = 2x1 + 3x 2 5x3 + x 4 in x1 + x 2 3x3 + x 4 ≥ 5 x4 ≤ 4 2x1 + 2x 2 x 2 + x3 + x 4 ≤ 6 x1 ≤ 0, x 2 , x3 ≥ 0, x 4无约束

答案： 答案：

maxZ=5y1+4y2+6y3 y1+2y2≥ 2  y1 +2y2 +y3 ≤ 3  -3y1 +y3 ≤ -5 y1 -y2 +y3=1 y1 ≥ 0, y2 , y3 ≤ 0

对偶理论与灵敏度分析

§2.3 对偶问题的基本性质定理1 (对称性定理) 即对偶问题的对偶是原问题。 定理2 (弱对偶定理) 设x和y分别是原问题和对偶问题的可行解，则必有cx≤yb 定理3 (无界性) 若原问题(对偶问题)为无界解，则其对偶问题(原问题)为 无可行解。 若原问题有可行解对偶问题无可行解，则原问题一定无界； 反之，如对偶问题有可行解原问题无可行解，则对偶问题一定无 界。

对偶理论与灵敏度分析

定理4 (可行解是最优解的性质) 设X*是原问题的可行解，Y*是对偶问题的可行解，当 CX*=Y*b时， X*与Y*是最优解 。 * * * * 定理5 (强对偶定理) 若原问题有最优解，那么对偶问题也有最优解，且目标 函数值相等。 综合上述结论得原问题与对偶问题的解的关系

本文来源：https://www.bwwdw.com/article/06xe.html