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

1、2、对偶理论与灵敏度分析,2.1 线性规划的对偶问题的提出 及其数学模型,例1 生产计划问题（资源利用问题） 胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？,数学模型 max S= 50 x1 + 30 x2 s.t. 4x1 + 3x2 120 (2.1) 2x1 + x2 50 x1,x2 0,如果我们换一个角度，考虑另外一种经营问题

2、。 假如有一个企业家有一批等待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。因此，他要同家具厂谈判付给该厂每个工时的价格。可以构造一个数学模型来研究如何使自己付的租金最少，又使家具厂觉得有利可图肯把资源出租给他？,假设 y1, y2 分别表示每个木工和油漆工工时的租金，则所付租金最小的目标函数可表示为： min s = 120 y1 + 50 y2 目标函数中的系数 120，50 分别表示可供出租的木工和油漆工工时数。,该企业家所付的租金不能太低，否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能得到的利益： 4 y1 + 2y2 50

3、3 y1 + y2 30 y1, y2 0,于是得到数学模型： min g = 120 y1 + 50 y2 s.t. 4 y1 + 2y2 50 (2.2) 3 y1+ y2 30 y1, y2 0,模型(2.1)和模型(2.2) 既有区别又有联系。联系在于它们都是关于家具厂的模型并且使用相同的数据，区别在于模型反映的内容是不同的。模型(2.1)是站在家具厂经营者立场追求销售收入最大，模型(2.2)是则站在家具厂对手的立场追求所付的租金最少。,如果模型(2.1)称为原问题（P）， 则模型(2.2)称为对偶问题（D）。 任何线性规划问题都有对偶问题。 原问题与对偶问题之间没有严格的界限，它们互

4、为对偶。,例1.1,例1.2,(P),(D),原问题与对偶问题： P（D） D（P） 目标函数系数 c 右端常数项 b 系数矩阵 A 系数矩阵 A,约束条件 变量,T,（个数）,（符号）,对称形式的对偶关系,（1）若原问题是,这两个式子的变换关系称为“对称形式的对偶关系”。,(2) 其对偶问题为,(P),(D),怎样写出非对称形式的对偶问题？ 根据对应规律（参见对偶关系表）直接写出；,例1：写出下列线性规划问题的对偶问题 min S = x1 + 2x2 + 3x3 s.t. 2x1+3x2 + 5x3 2 3x1+ x2 + 7x3 3 x1，x2 ， x3 0,该问题的对偶问题： max

5、z = 2 y1 + 3y2 s.t. 2y1+3y2 1 3y1+ y2 2 5y1+7y2 3 y1 0， y2 0,例2：写出下列线性规划问题的对偶问题 min S = 2x1 + 3x2 - 5x3 s.t. x1+ x2 - x3 5 2x1 + x3 = 4 x1，x2 ， x3 0,该问题的对偶问题为： max z = 5 y1 + 4y2 s.t. y1 + 2y2 2 y1 3 -y1+ y2 -5 y1 0 ，y2 无非负约束,练习1：写出下列线性规划问题的对偶问题 min S = 3x1 - 2x2 + x3 s.t. x1+2x2 = 1 2x2 - x3 -2 2x1

6、 +x3 3 x1- 2x2 + 3x3 4 x1，x2 0 ， x3 无非负限制,练习2、已知下表为求解某线性规划问题的最终单纯形表，表中x4、x5为松弛变量。试： （1）写出线性规划原问题。 （2）写出对偶问题。 （3）求对偶问题的最优解。,练习1答案 解: 对偶问题为： max z = 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

7、.2 对偶问题的基本定理,定理1、对称性定理： 对偶问题的对偶是原问题。,定理2、弱对偶定理（弱对偶性）：设 和 分别是问题（P）和（D）的可行解，则必有,例1、,试验证弱对偶性原理。,（P）,解：,（D）,由观察可知： =（1.1.1.1）， =（1.1），分别是 （P）和（D）的可行解。 =10 ， =40，故有 ，弱对偶定理成立。,推论: 若 和 分别是问题（P）和（D）的 可行解，则 是（D）的目标函数最小值的一个下界； 是（P）的目标函数最大值的一个上界。,定理2,由观察可知： =（1.1.1.1）， =（1.1），分别是（P）和（D）的可行解。CX=10 ，Yb=40。 由推论可知

