运筹学-第1章解析.ppt

第四节 对偶问题和对偶单纯形法 二、对偶基本定理 考虑如下线性规划问题： 第四节 对偶问题和对偶单纯形法 二、对偶基本定理 单纯形表的矩阵形式 基 　 解 基 解 　 　 初始表： 迭代后表： 第四节 对偶问题和对偶单纯形法 二、对偶基本定理 构造如下线性规划问题： 令 （单纯形乘子，对偶问题的最优解） 第四节 对偶问题和对偶单纯形法 二、对偶基本定理 对偶关系示意图 非最优 非最优 可行 可行 ... ... ... 最优 最优 最优 最优 可行 不可行 不可行 不可行 ... ... 原问题 对偶问题 第四节 对偶问题和对偶单纯形法 二、对偶基本定理 基本定理 定理1 （弱对偶性）若 是原问题的可行解， 是对偶 问题的可行解，则有 。 定理2 （最优性）设 、 分别为原问题和对偶问题的 可行解。若 ，则 、 分别为原问题和对偶问 题的最优解。 定理3 （强对偶性）若原问题和对偶问题均有可行解，则两 者都有最优解，且最优值相等。 第四节 对偶问题和对偶单纯形法 三、对偶单纯形法 例4 用对偶单纯形法求如下线性规划： 最优解： 最优值： 第四节 对偶问题和对偶单纯形法 三、对偶单纯形法 对偶单纯形法的基本步骤 1、将约束条件化成小于等于约束，列出初始单纯形表。 2、 确定出基变量。选右端向量 中，负的最大的基变量 （若 ，则已得最优解）记为 。 3、 确定进基变量。若第 行系数 ，则原问题无解。 反之，令 即为进基变量， 为旋转元。 4、用初等行变换，得到一个新的基，重复以上步骤直到最优。 第四节 对偶问题和对偶单纯形法 四、对偶问题的经济意义 max z=50x1+100x2 min w=300y1+400y2+250y3 s.t. x1 + x2≤300 s.t. y1+ 2y2 ≥50 2x1 + x2≤400 y1 + y2 + y3≥100 x2≤250 y1、y2、y3 ≥0 x1、x2≥0 例1（续） 最优解： 最优解： 影子价格：约束条件右端项增加一个单位，目标函数值的增加量（即为对偶问题的最优解） 本节作业 1-38（2）（3） 1-48 1-42 第四节 对偶问题和对偶单纯形法 第 五节 灵敏度分析 一、引例 例1 某企业利用甲、乙两种原料，生产A、B、C三种产品，每 种的产品单位利润及原材料消耗定额等数据如下表，问如何 安排生产计划使企业利润最大？ 产 品 原料 A B C 供应量 甲 乙 1 2 0 2 1 1 30 80 单位利润 4 3 2 第 五节 灵敏度分析 一、引例 例1的LP模型： 设x1、x2、x3分别代表A、B、C三种产品的生产数量，则 max z=4x1+3x2+2x3 max z=4x1+3x2+2x3 s.t. x1+ x3≤30 s.t. x1+ x3+s1=30 2x1+2x2+x3≤80 2x1+2x2+x3 +s2=80 x1 ，x2≥0 x1 ，x2 , s1 ，s2≥0 第 五节 灵敏度分析 一、引例 初始单纯形表： 基 解 　 　 基 解 　 　 最优单纯形表： 第 五节 灵敏度分析 二、灵敏度分析的概念 1、什么是灵敏度分析 在 LP求出最优解之后，要研究： 1）当 ci 发生变化时，最优解如何变化？ 2）当 bi 发生变化时，最优解是否变化？最优值变化多少？ 3）当 aij 发生变化时，最优解如何变化？ 2、为什么要进行敏感性分析？ 1）现实世界是动态变化的，如：市场变化，售价的变化将导致利润率的变化，进而导致目标函数系数的变化。 2）有些资源是可控的，如：是否加班？将导致可用工时的变化，进而导致右端项值的变化。 3）模型中的数据有些是估计的、近似的。 3、LP模型系数变化后的处理方法 1）重新求解——麻烦，除了最优解外，其他额外价值信息无法获得。 2）灵敏