[经济学]第二章new 对偶理论与灵敏度分析ppt课件

1、Chapter 2对偶实际与灵敏度分析对偶实际与灵敏度分析上海工程技术大学上海工程技术大学管理学院管理学院Chapter 2 灵敏度分析灵敏度分析 对偶问题提出对偶问题提出问题一：某公司在方案期内要安排消费问题一：某公司在方案期内要安排消费I、 II两种产两种产品，知消费单位产品所需的设备台时及品，知消费单位产品所需的设备台时及A B两种两种原资料的耗费如表所示，该工厂每消费一件产品原资料的耗费如表所示，该工厂每消费一件产品I可获利可获利2元，每消费一件产品元，每消费一件产品II可获利可获利3元，问应元，问应该如何安排方案使该工厂获利最多？该如何安排方案使该工厂获利最多？ 如何安排方案？如何安

2、排方案？举例Chapter 2 灵敏度分析灵敏度分析 先根据图表来列出模型 Max Z= 2X1+3X2 X1+2X2 8 4X1 16 4X2 12 X1, X2 0 举例我们从另一个角度来讨论这个问题我们从另一个角度来讨论这个问题.假设该工假设该工厂的决策者决议不消费产品厂的决策者决议不消费产品I II，而将其一，而将其一切资源出租或外售切资源出租或外售.这时工厂的决策者就要这时工厂的决策者就要思索给每种资源如何定价的问题思索给每种资源如何定价的问题.设用设用Y1, Y2, Y3分别表示出租单位设备台时的租金分别表示出租单位设备台时的租金和出让单位原资料和出让单位原资料A,B的附加额的附加

3、额.从工厂决策者的角度来看从工厂决策者的角度来看f f当然是越大越好当然是越大越好, ,但从接受者目光来说但从接受者目光来说f f是越少越好是越少越好, ,所以工所以工厂决策者只可以在满足厂决策者只可以在满足 一切产品的利一切产品的利润条件下润条件下, ,使其总收入尽能够的小使其总收入尽能够的小. .因此可因此可以列出如下线性规划问题以列出如下线性规划问题 min f= min f= 8Y1+16Y2+12Y38Y1+16Y2+12Y3 Y1+4Y2 2Y1+4Y2 2 2Y1+4Y3 32Y1+4Y3 3 Yi 0, Yi 0, i = 1,2,3 i = 1,2,3 Chapter 2 灵

4、敏度分析灵敏度分析v 各模型中有关数据的各模型中有关数据的“位置表示图如下。位置表示图如下。 v由上面的例子我们可以知道原问题与由上面的例子我们可以知道原问题与对偶问题的关系对偶问题的关系v1线性规划问题是对称方式线性规划问题是对称方式v Max z = CX Min f = Ybv s.t. Ax b s.t. YA cv x 0 y 0 v “Max - “Min- 0,5 64 3 7 32532432max32132132132321xxxxxxxxxxxxxxxZ 0,4675343232 532min 321321321321321yyyyyyyyyyyyyyyW对对偶偶问问题题：

5、Chapter 2 灵敏度分析灵敏度分析v如上面例题所示一对对称方式的对偶规划如上面例题所示一对对称方式的对偶规划之间具有下面的对应关系之间具有下面的对应关系v(1)假设一个模型为目的求假设一个模型为目的求“极大，约束为极大，约束为“小于等于的不等式，那么它的对偶模型小于等于的不等式，那么它的对偶模型为目的求为目的求“极小，约束是极小，约束是“大于等于的大于等于的不等式。即不等式。即“max，和和“min，相对应。相对应。(2)从约束系数矩阵看：一个模型中为，那从约束系数矩阵看：一个模型中为，那么另一个模型中为么另一个模型中为AT。一个模型是。一个模型是m个约个约束，束，n个变量，那么它的对偶

6、模型为个变量，那么它的对偶模型为n个约个约束，束，m个变量。个变量。(3)从数据从数据b、C的位置看：在两个规划模型中，的位置看：在两个规划模型中，b和和C的位置对换。的位置对换。(4)两个规划模型中的变量皆非负。两个规划模型中的变量皆非负。Chapter 2 灵敏度分析灵敏度分析v然而在普通线性规划问题中遇到非对称方然而在普通线性规划问题中遇到非对称方式时我们的处置如下：式时我们的处置如下：v 非对称方式的对偶规划非对称方式的对偶规划普通称不具普通称不具有对称方式的一对线性规划为非对称方式有对称方式的一对线性规划为非对称方式的对偶规划。的对偶规划。v对于非对称方式的规划，可以按照下面的对于非

