第03章 对偶单纯形法与灵敏度分析 运筹学

第3章 线性规划问题的 对偶与灵敏度分析1

本章内容重点 线性规划的对偶问题的概 念、理论及经济意义 线性规划的对偶单纯形法

线性规划的灵敏度分析2

3.1 线性规划对偶问题3.1.1 对偶问题的提出： 若第二章例2.1问题的设备都用于 外协加工，工厂收取加工费。试问： 设备 A、B、C 每工时各如何收费才 最有竞争力？ 设 y1 ,y2 ,y3 分别为每工时设备 A、B、C 的收取费用。3

例2.1:某工厂拥有A、B、C三种类型 的设备，生产甲、乙两种产品。每件产品 在生产中需要占用的设备机时数，每件产 品可以获得的利润以及三种设备可利用的 时数如下表所示。求获最大利润的方案。产品甲 产品乙

3.1 线性规划对偶问题

设备A设备B

32

21

设备能力 (h) 65 40

设备C利润(元/件)

01500

32500

75

Max z = 1500x1 + 2500x2 原问题 s.t. 3x1 + 2x2 ≤ 65 2x1 + x2 ≤ 40 3x2 ≤ 75 x1 , x2 ≥ 0 Min f = 65y1+ 40y2 + 75y3 对偶问题 s.t. 3y1+2y2 ≥1500 (不少于甲产品的利润) 2y1+y2+3y3 ≥2500(不少于乙产品的利润) y1, y2 , y3 ≥ 05

3.1.2 对偶规划的形式 有对称形式和非对称形式。 对称形式的对偶规划之间具有下面的 对应关系： (1) 若一个模型为目标求“极大”,约 束为“小于等于”的不等式，则它的 对偶模型为目标求“极小”,约束是 “大于等于”的不等式。即 “max,≤” 和 “min,≥” 相对应。6

(2) 从约束系数矩阵看：一个模型中 为 A ,则另一个模型中为AT 。一个 模型是m个约束，n个变量，则它的 对偶模型为n个约束，m个变量。(3) 从数据b、C的位置看：在两个规 划模型中，b和C的位置对换。 (4) 两个规划模型中的变量皆非负。

对称形式：(LP) Max z = cT x s.t. Ax ≤ b x ≥0 “Max ≤ ”

互为对偶(DP) Min f = bT y s.t. AT y ≥ c y ≥0 “Min ≥”

原问题与对偶问题的对应关系

练习：写出下面问题的对偶问题

max Z 8 x1 10 x2 2 x3 2 x1 x2 3x3 70 4 x 2 x 2 x 80 2 3 1 x3 15 3x1 2x 2 x3 50 1 x1 , x2 , x3 0

参考答案：

min f 70 y1 80 y 2 15 y 3 50 y 4 2 y1 4 y 2 3 y 3 2 y 4 8 y 2y 2 y 4 10 1 2 3 y1 2 y 2 y 3 2 y1 , y 2 , y 3 , y 4 0 11

非对称形式的对偶规划:对非对称形式，可以按照下面的对应关系直接给出其对偶规划

(1) 将模型统一为“max,≤”或“min, ≥” 的形式，对于其中的等式约束按 下面(2)、(3)中的方法处理； (2) 若原规划的某个约束条件为等式约 束，则在对偶规划中与此约束对应的 那个变量取值没有非负限制； (3) 若原规划的某个变量的值没有非负 限制

,则在对偶问题中与此变量对应 的那个约束为等式。12

下面对关系(2)作一说明。对于关系 (3)可以给出类似的解释： 设原规划中第一个约束为等式： a11x1 + … + a1nxn = b1 那么，它与下面两个不等式等价

a11 x1 ... a1n x n b1 a11 x1 ... a1n x n b113

原规划模型可以写成max Z c1 x1 c n x n a11 x1 a1n x n = b1 a x a x b 1n n 1 11 1 a x a x b m1 1 mn n m x j 0, j 1,2, , m 14

转化为对称形式，直接写出对偶规划min f b1 y1 ' b1 y1 ' ' b2 y2 bm ym a11 y1 ' a11 y1 ' ' a m 1 ym c1 a y ' a y ' ' a y c m2 m 2 12 1 12 1 a y ' a y ' ' a y c mn m n 1n 1 1n 1 y1 ' , y1 ' ' , y2 , , ym 0, y1没有非负限制

这里，把y1看作是 y1 =y1’ - y1’’, 于是y1没有非负限制。15

例 写出下面线性规划的对偶规划模型max Z x1 x2 5 x3 7 x4 x1 3 x2 2 x3 x4 25 2x 7x 2 x4 60 1 3 30 2 x1 2 x2 4 x 3 5 x4 10, x1 , x 2 0, x3没有非负限制