理论教育 线性规划问题的图解优化方法

线性规划问题的图解优化方法

时间:2023-07-06 理论教育 版权反馈
【摘要】:当线性规划问题只有两个变量时,可以考虑用图解的方法进行求解。在这一区域内或边界上的点能够满足所有的约束条件,所以把这一区域称为线性规划问题的可行域,可行域中每个点对应着线性规划问题的一个可行解。线性规划问题的解可能呈现出多种形态,如图2-2所示。图2-2线性规划问题解的情况需要说明的是,当线性规划问题的求解结果为无可行解时,说明约束条件之间存在着矛盾;而当求解结果为无界解时,通常表明必要的约束条件不足。

线性规划问题的图解优化方法

线性规划问题只有两个变量时,可以考虑用图解的方法进行求解。尽管图解方法不能成为求解线性规划问题的一般方法,但图解法直观明了,而且对于后面单纯形法的理解有着形象化的帮助,所以有必要对线性规划问题的图解方法进行介绍。

以模型(2.6)为例,由于该模型只涉及两个变量,所以可以分别以x1为横轴、x2为纵轴建立平面坐标系,如图2-1所示。

图2-1 图解法

首先,由于存在变量的非负约束,所以只需在第一象限内考虑问题的解。其次,根据3种资源方面的约束条件可以得到满足所有约束条件的解所形成的一个闭合区域(图中的阴影部分)。在这一区域内或边界上的点能够满足所有的约束条件,所以把这一区域称为线性规划问题的可行域,可行域中每个点对应着线性规划问题的一个可行解。另外,当问题的目标函数值由小变大时,如图2-1中z1=10和z2=20时,目标函数表示的直线向可行域的右上方移动,当移动到可行域的边界时,目标函数值达到最大值z=36,此时根据直线2x2=12和3x1+2x2=18的交点可以得到问题的最优解为x1=2,x2=6。

这一过程就是线性规划的图解法,使用它可以解决具有两个变量的线性规划问题。但当变量数增多以后,这一方法就不再适用了,所以它不是解决线性规划问题的一般方法。然而,通过线性规划的图解过程,可以发现一些线性规划问题的特点。(www.daowen.com)

(1)线性规划问题如果存在可行域,则其可行域为一凸集,即可行域内任意两点的连线仍在可行域内。

(2)线性规划问题如果存在可行域,则线性规划问题的最优解不可能在可行域内部的点实现。

(3)线性规划问题的解可能呈现出多种形态,如图2-2所示。

图2-2 线性规划问题解的情况

需要说明的是,当线性规划问题的求解结果为无可行解时,说明约束条件之间存在着矛盾;而当求解结果为无界解时,通常表明必要的约束条件不足。根据企业实际建立起来的线性规划问题,如果出现了这两种解的情况,表明在建模时要么多考虑了约束条件要么漏掉了必要的约束条件。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