三节对偶与灵敏度分析ppt课件

1、 对偶问题与灵敏度分析一、对偶问题及其模型问题的提出0,3001032005436049. .21212121xxxxxxxxts21127xxMaxz乙甲油电煤 这时有另一家厂商提出要购买其煤、电、油全部资源，并希望破费尽量少。试建立购买者的线性规划模型。则总花费为分别为的价格解：设其购买三种资源,321wyyy0,5449.21212133312107 3yyyyyyyyyts321300200360yyyMinw油电煤 乙甲原问题原问题, ,记为记为P P对偶问题对偶问题, ,记为记为D D对偶模型的普通式对偶模型的普通式则对偶问题为，记),(321yyyY以例1为例，原问题为0.XbA

2、XtsCXzmaxP0. .minYCYAt sYbwD这是最常见的对偶模型方式，称为对称式对偶模型。二者间具有非常对称的对应关系： 原问题P 对偶问题 D 目的max型 目的min型 有n个变量非负 有n个约束大于等于 有m个约束 小于等于 有m个变量非负 价钱系数 资源向量 资源向量 价钱系数 技术系数矩阵 技术系数矩阵的转置此外，还有一种情形此外，还有一种情形 原问题P 对偶问题 D 第j个变量为自在变量 第j个约束为等式约束 第i个约束为等式约束 第i个变量为自在变量例：写出下面线性规划的对偶规划模型：0135232. .32max121212121xxxxxxxtsxxz则对偶目标为

3、解：设对偶变量为,321wyyy0,322.5321321321321yyyyyyyytsyyyw32min写出下面线性规划的对偶规划模型：4321432maxxxxxz0,2023220322432143214321xxxxxxxxxxxx321635maxxxxz无约束321321322321,0,101632182xxxxxxxxxxxx32122minxxxz无约束321321321, 0, 064xxxxxxxxx0,64321321321xxxxxxxxx32122minxxxz练习：写出下面LP的对偶43214532minxxxxz无约束43214324314321, 0, 06

4、42253. .xxxxxxxxxxxxxxts其对偶模型为：321645maxyyyw无约束3213213213121,0,4523322.yyyyyyyyyyyyyts二、对偶的性质0.XbAXtsCXzmaxP0.YCYAtsYbzminD思索1 .1 .对称性对称性 P P与与D D互为对偶。互为对偶。证：X,Y分别为(P)、(D)的可行解，由约束条件可得几何意义：CXYb2. 2.弱对偶性弱对偶性 YbCXDP的可行解，则，分别是，设YXbAX CYA YbYAX CXYAX YbYAXCXYbCX 由此可以推出：由此可以推出：假设假设(P)(P)为无界解，那么为无界解，那么(D)(

5、D)无可行解无可行解假设假设(D)(D)为无界解，那么为无界解，那么(P)(P)无可行解无可行解例 设线性规划问题1 ， 是其对偶问题的最优解；CXz 1maxY0.XbAXts又设线性规划问题2 ，其中k是知的常向量；CXz2max0.XkbAXts求证：kYzz*12maxmax0. 0. 2121YCYAtsYCYAtsYkYbMinwYbMinw）（）（的对偶问题分别是与问题证：问题由(I)和(II)的约束一样，故(I)的最优解 为(II)的可行解。Y由弱对偶性， ，由解的最优性 ，得证kYbYz*2max1max zbY3. 3. 解的最优性解的最优性., ,)D(P)(YYXXbY

6、XCYX则的可行解，且与分别是与若.XCbYCXX，由弱对偶性，证：对任可行解.YYXX同理，故4. 4. 对偶定理对偶定理 假设假设(P)(P)有最优解，那么有最优解，那么(D)(D)也有最优解，且二也有最优解，且二者最优值相等者最优值相等证：对P添加松弛变量Xs，化为0,. .ssXXbIXAXtsCXMaxz设其最优基为B，终表为sXXC 0 IBAB11 1bBCBIBCABCCBB110 00011IBCABCCBsB其检验数为满足则取YBCYB,10YCAYzbBCbYYB1D）的可行解，且是（即.3YY，由性质问题：(1) 由性质4可知，对偶问题最优解的表达式 Y* =？ (2)

7、 求Y*能否有必要重新求解 D？ CBB-1 不用。可以从原问题P的单纯形终表获得。0,25.2121 21xxxxxxts105153212.5xxMaxz例如，在前面的练习中知的终表为51 0 52 153- 1 519 02913xx2.50 0.5- 0 0 0TX)09,0,2,(5z请指出其对偶问题的最优解和最优值。5)5 . 0 , 0(wY5. 5.互补松弛定理互补松弛定理。最优解的充要条件是、是和的可行解，则、分别是与若0)()()D()P( XYXYDPYXYXss自证。故只需而即是最优解，所以、由于 0 , 0,),()( , XYXYXYXYXIXAYXIYAYbYXC

8、YXssssss的约束化为等式：、证：将,)D()P(CIYYAbIXAXssy1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1xn+ixn+m 对偶问题的变量 对偶问题的松弛变量 原始问题的变量 原始问题的松弛变量xjym+j=0 yixn+i=0(i=1,2,m; j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0直观上直观上 在线性规划问题的最优解中，在线性规划问题的最优解中，假设对应某一约束条件的对偶变量假设对应某一约束条件的对偶变量值为非零，那么该约束条件取严厉值为非零，那么该约束条件取严厉等式，另一方面，假设约束条件取等式，另一方面，假设约束条件

9、取严厉不等式，那么其对应的变量一严厉不等式，那么其对应的变量一定为零。定为零。例：知线性规划问题5432132532minxxxxxw5,.,2 , 1, 0332432. .5432154321jxxxxxxxxxxxtsj知其对偶问题的最优解为：5,53,54*2*1zyy试用对偶实际找出原问题的最优解 对偶问题的经济解释1对偶最优解的经济解释资源的影子价钱Shadow PriceCBB-1 对偶问题的最优解 买主的最低出价； 原问题资源的影子价钱 当该资源添加1单 位时引起的总收入的增量卖主的内控价钱。 简单推导：简单推导：设D其最优值为 (注：与3最优值一样，那么根据zmmbybyby

10、bYz*2*21*1*.*/iiybz例：例1煤电油例的单纯形终表如下：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z1请指出资源煤、电、油的影子价钱，并解释其经济意义。2由单纯形终表还可得到哪些有用的信息？解：1煤、电、油的影子价钱分别是0、1.36、0.52； 其经济意义是当煤、电、油分别添加1单位时可使总 收入分别添加0 、1.36、0.52。2由单纯形终表还可得到：原问题的最优消费方案、最大收入、资源剩余，对偶问题的最低购买价钱、最少的购买费用等。 影子价钱在管理决

11、策中的作用：影子价钱在管理决策中的作用：1 1影子价钱影子价钱市场价钱市场价钱 假设影子价钱市场价钱，那么应买进假设影子价钱市场价钱，那么应买进该资源该资源 影子价钱市场价钱，那么应卖出该影子价钱市场价钱，那么应卖出该资源资源2 2影子价钱反映了资源的稀缺性，影影子价钱反映了资源的稀缺性，影子价钱越高，那么越稀缺。子价钱越高，那么越稀缺。y1y2ym2对偶约束的经济解释产品的时机本钱 (Opportunity Cost)时机本钱时机本钱表示减少一件产品所节省的资源可以添加的利润表示减少一件产品所节省的资源可以添加的利润mmjiijjjyayayaya2211添加单位资源可以添加的利润减少一件产

12、品可以节省的资源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211时机本钱利润差额本钱3对偶松弛变量的经济解释产品的差额本钱Reduced Cost差额本钱差额本钱=时机本钱时机本钱 利润利润jjTjmjmjjjmcaYcayayayy)(22110. .min212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmmyyyyyycyyayayacyyayayacyyayayatsybybybw0000

13、000000jjmjmjjmjiininiinixyyxyxyxxyxy 在利润最大化的消费方案中 1影子价钱大于0的资源没有剩余； 2有剩余的资源影子价钱等于0； 3安排消费的产品时机本钱等于利润； 4时机本钱大于利润的产品不安排消费。4互补松弛关系的经济解释三、灵敏度分析三、灵敏度分析 讨论模型的系数或变量发生小的变化讨论模型的系数或变量发生小的变化时对解的影响时对解的影响如它们在何范围内变化时可使原最优解或如它们在何范围内变化时可使原最优解或最优基不变？最优基不变？我们主要讨论C、b和变量构造变化时对解的影响。对解怎样影响？- 最优性 - 可行性001bB1. b变化时的分析变化时的分析

14、 只影响解的可行性只影响解的可行性不变。则原最优基使得故只要变化后的因为它只影响可行性，变为种资源设第BbBbbbbrrrr0,1 的范围即可。解出只要由rmrrbbbbbBbB01112. C变化时的分析变化时的分析但要分两种情况讨论。只影响最优性时变为价格,jjjccc的范围。解得只需由jjc 0即可。故只需，为因只影响本人的检验数0, 1jjBjjjPBCcc的价钱系数是非基变量(1)jjxc 的价钱系数是基变量jjxc (2)。解得公共的应由一切的数这时要影响一切的检验jiimiiiicPBccccc0,)( 113.添加新变量时的分析添加新变量时的分析 主要讨论添加新变量主要讨论添加

15、新变量xn+1能否有利。经济意能否有利。经济意义是第义是第n+1种新产品能否该当投产，数学意义是种新产品能否该当投产，数学意义是xn+1能否应进基。能否应进基。，即投产无利。，则不增加若，即投产有利；，则增加若的检验数方法：计算1111111110 0 ,nnnnnBnnnxx3BCcx1111nBnn3BCc经济意义：市场价影子价例：在例1煤电油例中，其单纯形终表如下：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z1电的影子价钱是多少？使最优基仍适用的电的变 化范围为何？

16、2假设有人愿以每度1元的价钱向该厂供应25度电，是 否值得接受？3甲产品的价钱在何范围内变化时，现最优解不变？4假设现又思索一新产品丙，其资源单耗为10，2，5， 售价为6.5，问该产品能否可投产？例：在例1煤电油例中，其单纯形终表如下：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z1电的影子价钱是多少？使最优基仍适用的电的变 化范围为何？解：1电的影子价钱是1.36。解得由 00.120.43.12242084300200360221bbB仍适用的范围。，即使原最优基Bb

17、26.92502例：在例1煤电油例中，其单纯形终表如下：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z2假设有人愿以每度1元的价钱向该厂供应25度电，是 否值得接受？解：2值得。 因25在B的适用范围内即影子价钱适用，且 1.36-1.000。0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z3甲产品的价钱在何范围内变化时，现最优解不变？解：甲产品的价钱c1是基变量的价钱系数。044. 14 . 08 . 2