单纯形法和拟牛顿法五篇范文

第一篇：单纯形法和拟牛顿法

拟牛顿法(Quasi-Newton Methods)是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R.Fletcher和M.J.D.Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。在之后的20年里，拟牛顿方法得到了蓬勃发展，出现了大量的变形公式以及数以百计的相关论文。

拟牛顿法和最速下降法(Steepest Descent Methods)一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法(Newton's Method)更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。

拟牛顿法的基本思想如下。首先构造目标函数在当前迭代$x_k$的二次模型：m_k(p)=f_k+g_k^T p+p^T B_k p/2，这里f_k=f(x_k)，g_k=▽f(x_k)，B_k是一个对称正定矩阵。于是我们取这个二次模型的最优解p_k=-B_k^{-1} g_k作为搜索方向，并且得到新的迭代点x_{k+1}=x_k+a_k p_k，其中我们要求步长a_k满足Wolfe条件。这样的迭代类似与牛顿法，区别就在于用近似的Hesse矩阵B_k代替真实的Hesse矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵B_k的更新。现在假设得到一个新的迭代x_{k+1}，并得到一个新的二次模型：m_{k+1}(p)=f_{k+1}+g_{k+1}^T p + p^T B_{k+1} p/2。我们尽可能地利用上一步的信息来选取B_{k+1}。具体地，我们要求g_{k+1}-g_k=a_k B_{k+1} p_k，从而得到B_{k+1}s_k=y_k，其中s_k=x_{k+1}-x_k，y_k=g_{k+1}-g_k。这个公式被称为割线方程。下面主要介绍这几种方法：DFP方法，BFGS方法，SR1方法，Broyden族方法。

纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。

最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。

单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。

用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得

第二篇：单纯形法理论

单纯形法

单纯形法不用计算函数的导数，只需要计算目标函数的函数值，因此计算比较简单，几何概念也比较清晰，属于直接法的无约束最优化方法。所谓n维欧氏空间E中的单纯形，是指在n维空间中由n1个线性独立的点构成的简单图形或凸多面体。

基本思想：根据问题的维数n选取n1个线性独立的点，然后计算这n1个点的函数值并进行比较，确定其中的最大值的点及函数的下降方向，再设法找到一个新的好点替换函数值最大的点，从而构成新的单纯形。这个过程不断进行，新的单纯形将向极小点收缩。经过若干次迭代后，即可得到满足收敛条件的极小点。

基本过程包括：反射、扩张和压缩。下面以二维问题为例来说明单纯形法的求优过程。设二维函数f(X)在平面上有线性独立的三个点Xh，Xl，Xg，构成单纯形（三角形），计算这三个点的函数值，若

nf(Xh)f(Xg)f(Xl)

则说明Xh是最差点，Xl是最好点，Xg为次差点，迭代应该找出好的点Xr来替换最差点Xh，构成新的单纯形。Xr在Xh与除去最差点Xh以后所有顶点的形心点Xc连线的延长线上进行选取。

XrXc(XcXh)

式中：——反射系数，一般取1。

这个步骤称为反射。通常，反射点Xr的取法是使Xr点Xr点称为最差点Xh的反射点，至Xc点的距离等于Xc点到Xh的距离。

反射点Xr对新单纯形构造的影响，有以下几种情况：（1）扩张

1若反射点的函数值f(Xr)小于最好点的函数值f(Xl)，即当 ○f(Xr)f(Xl)

时，说明所取的方向是正确的，可进一步扩大效果，继续沿XhXr向前进行扩张，在更远处取一点Xe，并满足 XeXc(XrXc)

式中：——扩张系数，1.2~2.0，一般取2.0。

如果f(Xe)f(Xl)，说明扩张有利，就用Xe代替最差点Xh，构成新的单纯形。否则，说明扩张不利，舍弃Xe，仍以Xr代替最差点Xh，构成新的单纯形。

2若f(Xr)f(Xl)不成立，则不能进行扩张，此时如果 ○f(Xr)f(Xg)

则用反射点Xr替换最差点Xh，构成新的单纯形。（2）压缩

1若反射点的函数值f(Xr)小于最差点的函数值f(Xh)，但大于次差点的函数值○f(Xg)，即当

f(Xg)f(Xr)f(Xh)

时，则表示Xr点走得太远，需缩回一些，即进行压缩，并且得到的压缩点应为

XsXc(XrXc)

式中：——压缩系数，常取0.5。这时若f(Xs)f(Xh)

则用压缩点Xs代替最差点Xh，构成新的单纯形。

2若反射点的函数值f(Xr)大于最差点的函数值f(Xh)，即当 ○f(Xr)f(Xh)

时，应当压缩更加多些，即将新点压缩至Xh与Xc之间，这时所得的压缩点应为

XsXc(XcXh)Xc(XhXc)

如果f(Xs)f(Xh)，说明不能沿Xh的反射方向搜索，应进行缩边。（3）缩边

使单纯形向最好点进行收缩，即使最好点Xl不动，其余各顶点皆向Xl移近为原距离的一半。

XiXiXl

i0,1,,n 2从以上各步得到新的单纯形后，再重复开始各步，逐渐缩小单纯形直至满足精度要求为止。

初始单纯形的形成：

构成单纯形的顶点应是线性独立的，否则，如二维问题，三个点在一条直线上，就变成二维问题了，即在一条直线上找极小点的问题，称为退化。为防止退化，一般取成等边三角形，因为它是周长一定前提下包围面积最大的布点方式。

把二维等边三角形推广到n维的情况是n1个点中任两个点的距离都相等，这种单纯形就称为正规单纯形。选取正规单纯形作初始单纯形的方法如下：

给定一个初始点X0[x1,x2,,xn]T，其余n个点可取为：

X1[x1p,x2q,x3q,xnq]T



Xn[x1q,x2q,x3q,xnp]T

即第i个顶点的第i个坐标分量比初始点增加p，其他分量增加q。设正规单纯形任意两顶点的距离等于c，这时p，q的公式推导如下。对于点X2和X1，有X2X1c即

(x1qx1p)2(x2px2q)2(x3qx3q)2(xnqxnq)2c

2化简得

(qp)2(pq)22(pq)2c2

对于X1和X0，有X1X0c，即

(x1px1)2(x2qx2)2(x3qx3)2(xnqxn)2c2

化简得

p2(n1)q2c2

联立求解得 p(n1n1)c

n2(n11)c

n2q初始单纯形也可以采用下面的方法：设目标函数f(X)为n维向量，因此单纯形应有n1个顶点X1，X2，，Xn1。构造单纯形时，现在n维空间中选取初始点X1(0)（尽量靠近最优点），从X1(0)出发沿各坐标轴方向ei、以步长h找到其余n个顶点X(0)j（j2，3，…，n1）：

(0)X(0)Xj1hei

式中：ei——第i个坐标轴的单位向量；

h——步长，一般取值范围为0.5~15.0，接近最优点时要减小。构成初始单纯形的步长可取1.6~1.7。

构成初始单纯形后，可按以下步骤进行：

(k)(k)（1）计算各顶点的函数值并进行比较，找出最好点Xl(k)，最差点Xh，次差点Xg，(k)(k)(k)以及除最差点外其它各点的形心Xn2。求Xh对形心点Xn2的反射点：

(k)(k)(k)(k)Xn3Xn2(Xn2Xh)

(k)(k)(k)(k)（2）比较Xn，如果反射点Xn还好，即进行扩张，得扩张点3和Xl3比最好点Xl为：

(k)(k)(k)(k)Xn4Xn2(Xn3Xn2)

(k)(k)(k)(k)(k)得到扩张点Xn，否则4后，若f(Xn4)f(Xl)，用Xn4代替Xh，并转步骤（5）(k)(k)用Xn代替。X3h后转入步骤（5）(k)(k)若f(Xn3)f(Xl)，即反射点比最好点差，则转下一步。

(k)(k)（3）将反射点Xn3与次差点Xg比较，如果f(Xn3)f(Xg)，则用Xn3代替最(k)(k)(k)差点Xh，并转步骤（5）；若f(Xg)f(Xn3)f(Xh)，则用Xn代替X3h后进行

(k)(k)(k)(k)(k)(k)压缩，否则直接进行压缩，得压缩点为：(k)(k)(k)(k)Xn5Xn2(XhXn2)

(k)(k)(k)(k)(k)（4）求得压缩点Xn后与最差点比较，若，则用Xf(X)f(X)X5hn5hn5代替(k)以后转下一步；否则使单纯形向最好点Xl(k)收缩，收缩后的单纯形顶点为： XhX(jk)Xl(k)0.5(X(jk)Xl(k))

j1，2，…，n1

然后转下一步。

（5）进行收敛性检验。若

1n12(k)(k)f(X)f(X)jn2 n1j1则停止迭代并输出Xl(k)及f(Xl(k))，否则使kk1后转第1步。式中为任意的小(k)数，Xn2为形心。

12例

试用单纯形法求解目标函数f(X)4(x15)2(x26)2的极小值。

Function f=fun(x)syms

x1

x2

f = 4*(x1-5)^2+(x2-6)^2;clear

x1= 0 x2= 0 z=0 e= [1;1] h=1.6 X0=[x1;x2] X1=X0 + h* e X2=X0 + h*e X3=X0 + h*e

第三篇：单纯形法综述

单纯形法综述

zy1415104-曹文亮

单纯形法是1947年由George Bernard Dantzing(1914-2005)创建的，单纯形法的创建标志着线性规划问题的诞生。线性规划问题是研究在线性约束条件下，求线性函数的极值问题。然而，对这类极值问题，经典的极值理论是无能为力的，只有单纯形法才能有效解决这类极值问题的求解。线性规划是数学规划的一个重要分支，也是最早形成的一个分支，线性规划的理论与算法均非常成熟，在实际问题和生产生活中的应用非常广泛；线性规划问题的诞生标志着一个新的应用数学分支——数学规划时代的到来。过去的60年中，数学规划已经成为一门成熟的学科。其理论与方法被应用到经济、金融、军事等各个领域。数学规划领域内，其他重要分支的很多问题是在线性规划理论与算法的基础上建立起来的，同时也是利用线性规划的理论来解决和处理的。由此可见，线性规划问题在整个数学规划和应用数学领域中占有重要地位。因此，研究单纯形法的产生与发展对于认识整个数学规划的发展有重大意义。

单纯形法是从某一基可行解出发，连续地寻找相邻的基可行解，直到达到最优的迭代过程，其实质是解线性方程组。

概述：

根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。

无最优解与无可行解是两个不同的概念。无可行解是指原规划不存在可行解，从几何的角度解释是指 线性规划问题的可行域为空集； 无最优解则是指线性规划问题存在可行解，但是可行解的目标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为无限最优解，或无界解。

无最优解判别定理：在求解极大化的线性规划问题过程中，若某单纯形表的检验行存在某个大于零的检验数，但是该检验数所对应的非基变量的系数列向量的全部系数都为负数或零，则该线性规划问题无最优解。

无穷多最优解判别原理：若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。

退化与循环：如果在一个基本可行解的基变量中至少有一个分量为零，则称此基本可行解是退化的基本可行解。产生的原因：在单纯形法计算中用最小比值原则确定换出变量时，有时存在两个或两个以上相同的最小比值θ，那么在下次迭代中就会出现一个甚至多个基变量等于零。

退化可能出现以下情况：

① 进行进基、出基变换后，虽然改变了基，但没有改变基本可行解（极点），目标函数当然也不会改进。进行若干次基变换后，才脱离退化基本可行解（极点），进入其他基本可行解（极点）。这种情况会增加迭代次数，使单纯形法收敛的速度减慢。

② 在特殊情况下，退化会出现基的循环，一旦出现这样的情况，单纯形迭代将永远停留在同一极点上，因而无法求得最优解。事实上，已经有人给出了循环的例子。

单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。

用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。

求解步骤：

（1）确定初始基可行解

① 从线性规划标准形的系数矩阵中能直接找出m个线性独立的单位向量；

② 对约束条件全为“<=”连接的LP，化为标准形，左端添加松弛变量后即形成一个单位子矩阵；

③ 约束条件中含有“<=”或“=”连接的方程，在插入剩余变量后找不到单位矩阵，则必须采用“人造基”法，也称“人工变量”法。

（2）最优性检验及解的判别准则

① 最优性判定准则 ② 多重最优解判定准则 ③ 无界最优解判定准则（3）换基迭代

① 确定换入变量 ② 确定换出变量 ③ 枢运算（旋转运算）

单纯形法-正文：

根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。

可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。

要缩小对最优解的搜索范围，就必须认识最优解的一般性质，最优解如果存在的话，则它必然处于可行区域的边界上。

任何一项约束条件的边界方程是用“＝”号来替换该约束条件中的“≤”或“≥”号而得到的。每一个边界方程确定一个超平面。因此，可行区域的边界是由那些满足一个或同时满足几个边界方程（即处在作为边界的一个或几个超平面上）的可行解所组成，而且最优解必在其中。最优解不仅是在可行区域的边界上，而且也在这个区域的一个隅角上。一个可行解，如果不处在由另两个可行解连接起来的任何线段上，它就是一个角点可行解。如果连接两个角点可行解的线段处在可行区域的边界上，这两个角点可行解就称为相邻的角点可行解。角点可行解具有下列三个重要性质：①如果存在着一个最优解，那么它必定是角点可行解。如果存在有多个最优解，那么至少有两个最优解必定是相邻的角点可行解。②只存在有限个数的角点可行解。③如果一个角点可行解按目标函数值来衡量时比其所有的相邻角点可行解更好一些，那它就比所有其他角点可行解都更好，也就是最优解。

上述这些性质构成单纯形法的原理基础。最后一个性质的重要性在于它为一个角点可行解是否是最优解提供了一种简便的检验标准，因而毋需列举所有的可行解。单纯形法正是利用了这个性质，只要检查少数的角点可行解，并且一旦这个最优性检验获得通过就可立即停止运算。

单纯形法的运算步骤可归结为：①起始步骤──在一个角点可行解上开始。②迭代步骤──移动至一个更好一些的相邻角点可行解（根据需要反复进行这一步骤）。③停止法则──在当前角点可行解比所有相邻角点可行解都更好些时停止。当前角点可行解就是一个最优解。

单纯形法的优点及其成功之处在于它只需要较少的有限次数的迭代，即可找到最优解。

改进单纯形法：

原单纯形法不是很经济的算法。1953年美国数学家G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。

对偶单纯形法：

（Dual Simplex Method）1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题（Dual Problem）为 max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0。即知y=cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。

对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换——每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量（作为换入变量），使原始问题的非可行解向可行解靠近。

第四篇：单纯形法matlab程序

算法实现与分析

算法1．单纯形法 具体算例：

minz=−3x1+x2+2x3 3x1+2x2−3x3=6 x1−2x2+x3+x5=4

x1,x2,x3≥0标准化后：

min z=−3x1+x2+2x3+Mx4+Mx5

3x1+2x2−3x3+x4=6 x1−2x2+x3+x5=4

x1,x2,x3,x4,x5≥0用单纯形法求解，程序如下： clear clc

M=1000000;

A=[3,2,-3,1,0;1,-2,1,0,1];%系数矩阵 C=[-3,1,2,M,M,0];%价值矩阵 B=[6;4];Xt=[4 5];

for i=1:length(C)-1 D=0;

for j=1:length(Xt)

D=D+A(j,i)*C(Xt(j));

end

xi(i)=C(i)-D;end s=[];

for i=1:length(xi)

if xi(i)<0 s=[s,i];

end end

f=length(s);h=1;

while(f)

for k=1:length(s)j=1;A x=[];

for i=1:length(Xt)

if A(i,s(k))>0 x(j)=i;j=j+1;

end end x

if(length(x)+1==1)break;end y=1 x

for i=1:length(x)

if B(x(i))/A(x(i),s(k))

end end y=x(y);end

y1=Xt(y);%»»³ö±äÁ¿ s k

aa=A(y,s(k))%s(k)Ϊ»»Èë±äÁ¿ A(y,:)=A(y,:)./aa;B(y,:)=B(y,:)./aa;z=[];

for i=1:length(Xt)z=[z,i];end

z z(y)=[];z Xt

for i=1:length(z);yz=-A(z(i),s(k))

A(z(i),:)=A(z(i),:)+A(y,:).*yz B(z(i))B(y)yz

B(z(i))=B(z(i))+B(y).*yz end

for i=1:length(Xt)

if Xt(i)==y1 Xt(i)=s(k);break

end end Xt

disp('ת»»ºó')A=A B=B AB=[A,B];

for i=1:length(C)D=0;

for j=1:length(Xt)D=D+AB(j,i)*C(Xt(j));

end

xi(i)=C(i)-D;

end xi s=[];

for i=1:length(xi)-1

if xi(i)<0 s=[s,i];

end

end s

vpa([A,B;C]);f=length(s);h=h+1;

if h==5

break

end end

-xi(length(xi))

第五篇：单纯形法课程论文

最优化方法课程论文

题目：单纯形法的发展及其应用系别：理学院专业：信息与计算科学姓名：班级：信息

101班

单纯形法的发展及其应用

一． 单纯形法简介：

单纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

二． 单纯形法在线性规划中的应用 1.单纯形法解线性规划问题

在生产管理和经济活动中，经常遇到这些问题，如生产计划问题，即如何合理利用有限的人、财、物等资源，以便得到最好的经济效果；材料利用问题，即如何下料使用材最少；配料问题，即在原料供应量的限制下如何获取最大利润；劳动力安排问题，即如何用最少的劳动力来满足工作的需要；运输问题，即如何制定调运方案，使总运费最小；投资问题，即从投资项目中选取方案，使投资回报最大等等。对于这些问题，都能建立相应的线性规划模型。事实上，线性规划就是利用数学为工具，来研究在一定条件下，如何实现目标最优化。单纯形法是求解线性规划问题的通用方法。

(1)单纯形法解线性规划问题的理论根据是：

线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。

(2)单纯形法的基本思想是：

先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

(3)单纯形法的一般解题步骤可归纳如下：

①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。(4)概述

根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。

最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。

单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。

用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有10^6个决策变量和10^4个约束条件的线性规划问题已能在计算机上解得。

2.线性规划问题的标准化

使用单纯形法求解线性规划时，首先要化问题为标准形式 所谓标准形式是指下列形式：

maxzcj1njxj

naijxjbi(i1,,m)stj1

x0(j1,2,,n)j当实际模型非标准形式时，可以通过以下变换化为标准形式： ①当目标函数为minzcjxj时，可令Z′=-Z，而将其写成为

j1nminzcjxj

j1n求得最终解时，再求逆变换Z=-Z′即可。

②当s·t·中存在ai1x1ai2x2ainxnbi形式的约束条件时，可引进变量

xn1bi(ai1x1ai2x2ainxn)xn10便写原条件成为

ai1x1ai2x2ainxnxn1bi x0n1其中的xn+1称为松驰变量，其作用是化不等式约束为等式约束。同理，若该约束不是用“≤”号连接，而是用“≥”连接，则可引进松驰变量

xn1(ai1x1ai2x2ainxn)bi xn10使原条件写成

ai1x1ainxnxn1bi xn10

3.单纯形法迭代原理（1）确定初始可行解

① 当线性规划问题的所有约束条件均为≤号时，松弛变量对应的系数矩阵即为单位矩阵，以松弛变量为基变量可确定基可行解。

② 对约束条件含≥号或=号时，可构造人工基，人为产生一个m×m单位矩阵用大M法或两阶段法获得初始基可行解。

（2）最优性检验与解的判别（目标函数极大型）

① 当所有变量对应的检验数均非正时，现有的基可行解即为最优解。若存在某个非基变量的检验数为零时，线性规划问题有无穷多最优解；当所有非基变量的检验数均严格小于零时，线性规划问题具有唯一最优解。② 若存在某个非基变量的检验数大于零，而该非基变量对应的系数均非正，则该线性规划问题具有无界解（无最优解）。③ 当存在某些非基变量的检验数大于零，需要找一个新的基可行解，基要进行基变换。

4.确定初始可行解

确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定，为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ中前m个系数列向量恰好构成一个可行基，即Ａ=（ＢＮ），其中Ｂ=（Ｐ1，Ｐ2，„Ｐm）为基变量x1，x2，„xm的系数列向量构成的可行基，Ｎ=(Ｐm+1，Pm+2，„Pn)为非基变量xm+1，xm+2，„xn的系数列向量构成的矩阵。

所以约束方程AX=b就可以表示为AX=(BN)XB=BXB+NXN=b XN用可行基Ｂ的逆阵Ｂ-1左乘等式两端，再通过移项可推得：XB=B-1b-B-1NXN

若令所有非基变量XN=0，则基变量XB=B-1b

B1b由此可得初始的基本可行解X=

0

5.最优性检验

B1b假如已求得一个基本可行解X=将这一基本可行解代入目，0B1b-1标函数，可求得相应的目标函数值Z=CX=(CBCN)=CBBb

0其中CB=(c1,c2,cm), CN=(cm+1,cm+2,cn)分别表示基变量和非基变量所对应的价值系数子向量。

要判定Z=CBB-1b是否已经达到最大值，只需将XB=B-1b-B-1NXN代入目标函数，使目标函数用非基变量表示，即：

XZ=CX=(CBCN)BXN=CBXB+CNXN=CB(B-1b-B-1NXN)+CNXN

CBB-1b+σNXNCBB-1b+(σm+1,σm+1,xm+1xm+2 σn)xn其中N=CN-CBB-1N=(m+1,m+1,n)称为非基变量ＸN的检验向量，它的各个分量称为检验数。若σN的每一个检验数均小于等于0，即σN≤0，那么现在的基本可行解就是最优解。

6.解的判别

定理1：最优解判别定理

对于线性规划问题maxZ=CX,D=XRn/AX=b,X0，若某个基本可行解所对应的检验向量N=CN-CBB-1N0，则这个基本可行解就是最优解。

定理2：无穷多最优解判别定理

B1b若X=是一个基本可行解，所对应的检验向量0N=CN-CBB-1N0，其中存在一个检验数σm+k=0，则线性规划问题有无穷多最优解。定理3：无最优解判别定理

B1b若X=是一个基本可行解，有一个检验数m+k0，但是0B-1Pm+k0，则该线性规划问题无最优解。

7.基本可行解的改进

如果现行的基本可行解Ｘ不是最优解，即在检验向量N=CN-CBB-1N中存在正的检验数，则需在原基本可行解Ｘ的基础上寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是：

（1）先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值）。

（2）再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）。

xm+1xm+2σn)xn由此可得一个新的基本可行解，由ZCBB-1b+(σm+1,σm+1,可知，这样的变换一定能使目标函数值有所增加。

8.换入变量的确定--最大增加原则

把基检验数大于0的非基变量定为入基变量。若有两个以上的σj＞0，则选其中的σj最大者的非基变量为入基变量。

从最优解判别定理知道，当某个σj＞0时，非基变量xj变为基变量不取零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中去（称之为入基变量）。若有两个以上的σj＞0，则为了使目标函数增加得更大些，一般选其中的σj最大者的非基变量为入基变量。

9.换出变量的确定--最小比值原则

把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。

即若

bbxkmini|aik0laikalk

则应令xl出基。其中bi是目前解的基变量取值，aik是进基变量xk所在列的各个系数分量，要求仅对正分量做比，（这由前述作法可知，若aik≤0，则对应的xi不会因xk的增加减值而成为出基变量）。

10.两阶段法

用大M法求解含人工变量的LP时，用手工计算不会碰到麻烦，但用电子计算机求解时，对M就只能在计算机内输入一个机器最大字长的数字，这就可能造成一种计算上的误差，为克服这个困难，对添加人工变量后的LP分两个阶段来计算，称为两阶段法。

第一阶段：不考虑原问题是否存在基可行解，给原LP加入人工变量，并构造仅含人工变量的目标函数Minw,然后用单纯形法求解，若得w=0，说明原LP存在基可行解，可进行第二阶段计算，否则，停止计算。

第二阶段：将第一阶段计算得到的最终单纯形表除去人工变量，将目标函数行的系数换成原LP的目标函数，作为第二阶段计算的初始表。然后按照前面的方法进行计算。

11.大M法

大M法首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位矩阵I，那么已经得到了一个初始可行基。否则在约束方程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向量与其它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初始基，即可求得一个初始的基本可行解。

为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值很大的负系数-Ｍ。这样只要基变量中还存在人工变量，目标函数就不可能实现极大化。

以后的计算与单纯形表解法相同，Ｍ只需认定是一个很大的正数即可。假如在单纯形最优表的基变量中还包含人工变量，则说明原问题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初始基本可行解。

三． 结论 单纯形法的创建标志着线性规划的诞生。单纯形法的创建统一了以往运输问题和营养问题等的算法，同时推进线性规划理论的发展。反过来，理论的发展也刺激算法的更新。线性规划在这样理论与算法相互促进和相互作用中发展。单纯形法有效地提升了数学规划的应用。很多重大理论诞生之初遭到人们的质疑和反对，但是线性规划不一样，一诞生就得到人们的青睐。这是因为，单纯形算法的计算简洁明了，计算结果精确有效。它求出的是最优解，超乎很多人的期望和想象力。因此被各个领域频频应用来提高工作效率、节

约能量和减少损失，使利润最大化。线性规划加速了数学规划的普及。线性规划是有史以来传播速度最快的学科之一。诞生后很快就普及五大洲，并几乎应用到所有的行业，故后兴起的整数规划、二次规划和非线性规划等倍受关注、期待和欢迎。从而，促进了数学规划的普及。