1
线性规划 Linear Programming（ LP）
第二章线性规划的对偶理论与灵敏度分析
2
线性规划 Linear Programming（ LP）
线性规划对偶理论
3
线性规划 Linear Programming（ LP）
线性规划的对偶理论对偶 理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，
对偶问题是怎样提出的，为什么会产生这样一种问题呢？
且看下面详解 ……
4
线性规划 Linear Programming（ LP）
线性规划的对偶理论引例 —— 俩家具制造商间的对话,唉 !我想租您的木工和油漆工一用。咋样？价格嘛 …… 好说，
肯定不会让您兄弟吃亏讪。 王老板做家具赚了大钱，可惜我老李有高科技产品，却苦于没有足够的木工和油漆工咋办？只有租咯。
Hi：王老板，听说近来家具生意好惨了，
也帮帮兄弟我哦 !
家具生意还真赚钱，但是现在的手机生意这么好，
不如干脆把我的木工和油漆工租给他，又能收租金又可做生意。
价格嘛 …… 好商量，
好商量。只是 …...
王 老 板 李 老 板
5
线性规划 Linear Programming（ LP）
线性规划的对偶理论王老板的 家具生产模型,
x1,x2是桌、椅生产量。
Z是家具销售总收入（总利润）。
max Z = 50x1 + 30x2
s.t,4x1+3x2 ≤ 120（ 木工）
2x1+ x2 ≤ 50 （油漆工）
x1,x2 ≥ 0
原始线性规划问题，记为（ P）
王老板的 资源出租模型,
y1,y2单位木、漆工出租价格。
W是资源出租租金总收入。
min W =120y1 + 50y2
s.t,4y1+2y2 ≥ 50
3y1+ y2 ≥ 30
y1,y2 ≥ 0
对偶线性规划问题，记为（ D）
6
线性规划 Linear Programming（ LP）
线性规划的对偶理论王老板按（ D）的解 y1,y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金 W最少）。
按时下最流行的一个词，叫什么来着 ————
7
线性规划 Linear Programming（ LP）
线性规划的对偶理论例 1 第一章例 1中美佳公司利用该公司资源生产两种家电产品时，其线性规划问题为 —— 将其称为原始问题，记为 P
对应第一个约束条件对应第一个约束条件
（ P）
max Z = 2X1 + X2
5X2 ≤ 15 对应第一个对偶变量 y1
6X1 + 2X2 ≤ 24 对应第二个对偶变量 y2
X1 + X2 ≤ 5 对应第三个对偶变量 y3
X1,X2 ≥ 0
8
线性规划 Linear Programming（ LP）
线性规划的对偶理论下面我们从另一角度提出一个新的问题。这个问题我们将其称为原始问题的对偶问题，记为 D
（ D）
min w = 15y1 + 24y2 + 5y3
6y2 + y3 ≥ 2
5y1 + 2y2 + y3 ≥ 1
y1,y2,y3 ≥ 0
9
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对称形式下对偶问题的一般形式项目 原问题 对偶问题
A
b
C
目标函数约束条件决策变量约束系数矩阵约束条件的右端项向量目标函数中的价格系数向量
max Z = CX
AX ≤ b
X ≥ 0
其约束系数矩阵的转置目标函数中的价格系数向量约束条件的右端项向量
min W = Y′b
A′Y ≥ C′
Y ≥ 0
10
线性规划 Linear Programming（ LP）
线性规划的对偶理论
非对称形式下对偶问题的一般形式 — 原始（ 对偶 ）对偶（ 原始 ）关系表项目 原问题 （对偶问题） 对偶问题 （原问题）
目标函数类型 max min
目标函数系数与右边项的对应关系目标函数各变量系数对应约束条件右边项的系数右边项的系数对应目标函数系数变量个数与约束条件个数的对应关系变量个数 n
约束条件个数 m
约束条件个数 n
变量个数 m
原问题变量类型与对偶问题约束条件类型的对应关系
≥0
变量类型 ≤0
自由
≥
约束条件类型 ≤
=
原问题约束条件类型与对偶问题变量类型的对应关系
≥
约束条件类型 ≤
=
≤ 0
变量类型 ≥ 0
自由
11
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶问题的基本性质
1,对称性 —— 原始问题与对偶问题是两个互为对偶的问题。
2,弱对偶性 —— 两个问题的可行解对应的目标函数值互为上下界。
3,最优性 —— 两个问题最优解的目标函数值必相等。
4,强对偶性 —— 两个问题都有可行解时则两个问题必都有最优解。
5,互补松弛性 —— 两个问题最优解中，一个问题中某个变量取值非零，
则该变量在对偶问题中对应的某个约束条件必为紧约束；反之，如果约束条件为松约束，则其对应的对偶变量一定取值为零。因此，
该定理又称为松紧定理。
12
线性规划 Linear Programming（ LP）
线性规划的对偶理论原问题与对偶问题解的对应关系表问题与解的状态 对偶 问题有最优解 无界解 无可行解原问题有最优解 一定 不可能 不可能无界解 不可能 不可能 可能无可行解 不可能 可能 可能
13
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶问题解的经济解释 —— 影子价格我们已经明白原始线性规划与对偶线性规划之间形式上的对偶以及他们的解之间的关系，那么对偶问题的解除了前面引例中提到的租金这种经济含义外其深刻的经济含义是什么呢？
14
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶问题解的经济含义分析：
从单纯形法的矩阵描述中，目标函数取值 Z = CBB-1 b,和检验数
CN -CBB-1N 中都有乘子 Y = CBB-1。
设 B是 { max Z = CX | AX ≤ b,X ≥0 }的最优基矩阵，由 强 对偶 定理知
Z* =CX*= CBB-1b=Y*b=W*
由此
Z*
b
Z*
bi
（ Y*b）
bi= CBB
-1= Y* 或 = = y
i*
15
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶问题解的经济含义：
由上面分析 —— 对偶问题解中变量 yi* 的 经济含义是在其他条件不变的情况下，单位第 i 种“资源”变化所引起的目标函数最优值的变化。所以,yi* 描述了原始线性规划问题达到 最优时 （各种“资源”都处于 最优的配置时），第 i 种“资源”的某种“价值”，故称其为第 i 种“资源”
的 影子价格。
下面图解阐述影子价格的直观含义：
16
线性规划 Linear Programming（ LP）
线性规划的对偶理论
影子价格我们首先采用 单纯形法求解得 王老板的家具生产模型 （ P） 的最优解、
最优基矩阵如下
（ P） 的最优解为 X* =（ 15,20,0,0） T B =（ p2,p1） = 3 41 2
（ D） 的最优解为 Y* = CBB-1 =（ 5,15）
CB =（ C2,C1） =（ 30,50）
B-1=
1 -2
-1/2 3/2
17
线性规划 Linear Programming（ LP）
线性规划的对偶理论
影子价格王老板的家具生产模型的图解：
x1
x2
D可行域 1350=50x1+30x2
（ 15,20）
（ P） max Z = 50x1+30x2
s.t,4x1+ 3x2 ≤ 120
2x1+ x2 ≤ 50
x1,x2 ≥ 0
2x1+ x2 = 50
4x1+3x2 = 120
L0,50x1+30x2
18
线性规划 Linear Programming（ LP）
线性规划的对偶理论
影子价格的直观含义,
x1
x2
4x1+3x2 = 120
2x1+ x2 = 50
L0,50x1+30x2
D可行域
（ P） max Z = 50x1+30x2
s.t,4x1+3x2≤ 120
2x1+ x2 ≤ 50
x1,x2 ≥ 0
2x1+ x2 = 51
4x1+3x2 = 121
1365=50x1+30x2
1355=50x1+30x2
19
线性规划 Linear Programming（ LP）
线性规划的对偶理论
影子价格的特点：
影子价格是对偶解的一个十分形象的名称，它既表明对偶解是对系统内部资源在当前的 最优利用配置下 的一种客观估价，又表明它是一种虚拟的价格（或价值的影象）而不是真实的价格。
特点 1,影子价格是对系统资源的一种 内部最优估价,只有当系统 达到最优状态时才可能赋予资源这种价值。
特点 2,系统资源的一种 动态价格体系,影子价格的大小与系统的价值取向有关，并受系统状态变化的影响。系统环境的任何变化都可能会引起影子价格的变化。
20
线性规划 Linear Programming（ LP）
线性规划的对偶理论
影子价格的特点：
特点 3,影子价格的大小客观地反映 资源在系统内的 稀缺程度 。如果某种资源在系统内供大于求，尽管它有实实在在的市场价格，但它在系统内的 影子价格却为零，而影子价格越高,资源在系统内 越 稀缺。
特点 4,影子价格是一种边际价值，其与经济学中的边际成本的概念相同。因而，在经济管理中十分重要的应用价值。企业管理者可以根据资源在企业内部的影子价格的大小决定企业的经营策略。
特点 5,对偶解准确的经济意义与线性规划模型的构造方法有关，模型构造方法的不同有时会导致对偶解的不同经济解释。
21
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶单纯形法思路
max Z =2x1+x2
s.t,x1+ x2+ x3 = 5
2x2+ x3 ≤5
4x2+6x3 ≥9
x1,x2,x3 ≥0
max Z =2x1+x2
s.t,x1+ x2+ x3 = 5
2x2+ x3+ x4 = 5
4x2+6x3 -x5= 9
x1,x2,x3,x4,x5 ≥0
准典式,max Z = -1x2 -2x3
s.t,x1+ x2+ x3 = 5
2x2+ x3+ x4 = 5
-4x2 -6x3 +x5 = -9
x1,x2,x3,x4,x5 ≥0
标准化化典式
22
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶单纯形法思路对偶单纯形法基本思路：
如果线性规划原问题标准化之后不能简单得出一个初始基可行解（典式），但却能容易得到该问题的对偶问题的一个初始基可行解（准典式），
此时我们就可以通过保持对偶基可行解的可行性的方法进行迭代，逐步消除原问题基本解的不可行性，最终，当对偶基可行解迭代到对偶最优解的同时原问题也得到了最优的基可行解。
23
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶单纯形法的计算方法基 解 X1 X2 X3 X4 X5
X1
X4
X5
5
5
-9
1 1 1 0 0
0 2 1 1 0
0 -4 -6 0 1
检验数 0 -1 -2 0 0
比值? -- 1/4 1/3 -- --
基 解 X1 X2 X3 X4 X5
X1
X4
X2
11/4
1/2
9/4
1 0 -1/2 0 1/4
0 0 -2 1 1/2
0 1 2/3 0 -1/4
检验数 0 0 -1/2 0 -1/4
比值?
迭代准典式,max Z = -1x2 -2x3
s.t,x1+ x2+ x3 = 5
2x2+ x3+ x4 = 5
-4x2 -6x3 +x5 = -9
x1,x2,x3,x4,x5 ≥0
24
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶单纯形法的计算方法
min W =120y1 + 50y2
s.t,4y1+2y2 ≥ 50
3y1+ y2 ≥ 30
y1,y2 ≥ 0
max W’ = –120y1 – 50y2
s.t,4y1 + 2y2 – y3 = 50
3y1 + y2 – y4 = 30
y1,y2,y3,y4 ≥ 0
max W’ = –120y1 – 50y2
s.t,– 4y1 – 2y2 + y3 = – 50
– 3y1 – y2 + y4 = – 30
y1,y2,y3,y4 ≥ 0
25
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶单纯形法的计算方法
max W’ = –120y1 – 50y2
s.t,– 4y1 – 2y2 + y3 = – 50
– 3y1 – y2 + y4 = – 30
y1,y2,y3,y4 ≥ 0
基 解 y1 y2 y3 y4
y3 - 50 - 4 - 2 1 0
y4 - 30 - 3 - 1 0 1
检验数?j - 120 - 50 0 0
- 120/- 4 - 50/- 2 --- ---
26
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶单纯形法的计算方法基 解 y1 y2 y3 y4
y3 - 50 - 4 - 2 1 0
y4 - 30 - 3 - 1 0 1
检验数?j - 120 - 50 0 0
2 25 2 1 -1/2
- 5 1 0 -1/2
- 20 0 - 25
20 --- 50 ---
27
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶单纯形法的计算方法基 解 y1 y2 y3 y4
y2 25 2 1 - 1/2 0
y4 - 5 - 1 0 - 1/2 1
检验数?j - 20 0 - 25 0
1 5 1 1/2 - 1
15 0 3 - 2
0 15 - 20
28
线性规划 Linear Programming（ LP）
灵敏度分析
29
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析敏感性分析的重要性在于向决策者提供线性规划问题的最优解所能适应的环境条件变化的范围，环境条件变化时可能对经营状况带来何种影响，
产生影响后的解决途径。
敏感性分析的类型：
1,模型中各个 参数在什么范围变化时，最优基不发生改变。
2,模型中 参数变化已经超出上述范围时，如何快速确定新的最优 基和最优解 —— 新的最优决策方案。
敏感性分析的方法：
敏感性分析方法的关键是从单纯形法对应的 I 表 中 参数的变化来分析
B 表 中 对应参数的变化情况来回答决策者所关心问题。
30
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析线性规划原问题单纯形法对应的 I 表 中 参数的变化将引起 B 表 中 对应参数的变化情况表：
原问题 对偶问题 结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解问题的最优解或最优基不变可以用单纯形法继续迭代求最优解可以用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算
31
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
线性规划问题 I 表与 B 表的关系给定符合典式的线性规划问题如下：
Max Z = CX + 0XS
AX + IXS = b
X,XS ≥ 0
其中
C = （ c1,c2,…,cn ）
X =
x1
x2.
..
xn
XS =
xS1
xS2.
..
xSm
A =
a11 a12 … a 1n
a21 a22 … a 2n
………………..
am1 am2 … a mn
b =
b1
b2.
..
bm
32
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
线性规划问题 I 表与 B 表的关系对于前面给定符合典式的线性规划问题中，初始基矩阵为 I,
基变量为 XS,即松弛变量。其对应的初始单纯形表如下：
I 表（初始表）
基 解 X XS?
XS b B I
j? C 0
33
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
线性规划问题 I 表与 B 表的关系对初始单纯形表进行迭代之后得到 B 为最优基矩阵，则初始典式和初始单纯形表可以改写为如下：
Max Z = CBXB +CNXN + 0XS
BXB + NXN + IXS = b
XB,XN,XS ≥ 0
基 解 XB XN XS?
XS b B N I
j? CB CN 0
34
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
线性规划问题 I 表与 B 表的关系对初始单纯形表进行迭代之后得到 B 为最优基矩阵，则初始典式可以表示为最终典式如下,Max Z = C
BXB +CNXN + 0XS
BXB + NXN + IXS = b
XB,XN,XS ≥ 0
Max Z = CB B-1 b +（ CN - CB B-1 N ） XN + （ 0 - CB B-1 I ） XS
XB + B-1 N XN + B-1 IXS = B-1 b
XB,XN,XS ≥ 0
35
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
线性规划问题 I 表与 B 表的关系最终典式所对应的单纯形表,B 表（最终表）
Max Z = CB B-1 b +（ CN - CB B-1 N ） XN + （ 0 - CB B-1 I ） XS
XB + B-1 N XN + B-1 IXS = B-1 b
XB,XN,XS ≥ 0
基 解 XB XN XS?
XB B -1b I B -1N B -1
j? 0 CN – CB B -1N - CB B -1
36
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析一、分析 C 的变化当 Ci 是 基变量 Xi 的目标系数时，若要保持 最优解（或基）
不变，则必须满足：
CN – C’B B –1N ≤0
-C’B B -1 ≤0
基 解 XB XN XS?
XS b B N I
j? C’B CN 0
基 解 XB XN XS?
XB B -1b I B -1N B -1
j? 0 CN – C’B B -1N -C’B B -1
对应 I 式 的 单纯形表 —— I 表对应 B式 的 单纯形表 —— B 表
37
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析一、分析 C 的变化当 Cj 是 非基变量 Xj 的目标系数时，若要保持 最优解（或基）
不变，则必须满足：
C’N– CB B -1N ≤0
基 解 XB XN XS?
XS b B N I
j? CB C’N 0
基 解 XB XN XS?
XB B -1b I B -1N B -1
j? 0 C’N – CB B -1N - CB B -1
对应 I 式 的 单纯形表 —— I 表对应 B式 的 单纯形表 —— B 表
38
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析二、分析 b 的变化当 I表 中 b变化为 b’时，在
B 表中将只有解列 B -1b’
发生变化，为保证 最优基不变则 必须满足：
B -1b’≥0
基 解 XB XN XS?
XS b’ B N I
j? CB CN 0
基 解 XB XN XS?
XB B-1b’ I B -1N B -1
j? 0 CN – CB B -1 - CB B -1
对应 I 式 的 单纯形表 —— I 表对应 B式 的 单纯形表 —— B 表
39
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析例
max z = 2x1 + x2
5x2 ≤15
s.t,6x1 + 2x2 ≤ 24
x1 + x2 ≤ 5
x1,x2 ≥ 0
max z = 2x1 + x2
5x2 + x3 ＝ 15
s.t,6x1 + 2x2 + x4 ＝ 24
x1 + x2 + x5 ＝ 5
xj ≥ 0
40
线性规划 Linear Programming（ LP）
例 I 表 Cj 2 1 0 0 0
CB 基 解 X1 X2 X3 X4 X5
C3 X3 15 0 5 1 0 0
C4 X4 24 6 2 0 1 0
C5 X5 5 1 1 0 0 1
检验数?j 2 1 0 0 0
B 表 Cj 2 1 0 0 0
CB 基 解 X1 X2 X3 X4 X5
C3 X3 15/2 0 0 1 5/4 -15/2
C1 X1 7/2 1 0 0 1/4 -1/2
C2 X2 3/2 0 1 0 -1/4 3/2
检验数?j 0 0 0 -1/4 -1/2
41
线性规划 Linear Programming（ LP）
例 图解法进行灵敏度分析 max z = 2x1 + x2
5x2 ≤15
s.t,6x1 + 2x2 ≤ 24
x1 + x2 ≤ 5
x1,x2 ≥ 0
（ 7/2,3/2）
（ 5,0）
（ 2,3）
（ 3,3）
（ 4,0）
42
线性规划 Linear Programming（ LP）
问题 ——某厂生产甲、乙、丙三种产品，都要在 A,B 两种设备上加工，有关数据如下表：
1,如何充分发挥设备的能力，使产品总利润最大？
2,若为了提高产量，以每台时 350 元租用外厂 A 设备，是否合算？
3,分别确定甲产品单位利润,B 设备量各自的影响范围。
4,若能以 39 万元租用外厂 B 设备 300 台时，应否租用？为什么？
产品设备单耗（台时 /件） 设备有效台时
（每月）甲 乙 丙
A 1 2 1 400
B 2 1 2 500
利润（元 /件） 3000 2000 1000
43
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析三、分析增加一个新变量 Xj 的变化
44
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析四、分析参数 aij 的变化
45
.
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析五、分析新增加约束条件的变化线性规划 Linear Programming（ LP）
46
线性规划 Linear Programming（ LP）
第一章结束谢谢！
线性规划 Linear Programming（ LP）
第二章线性规划的对偶理论与灵敏度分析
2
线性规划 Linear Programming（ LP）
线性规划对偶理论
3
线性规划 Linear Programming（ LP）
线性规划的对偶理论对偶 理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，
对偶问题是怎样提出的，为什么会产生这样一种问题呢？
且看下面详解 ……
4
线性规划 Linear Programming（ LP）
线性规划的对偶理论引例 —— 俩家具制造商间的对话,唉 !我想租您的木工和油漆工一用。咋样？价格嘛 …… 好说，
肯定不会让您兄弟吃亏讪。 王老板做家具赚了大钱，可惜我老李有高科技产品，却苦于没有足够的木工和油漆工咋办？只有租咯。
Hi：王老板，听说近来家具生意好惨了，
也帮帮兄弟我哦 !
家具生意还真赚钱，但是现在的手机生意这么好，
不如干脆把我的木工和油漆工租给他，又能收租金又可做生意。
价格嘛 …… 好商量，
好商量。只是 …...
王 老 板 李 老 板
5
线性规划 Linear Programming（ LP）
线性规划的对偶理论王老板的 家具生产模型,
x1,x2是桌、椅生产量。
Z是家具销售总收入（总利润）。
max Z = 50x1 + 30x2
s.t,4x1+3x2 ≤ 120（ 木工）
2x1+ x2 ≤ 50 （油漆工）
x1,x2 ≥ 0
原始线性规划问题，记为（ P）
王老板的 资源出租模型,
y1,y2单位木、漆工出租价格。
W是资源出租租金总收入。
min W =120y1 + 50y2
s.t,4y1+2y2 ≥ 50
3y1+ y2 ≥ 30
y1,y2 ≥ 0
对偶线性规划问题，记为（ D）
6
线性规划 Linear Programming（ LP）
线性规划的对偶理论王老板按（ D）的解 y1,y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金 W最少）。
按时下最流行的一个词，叫什么来着 ————
7
线性规划 Linear Programming（ LP）
线性规划的对偶理论例 1 第一章例 1中美佳公司利用该公司资源生产两种家电产品时，其线性规划问题为 —— 将其称为原始问题，记为 P
对应第一个约束条件对应第一个约束条件
（ P）
max Z = 2X1 + X2
5X2 ≤ 15 对应第一个对偶变量 y1
6X1 + 2X2 ≤ 24 对应第二个对偶变量 y2
X1 + X2 ≤ 5 对应第三个对偶变量 y3
X1,X2 ≥ 0
8
线性规划 Linear Programming（ LP）
线性规划的对偶理论下面我们从另一角度提出一个新的问题。这个问题我们将其称为原始问题的对偶问题，记为 D
（ D）
min w = 15y1 + 24y2 + 5y3
6y2 + y3 ≥ 2
5y1 + 2y2 + y3 ≥ 1
y1,y2,y3 ≥ 0
9
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对称形式下对偶问题的一般形式项目 原问题 对偶问题
A
b
C
目标函数约束条件决策变量约束系数矩阵约束条件的右端项向量目标函数中的价格系数向量
max Z = CX
AX ≤ b
X ≥ 0
其约束系数矩阵的转置目标函数中的价格系数向量约束条件的右端项向量
min W = Y′b
A′Y ≥ C′
Y ≥ 0
10
线性规划 Linear Programming（ LP）
线性规划的对偶理论
非对称形式下对偶问题的一般形式 — 原始（ 对偶 ）对偶（ 原始 ）关系表项目 原问题 （对偶问题） 对偶问题 （原问题）
目标函数类型 max min
目标函数系数与右边项的对应关系目标函数各变量系数对应约束条件右边项的系数右边项的系数对应目标函数系数变量个数与约束条件个数的对应关系变量个数 n
约束条件个数 m
约束条件个数 n
变量个数 m
原问题变量类型与对偶问题约束条件类型的对应关系
≥0
变量类型 ≤0
自由
≥
约束条件类型 ≤
=
原问题约束条件类型与对偶问题变量类型的对应关系
≥
约束条件类型 ≤
=
≤ 0
变量类型 ≥ 0
自由
11
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶问题的基本性质
1,对称性 —— 原始问题与对偶问题是两个互为对偶的问题。
2,弱对偶性 —— 两个问题的可行解对应的目标函数值互为上下界。
3,最优性 —— 两个问题最优解的目标函数值必相等。
4,强对偶性 —— 两个问题都有可行解时则两个问题必都有最优解。
5,互补松弛性 —— 两个问题最优解中，一个问题中某个变量取值非零，
则该变量在对偶问题中对应的某个约束条件必为紧约束；反之，如果约束条件为松约束，则其对应的对偶变量一定取值为零。因此，
该定理又称为松紧定理。
12
线性规划 Linear Programming（ LP）
线性规划的对偶理论原问题与对偶问题解的对应关系表问题与解的状态 对偶 问题有最优解 无界解 无可行解原问题有最优解 一定 不可能 不可能无界解 不可能 不可能 可能无可行解 不可能 可能 可能
13
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶问题解的经济解释 —— 影子价格我们已经明白原始线性规划与对偶线性规划之间形式上的对偶以及他们的解之间的关系，那么对偶问题的解除了前面引例中提到的租金这种经济含义外其深刻的经济含义是什么呢？
14
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶问题解的经济含义分析：
从单纯形法的矩阵描述中，目标函数取值 Z = CBB-1 b,和检验数
CN -CBB-1N 中都有乘子 Y = CBB-1。
设 B是 { max Z = CX | AX ≤ b,X ≥0 }的最优基矩阵，由 强 对偶 定理知
Z* =CX*= CBB-1b=Y*b=W*
由此
Z*
b
Z*
bi
（ Y*b）
bi= CBB
-1= Y* 或 = = y
i*
15
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶问题解的经济含义：
由上面分析 —— 对偶问题解中变量 yi* 的 经济含义是在其他条件不变的情况下，单位第 i 种“资源”变化所引起的目标函数最优值的变化。所以,yi* 描述了原始线性规划问题达到 最优时 （各种“资源”都处于 最优的配置时），第 i 种“资源”的某种“价值”，故称其为第 i 种“资源”
的 影子价格。
下面图解阐述影子价格的直观含义：
16
线性规划 Linear Programming（ LP）
线性规划的对偶理论
影子价格我们首先采用 单纯形法求解得 王老板的家具生产模型 （ P） 的最优解、
最优基矩阵如下
（ P） 的最优解为 X* =（ 15,20,0,0） T B =（ p2,p1） = 3 41 2
（ D） 的最优解为 Y* = CBB-1 =（ 5,15）
CB =（ C2,C1） =（ 30,50）
B-1=
1 -2
-1/2 3/2
17
线性规划 Linear Programming（ LP）
线性规划的对偶理论
影子价格王老板的家具生产模型的图解：
x1
x2
D可行域 1350=50x1+30x2
（ 15,20）
（ P） max Z = 50x1+30x2
s.t,4x1+ 3x2 ≤ 120
2x1+ x2 ≤ 50
x1,x2 ≥ 0
2x1+ x2 = 50
4x1+3x2 = 120
L0,50x1+30x2
18
线性规划 Linear Programming（ LP）
线性规划的对偶理论
影子价格的直观含义,
x1
x2
4x1+3x2 = 120
2x1+ x2 = 50
L0,50x1+30x2
D可行域
（ P） max Z = 50x1+30x2
s.t,4x1+3x2≤ 120
2x1+ x2 ≤ 50
x1,x2 ≥ 0
2x1+ x2 = 51
4x1+3x2 = 121
1365=50x1+30x2
1355=50x1+30x2
19
线性规划 Linear Programming（ LP）
线性规划的对偶理论
影子价格的特点：
影子价格是对偶解的一个十分形象的名称，它既表明对偶解是对系统内部资源在当前的 最优利用配置下 的一种客观估价，又表明它是一种虚拟的价格（或价值的影象）而不是真实的价格。
特点 1,影子价格是对系统资源的一种 内部最优估价,只有当系统 达到最优状态时才可能赋予资源这种价值。
特点 2,系统资源的一种 动态价格体系,影子价格的大小与系统的价值取向有关，并受系统状态变化的影响。系统环境的任何变化都可能会引起影子价格的变化。
20
线性规划 Linear Programming（ LP）
线性规划的对偶理论
影子价格的特点：
特点 3,影子价格的大小客观地反映 资源在系统内的 稀缺程度 。如果某种资源在系统内供大于求，尽管它有实实在在的市场价格，但它在系统内的 影子价格却为零，而影子价格越高,资源在系统内 越 稀缺。
特点 4,影子价格是一种边际价值，其与经济学中的边际成本的概念相同。因而，在经济管理中十分重要的应用价值。企业管理者可以根据资源在企业内部的影子价格的大小决定企业的经营策略。
特点 5,对偶解准确的经济意义与线性规划模型的构造方法有关，模型构造方法的不同有时会导致对偶解的不同经济解释。
21
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶单纯形法思路
max Z =2x1+x2
s.t,x1+ x2+ x3 = 5
2x2+ x3 ≤5
4x2+6x3 ≥9
x1,x2,x3 ≥0
max Z =2x1+x2
s.t,x1+ x2+ x3 = 5
2x2+ x3+ x4 = 5
4x2+6x3 -x5= 9
x1,x2,x3,x4,x5 ≥0
准典式,max Z = -1x2 -2x3
s.t,x1+ x2+ x3 = 5
2x2+ x3+ x4 = 5
-4x2 -6x3 +x5 = -9
x1,x2,x3,x4,x5 ≥0
标准化化典式
22
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶单纯形法思路对偶单纯形法基本思路：
如果线性规划原问题标准化之后不能简单得出一个初始基可行解（典式），但却能容易得到该问题的对偶问题的一个初始基可行解（准典式），
此时我们就可以通过保持对偶基可行解的可行性的方法进行迭代，逐步消除原问题基本解的不可行性，最终，当对偶基可行解迭代到对偶最优解的同时原问题也得到了最优的基可行解。
23
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶单纯形法的计算方法基 解 X1 X2 X3 X4 X5
X1
X4
X5
5
5
-9
1 1 1 0 0
0 2 1 1 0
0 -4 -6 0 1
检验数 0 -1 -2 0 0
比值? -- 1/4 1/3 -- --
基 解 X1 X2 X3 X4 X5
X1
X4
X2
11/4
1/2
9/4
1 0 -1/2 0 1/4
0 0 -2 1 1/2
0 1 2/3 0 -1/4
检验数 0 0 -1/2 0 -1/4
比值?
迭代准典式,max Z = -1x2 -2x3
s.t,x1+ x2+ x3 = 5
2x2+ x3+ x4 = 5
-4x2 -6x3 +x5 = -9
x1,x2,x3,x4,x5 ≥0
24
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶单纯形法的计算方法
min W =120y1 + 50y2
s.t,4y1+2y2 ≥ 50
3y1+ y2 ≥ 30
y1,y2 ≥ 0
max W’ = –120y1 – 50y2
s.t,4y1 + 2y2 – y3 = 50
3y1 + y2 – y4 = 30
y1,y2,y3,y4 ≥ 0
max W’ = –120y1 – 50y2
s.t,– 4y1 – 2y2 + y3 = – 50
– 3y1 – y2 + y4 = – 30
y1,y2,y3,y4 ≥ 0
25
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶单纯形法的计算方法
max W’ = –120y1 – 50y2
s.t,– 4y1 – 2y2 + y3 = – 50
– 3y1 – y2 + y4 = – 30
y1,y2,y3,y4 ≥ 0
基 解 y1 y2 y3 y4
y3 - 50 - 4 - 2 1 0
y4 - 30 - 3 - 1 0 1
检验数?j - 120 - 50 0 0
- 120/- 4 - 50/- 2 --- ---
26
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶单纯形法的计算方法基 解 y1 y2 y3 y4
y3 - 50 - 4 - 2 1 0
y4 - 30 - 3 - 1 0 1
检验数?j - 120 - 50 0 0
2 25 2 1 -1/2
- 5 1 0 -1/2
- 20 0 - 25
20 --- 50 ---
27
线性规划 Linear Programming（ LP）
线性规划的对偶理论
对偶单纯形法的计算方法基 解 y1 y2 y3 y4
y2 25 2 1 - 1/2 0
y4 - 5 - 1 0 - 1/2 1
检验数?j - 20 0 - 25 0
1 5 1 1/2 - 1
15 0 3 - 2
0 15 - 20
28
线性规划 Linear Programming（ LP）
灵敏度分析
29
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析敏感性分析的重要性在于向决策者提供线性规划问题的最优解所能适应的环境条件变化的范围，环境条件变化时可能对经营状况带来何种影响，
产生影响后的解决途径。
敏感性分析的类型：
1,模型中各个 参数在什么范围变化时，最优基不发生改变。
2,模型中 参数变化已经超出上述范围时，如何快速确定新的最优 基和最优解 —— 新的最优决策方案。
敏感性分析的方法：
敏感性分析方法的关键是从单纯形法对应的 I 表 中 参数的变化来分析
B 表 中 对应参数的变化情况来回答决策者所关心问题。
30
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析线性规划原问题单纯形法对应的 I 表 中 参数的变化将引起 B 表 中 对应参数的变化情况表：
原问题 对偶问题 结论或继续计算的步骤可行解可行解非可行解非可行解可行解非可行解可行解非可行解问题的最优解或最优基不变可以用单纯形法继续迭代求最优解可以用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算
31
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
线性规划问题 I 表与 B 表的关系给定符合典式的线性规划问题如下：
Max Z = CX + 0XS
AX + IXS = b
X,XS ≥ 0
其中
C = （ c1,c2,…,cn ）
X =
x1
x2.
..
xn
XS =
xS1
xS2.
..
xSm
A =
a11 a12 … a 1n
a21 a22 … a 2n
………………..
am1 am2 … a mn
b =
b1
b2.
..
bm
32
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
线性规划问题 I 表与 B 表的关系对于前面给定符合典式的线性规划问题中，初始基矩阵为 I,
基变量为 XS,即松弛变量。其对应的初始单纯形表如下：
I 表（初始表）
基 解 X XS?
XS b B I
j? C 0
33
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
线性规划问题 I 表与 B 表的关系对初始单纯形表进行迭代之后得到 B 为最优基矩阵，则初始典式和初始单纯形表可以改写为如下：
Max Z = CBXB +CNXN + 0XS
BXB + NXN + IXS = b
XB,XN,XS ≥ 0
基 解 XB XN XS?
XS b B N I
j? CB CN 0
34
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
线性规划问题 I 表与 B 表的关系对初始单纯形表进行迭代之后得到 B 为最优基矩阵，则初始典式可以表示为最终典式如下,Max Z = C
BXB +CNXN + 0XS
BXB + NXN + IXS = b
XB,XN,XS ≥ 0
Max Z = CB B-1 b +（ CN - CB B-1 N ） XN + （ 0 - CB B-1 I ） XS
XB + B-1 N XN + B-1 IXS = B-1 b
XB,XN,XS ≥ 0
35
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
线性规划问题 I 表与 B 表的关系最终典式所对应的单纯形表,B 表（最终表）
Max Z = CB B-1 b +（ CN - CB B-1 N ） XN + （ 0 - CB B-1 I ） XS
XB + B-1 N XN + B-1 IXS = B-1 b
XB,XN,XS ≥ 0
基 解 XB XN XS?
XB B -1b I B -1N B -1
j? 0 CN – CB B -1N - CB B -1
36
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析一、分析 C 的变化当 Ci 是 基变量 Xi 的目标系数时，若要保持 最优解（或基）
不变，则必须满足：
CN – C’B B –1N ≤0
-C’B B -1 ≤0
基 解 XB XN XS?
XS b B N I
j? C’B CN 0
基 解 XB XN XS?
XB B -1b I B -1N B -1
j? 0 CN – C’B B -1N -C’B B -1
对应 I 式 的 单纯形表 —— I 表对应 B式 的 单纯形表 —— B 表
37
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析一、分析 C 的变化当 Cj 是 非基变量 Xj 的目标系数时，若要保持 最优解（或基）
不变，则必须满足：
C’N– CB B -1N ≤0
基 解 XB XN XS?
XS b B N I
j? CB C’N 0
基 解 XB XN XS?
XB B -1b I B -1N B -1
j? 0 C’N – CB B -1N - CB B -1
对应 I 式 的 单纯形表 —— I 表对应 B式 的 单纯形表 —— B 表
38
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析二、分析 b 的变化当 I表 中 b变化为 b’时，在
B 表中将只有解列 B -1b’
发生变化，为保证 最优基不变则 必须满足：
B -1b’≥0
基 解 XB XN XS?
XS b’ B N I
j? CB CN 0
基 解 XB XN XS?
XB B-1b’ I B -1N B -1
j? 0 CN – CB B -1 - CB B -1
对应 I 式 的 单纯形表 —— I 表对应 B式 的 单纯形表 —— B 表
39
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析例
max z = 2x1 + x2
5x2 ≤15
s.t,6x1 + 2x2 ≤ 24
x1 + x2 ≤ 5
x1,x2 ≥ 0
max z = 2x1 + x2
5x2 + x3 ＝ 15
s.t,6x1 + 2x2 + x4 ＝ 24
x1 + x2 + x5 ＝ 5
xj ≥ 0
40
线性规划 Linear Programming（ LP）
例 I 表 Cj 2 1 0 0 0
CB 基 解 X1 X2 X3 X4 X5
C3 X3 15 0 5 1 0 0
C4 X4 24 6 2 0 1 0
C5 X5 5 1 1 0 0 1
检验数?j 2 1 0 0 0
B 表 Cj 2 1 0 0 0
CB 基 解 X1 X2 X3 X4 X5
C3 X3 15/2 0 0 1 5/4 -15/2
C1 X1 7/2 1 0 0 1/4 -1/2
C2 X2 3/2 0 1 0 -1/4 3/2
检验数?j 0 0 0 -1/4 -1/2
41
线性规划 Linear Programming（ LP）
例 图解法进行灵敏度分析 max z = 2x1 + x2
5x2 ≤15
s.t,6x1 + 2x2 ≤ 24
x1 + x2 ≤ 5
x1,x2 ≥ 0
（ 7/2,3/2）
（ 5,0）
（ 2,3）
（ 3,3）
（ 4,0）
42
线性规划 Linear Programming（ LP）
问题 ——某厂生产甲、乙、丙三种产品，都要在 A,B 两种设备上加工，有关数据如下表：
1,如何充分发挥设备的能力，使产品总利润最大？
2,若为了提高产量，以每台时 350 元租用外厂 A 设备，是否合算？
3,分别确定甲产品单位利润,B 设备量各自的影响范围。
4,若能以 39 万元租用外厂 B 设备 300 台时，应否租用？为什么？
产品设备单耗（台时 /件） 设备有效台时
（每月）甲 乙 丙
A 1 2 1 400
B 2 1 2 500
利润（元 /件） 3000 2000 1000
43
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析三、分析增加一个新变量 Xj 的变化
44
线性规划 Linear Programming（ LP）
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析四、分析参数 aij 的变化
45
.
线性规划问题的参数变化灵敏度分析
灵敏度（敏感性）分析五、分析新增加约束条件的变化线性规划 Linear Programming（ LP）
46
线性规划 Linear Programming（ LP）
第一章结束谢谢！
