单纯形法的基本思路

单纯形法的基本求法和思想~

单纯形法
　　simplex method
　　求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。
　　根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。
　　最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。
　　单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。
　　用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。
　　改进单纯形法
　　原单纯形法不是很经济的算法。1953年美国数学家G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。
　　对偶单纯形法
　　1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题为 max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0。即知y＝cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。
　　数学优化中，由George Dantzig发明的单纯形法是线性规划问题的数值求解的流行技术。有一个算法与此无关，但名称类似，它是Nelder-Mead法或称下山单纯形法，由Nelder和Mead发现（1965年），这是用于优化多维无约束问题的一种数值方法，属于更一般的搜索算法的类别。
　　这二者都使用了单纯形的概念，它是N维中的N + 1个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体，等等。

单纯形法是是保证b>=0，通过转轴，使得检验数r>=0来求得最优解，而使用对偶单纯形法的前提是r=0。

我这是从参考资料上弄下来的，有点乱，你最好自己点参考资料查看：
http://www.hebust.edu.cn/jpk/ycx/introduce/images/ksja.doc

单纯形法
§1.3.1 单纯形法的解题思路
由具体例题突出相关概念。
§1.3.2 单纯形法要点和单纯形表
1. 检验数的意义和计算公式

（1.19）
2.单纯形表
表1-5
cj c1 c2 … cm cm+1 … ck … cn
CB XB b x1 x2 … xm xm+1 … xk … xn
c1
c2
…
cm x1
x2
…
xm b1
b2
…
bm 1 0 … 0 a1m+1 … a1k … a1n
0 1 … 0 a2m+1 … a2k … a2n
… … … … … …
0 0 … 1 amm+1 … amk … amn
σj 0 0 … 0 … …

3. 单纯形法的基本法则
法则1 最优性判定法则
法则2 换入变量确定法则
设 ，则xk为换入变量。
法则3 换出变量确定法则
（1.21）
再强调一下，这个法则的目的是，保证下一个基本解的可行性，违背这一法则，下一个基本解一定包含负分量，即不是可行解。
法则4 换基迭代运算法则

表1-6
cj 2 5 0 0 0 θ比
CB XB b x1 x2 x3 x4 x5
0
0
0 x3
x4
x5 8
20
12 1
5
0 2
2
[4] 1
0
0 0
1
0 0
0
1 8/2
20/2
12/4
σj 2 5 0 0 0
0
0
5 x3
x4
x2 2
14
3 [1]
5
0 0
0
1 1
0
0 0
1
0 -1/2
-1/2
1/4 2/1
14/5
—
σj 2 0 0 0 -5/4
2
0
5 x1
x4
x2 2
4
3 1
0
0 0
0
1 1
-5
0 0
1
0 -1/2
2
1/4
σj 0 0 -2 0 -1/4
最优解X*=（2，3，0，4，0）T，z*=2×2+5×3=19。
参考资料：http://www.hebust.edu.cn/jpk/ycx/introduce/images/ksja.doc

---

宝安区13881913475： 什么是运筹学里的单纯形法? - ？
吴背复方：[答案] 单纯形法 simplex method 求解线性规划问题的通用方法.单纯形是美国数学家G.B.丹齐克于1947年首先提出来的.它的理论根据是:线性规划问题的可行域是 n维向量空间Rn中的多面凸集,其最优值如果存在必在该凸集的某顶点处达到.顶点所对应...

宝安区13881913475： 单纯形法的原理是什么 - ？
吴背复方： 单纯形法是一种迭代算法,其基本原理及主要步骤是:首先设法找到一个(初始)基可行解,然后再根据最优性理论判断这个基可行解是否最优解.若是最优解,则输出结果,计算停止;若不是最优解,则设法由当前的基可行解产生一个目标值更优的新的基可行解,再利用最优性理论对所得的新基可行解进行判断,看其是否最优解,这样就构成一个迭代算法.由于基可行解只有有限个,而每次目标值都有所改进,因而必可在有限步内终止.如果原问题确有最优解,必可在有限步内达到,且计算量大大少于穷举法;若原问题无最优解,也可根据最优性理论及时发现,停止计算,避免错误及无效运算.

宝安区13881913475： 单纯形法怎么做? - ？
吴背复方： 单纯形法 求解线性规划问题的通用方法.单纯形是美国数学家G.B.丹齐克于1947年首先提出来的.它的理论根据是:线性规划问题的可行域是 n维向量空间Rn中的多面凸集,其最优值如果存在必在该凸集的某顶点处达到.顶点所对应的可行解...

宝安区13881913475： 线性规划 单纯形法 - ？
吴背复方： 单纯形法的一般解题步骤可归纳如下:①把线性规划问题的约束方程组表达成典范型方程组,找出基本可行解作为初始基本可行解.②若基本可行解不存在,即约束条件有矛盾,则问题无解.③若基本可行解存在,从初始基本可行解作为起点,根据最优性条件和可行性条件,引入非基变量取代某一基变量,找出目标函数值更优的另一基本可行解.④按步骤3进行迭代,直到对应检验数满足最优性条件(这时目标函数值不能再改善),即得到问题的最优解.⑤若迭代过程中发现问题的目标函数值无界,则终止迭代.按照上面说的,如果基本可行解不存在,问题无解了 而且初始解就是“初始可行解” 当然不可能是非可行解

宝安区13881913475： 单纯形法为什么叫做单纯形法 - ？
吴背复方： 单纯形法的基本思想是:先找出一个基本可行解,对它进行鉴别,看是否是最优解;若不是,则按照一定法则转换到另一改进的基本可行解,再鉴别;若仍不是,则再转换,按此重复进行.因基本可行解的个数有限,故经有限次转换必能得出问题的最优解.如果问题无最优解也可用此法判别.

宝安区13881913475： 运筹学单纯形法 - ？
吴背复方： 如果主列中都为负数,就不用再算了,答案为无界解.求解与非基变量前的系数正负没有关系,只与目标函数的形式有关,有Max,Min 两种,如是Max形式,则找检验数时,找最大的一个;如果是Min形式,其他都不用变,找最小的检验数.

宝安区13881913475： 单纯行发的详细步骤?？
吴背复方： 是求解线性规划问题的一种常用基本方法.单纯形法的思路是:根据问题的标准型,从可行域中一个基本可行解(一个顶点)开始,转换到另一个基本可行解(一个顶点),并且使目标函数值增大,当目标函数值达到最大时问题就得到了最优解.单纯形法的特点是:(1)二元情况下满足约束条件的集合是凸多边形,在多元情况下,满足约束条件的集合是凸多面体.(2)目标函数的最大值或最小值恰好在多边型的顶点,在多元情况下,目标函数值一定在凸集的极点上.(3)各极点的值代入目标函数中,进行比较就可以求得极值,即所求得的解.

宝安区13881913475： 单纯形法具体有哪两种方法?？
吴背复方： 大M法,M为任意大正数.还有二阶法

宝安区13881913475： 250分悬赏线性规划问题(单纯形法) - ？
吴背复方： 一、线性规划单纯形法的概念 (一)线性规划单纯形解法的基本思路 若一个凸集仅包含有限个极点,则称此凸集为单纯形.线性规划的可行域是单纯形(证明略,但可以从上节图解...

宝安区13881913475： 谁知道“简单的线性规划问题”的求解过程?？
吴背复方： (一)线性规划单纯形解法的基本思路 若一个凸集仅包含有限个极点,则称此凸集为单纯形. 线性规划的可行域是单纯形(证明略,但可以从上节图解法的例子得到认同),进而线性规划的基可行解又与线性规划问题可行域的极点1-1对应(定...