首页 >
单纯形方法
✍ dations ◷ 2025-04-25 18:56:49 #单纯形方法
单纯形法(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(相同值的情况下取字典序最小)之后,可以证明单纯形法一定能够在有限步之后终止,但是最坏情况算法的时间复杂度为指数级别的,而且可以构造出让单纯形法的时间复杂度达到指数级别的具体实例。不过实践证明在绝大多数情况下单纯形法的效率非常令人满意。单纯形法的最坏时间复杂度为指数级别,并不意味着线性规划不存在多项式级别的算法。椭球算法和内点算法均为解决线性规划的多项式时间算法。
相关
- 支气管扩张支气管扩张(英语:Bronchiectasis)指的是肺脏中支气管永久性的扩张。患者的常见症状包括有痰的慢性咳嗽,其他还有呼吸困难、咳血与胸痛等,有些患者同时也有喘鸣与杵状指(英语:nail c
- 危险素数安全素数是满足2p+1形式的一类数,在这里p也是素数。(相反地,素数p叫做索菲热尔曼素数。)开始的几个安全素数是:之所以叫它们是“安全”素数,是因为它们在加密算法中的运用:某些约数
- 视网膜病变糖尿病视网膜病变(英语:Diabetic retinopathy)是糖尿病的并发症。长期的高血糖环境会损伤视网膜血管的内皮,引起一系列的眼底病变,如微血管瘤、硬性渗出、棉絮斑、新生血管、玻璃
- 内脏内脏,一般是统称人和动物胸腔和腹腔内部的器官。具体主要包括心脏、肝脏、脾脏、肺、肾脏、胃、胆、肠、子宫、卵巢等。各内脏可组成不同系统,包括循环系统、神经系统及呼吸系
- 痕痒痒,中医叫风瘙痒,是一种使动物有对发生部位产生抓挠欲的不快感觉,与疼痛有许多相似之处。其发生多源自周围神经系统(皮痒性和神经性)和中枢神经系统(神经性、神经源性和心理性)。皮
- Hugo Boss雨果博斯(德语:Hugo Boss AG)是一个德国的时尚品牌,主攻高价位男装成衣及配件,创办人是Hugo Ferdinand Boss(1885–1948)。雨果博斯创立于1923年,第一次世界大战之后,发源地在德国斯
- 滑板滑板被称为是“世界上最酷的运动”而究竟是谁第一个创造了滑板已无法考证,但可以确定的是,滑板最初的起源是与加州的冲浪爱好者们有关,冲浪十分受地理与气候条件的影响,于是浪人
- 缅甸总理政治主题缅甸总理曾是缅甸的政府首脑,缅甸于2011年大选后实行议会制,政府首脑职权移交总统,总理一职不再设立。自2016年4月起设立的国务资政被外界视为相当于总理的职务。
- B型流感嗜血菌流感嗜血杆菌(学名:Haemophilus influenzae),简称嗜血杆菌,前称费佛氏杆菌(或译拜菲尔氏菌)或流感杆菌,是一种没有运动力的革兰氏阴性杆菌。它是于1892年由费佛(英语:Richard Friedric
- 夜光藻属夜光藻(学名:Noctiluca scintillans),属于甲藻门单细胞生物(英语:dinoflagellate),俗称海耀,又称夜光虫,在马来西亚和台湾也被称作蓝眼泪,为一种在海中生存的非寄生甲藻,能作生物发光(bio