单纯形方法

✍ dations ◷ 2025-09-15 17:44:50 #单纯形方法
单纯形法(simplex algorithm)在数学优化领域中常用于线性规划问题的数值求解,由乔治·伯纳德·丹齐格发明。下山单纯形法(Nelder-Mead method)与单纯形法名称相似,但二者关联不大。该方法由Nelder和Mead于1965年发明,是用于优化多维无约束问题的一种数值方法,属于更普遍的搜索算法的类别。这两种方法都使用了单纯形的概念。单纯形是 N {displaystyle N} 维中的 N + 1 {displaystyle N+1} 个顶点的凸包,是一个多胞体:直线上的一个线段,平面上的一个三角形,三维空间中的一个四面体等等,都是单纯形。假设有n个变量和m个约束。线性规划的标准形式如下:所有其他形式的线性规划方程组都可以按照下列方式转化成标准形式:可以将标准形式的线性规划转化为松弛形式,以方便运算。 在原来n个变量,m个约束的线性规划中,加入m个新的变量,将原来的不等式化为等式:x n + j = b j − ∑ 1 ≤ k ≤ n A j , k x k {displaystyle {{x}_{n+j}}={{b}_{j}}-sum limits _{1leq kleq 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 _{kin N}{{{c}_{k}}{{x}_{k}}}\&s.t.\&forall 1leq ileq n+m,{{x}_{i}}geq 0\&forall jin B,{{x}_{j}}={{b}_{j}}-sum limits _{kin N}{{{A}_{j,k}}{{x}_{k}}}\end{aligned}}}因此,线性规划的松弛形式可以由c, A, b, N, B唯一确定,c是长度为n+m的向量,b是长度为m的向量,A是m*(n+m)的矩阵。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 _{kin 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 _{kin N,kneq 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 _{kin N,kneq 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}}} 在基变量和非基变量上的互换。单纯形法的一般解题步骤可归纳如下:如果b向量所有元素非负,则显然我们只需要令所有的变量等于0,就可以得到一个可行解。在这种情况下,通过下述最优化过程,我们可以得到该线性规划的最优解,或者指出该线性规划的最优解为无穷大(不存在)。根据 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一定是不降的。这就达到了更新解的目的。不难发现,算法终止有两种情况:可以证明,对于第一种情况,我们已经得到了该线性规划的最优解。当前的v即为答案。严格证明比较复杂,但是直观上是很容易理解的。因为所有的非基变量都是非负的,而所有的c都是非正的,因此只要某个非基变量不为0,就会使得目标函数更小。对于第二种情况来说,很容易证明此时线性规划的最优解是无穷大。只要让其他所有变量均为0,变量 x e {displaystyle {{x}_{e}}} 为正无穷。由于所有的 A d , e {displaystyle {{A}_{d,e}}} 都非正,因此非基变量的非负性得到保证。同时由于 c e > 0 {displaystyle {{c}_{e}}>0} ,目标函数值为正无穷。例:解最优化问题:min − x 1 − x 2 {displaystyle min quad -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 x_{1}+2x_{2}+x_{4}=9,}x i ≥ 0 , i = 1 , 2 , 3 , 4. {displaystyle x_{i}geq 0,i=1,2,3,4.}列单纯形表(即矩阵):然后从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}} 所在列变成单位向量:接下来令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}} 离开基变量。继续进行行变换,得到由于c所在行的所有数都非正,问题结束。最优解为 x 1 = 5 , x 2 = 2 {displaystyle x_{1}=5,x_{2}=2} ,最优值为 min − x 1 − x 2 = − 7 {displaystyle min -x_{1}-x_{2}=-7} 。如果b向量并不全为非负,则我们需要通过初始化过程来找到一个可行解,然后才可以使用最优化过程进行优化。当然,此时原线性规划不一定存在可行解。具体的方法是,加入一个新的非基变量 x 0 {displaystyle {{x}_{0}}} ,并在原线性规划的基础上构造一个新的辅助的线性规划。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}&max -{{x}_{0}}\&s.t.\&forall 0leq ileq n+m,{{x}_{i}}geq 0\&forall jin B,{{x}_{j}}={{b}_{j}}-(sum limits _{kin N}{{{A}_{j,k}}{{x}_{k}}})+{{x}_{0}}\end{aligned}}} 注意这里N集合并不包含 x 0 {displaystyle {{x}_{0}}} 。然后,选择一个基变量 x d {displaystyle {{x}_{d}}} 使得 b d {displaystyle {{b}_{d}}} 最小,执行转轴操作pivot(d, 0)。不难证明该操作过后所有的b值全部非负。然后,使用前文中所述的最优化过程求解该辅助线性规划。由于 x 0 {displaystyle {{x}_{0}}} 非负,因此该线性规划的答案非正。如果答案为负数,则说明原线性规划不可能让所有的基变量都非负,因此原线性规划无可行解。否则,只要令所有变量为0,并去掉 x 0 {displaystyle {{x}_{0}}} 变量,就可以得到可行解。在从辅助线性规划转化到原来的线性规划的过程中,如果 x 0 {displaystyle {{x}_{0}}} 已经是非基变量,则可以将其从约束条件和目标函数中直接去掉。否则,需要任取一个非基变量 x e {displaystyle {{x}_{e}}} 执行pivot(0, e),将 x 0 {displaystyle {{x}_{0}}} 变为非基变量。由于此时 x 0 {displaystyle {{x}_{0}}} 是基变量且 x 0 = 0 {displaystyle {{x}_{0}}=0} ,故 b 0 = 0 {displaystyle {{b}_{0}}=0} 一定成立,因此这个转轴操作不会破坏b向量的非负性。在采用Bland's法则选择用于转轴操作的d和e(相同值的情况下取字典序最小)之后,可以证明单纯形法一定能够在有限步之后终止,但是最坏情况算法的时间复杂度为指数级别的,而且可以构造出让单纯形法的时间复杂度达到指数级别的具体实例。不过实践证明在绝大多数情况下单纯形法的效率非常令人满意。单纯形法的最坏时间复杂度为指数级别,并不意味着线性规划不存在多项式级别的算法。椭球算法和内点算法均为解决线性规划的多项式时间算法。

