1 线性规划

约束优化问题：给定约束条件和目标函数，计算约束条件下目标函数的最大（最小）值。目标函数和约束条件都是线性函数的情况，称为线性优化问题。此外，还有非线性优化问题。

线性规划问题有4个可能的情况：
1.唯一解：目标函数对应的直线与可行解空间相交于一点（图15-1所示）；
2.有无穷多个最小值解：目标函数所对应的直线与某个约束线精确垂直（图15-2(a)所示）；
3.没有可行解：构建的线性规划问题的可行解域为空集，没有可行解（图15-2(b)所示）；
4.无边界问题：可行解域是无界的（图15-2(c )所示）。

本文主要讨论有界线性规划问题求解（就是第1和第2种情况），对于无界线性规划问题，会在本文1.2.3 无界线性规划问题*中简单提到。

1.1 图解法（计算机不适用，便于理解）

以下面的例子来讲。
约束条件如下：

目标函数为：

解：画图如下，图中对每个约束进行了编号，以便在以下的图解方法中识别它们。

让Z值不停地增大，直到再次增大Z值，使目标超出了可行区域为止。图15-1(b)显示了该变化过程，得到Z的最大值为1400。

优缺点：计算机不适用，且只能处理二维三维问题。但是便于理解，解释概念。

启示：由上述过程可以看到，最优解通常在两个约束线交汇的一个角点出现。这个点称为极点*。
因此，对于有界规划问题，最优解可以使用穷举法来比较每个可行极点的目标函数值来得到。*

1.2 单纯形法

由图解法得到的启示，有界线性规划的极点都是出现在两个约束线交汇的角点。由此我们可以想办法计算每个可行的极点，然后取这些极点中最大的目标函数值，就得到线性规划问题的最优解。

为了更容易理解单纯形法，我将其单独列出来讲。感兴趣可参见：线性规划（LP）问题求解——单纯形法：https://blog.csdn.net/luolei188/article/details/105458822

单纯形法：适用于约束条件和变量数目都很多的情况；对于变量数量较少的情况，以下介绍的计算几何的方法效率会更高。

1.3 计算几何的方法（待更新）

对于两个变量的线性规划问题，下面介绍的方法会更适用。不过这里面的会用到一些计算几何方面的知识。

1.3.1 分治式算法

对于线性规划问题，我们可以直接计算所有约束的可行解域（feasible region）。然后根据可行解域的边界交点，计算得到线性规划问题的最优解。

计算可行解域的最直接的方法，就是分治式算法，可计算任意 n 个约束的公共交集。算法伪代码如下：
INTERSECTHALFPLANES(H)
1.如果约束集H中约束的个数为1，返回；否则将约束集H分成两个子集H1和H2 ，大小分别为n/2；
2.如果子集H1中约束的个数大于1，调用INTERSECTHALFPLANES(H)，继续将子集一分为二；
3.如果子集H1中约束的个数大于1，调用INTERSECTHALFPLANES(H)，继续将子集一分为二；
4.否则，调用IntersectConvexRegions(H1 , H2)。

其中的子函数IntersectConvexRegions(H1 , H2)为计算两个凸多边形交集的算法。方法思路如下：

**结论：**函数IntersectConvexRegions(H1 , H2)，可以 O(n)时间内计算出任意两个凸多边形的交集。

**结论：**给定平面上的一组共 n 个约束，可以使用线性的空间，在 O(nlogn)时间内计算出其公共的交集。

1.3.1 递增式算法

1.3.2 随机递增式算法

改进的平面扫描算法： 随机平面扫描算法。

1.3.3 无界线性规划问题*

无界线性规划问题。