线性规划 4 对偶理论与灵敏度分析(1)

n a u j 1 ij j
bi , i M 3
j N1
j N2

m a y i 1 ij i m a y i 1 ij i m a y i 1 ij i
cj , cj , cj ,
j N1 j N2 j N3
uj 0 ,
uj 0 ,
x4 1 0 0
x5 0 1 1 2 0 0
x1 x 2 x 3 x 4 x 5 x2 1 1 4
5 13
3 x 4 13 0 4 1 1 1 4 4 2 3 5 0 4 0 1 4 4 1 4
x1 x 2 x 3 x1 1 0 x2 0 1 0 0
1 2 1 2
3 13 4 13 6 13
m i 1 aij yi c j ,
m a y cj , i 1 ij i m a y cj , i 1 ij i
j N1 j N2 j N3
典则形的对偶（对称形式）
max s .t . cT x Ax b x0
m in b T y s .t . AT y c y0
若已得上述线性规划的一个最优解，问：
当参数c j、b j、a ij 中的一些发生变化时， 最优解是否 发生变化？若发生变化 ，是否要从头开始计算 ？
设 B 为上述线性规 划的一个最优基， 相应的单纯形表为
xT B xB
0 T c T c T B 1 N c T B 1 b N B B
T T
BT I nm
是对偶 问题的 一个基
y
T 1 T (c B B )
y 0 , y s1 0 , y s 2 0
y s1 0 y s 2 ( c T B 1 N ) T c N B
ys1、ys2 为剩余变量。
是对应的基本解
xT B xB Im 0T xT N B 1 N cT cT B 1 N N B xT A B 1 B 1b c T B 1 c T B 1b B B
min bT y s.t . AT y c
称之为（LP）的对偶规划。
一般地，可以定义线性规划 (P) 的对偶问题 (D)如下：
原 问 题( P ) max
对 偶 问 题( D ) min

n c x j 1 j j

m b i 1 i
yi
s.t .


n a x j 1 ij j
bi , i M1
s.t . Bx B Nx N I m x A b xB 0 , x N 0 , x A 0
其中 B 是原问题的一个可 行基， xA 是人工变量。
对偶问题即为
m in b y s .t . B T y I m y s1 c B N y I n m y s 2 c N
考虑标准形线性规划
( LP) max z c T x
s.t . Ax b ,
x0
设已有一个对偶可行基 B，即
cT cT B 1 A 0T , B
x i1 在 B 对 应 的 基 本 解 中 ， 基 量 的 值 x B 变 xi m
B 1b x il ( B 1 b ) l 0 ， 若 B 不是可行基，则有某个基变量

