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

例谈寻找最优解的方法总结学生解简单的线性规划及相关类问题的难点是：如何利用可行域求得最优解.这 里介绍五种方法供同学们参考.1 直线平移法平移法是一种最基本的方法，其基本原理是两平行直线中的一条上任意一点到另 一条直线的距离相等.例1求Z=10x+15y的最大值，使得x、y满足约束图1x + 2jp <24,3x + 2.y <3&解：作出约束条件所表示的平面区域(如图 1) 即可行域.作直线l： 10x+15y=0,即直线l： 2x+3y=0,把直线l 向上方移至m的位置，直线经过可行域上的点P.P + = 24此时Z=10x+15y取最大值.解方程组1% + ® = 36得P点坐标x=6, y=9，代入计算得Z =195. max说明：在直线向上平移过程中，Z的值是变大还是变小，这可以通过直线的法向 量来判断，当直线沿直线对应的法向量方向平移时，Z值变大，反之则变小•如 例1中直线l的法向量为(2,3)，所以直线l向上平移时Z的值变大.另外，通过平移法可以发现，取得最优解对应的点往往是可行域的顶点，其实这 具有必然性.2 斜率比较法平移法的缺陷在于，当可行域的顶点数较多时，不易直观地判断出哪个或哪几个顶点的坐标是最优解. 这时若进一步考虑直线斜率的大小，则可以确定出最优解.例2求Z=600x+1000y的最大值，使得x、y满足约束条件:10z+4y=300 图2解：作出约束条件所表示的平面区域(如图 ^lOx + 4^ <300?5x + 4.y < 200,'Ax-^9y<360r2),即可行域丨止°且沖0-.作直线 1： 600x+1000y=0,即直线 1： 3x+5y=0.5 5 3 4因为――二<—§，即k 占>12.4,100034.5> 眇 >34.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.31,乙产品34.51，能使利润总额达到最大.说明：这是高中新教材第二册上册第七章，“简单的线性规划”一节中的例 3360(P62〜63) •原解中的答案为x=12.3, y=24.4，这个结果直接来自于取x=翦,1000y=W 的不足近似值•显然这个答案过于简单化了，实际是给出了一个不良的导 向，使得学生在后续解题中，不知到底应该取不足近似值，还是过剩近似值，引 起解题中的思维混乱. 其实从“代入检验法”可知，这里 x， y 的近似取值应由目 标函数值的大小来确定，而不是简单取近似值的问题. 对于 x， y 要求整数的情况 也可以类似例 3 求得相应解.4 直线旋转法当目标函数涉及到某定点的距离问题时，我们可以考虑“直线旋转法”.2x+.y-2> 0 r —2尹+ 4例4已知平面区域〔％-3机，函数乙二乂:+丫?•问z在哪一点处取得最大值和 最小值？最大值和最小值各是多少？图3解一：作出约束条件所表示的平面区域(如图3)，即可行 域 ABC.过原点作直线EF，设与可行域ABC边界的交点为E、F.因 为J宀b =Jb_O)，+® —血，所以Z2表示点(x,y)到原 点的距离，所以线段 EF 上到原点距离最小点为 E. 将直线绕 原点旋转，则E点跑遍线段AB，又线段AB上到原点距离最 小点为过原点作直线 AB 垂线的垂足 H. 求得垂直 OH 的方程4 2 4为：2y-x=0,并求得垂足H的坐标为(，)，计算得z二、.min同理，距离最大点为F，将直线绕原点旋转，则F点跑遍线段AC和BC，由于k、AC k 都大于 0，所以 C 点到原点的距离最大. 计算得 C 点的坐标(2， 3)， z =12.BC max说明：用旋转直线法求最优解，实质是一种整体局部化思想.5曲线扩张法通常将二元的目标函数中的 Z 看作一常数，则方程的几何意义为一曲线，如例4 中方程Z==X2+y2表示的曲线为以原点为圆心，半径为返的圆•利用这一特点往 往可以轻松找到最优解.解二：因为方程Z==X2+y2表示的曲线为以原点为圆心，半径为返的圆•考察图3 知，当圆与直线AB相切时Z值最小.RT右ABC中0H丄AB，所以有10H|・| AB| = |OA| ・|0B|，计算得|0H|"鸟.H 的坐标 x=|OH|cos三 HOB=|OH|cos三 OAB二 E ,2 4 2y=|OH|sin^HOB=|OH|sin/OAB二即可行域内点（乙，）使Z取得最小，最小值为E •当圆过C点时Z值最大，C为已知直线AB与BC的交点，易计算得C点的坐标（2, 3）,此时 z =12.max说明：由于圆的半径为返，所以同一圆弧上的点对应的Z值相等，且圆的半径越大相应的Z值越大，这是判断最优解的依据.而且这一思路可以适用于更为一 般的曲线问题.。