简单线性规划整点最优解问题研究

1、简单线性规划整点最优解问题研究黄建华摘要: 本文主要介绍简单线性规划整点最优解的几种搜索方法，它们都是在图解平移法的基础上运用交轨，换元，近值的方法来对整点进行搜索定位。关键词：简单线性规划；整点最优解；平移交轨法；平移换元法；平移近值法中图分类号：o221The Research Into Simple Linear Programmings Optimal To Integral Point Huangjianhua (Class200001,mathematics departmeat of Huanggang Normal University Huangzhou,438000,HuB

2、ei,China) Abstruct: This topie mainly intrduces several methods about simple liner programmings optimal solution to integral point .They all based the graphic translating on the joint,tranform and approximate value method to search for and fix the integral point.Key words: Simple linear programming;

3、optimal solution to integral point;The method of graphic translating on the joint;transform and approximate value.随着中学数学教育的改革和发展，简单线性规划问题已经逐渐成为中学数学教学的一个基本内容。简单线性规划问题与我们的日常生活息息相关，它主要涉及人力、物力、资金等资源的最优配置。作为中学数学教学，整点最优解问题是简单线性规划的核心内容，但教材对于具体的验算过程并没有作过多的描述，以致中学生在解题过程中对于具体的验算过程掌握还不够清晰。在资料上也经常见到有关简单线性规划整点最优

4、解问题的求解方法，如：网格法，穷举法，筛选法，最小距离法等。本文将介绍利用平移法求整点最优解的几种具体的操作方法平移交轨法，平移换元法，平移近值法。一 平移交轨法该方法主要是在平移直线过程中，利用直线间的交点来缩小最优值的存在范围，因此其主要思想是联立方程求解交点，然后确定最优解可能的存在范围。例1 要将两种大小不同的钢板截成A、B、C三种规格,每张钢板可同时截得三种规格的小钢板的块数如下表所示： 规格类型钢板类型A规格B规格C规格第一种钢板211第二种钢板123今需要A、B、C三种规格的成品分别为15、18、27块,问各截这两种钢板多少张可得所需三种规格成品,且使所用钢板张数最少? (新教材

5、63页例4)分析：这类问题涉及物资的优化配置,在任务一定的条件下,使物资用量最少。设需截第一种钢板x张,第二种钢板y张,设所用钢板的张数为z张，则： Yy yy2x+y15 x+2y18 x+3y27x0,y0目标函数为：z=x+y可行域如图所示(图1) 根据目标函数作出一组平行直线:x+y=t。这些直线中经过可行域且和原点距离最近的直线,此直线经直线x+3y=27和2x+y=15的交点A(),此直线与原点的距离最近,z取得最小值,即：z=x+y=显然和都不是整数,而最优解中,x和y必须为整数,故A不是最优解,故将直线x+y=向上平移到x+y=12,最优解可能存在于此直线上。最优解必须在可行域

6、内,故应求出直线2x+y=15和x+3y=27与x+y=12的交点： 2x+y=15 x+3y=27 x+y=12 x+y=12可得交点坐标为B(3,9),D()，故有：3x这样便更进一步的缩小了x的范围，即x=3或4，将其代入x+y=12 ，可得y=9或8。即（3，9）和（4，8）均为所求的最优解。根据上述的分析解答过程，我们可以看到利用平移交轨法解题对于一般的简单线性规划问题都是适用的，其解题步骤如下：1 设出所求的未知数，列出约束条件,建立目标函数；2 作出可行域；3 确定平移直线,寻找非整最优解；4 联立方程求交点确定x或y的范围；5 对x，y进行整点搜索，并确定整点解。二 平移换元法

