0 x6 1 -2 1 -1 -1 0 1 0
0 x7 9 0 3 1 0 0 0 1
j
-3 0 1 0 0 0 0
……
0 x5 0 0 0 0 -1/2 1 1/2 -1/2
0 x2 3 0 1 1/3 0 0 0 1/3
-3 x1 1 1 0 2/3 1/2 0 -1/2 1/6
j
0 0 3 0 0 -3/2 1/2
…………………………
a1n y1 a2n y2 amn ym cn
y1, y2 , , ym 0
3
二、对称形式下对偶问题的一般形式
LP1：s.t.
n
Max Z c j x j
j 1 n
aij x j bi
i 1,2, , m
j 1
xj 0
j 1,2, , n
m
Min W bi yi i 1
j 1,2, , n
yi 0
i 1,2, , m
12
对称形式的线性规划问题：
max z 3x1 x3
x1 x2 x3 4
st.3x22x1
x2 x3
9
x3
x4
1
x1~3 0
13
-3 0 1 0 0 0 0
CB 基 b x1 x2 x3 x4 x5 x6 x7
0 x5 4 1 1 1 0 1 0 0
例：
二、对称形式下对偶问题的一般形式
线性规划问题具有对称形式，若：
➢ 变量非负
➢ 目标函数求极大值时，约束方程均为≤
目标函数求极小值时，约束方程均为≥
2
二、对称形式下对偶问题的一般形式
对称形式的LP问题(LP1)：
Max Z c1x1 c2 x2 cn xn a11x1 a12 x2 a1n xn b1 a21 x1 a22 x2 a2n xn b2
X 0 Xs 0
16
一、单纯形算法的矩阵描述
LP2的初始单纯形表及经过若干步迭代后某一步的
单纯形表如下：
表1
B为某步单 纯形表中基 变量在初始 单纯形中对 应的矩阵
N由A中去 掉B后剩下 的列向量 组成
项目
非基变量
XB
XN
基变量
XS
0 XS b B
N
I
cj-zj
CB
CN
0
表2
项目
基变量
XB
CB XB B-1b
10
2.2 对偶问题的基本性质
本节讨论的问题假定原问题及对偶问题为对称形式
LP1：s.t.
n
Max Z c j x j
j 1 n
aij x j bi
i 1,2, , m
j 1
xj 0
j 1,2, , n
m
Min W bi yi i 1
m
LP2：s.t.
aij yi c j
i 1
n
则两侧同乘以“-1”， aij x j bi j 1
8
三、非对称形式的原--对偶问题的关系
P50 例题 2. 线性规划原问题同对偶问题的对应关系如下：
原问题
对偶问题
目标函数 Max
目标函数 Min
约
m个
m个
决
束
0
策
条
0
变
件
=
无约束
量
决
n个
n个
约
策
0
束
变
0
条
量
无约束
=
件
资源向量 b
价值系数 b‘
14
0 -3 0 1 0 0 0 0
CB 基 b x5 x2 x1 x3 x4 x5 x6 x7
0 x5 4 1 1 1 1 0 1 0 0
B 0 x6 1 0 1 -2 -1 -1 0 1 0
0 x7 9 0 3 0 1 0 0 0 1
j
0 0 -3 1 0 0 0 0
……
0 x5 0 1 0 0 0 -1/2 1 1/2 -1/2
价值系数 C
资源向量 C’
约束条件系数矩阵 A 约束条件系数矩阵 A ‘
9
三、非对称形式的原--对偶问题的关系 练习: 给出下述LP问题的对偶问题:
max z x1 2x2 3x3
x1 x2 x3 4
st.
x1 x1
2x2 2x2
3x3 3x3
5 6
x1 0, x2无约束, x3 0
0 x2 3 0 1 0 1/3 0 0 B0-1 1/3
-3 x1 1 0 0 1 2/3 1/2 0 -1/2 1/6
j
0 0 0 3 0 0 -3/2 1/2
15
一、单纯形算法的矩阵描述
Max Z CX
对称形式的LP： AX b
s.t.
X 0
加上松驰变量Xs后为(LP2)：
Max Z CX 0X s s.t. AX IX s b
s.t. ………………………… am1 x1 am2 x2 amn xn bm x1, x2 , , xn 0
注：对称形式的LP问 题,对b没有非负要求。
其对偶问题为(LP2) ：
s.t.
Min W b1 y1 b2 y2 bm y m a11 y1 a21 y2 am1 ym c1 a12 y1 a22 y2 am2 ym c2
I
cj-zj
0
非基变量
XN
XS
B-1N
B-1
CN-CB B-1N -CB B-1 17
一、单纯形算法的矩阵描述
x1~3 0
6
三、非对称形式的原--对偶问题的关系
1. 非对称转化为对称LP问题的步骤
➢ 目标函数及变量约束的转化同标准形:
n
aij x j bi
j 1
n
aij x j bi
j 1
n
aij x j bi j 1
n
➢ 约束方程若为” ≥”， aij x j bi j 1
资源向量
价格系数
价格系数
资源向量
max z=CX
min w=Y’b
AX≤b
A’Y ≥C’
X≥0
Y≥0
5
二、对称形式下对偶问题的一般形式
练习: 给出下述LP问题的对偶问题:
max z 2x1 4x2 3x3
3x1 4x2 2x3 60
st.2x1x1 3xx22
2 x3 2 x3
40 80
第二章 线性规划的对偶理论 与灵敏度分析
➢ 线性规划的对偶问题 ➢ 对偶问题的基本性质 ➢ 影子价格 ➢ 对偶单纯形法 ➢ 灵敏度分析 ➢ 参数线性规划
1
2.1 线性规划的对偶问题
一、对偶问题的提出
支持对偶理论的基本思想是：每一个线性规划问题都存 在一个与其对偶的问题。在求一个问题的解的同时，也 给出了另一个问题的解。
m
LP2：s.t.
aij yi c j
i 1
j 1,2, , n
yi 0
i 1,2, , m
Max Z CX AX b
s.t.
X 0
Min Y 'b A'Y C'
s.t.
Y 0
4
二、对称形式下对偶问题的一般形式
项目
A b C 目标函数 约束条件 决策变量
原问题
对偶问题
约束系数矩阵 约束系数矩阵的转置