单纯形法

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

(重定向自简捷法)

单纯形法(Simplex Method)

目录

单纯形法的提出及依据[1]

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

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

单纯形法的基本思想

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

单纯形法的特点

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

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

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

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

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

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

  5.若迭代过程中发现问题的目标函数值无界,则终止迭代。

改进的单纯形法[2]

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

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

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

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

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

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

  (4)若R1 > R2,R1 = R2,X1 = X2,

  代入:X_i=X_i+\S_i(X_i{\max}-X_i{\min})  (i=1,2,…,t)(1)

式中,XimaxXimin为参数X_i的上、下限;\S_i为0到1之间的随机数。

  (5)若R_1\le R_2,对进行变异操作,计数器m=m+1:

  (6)若计数器m < mmax,转(1),否则输出结果X1

实例

Image:Ddd1.jpg

即求max:x1+x2,列单纯形表(即矩阵):

Image:Ddd2.jpg

Image:Ddd3.jpg

单纯形法原理

原理1,根据方程组消元法对矩阵进行行变换,变换后约束条件等价不变。如以上实例。

原理2,令非基变量为0,此时基变量的取值满足约束条件。单纯形法正是通过消元法交换基变量和非基变量,令非基变量为0,以求达到目标函数最优值的基变量组合。基变量即为系数为1,0的变量。 图解如下: 初始,将非基变量和基变量分为各自两部分,

Image:Ddd9.jpg

对矩阵进行行变换,

Image:Ddd8.jpg

如图所示,令非基变量为0,此时基变量的取值仍满足约束条件。基变量的取值为Image:Latex.gif

原理3,对实例中c行的变换的解释: 将基变量用非基变量表示如下图,

Image:Ddd7.jpg

x1到xm即基变量。

Image:Ddd6.jpg

Image:Ddd5.jpg

c行所进行的变换就是求上图中的Image:Latex22.gif

显然当Image:Latex22.gif的累加值小于0时,令非基变量为0则Z(实例中x1+x2)达到最大。

参考文献

  1. 刘勇,陈国东.基于单纯形法的LINGO求解一般指派问题的探讨[J].中国管理信息化.2008(6)
  2. 李春风,许承权,蒲文利.改进的单纯形法及其在非线性参数估计中的应用[J].海洋测绘,2009,29(6)
本条目对我有帮助19
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您认为本条目还有待完善,需要补充新内容或修改错误内容,请编辑条目

本条目由以下用户参与贡献

Yixi,卓奕涛.

评论(共1条)

提示:评论内容为网友针对条目"单纯形法"展开的讨论,与本站观点立场无关。
Lvshaofei (Talk | 贡献) 在 2011年3月2日 23:31 发表

很具体,很实用

回复评论

发表评论请文明上网,理性发言并遵守有关规定。

打开APP

以上内容根据网友推荐自动排序生成