《运筹学 第2版 教学课件 ppt 作者 沈荣芳 第三章 对偶规划和灵敏度分析》由会员分享，可在线阅读，更多相关《运筹学 第2版 教学课件 ppt 作者 沈荣芳 第三章 对偶规划和灵敏度分析（39页珍藏版）》请在金锄头文库上搜索。
1、第三章 对偶规划和灵敏度分析,第一节 对偶规划和对偶原理 第二节 对偶单纯形法和影子价格 第三节 灵敏度分析 第四节 参 数 规 划,第一节 对偶规划和对偶原理,一、线性规划的对偶规划 二、对偶规划的性质和原理,一、线性规划的对偶规划,1.问题的提出 2.两个问题之间的对偶关系 3.对偶规划,1.问题的提出,表 3-1,表 3-2,2.两个问题之间的对偶关系,2.两个问题之间的对偶关系,表 3-3,表 3-4,3.对偶规划,3.对偶规划,表 3-5,二、对偶规划的性质和原理,定理1 对称性 对偶规划的对偶规划是原规划。 定理2 弱对偶性 如果X、Y分别是原规划和对偶规划的可行解，那么必有C X
2、 Y b 定理3 如果原(对偶)规划具有无界解，那么其对偶(原)规划无可行解。,二、对偶规划的性质和原理,表 3-6,例4 运用互补松弛定理求解线性规划,极大化z=2x1+3x2 满足x1+2x29 2x1+x210 4x116 4x212 x1,x20的对偶规划。 已知原规划的最优解是x1=113,x2=83;最优值z=463。,第二节 对偶单纯形法和影子价格,一、对偶单纯形法 二、影子价格,一、对偶单纯形法,1.对偶单纯形法的步骤 2.对偶单纯形法的特点,1.对偶单纯形法的步骤,表 3-7,表 3-8,2.对偶单纯形法的特点,表 3-9,二、影子价格,影子价格是对偶规划解的一个经济学解释，
3、它能够告诉决策者，在现有生产情况下，哪种资源最为关键？企业以什么样的价格买进或卖出某种资源才是合适的？ 影子价格是随情况而改变的，在市场经济的情况下，当某种资源的市场价格低于企业的影子价格时，企业应购进一定数量的资源来扩大生产；而当市场价格高于企业的影子价格时，企业应卖出资源。可见影子价格对市场和企业的生产都有调节作用。,第三节 灵敏度分析,一、价值系数cj的变化 二、右端常数bi的变化 三、约束条件矩阵元素aij的改变,一、价值系数cj的变化,1.非基变量xj的系数cj改变 2.基变量xi的系数ci改变,1.非基变量xj的系数cj改变,表 3-10,表 3-11,2.基变量xi的系数ci改变
4、,表 3-12,二、右端常数bi的变化,设B=(p1,p2,pm)为线性规划的最优基。因 XB=B-1b,z=CBB-1b 所以，仅是资源数量的改变，只是影响原最优解的可行性及目标函数值。,表 3-13,二、右端常数bi的变化,三、约束条件矩阵元素aij的改变,1.非基变量xk的系数向量pk的改变 2.基变量xi的系数向量pi的改变 3.增加新的决策变量xn+1 4.增加新的约束条件,1.非基变量xk的系数向量pk的改变,2.基变量xi的系数向量pi的改变,表 3-14,3.增加新的决策变量xn+1,表 3-15,4.增加新的约束条件,4.增加新的约束条件,表 3-16,表 3-17,第四节
5、参 数 规 划,一、目标函数系数向量C的变化 二、资源向量b的变化,一、目标函数系数向量C的变化,(1)对含参数t的参数规划，先令t0，用单纯形法求出最优解。 (2)将t直接反映到最优单纯形表中，并用灵敏度分析的方法进行分析。 (3)当t连续变化时，观察b列和检验数行各元素的变化。 (4)在迭代后的单纯形表上，令t继续变化，重复步骤(3)，直到b不出现负值，检验数不出现负值为止。,例15 求解参数规划，其中参数t0。,极大化z (t)=(3，5)+t(2，-1)(x1,x2)T 满足x14 2x212 3x1+2x218 x1,x20,解 令t0，求解线性规划(表3-18)。,表 3-18,表
6、 3-19,表 3-20,解 令t0，求解线性规划(表3-18)。,表 3-21,解 z与t的关系可用图3-1表示,图 3-1,二、资源向量b的变化,这类问题的数学模型是 极大化z (t) =C X , t T 满足AX=b + t b，X0 其中b是给定的m维列向量，t是参数。由灵敏度分析已经知道，t的变化会改变原最优解的可行性，但不会改变检验数行的元素，所以只要B-1(b+tb)0，那么(B-1(b+tb),0)T就是最优解。,例16 求解参数规划,极大化z (t) =3x1+2x2+5x3 满足x1+2x2+3x3430+t 3x1+2x3460-4t x1+4x2420-4t x1,x2,x30,-t+,解 。令t=0，用单纯形法求解,表 3-22,表 3-23,表 3-24,解 在本例中，b=(1,-4,-4)T，t是参数,表 3-25,解 最优值z (t) 随t的变化而变化如图3-2所示,图 3-2,
