单纯形法

第一篇：单纯形法

       单纯形法

       可按现代电子计算机标准程序求解线性规划模型的一般方法。分为代数形式的单纯形法和表格形式的单纯形法。前者提供基本算法所依据的逻辑规则，适用于在电子计算机上进行求解运算；后者将变量和数据列成表格，适用于笔算。两者在数学上是等价的。单纯形法是由美国数学家G.B.丹齐克（1914～）于1947年提出来的，它与苏联数学家Л.Β.坎托罗维奇（1912～）于1938年提出的解乘数法相类似。

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

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

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

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

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

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

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

       单纯形法的提出及依据

       单纯形法是美国数学家George Dantzig于1947年首先提出的。

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

       单纯形法的基本思想

       单纯形法是一种多变量函数的寻优方法，其主要思想是先找一个基本可行解，判断是否为最优解，如果不是则找另外一个解，再进行判定，如此迭代运算，直至找到最优解或者判定其无界。单纯形法的特点

       单纯形法是一种直接、快速的搜索最小值方法，其优点是对目标函数的解析性没有要求，收敛速度快，适用面较广。

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

       1.把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。

       2.若基本可行解不存在，即约束条件有矛盾，则问题无解。

       3.若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。

       4.按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。

       5.若迭代过程中发现问题的目标函数值无界，则终止迭代。改进的单纯形法

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

       改进的单纯形法是在单纯形操作中引入变异操作，以此来增强全局搜索能力。具体做法是：

       首先，进行基本单纯形法操作，快速得到局部极小值，再对极小值点在取值范围内进行变异操作，并重新进行基本单纯形法操作，直到得到最优解为止。该算法的计算步骤如下：

       (1)选取初始单纯形，初始步长L，最大变异次数mmax，计数器m=0；

       (2)进行基本单纯形操作，找到一个极值点X1；

       (3)以极值点臵作新的顶点，再选取初始单纯形，并进行新一轮的单纯形操作，得到新的极值点，两极值点对应的目标函数为R1,R2；

       (4)若R1 > R2,R1 = R2,X1 = X2，代入：

       (i=1,2,…,t)(1)

       式中，Ximax、Ximin为参数X_i的上、下限；为0到1之间的随机数。

       (5)若，对进行变异操作，计数器m=m 1：

       (6)若计数器m < mmax，转(1)，否则输出结果X1。参考文献

       1.刘勇,陈国东.基于单纯形法的LINGO求解一般指派问题的探讨[J].中国管理信息化.2022(6)

       2.李春风,许承权,蒲文利.改进的单纯形法及其在非线性参数估计中的应用[J].海洋测绘,2022,29(6)

       在数学 最优化理论 单纯形算法由创造 美国 数学家 乔治Dantzig 在 1947是普遍 算法 为 数字 解答 线性规划 问题。学报 计算在科学和设计 列出它作为世纪的名列前茅10种算法之一。

       一个无关，但相似地名为方法是 Nelder-Mead方法 或 下坡单纯形法 归结于Nelder & Mead(1965)和a 数字方法 为优选许多尺寸 跌宕的问题，属于更加一般的类 搜索算法.[1]在两种情况下，方法使用a的概念 单缸是a polytope N 1端点 N 维度： a 线段 在一个维度，a 三角 在二个维度，a 四面体 在三维空间等等。

第二篇：单纯形法

       单纯形法

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

       概述

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

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

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

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

       改进单纯形法

       原单纯形法不是很经济的算法。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（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。

       其他信息

       数学优化中，由George Dantzig发明的单纯形法是线性规划问题的数值求解的流行技术。有一个算法与此无关，但名称类似，它是Nelder-Mead法或称下山单纯形法，由Nelder和Mead发现（1965年），这是用于优化多维无约束问题的一种数值方法，属于更一般的搜索算法的类别。

       这二者都使用了单纯形的概念，它是N维中的N 1个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体，等等。

