对偶理论和灵敏度分析
1.单纯形的矩阵描述
用矩阵语言描述单纯形法的关键是写出两个基本的表达式,设线性规划的标准型为
maxz=CX
AX=b
X≥0
C=(CB,CN)，X=(XB,XN)’，A=(B,N)
由约束条件AX=(B,N)(XB,XN)=BXB+NXN=b，可以得到用非基变量表示基变量的表达式:
XB=B-1b-B-1NXN (1)
将(1)式代入目标函数的表达式,可以得到用非基变量表示目标函数的表达式.
Z=CX=(CB,CN)(XB,XN)’=CBXB+CNXN
=CB(B-1-B-1NXN)+CNXN
=CBB-1b+(CN-CBB-1N)XN
=CBB-1b+σNXN
另非基变量等于零，则Z=CBB-1b
注意XB检验数为零,实质上是CB-CBB-1B=0
Y=CBB-1为单纯形乘子
-CBB-1b
B-1b
c
x b
0 CN-CBB-1 N
-z
XB XN
θ
B-1B B-1N
CB CN
XB
注意:在初始单位矩阵的位置,在各运算表中就是B-1的所在位置
B-1
…
I
I
…
B
2.改进单纯形法
改进单纯形法又称为逆矩阵法或修正单纯形法,是在原来单纯形法基础上加以改进，关键在于求B-1,有了B-1,单纯形算法的各个表中的数字都可以利用线性规划中的原始数据计算出来。
3对偶理论
某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示：
问如何安排甲、乙两产品的产量，使利润为最大。
3 5
单位产品获利
8
12
36
1 0
0 2
3 4
A
B
C
生产能力
工时单耗
甲 乙
产品
车间
maxZ= 3x1 +5 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1 ≥0, x2 ≥0
.
若上例中该厂的产品平销，现有另一企业想租赁其设备。厂方为了在谈判时心中有数，需掌握设备台时费用的最低价码，以便衡量对方出价，对出租与否做出抉择。
在这个问题上厂长面临着两种选择：自行生产或出租设备。首先要弄清两个问题：
①合理安排生产能取得多大利润?
②为保持利润水平不降低，资源转让的最低价格是多少？
问题 ①的最优解：x1=4，x2=6，Z*=42。
假设出让A、B、C设备所得利润分别为y1、y2、y3
原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有
y1+0y2+3y3≥ 3
同理，对乙产品而言，则有
0y1+2y2+4y3≥ 5
设备台时出让的收益（希望出让的收益最少值）
min=8y1+12y2+36y3
显然还有
y1，y2，y3≥0
min =8y1+12y2+36y3
y1+ 0y2+ 3y3≥ 3
0y1+ 2y2+ 4y3≥ 5
y1，y2，y3≥0
.
maxZ= 3x1 +5 x2
x1 ≤8
2x2 ≤12
3x1 +4 x2 ≤36
x1 , x2 ≥0
.
例 线性规划问题
maxz=3x1+5x2
st x1+3x2 10
7x1+4x2 20
xj0;j=1,2.
对偶问题为：
ming=10y1+20y2
st y1+7y2 3
3y1+4y2 5
yi 0;i=1,2。
对偶变换的规则
对偶问题的基本性质
为了便于讨论，下面不妨总是假设
(1)对称性：对偶问题的对偶是原问题。
(2) 弱对偶性：对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值，即CX0≤Yb0。
弱对偶定理推论：
原问题的任何可行解目标函数值是其对偶问题目标函数值的下限；对偶问题的任何可行解目标函数值是原问题目标函数值的上限。
(3)无界性 若原(对偶)问题为无界解，则其对偶(原)问题无可行解
当原问题(对偶问题)为无可行解,其对偶问题(原问题)或具有无界解或无可行解。
如果原(对偶)问题有可行解，其对偶 (原)问题无可行解，则原问题为无界解。
(4)强对偶性
可行解是最优解的性质(最优性准则定理)
若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0, Y0分别是相应问题的最优解
（5）主对偶定理
若原问题和对偶问题两者皆可行,则两者均有最优解,且此时目标函数值相等。
综上所述，一对对偶问题的解必然是下列三种情况之一:
原问题和对偶问题都有最优解。
一个问题具有无界解，另一个问题无可行解。
原问题和对偶问题都无可行解。
(6)互补松弛性
设X0, Y0分别是原问题和对偶问题的可行解，Xs为原问题的松弛变量的值、Ys为对偶问题剩余变量的值。X0, Y0分别是原问题和对偶问题最优解的充分必要条件是 ：Y0 Xs = Ys X0 = 0
(7)原问题单纯形表检验数行与对偶问题解的关系
原问题单纯形表检验数的相反数对应对偶问题的一个基解.显然,原问题最终单纯形表检验数的相反数对应对偶问题的一个基可行解
-Y
-YS2
YS1
-CBB-1
CN-CBB-1N
0
XS
XN
XB
例已知线性规划问题：
试用对偶理论证明此线性规划问题无最优解。
解：对偶问题为：
由第一约束条件显见，对偶问题无可行解因为（0，0，0）为线性规划问题的可行解。而对偶问题无可行解，则原问题为无界解或无可行解，故原问题无最优解。
例5：线性规划问题最优解为
用对偶问题求原问题的最优解。
对偶问题为：
将对偶问题的解代入上述约束条件，可知2、3、4式为严格不等式；由松弛互补性，可得x2=x3=x4=0,因y1,y2大于零，所以原问题的两个约束条件应该取等式，故有：
4.影子价格（对偶价格）
对偶变量yi(i=1,2,…,m)表示原问题的第i个约束条件的影子价格，它表示：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。
(1)影子价格能指示企业内部挖潜的方向。影子价格越高的资源，它对目标增益的影响越大，同时也表明这种资源越稀缺和贵重。企业的管理者要重视这种资源的管理，挖掘潜力，及时组织资源，由此可以给企业带来较大的收益。
(2)影子价格指导企业间的分工与协作。影子价格可以作为企业在接受外协加工任务时，对外协单位使用资源的收费标准，按照影子价格收费，保证了企业与外协单位双方平等互利的格局，可以促进双方合作。
(3)影子价格在新产品开发决策中的应用。
两种新产品A,B的机会成本（万元）：
A单位产品的机会成本=1×3/4+2×0+3×1/4=3/2
B单位产品的机会成本=2×3/4+1×0+4×1/4=5/2
1 3
单位利润(万元)
3/4
0
1/4
影子价格(万元)
1 2
2 1
3 4
A B
钢材
煤
机时
产品
资源
由于投产A产品所能提供的单位利润（1万元）不大于投产的机会成本（万元），因此A产品不宜投产；
而B产品的机会成本（万元）小于该产品投产后所能提供的利润（3万元），因此投产B产品可以给工厂带来较大的收益。
如果新产品B确实为社会所欢迎,而在资源利用上与老产品发生冲突，工厂可以考虑用B产品去更换老产品，以获得更大的经济效益。
(4)影子价格在资源采购决策中的应用。
当资源的市场价格低于影子价格，企业买进该资源，扩大生产，当资源的市场价格高于影子价格，企业应设法转让该资源。
(5)利用影子价格分析工艺改变后对资源节约的收益。
例如设工厂现有钢材100吨，其影子价格为3/4，采用新工艺后，钢材可以节约2%，则由此带来的经济收益为：
100×3/4×2%=3/2(万元)
5.对偶单纯形法
对偶单纯形法是应用对偶原理求解原问题线性规划的一种方法,采用的技术是在原问题的单纯形表格上进行对偶处理。注意:对偶单纯形法不是求解对偶问题的单纯形法。
单纯形法的求解过程是：在保持原始可行(b列保持≥０）的前提下，通过逐步迭代实现对偶可行（检验数行≤０）。换个角度考虑线性规划的求解过程：能否保持对偶可行（检验数行保持≤０）的前提下，通过逐步迭代实现原始可行 (b列≥０，从非可行解变成可行解）呢？答案是肯定的，这就是对偶单纯形法的基本思想。
步骤：
（1）根据线性规划问题，列出初始单纯形表。若b列数字还有负分量，检验数保持非正，则
（2）确定换出变量
选min[(B-1b)i/ (B-1b)i <0]对应的变量xl为换出变量
（3）确定换入变量
θ=min[cj-zj/aij](aij<0)所对应的非基变量xk为换入变量。
（4）以alk为主元素进行迭代运算，并重复以上步骤
利用对偶单纯形法求解以下线性规划问题：
解法
cj
CB
XB
b
x1
x2
x3
x4
x5
-1
-3
0
0
0
-2
-3
-1
-1
-2
-2
1
0
0
0
1
0
0
0
1
-3
-4
-1
x3
x4
x5
0
0
0
-1
-3
0
0
0
cj-zj
1/3
3/2
x3
x1
x5
0
1
0
1/3
2/3
-4/3
1
0
0
-2/3
-1/3
-1/3
0
0
1
cj-zj
-1/3
4/3
1/3
0
-7/3
0
-1/3
0
1/2
0
-1
0
x4
x1
x5
½
3/2
1/2
0
1
0
-1/2
½
-3/2
-3/2
-1/2
-1/2
1
0
0
0
0
1
0
-1
0
cj-zj
0
-5/2
-1/2
0
0
-3/2
此时所有的B-1b均≥0 ，且所有的cj-zj均≤0，此时已得到最优解为：
X*=(3/2,0,0,1/2,1/2)T
Z*=-3/2
总结：对偶单纯形法与单纯形法的比较
最优解时
要求
单纯形法
对偶单纯形法
保持
B-1b
≥0
所有的
cj-zj≤0
所有的
cj-zj≤0
B-1b
≥0
特点：
可以避免加人工变量，简化计算．
灵敏度分析和整数规划常借助于对偶单纯形法分析．
局限性在于初始单纯形表的检验数行很难满足小于或等于零的要求，即满足检验数行对应的对偶问题的解是可行解．
6.灵敏度分析
灵敏度分析的意义
线性规划研究的是一定条件下的最优化问题，采用优化方案可以达到节约资源、提高效益的目的，但是对“优化方案”必须要有全面的认识，不可机械地对待。
优化方案是建立在特定的资源环境和技术条件之上的，而环境和条件总是处在不断地变化之中，如产品价格、原材料成本、加工技术水平、资源消耗系数等时有波动，所以优化方案是个相对稳定的概念。当基础数据发生变化时，最优方案也就变了。
基础数据往往是测算估计的数值，虽然在运算过程中要求十分严格，但基础数据的误差是不可避免的。为了对优化结果有更全面的了解和恰当的运用，就需要进行灵敏度分析。
灵敏度分析所要解决的问题：
系数在什么范围内变化，不会影响已获得的最优基(即最优解或最优解结构不变)。
如果系数的变化超过以上范围，如何在用最简便的方法在原来最优解的基础上求得新的最优解
当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。
右端项bi变化的灵敏度分析
bi变化到什么程度可以保持最优基不变？
用xB= B-1b ≥0。
例：求以下模型中第二个约束条件右端项b2的变化范围。
maxZ=70X1+120X2
9X1+4X2≤360
4X1+5X2 ≤200
3X1+10X2 ≤300
X1≥0 X2≥0
0 0 0
4280
σj
0 0 1
1 0 0
0 1 0
84
20
24
X3
X1
X2
0
70
120
34 0 0 0 -12
3600
σj
20
100
0 1 0
0 0 1
1 0 0
240
50
30
X3
X4
X2
0
0 120
70 120 0 0 0
0
σj
90
40
30
9 4 1 0 0
4 5 0 1 0
3 10 0 0 1
360
200
300
X3
X4
X5
0
0
0
θi
X1 X2 X3 X4 X5
b
XB
CB
70 120 0 0 0
Cj
解：从最优单纯形表得出：XB=(20,24,84)T
最优基为：
注意：应为初始数据。
还可以从单纯形表中找出B-1.
设b2由200变为200＋∆ b2，则b由
由此得到迭代后的单纯形表：
cj
70
120
0
0
0
CB
XB
b
x1
x2
x3
x4
x5
θi
0
1
0
0
0
1
1
0
0
∆b2
20+ ∆ b2
24-0,12 ∆ b2
x3
x1
x2
0
70
120
σj
4280+ ∆ b2
0
0
0
上述解是最优解，必须是可行解：
即：
解得：－50 ≤ ∆ b2 ≤ 。
可知右端项系数b2的变化范围是:
（200－50） ～（200＋)
在此范围内σj ≤0， B-1b ≥0，最优解仍有效，即最优解的基变量不变，最优解为：
最优值为：Z*=4280+ ∆ b2
目标函数中价值系数cj的灵敏度分析
分cj是非基变量的系数还是基变量的系数两种情况来讨论。
①若cj是非基变量xj的系数，此时，当cj变化∆ cj后，要保证最终表中这个检验数仍小于或等于零即可。
②若cj是基变量xj的系数，则引起的变化较大。
例：在模型例1中，求基变量x2的系数变化范围。
解：本例的最优单纯形表如下：
0
70
120
cj
CB
XB
b
x3
x1
x2
84
20
24
x1
x2
x3
x4
x5
θi
70
120
0
0
0
0
1
0
0
0
1
1
0
0
σj
4280
0
0
0
基变量系数c2由120变为120＋ ∆ c2后，可以得到迭代后的单纯形表。
cj
CB
XB
b
x3
x1
x2
84
20
24
x1
x2
x3
x4
x5
θi
70
120＋ ∆ c2
0
0
0
0
1
0
0
0
1
1
0
0
σj
4280＋24∆ c2
0
0
0
+∆ c2
∆ c2
0
70
120+ ∆ c2
要保持最优解，必须使σj ≤0， 即：
－+ ∆ c2 ≤0
∆ c2 ≤0
解得－ ≤ ∆ c2 ≤
由此可知， c2 的变化范围为：
（120－)~(120+)，即 ≤ c2 ≤。
技术系数aij的灵敏度分析
某非基变量技术系数的改变会影响该非基变量的检验数，如果检验数仍然可以满足≤０，则最优解保持不变．否则继续迭代．
某基变量技术系数j的改变的灵敏度分析比较复杂，因为某基变量技术系数的改变对最终表解的可行性和检验数行的检验系数都可能产生影响．
例：讨论线性规划
的系数列向量 的情况。
解：首先利用单纯形法得出初始单纯形表及最优单纯形表如下。
CB
XB
b
x1
x2
x3
x4
x5
2
-1
-1
0
0
0
0
x4
x5
6
4
1
-1
1
2
1
0
1
0
0
1
σj
2
-1
-1
0
0
2
0
x1
x5
6
10
1
0
1
3
1
1
1
1
0
1
σj
0
-3
-1
-2
0
由于 .所以
CB
XB
b
x1
x2
x3
x4
x5
2
-1
-1
0
0
0
0
x4
x5
6
4
1
-1
1
2
1
0
1
0
0
1
σj
2
-1
-1
0
0
2
0
x1
x5
6
10
1
0
1
3
1
1
1
1
0
1
σj
0
-3
-1
-2
0
2
7
-5
由此可知，当前解仍为最优解。
