数值最优化之单纯形法学习

2020-05-28

单纯形法的基本思想

先设法找出一个可行基，然后判断他对应的基可行解是不是最优的，如果是，问题解决；如果不是，就设法把现有的可行基换成一个更好的可行基。。。。直到问题解决为止。

两个需要解决的问题：

如何判断一个基可行解是否最优；

二是如何改进基可行解

最优基的判定

不妨设 B=（a₁,...,a_n）

 方程组Ax=b 可以写成：

                                 BxB   +  NX_n   =  b

f的值其实就是带入各个x 的值，然后计算。

上面这个也就是得到的单纯形表。

当λ_{i <= 0的时候，可行基B就是最优基，B对应的解就是最优解。}

(如何理解呢，你可以这样想

 如果f(x₀)比任何一个f(x)都小，那么就是所要求的最优值。f(x₀)对应的值是f_0，所以要达到要任意一个x值对应的函数值是，所以如上，λ应该小于等于0.

 练习题：

 α_i 是x_B 的各个分值。

注意：

 λ和β是相对应的，也可以直接看表，就是x_N 上的检验数大于0.然后这个检验数所在的列式对应的β值

x_{N 才对应着检验数。（可以看下上面关于检验数求法的介绍）}