线性规划化问题的简单解法

线性规划问题的解法 简单线性规划问题的几种简单解法 依不拉音。司马义(吐鲁番市三堡中学,838009) “简单的线性规划问题”属于高中数学新课程必修5,进入了高考试题,并且保持了较大的考察比例,几乎是每年高考的必考内容,也是高中数学教学的一个难点。

简单的线性规划是指目标函数只含两个自变量的线性规划。简单线性规划问题的标准型为 , 下面介绍简单线性规划问题的几种简单解法。

1. 图解法 第一步、画出约束条件表示的可行区域,这里有两种画可行区域的方法

⑴代点法直线AxByC0(c不为0)的某侧任取一点,把它的坐标代入不等式,若不等式成立,则不等式表示的区域在该点的那一侧;
若不成立,则在另一侧。

⑵B判别法若B>0(<0),则不等式AxByC>0(<0)表示的区域在直线AxByC=0的上方;
若B>0(<0),则不等式AxByC<0>0表示的区域在直线AxByC=0的下方。(即若B与0的大小方向跟不等式的方向相同,则可行区域是边界线的上方;
若B与0的大小方向与不等式的方向相反,则可信分区域是边界线的下方) 用上面的两种方法画出可行区域是很简单,所以这里不必举例说明。

第二步、在画出的可行区域内求最优解(使目标函数取最大值或最小值的点),这个可以用下面的两种办法解决。

⑴y轴上的截距法若,直线所经过可行域上的点使其y轴上的截距最大(最小)时,便是z取得最大值(最小值)的点;
若,直线所经过可行域上的点使其y轴上的截距最大(最小)时,是z取得最小值(最小值)的点(提醒截距不是距离,截距可以取正负)。

例1.设x,y满足约束条件求的最大值、最小值。

解如图1作出可行域,因为y的系数1大于0,目标函数表示直线在y轴上的截距,当直线过A(1,0)时,截距值最大,当直线过点O(0,0)时,截距值最小。

图1 例2.若变量满足约束条件,求的最大值和最小值。

解如图作出可行域,y的系数-2小于0,过点A1,-1时在y轴上的距最小,目标函数取得最大值,所以;
过点B(-1,1)时在y轴上的截距最大,目标函数取得最,所以。

⑵法向量法目标函数的法向量为(A,B),它垂直于目标函数直线的向量。当目标函数的值线沿目标函数法向量方向平移时,目标函数值逐步增加,与可行区域最后(最先)相交的点上取最大值(最小值);
当等值线沿目标函数法向量反方向平行移动时,目标函数值逐步减少,与可行区域最后(最先)相交的点上取最小值(最大值)。

例3.点Px, y在以A2, 1、B–1, –6、C–3, 2为顶点的三角形区域(包括边界)内,求z 4x–3y的最大值与最小值。

解目标函数z 4x–3y的法向量为(4,-3),目标函数的直线沿法向量的方向平移时,最先与可行域在C点上相交,最后在B点上相交(因为目标函数的等值线从左上角平移过来)。所以目标函数在点C(-3,2)上取最小值,在点B(-1,-6)上取最大值。

图解法虽然直观、形象,它容易使人具体地认识线性规划模型的求解过程,但是,这里难点至少有二;
一是必要考虑y的系数b的正负,否则容易得出反相的结论;
二是要注意直线束的倾斜程度,尤其,要注意与约束条件中的一条或两条只想的倾斜程度的关系,即斜率大小对直线倾斜程度的影响。其中,当斜率为负值时,是学生最感头疼的,也是学生最易出错的。为此,下面介绍通过向量数量积解决线性规划问题的方法,这种方法尽量避开以上两个难点,使解法更直观,更简单,更不易出错。

2. 向量的数量积法 把看成平面内的向量与的数量积,即。因为为定值,所以当且仅当取最大值(最小值)时,z取最大值(最小值),即当且仅当在上的射影取最大值(最小值)时,z取最大值(最小值)(注意在正方向上的射影是正值,在负方向上的射影是负值)。这样目标函数在约束条件下的最大值(最小值)问题,就转化为研究点O与可行域内的任意一点N所组成的向量在上的射影的最大值(最小值)问题。即线性规划最大值(最小值)问题就转化为一向量在另一向量上的射影的最大值(最小值)问题。

例4.若实数,满足,求的最小值。

解设是向量与的数量积。因为,所以当且仅当取最小值时z取最小值,即当且仅当在上的射影OP取最小值时,取得最小值。如图,当点N与点B(4,-2)重合时,在负方向上的射影OP取最小值,所以最小值为。

3. 顶点法 目标函数的最优解肯定在可行区域的顶点上(这个命题可以证明)。因此,首先求约束表示的可行区域顶点的坐标,代入目标函数,然后从计算出来的几个函数值里面选最大(或最小)的即可。把约束条件中的每两个不等式组成一个方程组,方程组的解是两条边界线的交点。有些交点肯能不属于可行区域,所以每个交点必须代入约束条件检验不等式是否成立。若不成立排除这个交点(它不属于可行区域);
若成立它是可行区域的顶点。

例5.求满足线性约束条件的目标函数的最大值和最小值。

解先找出约束条件表示的可行区域的顶点。

,,,,,的解分别为A(1,1),B(0,3),C(,0),D(0,),E(3,0),F(0,0)。其中B和E不满足约束条件,所以排除。可行区域是以点A,C,D,F为顶点的四边形。

,,, 所以,目标函数在A(1,1)上取最大值,在F(0,0)上取最小值。

(提醒若约束条件包含不等式的个数不超过3,边界线的交点属于可行区域。所以不需检验;
若不等式的个数超过3,必须检验) 共4页,第4页