运筹学课件第三章线性规划问题的对偶与灵敏度分析制作：北京理工大学 吴祈宗等
2
第三章线性规划问题的对偶与灵敏度分析
线性规划的对偶问题概念、
理论及经济意义
线性规划的对偶单纯形法
线性规划的灵敏度分析本章内容重点
3
1.线性规划对偶问题对偶原理对偶问题定义 —— 线性规划问题写出其对偶问题，要掌握在对称形式和非对称情况下由原问题写出对偶问题的方法。
对偶定理 —— 只需了解原问题与对偶问题解的关系，证明从略。
4
1.对偶问题：
若 第二章例 2.1问题 的设备都用于外协加工，工厂收取加工费。试问：设备 A,B,C 每工时各如何收费才最有竞争力？
设 y1,y2,y3 分别为每工时设备
A,B,C 的收取费用。
1.线性规划对偶问题
5
线性规划原问题例 2.1:某工厂拥有 A,B,C三种类型的设备,生产甲,乙两种产品 。 每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示 。 求获最大利润的方案 。
产品甲 产品乙 设备能力
（ h）
设备 A 3 2 65
设备 B 2 1 40
设备 C 0 3 75
利润 /（元 /件） 1500 2500
6
Max z = 1500x1 + 2500x2
s.t,3x1 + 2x2 ≤ 65
2x1 + x2 ≤ 40 原问题
3x2 ≤ 75
x1,x2 ≥ 0
Min f = 65y1+ 40y2 + 75y3
s.t,3y1+2y2 ≥1500
（不少于甲产品的利润）
2y1+y2+3y3 ≥2500 对偶问题
（不少于乙产品的利润）
y1,y2,y3 ≥ 0
1.线性规划对偶问题
7
2、对偶定义对称形式,互为对偶
(LP) Max z = cT x (DP) Min f = bT y
s.t,Ax ≤ b s.t,AT y ≥ c
x ≥ 0 y ≥ 0
“Max -- ≤,,Min-- ≥”
1.线性规划对偶问题
8
一对 对称形式 的对偶规划之间具有下面的对应关系 。
(1)若一个模型为目标求,极大,,
约束为,小于等于,的不等式,则它的对偶模型为目标求,极小,,约束是
,大于等于,的不等式 。 即,max,≤,
和,min,≥,相对应 。
1.线性规划对偶问题
9
(2)从约束系数矩阵看：一个模型中为 Ａ,则另一个模型中为 AT。 一个模型是 m个约束,n个变量,则它的对偶模型为 n个约束,m个变量 。
(3)从数据 b,C的位置看：在两个规划模型中,b和 C的位置对换 。
(4)两个规划模型中的变量皆非负 。
1.线性规划对偶问题
10
非对称形式 的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划 。
对于非对称形式的规划,可以按照下面的对应关系直接给出其对偶规划 。
（ 1） 将模型统一为,max,≤,或,min，
≥,的形式,对于其中的等式约束按下面
（ 2）,（ 3） 中的方法处理；
（ 2） 若原规划的某个约束条件为等式约束,
则在对偶规划中与此约束对应的那个变量取值没有非负限制；
1.线性规划对偶问题
1x23 0?j
1y11a1213
1b2y21a2223
2b
3y31a3233b
4y41a4243b 0?jy1c231x23 0?j
1y11a1213
1b2y21a2223
2b
3y31a3233b
4y41a4243b 0?jy1c23
11
（ 3） 若原规划的某个变量的值没有非负限制,则在对偶问题中与此变量对应的那个约束为等式 。
下面对关系 （ 2） 作一说明 。 对于关系 （ 3）
可以给出类似的解释 。
设原规划中第一个约束为等式：
a11x1 + … + a1nxn = b1
那么,这个等式与下面两个不等式等价
1.线性规划对偶问题
12
1.线性规划对偶问题这样,原规划模型可以写成
13
1.线性规划对偶问题此时已转化为对称形式,直接写出对偶规划这里,把 y1 看作是 y1 = y1’ - y1’’，
于是 y1 没有非负限制,关系 （ 2） 的说明完毕 。
14
1.线性规划对偶问题例 3.1 写出下面线性规划的对偶规划模型解 先将约束条件变形为,≤,形式
15
1.线性规划对偶问题再根据非对称形式的对应关系,直接写出对偶规划
16
1.线性规划对偶问题
17
作业：
习题 — 1(1)(2)(3)(4)
18
3.对偶定理
(原问题与对偶问题解的关系）
考虑（ LP）和（ DP）
定理 3-1 (弱对偶定理）
若 x,y 分别为（ LP) 和（ DP）
的可行解，那么 cTx ≤ bTy。
推论 若（ LP）可行，那么（ LP）
无有限最优解的充分必要条件是（ LD）
无可行解。
1.线性规划对偶问题
19
定理 3-2 (最优性准则定理 )
若 x,y分别 (LP),(DP)的可行解,且
cTx=bTy,那么 x,y分别为 (LP)和 (DP)
的最优解。
定理 3-3 (主对偶定理 )
若 (LP)和 (DP)均可行 那么 (LP)和
(DP)均有最优解,且最优值相等。
以上定理、推论对任意形式的相应性规划的对偶均有效
1.线性规划对偶问题
20
对偶性质应用例 不计算，判断下列线性规划解的特征：
0
12
2
321
321
321
21
x,x,x
xxx
xxx.t.s
xxzM a x
21
解显然,x = ( 0,0,0 )T是原规划的可行解；
对偶规划为：
显然，第一约束与非负约束矛盾，对偶规划无解。故原规划无有限最优解。
0,
0
1
12.s,t
2M a x
21
21
21
21
21
yy
yy
yy
yy
yyf
22
习题：
习题 --2
23
4.影子价格 —— 是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。
若 x*,y* 分别为（ LP）和（ DP）的最优解，
那么,cT x* = bT y* 。
根据 f = bTy*=b1y1*+b2y2*+? +bmym*
可知?f /?bi = yi*
yi* 表示 bi 变化 1个单位对目标 f 产生的影响，称 yi* 为 bi的影子价格。
注意,若 B 是最优基，
y* = (BT)-1 cB 为影子价格向量。
1.线性规划对偶问题
24
影子价格的经济含义
(1)影子价格是对现有资源实现最大效益时的一种估价企业可以根据现有资源的影子价格,对资源的使用有两种考虑：第一,
是否将设备用于外加工或出租,若租费高于某设备的影子价格,可考虑出租该设备,否则不宜出租 。 第二,是否将投资用于购买设备,以扩大生产能力,若市价低于某设备的影子价格,
可考虑买进该设备,否则不宜买进 。
1.线性规划对偶问题
25
1.线性规划对偶问题
（ 2） 影子价格表明资源增加对总效益产生的影响 。 根据 推论,设 x0和 y0分别为原规划 （ P） 和对偶规划 （ D） 的可行解,当
cx0=bTy0时,x0,y0分别是两个问题的最优解,可知,在最优解的情况下,有关系因此,可以将 z*看作是 bi,i=1,2,…,m的函数,对 bi求偏导数可得到这说明,如果右端常数增加一个单位,则目标函数值的增量将是
26
影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益 。 如果为了扩大生产能力,考虑增加设备,就应该从影子价格高的设备入手 。 这样可以用较少的局部努力,
获得较大的整体效益 。
1.线性规划对偶问题需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，
影子价格的经济含义是指资源在一定范围内增加时的情况,当某种资源的增加超过了这个,一定的范围,时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。
1.线性规划对偶问题
28
5.由最优单纯形表求对偶问题最优解标准形式：
Max z = 50 x1 + 100 x2
s.t,x1 + x2 + x3 = 300
2x1 + x2 + x4 = 400
x2 + x5 = 250
x1,x2,x3,x4,x5 ≥ 0
1.线性规划对偶问题
29
50 100 0 0 0
C
B
X
B
x
1
x
2
x
3
x
4
x
5
θ
i
0 x
3
300 1 1 1 0 0 300
0 x
4
400 2 1 0 1 0 400
0 x
5
250 0 ( 1) 0 0 1 250
-z 0 50 100* 0 0 0
0 x
3
50 ( 1) 0 1 0 -1 50
0 x
4
150 2 0 0 1 -1 75
100 x
2
250 0 1 0 0 1
-z - 25000 50* 0 0 0 - 100
50 x
1
50 1 0 1 0 -1
0 x
4
50 0 0 -2 1 1
100 x
2
250 0 1 0 0 1
-z - 27500 0 0 - 50 0 - 50
-cBTB-1
I
B=(p1,p4,p2 )
oT
B-1
最优解 x1 = 50 x2 = 250 x4 = 50
影子价格 y1 = 50 y2 = 0 y3 = 50,
B-1对应的检验数?T = cBTB-1 。
1.线性规划对偶问题
30
作业：
习题 --3
31
对偶单纯形法的基本思想对偶单纯形法的基本思想是：
从原规划的一个 基本解 出发,此基本解不一定可行,但它对应着一个 对偶可行解 （ 检验数非正 ）,所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行,即是否有负的分量,如果有小于零的分量,
则进行迭代,求另一个基本解,此基本解对应着另一个对偶可行解 （ 检验数非正 ） 。
2.对偶单纯形法
32
如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解 。
2.对偶单纯形法
33
对偶单纯形法在什么情况下使用,
应用前提,有一个基，其对应的基 满足,
① 单纯形表的检验数行全部非正（对偶可行）；
② 变量取值可有负数（非可行解）。
注,通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。
2.对偶单纯形法
34
1.建立初始对偶单纯形表,对应一个基本解,
所有检验数均非正,转 2；
2.若 b’≥0,则得到最优解,停止 ;否则,若有
bk<0则选 k行的基变量为出基变量,转 3
3.若所有 akj’≥0( j = 1,2,…,n )，则原问题无可行解,停止 ;否则,若有 akj’<0 则选
=min{?j’ / akj’┃ akj’<0}=?r’/akr’那么
xr为进基变量,转 4；
4.以 akr’为转轴元,作矩阵行变换使其变为 1,
该列其他元变为 0,转 2。
对偶单纯形法求解线性规划问题过程：
2.对偶单纯形法
35
例 3.2,求解线性规划问题：
标准化：
Max z = - 2x1 - 3x2 - 4x3
s.t,-x1-2x2-x3+x4= -3
-2x1+x2-3x3+x5= -4
x1,x2,x3,x4,x5 ≥ 0
Min f = 2x1 + 3x2 + 4x3
S.t,x1 + 2x2 + x3 ≥ 3
2x1 - x2 + x3 ≥ 4
x1,x2,x3 ≥ 0
2.对偶单纯形法
C
I
- 2 - 3 - 4 0 0
C
B
x
B
b x
1
x
2
x
3
x
4
x
5
0 x
4
- 3 - 1 - 2 - 1 1 0
0 x
5
- 4 [ - 2] 1 - 3 0 1
σ
j
0 - 2 - 3 - 4 0 0
0 x
4
- 1 0 [ - 5/2] 1/2 1 - 1/2
- 2 x
1
2 1 - 1/2 3/2 0 - 1/2
σ
j
4 0 - 4 - 1 0 - 1
- 3 x
2
2/5 0 1 - 1/5 - 2/5 1/5
- 2 x
1
11/5 1 0 7/5 - 1/5 - 2/5
σ
j
5,6 0 0 - 9/5 - 8/5 - 1/5
表格对偶单纯形法最优解为,x = ( 2.2,0.4,0,0,0 )T,z = -5.6
最优值 f = 5.6
无可行解情况线性规划问题可能出现不存在可行解的情况，这时，在对偶单纯形表中显示矛盾方程。
例 Max z = － x1 － 3x2－ 2x3
s.t,x1 + 2x2 + 3x3 + x4 = -10
2x1 + x2 + 5x3 + x5 = 20
3x1 + 2x2 - x3 + x6 = -12
x1,x2,x3,x4,x5,x6 ≥ 0
对偶单纯形表表中第 1行反映了一个矛盾约束：
x1 + 2x2 + 3x3 + x4 = -10
即过程的第 3步,3.若所有 akj’≥0( j =
1,2,…,n )，则原问题无可行解,停止 ;
- 1 - 3 - 2 0 0 0
x B
x 1 x 2 x 3 x 4 x 5 x 6
x 4 - 10 1 2 3 1 0 0
x 5 20 2 1 5 0 1 0
x 6 - 12 3 2 - 1 0 0 1
0 - 1 - 3 - 2 0 0 0
－－－比较－－－
是是是是否否否否所有 所有得到最优解计算 计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有 所有计算计算以为中心元素进行迭代 以为中心元素进行迭代停没有最优解没有最优解单纯形法 对偶单纯形法
<
对偶单纯形法的适用范围适合于解如下形式的线性规划问题
2.对偶单纯形法在引入松弛变量化为标准型之后，约束等式两侧同乘 -1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。
41
对于有些线性规划模型,如果在开始求解时不能很快使所有检验数非正,最好还是采用单纯形法求解 。 因为,这样可以免去为使检验数全部非正而作的许多工作 。 从这个意义上看,
可以说,对偶单纯形法是单纯形法的一个补充 。 除此之外,在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法,可以简化计算 。
2.对偶单纯形法
42
习题：
习题 --7
单纯形表的理解（例题）
上表中 6个常数 a1,a2,a3,b,?1,?2 取值在什么范围可使
1、现可行解最优，且唯一？何时不唯一？
2、现基本解不可行；
3、问题无可行解；
4、无有限最优解；
5、现基本解可行，由 x1取代 x6 目标函数可改善。
C i
C B X B b ' x 1 x 2 x 3 x 4 x 5 x 6
x 3 b 4 a 1 1 0 a 2 0
x 4 2 - 1 - 5 0 1 - 1 0
x 6 3 a 3 - 3 0 0 - 4 1
σ
1 σ 2
0 0 - 3 0
44
进一步理解最优单纯性表中各元素的含义考虑问题
Max z = c1 x1 + c2 x2 + … + cn xn
s.t,a11x1 + a12x2 + … + a1nxn = b1
a21x1 + a22x2 + … + a2nxn = b2.
.,
am1x1 + am2x2 + … + amnxn = bm
x1,x2,…,xn ≥ 0
3.灵敏度分析
45
3、灵敏度分析无防设,xj= 0 j = m+1,…,n ; xi = bi’ i = 1,…,m 是基本可行解,对应的目标函数典式为,z = -f +?m+1xm+1+…+?nxn
以下是初始单纯形表：
m m
其中,f = -∑ ci bi’?j = cj -∑ ci aij’ 为检验数。 向量 b’ = B-1 b
i = 1 i = 1
A= [ p1,p2,…,p n ],pj’ = B-1 pj,
pj’ = ( a1j’,a2j’,…,a mj’ )T,j = m+1,…,n
c
1 …
c
m
c
m + 1 …
c
n
C
B
X
B x
1 …
x
m
x
m + 1 …
x
n
θ
i
c
1
x
1
b
1
'
1 … 0 a'
1 m + 1 …
a'
1n θ 1
c
2
x
2
b
2
'
0 … 0 a'
2 m + 1 …
a'
2n θ 2
┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇
c
m
x
m
b
m
'
0 … 1 a'
m m + 1 …
a'
mn θ m
-z f 0 … 0 σ
m + 1
… σ
n
46
ci,bj发生变化 —— 本段 重点增加一约束或变量及 A中元素发生变化 —通过例题学会处理对于表格单纯形法，通过计算得到最优单纯形表。 应能够找到最优基
B 的逆矩阵 B-1,B-1b 以及 B-1N，
检验数?j 等。
3.灵敏度分析
47
价值系数 c发生变化：
m考虑检验数
j = cj -∑ cri arij
j =1,2,……,n i = 1
1,若 ck是非基变量的系数：
设 ck变化为 ck +?ck
k’ = ck +?ck -∑ cri arik =?k+?ck
只要?k’ ≤ 0,即?ck ≤ -?k,则最优解不变；否则，将最优单纯形表中的检验数?k 用?k’ 取代，继续单纯形法的表格计算 。
3.灵敏度分析
48
例 3.3:
Max z = -2x1 - 3x2 - 4x3
S.t,-x1-2x2-x3+x4 = - 3
-2x1+x2-3x3+x5 = - 4
x1,x2,x3,x4,x5 ≥0
3.灵敏度分析
49
例：最优单纯形表
C I -2 -3 -4 0 0
C B X B b X 1 X 2 X 3 X 4 X 5
-3 X 2 2/5 0 1 - 1/5 - 2/5 1/5
-2 X 1 11/5 1 0 7/5 - 1/5 - 2/5
σ j 0 0 - 9/5 - 8/5 - 1/5
C I -2 -3 -4 + Δ c
3
0 0
C B X B b X 1 X 2 X 3 X 4 X 5
-3 X 2 2/5 0 1 -1/5 -2/5 1/5
-2 X 1 11 /5 1 0 7/5 -1/5 -2/5
σ j 0 0 -9/5 + Δ c 3 -8/5 -1/5
从表中看到 σ 3= c3+Δ c3-(c2× a13+c1× a23 )
可得到 Δ c3 ≤ 9/5 时，原最优解不变。
3.灵敏度分析
50
2、若 cs 是基变量的系数：
设 cs 变化为 cs +?cs,那么
j’= cj -∑cri arij - ( cs +?cs ) asj =?j -?cs asj,
i ≠ s
对所有非基变量,只要对所有非基变量
j’ ≤ 0,即?j ≤?cs asj,则最优解不变；否则，将最优单纯形表中的检验数
j 用?j’ 取代，继续单纯形法的表格计算 。
Max{?j/asj?asj>0}≤?cs≤Min{?j/asj?asj<0}
3.灵敏度分析
51
例 3.4:
Max z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5
s.t,x1 + 2x2 + x3 = 8
4x1 + x4 = 16
4x2 + x5 = 12
x1,x2,x3,x4,x5 ≥ 0
3.灵敏度分析
52
例,下表为最优单纯形表,考虑基变量系数 c2发生变化
C
i
2 3 0 0 0
C
B
X
B
B X
1
X
2
X
3
X
4
X
5
2 X
1
4 1 0 0 1/ 4 0
0 X
5
4 0 0 -2 1/ 2 1
3 X
2
2 0 1 1/ 2 - 1 / 8 0
σ
j 0 0 - 1.5 - 1 / 8 0
C
i
2 3+ Δ C 2 0 0 0
C
B
X
B
B X
1
X
2
X
3
X
4
X
5
2 X
1
4 1 0 0 1/ 4 0
0 X
5
4 0 0 -2 1/ 2 1
3+ Δ C
2 X 2 2 0 1 1/ 2 - 1 / 8 0
σ
j 0 0 - 1,5 - Δ C 2 /2 - 1 / 8 + Δ C 2 /8 0
从表中看到
σ j=cj-(c1× a1j+c5 × a5j+(c2+Δ c2) × a2j)j=3,4
可得到 -3≤Δ c2≤1 时，原最优解不变。
3.灵敏度分析
53
右端项 b 发生变化设分量 br 变化为 br +?br,根据第 1章的讨论，最优解的基变量 xB =
B-1b，那么只要保持 B-1(b +?b) ≥ 0,
则最优基不变，即基变量保持，只有值的变化；否则，需要利用对偶单纯形法继续计算。
对于问题 (LP) Max z = cT x
s.t,Ax ≤ b
x ≥ 0
3.灵敏度分析
54
最优单纯形表中含有
B-1=( aij ） i=1,…,m; j=n+1,…,n+m
那么新的 xi=(B-1b)i+?brair i=1,…,m 。
由此可得，最优基不变的条件是
Max {-bi/air?air>0}≤?br≤
Min{-bi/air?air<0}
3.灵敏度分析
55
例 3.5:
上例最优单纯形表如下
C
i
2 3 0 0 0
C
B
X
B
B X
1
X
2
X
3
X
4
X
5
2
X
1
4 1 0 0 1/4 0
0
X
5
4 0 0 -2 1/2 1
3
X
2
2 0 1 1/2 - 1/8 0
σ
j
0 0 - 1,5 - 1/8 0
3.灵敏度分析
56
0 0.25 0
这里 B-1 = -2 0.5 1
0.5 -0.125 0
各列分别对应 b1,b2,b3 的单一变化因此,设 b1 增加 4，则 x1,x5,x2
分别变为：
4+0× 4=4,4+(-2)× 4=-4<0,
2+0.5× 4=4
用 对偶单纯形法 进一步求解，可得：
x* = ( 4,3,2,0,0 )T f* = 17
3.灵敏度分析
57
增加一个变量增加变量 xn+1 则有相应的
pn+1,cn+1 。
那么计算出 B-1pn+1,?n+1=cn+1-∑ cri ari n+1
填入最优单纯形表,
若?n+1 ≤ 0 则 最优解不变；
否则,进一步用单纯形法求解。
3.灵敏度分析
58
例 3.6:
例 3.4增加 x6,p6=( 2,6,3 )T,
c6=5 计算得到
C
i
2 3 0 0 0 5
C
B
X
B
b X
1
X
2
X
3
X
4
X
5
X
6
2 X
1
4 1 0 0 1/4 0 1.5
0 X
5
4 0 0 -2 1/2 1 [ 2]
3 X
2
2 0 1 1/2 - 1/8 0 0.2 5
σ
j
0 0 - 1.5 - 1/8 0 1.2 5
用单纯形法进一步求解，可得：
x* = ( 1,1.5,0,0,0,2 )T f* = 16.5
3.灵敏度分析
59
增加一个约束增加约束一个之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为 0，进一步用单纯形法或对偶单纯形法求解。
3.灵敏度分析
60
例 3.7:
例 3.4增加 3x1+ 2x2≤15,原最优解不满足这个约束。 于是
C i 2 3 0 0 0 0
C B X B b X 1 X 2 X 3 X 4 X 5 X 6
2 X 1 4 1 0 0 1 / 4 0 0
0 X 5 4 0 0 - 2 1 / 2 1 0
3 X 2 2 0 1 1 / 2 - 1 / 8 0 0
0 X 6 - 1 0 0 - 1 - 1/ 2 0 1
σ
j
0 0 - 1,5 - 1 / 8 0 0
3.灵敏度分析经对偶单纯形法一步，可得最优解为（ 3.5,2.25,0,0,
3,2 )T，最优值为 13,75
61
A中元素发生变化 (只讨论 N 中某一列变化情况）
与增加变量 xn+1 的情况类似，假设 pj
变化 。 那么，重新计算出
B-1pj?j = cj -∑ cri ari j
填入最优单纯形表，若?j ≤ 0 则最优解不变；否则，进一步用单纯形法求解。
（例子从略）
3.灵敏度分析
62
习题：
习题 — 8,10
2
第三章线性规划问题的对偶与灵敏度分析
线性规划的对偶问题概念、
理论及经济意义
线性规划的对偶单纯形法
线性规划的灵敏度分析本章内容重点
3
1.线性规划对偶问题对偶原理对偶问题定义 —— 线性规划问题写出其对偶问题，要掌握在对称形式和非对称情况下由原问题写出对偶问题的方法。
对偶定理 —— 只需了解原问题与对偶问题解的关系，证明从略。
4
1.对偶问题：
若 第二章例 2.1问题 的设备都用于外协加工，工厂收取加工费。试问：设备 A,B,C 每工时各如何收费才最有竞争力？
设 y1,y2,y3 分别为每工时设备
A,B,C 的收取费用。
1.线性规划对偶问题
5
线性规划原问题例 2.1:某工厂拥有 A,B,C三种类型的设备,生产甲,乙两种产品 。 每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示 。 求获最大利润的方案 。
产品甲 产品乙 设备能力
（ h）
设备 A 3 2 65
设备 B 2 1 40
设备 C 0 3 75
利润 /（元 /件） 1500 2500
6
Max z = 1500x1 + 2500x2
s.t,3x1 + 2x2 ≤ 65
2x1 + x2 ≤ 40 原问题
3x2 ≤ 75
x1,x2 ≥ 0
Min f = 65y1+ 40y2 + 75y3
s.t,3y1+2y2 ≥1500
（不少于甲产品的利润）
2y1+y2+3y3 ≥2500 对偶问题
（不少于乙产品的利润）
y1,y2,y3 ≥ 0
1.线性规划对偶问题
7
2、对偶定义对称形式,互为对偶
(LP) Max z = cT x (DP) Min f = bT y
s.t,Ax ≤ b s.t,AT y ≥ c
x ≥ 0 y ≥ 0
“Max -- ≤,,Min-- ≥”
1.线性规划对偶问题
8
一对 对称形式 的对偶规划之间具有下面的对应关系 。
(1)若一个模型为目标求,极大,,
约束为,小于等于,的不等式,则它的对偶模型为目标求,极小,,约束是
,大于等于,的不等式 。 即,max,≤,
和,min,≥,相对应 。
1.线性规划对偶问题
9
(2)从约束系数矩阵看：一个模型中为 Ａ,则另一个模型中为 AT。 一个模型是 m个约束,n个变量,则它的对偶模型为 n个约束,m个变量 。
(3)从数据 b,C的位置看：在两个规划模型中,b和 C的位置对换 。
(4)两个规划模型中的变量皆非负 。
1.线性规划对偶问题
10
非对称形式 的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划 。
对于非对称形式的规划,可以按照下面的对应关系直接给出其对偶规划 。
（ 1） 将模型统一为,max,≤,或,min，
≥,的形式,对于其中的等式约束按下面
（ 2）,（ 3） 中的方法处理；
（ 2） 若原规划的某个约束条件为等式约束,
则在对偶规划中与此约束对应的那个变量取值没有非负限制；
1.线性规划对偶问题
1x23 0?j
1y11a1213
1b2y21a2223
2b
3y31a3233b
4y41a4243b 0?jy1c231x23 0?j
1y11a1213
1b2y21a2223
2b
3y31a3233b
4y41a4243b 0?jy1c23
11
（ 3） 若原规划的某个变量的值没有非负限制,则在对偶问题中与此变量对应的那个约束为等式 。
下面对关系 （ 2） 作一说明 。 对于关系 （ 3）
可以给出类似的解释 。
设原规划中第一个约束为等式：
a11x1 + … + a1nxn = b1
那么,这个等式与下面两个不等式等价
1.线性规划对偶问题
12
1.线性规划对偶问题这样,原规划模型可以写成
13
1.线性规划对偶问题此时已转化为对称形式,直接写出对偶规划这里,把 y1 看作是 y1 = y1’ - y1’’，
于是 y1 没有非负限制,关系 （ 2） 的说明完毕 。
14
1.线性规划对偶问题例 3.1 写出下面线性规划的对偶规划模型解 先将约束条件变形为,≤,形式
15
1.线性规划对偶问题再根据非对称形式的对应关系,直接写出对偶规划
16
1.线性规划对偶问题
17
作业：
习题 — 1(1)(2)(3)(4)
18
3.对偶定理
(原问题与对偶问题解的关系）
考虑（ LP）和（ DP）
定理 3-1 (弱对偶定理）
若 x,y 分别为（ LP) 和（ DP）
的可行解，那么 cTx ≤ bTy。
推论 若（ LP）可行，那么（ LP）
无有限最优解的充分必要条件是（ LD）
无可行解。
1.线性规划对偶问题
19
定理 3-2 (最优性准则定理 )
若 x,y分别 (LP),(DP)的可行解,且
cTx=bTy,那么 x,y分别为 (LP)和 (DP)
的最优解。
定理 3-3 (主对偶定理 )
若 (LP)和 (DP)均可行 那么 (LP)和
(DP)均有最优解,且最优值相等。
以上定理、推论对任意形式的相应性规划的对偶均有效
1.线性规划对偶问题
20
对偶性质应用例 不计算，判断下列线性规划解的特征：
0
12
2
321
321
321
21
x,x,x
xxx
xxx.t.s
xxzM a x
21
解显然,x = ( 0,0,0 )T是原规划的可行解；
对偶规划为：
显然，第一约束与非负约束矛盾，对偶规划无解。故原规划无有限最优解。
0,
0
1
12.s,t
2M a x
21
21
21
21
21
yy
yy
yy
yy
yyf
22
习题：
习题 --2
23
4.影子价格 —— 是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。
若 x*,y* 分别为（ LP）和（ DP）的最优解，
那么,cT x* = bT y* 。
根据 f = bTy*=b1y1*+b2y2*+? +bmym*
可知?f /?bi = yi*
yi* 表示 bi 变化 1个单位对目标 f 产生的影响，称 yi* 为 bi的影子价格。
注意,若 B 是最优基，
y* = (BT)-1 cB 为影子价格向量。
1.线性规划对偶问题
24
影子价格的经济含义
(1)影子价格是对现有资源实现最大效益时的一种估价企业可以根据现有资源的影子价格,对资源的使用有两种考虑：第一,
是否将设备用于外加工或出租,若租费高于某设备的影子价格,可考虑出租该设备,否则不宜出租 。 第二,是否将投资用于购买设备,以扩大生产能力,若市价低于某设备的影子价格,
可考虑买进该设备,否则不宜买进 。
1.线性规划对偶问题
25
1.线性规划对偶问题
（ 2） 影子价格表明资源增加对总效益产生的影响 。 根据 推论,设 x0和 y0分别为原规划 （ P） 和对偶规划 （ D） 的可行解,当
cx0=bTy0时,x0,y0分别是两个问题的最优解,可知,在最优解的情况下,有关系因此,可以将 z*看作是 bi,i=1,2,…,m的函数,对 bi求偏导数可得到这说明,如果右端常数增加一个单位,则目标函数值的增量将是
26
影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益 。 如果为了扩大生产能力,考虑增加设备,就应该从影子价格高的设备入手 。 这样可以用较少的局部努力,
获得较大的整体效益 。
1.线性规划对偶问题需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，
影子价格的经济含义是指资源在一定范围内增加时的情况,当某种资源的增加超过了这个,一定的范围,时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。
1.线性规划对偶问题
28
5.由最优单纯形表求对偶问题最优解标准形式：
Max z = 50 x1 + 100 x2
s.t,x1 + x2 + x3 = 300
2x1 + x2 + x4 = 400
x2 + x5 = 250
x1,x2,x3,x4,x5 ≥ 0
1.线性规划对偶问题
29
50 100 0 0 0
C
B
X
B
x
1
x
2
x
3
x
4
x
5
θ
i
0 x
3
300 1 1 1 0 0 300
0 x
4
400 2 1 0 1 0 400
0 x
5
250 0 ( 1) 0 0 1 250
-z 0 50 100* 0 0 0
0 x
3
50 ( 1) 0 1 0 -1 50
0 x
4
150 2 0 0 1 -1 75
100 x
2
250 0 1 0 0 1
-z - 25000 50* 0 0 0 - 100
50 x
1
50 1 0 1 0 -1
0 x
4
50 0 0 -2 1 1
100 x
2
250 0 1 0 0 1
-z - 27500 0 0 - 50 0 - 50
-cBTB-1
I
B=(p1,p4,p2 )
oT
B-1
最优解 x1 = 50 x2 = 250 x4 = 50
影子价格 y1 = 50 y2 = 0 y3 = 50,
B-1对应的检验数?T = cBTB-1 。
1.线性规划对偶问题
30
作业：
习题 --3
31
对偶单纯形法的基本思想对偶单纯形法的基本思想是：
从原规划的一个 基本解 出发,此基本解不一定可行,但它对应着一个 对偶可行解 （ 检验数非正 ）,所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行,即是否有负的分量,如果有小于零的分量,
则进行迭代,求另一个基本解,此基本解对应着另一个对偶可行解 （ 检验数非正 ） 。
2.对偶单纯形法
32
如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解 。
2.对偶单纯形法
33
对偶单纯形法在什么情况下使用,
应用前提,有一个基，其对应的基 满足,
① 单纯形表的检验数行全部非正（对偶可行）；
② 变量取值可有负数（非可行解）。
注,通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。
2.对偶单纯形法
34
1.建立初始对偶单纯形表,对应一个基本解,
所有检验数均非正,转 2；
2.若 b’≥0,则得到最优解,停止 ;否则,若有
bk<0则选 k行的基变量为出基变量,转 3
3.若所有 akj’≥0( j = 1,2,…,n )，则原问题无可行解,停止 ;否则,若有 akj’<0 则选
=min{?j’ / akj’┃ akj’<0}=?r’/akr’那么
xr为进基变量,转 4；
4.以 akr’为转轴元,作矩阵行变换使其变为 1,
该列其他元变为 0,转 2。
对偶单纯形法求解线性规划问题过程：
2.对偶单纯形法
35
例 3.2,求解线性规划问题：
标准化：
Max z = - 2x1 - 3x2 - 4x3
s.t,-x1-2x2-x3+x4= -3
-2x1+x2-3x3+x5= -4
x1,x2,x3,x4,x5 ≥ 0
Min f = 2x1 + 3x2 + 4x3
S.t,x1 + 2x2 + x3 ≥ 3
2x1 - x2 + x3 ≥ 4
x1,x2,x3 ≥ 0
2.对偶单纯形法
C
I
- 2 - 3 - 4 0 0
C
B
x
B
b x
1
x
2
x
3
x
4
x
5
0 x
4
- 3 - 1 - 2 - 1 1 0
0 x
5
- 4 [ - 2] 1 - 3 0 1
σ
j
0 - 2 - 3 - 4 0 0
0 x
4
- 1 0 [ - 5/2] 1/2 1 - 1/2
- 2 x
1
2 1 - 1/2 3/2 0 - 1/2
σ
j
4 0 - 4 - 1 0 - 1
- 3 x
2
2/5 0 1 - 1/5 - 2/5 1/5
- 2 x
1
11/5 1 0 7/5 - 1/5 - 2/5
σ
j
5,6 0 0 - 9/5 - 8/5 - 1/5
表格对偶单纯形法最优解为,x = ( 2.2,0.4,0,0,0 )T,z = -5.6
最优值 f = 5.6
无可行解情况线性规划问题可能出现不存在可行解的情况，这时，在对偶单纯形表中显示矛盾方程。
例 Max z = － x1 － 3x2－ 2x3
s.t,x1 + 2x2 + 3x3 + x4 = -10
2x1 + x2 + 5x3 + x5 = 20
3x1 + 2x2 - x3 + x6 = -12
x1,x2,x3,x4,x5,x6 ≥ 0
对偶单纯形表表中第 1行反映了一个矛盾约束：
x1 + 2x2 + 3x3 + x4 = -10
即过程的第 3步,3.若所有 akj’≥0( j =
1,2,…,n )，则原问题无可行解,停止 ;
- 1 - 3 - 2 0 0 0
x B
x 1 x 2 x 3 x 4 x 5 x 6
x 4 - 10 1 2 3 1 0 0
x 5 20 2 1 5 0 1 0
x 6 - 12 3 2 - 1 0 0 1
0 - 1 - 3 - 2 0 0 0
－－－比较－－－
是是是是否否否否所有 所有得到最优解计算 计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有 所有计算计算以为中心元素进行迭代 以为中心元素进行迭代停没有最优解没有最优解单纯形法 对偶单纯形法
<
对偶单纯形法的适用范围适合于解如下形式的线性规划问题
2.对偶单纯形法在引入松弛变量化为标准型之后，约束等式两侧同乘 -1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。
41
对于有些线性规划模型,如果在开始求解时不能很快使所有检验数非正,最好还是采用单纯形法求解 。 因为,这样可以免去为使检验数全部非正而作的许多工作 。 从这个意义上看,
可以说,对偶单纯形法是单纯形法的一个补充 。 除此之外,在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法,可以简化计算 。
2.对偶单纯形法
42
习题：
习题 --7
单纯形表的理解（例题）
上表中 6个常数 a1,a2,a3,b,?1,?2 取值在什么范围可使
1、现可行解最优，且唯一？何时不唯一？
2、现基本解不可行；
3、问题无可行解；
4、无有限最优解；
5、现基本解可行，由 x1取代 x6 目标函数可改善。
C i
C B X B b ' x 1 x 2 x 3 x 4 x 5 x 6
x 3 b 4 a 1 1 0 a 2 0
x 4 2 - 1 - 5 0 1 - 1 0
x 6 3 a 3 - 3 0 0 - 4 1
σ
1 σ 2
0 0 - 3 0
44
进一步理解最优单纯性表中各元素的含义考虑问题
Max z = c1 x1 + c2 x2 + … + cn xn
s.t,a11x1 + a12x2 + … + a1nxn = b1
a21x1 + a22x2 + … + a2nxn = b2.
.,
am1x1 + am2x2 + … + amnxn = bm
x1,x2,…,xn ≥ 0
3.灵敏度分析
45
3、灵敏度分析无防设,xj= 0 j = m+1,…,n ; xi = bi’ i = 1,…,m 是基本可行解,对应的目标函数典式为,z = -f +?m+1xm+1+…+?nxn
以下是初始单纯形表：
m m
其中,f = -∑ ci bi’?j = cj -∑ ci aij’ 为检验数。 向量 b’ = B-1 b
i = 1 i = 1
A= [ p1,p2,…,p n ],pj’ = B-1 pj,
pj’ = ( a1j’,a2j’,…,a mj’ )T,j = m+1,…,n
c
1 …
c
m
c
m + 1 …
c
n
C
B
X
B x
1 …
x
m
x
m + 1 …
x
n
θ
i
c
1
x
1
b
1
'
1 … 0 a'
1 m + 1 …
a'
1n θ 1
c
2
x
2
b
2
'
0 … 0 a'
2 m + 1 …
a'
2n θ 2
┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇
c
m
x
m
b
m
'
0 … 1 a'
m m + 1 …
a'
mn θ m
-z f 0 … 0 σ
m + 1
… σ
n
46
ci,bj发生变化 —— 本段 重点增加一约束或变量及 A中元素发生变化 —通过例题学会处理对于表格单纯形法，通过计算得到最优单纯形表。 应能够找到最优基
B 的逆矩阵 B-1,B-1b 以及 B-1N，
检验数?j 等。
3.灵敏度分析
47
价值系数 c发生变化：
m考虑检验数
j = cj -∑ cri arij
j =1,2,……,n i = 1
1,若 ck是非基变量的系数：
设 ck变化为 ck +?ck
k’ = ck +?ck -∑ cri arik =?k+?ck
只要?k’ ≤ 0,即?ck ≤ -?k,则最优解不变；否则，将最优单纯形表中的检验数?k 用?k’ 取代，继续单纯形法的表格计算 。
3.灵敏度分析
48
例 3.3:
Max z = -2x1 - 3x2 - 4x3
S.t,-x1-2x2-x3+x4 = - 3
-2x1+x2-3x3+x5 = - 4
x1,x2,x3,x4,x5 ≥0
3.灵敏度分析
49
例：最优单纯形表
C I -2 -3 -4 0 0
C B X B b X 1 X 2 X 3 X 4 X 5
-3 X 2 2/5 0 1 - 1/5 - 2/5 1/5
-2 X 1 11/5 1 0 7/5 - 1/5 - 2/5
σ j 0 0 - 9/5 - 8/5 - 1/5
C I -2 -3 -4 + Δ c
3
0 0
C B X B b X 1 X 2 X 3 X 4 X 5
-3 X 2 2/5 0 1 -1/5 -2/5 1/5
-2 X 1 11 /5 1 0 7/5 -1/5 -2/5
σ j 0 0 -9/5 + Δ c 3 -8/5 -1/5
从表中看到 σ 3= c3+Δ c3-(c2× a13+c1× a23 )
可得到 Δ c3 ≤ 9/5 时，原最优解不变。
3.灵敏度分析
50
2、若 cs 是基变量的系数：
设 cs 变化为 cs +?cs,那么
j’= cj -∑cri arij - ( cs +?cs ) asj =?j -?cs asj,
i ≠ s
对所有非基变量,只要对所有非基变量
j’ ≤ 0,即?j ≤?cs asj,则最优解不变；否则，将最优单纯形表中的检验数
j 用?j’ 取代，继续单纯形法的表格计算 。
Max{?j/asj?asj>0}≤?cs≤Min{?j/asj?asj<0}
3.灵敏度分析
51
例 3.4:
Max z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5
s.t,x1 + 2x2 + x3 = 8
4x1 + x4 = 16
4x2 + x5 = 12
x1,x2,x3,x4,x5 ≥ 0
3.灵敏度分析
52
例,下表为最优单纯形表,考虑基变量系数 c2发生变化
C
i
2 3 0 0 0
C
B
X
B
B X
1
X
2
X
3
X
4
X
5
2 X
1
4 1 0 0 1/ 4 0
0 X
5
4 0 0 -2 1/ 2 1
3 X
2
2 0 1 1/ 2 - 1 / 8 0
σ
j 0 0 - 1.5 - 1 / 8 0
C
i
2 3+ Δ C 2 0 0 0
C
B
X
B
B X
1
X
2
X
3
X
4
X
5
2 X
1
4 1 0 0 1/ 4 0
0 X
5
4 0 0 -2 1/ 2 1
3+ Δ C
2 X 2 2 0 1 1/ 2 - 1 / 8 0
σ
j 0 0 - 1,5 - Δ C 2 /2 - 1 / 8 + Δ C 2 /8 0
从表中看到
σ j=cj-(c1× a1j+c5 × a5j+(c2+Δ c2) × a2j)j=3,4
可得到 -3≤Δ c2≤1 时，原最优解不变。
3.灵敏度分析
53
右端项 b 发生变化设分量 br 变化为 br +?br,根据第 1章的讨论，最优解的基变量 xB =
B-1b，那么只要保持 B-1(b +?b) ≥ 0,
则最优基不变，即基变量保持，只有值的变化；否则，需要利用对偶单纯形法继续计算。
对于问题 (LP) Max z = cT x
s.t,Ax ≤ b
x ≥ 0
3.灵敏度分析
54
最优单纯形表中含有
B-1=( aij ） i=1,…,m; j=n+1,…,n+m
那么新的 xi=(B-1b)i+?brair i=1,…,m 。
由此可得，最优基不变的条件是
Max {-bi/air?air>0}≤?br≤
Min{-bi/air?air<0}
3.灵敏度分析
55
例 3.5:
上例最优单纯形表如下
C
i
2 3 0 0 0
C
B
X
B
B X
1
X
2
X
3
X
4
X
5
2
X
1
4 1 0 0 1/4 0
0
X
5
4 0 0 -2 1/2 1
3
X
2
2 0 1 1/2 - 1/8 0
σ
j
0 0 - 1,5 - 1/8 0
3.灵敏度分析
56
0 0.25 0
这里 B-1 = -2 0.5 1
0.5 -0.125 0
各列分别对应 b1,b2,b3 的单一变化因此,设 b1 增加 4，则 x1,x5,x2
分别变为：
4+0× 4=4,4+(-2)× 4=-4<0,
2+0.5× 4=4
用 对偶单纯形法 进一步求解，可得：
x* = ( 4,3,2,0,0 )T f* = 17
3.灵敏度分析
57
增加一个变量增加变量 xn+1 则有相应的
pn+1,cn+1 。
那么计算出 B-1pn+1,?n+1=cn+1-∑ cri ari n+1
填入最优单纯形表,
若?n+1 ≤ 0 则 最优解不变；
否则,进一步用单纯形法求解。
3.灵敏度分析
58
例 3.6:
例 3.4增加 x6,p6=( 2,6,3 )T,
c6=5 计算得到
C
i
2 3 0 0 0 5
C
B
X
B
b X
1
X
2
X
3
X
4
X
5
X
6
2 X
1
4 1 0 0 1/4 0 1.5
0 X
5
4 0 0 -2 1/2 1 [ 2]
3 X
2
2 0 1 1/2 - 1/8 0 0.2 5
σ
j
0 0 - 1.5 - 1/8 0 1.2 5
用单纯形法进一步求解，可得：
x* = ( 1,1.5,0,0,0,2 )T f* = 16.5
3.灵敏度分析
59
增加一个约束增加约束一个之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为 0，进一步用单纯形法或对偶单纯形法求解。
3.灵敏度分析
60
例 3.7:
例 3.4增加 3x1+ 2x2≤15,原最优解不满足这个约束。 于是
C i 2 3 0 0 0 0
C B X B b X 1 X 2 X 3 X 4 X 5 X 6
2 X 1 4 1 0 0 1 / 4 0 0
0 X 5 4 0 0 - 2 1 / 2 1 0
3 X 2 2 0 1 1 / 2 - 1 / 8 0 0
0 X 6 - 1 0 0 - 1 - 1/ 2 0 1
σ
j
0 0 - 1,5 - 1 / 8 0 0
3.灵敏度分析经对偶单纯形法一步，可得最优解为（ 3.5,2.25,0,0,
3,2 )T，最优值为 13,75
61
A中元素发生变化 (只讨论 N 中某一列变化情况）
与增加变量 xn+1 的情况类似，假设 pj
变化 。 那么，重新计算出
B-1pj?j = cj -∑ cri ari j
填入最优单纯形表，若?j ≤ 0 则最优解不变；否则，进一步用单纯形法求解。
（例子从略）
3.灵敏度分析
62
习题：
习题 — 8,10
