第2章+对偶理论和灵敏度分析-第1节

0.25 04 0 0.5 108
0.5 0.12500
2
cj→
2
CB
XB
b
x1
2 x1 4+0 1
0 x5 4-8 0
3 x2 2+2 0
cj-zj
0
3
0
0
0
x2
x3
x4
x5
0
0
0.25 0
0 [-2] 0.5 1
1 0.5 –0.125 0
0 -1.5 -0.125 0
由于表2-10中b列有负数，故用对偶单纯形法求新 的最优解。计算结果见表2-11。
4 1/ 2b2 0
2
1/ 8
0
由上式，可得 Δb2≥-4/0.25=-16，Δb2≥-4/0.5=-8， b2≤2/0.125=16。 所以Δb2的变化范围是［-8，16］；显然原b2 =16，加 它的变化范围后，b2的变化范围是［8，32］。
例7 从表1-5得知第1章例1中，每设备台时的影子价 格为1.5元，若该厂又从其他处抽调4台时用于生产产 品Ⅰ，Ⅱ。求这时该厂生产产品Ⅰ，Ⅱ的最优方案。
对偶理论和灵敏度分析第节
表 2-9
原问题 可行解 可行解 非可行解 非可行解
对偶问题 可行解 非可行解 可行解 非可行解
结论或继续计算的步骤 表中的解仍为最优解 用单纯形法继续迭代求最优解 对偶单纯形法继续迭代求最优解 引进人工变量，编制新的单纯形表， 求最优解
下面就各种情况分别按节进行讨论。
7.1 资源数量变化的分析
解 这时表1-5最终计算表便成为表2-12所示。
cj→
2 3+Δc2
0
0
0
CB

对偶问题习惯写为: min g (Y ) bTY T ATY T C T s.t. Y 0
2.1.2 标准(max,)型的对偶变换
• • • • • • 目标函数由 max 型变为 min 型 对应原问题每个约束行有一个对偶变量 yi，i=1,2,…,m 对偶问题约束为 型，有 n 行 原问题的价值系数 C 变换为对偶问题的右端项 原问题的右端项 b 变换为对偶问题的价值系数 原问题的技术系数矩阵 A 转置后成为对偶问题的技术 系数矩阵 • 原问题与对偶问题互为对偶
2.2.4 互补松弛定理
v0 x0 0 j j
j 1,2,, n
yi0ui0 0
i 1,2,, m
• • •
Y0 U0 + V0 X0 = 0 有什么应用 若(Y0 )i >0，则 (U0 )i =0，意味着原问题第 i 约束行 必须为 = 约束；对(X0 )i >0 亦如此 可用来简化问题的求解 线性规划的高级算法：利用互补松弛定理，原问题与 对偶问题同时解 –原问题为基础可行解，对偶问题为非可行解，但满足互补
主对偶定理的证明
证：现证明定理的后一句话。 设 X0 为原问题的最优解，它所对应的基矩阵是 B， X0= B1 b，则其检验数满足 C CBB1A 0 令 Y0= CBB1，则有 Y0 A C ；而对原问题松弛变 量的检验数有 0 CBB1I 0，即 Y0 0 。 显然Y0为对偶问题的可行解。因此有对偶问题目标函 数值， g(Y0)=Y0b= CBB1 b 而原问题最优解的目标函数值为 f(X0)=CX0= CBB1 b 故由最优解判别定理可知Y0 为对偶问题的最优解。证毕。
6 x' 3 1 (3) 1 M 6+M 0 1 0 6 0 0 1 0 6 0 1 2 1 7 1 0 0 1 6 0 y 6 =0

2018/8/5 16
当B为最优基时，XB为最优解时，则有： CN-CBB-1N≤0 -CBB-1≤0
∵CB-CBI=0
代入得： CN－CBB-1N+CB-CBI≤0 C－CBB-1(B+N)≤0 整理得： C－CBB-1 A≤0 -CBB-1≤0
令CBB-1为单纯形乘子，Y‘＝CBB-1 则： Y’ A≥C’ C－Y’ A≤0 -Y’≤0 Y’ ≥0 W＝Y’b=CBB-1b=Z 所以当原问题为最优解时，对偶问题为可行解且具有相 2018/8/5 17 同的目标函数值。
maxZ=x1+4x2+2x3 s.t. 5x1-x2+2x3≤8 x1+3x2-3x3≤5 x1,x2,x3≥0
minw=8y1+5y2 s.t. 5y1+y2≥1 -y1+3y2≥4 2y1-3y2 ≥2 y1,y2≥0
2018/8/5 9
三、非对称形式的原—对偶问题
minz=2x1+3x2-5x3+x4 s.t. x1+x2-3x3+x4≥5 2x1 +2x3-x4≤4 x2+x3+x4=6 x1≤0,x2,x3≥0
2018/8/5
第一种产品 第二种产品
x1 x2
6
原始问题为 min z=2x1+3x2-x3
s.t. x1+2x2+x3≥6
原始问题是极小化问题 原始问题的约束全为≥ 原始问题有3个变量，2个约束 原始问题的变量全部为非负
2x1-3x2+2x3≥9
x1, x2, x3≥0 根据定义，对偶问题为 max y=6y1+9y2 s.t. y1+2y2≤2 2y1- 3y2≤3 y1+2y2≤-1 y1, y2≥0

x1, x2 ,, xn 0
对 称 形 式 的
的 定 义
minW b1y1 b2 y2 bm ym
对
s.t.
a11 a12
a1n
a21 a22
a2n
am1 y1 c1
am2
y2
c2
amn ym cn
偶 问 题
y1, y2 ,, ym 0
max Z CX
用5h设备A,2h设备B及1h调试可 生产一件家电Ⅱ，赢利1元
该公司希望用最小代价把美佳公司的全部资源收买过来，即：
min z 15y1 24y2 y3
问 题 的 导 出
例2-1
综上所述，
（LP2） min w 15y1 24y2 y3
6 y2 y3 2
s.t.5 y1 2 y2 y3 1
的
x1, x2,, xn 0
对
minW b1y1 b2 y2 bm ym
a11 y1 a21 y2 am1 ym c1
偶 问 题
a12y1
a22 y2
am2 ym
c2
a1n y1 a2n y2 amn ym cn y1, y2 ,, ym符号不限
对
例2－3
称
minZ 4x1 2x2 3x3
[B-1A,B-1I]=[B-1B,B-1N,B-1I]=[I,B-1N,B-1] •若初始矩阵中变量xj的系数向量为Pj，迭代后为 Pj′，则有Pj′=B-1Pj •当B为最优基时，表中应有
CN-CBB-1N≤0,-CBB-1≤0
例2-5
对
偶
参看例2-1中的原问题和对偶问题，并分别加上松 弛变量和剩余变量，如下：
23 3