单纯形学习笔记
Ruizhangj
·
·
个人记录
单纯形
一般形式
单纯形有如下形式：
\max \sum_{i=1}^{n} a_ix_i\\
\forall 1\le i\le m,\sum_{j=1}^{n}b_{i,j}x_j\le c_i\\
\forall 1\le i\le n,x_i \ge 0
不妨引入m个变量x_{n+1},\dots,x_{n+m}来完成第二个限制，于是变成：
\max \sum_{i=1}^{n} a_ix_i\\
\forall 1\le i\le m,x_{n+i}=c_i-\sum_{j=1}^{n}b_{i,j}x_j\\
\forall 1\le i\le n+m,x_i \ge 0
基本思想
定义\max后面的那n个x_i叫做非基变量，用于表示限制的m个x_{n+i}叫做基变量。我们发现，其实基变量和非基变量之间是可以互相替换的，定义一个过程\text{pivot}(N,B)表示将非基变量x_N和基变量x_B互相替换，可以理解为把下面的方程变形，用x_B表示x_N，然后把每一条方程以及\max中的x_N带入替换，这样x_B,x_N就交换了身份，当然\max中可能会出现常数，不过可以直接提出，这样还是满足那个形式。
这么做的目的是想让所有的a_i\le0，且所有的c_i\ge 0，这样所有的x_i=0就是最优解了。
关于\text{pivot}，如下：
\text{pivot(N,B)}:x_N=\frac{c_B-\sum_{j=1 \land j\not =N}^{n}b_{B,j}x_j-x_B}{b_{B,N}}
具体内容
不过事情并没有那么简单，有各种情况是要特殊处理的，以及\text{pivot(N,B)}中的N,B怎么选取也还没有解决，上面的都是一个比较好的假设。
操作步骤
如何\text{pivot}
先来考虑\text{pivot(N,B)}。首先a_i\le 0的x_i是不用\text{pivot}的，因为它已经符合我们的期望，那么挑选出一个a_N>0的x_N作为非基变量。接着挑选x_B，我们找到一个\frac{c_i}{b_{i,N}}最小的i并且b_{i,N}>0，这就是对于x_B最紧的一个限制，令B=i，然后进行一次\text{pivot(N,B)}，观察上面的式子，变换后方程中的常数依然是一个非负值，所以这样的变换也是满足我们对c_i的期望的。
当然，有可能存在这样的N，但是没有符合的B，这说明x_N可以任取，故答案为+\infin。
如果有c_i<0
如果\exist i,c_i<0，那么我们要找一个j使得b_{i,j}<0，那么进行一次\text{pivot(j,i)}就能让x_j变成基变量后c>0；假如找不到那么说明x_i<0，则无解。
对偶形式
假如我们人为的根据上面的形式再构造一个新的线性规划，如下：
\min \sum_{i=1}^{m}c_iy_i\\
\forall 1\le i\le n,\sum_{j=1}^{m}b_{j,i}y_j\ge a_i\\
\forall 1\le i\le m,y_i\ge 0
其实就是给上面的每条不等式都配上一个系数y_i，然后分别乘上系数后相加，最后再去逼近各项系数a_i，有大佬证明了这两个问题是等价的，但是我不会，不过可以感性理解。