- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
原问题
min z 800y1 650y2 850y3 700y4 2 y1 y2 4 y3 2 y4 4.5 2 y 2 y 2 y 4 y 5 1 2 3 4 4 y1 3 y2 3 y3 2 y4 7 y1 , y2 , y3 , y4 0
26
解： x1* + x2* = 300 y1* 0, 2x1* + x2* < 400 y2* = 0, x2* = 250 y3* 0; x1* > 0 y1* + 2y2* = 50, x2* > 0 y1* + y2* + y3* = 100. 所以， y1* = 50, y2* = 0, y3* = 50.
14
非对称形式的对偶规划
原问题（对偶问题）
max z = cx
对偶问题（原问题）
min w = yb
n 个变量
xj ≥ 0 xj ≤ 0
n 个约束
a1jy1 + a2jy2 + … + a2jym ≥ cj a1jy1 + a2jy2 + … + a2jym ≤ cj
xj 无约束 m 个约束
ai1x1 + ai2x2 + … + ainxn ≤ bi aiainxn ≥ bi ai1x1 + ai2x2 + … + ainxn = bi
对偶问题无可行解
29
课堂练习：
max z =2x1 + 4x2+x3+x4 s.t. x1 + 3x2 + x4 ≤ 8 2x1 + x2 ≤6 x2 + x3 + x4 ≤ 6 x1 + x2 + x3 ≤9 xj ≥ 0 已知原问题最优解为（2,2,4,0），根据对偶 理论，写出对偶问题的最优解
cB cB 0 xB xS b b xB B cB cN xN N cN 0 xS I 0
检验数行
经过若干次迭代
cB cB cB xB xB b B-1b xB I cN xN B-1N 0 xS B-1
检验数行
0
cN -cBB-1N
-cBB-1
33
z z 1 0
z z 1 0 z z XB 1 0 XB -CBT B XB -CBT I
16
课堂练习：
1
min s.t.
z =2x1 + 2x2+4x3 x1 + 3x2 + 4x3 ≤ 2 2x1 + x2 + 3x3 ≤ 3 x1 + 4x2 + 3x3 = 5 x1, x2 ≥ 0 , x3无约束
17
§2. 对偶问题的基本性质
(LP) Max z = j=1,2,…,n cj xj s.t. j=1,2,…,n aij xj bi , i = 1, 2, …, m xj 0, j = 1, 2, …, n Min w = i=1,2,…,m bi yi s.t. i=1,2,…,m aij yi cj , yi 0,
对偶的定义
s.t. -AX≤-b X ≥0
W ≥0
19
定理2.1 (弱对偶定理） 若 x, y 分别为(LP)和(DP)的可行解，则 cx ≤ yb
20
推论(无界性) 若(LP)具有无界解，则(DP)无可行解。
注：反之则不一定成立。 (DP)无可行解，对应(LP)或有无 界解，或无可行解
定理2.2 (最优性定理) 若x*, y*分别(LP)和(DP)的可行解，且 cx* = y*b, 那么x*, y*分别为(LP)和(DP)的最优解。
(DP)
j = 1, 2, …, n i = 1, 2, …, m
18
对偶规划的性质和原理 定理2.0 (对称性） 对偶规划的对偶规划是原规划
min z=CTX s.t. AX≥b X ≥0
对偶的定义
max y=bTW s.t. ATW≤C
W ≥0
max z’=-CTX
min y=-bTW s.t. -ATW≥-C
A 甲 乙 丙 2 1 4 B 2 2 2 C 4 3 3 设备可用 工时 800 650 850
丁
2
4
2
700
3
max z 4.5 x1 5 x2 7 x3 2 x1 2 x2 4 x3 800 x 2 x 3 x 650 2 3 1 4 x1 2 x2 3 x3 850 2 x 4 x 2 x 700 2 3 1 x1 , x2 , x3 0
原始问题的松弛变量
x1
xj
xn
xn+1 xn+i xn+m
w1
wi wm wm+1
wm+j
wn+m
对偶问题的变量
对偶问题的松弛变量
xjwm+j=0 wixn+i=0
(i=1,2,…,m; j=1,2,…,n)
在一对变量中，其中一个大于0，另一个一定等于0
例2.3： 已知线性规划 max z = 50x1 + 100x2 s.t. x1 + x2 300 2x1 + x2 400 x2 250 x1, x2 0 的最优解为 x1* = 50, x2* = 250，求出该 线性规划对偶问题的最优解。
例2.2： max z = 50x1 + 100x2 s.t. x1 + x2 ≤ 300 2x1 + x2 ≤ 400 x2 ≤ 250 x 1, x 2 ≥ 0
10
非对称形式的对偶规划
举列说明：等号形式的约束 设原规划中第一个约束为等式： a11x1 + … + a1nxn = b1 那么，这个等式与下面两个不等式等价 a11x1 + … + a1nxn b1 a11x1 + … + a1nxn b1
4
若这家公司决定不生产这三种产品， 决定将设备进行出租，那么如何对各种资 源的租金进行定价？ 假设y1、y2、y3 、y4为单位时间4种资源 的租赁价格，则新的线性规划数学模型：
max z 4.5 x1 5 x2 7 x3 2 x1 2 x2 4 x3 800 x 2 x 3 x 650 2 3 1 4 x1 2 x2 3 x3 850 2 x 4 x 2 x 700 2 3 1 x1 , x2 , x3 0
(DP) min w =y b s.t. yA ≥ c y≥0
标准化 max z = cx + 0xs s.t. Ax + Ixs = b x, xs ≥ 0
max z = cBxB +cNxN + 0xs BxB +NxN + Ixs = b x, xs ≥ 0
32
（标准化）原问题的初始单纯形表
原始问题和对偶问题最优解之间的互补松弛关系
max y=bTW s.t. ATW≤C W≥0
引进松弛变量
min z=CTX s.t. AX≥b X ≥0 对 引进松弛变量 偶
min z=CTX s.t. AX-XS=b X, XS≥0
W，Ws
max y=bTW s.t. ATW+WS=C W, WS≥0
27
例： 已知线性规划 max z = x1 + x2 s.t. -x1 + x2 + x3 2 -2x1 + x2 - x3 1 x1, x2 x3 0 试用对偶理论证明该线性规划无最优 解。
28
解：
min w = 2y1 + y2 s.t. - y1 - 2y2 2 y1 + y2 1 y1 - y2 0 y1 , y 2 0
8
原规划
cj CB XB 4.5 x1 5 x2 7 x3 0 x4 0 x5 0 x6 0 x7 b
4.5
5 7
x1
x2 x3
1
0 0
0
1 0
0
0 1
-2/7
-1/14 -3/7
0
0 0
3/7
-1/7 -1/7
-1/14
5/14 -1/7
600/7
500/7 850/7
0
j
x5
0
0
0
0
0
0
-6/7
X，Xs
XTWS=0 WTXS=0
互补松弛关系
原始问题和对偶问题变量、松弛变量的维数
min z=CTX s.t. AX-XS=b X, XS ≥0 max y=bTW s.t. ATW+WS=C W, WS ≥0
n n m XS
X
m W
A
WS
-I
= b
AT
I
= C
XTWS=0 WTXS=0
m
n
原始问题的变量
X -CT A
XN -CNT N XN -CNT B-1N
RHS 0 b
RHS 0 b RHS 0 B-1b
z z XB 1 0
XB 0T I
-19/14
1
0
2/7
-3/14
-3/14
400/7
-13/28 -11150/7
对偶规划
-800
CB -800 -850 -700 YB y1 y1 1 0 0
0
-650
y2 6/7 -2/7 3/14
-400/7
-850
y3 0 1 0
