第二章 运筹学对偶理论

22
3．最优性。 若 X0——原问题可行解，Y0——对偶问题可行解，且 CX0 = Y0 b 则 X0——原问题最优解， Y0——对偶问题最优解 证明：设 X* ——原问题最优解， Y* ——对偶问题最优解
则 CX0 CX* Y* b Y0 b
但 CX0 = Y0 b， ∴ CX0 = CX* = Y* b = Y0 b ∴ X0 = X* ， Y0 = Y* 即 X0——原问题最优解， Y0——对偶问题最优解 证毕。
20
（1）原问题任一可行解的目标函数值是其对偶问题目标函 数值的下界；反之对偶问题任一可行解的目标函数值是其 原问题目标函数值的上界。 （2）如原问题有可行解且目标函数值无界（具有无界解）， 则其对偶问题无可行解，反之对偶问题有可行解且目标函 数值无界，则其原问题无可行解。 证：有性质1，C X0 Y0 b，当 CX0 ∞ 时，则不可能存在 Y0，使得 C X0 Y0 b 。 本性质的逆不成立。当对偶问题无可行解时，其原问题或 具有无界解或无可行解，反之亦然。
min =15y1+24y2+5y3 0y1+ 6y2+ y3≥ 2 S.t. 5y1+ 2y2+ y3≥ 1 y1，y2，y3≥0
• 对偶问题的最优解： y1=0，y2=1/4，y3=1/2，W* =8.5 • 两个问题的目标函数值相等，这不是偶然的，上述两个问题 实际上是一个问题的两个方面，如果把前者称为线性规划原 问题，则后者便是它的对偶问题，反之亦然。 • 对偶问题的最优解对应于原问题最优单纯型法表中，初始基 变量的检验数的负值。
∴ Y*是对偶问题的最优解。
24
• 5.互补松弛性：在线性规划问题的最优解中，如果对应 某一约束条件的对偶变量值为非零，则该约束条件取严 格等式；反之如果约束条件取严格不等式，则其对应的 对偶变量一定为零。即 • 若yi*＞0，则有 n * ai j x j bi ,
j 1
若
a
j 1
29
得到对偶问题各松弛变量的值
y3=0，y4=2，y5=3
即对偶问题的最优解和最优目标函数值为 YT=(y1，y2，y3，y4，y5)T=(6，0，0，2，3)T w=6
根据互补松弛定理，以下的互补松弛关系成立 由 由 y1>0 y4>0 得到 x4=0 得到 x2=0
由
y5>0
得到 x3=0
n
ij
x j bi ,
*
则有yi*=0.
25
证： ∵
n m
n
n
m
m
i =1
j=1
cj x j* = ( a ij y i* ) xj* = bi y i*
j=1 i =1
m
i =1
∴
j=1 i =1
( a ij y i* ) xj* - bi y I* =0
n
m n
21
• • • • •
原问题 Maxz=x1+x2 x1-x2≤-1 -x1+x2 ≤-1 x1, x2≥0
• • • • •
对偶问题 Minw=-y1+-y2 y1-y2≥1 -y1+y2 ≥ 1 y1, y2≥0
• （3）原问题有可行解而其对偶问题无可行解，则原 问题目标函数值无界；反之对偶问题有可行解而原 问题无可行解，则对偶问题的目标函数值无界。
17
例
max z= 8x1 +5x2
s.t.
-x1
3x1 2x1
+2x2
-x2 +4x2
≤4
=7 ≥8
x1≥0,
x2≤0
min w= s.t.
4y1 -y1 2y1
+7y2 +3y2 -y2
+8y3 +2y3 +4y3 ≥8 ≤5
y1≥0,
18
y2:unr
y3≤0
第二节 对偶问题的基本性质
与对偶有关的定理
14
非对称形式对偶规则
原问题（或对偶问题） A 约束系数矩阵 对偶问题（或原问题） 约束系数矩阵的转置
b 约束条件右端项
C 目标函数变量的系数 目标函数max z
目标函数变量的系数
约束条件右端项 目标函数min w
N个
变 量 ≥0 ≤0 无约束
N个
≥ ≤ =
约束 条件
约 束 条 件
m个
≤ ≥ =
15
XB , XN, , XS0
非基对应的矩阵， I—— 单位矩阵
XB ——最终表中基变量
XN——初始表与最终表中均为非基变量 2
CB
初始单纯形表
CN 非基变量
0 基变量 XS I 0
XB B CB
XN N CN
0 XS b σ
当基变量变为XB时，单纯形表中XB对应的系数矩阵变为I，约束方程两 端同乘B-1，则可得如下表达式： B-1 BXB+ B-1 NXN+ B-1 XS= B-1 b
23
4.对偶定理（强对偶性）：若原问题LP有最优解X*，则其 对偶问题DP也一定有最优解Y*，且
z*=CTX * =bTY *=w*.
证： 由 = C- CB B-1 A 0 得 Y* A C -Y * = -CBB-1 0， 令 CBB-1 = Y* ， Y* 0
因此， Y*是对偶问题的可行解， 又 CX* = CB (B-1 b) = CB B-1b = Y* b
7
二、对称形式下对偶问题的一般形式
满足下列条件的线性规划问题称为具有对称形式，其变量均 有非负约束，其约束条件当目标函数求极大时均取“≤”号， 当目标函数求极小时均取“≥”号。 定义 设以下线性规划问题 Max z=CX s.t. X≥0 为原问题。 AX ≤ b (LP)
8
• 则称以下问题 • Min z=bTY • s.t. ATY≥ C Y≥0 • 为原问题的对偶问题。
第二章 线性规划的对偶理论与灵敏度分析
• 第一讲 线性规划的对偶问题
第一节 第二节 第三节 第四节 单纯形法的矩阵描述 线性规划的对偶问题 对偶问题的基本性质 影子价格
• 第二讲 对偶单纯形法
第一节 对偶单纯形法 第二节 灵敏度分析 第三节 参数线性规划
1
第一节 单纯形原理的矩阵描述
19
对偶问题的基本性质
• 1．对称性：对偶问题的对偶问题是原问题 • 2．弱对偶性： 若 X0——原问题可行解，Y0——对偶问题可 行解，则恒有 CX0 Y0 b 证明：
∵ Y0 0， AX0 b， ∴ Y0 AX0 Y0 b， 而 Y0 A C ， ∴ CX0 Y0AX0 ， ∴ CX0 Y0 AX0 Y0 b
16
对偶规则简捷记法
•原问题标准则对偶问题标准 •原问题不标准则对偶问题不标准 •例 max ω=7y1+4y2-2y3 minZ=3x1+2x2-6x3+x5 2y1+ y2- y3 ≤3 2x1+x2-4x3+x4+3x5 ≥7 y1 +3y3 ≤2 x1+ 2x3 -x4 ≤4 -4y1+ 2y2 ≤-6 -x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 ≥ 0 x1，x2，x3 ≥0; 3y1 +y3=1 x4 ≤ 0;x5无限制 y1 ≥ 0,y2 ≤ 0,y3 无约束
对偶问题：
minω=360y1+200y2+300y3 9y1+4y2+3y3 ≥70 4y1+5y2+10y3 ≥120 y1 ≥0, y2 ≥0, y3 ≥0
11
对偶规则
原问题一般模型： maxZ=CX
AX ≤b
X ≥0
对偶问题一般模型： min ω=Yb YA ≥C Y ≥0
12
对称形式对偶规则
( a ij xj* - bi ）y i* =0
i =1 j=1
∴ 当 y i*>0,
n
j=1
a ij xj* - bi =0,
即 a ij xj* = bi
j=1
n
当 a ij xj* - bi <0,
j=1
y i*=0
26
• • • • • •
例题： Minw=2x1+3x2+5x3+2x4+3x5 x1+x2+2x3+x4+3x5 ≥ 4 2x1-x2+3x3+x4+x5 ≥ 3 xj ≥ 0 j=1…5 已知其对偶问题的最优解为y1=4/5,y2=3/5,z=5。试用 对偶理论找出原问题的最优解
Max z=CX st. AX b X0 标准形 Max z=CX+0Xs st.
AX +IXs = b X0
A=[ B N ]
XB X X N
CB=[ CB CN ]
max z=CBXB+ CNXN+0XS 式中， B——最终表中基对应的矩阵， st BXB+ NXN+IXS=b N——初始表与最终表中均为
基变量
最终表
非基变量 XN B-1N XS B-1
CB XB B-1b σ
XB I 0
CN-CBB-1N
1
3
-CBB-1
C CB B A
第二节 线性规划的对偶问题
• 例1. 生产计划问题 • 美佳公司生产Ⅰ、Ⅱ两种产品，相关数据如表所示：
产品 工序 A B C 单位产品获利 工时单耗 Ⅰ Ⅱ 0 6 1 3 5 2 1 5 生产能力 15 24 5