7、对称方式的规划，可以按照下面的对应关系直接给出其对偶规划。对应关系直接给出其对偶规划。v1将模型一致为将模型一致为“max，或或“min， 的方式，对于其中的等式约束按下面的方式，对于其中的等式约束按下面2、3中的方法处置；中的方法处置；2假设原规划的某个约束条件为等式约束，假设原规划的某个约束条件为等式约束，那么在对偶规划中与此约束对应的那个变那么在对偶规划中与此约束对应的那个变量取值没有非负限制；量取值没有非负限制；3假设原规划的某个变量的值没有非负限假设原规划的某个变量的值没有非负限制，那么在对偶问题中与此变量对应的那制，那么在对偶问题中与此变量对应的那个约束为等式。个约束为等式。Cha

8、pter 2 灵敏度分析灵敏度分析v非对称型对偶问题非对称型对偶问题 0XbAX max CXZP矩矩阵阵形形式式： 无无符符号号限限制制（无无约约束束） min YCYAYbWDChapter 2 灵敏度分析灵敏度分析举例 0,5643732532432max321321321321321xxxxxxxxxxxxxxxZ Chapter 2 灵敏度分析灵敏度分析 无无约约束束解解：对对偶偶问问题题为为 ,467534 3 2 32 532min 321321321321321yyyyyyyyyyyyyyyW原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函

9、数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量0 00= =无约束无约束变变量量n个个n个个约约束束条条件件0 00 0无约束无约束= =约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项Chapter 2 灵敏度分析灵敏度分析 小练习写出以下问题的对偶问题写出以下问题的对偶问题Chapter 2 灵敏度分析灵敏度分析对偶问题的根本性质对偶问题的根本性质 性质性质1:对称性对称性规范原始，对偶问题的对偶是原问题。规范原始，对偶问题的对偶是原问题。 Max z = CX Min f =

10、Yb s.t. AX b s.t. YA C X 0 Y 0 “Max - “Min- Chapter 2 灵敏度分析灵敏度分析性质性质2:2:弱对偶原理弱对偶性：设弱对偶原理弱对偶性：设 和和 分别是分别是 问题问题P P和和D D的可行解，那么必有的可行解，那么必有_X_Y njmiiijjbyxcbYXC11_ , 即即性质性质3:无界性无界性假设原问题对偶问题的解为无界解，那假设原问题对偶问题的解为无界解，那么其对偶问题原问题无可行解。无么其对偶问题原问题无可行解。无界性界性性质性质4:可行解是最优解的性质：可行解是最优解的性质：假设假设 X* 和和 Y* 分别是分别是 P 和和 D

11、的可行解且的可行解且 CX* = Y* b，那么那么X*. Y*分别是问题分别是问题 P和和D 的最优解。的最优解。Chapter 2 灵敏度分析灵敏度分析性质性质5:5:对偶定理对偶定理假设原问题有最优解，那么对偶问题也有最假设原问题有最优解，那么对偶问题也有最优解，而且二者最优值相等。强对偶性优解，而且二者最优值相等。强对偶性性质性质6:6:互补松弛定理互补松弛定理设设X X* *和和Y Y* *分别是问题分别是问题 P P 和和 D D 的可行解，那的可行解，那么它们分别是最优解的充要条件是么它们分别是最优解的充要条件是剩剩余余变变量量或或或或ssssYXXYXCAYXYAXbY.00)

