本文来自我的个人博客 https://www.zhangshenghai.com/posts/55620/
线性规划概述
在给定有限的资源和竞争约束情况下，很多问题都可以表达为最大化或最小化某个目标。如果可以把目标指定为某些变量的一个线性函数，而且如果可以将资源的约束指定为这些变量的等式或不等式，则得到一个线性规划问题（Linear-Programming Problem）。
在求解线性规划时又两种有用的格式：标准型和松弛型。在标准型中所有的约束都是不等式，而在松弛型中所有的约束都是等式。
下面给出一个将实际问题转换为线性规划形式的例子。
有m种不同的食物
，这些食物能够提供n种营养
，营养
每天的最低需求量是
，
是
的单位价格。
代表食物
假设每种食物的数量为
，则使用线性规划的形式可表示为：
这个问题的目标是求满足营养需求的条件下最小化价格，接下来我们会看到，其实它的对偶问题就是最大化营养的需求量。
单纯形算法
解决线性规划问题主要用三种算法：
- 单纯形算法：指数时间的复杂度，但是在实际中应用广泛，当它被精心实现时，通常能够快速地解决一般的线性规划问题。
- 椭圆算法：第一个指数时间算法，但是在实际中运行缓慢。
- 内点法：在理论和实际中都能比较有效率地解决线性规划问题。
本章我们主要讨论在实际问题中应用广泛的单纯形算法。
首先从一个例子开始，考虑下列松弛型的线性规划并将等式重写后可得到一个tableau：
现在，是基本解，令
，可得
，且
。
我们当然希望改善的值，很明显需要增加
或者
。令
，由于
，
最大可取至1，此时
。现在基本解变为
，重写tableau：
重复上面的过程，为了增加的值，我们可以增加
（由于
的系数是负数，因此增加
是无效的）。令
，
最大可取至1，此时
。这时基本解变为
，重写tableau：
重复上面的过程，为了增加的值，我们可以增加
（由于
的系数是负数，因此增加
是无效的）。令
，
最大可取至2，此时
变为0。这时基本解变为
，重写tableau：
此时可看出的取值已达最优，因此解是
，目标值
。
对偶性
对偶性是个非常重要的性质。在一个最优化问题中，一个对偶问题的识别几乎总是伴随着一个多项式时间算法的发现。
在线性规划的形式下，对偶问题可互相转化，具体如下图所示：
下面给出一个实际例子，照着原问题的线性规划形式，我们即可写出对偶问题的线性规划形式。
原问题有多少个未知数，对偶问题就有多少个式子；原问题有多少个式子，对偶问题就有多少个未知数。
如下图所示，原问题给出了对偶问题的可行解的下界，对偶问题给出了原问题的可行解的上界。
总结几个经典的对偶问题：
- 最大流的对偶问题是最小割
- 最大匹配的对偶问题是最小顶点覆盖
- 最优匹配的对偶问题是最小定标和
最大流与最小割的线性规划表示
最大流满足两个性质：反对称性、容量限制。最大流是满足这两个约束和最大化流量值的流，其中流量值是从源流出的总流量。因此，流满足线性约束，且流的值是一个线性函数。可以将最大流问题表示为线性规划并作如下的转换：
其对偶问题的实际意义是最小割：
