线性规划——单纯形法

单纯形法

现在假设原线性规划中，不存在单位矩阵$I$I，所取的基是一般形式的$B$B，则形式如下：

①最优解判别准则（如何判断我们得到的解是否是最优解，然后终止迭代）：
判别数和基都一般化时的情况：

若令$\sigma_j=C^T_BB^{-1}P_j - c_j$σj​=CBT​B−1Pj​−cj​，$j = 1,\dots,n$j=1,…,n，则当任意$\sigma_j\leq 0$σj​≤0时，$X = (B^{-1}b，0)$X=(B−1b，0)为最优解

②换基操作：如果当前顶点不是最优解时，如何从一个基可行解（顶点）沿下降方向到另一个基可行解（顶点）

设第$l$l列是进基列，第$k$k列是出基列，$a_{kl}$akl​是主元，即$\sigma_l >0$σl​>0，$a_{kl} > 0$akl​>0，则我们的目标是将$P_l$Pl​通过行初等变换变成单位向量，此时$P_k$Pk​变成非单位向量，如下：

行初等变换规则（分为系数和增广系数）如下，不用死记硬背：

主元的选择方法：
首先，主元必须大于0，不然进基后，增广系数会为负数，破坏标准线性规划形式；在同样大于0的情况下，要保证在行变换过程中所有增广系数都非负，因此满足下式成立：

③进基列的选择：如何选择进基列可以使目标函数有较大的下降

• 基可行解$X^0=(B^{-1}b,0)$X0=(B−1b,0)非退化
  若是退化的基可行解，则此时不同的基可能对应相同的解，因此是非严格下降的，该要求能保证严格递减
• 进基列的判别数$\sigma_j >0$σj​>0
  $\sigma_j >0$σj​>0说明以它为基，目标函数值还可以减小
• 进基列向量中至少有一个元素是正的
  保证可以变小并且是有界的变小，而不是无穷小导致原线性规划无最优值

判别数：
$\sigma_j = C^T_BB^{-1}P_j-c_j$σj​=CBT​B−1Pj​−cj​

无解：判别数$\sigma_j >0$σj​>0，但是$P_j<0$Pj​<0，此时无解
无穷多最优解：存在一个非基变量对应的判别数为0
唯一解：所有非基变量对应的判别数严格小于0

补充：计算单纯形表最后一行的小技巧

在进行换基运算时，可以同时对单纯行表最后一行做行初等变换（让进基列判别数为0），变换公式如下：

避免循环

当基可行解退化时，可能出现循环情况
解决方法：左上原则
进基列选择所有判别数为正的最左边的一列，主元选择（多个最小值）行标最小的

修正单纯形法（一般计算机编程实现用）

优点： 不需要画多个表格，只需要存储一个基矩阵的逆
思想： 用初等矩阵记录一系列的行初等变换的过程，只保留参与迭代的列向量的运算

新一轮迭代：
上一轮迭代变换后的进基列$P_j^{k-1} = B_{k-1}^{-1}P_j^0$Pjk−1​=Bk−1−1​Pj0​
加入新进基列后的矩阵$M$M，强制转化成单位阵需要的初等矩阵$E$E，也就是求$M$M的逆
在上一轮基矩阵的逆的基础上，得到新一轮基矩阵的逆：$B_k = M^{-1}B_{k-1}$Bk​=M−1Bk−1​
计算新$b$b、新$\sigma$σ
根据新$\sigma$σ找出本轮的进基列，并计算本轮迭代变换后的进基列$P_j^{k} = B_{k}^{-1}P_j^0$Pjk​=Bk−1​Pj0​
根据本轮迭代变换后的进基列和新$b$b，挑选主元进入下一轮迭代

都是找的第一张表的值，因为用到了基矩阵的逆，而基矩阵的逆是一个累计值