7、该方法仍然是以平移法为基础，主要是利用换元来减少线性约束条件的元数，以得出参数的范围，从而确定出变量x，y的取值，再来确定最优解的可能值。例2 某人有房子一幢，室内面积共180m2，拟分隔成两类房间作为游客住房。大房间每间面积为18m2，可住游客5名，每名游客每天住宿费为40元；小房间每间面积为15m2，可住游客3名，每名游客每天住宿费为50元；装修大房间每间需1000元，装修小房间每间需600元。如果他只能筹款8000元用于装修，且游客能住满客房，他应隔出大房间和小房间各多少间，能获得最大收益？（新教材65页习题4）分析：这类问题涉及物资的优化运用，在物资一定的条件下，要求获利最大。设他应隔

8、出大房间x间，小房间y间，能获得收益为z元。18x+15y1801000x+600y8000x0，y0目标函数：z=200x+150y约束条件化简：6x+5y605x+3y40x0，y0可行域如图所示（图2）根据目标函数作一组平行直线：4x+3y=t，这些直线中经过B（）的直线与原点的距离最大。此时z=200x+150y取最大值 ，z=200×+150×=。但此时x，y均不为整数，故不是最优解，因此又要进行调整。故因将直线4x+3y=37，向左下方平移，又z为整数，故应平移至4x+3y=37 （1）由（1）知y=，将其代入约束条件：6x+5×605x+3×

9、;40可得x3。又x为整数，则x=3，此时y为非整数，故在直线4x+3y=37时无最优解，又向下方平移一个单位：4x+3y=36（2）由（2）知y=，将其代入约束条件：6x+5×605x+3×40可得0x4，x为整数则x=0，1，2，3或4，代入（2）求得它们对应的y=12，8，。故可得最优解有（0，12）和（3，8），此时z=1800。平移换元法对一般的简单线性规划问题也都适用，根据上面的例题分析我们将其一般步骤归纳如下：1 设出所求的未知数，列出约束条件，建立目标函数；2 作出可行域；3 确定平移直线，寻找非整最优解；4 由直线方程换元代入约束条件，并求变量范围：5 对

10、x，y进行整点搜索，并确定整点解。三 平移近值法该方法也是以平移直线为基础，但它并非一步一步的平移，而是在非整点最优解附近搜索，同时结合网格（并非所有网格都打出），直接找出附近的整点来减小搜索范围，从而求出整点最优解。下面以例2求解介绍此法。分析：设他应隔出大房间x间，小房间y间，能获得收益为z元。6x+5y605x+3y40x0，y0 目标函数：z=200x+150y可行域如图所示（图3）作直线：4x+3y=0，平移到B点时，z取得最大值，但B（）并非整点，故我们要进一步来搜索。由于B（），我们利用B附近的网格，可在B附近找到A（2，9）、C（2，8）、D（3，8）这几个整点。此时还必须从中

11、选出一个最适合的点： z1=8+27=35 ; z2=8+24=32 ; z3=12+24=36故在直线平移过程中，必先过D点，因此A.C两点被淘汰，故过D作直线：4x+3y=36此后，必需检验阴影区域内有无整点，此时要利用阴影区的网格寻找整点。经检验无整点。故直线4x+3y=36上必存在最优整点解。利用网格知：（0，12），（3，8）为最优整点解。平移近值法可以克服在前两种方法中有可能要多次平移找解的缺陷，适用范围广泛。其一般步骤归纳如下：1 设出所求的未知数，列出约束条件，建立目标函数；2 作出可行域；3 寻找非整点最优解A，根据A点的坐标在其附近寻找最近的整点B；4 过B作平移直线，通过直线确定较小的搜索范围；5 利用部分网格在确定的范围内求最优解。总之，以上三种基本方法都是以平移法为基础，对于一般的简单线性规划问题都能够求解。前两种方法的相似点很多，首先它们的基点相同，适用范围几乎相同，但对于目标函数t=ax+by，若t，a，b经约分后仍较大时，运用以上两种方法均要调整多次才可能达到最优。平移近值法弥补了前两种方法的不足，直接在非整点最优解附近的小范围内搜索，借用部分网格得出整点最优解。三种方法各有各的特点，因此有时要根据具体情况选择合理的方法。参考文献1安培录. 如何寻找线性规划问题的整点最优解. 数学通报，2000年第3期：18-21.2