答：不能。因为此时右边常数项为负数，解不可 行。为了保证初始解可行
北京联合大学 耿钰
第四节 对偶单纯形法
例 用对偶单纯形法求解
maxZ x1 4x2 3x4
x1 2x2 x3 x4 3
x
2x j
10 jx2
1,24,x33,4 x4

2
能否用对偶单纯形法呢？
原问题表中的检验数满足最优性条件
CN-CB B-1 N≤0
ATY ≥ CT;
min w Y T b bTY
-CB B-1 ≤0;
Y≥0
CB:1×m B-1：m ×m
YT= CB B-1
CB B-1：1 ×m Y： m ×1
ATY CT s.t.
Y 0
从上面可以看出：
1、当原问题达到最优时，松弛变量经过上述转换后构成的检验 数的相反数为其对偶问题的一个可行解，反之亦成立
-1 x1 7 0 x3 4
7
1 7/2 0 5/2 -2 -1/2 0 3/2 1 3/2 -1 -1/2 0 -1/2 0 -1/2 -2 -1/2
最优解 X*=（7，0，4， 0）T
Z*=-7
北京联合大学 耿钰
例6 用对偶单纯形法求解
min w 2x1 3x2 4x3
（P）
x1 2x2 x3 3 2x1 x2 3x3 4
原问题不 可行，应 该换基迭 代。但按 对偶单纯 形法的思 想，每次 均应保证 检验数均 非正
cj
CB XB b -1 x1 3 0 x6 -8
3
-1 -4 0 -3 0 0
x1 x2 x3 x4 x5 x6 1 2 - 1 1 -1 0 0 -3 -2 -3 2 1 0 -2 -1 -2 -1 0
j1

x
j

0
（j 1,
, m） , n）
北京联合大学 耿钰
一、含义和研究对象
2、灵敏度分析的研究对象：
• 目标函数的系数 cj 变化对最优解的影响； • 约束方程右端系数 bi 变化对最优解的影响； • 约束方程组系数矩阵 A 变化对最优解的影响 ；
①这些系数在什么回范答两围个内问题发：生变化时，最优解不变？ ②系数变化超出上述范围，如何用最简便的方法求出 新的最优解？
北京联合大学 耿钰
第五节 灵敏度分析
一、含义和研究对象
1、什么是灵敏度分析？ 灵敏度分析是指系统或事物因为周围条件变化
而显示出来的敏感程度分析。
北京联合大学 耿钰
第五节 灵敏度分析
在生产计划问题的一般形式中，A代表企业的技术状 况，b代表企业的资源状况，而C代表企业产品的市场状 况，在这些因素不变的情况下企业的最优生产计划和最大 利润由线性规划的最优解和最优值决定。
北京联合大学 耿钰
第四节 对偶单纯形法
怎么做呢？
① 先找一个基，建立初始对偶单纯形表，使检 验数全部非正，即C全部为非正； ② 若b列元素非负，则已经是最优基。反之， 则换基迭代，直至原问题可行。
北京联合大学 耿钰
第四节 对偶单纯形法
例 用对偶单纯形法求解
maxZ x1 4x2 3x4
也就是说：对偶单纯形法是在保持原问题所有检验数 都小于等于零的基础上，通过迭代，使原问题的解（即 右边常数项）都大于等于零，从而求得最优解。
北京联合大学 耿钰
第四节 对偶单纯形法
使用对偶单纯形法必须满足两个条件： （1）单纯形表中的所有检验数必须符合对偶可行，即 小于等于0
（2）初始解不可行，即右端常数项有负分量（如果原 问题可行，则直接用单纯形法）
单 系数
行解
纯
形
0
Xs
b
表
cj zj
非基变量 XB XN BN CB CN
பைடு நூலகம்
基变量 Xs I 0
最 优 单 纯 形 表
基变量 基变量 基可
系数
行解
CB
XB
B-1b
cj zj
基变量
非基变量
XB
XN
Xs
CN－CBB-1N ≤0
I
B-1N
B-1
0
CN－CBB-1N －CBB-1
－CBB-1 ≤0
原问题基变量的最优解：X*=B-1b 最优值：Z*=CBB-1b 对偶问题决策变量的最优解<影子价格>： Y*T= CBB-1
0
x1 x2 x3 x4 x5 x6 -1 -2 1 - 1 1 0 2 1 -4 -1 0 1 -1 -4 0 -3 0 0


mi
n

1 1
,

4 2
,

3 1

