线性规划_单纯形法

实用优化方法第 2章 线性规划：单纯形法刘红英理学院数学系线性规划： 目标函数是线性的，约束条件是线性等式或不等式线性规划线性规划的历史 渊源要追溯到 Euler、 Liebnitz、 Lagrange等 George Dantzig, Non Neumann(Princeton)和Leonid Kantorovich在 1940s创建了线性规划 1947年 , George Dantzig于 发明了 单纯形法 1979年 ， L. Khachain找到了求解线性规划的一种有效方法 (第一个多项式时间算法 椭球内点法) 1984年 ， Narendra Karmarkan发现了另一种求解线性规划的有效方法，已证明是单纯形法的强有力的竞争者 (投影内点法 ) 现在求解大规模、退化问题最有效的是 原对偶内点法 问题 ：确定食品数量，满足营养需求，花费最小？ 变量：n种食品， m种营养成份； 第 j 种食品的单价每单位第 j 种食品所含第 i 种营养的数量食用第 j 种食品的数量为了健康，每天必须食用第 i 种营养的数量 模型：例 1. 食谱问题例 2. 运输问题产销 平衡 /不平衡 的运输问题例 3. 目标值带绝对值的问题假设：事实：转化为：例 4. 其它应用 数据包络分析 (data envelope analysis, DEA) 网络流问题 (Network flow) 博弈论 (game theory)等线性规划的一般形式线性规划的标准形 (分析、算法 )*标准形的特征： 极小化 、 等式约束 、 变量非负向量表示：一般形式 标准形转化称 松弛 (slack)/盈余 (surplus)变量例 5. 化成标准形等价表示为定义 设 B是 A 的 m个线性无关列组成的矩阵 . 置所有与 B无关列对应的变量为零，称所得方程组的解是 Ax=b的基本解 (basic solution) 称 B是 基 (basis)；称与 B对应的变量为 基变量 (basic variables)基本解与基变量 (*)其中满秩假定： mn，且 A的行向量线性无关基本可行解定义 称 的非负基本解是 标准形 的 基本可行解 (basic feasible solution)；例 6. 基本可行解及几何意义基本可行解的个数 不超过线性规划的基本定理 (*)i) 若有可行解，则 必存在 基本可行解；ii) 若有解，则 必有某个基本可行解 是最优解 .考虑线性规划标准形，其中 A是秩为 m的 mn阶矩阵，则以下结论成立：与凸性的关系线性规划的基本定理 (标准形 )基本可行解线性方程组的基本性质代数理论(与 表述形式有关 )设计算法极点凸集理论几何理论(与表述形式 无关 )直观理解凸性 (凸集及性质)几何解释 ：连接集合中任两点的线段仍含在该集合中性质定义 是凸集 (convex set)，如果对 S中任意两 点 x , y 和 (0,1)中的任一数 满足一些重要的凸集有限个闭半空间的交集多面集 (polyhedral convex set):推广平面上：多边形注： 任一线性规划的可行集是 多面集 ！超平面 (hyperplane):正 /负闭半空间：极点几何上 ：极点即不能位于连接该集合中其它两点的开线段上的点定义 称凸集 C中的点 x 是 C的极点，如果存在 C 中的点 y, z 和某 ，有则必有 y=z.极点与基本可行解的等价性定理推论：线性规划基本定理的几何形式i) 若 K非空，则至少有一个极点 .ii) 若线性规划有解，则必有一个极点是最优解 .iii) K的极点是有限集 .考虑线性规划标准形，其中 A是秩为 m的 mn矩阵，令则 x是 K 的极点 当且仅当 x是线性规划的基本可行解.例 2. K 有 2个极点有 3个基本解， 2个 可行K 有 3个极点有 3个基本解， 均可行例 1. 例 3. Subject to5个极点极点问题 /作业考虑集合证明这两个集合的极点是 一一对应 的！线性规划问题解的几种情况线性规划解的几何特征唯一 解 (顶点 )！顶点一条边无 (下 )界线性规划解的 几何特征 无界 ：没有有限最优解 不可行 ：没有可行解 无解可行集： 多边形 (二维 ) 多边集 (高维空间 )给出 有效的代数刻画 和 严谨的几何描述 ，从理论上证实上述几何特征，并 寻求有效算法 有解 ： 唯一解 /多个解 (整条边、面、甚至整个可行集 ) 有顶点解单纯形法简介 适用形式： 标准形 (基本可行解 =极点 ) 理论基础： 线性规划的 基本定理 ！ 基本思想： 从约束集的 某个极点 /BFS开始，依次移动到 相邻极点 /BFS，直到找出最优解，或判断