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

线性规划问题有4个可能的情况： 1.唯一解：目标函数对应的直线与可行解空间相交于一点（图15-1所示）； 2.有无穷多个最小值解：目标函数所对应的直线与某个约束线精确垂直（图15-2(a)所示）； 3.没有可行解：构建的线性规划问题的可行解域为空集，没有可行解（图15-2(b)所示）； 4.无边界问题：可行解域是无界的（图15-2(c )所示）。 本文主要讨论有界线性规划问题求解（就是第1和第2种情况），对于无界线性规划问题，会在本文1.2.3 无界线性规划问题*中简单提到。

以下面的例子来讲。 约束条件如下： 目标函数为： 解：画图如下，图中对每个约束进行了编号，以便在以下的图解方法中识别它们。

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

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

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

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

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

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

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

对于线性规划问题，我们可以直接计算所有约束的可行解域（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)时间内计算出其公共的交集。

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

无界线性规划问题。