[数据结构与算法]【数学】整数线性规划问题与对偶单纯形法

我们此前探讨过了一般的单纯形法(传送门)，这次则来研究所谓“对偶单纯形法”。

线性规划的对偶问题

原始的线性规划问题：
$\max c^{T}x$
$Ax\le b$
$x\ge 0$

它的对偶问题：
$\min b^{T}y$
$A^{T}y\ge c$
$y\ge 0$

容易看出，对偶的对偶就是它自身。

定理1：$c^{T}x\le (A^{T}y{)}^{T}x=y^T(Ax)\le y^{T}c=c^{T}y$

定理2：若原始问题有一组可行解$x$，对偶问题有一组可行解$y$，且$c^{T}x=b^{T}y$，则两个解分别是它们的最优解。（由定理1确定的上下界知，显然）

定理3：若原问题有最优解，则对偶问题有最优解。
证明：
先按照单纯形的流程做一下，在原问题引入松弛变量$u$后转化为$Ax+Eu=b$。我们找到了一组基本最优解，基向量为$x_B=B^{?1}b$。
还记得最优解的条件码？对，检验数。由于这个原问题是最大化问题，所以检验数此时应该全部小于等于0。
还记得检验数的公式吗？${\lambda }^T=c^T?c_B^T{B}^{?1}A$，不过由于我们加了变量没有扩展$A$，所以松弛变量$u$这一块要额外考虑考虑。考虑的结果就是：
${\lambda }^T=(c^T?c_B^T{B}^{?1}A,?c_B^T{B}^{?1}E)$
因此$c^T?c_B^T{B}^{?1}A\le 0$即$c^T\le c_B^T{B}^{?1}A$。两边同时取反一下得：$c\le A^T((B^{?1}{)}^T{c}_B)$
对比一下对偶问题的条件$A^{T}y\ge c$，发现$y=(B^{?1}{)}^T{c}_B$是一组可行解。
而$y^{T}b=c_B^T{B}^{?1}b=c_B^T{x}_B$，即$b^{T}y=c^{T}x$，根据定理2，$y$是最优解。

对偶单纯形法

由以上证明过程可以看出，如果认为$y^T=c_B{B}^{?1}$，对偶问题的一组可行解，能够保证原问题$\lambda \ge 0$，虽然此时它不一定是原问题的可行解。我们定义这样的解叫做正则解。

普通的单纯形法，是可行解保证了可行性后，我们再将其逐步变为正则解保证最优性。

交换后，要让${\lambda }_j^{\prime }={\lambda }_j?{\lambda }_k{\alpha }_{lj}/{\alpha }_{lk}\ge 0$，即正则性依然成立。

当${\alpha }_{lj}\ge 0$等式自然成立，则只需要对于${\alpha }_{lj}<0$的，有$\frac{{\lambda }_j}{{\alpha }_{lj}}\le \frac{{\lambda }_k}{{\alpha }_{lk}}$即可。

故对偶单纯形法的流程如下：

1. 先找到正则解和正则基
2. 判断$\beta =B^{?1}b\ge 0$是否成立，也就是是否可行。若可行则结束。
3. 否则取${\beta }_l<0$，若${\alpha }_{ij}\ge 0$则无可行解。
4. 否则找 λ k α l k = max ? { λ j α l j ∣ α l j < 0 } \frac{\lambda_k}{\alpha_{lk}}=\max\{\frac{\lambda_j}{\alpha_{lj}} |\alpha_{lj} < 0\} αlk?λk??=max{αlj?λj??∣αlj?<0}的$x_k$和$x_{\pi (l)}$交换做基变换。
5. 重复2

整数线性规划问题

你可能要问，既然我们已经有了普通的单纯形算法，为什么需要对偶单纯形算法？这就要提整数线性规划问题了。

整数线性规划问题，指的是添加了条件“变量必须是整数”的线性规划问题，视具体的约束条件不同，又分了很多种，就不细说了。

算分书中的例题：

$\min z=?3x?5y$
$?x+y\le 1.5$
$2x+3y\le 11$
$x,y\ge 0$且它们都是整数。

同样，本文不作数学证明，只说解法：

先去掉整数条件，做线性规划求最优解。比方说例题，两个条件添加松弛变量$u_1$和$u_2$，去掉整数条件做完单纯形算法，最终单纯形表如下：

如果解都是整数，很好。但是我们得到的$x=1.3,y=2.8$，解都不是整数！所以我们得继续。

有若干变量不是整数，任选一个，比如$x_i=s$，将这个问题分裂成两个子问题，分别添加条件$x_i\le ?s?$和$x_i\ge ?s?$两个条件，分别求解。然后选择得到的最优解值更优的，再继续重复分裂，直到所有解都变成整数为止。

一个$x_i\le a$的条件相当于$x_i+u=a$。
一个$x_i\ge a$的条件相当于$?x_i+u=a$。

比方说例题，我们先来解决添加了$x\le 1$条件的子问题吧。

我们需要给$A$添加一行（一个新条件）和一列（一个新变量u），并且基变量也要增加一个$u$。

而由于$x$已经是一个基变量的，所以应该把$u$这一行的那个1给消掉（严格证明略，即我不会），也就是说要这样：

可以看到，现在$u\ge 0$的条件并没有满足，但$\lambda \ge 0$的条件还是满足的，也就是说这是一组基本正则解。

所以此时应用对偶单纯形算法，就可以继续求解了。

此时我们把$\theta$写最上面，值为$|\frac{{\lambda }_j}{{\alpha }_{lj}}|$，其中这个$l=3$：

若${\alpha }_{lj}\ge 0$，那这一列就直接忽略，所以只有$u_2$是我们心仪的换入变量。将其换入，消元如出一辙，将第3行第4列消成1，其他行第4列都消成0：

可喜可贺可喜可贺。加$x\ge 1$的子问题也类似，我也没有算，按算分书的说法，那个子问题的解更优，应该从它开始继续分裂。要分好几次才能找到最优解$x=4,y=1,z=?17$。

这个算法被称为分支限界算法。

总结

讨论了线性规划的对偶单纯形法，以及它在整数线性规划问题中的应用。