第二章 对偶理论及灵敏度分析.pptVIP

最优解例：用对偶单纯形法求解线性规划问题：第61页，共100页，星期日，2025年，2月5日对偶单纯形法的优点：当约束条件为“≥”时，不必引进人工变量，使计算简化；在灵敏度分析中，有时需要用对偶单纯形法处理简化。对偶单纯形法缺点：在初始单纯形表中对偶问题是基可行解，这点对多数线性规划问题很难做到。因此，对偶单纯形法一般不单独使用。第62页，共100页，星期日，2025年，2月5日练习：P76,2.9（1）用对偶单纯形法求解线性规划问题：第63页，共100页，星期日，2025年，2月5日结束第4节对偶单纯形法第64页，共100页，星期日，2025年，2月5日5.1灵敏度问题及其图解法灵敏度问题灵敏度分析——图解法第5节灵敏度分析第65页，共100页，星期日，2025年，2月5日背景：线性规划问题中，都是常数，但这些系数是估计值和预测值。市场的变化值变化；工艺的变化值变化；资源的变化值变化。第5.1节灵敏度问题第66页，共100页，星期日，2025年，2月5日问题：当这些系数中的一个或多个发生变化时，原最优解会怎样变化？当这些系数在什么范围内变化时，原最优解仍保持不变？若最优解发生变化，如何用最简单的方法找到现行的最优解？第67页，共100页，星期日，2025年，2月5日研究内容：研究线性规划中，的变化对最优解的影响。研究方法：图解法对偶理论分析仅适用于含2个变量的线性规划问题在单纯形表中进行分析第68页，共100页，星期日，2025年，2月5日MaxZ=34x1+40x24x1+6x2?482x1+2x2?182x1+x2?16x1、x2?0线性规划模型灵敏度分析——图解法第69页，共100页，星期日，2025年，2月5日x218—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x14x1+6x2?482x1+2x2?182x1+x2?16ABCDE(8,0)(0,6.8)最优解(3,6)4x1+6x2=482x1+2x2=18灵敏度分析——图解法第70页，共100页，星期日，2025年，2月5日一、对称定理：定理：对偶问题的对偶是原问题。设原问题（1）对偶问题（2）三、对偶问题的基本性质第29页，共100页，星期日，2025年，2月5日二、弱对偶性定理：——若和分别是原问题（1）及对偶问题（2）的可行解，则有证明：三、对偶问题的基本性质第30页，共100页，星期日，2025年，2月5日（1）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。（2）极小化问题（对偶问题）的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。（3）若原问题可行，但其目标函数值无界，则对偶问题无可行解。由弱对偶性可得以下结论：三、对偶问题的基本性质第31页，共100页，星期日，2025年，2月5日（4）若对偶问题可行，但其目标函数值无界，则原问题无可行解。（5）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。（6）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。原问题对偶问题三、对偶问题的基本性质第32页，共100页，星期日，2025年，2月5日三、最优性定理：——若和分别是（1）和（2）的可行解，且有则分别是（1）和（2）的最优解。三、对偶问题的基本性质第33页，共100页，星期日，2025年，2月5日证明：原问题与对偶问题的解一般有三种情况：一个有有限最优解另一个有有限最优解。一个有无界解另一个无可行解。两个均无可行解。四、强对偶性（对偶定理）：——若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。三、对偶问题的基本性质第34页，共100页，星期日，2025年，2月5日五、互补松弛性：