约束最优化——线性规划(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