运B_3对偶与灵敏度分析资料

原问题目标函数的系数是其对偶问题约束条件 的右端项。
可用如下表格来表示：
对 b1 y1
偶 问 题
b2 y2 ..
（..
求 ..
极 bm ym 小） 右端项
原问题（求极大）
c1
c2
…
cnΒιβλιοθήκη x1x2…
xn
a11
a12
…
a1n
a21
a22
… a2n
.
.
.
.
.
…
.
.
.
.
am1
am2
…
amn
≥ c1
≥ c2
解：当λ1=λ2=0时，上述LP问题的最终单纯形表如 上表所示。 （i）对基变量x1的目标函数系数进行灵敏度分析： 将λ1的变化反映到最终单纯形表中：
设产品Ⅰ的计划产量为x1，产品Ⅱ的计划产 量为x2， 则有线性规划问题LP1：
目标函数： max
约束条件：
s.t.
z 50x1 100x2
x1 x2 300 2x2x12x520 400 x1, x2 0
现假定有另一八卦机器厂，该厂的规模较小一些， 想租用阴阳厂的设备进行生产。那么阴阳厂的领导应 该给自己的设备制定一个怎样的出租价格呢？
(B, N ) ( X B , X N )T X S b
即： Z CB X B CN X N
(4)
BXB NX N X s b
(5)
式（5）两端左乘B-1得：
X B B1NX N B1X s B1b
由式（6）得：
X B B1b B1NX N B1X s
A (B, N)
(6)
s.t. 3x1 6x2 4x3 15 5x2 3x3 30 x1 0, x2无约束, x3 0

2x1 x2 3x3 2x4 20
x1
4
0
试验证弱对偶性原理。
第25页/共86页
解：
m i nW 20y1 20y2
（D）
y1 2 y2 1
22
y1 y1
y2 3 y2
2 3
3 y1 2 y2 4
y1 0, y2 0
由观察可知：
__
X =（1.1.1.1），
Y__=（1.1），分别是
（1）若原问题是
MaxZ CX
(P)
s.t.
AX b X 0
(2) 其对偶问题为
MinW bY
(D)
YA C
s.t.
Y
0
这两个式子的变换关系称为“对称形式的对偶关系”。
第11页/共86页
怎样写出非对称形式的对偶问题？ 根据对应规律（参见对偶关系表）直接 写出；
第12页/共86页
原问题（或对偶问题） 对偶问题（或原问题）
第7页/共86页
如果模型(2.1)称为原问题（P）， 则模型(2.2)称为对偶问题（D）。 任何线性规划问题都有对偶问题。
原问题与对偶问题之间没有严格的 界限，它们互为对偶。
第8页/共86页
(P) 例1.1
MaxZ 2x1 3x2
x1 2x2 8
s.t.44
x1 x2
16 12
x1, x2 0
第37页/共86页
对偶性质定理总结：
定理2弱对偶定理： 判断原问题（对偶问题）目标函数值的上界 （下界）。
定理3、4、5： 判断原问题（对偶问题）解的两种对应关系。
判断原问题（对偶问题）有无最优解。
定理6互补松弛性定理： 根据原问题（或对偶问题）最优解，直接求出 对偶问题（或原问题）的最优解。

推导:
对 偶 问 题
max z CX
原问题


AX b AX b
X 0
上页
max z CX
下页 返回
XAA0X

b b
对
根据对称形式的对偶模型,可直接
偶 问
写出上述问题的对偶问题:
题

min
w

(Y
1,Y
2
)

b -b
返回
用同等数量的资源
收
自己生产的利润。
购
厂家能接受的条件：
对 偶 问 题
出 用同让等代6 y数价2量应的不y资低3 源于 2 5 y自1己生2产y的2 利润y3。 1
单位产品Ⅰ出租 收入不低于2元
单位产品Ⅱ出租 收入不低于1元
收购方的意愿：
min w 15 y 24 y 5 y
继续
三、原问题与对偶问题的对应关系
返回
一、对偶问题的提出
对
偶 问
实例：某家电厂家利用现有资源生产两种
题
产品， 有关数据如下表：
上页 下页 返回
设备A 设备B 调试工序
产品Ⅰ 产品Ⅱ
0
5
6
2
1
1
利润（元） 2
1
D
15时 24时 5时
对 偶
x 设 Ⅰ产量––––– 1
x Ⅱ产量––––– 2
如何安排生产， 使获利最多？
（4）若对偶问题可行，但其目标函数值无界，
对
则原问题无可行解。
偶 问
（5）若原问题有可行解而其对偶问题无可行
题
解，则原问题目标函数值无界。

⎟ ⎟ ⎟⎟⎠
⎪⎩x1, x2 ,", xn ≥ 0
min z = b1y1 + b2y2 +" + bm ym
（3-5）
⎪⎧⎜⎛ s.t.⎪⎪⎪⎪⎨⎜⎜⎜⎜⎝
a11 a12 #
a1n
a21 a22 #
a2n
" "
"
am1 ⎟⎞⎜⎛ y1 ⎟⎞ ⎜⎛ c1 ⎟⎞
am2 #
amn
⎟⎜ y ⎟⎟⎟⎠⎜⎜⎜⎝#y
+ −
y3* =3 y3* = 4
把 X * 代入原问题 3 个约束中可知原问题式（3）是不等式，故 y 3 * =0，然后解方程组
得到
⎧⎪ ⎨ ⎪⎩
2y1* 3y1*
+ +
3y2* =3 2 y2* = 4
⎧⎪ ⎨ ⎪⎩
y1* =6/5 y2* = 1/ 5
故对偶最优解为 Y * =(6/5,1/5,0), z * =w * =28.
⎪⎪⎪⎨22yy11++3yy22
− +
y3 y3
≥2 ≥3
⎪⎪3y1 + 2 y2 − y3 ≥ 4
⎪⎩y1, y2 , y3 ≥ 0
由于 x 3 * =x 4 * =4>0，故对偶问题约束方程式（3）、（4）是等式约束，即对 Y * 成立等式
⎧⎪ ⎨ ⎪⎩
2y1* 3y1*
+ +
3 y2* 2 y2*
推论 3 若原始问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。
定理 3.2 最优性准则定理
若 X 和 Y 分别为互为对偶问题的线性规划（3-5）与（3-6）的可行解，且使 CX = bT Y T ，