一 平移交轨法.doc

一 平移交轨法该方法主要是在平移直线过程中，利用直线间的交点来缩小最优值的存在范围，因此其主要思想是联立方程求解交点，然后确定最优解可能的存在范围。例1 要将两种大小不同的钢板截成A、B、C三种规格,每张钢板可同时截得三种规格的小钢板的块数如下表所示： 规格类型钢板类型A规格B规格C规格第一种钢板211第二种钢板123今需要A、B、C三种规格的成品分别为15、18、27块,问各截这两种钢板多少张可得所需三种规格成品,且使所用钢板张数最少? (新教材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,最优解可能存在于此直线上。最优解必须在可行域内,故应求出直线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进行整点搜索，并确定整点解。二 平移换元法该方法仍然是以平移法为基础，主要是利用换元来减少线性约束条件的元数，以得出参数的范围，从而确定出变量x，y的取值，再来确定最优解的可能值。例2 某人有房子一幢，室内面积共180m2，拟分隔成两类房间作为游客住房。大房间每间面积为18m2，可住游客5名，每名游客每天住宿费为40元；小房间每间面积为15m2，可住游客3名，每名游客每天住宿费为50元；装修大房间每间需1000元，装修小房间每间需600元。如果他只能筹款8000元用于装修，且游客能住满客房，他应隔出大房间和小房间各多少间，能获得最大收益？（新教材65页习题4）分析：这类问题涉及物资的优化运用，在物资一定的条件下，要求获利最大。设他应隔出大房间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+5605x+340可得x3。又x为整数，则x=3，此时y为非整数，故在直线4x+3y=37时无最优解，又向下方平移一个单位：4x+3y=36（2）由（2）知y=，将其代入约束条件：6x+5605x+340可得0x4，x为整数则x=0，1，2，3或4，代入（2）求得它们对应的y=12，8，。故可得最优解有（0，12）和（3，8），此时z=1800。平移换元法对一般的简单线性规划问题也都适用，根据上面的例题分析我们将其一般步骤归纳如下：1 设出所求的未知数，列出约束条件，建立目标函数；2 作出可行域；3 确定平移直线，寻找非整最优解；4 由直线方程换元代入约束条件，并求变量范围：5 对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）这几个整点。此时还必须从中选出一个最适合的点： 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）为最优整点解。平移近值法可以克服在前两种方法中有可能要多次平移找解的缺陷，适用范围广泛。其一般