《对偶理论与灵敏度分析》由会员分享，可在线阅读，更多相关《对偶理论与灵敏度分析（67页珍藏版）》请在金锄头文库上搜索。
1、1,概要1 对偶问题及对偶关系 1.1 对偶问题 1.2 对偶定义 1.3 对偶关系2 对偶理论3 对偶单纯形法4 灵敏度分析 4.1 目标函数系数 Cj 的改变 4.1.1 非基变量的Cj改变 4.1.2 基变量的Cj改变 4.2 常数项bi的改变 4.3 技术系数aij的改变 4.4 增加一个变量 4.5 增加一个约束条件,2,如何合理使用资源，使总利润最大？,有限资源下的利润最大化问题,3,线性规划模型,4,最优生产计划为： x1= 41.82 (件)， x2= 52.73 (件)最大利润 z=389.09（万元）,资源的剩余量：资源1：200-(x1+3x2)= 0 （吨）资源2：35
2、0-(2x1+2x2)= 160.9 （吨）资源3：220-(4x1+2x2)= 0 （吨）资源4：400-(3x1+2x2)= 169.09 （吨）,最优解,5,问题：每种资源的价值如何？应如何定价？与市场采购价关系如何？,影子价格的引入,6,1.1 对偶问题,最优解 (四种资源的影子价格：万元/吨) : y1=1.55 , y2= 0, y3= 0.36, y4= 0 目标函数值 w=389.09（万元）,7,影子价格的经济意义,8,利润最大化问题影子价格的经济解释,每一种资源的影子价格=当该资源增加一个单位时，总利润Z的增加量,9,成本最小化问题影子价格的经济解释,每一种需求的影子价格=
3、当该需求增加一个单位时，总成本Z的增加量,10,1.2 对偶的定义,定义 设以下线性规划问题 Max z=CXs.t.AX b (P) X0为原始问题，则称以下问题 Min w=Ybs.t.YA C (D) Y0为原始问题的对偶问题。,11,（LP）,（DP）,12,(P),(D),13,对偶的对偶,设原始问题(P)为：max z=CXs.t.AX bX0,(P)的对偶 (D)为:min y=Ybs.t.YA CY0,(D)的等价问题为: max y= -Yb s.t. -YA -CY0,(D) 的对偶 为:min z=-CXs.t. -AX - bX0,14,定理 对偶问题的对偶就是原始问题
4、,15,1.2 对偶关系,16,17,2 对偶理论,18,2.1 弱对偶定理,若 分别是原问题LP(max)与其对偶问题DP(min)的可行解，且 z=CX(0)、w=Y(0)b,则 wz,19,2.2 最优性定理,若 分别是原问题LP与其对偶问题DP的可行解，且 CX(0) =Y(0)b,则 X(0),Y(0) 分别是原问题LP与其对偶问题DP的最优解。,20,2.3 强对偶定理,若原问题LP有最优解X*，则其对偶问题DP也有最优解Y*，且 Z*=CX * =Y*b=W*,21,2.4 对偶解定理,若用单纯形法解原问题LP，得有最优解X*，相应的最优基为B，则 Y*=CBB-1为其对偶问题D
5、P的最优解 附注：如何在最优单纯形表中看出对偶问题的最优解,22,23,当前基本可行解：(30, 12, 0, 8, 0) , Z=1980,24,25,2.5 互补松弛定理,26,互补松弛定理的应用,求解以下线性规划问题LP ：,27,写出对偶问题DP：,利用图解法，可以求得DP的最优解为 (y1，y2)T=(6，0)T,28,得到对偶问题各松弛变量的值y3=0，y4=2，y5=3即对偶问题的最优解和最优目标函数值为yT=(y1，y2，y3，y4，y5)T=(6，0，0，2，3)Tw=6 根据互补松弛定理，以下的互补松弛关系成立由y10得到x4=0由y40得到x2=0由y50得到x3=0,2
6、9,因此原始问题的约束条件,成为,由此得到x1=1，x5=2即原始问题的最优解为X=(x1，x2，x3，x4，x5)T=(1，0，0，0，2)Tz=6,30,3 对偶单纯形法,LP可行解,DP可行解,31,当LP与DP均为可行时，LP与DP均得到最优解,单纯形方法：保持LP可行的同时，逐步将DP变可行,对偶单纯形方法：保持DP可行的同时，逐步将LP变可行,32,33,34,35,36,改进单纯形法,37,38,4 灵敏度分析,灵敏度分析所要解决的问题：系数在什么范围内变化，不会影响已获得的最优基。如果系数的变化超过以上范围，如何在原来最优解的基础上求得新的最优解当线性规划问题增加一个新的变量或
7、新的约束，如何在原来最优解的基础上获得新的最优解。,39,灵敏度分析内容,4.1 目标函数系数 cj 的改变 4.1.1 非基变量的cj改变 4.1.2 基变量的cj改变4.2 常数项bi的改变4.3 技术系数aij的改变4.4 增加一个变量4.5 增加一个约束条件,40,4.1 目标函数系数cj的改变,非基变量在目标函数中系数的灵敏度分析,基变量在目标函数中系数的灵敏度分析,41,4.1.1非基变量在目标函数中系数的灵敏度分析,在线性规划问题中，对c2进行灵敏度分析 。,42,得到以上问题的最优单纯形表：,43,44,要使原来的解仍保持最优解，就要 0（j=1,2,3,4,5），即,由此得到
8、 ，即当 时，最优基保持不变,最优解保持不变.,45,4.1.2基变量在目标函数中系数的灵敏度分析,在线性规划问题中，对c1进行灵敏度分析 。,46,得到以上问题的最优单纯形表：,47,当 时，相应的单纯形表为：,48,要使原来的基仍保持最优基，就要 0（j=1,2,3,4,5），即,由此得到，-3 3，即当-4 2 时，最优基保持不变，最优解保持不变.,49,4.2 右边常数的灵敏度分析,右边常数的灵敏度分析,50,51,例,在线性规划问题中，对b1进行灵敏度分析 。,52,最优单纯形表,初始单纯形表,53,对于上述最优解，最优基为：,54,当b1=b1+=9+时，最后一张单纯形表中的右边常
9、数将成为,最后一张单纯形表中的右边常数将成为：,55,原始可行条件为：,-1，b1=b1+8时，原来的最优基仍为原始可行基最优解已改变.,56,4.3 技术系数的改变,如何求灵敏度范围？如果超出灵敏度范围，如何求新的最优解?,57,最优单纯形表,初始单纯形表,58,59,60,61,4.4 增加一个新的变量,增加一个新的变量x7，它在目标函数中的系数c7=1，在约束条件中的系数向量为 ：,求新的最优基和最优解。,62,最优单纯形表,初始单纯形表,63,对于上述最优解，最优基为：,单纯形表中x7对应的系数：,64,加入x7后的单纯形表为：,65,4.5 增加一个新的约束,增加一个新的约束：-x1+2x22，求新的最优基和最优解。,-x1+2x22,-x1+2x2-x7=2,x1-2x2+x7=-2,66,在原最优单纯形表中加入新方程信息：,67,变成单纯形表：,
