第2讲 对偶理论和灵敏度分析.pptVIP

灵敏度分析内容 ※目标函数系数cj的改变 ※常数项bi的改变 ※技术系数aij的改变 灵敏度分析步骤 对于变化的系数，经过一定的计算将结果填入最终单纯形表。 求出LP问题的最终单纯形表 检查与分析最终单纯形表的变化，采取相应的处理措施。 判断: 任何线性规划问题存在并具有唯一的对偶问题. 已知y*i为线性规划的对偶问题的最优解,如果y*i=0,说明在最优生产计划中第i种资源一定有剩余 （不一定有剩余）. 已知y*i为线性规划的对偶问题的最优解,如果y*i0,说明在最优生产计划中第i种资源已经完全耗尽. √ √ × 判断: 若线性规划的原问题有无穷多最优解,则其对偶问题也一定具有无穷多解. 根据对偶的性质,当原问题无界解时,其对偶问题无可行解,反之,当对偶问题无可行解,其原问题具有无界解. （或者无可行解） 若线性规划问题的原问题存在可行解，则对偶问题也一定存在可行解 若线性规划的原问题和其对偶问题都具有可行解，则该线性规划问题一定具有有限最优解. × × × × 思考题 技术系数变化的灵敏度分析通常在什么情况下是必要的? 影子价格可以为决策者提供哪些信息? 作业：习题1 15，16，习题2 1，3，4，5 弱对偶定理推论 原问题的任何可行解目标函数值是其对偶问题目标函数值的下限；对偶问题的任何可行解目标函数值是原问题目标函数值的上限 如果原(对偶)问题为无界解，则其对偶(原)问题无可行解 如果原(对偶)问题有可行解，其对偶(原)问题无可行解，则原问题为无界解 当原问题(对偶问题)为无可行解,其对偶问题(原问题)或具有无界解或无可行解 (3)强对偶性 证：由弱对偶定理推论1，结论是显然的。 若　是原问题的可行解，是对偶问题可行解，当　　　　 　　 , , 分别是相应问题的最优解 是使目标函数取最小值的解，因此是最优解 可行解是最优解的性质(最优性准则定理) (4) 对偶定理 若原问题和对偶问题两者皆可行,则两者均有最优解,且此时目标函数值相等. 第1部分:证明两者均有最优解 证明分两部分 由于原问题和对偶问题均可行,根据弱对偶性,可知两者均有界,于是均有最优解. 第2部分:证明有相同的目标函数值 设 为原问题的最优解 它所对应的基矩阵是B， 则其检验数满足 C ? CBB?1A ? 0 因此有对偶问题目标函数值 而原问题最优解的目标函数值为 显然 为对偶问题的可行解。 证毕 故由最优解准则定理可知 为对偶问题的最优解. 对偶定理推论 根据对偶定理第2部分的证明,可以得出:若互为对偶的线性规划问题中的任一个有最优解,则另一个也有最优解,且目标函数值相等. 综上所述,一对对偶问题的解必然是下列三种情况之一: 原问题和对偶问题都有最优解 一个问题具有无界解,另一个问题无可行解 原问题和对偶问题都无可行解 (5)互补松弛定理 证：由定理所设，可知有 设 , 分别是原问题和对偶问题的可行解， 为原问题的松弛变量的值，为对偶问题剩余变量的值。 , 分别是原问题和对偶问题最优解的充分必要条件是 分别以 左乘(1)式，以 右乘(2)式后，两式相减，得 根据最优解判别定理， 分别是原问题和对偶问题最优解。反之亦然。 证毕。 （1） （2） max z=CX s.t. AX+XS=b X, XS ≥0 min w=Yb s.t. AY-YS=C Y, YS ≥0 XYS=0 YXS=0 m n = Y YS A -I C n = A XS I b n m m X 原始问题和对偶问题变量、松弛变量的维数 原始问题和对偶问题最优解之间的互补松弛关系 maxz=CX s.t. AX+XS=b X, XS≥0 min w=bY s.t. AY-YS=C Y, YS≥0 maxz=CX s.t. AX≤b X ≥0 min w=bY s.t. AY≥C Y≥0 对偶 引进松弛变量 引进松弛变量 XYS=0 YXS=0 互补松弛关系 X，Xs Y，Ys y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对偶问题