？
•两个问题的最优解的值一致 •最大值问题可行解的目标值必定不大于最
结 论
小值问题可行解的目标值 •一个问题的剩余变量（松弛变量） 不为0 （即有资源剩余），则对应问题的解为0 •一个决策变量不为0，则对应的问题的约束 条件的剩余变量(松弛变量) 为0(即资源彻 底用完)
5*3/2 = 15/2 ＜ 15 6*7/2+2*3/2 = 24 = 24 7/2+3/2 = 5 = 5
分
总价值
6y2 + y3 ≥
析
2
st .
5y1 + 2y2 + y3 y1 , y 2 , y3
≥ 1 ≥ 0
问题求解
min z= 15 y1 + 24y2 + 5y3 6y2 + y3 ≥ 2 max z'= -15 y1 - 24y2 - 5y3 6y2 + y3 – y4 = 2
st .
5y1 + 2y2 + y3 y1 , y 2 , y3
运筹学基础
教 材
《运筹学教程》（第二版） 胡运权 主编 清华大学出版社
例一
美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设 备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、 各售出一件时的获利情况如下表所示。问该公司应制造Ⅰ、Ⅱ两种家电备多少 件．使获取的利润为最大。
C
CB 0 0 0 2 0 1 XB bb
2
x1 0 0 6 1 1 0 2 0
1
x2 5 0 2 0 1 1 1 0
0
x3 1 1 0 0 0 0 0 0
0
x4 0 5/4 1 1/4 0 -1/4 0 -1/4
0
x5 0 -15/2 0 -1/2 13/2 0 -1/2 θ
15 xx3 15/2 3 24 xx4 7/2 1 5 xx5 3/2 2 σ σ
0 x3 1 0 0
0 x4 5/4 1/4 -1/4
0 x5 -15/2 -1/2 3/2 θ
B=
x1 0 1 0
B =
-1
1 0 0
5/4 1/4 -1/4
-15/2 -1/2 3/2
影子价格
从上节对偶问题的基本性质可以看出 ， 当线性规划原问题求得最优解 xj*(j=1,…n)时，其对偶问题也得到最优解yi*(i=1,….,m)，且代入各自的目标 函数后有： n m
一、线性规划的对偶问题
非对称形式？
max z = c1x1 + c2x2 +c3x3 a11x1+a12x2+a13x3 ≤ b1 st. a21x1+a22x2+a23x3 = b2 a31x1+a32x2+a33x3 ≥ b3 st.
min w = b1y1 +
a11y1 + a12y1 + a13y1 + y1≥0,
CB XB B B
-1 -1
min w = Y b st.
T
AY ≥ C
Y≥ 0
T
T
CN XN B N
-1 -1
0 Xs B I -CBB
-1 -1
原问题为最优解σ≤0，即：
CB-CBB B CN-CBB N -CBB
T
-1 -1 -1 -1
CB-CBB B CN-CBB N
≤0 ≤0 ≤0
C - CBB A≤0 CBB
max z=CX AX (≤ ＝ ≥) b X (≤ ＝ ≥) 0 或无约束 有n个决策变量 xj (j＝0、2……n) xj ≥ 0
对偶问题（原问题）
min w=Yb -T YA (≤ ＝ ≥) C Y (≤ ＝ ≥) 0 或无约束 有n个约束条件 对应的约束为 ≥
变量
xj ≤ 0 xj 无约束
约束
0 Xs B I 0-CBB I
-1 -1
CB
XB
σ
B b
B B
0
-1
B N
CN-CBB N
-1
-1
B I
-CBB
-1
XB B b σ
CB-CBB B CN-CBB N
对偶问题性质证明的几个重要内容
对 称 形 式
C CB CB XB XB σ b B b
-1
max z = CX st. AX ≤ b X≥ 0
0 x4 5/4 1/4 -1/4 -1/4 1/4
0 x5 -15/2 -1/2 3/2 -1/2 1/2
x3 15/2 0 7/2 3/2
-24 y2 1/4
-5
y3 1/2
σ -σ
X =(7/2,3/2,
15/2,0,0)
Y=(0, ¼, ½ , 0, 0 )
一、线性规划的对偶问题
1、对偶问题定义
X =(7/2,3/2,15/2,0,0) Z = 17/2
* *
6y 估价——影子价格 2 + y3 ≥ 2 （即增加单位资源所 + y st . 5y1 + 2y2 ≥ 1 3 得到的贡献） y1 , y 2 , y3 ≥ 0 问题 Y=(0, ¼, ½ , 0, 0 ) 的解
Z = 17/2
*


