《最优化LP对偶单纯形法.ppt》由会员分享，可在线阅读，更多相关《最优化LP对偶单纯形法.ppt（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、对偶单纯形法对偶单纯形法设设 是一个基，是一个基，满足约束满足约束 的对偶向量的对偶向量 称为称为对偶基本解对偶基本解。若对偶基本解若对偶基本解 也是可行的，即松弛向量也是可行的，即松弛向量 ，称，称 为为对偶基本可行解对偶基本可行解。若若 的所有分量均不为零，称的所有分量均不为零，称 是非退化的是非退化的。若若 对应的原始基本解和对偶基本解都是非退化的，对应的原始基本解和对偶基本解都是非退化的，称称 为为非退化基非退化基。定理定理(最优条件最优条件)若若 对应的原始基本解对应的原始基本解 和对偶基本解和对偶基本解 都是可行都是可行的，则这两个基本解分别是原始问题和对偶问题的的，则这两个基本解
2、分别是原始问题和对偶问题的最优解，最优解，为为最优基最优基。证明：证明：原始单纯形方法分析原始单纯形方法分析在算法中，当前基在算法中，当前基 保持原始基本解保持原始基本解 可行。可行。在该方法中，对偶基本解在该方法中，对偶基本解 仅在算法仅在算法停止时才变成可行的。停止时才变成可行的。算法中的检验数算法中的检验数 就是松弛向量就是松弛向量 。在任一基。在任一基 ，总是互补的总是互补的。当算法停止时，当算法停止时，成为原始最优解，成为原始最优解，成为对偶可行，成为对偶可行，因此也是对偶最优的，二者最优值相等因此也是对偶最优的，二者最优值相等。对偶单纯形主要思想对偶单纯形主要思想原始单纯形：保持原
3、始基本解原始单纯形：保持原始基本解 可行和互补松弛可行和互补松弛条件条件 可行可行;对偶单纯形：保持原始基本解对偶单纯形：保持原始基本解 可行和互补松弛可行和互补松弛条件条件 可行。可行。s.ts.t.注意到：注意到：对偶单纯形分析对偶单纯形分析给定基给定基 ，写出，写出LP的典式，则有：的典式，则有：(1),最优解，停止。最优解，停止。(2)且且 ，原问题不可行。，原问题不可行。(3),但但 。根据算法思想，需要保持对偶可行性：根据算法思想，需要保持对偶可行性：选择这些负数选择这些负数 之一为转轴中心，之一为转轴中心，为出基变量。为出基变量。为进基变量为进基变量第一个对偶基本可行解的求法第一个对偶基本可行解的求法s.ts.t.第一个对偶基本可行解的求法第一个对偶基本可行解的求法