单纯形法 (simplex algorithm)在数学优化领域中常用于线性规划 问题的数值求解 ,由喬治·伯納德·丹齊格 发明。
下山单纯形法(Nelder-Mead method)与单纯形法名称相似,但二者关联不大。该方法由Nelder和Mead于1965年发明,是用于优化多维无约束问题的一种数值方法,属于更普遍的搜索算法 的类别。这两种方法都使用了单纯形 的概念。单纯形 是 N {\displaystyle N} 维中的 N + 1 {\displaystyle N+1} 个顶点 的凸包 ,是一个多胞体 :直线上的一个线段,平面上的一个三角形,三维空间中的一个四面体 等等,都是单纯形。
标准形式 编辑
假设有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}&&\max \sum \limits _{1\leq k\leq n}{{{c}_{k}}{{x}_{k}}}\\&s.t.&\sum \limits _{1\leq k\leq n}{{{A}_{1,k}}{{x}_{k}}}\leq {{b}_{1}},\\&&\sum \limits _{1\leq k\leq n}{{{A}_{2,k}}{{x}_{k}}\leq {{b}_{2}},}\\&...\\&&\sum \limits _{1\leq k\leq n}{{{A}_{m,k}}{{x}_{k}}}\leq {{b}_{m}}\\&&{{x}_{1}},{{x}_{2,}}...,{{x}_{n}}\geq 0\end{aligned}}} 所有其他形式的线性规划方程组都可以按照下列方式转化成标准形式:
目标函数 并非最大化:将所有 c k {\displaystyle {{c}_{k}}} 取负。约束条件中存在大于或等于约束:将约束两边取负。 约束条件中存在等式 :将其拆分为两个不等式 (一个大于等于,一个小于等于) 有的变量没有非负约束:加入新变量 x ′ , x ″ ( x ′ , x ″ >= 0 ) {\displaystyle x',x''(x',x''>=0)} 并用 x ′ − x ″ {\displaystyle x'-x''} 替换原来的变量 x {\displaystyle x} 松弛形式 编辑
可以将标准形式的线性规划转化为松弛形式,以方便运算。在原来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}}}}
当然,此时 x n + j ≥ 0 {\displaystyle {{x}_{n+j}}\geq 0} 依然成立。
我们将 x 1 , x 2 , . . . , x n {\displaystyle {{x}_{1}},{{x}_{2}},...,{{x}_{n}}} 这些变量称为非基变量 ,它们构成的集合 记为N。将 x n + 1 , x n + 2 , . . . , x n + m {\displaystyle {{x}_{n+1}},{{x}_{n+2}},...,{{x}_{n+m}}} 这些变量称为基变量 ,它们构成的集合记为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}&\max \sum \limits _{k\in N}{{{c}_{k}}{{x}_{k}}}\\&s.t.\\&\forall 1\leq i\leq n+m,{{x}_{i}}\geq 0\\&\forall j\in B,{{x}_{j}}={{b}_{j}}-\sum \limits _{k\in N}{{{A}_{j,k}}{{x}_{k}}}\\\end{aligned}}}
因此,线性规划的松弛形式可以由 c , A , b , N , B {\displaystyle c,A,b,N,B} 唯一确定, c {\displaystyle c} 是长度为n的向量 , b {\displaystyle b} 是长度为m的向量 , A {\displaystyle A} 是m*(n+m)的矩阵 。 N , B {\displaystyle N,B} 是整数 集合,分别表示非基变量集合以及基变量集合。
转轴操作 编辑
转轴操作 是单纯形法中的核心操作,其作用是将一个基变量与一个非基变量进行互换。可以将转轴操作理解为从单纯形 上的一个顶点 走向另一个顶点。
设变量 x n + d {\displaystyle {{x}_{n+d}}} 属于B(基变量),变量 x e {\displaystyle {{x}_{e}}} 属于N(非基变量),执行转轴操作pivot(d,e)之后, x n + d {\displaystyle {{x}_{n+d}}} 将变为非基变量,相应地 x e {\displaystyle {{x}_{e}}} 将变为基变量。
具体地说,一开始我们有
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}}}}
移项,得
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}}
如果 A d , e ≠ 0 {\displaystyle {{A}_{d,e}}\neq 0} ,我们有
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}}}
将此式代入其他的约束等式以及目标函数,我们就实现了 x n + d {\displaystyle {{x}_{n+d}}} 与 x e {\displaystyle {{x}_{e}}} 在基变量和非基变量上的互换。
方法步骤 编辑
单纯形法的一般解题步骤可归纳如下:
把线性规划问题的约束方程组表达成典范型方程组,找出基本可行解作为初始基本可行解。 若基本可行解不存在,即约束条件有矛盾,则问题无解。 若基本可行解存在,从初始基本可行解作为起点,根据最优性条件和可行性条件,引入非基变量取代某一基变量,找出目标函数值更优的另一基本可行解。 按步骤3进行迭代,直到对应检验数满足最优性条件(这时目标函数值不能再改善),即得到问题的最优解。 若迭代过程中发现问题的目标函数值无界,则终止迭代。 最优化过程 编辑
如果b向量所有元素非负,则显然我们只需要令所有的变量等于0,就可以得到一个可行解。在这种情况下,通过下述最优化 过程,我们可以得到该线性规划的最优解,或者指出该线性规划的最优解为无穷大 (不存在)。
任取一个非基变量 x e {\displaystyle {{x}_{e}}} ,使得 c e > 0 {\displaystyle {{c}_{e}}>0} 。 选取一个基变量 x d {\displaystyle {{x}_{d}}} ,使得 A d , e > 0 {\displaystyle {{A}_{d,e}}>0} ,且最小化 b d / A d , e {\displaystyle {{b}_{d}}/{{A}_{d,e}}\;} 执行转轴操作pivot(d, e),并转到第一步继续算法。 根据 b d / A d , e {\displaystyle {{b}_{d}}/{{A}_{d,e}}\;} 的最小性不难证明pivot(d, e)不会破坏b的非负性。因此将所有变量取0值仍然是可行解。同时,根据 Δ v = c e b d A d , e ≥ 0 {\displaystyle \Delta v={{c}_{e}}{\frac {{b}_{d}}{{A}_{d,e}}}\geq 0} ,我们发现v一定是不降的。这就达到了更新解的目的。
不难发现,算法终止有两种情况:
对于所有的非基变量,c均非正。 对于某一个e,所有的 A d , e {\displaystyle {{A}_{d,e}}} 均非正。 可以证明,对于第一种情况,我们已经得到了该线性规划的最优解。当前的v即为答案。严格证明比较复杂,但是直观上是很容易理解的。因为所有的非基变量都是非负的,而所有的c都是非正的,因此只要某个非基变量不为0,就会使得目标函数更小。
对于第二种情况来说,很容易证明此时线性规划的最优解是无穷大。只要让其他所有变量均为0,变量 x e {\displaystyle {{x}_{e}}} 为正无穷。由于所有的 A d , e {\displaystyle {{A}_{d,e}}} 都非正,因此非基变量的非负性得到保证。同时由于 c e > 0 {\displaystyle {{c}_{e}}>0} ,目标函数值为正无穷。
实例 编辑 例:解最优化问题:
min Z = − x 1 − x 2 {\displaystyle \min \quad Z=-x_{1}-x_{2}}
s . t . 2 x 1 + x 2 + x 3 = 12 , {\displaystyle s.t.\quad 2x_{1}+x_{2}+x_{3}=12,}
x 1 + 2 x 2 + x 4 = 9 , {\displaystyle \quad \quad \quad x_{1}+2x_{2}+x_{4}=9,}
x i ≥ 0 , i = 1 , 2 , 3 , 4. {\displaystyle \quad \quad \quad x_{i}\geq 0,i=1,2,3,4.}
列单纯形表(即矩阵):
x 1 {\displaystyle x_{1}} x 2 {\displaystyle x_{2}} x 3 {\displaystyle x_{3}} x 4 {\displaystyle x_{4}} b x 3 {\displaystyle x_{3}} 2 1 1 0 12 x 4 {\displaystyle x_{4}} 1 2 0 1 9 c 1 1 0 0 0
从c所在行的正数中最大的一个所对应的变量作为基变量,因为这里两者相等,不妨选为 x 1 {\displaystyle x_{1}} 。
用 x 1 {\displaystyle x_{1}} 所在列的正系数除b所在列的数并比较大小,有 12 2 = 6 < 9 1 = 9 {\displaystyle {\frac {12}{2}}=6<{\frac {9}{1}}=9} ,故取 x 3 {\displaystyle x_{3}} 离开基变量。
然后对该矩阵进行转轴操作,使 x 1 {\displaystyle x_{1}} 所在列变为单位向量:
x 1 {\displaystyle x_{1}} x 2 {\displaystyle x_{2}} x 3 {\displaystyle x_{3}} x 4 {\displaystyle x_{4}} b x 1 {\displaystyle x_{1}} 1 1/2 1/2 0 6 x 4 {\displaystyle x_{4}} 0 3/2 -1/2 1 3 c 0 1/2 -1/2 0 -6
令c所在行其余最大的正数所在列的变量 x 2 {\displaystyle x_{2}} 进入基变量,并且根据 6 1 / 2 = 12 > 3 3 / 2 = 2 {\displaystyle {\frac {6}{1/2}}=12>{\frac {3}{3/2}}=2} ,令 x 4 {\displaystyle x_{4}} 离开基变量。
继续进行行变换,得到
x 1 {\displaystyle x_{1}} x 2 {\displaystyle x_{2}} x 3 {\displaystyle x_{3}} x 4 {\displaystyle x_{4}} b x 1 {\displaystyle x_{1}} 1 0 2/3 -1/3 5 x 2 {\displaystyle x_{2}} 0 1 -1/3 2/3 2 c 0 0 -1/3 -1/3 -7
由于c所在行的所有数均非正,问题结束。最优解为 x 1 = 5 , x 2 = 2 {\displaystyle x_{1}=5,x_{2}=2} ,最优值为 Z = − x 1 − x 2 = − 7 {\displaystyle Z=-x_{1}-x_{2}=-7} 。
初始化过程 编辑 效率分析 编辑 在采用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国家集训队论文,《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》,作者:李宇骞 参看 编辑 外部链接 编辑