文档介绍：(simplexalgorithm)数学最优化中,eDantzig发明的单纯形法(simplexalgorithm)是线性规划问题的数值求解的流行技术。有一个算法与此无关,但名称类似,它是Nelder-Mead法或称下山单纯形法,由Nelder和Mead发现(1965年),这是用于优化多维无约束问题的一种数值方法,属于更一般的搜索算法的类别。这二者都使用了单纯形的概念,它是N维中的N+1个顶点的凸包,是一个多胞体:直线上的一个线段,平面上的一个三角形,三维空间中的一个四面体,等等。标准形式以下为线性规划的标准形式,假设有n个变量和m个约束。所有其他形式的线性规划方程组都可以按照下列方式转化成标准形式:?目标函数并非最小化:将所有ck取负。?约束条件中存在大于或等于约束:将约束两边取负。?约束条件中存在等式:将其转化为两个不等式(一个大于等于,一个小于等于)?有的变量没有非负约束:加入新变量x',并用x?x'替换原来的变量x松弛形式可以将标准形式的线性规划转化为松弛形式,以方便运算。在原来n个变量,m个约束的线性规划中,加入m个新的变量,将原来的不等式化为等式:当然,此时依然成立。我们将x1,x2,...,xn这些变量称为基变量,它们构成的集合记为B。将xn+1,xn+2,...,xn+m这些变量称为非基变量,它们构成的集合记为N。简单地理解,非基变量能够由基变量唯一确定。在这样的定义下,线性规划的松弛形式可以写为如下形式:因此,线性规划的松弛形式可以由v,c,A,b,N,B唯一确定,其中v是实数,c和b是长度为n+m的向量,A是(n+m)*(n+m)的矩阵。N,B是整数集合,分别表示非基变量集合以及基变量集合。转轴操作转轴操作是单纯形法中的核心操作,其作用是将一个基变量与一个非基变量进行互换。可以将转轴操作理解为从单纯形上的一个顶点走向另一个顶点。设变量xd属于B(基变量),变量xe属于N(非基变量),执行转轴操作pivot(d,e)之后,xd将变为非基变量,相应地xe将变为基变量。具体地说,一开始我们有移项,得如果,我们有将此式代入其他的约束等式以及目标函数,我们就实现了xd与xe在基变量和非基变量上的互换。最优化过程如果b向量所有元素非负,则显然我们只需要令所有的变量等于0,就可以得到一个可行解。在这种情况下,通过下述最优化过程,我们可以得到该线性规划的最优解,或者指出该线性规划的最优解为无穷大(不存在)。,使得ce>0。,使得Ad,e>0,(d,e),并转到第一步继续算法。根据的最小性不难证明pivot(d,e)不会破坏b的非负性。因此将所有变量取0值仍然是可行解。同时,根据,我们发现v一定是不降的。这就达到了更新解的目的。不难发现,算法终止有两种情况:,c均非正。,所有的Ad,e均非正。可以证明,对于第一种情况,我们已经得到了该线性规划的最优解。当前的v即为答案。严格证明比较复杂,但是直观上是很容易理解的。因为所有的非基变量都是非负的,而所有的c都是非正的,因此只要某个非基变量不为0,就会使得目标函数更小。对于第二种情况来说,很容易证明此时线性规划的最优解是无穷大。只要让其他所有变量均为0,变量xe为正无穷。由于所有的Ad,e都非正,因此非基变量的非负性得到保证。同时由于ce>0,目标函数值为正无穷。实例例:解最优化问题:列单纯形表(即矩阵):x1x2x3x4bx3211012x412019c11000然后从c所在行的正数中最大的一个所对应的变量作为基变量,因为这里两者一样,不妨选为x1。由于拿x1所在列的正系数去除b所在列的数的结果为,故取x3离开基变量。然后对该矩阵进行行变换,使x1所在列变成单位向量:x1x2x3x4bx111/21/206x403/2-1/213c01/2-1/20-6接下来令c所在行的其余的正数中最大的一个所在列的变量x2进入基变量,并且根据,令x4离开基变量。继续进行行变换,得到x1x2x3x4bx1102/3-1/35x201-1/32/32c00-1/3-1/3-7由于c所在行的所有数都非正,问题结束。最优解为x1=5,x2=2,最优值为min?x1?x2=?7。初始化过程如果b向量并不全为非负,则我们需要通过初始化过程来找到一个可行解,然后才可以使用最优化过程进行优化。当然,此时原线性规划不一定存在可行解。具体的方法是,加入一个新的非基变量x0,并在原线性规划的基础上构造一个新的辅助的线性规划。注意这里N集合并不包含x0。然后,选择一个基变量xd使得bd最小,执行转轴操作pivot(d,0)。不难证明该操作过后所有的b值全部非负。然后,使用前文中所述