第三篇：单纯形法

       单纯形法（不可以解空集问题，无初始解）

       一、单纯形法的基本思想

       1、顶点的逐步转移

       即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。

       2．需要解决的问题：

       (1)为了使目标函数逐步变优，怎麽转移？

       (2)目标函数何时达到最优——判断标准是什么？

       （3）初始解的寻找

       二、单纯形法原理（用代数方法求解LP）

       第一步：引入非负的松弛变量（x3 x4 x5）和剩余变量（算完后剩余的资源）

       x3,x4,x5, 将该LP化为标准型 第二步：寻求初始可行基（单位阵对应的），确定基变量

       第三步：写出初始基本可行解（很多之中找一个，必令原x为0）和相应的目标函数值 两个关键的基本表达式：

       ① 用非基变量表示基变量的表达式 ② 用非基变量表示目标函数的表达式

       第四步：分析两个基本表达式，看看目标函数是否可以改善？

       ①

       分析用非基变量表示目标函数的表达式

       非基变量前面的系数均为正数（必为负数才可以），所以任何一个非基变量进基都能使Z值增加

       通常把非基变量前面的系数叫“检验数” ② 选哪一个非基变量进基？

       排在最前面的负检验数对应的非基变量 ③ 确定出基变量

       “最小比值原则”（或θ原则）见本 如果x2≤0，会出现什麽问题？

       最小比值原则会失效！ 基变换

       新的基变量——x2, x3,x4；新的非基变量x1, x5 ； 写出用非基变量表示基变量的表达式： 可得新的基本可行解（）X1=（0,3,2,16,0）T

       ⑤ 写出用非基变量表示目标函数的表达式: 检验数仍有正的

       第五步：上述过程何时停止？

       当用非基变量表示目标函数的表达式中，非基变量的系数（检验数）全部非正（0时表无穷解，负时表唯一解）时，当前的基本可行解就是最优解!

       为什麽？

       分析用非基变量表示目标函数的表达式，如果让负检验数所对应的变量进基，目标函数值将下降！

       （2）表格设计依据：

       将-Z看作不参与基变换的基变量，把目标函数表达式改写成方程的形式，和原有的m个约束方程组成一个具有n m 1个变量、m 1个方程的方程组：

       a11x1a12x2a1nxnxn1b1axaxaxxb2112222nnn22axaxaxxbmnnnmmm11m22Zc1x1c2x2cnxncn1xn1cnmxnm0取出系数写成增广矩阵的形式：

       0a11a120a21a220am1am21cc21a1na2namncn100010001cn1cn2cnmb1b2bm0

       -Z，Xn 1，…，Xn m所对应的系数

       列向量构成一个基

       用矩阵的初等行变换将该基变成单位阵,这时

       变成0，相应的增广矩阵变成如下形式：

       a22a2n

       

       am2amn

       2n

       其中，j=1，2，…，n ；

       m0z0cnibi

       i1 0a110a210am111a12a1n100b1010b2001bm000z0增广矩阵的最后一行就是用非基变量表示目标函数的表达式，(j=1,2,…,n)就是非基变量的检验数。

       （3）检验数的两种计算方法：

       ①利用矩阵的行变换，把目标函数表达式中基变量前面的系数变为0；

       ②使用计算公式——jcjci1mniijacjCBPjcjzj,j1,2,,n

       从最优表可知: 该LP的

       最优解是X*=(4,2,0,0,4)T

       相应的目标函数最优值是Zmax=14

第四篇：单纯形法

       运用单纯形法最优化气相色谱操作条件

       单纯形是指多维空间的一种凸图形，它的定点数仅比空间的维数多1。例如，二因素单纯形是一个三角形，三因素空间的单纯形为一四面体。n个因素空间的单纯形是n 1个点构成的超多面体。

       自从从1962年Spendley等首先将基本单纯形发（BSM）引入化学领域手，不少学者从不同角度对单纯形优化方法做了进一步研究，相继提出了改进单纯形法（MSM），超改进单纯形发（SMS）、控制加权形心超改进单纯形法（CWCSMS），加权形心单纯形法（WCM）、体积不变单纯形法、超改进控制加权形心单纯形法（SMCWC）和新改进单纯形优化方法（NMS）[1]，上述各种方法各有特点。在目前气相色谱中应用最多的是改进单纯形法（MSM）[2]。下面我们主要应用改进单纯形法对以柱温为主要操作条件的气相色谱进行优化。

       先在初始单纯形BNW，如图1，的三个顶点所对应的条件下进行实验，所得到的响应以B点最好，N点次之，W点最差。

       图1 MSM单纯形的移动

       为了寻找最佳点，我们向最差点的反对称方向进行搜索。以P为除W点以外所保留各点的重心（此处即BN的中点），在WP的延长线上取一新点R，使得：

       RP(PW)

       (1-1)式中，称为反映系数，一般取一；R称为W点于P的反射点。此步骤称为“反映”。

       在R点进行实验，其测得的响应值有三种可能。

       1.在R点的响应比B点的响应更好，则“扩大”产生新点E,使

       EPr(PW)

       (1-2)式中，r称为扩大系数，一般取r＝1.2～2.0，当r＝2，EP2(PW)

       (1-3)

       若E点的响应比B点的响应好，则保留E，以BNE为新的单纯形再开始，如果E点的响应不比B的好，扩大失败，则以BNR为新的单纯形开始。

       2.若R点的响应处于B点和N点的响应之间，既不扩大也不缩小，则以BNR为新单纯形再开始。

       3.若R的响应比N点的响应差，则缩小产生新点。

       A.若R点的响应比N点的差，但比W点的好，则新点Cr较靠近R点，再以BNCr开始：

       CrP(PW)

       (1-4)称为缩小系数，常取0.5，即：

       CrP0.5(PW)

       (1-5)B.若R点的响应在新单纯形中也是最差的，则保留Cw点，而改为放弃N点再做。

       CwP(PW)

       (1-6)称为缩小系数，常取0.5，即：

       CwP0.5(PW)

       (1-7)4.如果WP方向上所有点的响应值皆比W点差，则不能沿此方向搜索。这时，可以进行整体收缩。以原单纯形BNW中最好的点B为中心进行缩边，即使顶点W，N向B移动一半距离。见图2。得到新的单纯形BN'W'，再开始优化实验。

       图2 单纯形整体收缩

       按照以上规则和步骤，连续实验，直到满足某种收敛指标。通常采用如下的收敛准则：

       R(B)R(W)R(B)2

       (1-8)式中，R（B）及R（W）分别为最好点B和最差点W的响应值；2为预先给定的允许误差。

       我们采用两色谱峰的分离度为响应值。分离度定义为两个组分的保留值之差与其平均峰宽之比表示。参考文献

       [1] 邓勃，闵顺耕.几种单纯形优化方法优化性能的比较研究[J].分析化学，1994，(03)：272-277.[2] 许国旺.现代实用气相色谱法[M].北京：化学工业出版社，2022.