8、，W 的最小值不能小于10，Z 的最大值不能超过40。,定理5、对偶性,. P有最优解的充要条件是D有最优解。,.若 X* 和 Y* 分别是 P 和 D 的可行解，则它们分别是P和D 的最优解的充要条件是 CX* = Y* b。,若原问题和对偶问题都有可行解,则它们都有最优解。,最优性判别定理： 若 X* 和 Y* 分别是 P 和 D 的可行解且 CX* = Y*b，则X*、Y*分别是问题 P和D 的最优解。,定理4、最优性,若原问题有最优解,则对偶问题也一定有最优解，且目标函数值相等。,思考：根据定理4如何判断 原问题有（或者没有）最优解？,定理3 无界性：在一对对偶问题（P）和（D）中，若

9、其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。,无界,如：,（P）,例2、已知,显然，这两个问题都无可行解。,推论：在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行，（如D），则该可行的问题无界。,练习：（1）,试用对偶性质证明原问题无界。,解： =（0.0.0）是 P 的一个可行解，而 D 的第一个约束条件不能成立（因为y1 , y2 0)。因此，对偶问题不可行，由定理3推论可知，原问题无界。,练习：试用对偶理论讨论下列原问题是否有最优解？,（1）,（2）,答案：（1）无最优解（无界解） （2）有最优解,综上所述，一对对偶问题的关系，只能有下面三种情况之一

10、出现： .若 P 和 D 的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等，即有CX* =Y*b； . 一个问题无界，则另一个问题无可行解； .两个都无可行解。,对偶性质定理总结：,定理2弱对偶定理：,判断原问题（对偶问题）目标函数值的上界（下界）。,定理3、4、5：,判断原问题（对偶问题）有无最优解。,定理6互补松弛性定理：,根据原问题（或对偶问题）最优解，直接求出 对偶问题（或原问题）的最优解。,判断原问题（对偶问题）解的两种对应关系。,定理6、互补松弛定理：,在线性规划的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；另外，如果约束条件取严格不等式

11、，则其对应的对偶变量为零。,互补松弛定理（松紧定理）描述了线性规划问题达到最优时，一个问题的变量 和另一个问题约束的松紧性之间的对应关系：,如果一个问题的某一变量不等于0,则对应的另一个问题的约束一定取严格等式(紧约束) ；如果一个问题的某一约束取严格不等式(松约束),则对应的另一个问题的变量一定为0。,互补松弛定理：,在线性规划问题的最优解中： P（D） D（P） 约束条件（或）， 则变量=0。 变量0， 则约束条件（=）。,例3：见教材p20,y*=(4/5,3/5) Z*=5,练习1、已知原问题的最优解为X* =（50/7，200/7）T，Z*=4100/7 试求对偶问题的最优解。,解：

12、,将X* =（50/7，200/7）T代入原问题中，有：,所以，根据互补松弛条件，必有y*1=0;又因为x1*、x2*0，因此，两个对偶约束取等号，联立方程得到最优解为： Y*=（0，32/7，6/7），W*=4100/7。,(1) (2) = (3) =,练习2、已知原问题的最优解为X* =（2，2，4，0）T，试求对偶问题的最优解。,答案：y*=(4/5, 3/5, 1, 0),练习3： 已知线性规划问题如下，其最优解为 X*=（-5，0，-1）T，最优值Z*= -12，请求出k值，写出对偶问题的数学模型，并求出对偶问题的最优解。,X*=（-5，0，-1）T 最优值Z*= -12,答案：Y

13、*=（0，-2） k=1,例4、已知,试通过求对偶问题的最优解来求解原问题的最优解。,解：对偶问题为,用图解法求出： Y*=（1 . 3）， W=11。,(1 . 3),（1）,（2）,（3）,（4）,（5）,将y*1=1， y*2=3 代入对偶约束条件， （1）（2）（5）式为紧约束，（3）（4）为松约束。 则根据互补松弛条件，必有x*3 = x*4 =0,又由于y*1=10， y*2 =30，原问题的约束必为等式，即,化简为,此方程组为无穷多解,令x5 =0,得到x1=1，x2=2 即X*1 =（1.2.0.0.0）T为原问题的一个最优解，Z=11。,再令 x5 =2/3，得到x1=5/3