1
cj
-1 -4 0 -3 0 0
CB XB b -1 x1 3 0 x6 -8
3
x1 x2 x3 x4 x5 x6 1 2 - 1 1 -1 0 0 -3 -2 -3 2 1 0 -2 -1 -2 -1 0
x1 2x2 x3 x4 3
x
2x j
10 jx2
1,24,x33,4 x4

2
将约束方程化为标准型，再用（-1）乘不等式两边
maxZ x1 4x2 3x4
x1 2x2 x3 x4 x5 3
2 x
x
j
10x j2

14,x23, x,64
项目
非基变量
XB XN
0 XS b B N
Cj-Zj
CB CN
基变量 XS I 0
项目
CB
CN
0
基变量
非基变量
XB
XN
XS
CB XB B-1 b
I B-1 N
B-1
Cj-Zj
0 CN -CB B-1 N -CB B-1
单纯形法是在保持所有约束条件常数项总是保持大于等于零的情 况（保证可行），通过迭代，使所有检验数小于等于零（求最大 值），求得最优解。
x1 2x2 x3 x4 3
x
2x j
10 jx2
1,24,x33,4 x4

2
该问题用单纯形法求解时，需要先化标准型，此时约束
方程两边左边需要减去剩余变量，同时为了构造单位阵，
需要添加人工变量，采用大M法求解。
思考：上面约束方程化为标准型后，两边乘以-1， 就可得到单位阵。此时能否用单纯形法？原因?
第二章 线性规划的对偶理论与灵敏度分析
北京联合大学 耿钰
第四节 对偶单纯形法
对偶单纯形法并不是求对偶问题解的方法，而是利用单纯形 法求解规划问题时运用了对偶理论。
也就是说：对偶单纯形法与单纯形法一样都是是求解线性规划 的一种基本方法。它是根据对偶原理和单纯形法原理设计出来的， 因此称为对偶单纯形法。
也就是说，当原问题达到最优时，对偶问题的解可行。并且根据 对偶的性质，我们可以确定此时对偶问题也达到最优
北京联合大学 耿钰
初始单纯形表
项目
非基变量
XB XN
0 XS b B N
Cj-Zj
CB CN
基变量 XS I 0
项目
基变量
非基变量
CB XB B-1 b Cj-Zj
XB
XN
XS
I B-1 N
B-1
北京联合大学 耿钰
二、进行灵敏度分析的基本原则
1、在最终单纯形表的基础上进行； 2、尽量减少附加的计算工作量；
北京联合大学 耿钰
三、灵敏度分析的步骤
1. 先求问题的最优解. 2. 将参数的改变通过计算反映到最终单纯形表上来. 3. 检查原问题的可行解和检验数是否满足最优. 4. 依据不同情况决定继续计算或得到结论.
原问题 对偶问题
结论或继续计算的步骤
可行解 可行解 问题的最优解或最优基不变 可行解 非可行解 用单纯形法继续迭代求最优解 非可行解 可行解 用对偶单纯形法继续迭代求最优解 非可行解 非可行解 引进人工变量，编制新的单纯形表重
新计算
北京联合大学 耿钰
四、灵敏度分析的主要内容
1. 分析 cj 的变化 2. 分析 bi 的变化
x1, x2, x3 0
解：先将这问题化成下列形式，以便得到对偶
问题的初始可行基
max z 2 x1 3x2 4 x3
（P）
x1 2 x2 x3 x4 3 2 x1 x2 3 x3 x5 4
x j 0, j 1,2,,5
北京联合大学 耿钰
在实际生产过程中，上述三类因素均是在不断变化 的，如果按照初始的状况制订了最佳的生产计划，而在计 划实施前或实施中上述状况发生了改变，则决策者所关心 的是目前所执行的计划还是不是最优，如果不是应该如何 修订原来的最优计划。更进一步，为了防止在各类状况发 生时，来不及随时对其变化作出反应，即所谓“计划不如 变化快”，企业应当预先了解，当各项因素变化时，应当 作出什么样的反应。
-4 0 0
4/3
-
-
1/2 1 -1/2
3/2 0 -1/2
-1
0
-1
-
-
2
-1/5 7/5 -3/5
-2/5 -1/5 -8/5
1/5 -2/5 -1/5
X ( 11 / 5,2 / 5,0,0,0 )T
w

-z

28 5
北京联合大学 耿钰
第四节 对偶单纯形法
使用对偶单纯形法求初始解时右边常数项可以为负， 所以对于一些大于等于号的约束表达式不需要添加人工 变量，只要两边同时乘上-1，就可用对偶单纯形法求解， 简化计算，这是该方法的优点。缺点是很难找到一个初 始解使得所有检验数都小于等于零，因而很少单独使用。