④
10:11
二、例子：写出下面线性规划的 对偶规划模型
max x1 x2 x3 min 25 y1 2 y2 3 y3 s.t. x x 2 x 25 s.t. y y y 1 1 2 3 1 2 3 原问题： x1 2 x2 x3 2 y1 2 y2 y3 1, x1 x2 x3 3 2 y1 y2 y3 1 x1 , x2 0 y1 0, y2 0
原问题
max z 1500 y1 2500 y2 s.t . 3 y1 2 y2 65 2 y1 y2 40 3 y2 75 y1 , y2 , y3 0
10:11
对偶问题
一、对偶定义
1、对称形式（典则形式）的对偶定义
T max b y min c x 互为对偶 ( LP) s.t. Ax b ( DP) s.t. AT y c x 0 y0 T
10:11
3.3 对偶单纯形法(续4）
解: 引进松弛变量,化为标准型 min 2 x1 3x2 4 x3 s.t. x1 2 x2 x3 x4 3 2 x1 x2 3x3 x5 4 x1 , x2 , x3 , x4 , x5 0 取B ( p4 , p5 ) I 2 , 得一个对偶可行基本解(0,0,0,-3,-4)T
第三章 线性规划的对偶问题
• 3.1 对偶问题 • 3.2 对偶理论 • 3.3 对偶单纯形法
10:11
3.1 对偶问题
例子：某工厂拥有A、B、C 三种类型的设备，生产甲、乙 两种产品。每件产品在生产中需要占用的设备机时数，每 件产品可以获得的利润以及三种设备可利用的时数如下表 所示。求获最大利润的方案。 产品甲 设备A 设备B 设备C 利润（元/件） 3 2 0 1500 产品乙 2 1 3 2500 设备能力 （h） 65 40 75
x3 -4 -1 -3
x4 0 0 -3 -4
离基变量xr： b r min{bi } 0
i
进基变量xk： k / yrk min{ j / yrj | yrj 0}
j
（保持对偶可行性,yrj为r行第j列的元素）
10:11
3.3 对偶单纯形法(续2）
(2) 从约束系数矩阵看：一个模型中为 Ａ ， 则另一个模型中为 AT。一个模型是 m个约束， n个变量，则它的对偶模型为n个约束，m个变 量。 (3)从数据b、c的位置看：在两个规划模型 中，b和c的位置对换。 (4)两个规划模型中的变量皆非负。
10:11
2. 标准形式的对偶定义
min c x 标准形式 s.t. Ax b, x0
j
(4)以yrk 为主元进行消元,得到一个改进的对偶可行基本解, 返回步骤(2).
10:11
3.3 对偶单纯形法(续3）
例子 用对偶单纯形法求解线性规划问题 min 2 x1 3 x2 4 x3 s.t. x1 2 x2 x3 3 2 x1 x2 3 x3 4 x1 , x2 , x3 0
10:11
3.2 对偶理论
① 对称性：对偶问题的对偶是原问题 ② 弱对偶性：若x和y分别是(LP)和(DP)的 可行解，则cTx≥bTy. ③ 可行解为最优的充分条件：设x和y分别 是(LP)和(DP)的可行解，若cTx=bTy，则 x和y分别是(LP)和(DP)的最优解. ④ 无界性：若(LP)和(DP)之一为无界解， 则其对偶问题无可行解.
另一个问题：若设备 A 、 B 、 C 都用于外协加工，工厂收取 加工费。试问：设备 A 、 B 、 C 每工时各如何收费才最有 竞争力？
10:11
3.1 对偶问题
min f 65 x1 40 x2 75 x3 s.t. 3 x1 2 x2 1500 (不少于甲产品的利润) 2 x1 x2 3 x3 2500 (不少于乙产品的利润) x1 , x2 , x3 0
10:11
3.2 对偶理论（续）
⑤ 对偶定理：若(LP)和(DP)均有可行解， 则它们都有最优解，且最优值相同. ⑥ 最优基本可行解之间的关系：若(LP)存 在一个对应基B的最优基本可行解，则 单纯形乘子yT=cBTB-1是(DP)的一个最优 解. ⑦ 互补松弛性：设x和y分别是(LP)和(DP) 的可行解，则x和y分别是(LP)和(DP)的 最优解的充要条件为yT(Ax-b)=0，且 (cT-yTA)x=0.
10:11
对偶规则
① ② ③ 若原问题是极小化问题，则对偶问题是极大化问题；若 原问题是极大化问题，则对偶问题是极小化问题 在原问题和对偶问题中，约束右端向量与目标函数的系 数向量恰好互换 对于极小化问题的“≥”型约束(极大化问题的“≤”型 约束)，相应的对偶变量有非负限制；对于极小化问题 的“≤”型约束(极大化问题的“≥”型约束)，相应的对 偶变量有非正限制；对于原问题的“=”型约束，相应的 对偶变量无正负限制 对于极小化问题具有非负限制的变量(极大化问题具有 非正限制的变量),在其对偶问题中，相应的约束为“≤” 型约束；对于极小化问题具有非正限制的变量(极大化 问题具有非负限制的变量),在其对偶问题中，相应的约 束为“≥”型约束；对于原问题中无正负限制的变量， 在其对偶问题中，相应的约束为“=”型约束
10:11
对称形式(典则形式)的对偶定义（续1）
一对对称形式的对偶规划之间具有 下面的对应关系。 (1) 若一个模型为目标求“极大”， 约束为“小于等于”的不等式，则它的 对偶模型为目标求“极小”，约束是 “大于等于”的不等式。即“max，≤” 和“min，≥”相对应。
10:11
对称形式(典则形式)的对偶定义（续2）
T
互为对偶

max bT y 对偶形式 s.t. AT y c, y无符号限制
10:11
推导过程
T max c x T min c x s.t. Ax b, s.t. Ax b, Ax b, x0 x0
3.3 对偶单纯形法(续1） • 基本思想：从原问题的一个对偶 可行基本解出发,求改进的对偶可 行基本解（指对偶问题的目标函 数值得到改进）,当得到的对偶可 行基本解是原问题的可行解时,就 达到了最优解.
10:11
改进的对偶可行基本解的求取
f x4 x5
f 1 0 0
x1 -2 -1 -2
x2 -3 -2 1
• 计算步骤：
(1)给定一个初始对偶可行基本解,设想应的基为B; (2)若b B b 0, 则停止计算,现行的对偶可行基本解 为最优解, 否则,令 br min{bi } 0;
i 1
(3)若对所有的j, yrj 0,则停止计算,原问题无可行解.否则, 令 k / yrk min{ j / yrj | yrj 0};
f x2 x1
10:11
最优解x*=(11/5,2/5,0,0,0)T,f*=28/5
3.3 对偶单纯形法(续6）
• 初始对偶可行基本解的求取
– 观察法 Min cTx(c≥0) S.t. Ax≤b, x≥0 初始对偶可行基本解为（0,b）,其中b部分对 应松弛变量. – 扩充法
10:11
10:11
3.3 对偶单纯形法
min cT x (3.3.1) s.t. Ax b, x0
T max b y (3.3.2) T s . t . A yc
•
•
10:11
对偶可行基本解：设x是标准问题（原问题） (3.3.1)对应于基B的一个基本解(不要求是基 本可行解),若yT=cBTB-1是对偶问题(3.3.2)的可 行解（即ATy-c≤0或检验数j=cBTB-1pj -cj ≤0 , j=1,2, …,n), 则称x是原问题(3.3.1)的一个对偶 可行基本解. 当对偶可行基本解是原问题的可行解时,由于 检验数均小于零，因此它就是原问题的一个 最优解.
f x4 x5
10:11
f 1 0 0
x1 -2 -1 -2
x2 -3 -2 1
x3 -4 -1 -3
x4 0 1 0
x5 0 0 1
RHS 0 -3 -4
3.3 对偶单纯形法(续5）
f x4 x1
f 1 0 0 f 1 0 0 x1 0 0 1 x1 0 0 1 x2 -4 -5/2 -1/2 x2 0 1 0 x3 -1 1/2 3/2 x3 -9/5 -1/5 7/5 x4 0 1 0 x4 -8/5 -2/5 -1/5 x5 -1 1/2 -1/2 x5 -9/5 -1/5 -3/5 RHS 4 -1 2 RHS 28/5 2/5 11/5
max cT x min bT u bT v A b u T T s.t. x , s.t. A A c, A b v x0 u, v 0 min bT u bT v max bT y y v u T T s.t. A u A v c, s.t. AT y c, u, v 0 y无符号限制