学习笔记：运筹帷幄之中，决胜千里之外（3）

单纯形法

单纯形法是求解线性规划问题最常用、最有效的算法之一。

1. 单纯形法的基本思路和原理

(1) 单纯形法的基本思路
先找出可行域的一个顶点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一顶点，并使目标函数值更优；如此下去，直到找到某最优解为止。

① 找出一个初始基本可行解

1) 基本概念
基：Am×n是约束条件系数矩阵，秩为m。若Bm×m是A的子阵，且可逆，称B为一个基。基向量：基B中的一列即称为一个基向量。非基向量：在A中除了基B之外的一列称之为基B的非基向量。基变量：与基向量Pi相应的变量Xi叫基变量，基变量有m个。非基变量：与非基向量Pj相应的变量Xj叫非基变量，非基变量有n-m个。

2) 基本解：
若在约束方程组系数矩阵中找到一个基，令其非基变量为零，再求解该m元线性方程组可得到唯一解，该解称之为线性规划的基本解。

3) 可行解：
满足非负条件的基本解叫做基本可行解，并把这样的基叫做可行基。

4) 初始可行基：

5) 第一次找到的可行基为单位矩阵，称之为初始可行基，相应的基本可行解叫初始基本可行解。

② 最优性检验
判断已求得的基本可行解是否是最有解。

1) 最优性检验的依据——检验数σj

2) 最优解判别定理：
求最大目标函数的问题中，若某个基本可行解所有检验数σj≤0，则该解是最优解。

3) 基变换：
具体做法：更换可行基中的一个列向量，得到新的可行基，求出新的基本可行解使目标函数值更优。为了换基要确定换入变量——入基变量与换出变量——出基变量。

4) 入基变量的确定：
当σj＞0，非基变量Xj变为基变量，不取0值可使目标函数值最大，故选基检验数大于0的非基变量换到基变量中。若有两个以上σj＞0，为使目标函数更大，一般选σj较大和的非基变量为入基变量。

5) 出基变量的确定：
方法：把已确定的入基变量在各约束方程中的正系数除其所在约束方程中的常数项，把最小比值所在的约束方程中的原基变量确定为出基变量。确定入基变量后，需在原来的基变量中S1,S2,S3中选一个出基变量。若S3为出基变量，则新的基变量为X2，S1，S2，非基变量X1=S3=0。

2. 求目标函数值最小的线性规划问题的单纯形表解法

(1) 大M法（big M method）
线性规划问题的约束条件(=)等式或（≥）大于型时，使用人工变量法后，寻找其初始基可行解的一种方法。
（2）两阶段法（two-phase method）
是处理人工变量的另一种方法。将加入人工变量后的线性规划划分两阶段求解。

1) 第一阶段：要判断原线性规划是否有基本可行解；

2) 第二阶段：在第一阶段得到的基本可行解的基础上求解原线性规划问题。

3. 几种特殊情况

(1) 无可行解

(2) 无界解
是指在约束条件下目标函数值可以取任意的大。

(3) 无穷多最优解

(4) 退化解
在单纯形法计算过程中，确定出基变量有时存在两个以上的相同的最小比值，这样下一次迭代中就有了一个或几个基变量等于零，这称为退化。

今天的文章学习笔记：运筹帷幄之中，决胜千里之外（3）分享到此就结束了，感谢您的阅读。