线性规划讲义课件.ppt

线性规划讲义（linear program） 组员： 林舒进 万军 曾跃文 李婷 线性规划（LP） 线性规划是使用数学模型描述相关问题的一种工具 内涵 线性：模型中所有的数学函数都是线性函数。 规划：等同与计划，既在模型中找找出最优解。 线性规划解决什么类型的问题 狭义问题：给活动分配资源（竞争性活动中以最佳的可能方式分配有限资源） 例如：生产设施的分配，国家资源和家庭必须品的分配，部长职位的选举，海运模式的选择，农业生产计划，放射性治疗等 广义问题：数学模型符合线性规划一般形式的任何问题都是线性规划问题 线性模型的三个要素 决策变量:待求的未知数 约束条件：一组线性方程，该线性方程的集合为决策变量的可行域 目标函数：用函数表示的追求的目标，通常是最大或者最小 构建线性规划模型 图解法 无穷多解 无界解 无可行解 模型解的术语 可行解（feasible solution）满足所以约束条件的解（非可行解） 可行域（feasible region）所有可行解的集合 最优解（optimal solution）目标函数取得最有利的可行解 模型解的术语 基（the basis）：约束方程构成矩阵中的非奇异矩阵（基向量、基变量、基解） 基可行解：非负的基解 可行基：对应基可行解的基 单纯形法原理分析 单纯型法（simplex method） 1947年乔治.丹捷格（George Dantzig）提出单纯形法，（乔治.丹捷格堪称运筹学最重要的先驱，由于在单纯形法及其他方面的很多重要贡献，他被称为线性规划之父）单纯形法已经被证实是真正有效的方法，如今通常用于在计算机上解决大型问题。（除了一些小问题，这种方法总是在计算机上实现）单纯形法的延伸和变化也被用来对模型进行优化后分析（包括灵敏度分析） 单纯形法的实质 单纯形法是一个代数计算过程，但它本质上是基于几何原理 了解这些几何原理能为我们理解单纯形法的运算步骤提供非常直观的解释，同时也有助于我们将解释为什么单纯形法为什么会如此有效 单纯形法的几何原理 约束边界（constraint boundary）：每个约束条件都是一条直线，该直线就是满足对应约束的边界线 角点解（corner-point solutions）：约束边界的交点 角点可行解（CPF solutions）：在可行域上的角点 相邻（adjacent）：两个CPF解位于同一条约束边界上，它们是相邻的，两个相邻的CPF解连成的一条线段被称为可行域的边 （edge） 最优性检验（optimality test）：如果一个CPF解没有比它更好（以z来衡量）的相邻CPF解，那么它就是最优解 几何原理示例 关键的解原理 解原理1：单纯形法只关注CPF解 解原理2：单纯形法是一个迭代算法（一个系统化的求解过程，它重复着一系列固定的我们称之为迭代的步骤，直到得到期望的结果），结构如下 关键的解原理 解原理3： 只要有可能单纯形法的起始步骤就选择原点作为初始CPF解 解原理4：已知一个CPF解，从计算上来说，获取它的相邻CPF解的信息比获取其他CPF解的信息更快 解原理5：得到当前的CPF解后，单纯形法考察从这个解出发的可行域的每一条边（不是计算相邻CPF解，而仅仅是判断沿这条边移动时z的增长率） 关键的解原理 解原理6：z增长率为正，意味着相邻CPF解优于当前CPF解；z增长率为负，意味着相邻CPF解并不优于当前CPF解。因此，最优性检验及时检查是否有边界线会带给z正的增长率，如果没有，则证明当前的CPF解是最优的。 构建单纯形法 单纯形法通常是在计算机上实施的，而计算机只能执行代数运算，因此需要把上述几何原理转化成可应用代数计算的步骤。 第一步：把不等式约束转化为等价的等式约束，这个过程考引入松弛变量（slack variables）来完成 模型的扩展模式（augmented form）：原线性模型在引入松弛变量后形成的新的模式 扩展模式的术语 扩展解（augmented solution）：原始变量（决策变量）取值再加入相应的松弛变量取值后形成的解 基本解（basic solution）：是一个扩展后的角点解 基本可行解（BF解）：是扩展的CPF解（非负）（非基变量，基变量，基） BF解相邻（adjacent）：当非基变量只有一个不同时，两个BF解相邻（因此，从当前BF解转到另一个相邻的BF解时，围绕着把一个变量从非基变量转变为基变量来进行） 单纯形法的代数-初始化 选择 为非基变量（这些变量设为0） 单纯形法的代数-最优性检验 单纯形法的代数-确定移动方向 单纯形法的代数-确定在何处停下 单纯形法的代数-求解新的BF解 单纯形法的代数-求解新的BF解