本篇博客还是继续约束优化,介绍约束优化中的一种特殊情况——线性规划,根据一个实例来展示单纯形法(Simplex method)的流程。文中例子来源
给大家总结几句单纯形法的要点:统一形式转矩阵、目标提升选入基、约束收紧作出基,具体来说就是把线性规划问题转化为最大化目标函数+等式约束+非负决策变量,然后根据这一标准形式写成矩阵(表),确定基变量和非基变量,循环选择一个非基变量替换基变量,入基的准则是选择目标函数值增长最多的方向,出基的准则是确保移动的距离在可行域内,直到目标函数不能再增加为止。
统一形式转矩阵
假设有如下线性规划问题:
可以转化为如下标准形式(最大化目标函数+等式约束+非负决策变量):
将线性方程转化为矩阵:变量都移至左边,目标函数变为 ,放在表格最后一行。每一个变量对应一列,目标函数值 P 对应一列,等式约束右侧的常数对应一列 ,所以总共有 列。分别为 ;每一个等式约束对应一行,目标函数对应一行,总共有 行。
基变量和非基变量
表格中的每一行都有对应一个基变量(基变量所在的列只有一个非零元素),多余的变量为非基变量,在这里例子中,非基变量为 ,基变量可以通过删除非基列得到
目标提升选入基
非基变量的值为 ,因此有 ,我们接下来需要寻找下一个可行解,那么什么方向才是理想的呢?考虑目标函数 ,我们每沿着 移动一个单位可以使得目标函数值增大 ,沿着 移动一个单位可以使得目标函数值增大 。因此显然要选择移动的方向是 方向,对应到单纯形矩阵(表)里的最后一行,移动的方向(入基的变量)就是负的且绝对值最大的值所在列对应的变量,在这里对应的就是 ,即 为需要入基的变量。
约束收紧作出基
有进有出,选择了入基变量,还需要选择出基变量。在选择入基变量时我们选择了使得目标函数增加最多的方向,我们还需要确定要往这个方向移动多少的距离。对于入基变量 ,能移动的距离分别为 , , ,需要注意的是此时我们能移动的距离只能是最小的距离,不然就超过了可行域,即选择距离最小(约束最紧)对应的行变量作为出基,在这里为 。
确定好入基和出基变量后,将行变量的出基变量 替换为入基变量 ,并将基变量所在列的其他元素约简为 ,如下矩阵第一列所示
此时非基变量为 ,基变量为
继续根据先前的原则选取出基入基变量
将变量 替换为 后并化简矩阵有
此时单纯形矩阵的最后一行没有负数,这说明了目标函数已经没有增加的空间了,此时的解为最优解。
图像角度分析问题
对于标准化后的线性规划问题,可以用图像表示为
非基变量 对应可行解 ,经过第一轮出基入基后,沿着 (图中有误) 方向移动最短距离 8 个单位(保证约束)到达 点
再一次入基出基迭代,沿着 方向移动 3 个单位到达 点。
此时达到了最优解,目标函数取得最大值。
评论(0)
您还未登录,请登录后发表或查看评论