Question

单纯形方法详细资料大全

Answer 1

单纯形方法是用线性代数解联立方程所用的叠代法求最优解的方法，是线性规划问题的基本算法。它和代数学中解线性联立方程组的高斯消去法极为相似。

基本介绍

• 中文名 ：单纯形方法
• 外文名 ：Simplex method
• 定义 ：直接、快速的搜寻最小值方法
• 特点 ：收敛速度快，适用面较广
• 领域 ：目标函式的解析性
• 学科 ：数学

简介,基本思想,解题步骤,最最佳化过程,

简介

由George Dantzig发明的单纯形法（simplex algorithm）在数学最佳化领域中常用于线性规划问题的数值求解。 Nelder-Mead 法或称下山单纯形法，与单纯形法名称相似，但二者关联不大。该方法由Nelder和Mead于1965年发明，是用于最佳化多维无约束问题的一种数值方法，属于更普遍的搜寻算法的类别。这两种方法都使用了单纯形的概念。单纯形是N维中的N+1个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体等等，都是单纯形。

基本思想

它的基本思想是：采取逐步接近最优解的办法，先求出一个可行解，但它未必是最优者，然后逐步改善可行解，使目标函式值逐步增大(或减小)，直到目标函式达到极值(最大值或最小值)时，该问题就得到了最优解，或判断无最优解。

解题步骤

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

最最佳化过程

如果b向量所有元素非负，则显然我们只需要令所有的变数等于0，就可以得到一个可行解。在这种情况下，通过下述最最佳化过程，我们可以得到该线性规划的最优解，或者指出该线性规划的最优解为无穷大（不存在）。

1. 任取一个非基变数xe，使得ce>0。
   
2. 选取一个基变数xd，使得Ad,e>0，且最小化bd/Ad。
   
3. 执行转轴操作pivot(d, e)，并转到第一步继续算法。
   

根据bd/Ad的最小性不难证明pivot(d, e)不会破坏b的非负性。因此将所有变数取0值仍然是可行解。同时，根据Δv=ce(bd/Ad),e≥0，我们发现v一定是不降的。这就达到了更新解的目的。 不难发现，算法终止有两种情况：

1. 对于所有的非基变数，c均非正。
   
2. 对于某一个e，所有的Ad均非正。
   

可以证明，对于第一种情况，我们已经得到了该线性规划的最优解。当前的v即为答案。严格证明比较复杂，但是直观上是很容易理解的。因为所有的非基变数都是非负的，而所有的c都是非正的，因此只要某个非基变数不为0，就会使得目标函式更小。 对于第二种情况来说，很容易证明此时线性规划的最优解是无穷大。只要让其他所有变数均为0，变数xe为正无穷。由于所有的Ad都非正，因此非基变数的非负性得到保证。同时由于ce>0，目标函式值为正无穷。