约束最优化——线性规划（LP）问题
1 线性规划
约束优化问题：给定约束条件和目标函数，计算约束条件下目标函数的最大（最小）值。
目标函数和约束条件都是线性函数的情况，称为线性优化问题(LP问题)。此外，还有非线性优化问题。
线性规划问题有4个可能的情况：
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）问题求解——单纯形法_lp松弛-CSDN博客
单纯形法：适用于约束条件和变量数目都很多的情况；对于变量数量较少的情况，以下介绍的计算几何的方法效率会更高。
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 无界线性规划问题*
无界线性规划问题。
参考文献：
最优化方法笔记3：约束最优化——线性规划（LP）问题_线性优化约束问题例题-CSDN博客
线性规划（LP）问题求解——单纯形法_lp松弛-CSDN博客
标签：可行,LP,线性规划,约束,问题,计算 From： https://www.cnblogs.com/Gaowaly/p/18319848