例谈寻找最优解的方法总结.doc

例谈寻找最优解的方法总结学生解简单的线性规划及相关类问题的难点是：如何利用可行域求得最优解.这里介绍五种方法供同学们参考.1 直线平移法平移法是一种最基本的方法，其基本原理是两平行直线中的一条上任意一点到另一条直线的距离相等.例1 求Z=10x+15y的最大值，使得x、y满足约束条件：解：作出约束条件所表示的平面区域（如图1），即可行域.作直线l：10x+15y=0,即直线l：2x+3y=0,把直线l向上方移至m的位置，直线经过可行域上的点P.此时Z=10x+15y取最大值.解方程组得P点坐标x=6，y=9，代入计算得Zmax=195.说明：在直线向上平移过程中，Z的值是变大还是变小，这可以通过直线的法向量来判断，当直线沿直线对应的法向量方向平移时，Z值变大，反之则变小.如例1中直线l的法向量为(2,3)，所以直线l向上平移时Z的值变大.另外，通过平移法可以发现，取得最优解对应的点往往是可行域的顶点，其实这具有必然性.2 斜率比较法平移法的缺陷在于，当可行域的顶点数较多时，不易直观地判断出哪个或哪几个顶点的坐标是最优解.这时若进一步考虑直线斜率的大小，则可以确定出最优解.例2 求Z=600x+1000y的最大值，使得x、y满足约束条件：解：作出约束条件所表示的平面区域（如图2），即可行域.作直线l：600x+1000y=0,即直线l：3x+5y=0.因为-，即kENkMNkl12.4, 34.534.4,设直线n ：3(x-12.4)+5(y-34.4)=0，结合图2,再设直线n与直线MF交点A，直线n与直线MN交点B.AMB内及边界上精确到0.1的点有 (11.9,34.7)，（12.1,34.6），(12.3,34.5)，(12.4,34.4),代入检验得当x=12.3，y=34.5时对应z值大.所以在可行域内，精确到0.1的所有点中当x=12.3，y=34.5时z值最大.答：应生产甲产品约12.3t,乙产品34.5t，能使利润总额达到最大.说明：这是高中新教材第二册上册第七章，“简单的线性规划”一节中的例3（P6263）.原解中的答案为x=12.3，y=24.4，这个结果直接来自于取x=，y=的不足近似值.显然这个答案过于简单化了，实际是给出了一个不良的导向，使得学生在后续解题中，不知到底应该取不足近似值，还是过剩近似值，引起解题中的思维混乱.其实从“代入检验法”可知，这里x，y的近似取值应由目标函数值的大小来确定，而不是简单取近似值的问题.对于x，y要求整数的情况也可以类似例3求得相应解.4 直线旋转法当目标函数涉及到某定点的距离问题时，我们可以考虑“直线旋转法”.例4 已知平面区域，函数z=x2+y2.问z在哪一点处取得最大值和最小值？最大值和最小值各是多少？解一：作出约束条件所表示的平面区域（如图3），即可行域ABC.过原点作直线EF，设与可行域ABC边界的交点为E、F.因为=，所以z2表示点(x,y)到原点的距离，所以线段EF上到原点距离最小点为E.将直线绕原点旋转，则E点跑遍线段AB，又线段AB上到原点距离最小点为过原点作直线AB垂线的垂足H.求得垂直OH的方程为：2y-x=0,并求得垂足H的坐标为（，），计算得zmin=.同理，距离最大点为F，将直线绕原点旋转，则F点跑遍线段AC和BC，由于kAC、kBC都大于0，所以C点到原点的距离最大.计算得C点的坐标（2，3），zmax=12.说明：用旋转直线法求最优解，实质是一种整体局部化思想.5曲线扩张法通常将二元的目标函数中的Z看作一常数，则方程的几何意义为一曲线，如例4中方程Z=x2+y2表示的曲线为以原点为圆心，半径为的圆.利用这一特点往往可以轻松找到最优解.解二：因为方程Z=x2+y2表示的曲线为以原点为圆心，半径为的圆.考察图3知，当圆与直线AB相切时Z值最小.RTABC中OHAB，所以有|OH|AB|=|OA|OB|，计算得|OH|=.H的坐标x=|OH|cosHOB=|OH|cosOAB=,y=|OH|sinHOB=|OH|sinOAB=,即可行域内点（，）使Z取得最小，最小值为.当圆过C点时Z值最大，C为已知直线AB与BC的交点，易计算得C点的坐标