3对偶理论与灵敏度分析
3-1 线性规划对偶问题
3-2 对偶单纯形法
3-3 影子价格
3-4 灵敏度分析
3-1线性规划对偶问题
在例中：某工厂生产I、II两种型号的计算机，为了生产一台I型和 II型计算机，所需要原料分别为2和3个单位，需要的工时分别为4和2个单位。在计划期内可以使用的原料为100个单位，工时为120个单位。已知生产每一台I 、II型计算机可获利分别为6和4个单位，试确定获利最大的生产方案。
I 型计算机
II型计算机
原料
2
3
100
工时
4
2
120
利润（每台）
6
4
设 y1 ，y2 分别为每单位原料与每工时收取费用。
3-1线性规划对偶问题
1.对偶问题： 若该工厂的原料和工时都用于对外出租，工厂收取租赁费。试问：每单位原料与每工时各如何收费才最有竞争力？
3-1线性规划对偶问题
原问题
对偶问题
（不少于Ⅰ型的利润）
（不少于Ⅱ型的利润）
3-1线性规划对偶问题
2、对偶定义
对称形式： 互为对偶
(LP)
“Min-- ≥”
“Max -- ≤ ”
(DP)
3-1线性规划对偶问题
一对对称形式的对偶规划之间具有下面的对应关系。
（1）原问题的目标是对CX求极大，而对偶问题的目标是对Yb求极小；
（2）原问题的价值系数成为对偶问题的资源系数，原问题的资源系数b成为对偶问题的价值系数；
3-1线性规划对偶问题
（3）对偶问题与原问题相比较，约束条件的 方向改变了；
（4）原问题的系数矩阵的转置恰为对偶问题的系数矩阵，即原问题的每一列系数对应对偶问题的每一行系数；
（5）原问题的约束行数等于对偶问题的变量数，即列数，而原问题的变量数等于对偶问题的约束行数。
3-1线性规划对偶问题
3、 对偶理论
性质1：（对称性）对偶问题（D）的对偶是原问题（L）。
性质2：原问题第i个约束为等式，则其对偶问题中的第i个对偶变量为自由变量；
反之，若原问题的第j个变量是自由变量，则其对偶问题的第j个约束为等式。
***根据对偶的定义及前述的两个性质，可以求出任何形式的线性规划的对偶规划。***
3-1线性规划对偶问题
线性规划原问题与其对偶问题不仅具有形式上的对称性，而且它们的解之间也具有紧密的联系。
变形
互为
对偶
3-1线性规划对偶问题
性质3：（弱对偶性）设X、Y分别是原问题（L）和对偶问题（D）的任一可行解，则：
性质4：（无界性）若原问题(对偶问题)为无界解，则其对偶问题（原问题）无可行解。（这个性质可由弱对偶性证得，此处略。）
则
证明：由已知
在
在
得到：
3-1线性规划对偶问题
性质5：设 是原问题的可行解， 是对偶问题的可行解，且 ，则 、 是各自问题的最优解。
证明：设X是原问题的任一可行解，则有
是原问题的最优解。
同理 ，
性质6：若原问题有最优解，那么其对偶问题也有最优解，且它们的最优值相等
可见
是对偶问题的最优解。
所以
3-1线性规划对偶问题
性质7：在对称形式对偶问题的线性规划中，对偶问题最优解的单纯形表上，出现在目标
函数检验数行的后面的m个元素（不包括常数项），它们的相反数构成原问题的最优解。
3-1线性规划对偶问题
例 写出下面线性规划的对偶规划模型
解 先将约束条件变形为“≤”形式
3-1线性规划对偶问题
再根据非对称形式的对应关系，直接写出对偶规划
3-1线性规划对偶问题
3-2 对偶单纯形法
从前面讨论中，可以看到在原问题取得最优解时，也得到对偶问题的最优解。
即：如果原问题最优基为B，取
则所有
也就是
则
是对偶可行解
又因为
所以也是最优解。
3-2 对偶单纯形法
在单纯形算法中，是从一个原问题的基可行解转到另一个基可行解，一直迭代到 是对偶可行解为止。
3-2 对偶单纯形法
对偶单纯形法则是从原问题的一个对偶可行解（满足所有的 ）
出发，以基变量值是否全部非负为检验数，连续迭代到原问题的可行解为止。
3-2 对偶单纯形法
两种算法最终的结果是一样的，区别是对偶单纯形法的初始解不一定要满足原问题的可行性，而只要求所有检验数都非正即可，
在保证所得解始终是对偶可行解的前提下，连续迭代到原问题的基可行解，从而取得问题的最优解。
3-2 对偶单纯形法
对偶单纯形法计算步骤如下：
步骤1： 确定原问题（L）的初始基B，使所有 ，即 是基可行解，建立初始单纯形表。
步骤2： 检查基变量所取的值，若 ，
则已经得到最优解，停止计算。否则，计算
，确定 为旋出变量。
3-2 对偶单纯形法
步骤3： 若所有 ，则原问题无可行解，计算停。否则计算
确定为 xk 旋入变量。
步骤4： 以 alk 为主元作（L,K）旋转变换，转步骤2。
可以证明按照上述方法进行迭代，所得解始终是对偶可行解。
3-2 对偶单纯形法
例：用对偶单纯形法求解下面的问题：
解：令
则问题可以
标准化为：
3-2 对偶单纯形法
取初始基
是对偶可行解，建立单纯形表（见表3-1）
则
是非基可行解，但
3-2 对偶单纯形法
-2
3/4
0
-12
-2
-3
X5
X6
0
0
x1 x2 x3 x4 x5 x6
B-1b
XB
CB
C
3-2 对偶单纯形法
1
1/2
X2
X1
-8
-12
2
-1/4
X2
X4
-8
-12
x1 x2 x3 x4 x5 x6
B-1b
XB
CB
C
3-2 对偶单纯形法
一般情况下，如果问题能够用对偶单纯形法，计算量会少于单纯形法。
但是，并不是任何问题都能用对偶单纯形法计算的。当线性规划问题具备下面条件时，可以用偶单纯形法求解：
问题标准化后，价值系数全非正； 所有约束条件全是不等式。
一般，当问题中的变量多于约束条件时，用对偶单纯形法计算可以减少计算工作量。
3-2 对偶单纯形法
证明：首先看到问题存
在可行解，如（0 0 0）
上述问题的对偶问题：
由第一约束条件可知对
偶问题无可行解，因而
无最优解。由此，原问
题也无最优解。
例：已知线性规划问题：
试用对偶理论证明该
线性规划问题无最优解。
3-2对偶单纯形法
对偶单纯形法的适用范围
对偶单纯形法适合于解如下形式的线性规划问题
3-2对偶单纯形法
在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。
对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。
从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。
单纯形表的理解（例题）
上表中6个常数 a1 , a2 , a3 , b , 1 , 2 取值在什么范围可使
1、现可行解最优，且唯一？何时不唯一？
2、现基本解不可行；
3、问题无可行解；
4、无有限最优解；
5、现基本解可行，由 x1 取代 x6 目标函数可改善。
单纯形法和对偶单纯形法步骤
是
是
是
是
否
否
否
否
所有
所有
得到
最优解
计算
计算
典式对应原规划的基本解是可行的
典式对应原规划的基本解的检验数
所有
所有
计算
计算
以为中心元素进行迭代
以为中心元素进行迭代
停
没有最优解
没有最优解
单纯形法
对偶单纯形法
3-3影子价格
分别为（LP）和（DP）的最优解
那么有：
根据
可知
表示 bi 变化1个单位对目标 f 产生的影响
为 bi 的影子价格
称
3-3影子价格
影子价格 — 是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。
注意：若 B 是最优基，则
为影子价格向量
3-3影子价格
另单纯形中，设B是最优基，
是最优解；则最优值
取
则Y是对偶最优解。
3-3影子价格
下面我们进一步讨论一下
的经济含义。
设
有单位增量，即：
其它各参数不变。若最优基不变，则
3-3影子价格
综上，所以 表示在原问题已取得最优解的情况下，第i种资源改变一个单位时，总收益的变化值。
也可以说 是对第i种资源的一种价格估计。这种价格估计并不是第i种资源的实际成本或价值，而是由该企业在制产品的收益来估计所用资源的单位价值——称为影子价格。
3-3影子价格
由于影子价格是指资源增加时对最优收益的贡献，所以也称它为资源的机会成本或边际产出，它表示资源在最优产品组合时，具有的“潜在价值”或“贡献”。
资源的影子价格是与具体的企业及产品有关的，同一种资源，在不同企业或生产不同产品时，对应的影子价格并不相同。
3-3影子价格
影子价格是经济学中的重要概念，将一个企业拥有的资源的影子价格与市场价格比较，可以决定是购入或出让该种资源。
在考虑一个地区或国家某种资源的进出口决策中，资源的影子价格是影响决策的一个重要的因素。
当某种资源的市场价格低于影子价格时，企业应该
购入该资源用于扩大生产；
否则，应将已有资源卖掉。
20
20
4
6
备注
6 4 0 0
C
上表为例的最优单纯形表，在单纯形法计算表中，可以算得问题的各种资源的影子价格。
其中松弛变量
的检验数分别为：
3-3影子价格
20
20
4
6
…………………….
……………..
6 4 0 0
K=1
L=2
100/2
120/4
100
120
0
0
备注
6 4 0 0
C
3-3影子价格
影子价格的经济含义
影子价格是对现有资源实现最大效益时的一种估价。
企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。
第二，是否将投资用于购买设备，以扩大生产能力，若市价低于设备的影子价格，可考虑买进该设备，否则不宜买进。
3-3影子价格
影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。
3-3影子价格
需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。
另外，影子价格的经济含义另一方面，是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。
3-4灵敏度分析
在线性规划问题中，目标函数、约束条件的系数以及资源的限制量等都当作确定的常数，并在这些系数值的基础上求得最优解。
但是，实际上这些系数或资源限制量并非是一成不变的，它们往往是一些估计和预测的数字。
3-4灵敏度分析
市场经济条件下，价值系数随着市场的变化而变化
约束系数随工艺的变化或消耗定额的变化而变化，
计划期的资源限制量也是经常变化的。
当这些系数发生变化时，最优解会受到什么样的影响呢？最优解对哪些参数的变动最敏感？
搞清这些问题会使我们在处理实际问题时，具有更大的主动性和可靠性。
3-4灵敏度分析
确定线性规划模型的某些系数或限制参数的变动对最优解的影响分析被称作----灵敏度分析。
3-4灵敏度分析
灵敏度分析主要解决两个问题：
（1）这些系数在什么范围内变化时，
原求出的线性规划的最优解或最优基不变，
即最优解相对参数变化的稳定性。
（2）如果系数的变化引起了最优解变化，
如何用最简洁的方法求出新的最优解。
ci , bj发生变化—— 本段重点
增加一约束或变量及A中元素发生变化—通过例题学会处理
对于表格单纯形法，通过计算得到最优单纯形表。 应能够找到最优基 B 的逆矩阵 B-1 ， B-1b 以及 B-1N，检验数 j 等。
3-4灵敏度分析
3-4灵敏度分析
1、目标函数中价值系数C的灵敏度分析
分非基变量和基变量的价值系数两种情况讨论。
1）设非基变量 X j 的价值系数C j 有增 量
其它参数不变，求
的范围使原最优解不变
3-4灵敏度分析
由于 C j 是非基变量的价值系数，因此它的改变仅仅影响检验数 的变化，而对其它检验数没有影响。设
所以当
原最优解不变。
3-4灵敏度分析
即非基变量的价值系数 Cj 变化，只当
最优解不变；否则，将最优单纯形表中的检
验数
继续单纯形法的计算。
3-4灵敏度分析
例:
Max z = -2x1 - 3x2 - 4x3
. -x1-2x2-x3+x4 = - 3
-2x1+x2-3x3+x5 = - 4
x1 ,x2 ,x3 ,x4 ,x5 ≥0
3-4灵敏度分析
例：最优单纯形表
假设 C3的值有增量 Δc3
分析 Δc3 使最优解不变的范围
+Δc3
+Δc3
表中σ3= c3+Δc3-(c2×a13+c1×a23 ) = -9/5+Δc3
只要-9/5+Δc3 ≤0 ，即Δc3 ≤9/5 则原最优解不变
3-4灵敏度分析
(2)设基变量 XB 的价值系数 CB 有增量 ，其它参数不变，求使最优解不变。
由于 CB是基变量的价值系数，因此它的变化将影响所有的非基变量的检验数的变化。
令 则
3-4灵敏度分析
下标为r的基变量价值系数有增量，只要使所有
非基变量 则最优解不变
是单纯形表中下标为 r的基变量所在行的系数。
即使
3-4灵敏度分析
若下标为 r的基变量价值系数有增量，
只要使所有非基变量 的检验数满足
原最优解不变；否则将最优单纯形表中的检验
继续单纯形法的表格计算。
3-4灵敏度分析
例:
Max z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5
. x1 + 2x2 + x3 = 8
4x1 + x4 = 16
4x2 + x5 = 12
x1 , x2 , x3 , x4 , x5 ≥ 0
3-4灵敏度分析
例: 下表为最优单纯形表,考虑c2变化
可得到 -3≤Δc2≤1时，原最优解不变
+Δc2
+Δc2
-Δc2/2
+Δc2/8
可直接用公式
3-4灵敏度分析
以上就两种情况讨论了 在什么范围内变动时，原最优解不变，如果 不在上述（下式给出）范围内变动，则一定会出现正的检验数，原最优解不再是最优解，以该解为初始解，用单纯形法继续迭代可以尽快地求出新的最优解
再举2-2例如下：
20
20
4
6
…………………….
……………..
6 4 0 0
K=1
L=2
100/2
120/4
2 3 1 0
4 2 0 1
100
120
0
0
备注
6 4 0 0
C
（1） 即 是基变量的价值系数
（1）求 的范围使原最优解不变
（2）如 变为12，求新的最优解。
用非基变量的检验数与单纯形表中基变量X2所在行相应的元素作比值得：
（2）将 C1=12 代入原最优表，重新求检验数，原最优解不再是最优解，用单纯形法继续迭代运算
0
12
0 0 1 -7/2
K=1
L=2
0 1 1/2 -1/4 1 0 -1/4 3/8
20
20
4
12
备注
12 4 0 0
C
新的最优
解为：
40
30
3-4灵敏度分析
2、资源系数b的分析
设 有增量 ，其它参数不变，则
的变化将影响基变量所取的值，但是对于检验数没有影响。记：
3-4灵敏度分析
2、资源系数b的分析
如果变化后的基变量所取的数值仍大于或等于零，则原最优基不变，新的最优解就是：
3-4灵敏度分析
那么 ，取何值能够保证 呢？
令
时，原问题的最优基不变。
是原最优逆阵的第i列。
结果说明 的变化是由基变量的相反值与
的第 i 列相应的元素比值所确定的。
当
3-4灵敏度分析
如果 不在上述范围内变动，则变化后的基变量 所取的值肯定会出现负分量，但由于 不影响检验数的变化，因此可以用 取
代原有的 ，以该解为初始解，用对偶单纯形法继续求解。
例：已知线性规划问题的初始解及最优解上例
求：（1） 的范围使原最优基不变；
（2）若 变为200，求新的最优解。
幻灯片 58
20
20
4
6
…………………….
……………..
6 4 0 0
K=1
L=2
100/2
120/4
2 3 1 0
4 2 0 1
100
120
0
0
备注
6 4 0 0
C
例：已知线性规划问题的初始解及最优解上例
求：（1） Δb1 的范围使原最优基不变；
（2）若b1 变为200，求新的最优解
3-4灵敏度分析
解：（1）由单纯形表可知
用基变量的值与 第一列相应元素去比得：
原最优基不变。
（2）由于
是非基可行解，用 替换原最优表
中基变量的值，采用对偶单纯形法继续求解
4
0
0 0 -1 /2 -5/4
K=1
L=2
0 1 1/2 -1/4 1 0 -1/4 3/8
70
-5
4
6
备注
6 4 0 0
C
新的最优
解为：
60
20
3-4灵敏度分析
3、系数矩阵A的分析
以下分4种情况讨论系数矩阵的变化：
（1） 增加一个变量
增加变量 xn+1 则有相应的pn+1 ,cn+1 。
那么 计算出B-1pn+1 , n+1=cn+1-∑cri ari n+1
填入最优单纯形表。
若 n+1 ≤ 0 则 最优解不变；
否则，进一步用单纯形法求解。
3-4灵敏度分析
例:
例增加x6 , p6=( 2, 6, 3 )T, c6=5 计算得到
用单纯形法进一步求解，可得：
x* = ( 1,,0,0,0,2 )T f* =
3-4灵敏度分析
（2）增加一个约束
增加一个约束之后，应把最优解带
入新的约束，若满足则最优解不变。
否则，将增加的约束填入最优单纯形表，作为新的一行并引入新的松弛变量或人工变量构造单位阵；
再通过矩阵行变换把该行对应其他基变量所在“列”的元素变为0；
进一步用单纯形法或对偶单纯形法求解。
3-4灵敏度分析
例:
例增加3x1+ 2x2≤15，原最优解不
满足这个约束。于是
经对偶单纯形法一步，可得最优解为（, , 0, 0, 3, 2 )T，最优值为 13. 75
3-4灵敏度分析
（3）改变某非基变量的系数列向量分析
设非基变量 x j 的系数列向量变为
试分析原最优解变化。该变化只影响最优单纯形表的第j列及其检验数。因此，可以先计算
原问题最优解不变，若反之
则以 替代原最优表的第j列，用单纯形法继续求解至最优解。
3-4灵敏度分析
（4）改变某基变量系数列向量的分析
设 x j 基变量的系数列向量变为 ，试分析原最优解的变化。
的变化将导致B的变化，因而原最优表
所有元素都将发生变化，似乎只能重新计算
但是经过认真分析，还是可以利用原最优解来计算新的最优解。
3-4灵敏度分析
（4）改变某基变量系数列向量的分析
我们可以将x j 看作是新增的变量，用
替代原最优表的第 j 列（原为单位列向量）
然后再利用初等行变换将表中列
恢复到原来的单位列向量。
则变化后的单纯形表有以下几种情况：
3-4灵敏度分析
1）基变量值全非负，且检验数全非正，已得新的最优解。
2）基变量值全非负，但存在正检验数，该解是基可行解，可用单纯形法继续求解。
3）存在为负值的基变量，但检验数全非正，该解是对偶可行解，可以用对偶单纯形法继续求解。
3-4灵敏度分析
4）存在取负值的基变量，且存在取正值的检验数，该解既不是基可行解，又不是对偶可行解。
对于这种情况，我们可以将表中取负值的基变量 对应的行还原成约束方程，再用“-1”乘以约束方程的两端，再在方程左端加一个人工变量 X n+1
用该方程替代原单纯形表的第 i 行，则表中对应的基变量变为人工变量 X n+1 ，其价值系数为-M
其对应的数值为 -(B-1b) i ，然后用单纯形法求解。
1、现可行解最优，且唯一？何时不唯一？
唯一：1 , 2 < 0 , a1 , a2 , a3 , b≥0
不唯一：1 = 0， 2 ≤ 0, b≥0
或 1≤ 0, 2 = 0 , a1 > 0, b > 0
2、现基本解不可行： b < 0
3、问题无可行解： b < 0 , a1, a2 ≥ 0
4、无有限最优解: 2 > 0 , a1 ≤ 0 , b > 0
5、现基本解可行，由 x1 取代 x6 目标函数可改善:
1> 0, b > 0 ， a3 > 0 , 3/a3 < b/4 。
