Greenberg, Harvey J., Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method University of Colorado at Denver (1997) PDF download (页面存档备份,存于互联网档案馆)
Frederick S. Hillier and Gerald J. Lieberman: Introduction to Operations Research, 8th edition. McGraw-Hill. ISBN 0-07-123828-X
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 29.3: The simplex algorithm, pp.790–804.
单纯形法, simplex, algorithm, 在数学优化领域中常用于线性规划问题的数值求解, 由喬治, 伯納德, 丹齊格发明, 下山, nelder, mead, method, 与名称相似, 但二者关联不大, 该方法由nelder和mead于1965年发明, 是用于优化多维无约束问题的一种数值方法, 属于更普遍的搜索算法的类别, 这两种方法都使用了单纯形的概念, 单纯形是, displaystyle, 维中的, displaystyle, 个顶点的凸包, 是一个多胞体, 直线上的一个线段, 平面上的一个三角. 单纯形法 simplex algorithm 在数学优化领域中常用于线性规划问题的数值求解 由喬治 伯納德 丹齊格发明 下山单纯形法 Nelder Mead method 与单纯形法名称相似 但二者关联不大 该方法由Nelder和Mead于1965年发明 是用于优化多维无约束问题的一种数值方法 属于更普遍的搜索算法的类别 这两种方法都使用了单纯形的概念 单纯形是 N displaystyle N 维中的 N 1 displaystyle N 1 个顶点的凸包 是一个多胞体 直线上的一个线段 平面上的一个三角形 三维空间中的一个四面体等等 都是单纯形 目录 1 标准形式 2 松弛形式 3 转轴操作 4 方法步骤 5 最优化过程 5 1 实例 6 初始化过程 7 效率分析 8 参考 9 参看 10 外部链接标准形式 编辑假设有n个变量和m个约束 线性规划的标准形式如下 max 1 k n c k x k s t 1 k n A 1 k x k b 1 1 k n A 2 k x k b 2 1 k n A m k x k b m x 1 x 2 x n 0 displaystyle begin aligned amp amp max sum limits 1 leq k leq n c k x k amp s t amp sum limits 1 leq k leq n A 1 k x k leq b 1 amp amp sum limits 1 leq k leq n A 2 k x k leq b 2 amp amp amp sum limits 1 leq k leq n A m k x k leq b m amp amp x 1 x 2 x n geq 0 end aligned nbsp 所有其他形式的线性规划方程组都可以按照下列方式转化成标准形式 目标函数并非最大化 将所有c k displaystyle c k nbsp 取负 约束条件中存在大于或等于约束 将约束两边取负 约束条件中存在等式 将其拆分为两个不等式 一个大于等于 一个小于等于 有的变量没有非负约束 加入新变量x x x x gt 0 displaystyle x x x x gt 0 nbsp 并用x x displaystyle x x nbsp 替换原来的变量x displaystyle x nbsp 松弛形式 编辑可以将标准形式的线性规划转化为松弛形式 以方便运算 在原来n个变量 m个约束的线性规划中 加入m个新的变量 将原来的不等式化为等式 x n j b j 1 k n A j k x k displaystyle x n j b j sum limits 1 leq k leq n A j k x k nbsp 当然 此时x n j 0 displaystyle x n j geq 0 nbsp 依然成立 我们将x 1 x 2 x n displaystyle x 1 x 2 x n nbsp 这些变量称为非基变量 它们构成的集合记为N 将 x n 1 x n 2 x n m displaystyle x n 1 x n 2 x n m nbsp 这些变量称为基变量 它们构成的集合记为B 简单地理解 非基变量能够由基变量唯一确定 在这样的定义下 线性规划的松弛形式可以写为如下形式 max k N c k x k s t 1 i n m x i 0 j B x j b j k N A j k x k displaystyle begin aligned amp max sum limits k in N c k x k amp s t amp forall 1 leq i leq n m x i geq 0 amp forall j in B x j b j sum limits k in N A j k x k end aligned nbsp 因此 线性规划的松弛形式可以由c A b N B displaystyle c A b N B nbsp 唯一确定 c displaystyle c nbsp 是长度为n的向量 b displaystyle b nbsp 是长度为m的向量 A displaystyle A nbsp 是m n m 的矩阵 N B displaystyle N B nbsp 是整数集合 分别表示非基变量集合以及基变量集合 转轴操作 编辑转轴操作是单纯形法中的核心操作 其作用是将一个基变量与一个非基变量进行互换 可以将转轴操作理解为从单纯形上的一个顶点走向另一个顶点 设变量x n d displaystyle x n d nbsp 属于B 基变量 变量x e displaystyle x e nbsp 属于N 非基变量 执行转轴操作pivot d e 之后 x n d displaystyle x n d nbsp 将变为非基变量 相应地x e displaystyle x e nbsp 将变为基变量 具体地说 一开始我们有x n d b d k N A d k x k displaystyle x n d b d sum limits k in N A d k x k nbsp 移项 得A d e x e b d k N k e A d k x k x n d displaystyle A d e x e b d sum limits k in N k neq e A d k x k x n d nbsp 如果A d e 0 displaystyle A d e neq 0 nbsp 我们有x e b d A d e k N k e A d k A d e x k 1 A d e x n d displaystyle x e frac b d A d e sum limits k in N k neq e frac A d k A d e x k frac 1 A d e x n d nbsp 将此式代入其他的约束等式以及目标函数 我们就实现了x n d displaystyle x n d nbsp 与x e displaystyle x e nbsp 在基变量和非基变量上的互换 方法步骤 编辑单纯形法的一般解题步骤可归纳如下 把线性规划问题的约束方程组表达成典范型方程组 找出基本可行解作为初始基本可行解 若基本可行解不存在 即约束条件有矛盾 则问题无解 若基本可行解存在 从初始基可行解作为起点 根据最优性条件和可行性条件 引入非基变量取代某一基变量 找出目标函数值更优的另一基本可行解 按步骤3进行迭代 直到对应检验数满足最优性条件 这时目标函数值不能再改善 即得到问题的最优解 若迭代过程中发现问题的目标函数值无界 则终止迭代 最优化过程 编辑如果b向量所有元素非负 则显然我们只需要令所有的变量等于0 就可以得到一个可行解 在这种情况下 通过下述最优化过程 我们可以得到该线性规划的最优解 或者指出该线性规划的最优解为无穷大 不存在 任取一个非基变量x e displaystyle x e nbsp 使得c e gt 0 displaystyle c e gt 0 nbsp 选取一个基变量x d displaystyle x d nbsp 使得A d e gt 0 displaystyle A d e gt 0 nbsp 且最小化b d A d e displaystyle b d A d e nbsp 执行转轴操作pivot d e 并转到第一步继续算法 根据b d A d e displaystyle b d A d e nbsp 的最小性不难证明pivot d e 不会破坏b的非负性 因此将所有变量取0值仍然是可行解 同时 根据D v c e b d A d e 0 displaystyle Delta v c e frac b d A d e geq 0 nbsp 我们发现v一定是不降的 这就达到了更新解的目的 不难发现 算法终止有两种情况 对于所有的非基变量 c均非正 对于某一个e 所有的A d e displaystyle A d e nbsp 均非正 可以证明 对于第一种情况 我们已经得到了该线性规划的最优解 当前的v即为答案 严格证明比较复杂 但是直观上是很容易理解的 因为所有的非基变量都是非负的 而所有的c都是非正的 因此只要某个非基变量不为0 就会使得目标函数更小 对于第二种情况来说 很容易证明此时线性规划的最优解是无穷大 只要让其他所有变量均为0 变量x e displaystyle x e nbsp 为正无穷 由于所有的A d e displaystyle A d e nbsp 都非正 因此非基变量的非负性得到保证 同时由于c e gt 0 displaystyle c e gt 0 nbsp 目标函数值为正无穷 实例 编辑 例 解最优化问题 min Z x 1 x 2 displaystyle min quad Z x 1 x 2 nbsp s t 2 x 1 x 2 x 3 12 displaystyle s t quad 2x 1 x 2 x 3 12 nbsp x 1 2 x 2 x 4 9 displaystyle quad quad quad x 1 2x 2 x 4 9 nbsp x i 0 i 1 2 3 4 displaystyle quad quad quad x i geq 0 i 1 2 3 4 nbsp 列单纯形表 即矩阵 x 1 displaystyle x 1 nbsp x 2 displaystyle x 2 nbsp x 3 displaystyle x 3 nbsp x 4 displaystyle x 4 nbsp bx 3 displaystyle x 3 nbsp 2 1 1 0 12x 4 displaystyle x 4 nbsp 1 2 0 1 9c 1 1 0 0 0从c所在行的正数中最大的一个所对应的变量作为基变量 因为这里两者相等 不妨选为x 1 displaystyle x 1 nbsp 用x 1 displaystyle x 1 nbsp 所在列的正系数除b所在列的数并比较大小 有12 2 6 lt 9 1 9 displaystyle frac 12 2 6 lt frac 9 1 9 nbsp 故取x 3 displaystyle x 3 nbsp 离开基变量 然后对该矩阵进行转轴操作 使x 1 displaystyle x 1 nbsp 所在列变为单位向量 x 1 displaystyle x 1 nbsp x 2 displaystyle x 2 nbsp x 3 displaystyle x 3 nbsp x 4 displaystyle x 4 nbsp bx 1 displaystyle x 1 nbsp 1 1 2 1 2 0 6x 4 displaystyle x 4 nbsp 0 3 2 1 2 1 3c 0 1 2 1 2 0 6令c所在行其余最大的正数所在列的变量x 2 displaystyle x 2 nbsp 进入基变量 并且根据6 1 2 12 gt 3 3 2 2 displaystyle frac 6 1 2 12 gt frac 3 3 2 2 nbsp 令x 4 displaystyle x 4 nbsp 离开基变量 继续进行行变换 得到 x 1 displaystyle x 1 nbsp x 2 displaystyle x 2 nbsp x 3 displaystyle x 3 nbsp x 4 displaystyle x 4 nbsp bx 1 displaystyle x 1 nbsp 1 0 2 3 1 3 5x 2 displaystyle x 2 nbsp 0 1 1 3 2 3 2c 0 0 1 3 1 3 7由于c所在行的所有数均非正 问题结束 最优解为x 1 5 x 2 2 displaystyle x 1 5 x 2 2 nbsp 最优值为Z x 1 x 2 7 displaystyle Z x 1 x 2 7 nbsp 初始化过程 编辑如果b向量并不全为非负 则我们需要通过初始化过程来找到一个可行解 然后才可以使用最优化过程进行优化 当然 此时原线性规划不一定存在可行解 具体的方法是 加入一个新的非基变量x 0 displaystyle x 0 nbsp 并在原线性规划的基础上构造一个新的辅助的线性规划 max x 0 s t 0 i n m x i 0 j B x j b j k N A j k x k x 0 displaystyle begin aligned amp max x 0 amp s t amp forall 0 leq i leq n m x i geq 0 amp forall j in B x j b j sum limits k in N A j k x k x 0 end aligned nbsp 注意这里N集合并不包含x 0 displaystyle x 0 nbsp 然后 选择一个基变量x d displaystyle x d nbsp 使得b d displaystyle b d nbsp 最小 执行转轴操作pivot d 0 不难证明该操作过后所有的b值全部非负 然后 使用前文中所述的最优化过程求解该辅助线性规划 由于x 0 displaystyle x 0 nbsp 非负 因此该线性规划的答案非正 如果答案为负数 则说明原线性规划不可能让所有的基变量都非负 因此原线性规划无可行解 否则 只要令所有变量为0 并去掉x 0 displaystyle x 0 nbsp 变量 就可以得到可行解 在从辅助线性规划转化到原来的线性规划的过程中 如果x 0 displaystyle x 0 nbsp 已经是非基变量 则可以将其从约束条件和目标函数中直接去掉 否则 需要任取一个非基变量x e displaystyle x e nbsp 执行pivot 0 e 将x 0 displaystyle x 0 nbsp 变为非基变量 由于此时x 0 displaystyle x 0 nbsp 是基变量且x 0 0 displaystyle x 0 0 nbsp 故b 0 0 displaystyle b 0 0 nbsp 一定成立 因此这个转轴操作不会破坏b向量的非负性 效率分析 编辑在采用Bland s法则选择用于转轴操作的d和e 相同值的情况下取字典序最小 之后 可以证明单纯形法一定能够在有限步之后终止 但是最坏情况算法的时间复杂度为指數函數级别的 而且可以构造出让单纯形法的时间复杂度达到指数级别的具体实例 不过实践证明在绝大多数情况下单纯形法的效率非常令人满意 单纯形法的最坏时间复杂度为指数级别 并不意味着线性规划不存在多项式级别的算法 椭球算法和内点算法均为解决线性规划的多项式时间算法 参考 编辑Greenberg Harvey J Klee Minty Polytope Shows Exponential Time Complexity of Simplex Method University of Colorado at Denver 1997 PDF download 页面存档备份 存于互联网档案馆 Frederick S Hillier and Gerald J Lieberman Introduction to Operations Research 8th edition McGraw Hill ISBN 0 07 123828 X Thomas H Cormen Charles E Leiserson Ronald L Rivest and Clifford Stein Introduction to Algorithms Second Edition MIT Press and McGraw Hill 2001 ISBN 0 262 03293 7 Section 29 3 The simplex algorithm pp 790 804 IOI2007国家集训队论文 浅谈信息学竞赛中的线性规划 简洁高效的单纯形法实现与应用 作者 李宇骞参看 编辑Nelder Mead方法外部链接 编辑线性规划和单纯形法简介 页面存档备份 存于互联网档案馆 作者Spyros Reveliotis 乔治亚理工 分步单纯形法求解器 页面存档备份 存于互联网档案馆 可以求解线性规划问题 基于Java的交互式单纯形工具 由Argonne国家实验室提供 单纯形法 作者Elmer G Wiens 演示算法细节 使用了单纯形表 单纯形法教程 作者Stefan Waner hofstra edu 单纯形法分解 Mazoo学习网志 取自 https zh wikipedia org w index php title 单纯形法 amp oldid 71010859, 维基百科,wiki,书籍,书籍,图书馆,