简单线性规划整点最优.doc

简单线性规划整点最优黄建华:本文主要介绍简单线性规划整点最优解的几种搜索方法,它们都是在图解平移法的基础上运用交轨,换元,近值的方法来对整点进行搜索定位。:简单线性规划;整点最优解;平移交轨法;平移换元法;平移近值法:o221TheResearchIntoSimpleLinearProgramming’sOptimalToIntegralPointHuangjianhua(Class200001,mathematicsdepartmeatofHuanggangNormalUniversityHuangzhou,438000,HuBei,China)Abstruct:Thistopiemainlyintrducesseveralmethodsaboutsimplelinerprogramming’,:Simplelinearprogramming;optimalsolutiontointegralpoint;Themethodofgraphictranslatingonthejoint;,简单线性规划问题已经逐渐成为中学数学教学的一个基本内容。简单线性规划问题与我们的日常生活息息相关,它主要涉及人力、物力、资金等资源的最优配置。作为中学数学教学,整点最优解问题是简单线性规划的核心内容,但教材对于具体的验算过程并没有作过多的描述,以致中学生在解题过程中对于具体的验算过程掌握还不够清晰。在资料上也经常见到有关简单线性规划整点最优解问题的求解方法,如:网格法,穷举法,筛选法,最小距离法等。本文将介绍利用平移法求整点最优解的几种具体的操作方法—平移交轨法,平移换元法,平移近值法。该方法主要是在平移直线过程中,利用直线间的交点来缩小最优值的存在范围,因此其主要思想是联立方程求解交点,然后确定最优解可能的存在范围。要将两种大小不同的钢板截成A、B、C三种规格,每张钢板可同时截得1三种规格的小钢板的块数如下表所示:规格类型钢板类型A规格B规格C规格第一种钢板211第二种钢板123今需要A、B、C三种规格的成品分别为15、18、27块,问各截这两种钢板多少张可得所需三种规格成品,且使所用钢板张数最少?(新教材63页例4)这类问题涉及物资的优化配置,在任务一定的条件下,使物资用量最少。设需截第一种钢板x张,第二种钢板y张,设所用钢板的张数为z张,则:2x+y?15Yyx+2y?18yyx+3y?27x?0,y?0目标函数为:z=x+y可行域如图所示(图1)根据目标函数作出一组平行直线:x+y=t。这些直线中经过可行域且和原点距离最近的直线,此直线经直线x+3y=27和2x+y=151839的交点A(),此直线,55与原点的距离最近,z取得最小值,即:57z=x+y=51839显然和都不是整数,而最优解中,x和y必须为整数,故A不是最优解,故将直5557线x+y=向上平移到x+y=12,最优解