第2章对偶理论(完整).pptVIP

单纯形法和对偶单纯形法步骤 最优解 例、用对偶单纯形法求解线性规划问题： 是 是 是 是 否 否 否 否 所有 所有 得到 最优解 计算 计算 典式对应原规划的基本解是可行的 典式对应原规划的基本解的检验数 所有 所有 计算 计算 以为中心元素进行迭代 以为中心元素进行迭代 停 没有最优解 没有最优解 单纯形法 对偶单纯形法 §2.1 线性规划的对偶问题 Duality Theory §2.3 对偶问题的经济解释——影子价格 §2.4 对偶单纯形法 §2.5 灵敏度分析 §2.2 对偶问题的基本性质 第2章 线性规划的对偶理论 ?灵敏度分析主要讨论如下二类问题： ?线性规划的数据集合在什么范围内波动将不影响最优解或最优基？ ?若最优解发生变化，应如何用最简单的方法 找到新最优解。 0 CBB-1N-CN I B-1N XB XN 0 XB B-1b CB XB b cj→ CB CN Z CBB-1b θ σj ?对应基B，对应的单纯形表为： max z+(CBB-1N-CN) XN=CBB-1b s.t. XB+B-1NXN =B-1b XB,XN ≥ 0 变动 影响 不影响 bi 可行性，目标值 最优性 CB 最优性，目标值 可行性 CN 最优性 可行性，目标值 aij (j∈N) 最优性 可行性，目标值 B-1b≥0 可行性条件 CBB-1N-CN≥0 最优性条件 CBB-1b 目标函数值 σj=CBB-1Pj-cj max z+(CBB-1N-CN) XN=CBB-1b s.t. XB+B-1NXN =B-1b XB,XN ≥ 0 原问题 对偶问题 结论或继续计算的步骤 可行解 可行解 仍为原问题的最优解 可行解 非可行解 用单纯形法继续 迭代最优解 一、价值系数cj的变化分析 σj=CBB-1Pj-cj 设分量 br 变化为 br + ?br ， 最优解的基变量 xB = B-1b， 那么只要保持 B-1(b + ?b) ≥ 0 ，则最优基不变，即基变量保持，只有值的变化； 否则，需要利用对偶单纯形法继续计算。 二、右端项 b 发生变化 三、增加一个决策变量的分析 ?增加一个变量相当于增加一种产品。 ?分析步骤： Step1:计算σj=cj-CBB-1Pj Step2:计算P’j=B-1Pj Step3:若σj≥0，只需将P’j与σj的值直 接反映到最终单纯形表T(B)中， 原最优解不变。 若σj≤0，则按单纯形法继续迭代计算。 四、对增加约束条件的分析 ?增加一道工序。 ?分析步骤： Step1:将原问题的最优解代入新增加的约束 条件中。 Step2:若满足，则最优解不变。 Step3:若不满足，将新约束反映到最终 单纯形T(B)中，再分析迭代。 * * * * * * * * * * * * * * * * * * * * * 5、互补松弛性 定理：设 和 分别是原问题和其对偶问题的最优解， 若对偶变量 ，则原问题相应的约束条件 若约束条件 ，则相应的对偶变量 若 ，则 若 ，则 若 ，则 若 ，则 例2、利用互补松弛定理求最优解 max s.t. 已知原问题的最优解是 求对偶问题的最优解。 解： 设对偶变量为 min s.t. 则对偶问题为 设对偶问题的最优解为 因 由互补松弛性知 解方程组得 故对偶问题的最优解为 例3、利用互补松弛定理求最优解 已知原问题的最优解是 max s.t. 求对偶问题的最优解。 对偶变量为 min s.t. 则对偶问题为 设对偶问题的最优解为 将 代入原问题约束条件得 解： 由互补松弛性知 又 故对偶问题的最优解为 得 例4、利用互补松弛定理求最优解 已知其对偶问题的最优解是 min s.t. 求原问题的最优解。 对偶问题为 设原问题的最优解为 解： min s.t