对偶理论与灵敏度分析
对偶问题的提出
对偶理论
影子价格
对偶单纯形法
灵敏度分析
对偶问题的提出
定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题。
应用:
1. 在某些情况下，解对偶问题比解原问题更加容易
2. 对偶变量有重要的经济解释(影子价格)
3. 作为灵敏度分析的工具
4. 对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解)
5. 避免使用人工变量(人工变量带来很多麻烦，两阶段法则增加一倍的计算量)
一、对偶问题的提出
例：某家具厂木器车间生产木门与木窗；两种产品。加工木门收入为56元/扇，加工木窗收入为30元/扇。生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总共时为120小时，油漆工总工时为50小时。
问：(1)该车间应如何安排生产才能使每日收入最大？
(2)假若有一个个体经营者，手中有一批木器家具生产订单。他想利用该木器车间的木工与油漆工来加工完成他的订单。他就要考虑付给该车间每个工时的价格。他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少。
解(1)：设该车间每日安排生产木门x 1扇，木窗x 2扇，则数学模型为
X*=(15,20)’ Z*=1440元
??
?
??≥≤+≤++=-0502120343056max 21212121x x x x x x x z
解(2)：设y 1为付给木工每个工时的价格，y 2为付给油工每个工时的价格
Y*=(2,24)’ W*=1440元
将上述问题1与问题2称为一对对偶问题，两者之间存在着紧密的练习与区别：它们都使用了木器生产车间相同的数据，只是数据在模型中所处的位置不同，反映所要表达的含义也不同。
二、L P 和D P 的联系与区别
(1)一个极大化，一个极小化
(2)L P 的价值系数行向量＝(D P 右端项)’ (3)L P 的系数矩阵＝(D P 系数矩阵)’ (4)L P 的右端项＝(D P 的价值系数)’ (5)L P 的约束个数＝D P 的变量个数 (6)L P 的变量个数＝D P 的约束个数
三、原问题与对偶问题的关系
1．对称形式下对偶问题的一般形式
定义：满足下列条件的线性规划问题称为具有对称形式：(1)其变量均为非负约束；(2)其约束条件当目标函数求极大时取“≤”号，当目标函数求极小时取“≥”号；(3)右端项b 可取负值。
??
?
??≥≥+≥++=-0303562450120min 2121212
1y y y y y y y w ?????
???????=≥≤+???++????
??≤+???++≤+???++
+???++=),,1(0max :221122222121112121112211n j x b x a x a x a b x a x a x a b x a x a x a x c x c x c z LP j m n mn m m n n n n n
n
对称形式下原问题及对偶问题的矩阵形式
对称性定理：对偶问题的对偶是原问题。 证明：在D P 中，令W ’ = -W
则有
??
?≥-≤--=0
'max Y C YA bY
ω 其对偶问题为：
??
?≥-≥--=0
'min X b AX CX
Z 令Z’=-Z ，则有
??
?≥≤=0
max X b
AX CX
Z 所以，对偶问题的对偶是原问题。
例：写出L P 的对偶问题
2. 非对称形式的原－对偶问题关系
并非所有的LP 问题都有对称形式，故讨论一般情况下LP 问题如何写出其对偶问题
??
?≥≤=0
max :X b AX CX z LP ??
?≥≥=0
'''min :Y C Y A b Y w DP ??????
?≥≤+≤+≤++=0
2,1121214222max :21212121x x x x x x x x x x z LP ???
??≥≥++≥++++=0,,2242
22min :3
21321321321y y y y y y y y y y y y w DP
例 写出下述线性规划的对偶问题
解：先化为对称形式，因为目标函数求极大，所以约束条件变为“≤”，决策变量≥0
令对应上述4个约束条件的对偶变量分别为'',',',3321y y y y 则有
令''','33322y y y y y -=-=，将上边3，4两个约束条件合并，得
??????
?≤≥=++
≥+-≤-
+++=无约束
3213213213213
21004163253234max x x x x x x x x x x x x x x x z ??????
?≤≥=++-≤+-≥+
+++=无约束
3213213213213210
3
654313242min y y y y y y y y y y y y y y y w ??????
?-≤+-+
-≤-+-
-≤++--≤+---+-=4''''4''''1''6'6'32''55'32''3'3'4max 33213321332133213321x x x x x x x x x x x x x x x x x x x x z 0
'',',',3''''653''''654''''31''''32'
'4'4'2min 332133213321332133213321≥??????
?-≥+-+
≥
-+--≥+---≥
-+--+-=y y y y y y y y y y y y y y y y y y y y y y y y w
经过以上分析，可以总结出原规划与对偶规划相关数据间的联系。对偶关系相互对照表
例写出下列线性规划的对偶问题
结果?
?
?
?
?
?
?
≤
≥
=
+
-
≥
-
+
≤
-
+
+
+
=
无约束
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
1 2
1
2
1
3
2
25
min
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
z
?
?
?
?
?
?
?
≥
≤
=
+
-
-
≥
-
+
≤
+
+
-
+
+
=
无约束
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
3
2
2
25
2
max
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y
w
练习写出下列线性规划的对偶问题
练习结果?
?
?
?
?
?
?
≤
≥
=
+
≤
+
-
≥
+
+
+
+
=
无约束
3
2
1
3
1
3
2
1
3
2
1
3
2
1
3
4 3
1
3
2
4
2
max
x
x
x
x
x
x
x
x
x
x
x
x
x
x
z
?
?
?
?
?
?
?
≥
≤
=
+
+
≤
-
≥
+
+
+
+
=
无约束
3
2
1
3
2
1
2
1
3
2
1
3
2
1
4
1 3
2
3
2
3
4
min
y
y
y
y
y
y
y
y
y
y
y
y
y
y
w
对偶问题的基本性质(对偶定理)
一、单纯形法的矩阵描述
对于对称形式的线性规划问题，其标准形式为
X S 为松弛变量,X S =(x n +1,x n +2,…,x n +m ), I 为m ×m 矩阵
),(),(N B N B C C C X X X N B A =?
??
?
??== b NX BX b X X N B N B N B =+?=???? ??),(
列出初始单纯形表
设若干步迭代后，基变量为X B , X B 在初始单纯形表中的系数矩阵为B ，而A 中去掉B 的若干列组成矩阵N ，则迭代后的单纯形表为：
从表中看出：
(1)对应初始单纯形表中的单位矩阵I ，迭代后的单纯形表中为B -1
(2)初始单纯形表中的基变量X S =b ，迭代后为X B =B -1b
??
?≥≤=0
max X b AX CX z ??
?≥≥=+=0
,0max s s X X b IX AX CX z
(3)初始单纯形表中约束系数矩阵[A ,I ]=[B ,N ,I ]，迭代后的表中为[B -1A , B -1I ]=[ B -1B , B -1N , B -1I ]＝[ I , B -1N , B -1]
(4)若初始矩阵中变量x j 的系数列向量为P j ，迭代后为P j ’，则
P j ’= B -1P j
(5)当B 为最优基时，应有?????≤-≤---)2(0
)
1(01
1
B C N B C C B B N
又因为XB 的检验数可写为)3(001=-?=--B B C C I C C B B B B
将(1)和(3)合并，则有?????≤-≤---00
1
1
B C A B C C B
B
C B B -1称为单纯形因子，令C B B -1＝Y 则有???≥≥0
Y C
YA
C B B -1＝Y ，检验数行的相反数，恰好是对偶问题的可行解。
将Y ＝C B B -1代入对偶问题的目标函数值，Z b B C Yb W B ===-1
所以当原问题为最优解是，对偶问题为可行解，且两者目标函数值相同，根据下节的对偶问题的基本性质，将看到这时对偶问题的解也为最优解。
二、对偶问题的基本性质(对偶定理)
对于下面标准形式的原，对偶问题，有以下定理：
定理1(弱对偶定理)：如果X (0)是原问题的可行解，Y (0)是对偶问题的可行解，则恒有
C X (0) ≤ Y (0) b
??
?≥≤=0
max :X b AX CX z LP ??
?≥≥=0
'''min :Y C Y A b Y w DP
证明：X(0)是原问题的可行解，所以A X(0) ≤b (1)
Y(0)是对偶问题的可行解，所以Y(0) A≥C (2)
X(0) ，Y(0)≥0，用X(0)右乘(2)，Y(0)左乘(1)
Y(0)A X(0) ≤Y(0)b
Y(0) A X(0)≥C X(0)
即
C X(0)≤Y(0)b
(1)原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。
(2)如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界则其原问题无可行解。
(3)如原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。
定理2(最优准则定理)：如果X(0)是原问题的可行解，Y(0)是对偶问题的可行解，则当C X(0)＝Y(0)b时，X(0)，Y(0分别为各自问题的最优解。
证明：设X是LP的任一个可行解，则有
C X≤Y(0) b＝C X(0)
所以X(0) 是最大化问题的最优解
Y(0是最小化问题的最优解
定理3(最优解存在定理)：若LP和DP同时存在可行解，则它们必都存在最优解。
证明同上。
定理4(无界解定理)：若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。
证明：反证法
设原问题目标函数为极大值，无上界
对偶问题的可行解为Y(0)
则C X≤Y(0) b
根据定理1，原问题存在最优解，与假设矛盾，假设不成立
定理5(强对偶性定理)：如果原问题和对偶问题中有一个有最优解，则另一个问题也必存在最优解，且两个问题的最优解的目标函数值相等。
证明：设LP 存在最优解，将其化为标准型，则有
Xa 为松弛变量，Ca 为其价值系数(Ca =0)，设原问题的最优解为X (0)，基为B ，则有
???
???=**)0(a X X X
01≤-=-j B j j P B C C σ
即 0),()(1≤---I A B C C C B a
?
????≥≥??????≤-≤-?----0001
1
11B C C A B C I B C C A B C C B B B a B
令C B B -1＝Y (0)
则有 ?????≥≥0
)0()0(Y C A Y
所以Y (0)是对偶问题的一个可行解
引入定理2，W (0)=Y (0) b ＝C B B -1b=C B X B
∴ 也是对偶问题的最优解
原问题与对偶问题的解之间只有以下3种可能的关系
(1) 两个问题都有可行解，从而都有最优解 (2) 一个为无界，另一个必无可行解 (3) 两个都无可行解
??
?≥≥=++=00max :a a a
a X X b
IX AX X C CX z LP
定理6(互补松弛性定理)：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。
证明：设原问题和对偶问题的标准型是
则 ???+=+==-=-==S
S S S YX YAX X AX Y Yb W X Y YAX X Y YA CX Z )()(
充分性：若Y S X =0 YX S =0 则有Z=W 即CX (0)＝Y (0)b 则X (0)，Y (0)必是各自问题的最优解
必要性：若X (0)，Y (0)是各自问题的最优解 则有CX (0)＝Y (0)b ＝Y (0)A X (0) 即Y S X =0 YX S =0
互补松弛性定理的应用：
在已知一个问题的最优解时，可求其对偶问题的最优解。
例 已知下列问题的最优解为X *=(1/7,11/7),用互补松弛定理求其对偶问题的最优解。
??
?≥≥=+=00max :S S X X b X AX CX
z LP ??
?≥≥=-=00min :S S Y Y C Y YA Yb
w DP ??????
?≥≤-≤+-≤++=0
2,11332232max :21212121x x x x x x x x x x z LP ???????≥≥≥≥-+≥+
-
++=0
2
321332min :321321321321y y y y y y y y y y y y w DP
解：第一步，写出对偶问题
第二步，将LP ，DP 都化为标准型
第三步：将最优解代入标准型中，确定松弛变量取值
第四步：利用互补松弛定理
0****)*,*,(*332211321321=++=???
?
? ??=S S S S S S S X Y X Y X Y X X X Y Y Y X Y
∴ Y 3*=0
0****),(*22112121=+=???
?
??=X Y X Y X X Y Y X Y S S S S S
∴ Y 1S =0 Y 2S =0
第五步：将Y 3*=0 Y 1S =0 Y 2S =0 代入约束条件
则有75742213212121=?
??=????=+=-y y y y y y
∴ 对偶问题的最优解为Y *=(4/7,5/7,0)’
???????≥≥=+-=++-=+++=0,,02,11332232max :3213212211212
1S S S S S S x x x x x x x x x x x x x x z LP ???????≥≥≥≥=--+=-+-
++=0,0002321332min :21321232113213
21S S S S y y y y y y y y y y y y y y y w DP
解题步骤
第1步：写出对偶问题
第2步：将L P ，D P 都化为标准型
第3步：将最优解代入标准型中，确定松弛变量取值 第4步：利用互补松弛定理
练习 若对偶问题的最优解为Y *=(4.1)，试用互补松弛定理求原问题的最优解。X *=(0,0,4,4)’
??
?
??≥≤+++≤+++++=-0
12
22282652max 4143214314
321x x x x x x x x x x x x z
影子价格
定义：根据最优性定理Z *=C X *=Y *b =W *，其中b i 既是原问题约束条件的右端项(第i 种资源的拥有量)，又是对偶问题的价值系数，那么在最优解处
W * = Y *b ＝ Y *1b 1＋ Y *2b 2＋ …＋ Y *m b m
此时b i 增加一个单位，目标函数则变化Y i 个单位
则Y *(对偶解)的经济意义为：资源的单位改变量引起目标函数值的增加量，也就是在资源最优利用条件下对单位第种资源的估价。但这种估价不是资源的市场价格，而是根据资源对生产所作的贡献而作的估价。为区别起见，称为影子价格(s h a d o w p r i c e )。
(1)影子价格的大小客观的反映了资源的稀缺程度。
如果第I 种资源供大于求，即达到最优解时，资源并没用完
∑=n
j i
ij b x a
1
＜，即Xsi ＞0 为非稀缺资源
由互补松弛定理，Yi *=0，即该资源的影子价格＝0 增加该资源的供应不会引起目标函数值的增加。
反之，如果Yi *＞0，即影子价格＞0，则说明增加该资源的供应，会引起目标函数值的增加（Yi *=增加量）
例 木门，木窗
??
?
??≥≤+≤++=-0502120343056max 21212121x x x x x x x z
Z*=20, X*=(15,20)’ Y*=(2,24)
这说明增加这两种资源都会引起目标值的增加，也就是说，它们都是稀缺资源。
木工工时从120增加到121，Z*=1442
油工工时从50增加到51，Z*=1464
如果某个Yi*=0，则增加该资源对Z无影响
应用：
（1）边际价格。管理者增加某种资源对经济效益有无影响及影响程度。
（2）隐含成本。如果增加第3种产品（木椅子），告知新产品的定价标准。假设木椅子对两种资源的消耗分别为木工3h，油工2h，问销价应为多少才能盈利？
3×2＋2×24＝54元
∴售价≥54，才盈利。如售价≤54，不如把资源投入到原来的两种产品中。
（3）告知管理者目前工厂中各种资源的稀缺程度。
Y1*=0 则X1S≥0，第一种资源有剩余
Y2*≠0 则X2S=0，第二种资源无剩余
对偶单纯形法
对偶单纯形法是利用对偶理论求解原问题的一种方法，而不是求解对偶问题的方法
一、基本思路
原始单纯形法：从一个基可行解迭代到下一个基可行解，一直到找出最优解(在迭代过程中，保持解的可行性不变，变化的只是检验数行)
检验数行是对偶问题的解：不可行——可行
此时，原问题的解：可行——最优
也就是说，原问题的最优性条件与对偶解的可行性条件是一致的。
对偶单纯形法求解思路：在迭代过程中，始终保持对偶解的可行性，而原问题的解由不可行向可行性转化，一旦原问题的解也满足了可行性条件，根据对偶定理，两个问题同时达到最优。
二、计算步骤（通过例题说明）
正则解定义：设X(0)是原问题的一个基本解，对应的基是B。若它所对应的检验数向量≤0成立，则称X(0)是原问题的一个正则解。对应的基矩阵B称为正则基。
例1用对偶单纯形法解下列线性规划问题
解：先化为标准型?
?
?
?
?
≥
≥
+
+
≥
+
+
+
=
-
1
2
5
2
6
5
24
15
min
3
1
3
2
1
3
2
3
2
1
x
x
x
x
x
x
x
x
x
w
约束条件两边同乘(-1)
列单纯形表
X *=(0,1/4,1/2)’ Y *=(7/2,3/2)
例2 用对偶单纯形法解下列线性规划问题
??
?
??≥=-++=-+?+?+---=-0
125260052415max 51532143254321x x x x x x x x x x x x x z ??
???-=+-
---=+--1
25265321432x x x x x x x ??
???≥≥+≥+++=-0
5
223318124min 3132313
21x x x x x x x x z
解：改写为标准形式
???
??≥-=+---=+--?+?+---=-0522330018124'max 515
32431
5
4321x x x x x x x x x x x x z
列单纯形表如下：
X *=(0,3/2,1)’ Y *=(2,6)
对偶单纯形法并不万能，只有在约束条件全都为≥0时，才不必引进人工变量，使计算简化。
但在初始单纯形表中，使对偶问题是基可行解这点对多数LP 问题是很难实现的。因此，对偶单纯形法一般不单独使用，主要用于灵敏度分析和整数规划中。
对偶单纯形法计算步骤
第1步：给定一个初始正则解，其对应的基为B
第2步：计算b B b 1-=，若0≥b ，则停止计算，当前正则解为最优解，否则转下一步。
第3步：确定离基变量，令
则x r 为离基变量，第r 行为主行
第4步：确定进基变量
则x k 为进基变量，P k 是主列。
此时如果所有0'≥rj a ，则原问题无可行解。
∑∈-=N
J j j rj r Br x a b x ''
因为0' r b ，当0'≥rj a 时，无论x j 改为怎样的正数，都无法使x Br 的值转为正数，故无可行解。
第5步：迭代。用x k 替代x r 。
第三章线性规划对偶理论与灵敏度分析习题 一、思考题 1．对偶问题和对偶变量的经济意义是什么？ 2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？ 3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？ 4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系？ 5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？ 6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0>+k n x ，其经济意 义是什么？ 7．在线性规划的最优单纯形表中，松弛变量k n x +的检验数0>+k n σ（标准形为 求最小值），其经济意义是什么？ 8．将i j j i b c a ,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化？有多少种不同情况？如何去处理？ 二、判断下列说法是否正确 1．任何线性规划问题都存在且有唯一的对偶问题。 2．对偶问题的对偶问题一定是原问题。 3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。 4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。 5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。 6．已知在线性规划的对偶问题的最优解中，对偶变量 0>*i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。 7．已知在线性规划的对偶问题的最优解中，对偶变量 0=*i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。 8．对于i j j i b c a ,,来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。 9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 u k 。 10．应用对偶单纯形法计算时，若单纯形表中某一基变量0数学建模 对偶问题和灵敏度分析
对偶问题 例题1：某养鸡场所用的混合饲料由n 种天然饲料配合而成。要求在这批配合饲料中必须含有m 种不同的营养成分，且第i 种营养成分的含量不低于bi 。已知第i 种营养成分在每单位第j 种天然饲料中的含量为a ij ，每单位第j 天然饲料的价格为 c j 。试问，应如何对这n 种饲料配方，使这批饲料的费用最小? 解 设x j 为第j 种天然饲料的用量。 显然，a ij x j 即为所用第j 种天然饲料中第i 种营养成分的含量，1n ij j j a x =∑为这批 混合饲料中第i 种营养成分的总含量；它不应低于bi 。于是，我们得下列线性规划模型(1—1)： 1 m i n n j j j f c x ==∑ 1 1,,..01,,n ij j i j j a x b i m s t x j n =?≥=???≥=? ∑ 现设想有一个饲料加工厂欲把这m 种营养成分分别制成m 种营养丸。 设第i 种营养丸的价格为ui(i ＝1，…，m)。则养鸡场采购一个单位的第j 种天然饲料，就相当于对这m 种营养丸分别采购数量a 1j ，…a mj ，所化费用为1m ij i i a u =∑养鸡场自然希望在用营养丸代替天然饲料时，在价格上能相对地比较便宜，故而饲料加工厂为了能与天然饲料供应者竞争，在制订价格时必然满足下述条件： 1 1,,m i j i j i a u c j n =≤=∑ 另一方面，养鸡场如果全部采购营养丸来代替天然饲料进行配料，则第i 种营养丸就需采购bi 个单位，所化费用为b i u i ，总费用为z=∑b i u i 饲料加工厂面临的问题是：应把这m 种营养丸的单价ui(f=1，…，m)定为多少，才能使养鸡场乐意全部采用该厂生产的营养丸来取代这批天然饲料，且使本厂在竞争中得到最大收益。为该问题建立数学模型，即得如下线性规划(1—2)：
§2 对偶与灵敏度分析 §2.1 LP 的对偶问题 无论从理论和实践角度，对偶理论是LP 中的一个最重要和有趣的概念，支持对偶理论的基本思想是：每一个LP 问题都存在一个与其对偶的问题，在求解一个问题解的时候，也同时给出了另一问题的解。 一、问题的提出 例2.1：设某工厂生产两种产品甲乙，生产过程需要4种设备ABCD 进行加工，每件产品加工所需机时数，每件产品的利润值及每种设备的可利用机时如下表： 1.问：充分利用设备时，应怎样安排甲乙产品的生产数量，利润才能最大？ 2.问：如有另外一家公司想租用该厂设备加工生产，那么，这家公司应至少对每台设备的机时价格为多少时，才能使该厂愿意出租设备？ 解：1.设甲乙产品各生产1x 2x 件
LP1：?????? ?≥≤≤+≤++=0 ,1648 212 2232211 21212 1x x x x x x x x x MaxZ 2.设每台设备的机时最低价分别为：1y ，2y ，3y ，4y LP2：??? ??=≥≥++≥+++++=4,3,2,1,03422242121681242 13 214 321i y y y y y y y y y y y MinZ i 二、原问题和对偶问题之间的关系： 1.对称形式下的原问题与对偶问题 对称形式下原问题的一般式： 矩阵形式： ????? ?? ??=≥≤+++≤+++≤++++++=n j x b x a x a x a b x a x a x a b x a x a x a x c x c x c MaxZ j m n mn m m n n n n n n ....... 21,0 (221) 1222221211 12121112211 ???≥≤=0X b AX CX Max 若用i y 代表第i 种资源的估价，则其对偶问题的一般式为： ????? ?? ??=≥≥+++≥+++≥++++++=m j y c y a y a y a c y a y a y a c y a y a y a y b y b y b MinZ j n m mn n n m mn m m m m ....... 21,0 (221) 1222221121 12211112211 ???≥≥=0Y C Y A Yb Min T T ω 2.非对称形式下原问题与对偶问题： 方法一：将非对称形式转化为对称形式，求出对偶问题，然后再还原。
第二章 对偶理论与灵敏度分析练习题答案 1．判断下列说法是否正确： (1) 任何线性规划问题存在并具有惟一的对偶问题；() (2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；() (3) 设j ? x ，i ?y 分别为标准形式的原问题与对偶问题的可行解，* j x ，*i y 分别为其最优解，则恒有n n m m **j j j j i i i i j 1j 1i 1i 1??c x c x b y b y ====≤=≤∑∑∑∑；() (4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；() (5) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0>，说明在最优生产计划中第i 种资源已完全耗尽；() (6) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0=，说明在最优生产计划中第i 种资源一定有剩余；() (7) 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k ；() (8) 应用对偶单纯形法计算时，若单纯形表中某一基变量i x 0<，又x i 所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；() (9) 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；() (10) 在线性规划问题的最优解中，如某一变量x j 为非基变量，则在原来问题中，无论改变它在目标函数中的系数c j 或在各约束中的相应系数a ij ，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。() 2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x 4、x 5为松弛变量。 要求：(1) (3)其它条件不变时，约束条件右端项b 1在何范围内变化，上述最优基不变。(4)若以单价购入第一种资源是否值得，为什么若有人愿意购买第二种资源应要价多少，为什么
数学建模对偶问题和灵敏度分析
对偶问题 例题1：某养鸡场所用的混合饲料由n 种天然饲料配合而成。要求在这批配合饲料中必须含有m 种不同的营养成分，且第i 种营养成分的含量不低于bi 。已知第i 种营养成分在每单位第j 种天然饲料中的含量为a ij ，每单位第j 天然饲料的价格为c j 。试问，应如何对这n 种饲料配方，使这批饲料的费用最小? 解 设x j 为第j 种天然饲料的用量。 显然，a ij x j 即为所用第j 种天然饲料中第i 种营养成分的含量，1n ij j j a x =∑为这批混 合饲料中第i 种营养成分的总含量；它不应低于bi 。于是，我们得下列线性规划模型(1—1)： 1 min n j j j f c x ==∑ 1 1,,..01,,n ij j i j j a x b i m s t x j n =?≥=???≥=? ∑ 现设想有一个饲料加工厂欲把这m 种营养成分分别制成m 种营养丸。 设第i 种营养丸的价格为ui(i ＝1，…，m)。则养鸡场采购一个单位的第j 种天然饲料，就相当于对这m 种营养丸分别采购数量a 1j ，…a mj ，所化费用为1m ij i i a u =∑养 鸡场自然希望在用营养丸代替天然饲料时，在价格上能相对地比较便宜，故而饲料加工厂为了能与天然饲料供应者竞争，在制订价格时必然满足下述条件： 1 1, ,m ij i j i a u c j n =≤=∑ 另一方面，养鸡场如果全部采购营养丸来代替天然饲料进行配料，则第i 种营养丸就需采购bi 个单位，所化费用为b i u i ，总费用为z=∑b i u i
第二章 对偶理论与灵敏度分析练习题答案 1．判断下列说法是否正确： (1) 任何线性规划问题存在并具有惟一的对偶问题；() (2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；() (3) 设j ? x ，i ?y 分别为标准形式的原问题与对偶问题的可行解，*j x ，*i y 分别为其最优解，则恒有n n m m **j j j j i i i i j 1 j 1 i 1 i 1 ??c x c x b y b y ====≤=≤∑∑∑∑；() (4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；() (5) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0>，说明在最优生产计划中第i 种资源已完全耗尽；() (6) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0=，说明在最优生产计划中第i 种资源一定有剩余；() (7) 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k ；() (8) 应用对偶单纯形法计算时，若单纯形表中某一基变量i x 0<，又x i 所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；() $ (9) 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；() (10) 在线性规划问题的最优解中，如某一变量x j 为非基变量，则在原来问题中，无论改变它在目标函数中的系数c j 或在各约束中的相应系数a ij ，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。() 2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x 4、x 5为松弛变量。 X B ｂ x 1 x 2 x 3 x 4 x 5 — x 3 5/2 0 1/2 1 1/2 0 x 1 5/2 1 — -1/2 0 -1/6 1/3 σj 0 -4 0 -4 -2 ; 要求：(1)写出原线性规划问题及其对偶问题的数学模型；(2)直接由表写出对偶问题的最优解； (3)其它条件不变时，约束条件右端项b 1在何范围内变化，上述最优基不变。(4)若以单价购入
作业： 问题1：书本P71第7题 1、设x1 、x2 、x3分别为A产量，B产量，C产量 目标函数：Z=4 x1 +x2 +5x3 约束条件： +3x2 + 5x3<=45 6x 3x1 +4x2 +5x3<=30 x1 、x2 、x3>0 2、A的利润在3~6之间，最优计划不变。 3、设x1 、x2 、x3、x4 分别为A产量，B产量，C产量，D产量 目标函数：Z=4 x1 +x2 +5x3+2.5x4 约束条件： +3x2 + 5x3+3x4<=45 6x 3x1 +4x2 +5x3+2x4<=30 x1 、x2 、x3、x4>0 利润从35增加到37.5，值得生产。 4、见Excel 问题2：某厂拟生产甲、乙、丙三种产品，都需要在A，B两种设备上加工，有关数据如下表所示： （1）如何充分发挥设备能力，使产品总产值最大？ 设x1 、x2 、x3分别为甲产量，乙产量，丙产量 目标函数：Z=3 x1 +2x2 +x3 约束条件： +2x2 + 1x3<=400 x 2x1 +1x2 +2x3<=500 x1 、x2 、x3>0 最优解 甲产量乙产量丙产量 200 100 0 总产值最大800 （2） 200个甲产品在A设备上加工1小时，B设备上加工2小时。
100个乙产品在A设备上加工2小时，B设备上加工1小时。 丙产品不生产。 使得总产值最大为80万。 （3）试分别确定甲产品单位产值、B设备供量各自的影响范围。 甲产品的范围是198~201。 B设备供量的范围是200~800。 （4）若每月能以39万元租金租用外厂B设备300台时，则应否租用？为什么？ 原来的产值为80万，租用外厂之后的产值为120万，则产值增加了40万，而租金要39万，则增加的产值足够支付租金，最后剩余1万，说明能租用。 （5）若每月A设备提供量减少200台时，B设备供量增加100台时，试问最优解与影子价格有何变化？ 最优解是600 影子价格：A设备从0.333~3 ；B设备从1.333~0
线性规划的对偶理论与灵敏度分析习题
1 第二章 线性规划的对偶理论与灵敏度分析习题 1. 写出下列线性规划问题的对偶问题。 (1) ?????? ?≥=++≤++≥++++=无约束 3213213213213 21,0,5343322 43422min x x x x x x x x x x x x x x x z (2) ?????? ?≤≥≤++≥-+-=++++=0 ,0,8374355 22365max 321321321321321x x x x x x x x x x x x x x x z 无约束 (3) ????? ??????==≥=====∑∑∑∑====),,1;,,1(0),,1(),,1(min 1 111 n j m i x n j b x m i a x x c z ij m i j ij n j i ij m i ij n j ij
2 (4) ????? ??????=≥++==<=<=∑∑∑===) ,,,,1(0),,2,1(),,1(min 1 211 111 n n j x m m m i b x a m m i b x a x c z j n j i j ij n j i j ij n j j j 无约束 2. 判断下列说法是否正确，为什么? (1)如果线性规划的原问题存在可行 解，则其对偶问题也一定存在可行解； (2)如果线性规划的对偶问题无可行 解，则原问题也一定无可行解； ( 3)在互为对偶的一对原问题与对偶 问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值； (4)任何线性规划问题具有唯一的对 偶问题。 3. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。 3 2 2 0 0 0
对偶理论与灵敏度分析 对偶问题的提出 对偶理论 影子价格 对偶单纯形法 灵敏度分析
对偶问题的提出 定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题。 应用: 1. 在某些情况下，解对偶问题比解原问题更加容易 2. 对偶变量有重要的经济解释(影子价格) 3. 作为灵敏度分析的工具 4. 对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解) 5. 避免使用人工变量(人工变量带来很多麻烦，两阶段法则增加一倍的计算量) 一、对偶问题的提出 例：某家具厂木器车间生产木门与木窗；两种产品。加工木门收入为56元/扇，加工木窗收入为30元/扇。生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总共时为120小时，油漆工总工时为50小时。 问：(1)该车间应如何安排生产才能使每日收入最大？ (2)假若有一个个体经营者，手中有一批木器家具生产订单。他想利用该木器车间的木工与油漆工来加工完成他的订单。他就要考虑付给该车间每个工时的价格。他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少。 解(1)：设该车间每日安排生产木门x 1扇，木窗x 2扇，则数学模型为 X*=(15,20)’ Z*=1440元 ?? ? ??≥≤+≤++=-0502120343056max 21212121x x x x x x x z
解(2)：设y 1为付给木工每个工时的价格，y 2为付给油工每个工时的价格 Y*=(2,24)’ W*=1440元 将上述问题1与问题2称为一对对偶问题，两者之间存在着紧密的练习与区别：它们都使用了木器生产车间相同的数据，只是数据在模型中所处的位置不同，反映所要表达的含义也不同。 二、L P 和D P 的联系与区别 (1)一个极大化，一个极小化 (2)L P 的价值系数行向量＝(D P 右端项)’ (3)L P 的系数矩阵＝(D P 系数矩阵)’ (4)L P 的右端项＝(D P 的价值系数)’ (5)L P 的约束个数＝D P 的变量个数 (6)L P 的变量个数＝D P 的约束个数 三、原问题与对偶问题的关系 1．对称形式下对偶问题的一般形式 定义：满足下列条件的线性规划问题称为具有对称形式：(1)其变量均为非负约束；(2)其约束条件当目标函数求极大时取“≤”号，当目标函数求极小时取“≥”号；(3)右端项b 可取负值。 ?? ? ??≥≥+≥++=-0303562450120min 2121212 1y y y y y y y w ????? ???????=≥≤+???++???? ??≤+???++≤+???++ +???++=),,1(0max :221122222121112121112211n j x b x a x a x a b x a x a x a b x a x a x a x c x c x c z LP j m n mn m m n n n n n n