数值优化(Numerical Optimization)(5)约束优化(二)

本篇博客还是继续约束优化,介绍约束优化中的一种特殊情况——线性规划,根据一个实例来展示单纯形法(Simplex method)的流程。文中例子来源

给大家总结几句单纯形法的要点:统一形式转矩阵、目标提升选入基、约束收紧作出基,具体来说就是把线性规划问题转化为最大化目标函数+等式约束+非负决策变量,然后根据这一标准形式写成矩阵(表),确定基变量和非基变量,循环选择一个非基变量替换基变量,入基的准则是选择目标函数值增长最多的方向,出基的准则是确保移动的距离在可行域内,直到目标函数不能再增加为止。

统一形式转矩阵

假设有如下线性规划问题:

[公式]

可以转化为如下标准形式(最大化目标函数+等式约束+非负决策变量):

[公式]

将线性方程转化为矩阵:变量都移至左边,目标函数变为 [公式] ,放在表格最后一行。每一个变量对应一列,目标函数值 P 对应一列,等式约束右侧的常数对应一列 ,所以总共有 [公式] 列。分别为 [公式] 每一个等式约束对应一行,目标函数对应一行,总共有 [公式] 行。

基变量和非基变量

表格中的每一行都有对应一个基变量(基变量所在的列只有一个非零元素),多余的变量为非基变量,在这里例子中,非基变量为 [公式] ,基变量可以通过删除非基列得到

[公式]

目标提升选入基

非基变量的值为 [公式] ,因此有 [公式] ,我们接下来需要寻找下一个可行解,那么什么方向才是理想的呢?考虑目标函数 [公式] ,我们每沿着 [公式] 移动一个单位可以使得目标函数值增大 [公式] ,沿着 [公式] 移动一个单位可以使得目标函数值增大 [公式] 。因此显然要选择移动的方向是 [公式] 方向,对应到单纯形矩阵(表)里的最后一行,移动的方向(入基的变量)就是负的且绝对值最大的值所在列对应的变量,在这里对应的就是 [公式] ,即 [公式] 为需要入基的变量。

约束收紧作出基

有进有出,选择了入基变量,还需要选择出基变量。在选择入基变量时我们选择了使得目标函数增加最多的方向,我们还需要确定要往这个方向移动多少的距离。对于入基变量 [公式] ,能移动的距离分别为 [公式]  [公式]  [公式] ,需要注意的是此时我们能移动的距离只能是最小的距离,不然就超过了可行域,即选择距离最小(约束最紧)对应的行变量作为出基,在这里为 [公式] 

确定好入基和出基变量后,将行变量的出基变量 [公式] 替换为入基变量 [公式] ,并将基变量所在列的其他元素约简为 [公式] ,如下矩阵第一列所示

此时非基变量为 [公式] ,基变量为

[公式]

继续根据先前的原则选取出基入基变量

将变量 [公式] 替换为 [公式] 后并化简矩阵有

此时单纯形矩阵的最后一行没有负数,这说明了目标函数已经没有增加的空间了,此时的解为最优解。

图像角度分析问题

对于标准化后的线性规划问题,可以用图像表示为

图中x1和x2变量名有误,需要交换一下

非基变量 [公式] 对应可行解 [公式] ,经过第一轮出基入基后,沿着 [公式] (图中有误) 方向移动最短距离 8 个单位(保证约束)到达 [公式] 

图中x1和x2变量名有误,需要交换一下

再一次入基出基迭代,沿着 [公式] 方向移动 3 个单位到达 [公式] 点。

图中x1和x2变量名有误,需要交换一下

此时达到了最优解,目标函数取得最大值。