14、，x2=0 即X*2 =（5/3.0.0.0.2/3）T也是原问题的一个最优解，Z=11。,定理7、,若原问题P与对偶问题D分别如下：,则原问题单纯形表中检验数的相反数对应其对偶问题的一个基本可行解。,例5、,初 始 表,最终表,由上表可知： X*=（50/7 . 200/7）T，Z*=4100/7 对偶问题的最优解： Y*=（0 . 32/7 . 6/7），W*=4100/7,检验数3 =0，4 =-32/7, 5 =-6/7,对偶最优解是原问题松弛变量对应的检验数的相反数。,练习、已知下表为求解某线性规划问题的最终单纯形表，表中x4、x5为松弛变量，问题的约束为。试： （1）写出线性规划原

15、问题。 （2）写出对偶问题。 （3）求对偶问题的最优解。,练习：利用定理7求下面线性规划问题的对偶最优解。,用表格单纯形法求解如下：,X*=(1, 2, 0, 0, 0)T Y*=(5/3, 1/3, 0, 0, 1),对偶性质定理总结：,定理2弱对偶定理：,判断原问题（对偶问题）目标函数值的上界（下界）。,定理3、4、5：,判断原问题（对偶问题）有无最优解。,定理6互补松弛性定理：,根据原问题（或对偶问题）最优解，直接求出 对偶问题（或原问题）的最优解。,定理7：,根据原问题单纯形表可直接得到对偶问题的 基本可行解。,判断原问题（对偶问题）解的两种对应关系。,2.4 对偶问题的经济解释,影子

16、价格,什么是影子价格？,根据公式推导有：,对于生产计划问题（原问题）而言，bi是线性规划原问题约束条件右端项，它代表第i种资源的拥有量； 表示Z*对bi的变化率。即在资源最优利用条件下，对单位第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中所作的贡献而作的估价，为区别起见，称为影子价格。,对偶最优解y*i 就是第 i 种资源（约束条件）的影子价格。,影子价格的特点： （1）影子价格的大小反映了资源的稀缺与富有程度。 如果某一资源影子价格大于0，说明该资源是稀缺资源；而且影子价格越高，该资源在系统内越稀缺。为了提高总利润，就应该优先增加影子价格高的资源。 系统内有剩余资源时，影

17、子价格为0，该资源不应再继续购买添加，增加该资源不会使总利润进一步增加。,（2）影子价格是一种边际价格。它是在资源得到最优利用的生产条件下，资源每增加一个单位时，目标函数的增加量。 （3）影子价格是对系统资源的一种最优估价。 （4）影子价格是一种动态价格，其值与系统状态有关。系统内部资源数量（b）、技术系数（A）和价格（C）的变化，都有可能引起影子价格的变化。,练习题： 1、已知某工厂计划生产A1、A2、A3三种产品，各产品需要在甲、乙、丙设备上加工。具体数据如下表。问： （1）制定月生产计划，充分发挥设备能力，使工厂获利最大？ （2）若为了增加产量，可借用别的工厂设备甲，每月可借用10小时，

18、租金3000元，问是否合算？并解释原因。 （3）增加设备乙的台时是否可使企业总利润进一步增加？,（1）建立线性规划模型,X1 X5 X6,1、答案： （2）合算.因为 10*（3/8）千元3千元 . （3）不会.因为 设备乙的影子价格为0.,例 加工奶制品的生产计划,问题 一奶制品加工工厂用牛奶生产A1，A2两种奶制品，一桶牛奶可以在设备甲上用12个小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2，根据市场需求，生产的A1，A2全部能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加

19、工100公斤A1，设备乙的加工能力没有限制。试为该厂制定一个生产计划，使每天获利最大。,用x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(1),生产：x1公斤A1,x2公斤A2,获利 24x1,获利 16 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(2),模型（1）：,结果说明： 1、 x*1=20，x*2=30，最优值z*=3360； 即用20桶牛奶生产A1 60公斤，30桶牛奶生产A2 120公斤，可获最大利润3

20、360元。,2、原问题松弛变量: x3*=0,x4*=0,x5*=40,3、影子价格（对偶最优解）: y1*=48,y2*=2,y3*=0,进一步讨论： （1）若用35元可以买到1桶牛奶，应否作这项投资？ （2）若可以聘临时工以增加劳动时间，付给临时工的工资最多是每小时几元？,2.5 灵敏度分析,“灵敏度分析”（Sensitivity Analysis)， 是对系统因周围条件的变化显示出来的敏感性程度的分析。,线性规划问题灵敏度分析主要关注的是：,当初始参数（如：cj或bi)发生变化时，最优基、最优解、最优值、检验数会怎样变化？,初始参数在什么范围内变化时，最优解性质会保持不变。,当某个初始参数cj在一定范围内变动时，最优基不变