(4) 互补松弛定理：若 x 和 y 分别是原问题和对偶问 题的可行解，则 x 和 y 是最优解当且仅当
n a x b 0 , i 1,, m ui y i j 1 ij j i m a y c 0 , j 1, , n v j x j i 1 ij i j
可选择 xil 为出基变量。通常选择l 使得 xi
( B 1b) l min ( B 1b) i ( B 1b) i 0 } {
基 B 下的单纯形表为
x i1 0 ( B 1 P j )1 ( B 1 Pk )1 ( B 1 b)1 x il 1 ( B 1 P j ) l ( B 1 Pk ) l ( B 1 b) l x im 0 ( B 1 P j ) m ( B 1 Pk ) m ( B 1 b) m 0 x il xj xk
bi , i M 2
s.t . yi 0 ,
i M1
n a x j 1 ij j
yi 0 ,
i M2

n a x j 1 ij j
bi , i M 3
j N1
j N2
yi 无符号限制 i M 3 ,
xj 0,
xj 0 ,
x j 无符号限制 j N 3 ,
u j 无符号限制 j N 3 ,
在 ( D) 的对偶中令 j x j ，即得原问题P ) 。 u (
ˆ ˆ (2) 弱对偶定理：设 x 和 y 分别是原问题（极大化问 题）和对偶问题（极小化问题）的可行解， ˆ ˆ 则 cT x bT y ；且如果 cT x bT y ，则 x 和 y ˆ ˆ ˆ ˆ 分别是原问题和对偶问题的最优解。
z* (c T B 1 ) i ( y*)i , 其中b (b1 ,, bm )T B bi
(y*)i 的经济解释: 在其它条件不变的情况下，第 i 种资源的单位变化引 起的目标函数最优值的变化量，称 (y*)i 为第 i 种资源 的影子价格，当该资源的市场价格低于 (y*)i 时，企 业应增加该资源的利用；当市场价格高于 (y*)i 时， 企业应减少该资源的利用，而直接把部分资源拿到市 场上出售。
9. 对偶问题及性质
( LP) max z c T x s.t . Ax b , x0
的最优性准则要求最优基 B 使得
cT cT B 1 A 0 ， 即 cT B 1 A cT , B B
令y
T
T 1 T c B B ， 则应求 y 使得 A
y c。
引入目标函数，得到另一线性规划
由弱对偶定理，是对偶问题的最优解。 y
(6) 影子价格（对偶解的经济解释）
设 B 是 原 问 题 的 最 优 基 ，最 优 值 则 z* c T B 1b ( y*)T b , B 其 中 y* (c T B 1 )T 是 对 偶 问 题 的 最 优 解 。 B
若 b 变化而 B 仍保持是最优基时，y* 不变，若把 z* 视为 b 的函数，则

m ui i 1

n vj j 1
0
所以， i , v j 全为零。 u
(5) 单纯形表中的对偶信息：原问题单纯形表的检验 数行对应对偶问题的一个基本解，最优单纯形表 的检验数行对应对偶问题的一个最优解。 原问题可写为
max c B x B c N x N
T T
对偶问题
m i n bT y s .t . B T y c B N T y cN Im y 0
( B 1 Pk )l
k
j 1 m in 1 (B Pj )l 0 ( B P j )l
迭代：以 B 1 Pk ) l 为主元对单纯形表做转 ( 轴运算。
例 16. m i n x1 x 2 x 3 s .t . 3 x1 x 2 x 3 1 x1 4 x 2 x 3 2 x1 , x 2 , x 3 0
B
ˆ ˆ 即 y ( c T B 1 ) T 是 对 偶 问 题 的 可 行 解 ， ˆ
B
且
ˆ ˆ ˆ bT y c T B 1 b c T x , ˆ
B
ˆ 由性质(2) , y 是对偶问题的最优解。
对偶问题 有最优解 原问题
有最优解 解无界 不可行
解无界
不可行


标准形：
m ax x1 x 2 x 3 s .t . 3 x1 x 2 x 3 x 4 x1 4 x 2 x 3 1 x5 2
x1 , x 2 , x 3 , x 4 , x 5 0
x1 x4 3 x5 1 1
x2 1 4 1
x3 1 1 1
j

k
c T B 1 b B
结 论 1. 若 x il 对 应 的 行 中 各 元 素B 1 P j ) l 0 , 则 ( 原问题不可行。
因为不可能有 0 使 得 x

n j 1
( B 1 P j ) l x j ( B 1b) l 0 成立。
若 x il 对 应 的 行 中 有 某 些 元 小 于 0， 则 素 选取进基变量 k 使得 x
max cT x s.t . Ax b , x 0 证明：考虑标准形式
min b y s.t . A y c
T T
ˆ A yc ˆ x0
T
ˆ ˆ ˆ x T AT y x T c ˆ ˆ c T x bT y . ˆ b yT Ax yT b ˆ ˆ ˆ Ax
（1）资源向量（约束条件右端向量）变化时
设 br br br ，bi bi ( i r ) 即 b b b，b (0, ,0, br ,0, ,0)T
对应原 问题检 验数的 相反数
当 B 是最优基时，原问题检验数皆小于等于 0，因此
y (c T B 1 )T 0 , y s 2 (c T B 1 N )T c N 0 B B
即 y (cT B 1 )T 是对偶问题的可行解， B
且 bT y cT B 1b，与原问题的最优值相 等， B
另一部分结论显然。
(3) 对偶定理：如果原问题解无界，则对偶问题不可 行；如果原问题有最优解，则对偶问题也有最优 解，且二者目标函数值相等。