相关

  • 爱迪生托马斯·阿尔瓦·爱迪生(英语:Thomas Alva Edison,1847年2月11日-1931年10月18日),科学家、发明家、企业家、工程师,拥有众多重要的发明专利,被传媒授予“门洛帕克的奇才”称号的他,
  • 冯元桢冯元桢(1919年9月15日-2019年12月15日),江苏武进人,生物工程学家、生物力学家,生物力学的创始人,生物医学工程的奠基人。被称为“生物工程之父”。1934年毕业于北京四中。1937年毕
  • 移动进动(precession)是自转物体之自转轴又绕着另一轴旋转的现象,又可称作旋进。在天文学上,又称为“岁差现象”。常见的例子为陀螺。当其自转轴的轴线不再呈铅直时,即自转轴与对称轴
  • Memento mori (消歧义)Memento mori可以指:
  • 约翰·约阿希姆·贝歇尔约翰·约阿希姆·贝歇尔(德语:Johann Joachim Becher,1635年5月6日-1682年10月),德国医生、炼丹术士、学者和探险家。他提出了后世称为燃素说的理论来解释燃烧现象。约翰·贝歇尔
  • thuringiensis苏云金芽孢杆菌(学名:Bacillus thuringiensis,专著中简称为Bt),又称苏力菌,是革兰氏阳性的,芽孢杆菌属陆生习性的细菌。另外, 苏云金芽孢杆菌可寄生在一些蛾类和蝶类的幼虫上,甚至
  • 张干琦张干琦(1961年-)是台湾摄影师,英文名为Chien-Chi Chang,也是台湾唯一马格兰摄影通讯社的会员,已加入美国国籍。他最具代表性的作品是名为《The Chain》的摄影画册,内容是在一家台湾
  • 伊普雷斯期伊普雷斯期是始新世的第一个阶段,常与早始新亚世相对应,不过在某些情况下早始新亚世还包括卢台特期。该阶的起始和终止时间分别为56百万年前和47.8百万年前。该阶以比利时伊佩
  • 硒酸盐硒酸盐是硒酸H2SeO4形成的盐。硒酸根阴离子的符号为SeO2−4。原硒酸盐(游离酸未知)SeO6−6也是已知的。硒酸盐的化学性质类似于硫酸盐。和硫酸盐不同的是,硒酸盐是良好的氧化剂
  • 失蜡法失蜡法(英文lost wax casting),又称脱蜡法,是一种铸造方法,中国古代在青铜器铸造上已经使用这种方法,现代的精密铸造中称为熔模精密铸造。一般用于铸造立体结构非常复杂的、用常见