第五篇：单纯形法

       public class Linear{ public static double[] c={-3,-2,0,0,0,0};public double W(double x[]){return c[0]*x[0] c[1]*x[1] c[2]*x[2] c[3]*x[3] c[4]*x[4] c[5];} public static int cmin(double c1[]){ int min=0,i;for(i=0;i<5;i )if(c1[min]>c1[i])min=i;return min;} public int xmin(double a,double b,double c){double []x={0,0,0};int min,i;x[0]=a;x[1]=b;x[2]=c;if(a>0)

       {min=0;

       for(i=1;i<3;i )

       if(x[min]>x[i]&&x[i]>0)min=i;

       } else if(b>0)

       {min=1;

       if(x[min]>x[2]&&x[2]>0)min=2;

       } else

       min=2;

       return min;} public static void main(String[]args){ Linear Linear=new Linear();double []x={0,0,10,24,8};int i,l,r,j,t;double cl;double [] al={0,0,0};double W=0;double[][] a={{2,1,1,0,0},{3,3,0,1,0},{2,0,0,0,1}};double[] b={10,24,8};double[] c={-3,-2,0,0,0,0};W=Linear.W(x);System.out.println(“ x1 ” “ ” “x2” “

       ” “x3” “

       ” “x5” “

       ” “W”);System.out.println(x[0] “ ” x[1] “ ” x[2] “ ” x[3] “ ” W);while(c[0]<0||c[1]<0||c[2]<0||c[3]<0||c[4]<0){ l=(int)cmin(c);

       r=(int)Linear.xmin(b[0]/a[0][l],b[1]/a[1][l],b[2]/a[2][l]);

       cl=c[l];

       c[5]=c[5] b[r]*c[l]/a[r][l];

       for(i=0;i<5;i )

       c[i]=c[i]-a[r][i]*cl/a[r][l];

       for(j=0;j<3;j )

       {

       if(j==r)

       {al[j]=a[j][l];

       b[j]=b[j]/al[j];

       for(i=0;i<5;i )

       a[j][i]=a[j][i]/al[j];

       }

       else

       { al[j]=a[j][l];

       “ ”x4“ ” “ x[4] ”

       b[j]=b[j]-b[r]*al[j]/a[r][l];

       for(i=0;i<5;i )

       a[j][i]=a[j][i]-a[r][i]*al[j]/a[r][l];

       }

       } for(j=0;j<3;j )

       for(i=0;i<5;i )

       {if(c[i]==0&&a[j][i]!=0)

       { t=j;

       x[i]=b[t]/a[t][i];

       }

       if(c[i]!=0)x[i]=0;} W=Linear.W(x);System.out.println(x[0] “ ” x[1] “ ” x[2] “ ” x[3] “ ” W);} System.out.println(“最优解：” “W*=-Wmin=” -W);} }

       “ x[4] ”