线性优化之单纯性算法（1）

本人非数学专业，此篇为自己的demo方便以后查看，请各位不吝赐教

---

一. Formulate the problem

Ordinary Form

Standard Form

Why we’d like Standard Form?

将”不规范“的条件以升维的方式转化为“规范”等式条件以及规范不等条件规范？ x>=0; y>=0; z>=0 ;交点都在”坐标轴“，电脑算得巴适得很sum：以空间复杂度换取时间复杂度

二.最优解的刻画

Extreme Point 1）这是从Ordinary Form角度出发的概念，可行域一定为polygen，extreme point 则为可行域的“拐把子点” 2）如果存在最优解，易证，其中必定有一个在extreme point处取到

Basic Feasible Point 1） 这是从Standard Form角度出发的概念 2） 前提：A_m*n；行满秩； * 在n列选出m独立列组成A_B，求得X_B=A_B^-1*b； * 若X_B>=0，则X_B就为一组BFS

Relation 前面说过最值一定在extreme point，但是对计算机来说这种描述问题的方式不太舒服，于是利用前面提到的Standard Form的形式对extreme point在高维度重新进行了刻画，二者为硬币正反面。

只要把所有BFS找到，带进去取最小opt val就行了。如此，我们就大功告成了。但是这么一搞计算量太大，有很多冗余计算，有没有其他的方法呢？

三. 单纯型算法求得最优解

原理（neighbor中选improve最大的）

1）移动方向？ Neighbor: Basic Index 就一个不一样 怎么移动到neighbor？ X‘ = X+thata * d(j) 想从nonbasic挑一个进来得到d_N 通过确保移动后的点在可行域内得到d_B 综上： d(j) = (-A_B^-1 Aj,0…1…0)*

2) 移动成本与抉择？ 成本: C^T * d nonbasic里取成本小于0的当做入基方向 j 3）给到一个入基 j 如何选取出基 i？/ 步长怎么定 theta^* = max{theta>=0 : x+theta * d >= 0} （ 1 ）若 dj均 >=0 (table里j列<0)，=> 则xunbounded

（ 2 ）若存在 dj < 0，chose min{-xi/d, d属于B} xi 对应的 i 即为出基

Degeneracy

如何产生？ 低维度来看：多条线相交于一点，条件冗余。如果一个BFS不是degenerate的，那么迭代完obj一定严格递减，因为线性规划单纯性算法不converge的唯一因素即为degenerate.如果当选择出基变量时有多个indice of basic都取到了最小值，那么算出来的BFS必定为degenerate的。说明移动theta步长后，有多个basic变为0，但只能出去一个，生下来的可不就degenerate了如果一个BFS为degenerate，迭代完有可能obj不变，若逼不得已只能选0那row出基，下一步obj可不就不变了。不变的低维与高维分析一个点经历一次迭代后，opt val未变， 高维：该点到另外一个点，但是opt相同 低维：高维投影到低维来看，虽位置没变，但是“掉了个头”，从一条线转移到了另外一条线了（因为多条线相交为degenerate的原因之所在）Bland’s Rule 如果每次选入基出基都选最小indice 那么： 1）no cylcle will happen 2）可以保证有限次迭代后有最优解

Initialize

Two Phase Method 1）引入人工变量创建新的优化问题，BFS是(0,b) 2）simplex 求解，若opt val不为0，则infesible 3）去掉人工变量，若有0存在，则再从原问题挑能组成独立基的新列，将其值set为0，如此原问题bfs就get了 4）算出新的reduced cost 将上面最后一步的表，人工变量列去掉，若存在0的情况，需要交换row，则选择pivot element将其set为1，此列其余为0，则原始问题的tableau就ok了

Big M Method

表格(富士康流水线表) 。。。略