需要说明的是：这些性质同样适用于非对称形问题
B与B
C CB XB
-1
2 b 15 24 x1 0 6 1 x2 5 2 0 x3 1 0 0 x4 0 1 0 x5 0 0 θ
5
σ C CB XB b 15/2 7/2 3/2 σ 2
1
1
0
0
1
1 0 0 0 6 1 5 2 1
1 x2 0 0 1
C CB -M YB y6 b 2 -15 y1 0
≥ 1 ≥
-24 y2 6
st .
5y1 + 2y2 + y3
– y5 =
1
0
-5 y3 1 0 y4 -1 0 y5 0 -M y6 1
y1, y 2, y3, y 4, y5
≥ 0
-M y7 0 θ
-M
y7
σ
1
5
2
1
0
-M
-1
-M
0
0
1
0
M-15 8M-24 2M-5
三、最优解检验（唯一解、无限多解、无界解和无解）
X =(7/2,3/2,15/2,0,0)
*
Z = 17/2
*
四、分析 把解X=(7/2,3/2)代入原问题(因为x3、 x4、 x5为附加变量) 5×3÷2＝15/2 5x2 6x + 24 2x
1 2
约束 条件
x1 + 5 2 x x1，x2 ≥ 0
-24 y2 1
st .
5y1 + 2y2 + y3
– y5 =
1
0
-5 y3 0 0 y4 -1/4
y1, y 2, y3, y 4, y5
≥ 0
0 y5 1/4 θ
-24 y2
-5
y3
σ
1/2
15/2
-15/2
0
0
1
0
1/2
-7/2
-3/2
-3/2
Y=(0, ¼, ½ , 0, 0)
z'=-17/2
问题求解
min z= 15 y1 + 24y2 + 5y3 6y2 + y3 ≥ 2 max z'= -15 y1 - 24y2 - 5y3 6y2 + y3 – y4 = 2
st .
5y1 + 2y2 + y3 y1 , y 2 , y3
C CB YB b 1/4 -15 y1 -5/4
≥ 1 ≥
max z = CX + 0Xs st.
AX + IXs = b
X, Xs≥ 0
C
CB 0 XB Xs σ b b
C
X I
0
Xs
CB
XB B
CN
XN N
0
Xs I
C CB XB b
-1
CB XB
CN XN
0 Xs CB CB
-1
C XB b
-1
CB XB B B
-1 -1
CN XN B N
-1 -1
对偶规则

——
变量、约束与系数
原问题有m个约束条件，对偶问题有m个变量
原问题有n个变量，对偶问题有n个约束条件 原问题的价值系数对应对偶问题的右端项 原问题的右端项对应对偶问题的价值系数 原问题的技术系数矩阵转置后为对偶问题系数矩阵
对偶规则—— 变量与约束对应关系
原问题（对偶问题）
对 称 形 式
max z = CX
st. AX ≤ b X≥ 0 其中： C=（c1，c2, b=（b1，b2, X=（x1，x2, Y=（y1，y2,
min w = YTb T AY ≥ C st. Y≥ 0
a11 a12 … … … a1n a1n
┇
… … … …
,cn) ,bm)T ,xn)T ,ym)T
min w = b1y1 +
b2y2'- b2y2" - b3y3'
a11y1 + a21y2'– a21y2" - a31y3'≥ c1 -a12y1 - a22y2'+ a22y2" - a32y3'≥-c2 st. a13y1 + a23y2'– a23y2"- a33y3'≥ c3 -a13y1 - a23y2'+ a23y2"+ a33y3'≥-c3 y1 , y2', y2" ，y3'≥0