运筹学第1章 5对偶理论与灵敏度分析.ppt

2、对偶理论与灵敏度分析如果我们换一个角度，考虑另外一种经营问题。假如有一个企业家有一批等待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。因此，他要同家具厂谈判付给该厂每个工时的价格。可以构造一个数学模型来研究如何使自己付的租金最少，又使家具厂觉得有利可图肯把资源出租给他？假设y1,y2分别表示每个木工和油漆工工时的租金，则所付租金最小的目标函数可表示为：
mins=120y1+50y2
目标函数中的系数120，50分别表示可供出租的木工和油漆工工时数。该企业家所付的租金不能太低，否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能得到的利益：
4y1+2y250
3y1+y230
y1,y20于是得到数学模型：
ming=120y1+50y2
s.t.4y1+2y250(2.2)
3y1+y230
y1,y20模型(2.1)和模型(2.2)既有区别又有联系。联系在于它们都是关于家具厂的模型并且使用相同的数据，区别在于模型反映的内容是不同的。模型(2.1)是站在家具厂经营者立场追求销售收入最大，模型(2.2)是则站在家具厂对手的立场追求所付的租金最少。如果模型(2.1)称为原问题（P），
则模型(2.2)称为对偶问题（D）。
任何线性规划问题都有对偶问题。

原问题与对偶问题之间没有严格的界限，它们互为对偶。例1.1对称形式的对偶关系怎样写出非对称形式的对偶问题？

根据对应规律（参见对偶关系表）直接写出；原问题（或对偶问题）例1：写出下列线性规划问题的对偶问题

minS=x1+2x2+3x3
s.t.2x1+3x2+5x32
3x1+x2+7x33
x1，x2，x30该问题的对偶问题：

maxz=2y1+3y2
s.t.2y1+3y21
3y1+y22
5y1+7y23
y10，y20例2：写出下列线性规划问题的对偶问题

minS=2x1+3x2-5x3
s.t.x1+x2-x35
2x1+x3=4
x1，x2，x30
该问题的对偶问题为：
maxz=5y1+4y2
s.t.y1+2y22
y13
-y1+y2-5
y10，y2无非负约束
练习1：写出下列线性规划问题的对偶问题

minS=3x1-2x2+x3
s.t.x1+2x2=1
2x2-x3-2
2x1+x33
x1-2x2+3x34
x1，x20，x3无非负限制
练习2、已知下表为求解某线性规划问题的最终单纯形表，表中x4、x5为松弛变量。试：
（1）写出线性规划原问题。
（2）写出对偶问题。
（3）求对偶问题的最优解。练习1答案
解:对偶问题为：

maxz=y1-2y2+3y3+4y4
s.t.y1+2y3+y43
2y1+2y2-2y4-2
-y2+y3+3y4=1
y20，y3,y40，y1无非负约束练习2答案：（1）先求出C1=6,C2=-2,C3=10;再求出初始单纯形表(A|b)矩阵.于是原问题为：

2.2对偶问题的基本定理

定理1、对称性定理：

对偶问题的对偶是原问题。定理2、弱对偶定理（弱对偶性）：设和分别是问题（P）和（D）的可行解，则必有例1、解：推论:若和分别是问题（P）和（D）的

可行解，则是（D）的目标函数最小值的一个下界；是（P）的目标函数最大值的一个上界。由观察可知：=（1.1.1.1），=（1.1），分别是（P）和（D）的可行解。CX=10，Yb=40。
由推论可知，W的最小值不能小于10，Z的最大值不能超过40。定理5、对偶性思考：根据定理4如何判断
原问题有（或者没有）最优解？定理3无界性：在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。

关于无界性有如下结论：例2、已知推论：在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行，（如D），则该可行的问题无界。练习：（1）练习：试用对偶理论讨论下列原问题是否有最优解？综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：
①.若P和D的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等，即有CX*=Y*b；
②.一个问题无界，则另一个问题无可行解；
③.两个都无可行解。对偶性质定理总结：定理6、互补松弛定理：
互补松弛定理：
例3：见教材p20练习1、已知原问题的最优解为X*=（50/7，200/7）T，Z*=4100/7试求对偶问题的最优解。
解：将X*=（50/7，200/7）T代入原问题中，有：练习2、已知原问题的最优解为X*=（2，2，4，0）T，试求对偶问题的最优解。
练习3：已知线性规划问题如下，其最优解为
X*=（-5，0，-1）T，最优值Z*=-12，请求