《运筹学》图解法求解线性规划的最优解

图解法(图形方法)是求解线性规划最优问题最简单直观的方法之一。分为四步:

1.绘制 constraints(约束条件)

根据各个约束条件绘制出各条线。

2.确定 feasible region(可行域)

求出所有约束条件包围的区域,这就是可行域。

3.绘制 objective line(目标函数线)

根据目标函数绘制出目标函数线。

4.确定最优点

在可行域中,目标函数线与可行域的交点或切点,即为最优解。

具体步骤如下:

1) 根据问题的各个约束条件,绘制出对应的线段(红线),这些线段包围出一个区域,就是该问题的可行域。

2) 根据目标函数,绘制目标函数线(黄线)。

3) 目标函数线与可行域线段的交点或切点,即为最优解。取交点或切点中目标函数值最大的那个点。

4) 读出最优解下的自变量和目标函数值。

优点:

· 计划问题直接可视化,直观简单。

· 帮助理解问题含义。

· 帮助检验其他求解方法的有效性。

局限性:

· 只适用于有2个自变量的问题。

· 对于约束条件多的问题,绘制会复杂难以观察。

· 对于目标函数和约束条件复杂的问题,不易确定最优点。

因此图解法主要适用于问题简单、自变量少的情况。