12、(00)( 同时成立同时成立Chapter 2 灵敏度分析灵敏度分析例题判别下例说法能否正确，为什么？例题判别下例说法能否正确，为什么？ A 假设线性规划的原问题存在可行解，那么其假设线性规划的原问题存在可行解，那么其对偶对偶 问题也一定存在可行解问题也一定存在可行解 B 假设线性规划的对偶问题无可行解，那么原假设线性规划的对偶问题无可行解，那么原问题也一定无可行解。问题也一定无可行解。 C 在互为对偶的一对原问题和对偶问题中，不在互为对偶的一对原问题和对偶问题中，不论原问题是求极大或者极小，原问题可行解的目论原问题是求极大或者极小，原问题可行解的目的函数值都一定不超越其对偶问题可行解的目的的

13、函数值都一定不超越其对偶问题可行解的目的函数值。函数值。 Chapter 2 灵敏度分析灵敏度分析v解：解：vA不对。由于原问题为无界解时它当然有可行不对。由于原问题为无界解时它当然有可行解，其对偶问题无可行解。解，其对偶问题无可行解。vB此句为此句为A的逆否命题，所以也不对。的逆否命题，所以也不对。vC不对。由于哪个问题是原问题，哪个问题是对不对。由于哪个问题是原问题，哪个问题是对偶问题是相对而言的。偶问题是相对而言的。 Chapter 2 灵敏度分析灵敏度分析例题例题: :知原问题的最优解为知原问题的最优解为X X* * = =0,0,40,0,4，Z=12,Z=12,试求对偶问题的最优解

14、。试求对偶问题的最优解。 无无约约束束321321321321321,0,04 16 3253234maxxxxxxxxxxxxxxxxZChapter 2 灵敏度分析灵敏度分析 无无约约束束321321321321321,0,03654 3 132 42minyyyyyyyyyyyyyyyW解解: :将将X X* * = =0 , 0 , 40 , 0 , 4代入原问题中，有下式：代入原问题中，有下式：Chapter 2 灵敏度分析灵敏度分析 4 4 1 246 32 20532321321321xxxxxxxxx所以，根据互补松弛条件，必有所以，根据互补松弛条件，必有y y* *1= y1

15、= y* *2=02=0，代入对偶问题代入对偶问题 3 3式，式， y3 =3 y3 =3。因此，对偶。因此，对偶问题的最优解为问题的最优解为 Y Y* *= =0 . 0 . 30 . 0 . 3，W=12W=12。第二节第二节 影子价钱影子价钱Chapter 2 灵敏度分析灵敏度分析第三节第三节 对偶单纯形法对偶单纯形法对偶单纯形法是求解线性规划的另一的对偶单纯形法是求解线性规划的另一的根本方法。它是根据对偶原理和单纯根本方法。它是根据对偶原理和单纯形法的原理而设计出来的，因此称为形法的原理而设计出来的，因此称为对偶单纯形法。对偶单纯形法并不是对偶单纯形法。对偶单纯形法并不是求解对偶问题解

16、的方法，而是利用对求解对偶问题解的方法，而是利用对偶实际求解原问题的解的方法。偶实际求解原问题的解的方法。由单纯形方法，我们可以得到，由单纯形方法，我们可以得到，LPLP问题问题的最优解应该是可行的；的最优解应该是可行的； 最优的；最优的；由对偶性可知，由对偶性可知， LP LP问题的最优性相当问题的最优性相当于于DLPDLP的可行性，的可行性， LP LP问题的可行性相问题的可行性相当于当于DLPDLP的最优性的最优性. .(3) 对偶单纯形法因此单纯形方法可以解释为它是在坚持一个原因此单纯形方法可以解释为它是在坚持一个原始问题可行解的前提下，向对偶可行解的方向始问题可行解的前提下，向对偶可

17、行解的方向迭代迭代. .原始算法原始算法我们可以从一个对偶可行解开场，坚持对偶问我们可以从一个对偶可行解开场，坚持对偶问题的可行性，向原始可行解的方向迭代题的可行性，向原始可行解的方向迭代 对偶单纯形法对偶单纯形法0jjjzc01bBb对偶问题的可行解对偶问题的可行解对偶问题对偶问题最优解判别最优解判别 也就是说，求解原问题也就是说，求解原问题P P时，可以从时，可以从P P的一的一个根本解非基可行解开场，逐渐迭代，使目的函个根本解非基可行解开场，逐渐迭代，使目的函数值数值Z=Y b= CB B-1b =CXZ=Y b= CB B-1b =CX减少，当迭代到减少，当迭代到XB=B-1b0XB=

18、B-1b0时，即找到了时，即找到了P P的最优解，这就是对偶的最优解，这就是对偶单纯形法。单纯形法。 同原始单纯形求法一样，求解对偶问题同原始单纯形求法一样，求解对偶问题D D，也可，也可以从以从D D的一个根本可行解开场，从一个根本可行解的一个根本可行解开场，从一个根本可行解迭代到另一个根本可行解，使目的函数值减少。迭代到另一个根本可行解，使目的函数值减少。4 对偶单纯形法对偶单纯形法对偶单纯形法的根本思绪是：对偶单纯形法的根本思绪是： 在迭代过程中，一直坚持对偶问题解的可行性，而原问题的解由不可行逐渐向可行性转化，一旦原问题的解也满足了可行性条件,也就到达了最优解。也即在坚持正那么解的正那

19、么性不变条件下，在迭代过程中，使原问题解的不可行性逐渐消逝，一旦迭代到可行解时，即到达了最优解。v这样的优点在于，这样的优点在于，v一是当问题的模型中存在一是当问题的模型中存在“=的约束条件时，的约束条件时，不需求引入人工变量，只需在约束条件方程的两不需求引入人工变量，只需在约束条件方程的两边乘以边乘以“-1后参与松弛变量，再按单纯形法求解。后参与松弛变量，再按单纯形法求解。v二是当约束条件方程个数二是当约束条件方程个数m大于变量个数大于变量个数n的时候，的时候，将原问题变换成对偶问题求解，计算量普通会小将原问题变换成对偶问题求解，计算量普通会小些。些。Chapter 2 灵敏度分析灵敏度分析

20、对偶单纯形法求解线性规划问题过程：对偶单纯形法求解线性规划问题过程： 1.建立初始对偶单纯形表建立初始对偶单纯形表,对应一个根本解对应一个根本解,一切检验数均非正一切检验数均非正 ,转转2； 2.假设假设b0,那么得到最优解那么得到最优解,停顿停顿; 3.假设有假设有bi0,换出变量：设换出变量：设minbi|bi0=bk,，那么选，那么选k行行的基变量为换出变量的基变量为换出变量,转转40j 4. 4.假设一切假设一切akj0( j = akj0( j = 1,2,n )1,2,n )，那么原问题无可行解，那么原问题无可行解, ,停停顿顿; ;否那么否那么, ,假设有假设有akj0 akj0

21、 那么选那么选 =min=min j / j / akjakj0=akjakj0brMin-bi/airair0Chapter 2 灵敏度分析灵敏度分析例题: Max z = 2x1 + 3x2 + 0 x3 + 0 x4+ 0 x5 s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0Chapter 2 灵敏度分析灵敏度分析C i23000CBX BBX 1X 2X 3X 4X 52 X 141001 /400 X 5400-21 /213 X 22011 /2-1 /80j00-1 .5-1

22、/80最终单纯形表为最终单纯形表为: 0 0.25 0 这里 B-1 = -2 0.5 1 0.5 -0.125 0 各列分别对应各列分别对应 b1 b1、b2b2、b3 b3 的单一变化的单一变化因此，设因此，设 b1 b1 添加添加 4 4，那么，那么 x1 ,x5 ,x2 x1 ,x5 ,x2分别变为：分别变为：4+04+04=4, 4+(-2)4=4, 4+(-2)4=-40, 2+0.54=-40asj0 csMincsMin j/asjj/asjasj0 asj0 v Chapter 2 灵敏度分析灵敏度分析例题例题: : Max z = 2x1 + 3x2 + 0 x3 + 0

23、x4+ 0 x5 Max z = 2x1 + 3x2 + 0 x3 + 0 x4+ 0 x5 s.t. x1 + 2x2 + x3 = 8 s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x1 + x4 = 16 4x2 + x5 = 12 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0 x1 , x2 , x3 , x4 , x5 0下表为最优单纯形表下表为最优单纯形表,思索基变量系数思索基变量系数c2发生变化发生变化 Chapter 2 灵敏度分析灵敏度分析C i23000CBXBBX1X2X3X4X52 X141001/400 X

24、5400-21/213 X22011/2-1/80j00-1.5-1/80Ci23+ C2000CBXBBX1X2X3X4X52 X141001/400 X5400-21/213+ C2 X22011/2-1/80j00-1.5 - C2/2-1/8+ C2/80从表中可得到从表中可得到 -3c21 -3c21时，原最优解时，原最优解不变。不变。例：某企业利用三种资源消费两种产品的最优方案例：某企业利用三种资源消费两种产品的最优方案问题归结为以下线性规划问题归结为以下线性规划 0,45 802903 45 max2121212121xxxxxxxxxxZ知最优表如下。知最优表如下。1 1确定确

25、定x2x2的系数的系数c2c2的变化范围，使原最优的变化范围，使原最优解坚持最优；解坚持最优；2 2假设假设c2=6c2=6，求新，求新的最优方案。的最优方案。 一、 价值系数cj的变化分析cj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12000-1-3 0,45 802903 45 max2121212121xxxxxxxxxxZ4 = c25 05 = 52c2 0 5/2 c2 5cj5c2 000CBXBbx1x2x3x4x50 x3250012-55x1351001-1c2 x2 10 010-12000c2 - 55 - 2c2最优解最优解X X* *= =3535，1010，2525，0 0，0 0坚