线性规划中整点最优解的求解策略

郭海鹰

【摘 要】随着中学数学教育的改革和发展，简单线性规划问题已经逐渐成为中学数学教学中的一个基本内容。简单线性规划问题与我们的日常生活息息相关，它主要涉及人力、物力、资金等资源的最优配置。在中学数学教学中，整点最优解问题是简单线性规划的核心内容，但教材对于具体的验算过程并没有作过多的描述，以致中学生在解题过程中对于具体的验算过程掌握还不够清晰。在资料上也经常见到有关简单线性规划整点最优解问题的求解方法，如：网格法，穷举法，筛选法，最小距离法等。本文将介绍利用平移法求整点最优解的两种具体的操作方法—平移交轨法，平移近值法。

【关键词】线性规划；平移；整点最优解

【中图分类号】G633.6 【文献标识码】B 【文章编号】1671-8437（2018）10-0069-02

1 平移交轨法

该方法主要是在平移直线过程中，利用直线间的交点来缩小最优值的存在范围，因此其主要思想是联立方程求解交点，然后确定最优解可能的存在范围。

例1 要将两种大小不同的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：

根据目标函数作出一组平行直线：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的交点：

可得交点坐标为B（3，9），D（，），故有：3≤x≤

这样便更进一步的缩小了x的范围，即x=3或4，将其代入x+y=12，可得y=9或8。即（3，9）和（4，8）均为所求的最优解。

根据上述的分析解答过程，我们可以看到利用平移交轨法解题对于一般的简单线性规划问题都是适用的，其解题步骤如下：

（1）设出所求的未知数，列出约束条件，建立目标函数；

（2）作出可行域；

（3）确定平移直线，寻找非整最优解；

（4）联立方程求交点确定x或y的范围；

（5）对x，y进行整点搜索，并确定整点解。

2 平移近值法

该方法也是以平移直线为基础，但它并非一步一步的平移，而是在非整点最优解附近搜索，同时结合网格（并非所有网格都打出），直接找出附近的整点来减小搜索范围，从而求出整点最优解。

例2 某人有房子一幢，室内面积共180m2，拟分隔成两类房间作为游客住房。大房间每间面积为18m2，可住游客5名，每名游客每天住宿费为40元；小房间每间面积为15m2，可住游客3名，每名游客每天住宿费为50元；装修大房间每间需1000元，装修小房间每间需600元。如果他只能筹款8000元用于装修，且游客能住满客房，他应隔出大房间和小房间各多少间，能获得最大收益？（新教材65页习题4）

分析：设他应隔出大房间x间，小房间y间，能获得收益为z元。

作直线：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）为最优整点解。

平移近值法可以克服在前一种方法中有可能要多次平移找解的缺陷，适用范围广泛。其一般步骤归纳如下：

（1）设出所求的未知数，列出约束条件，建立目标函数；

（2）作出可行域；

（3）寻找非整点最优解A，根据A点的坐标在其附近寻找最近的整点B；

（4）过B作平移直线，通过直线确定较小的搜索范围；

（5）利用部分網格在确定的范围内求最优解。

总之，以上两种基本方法都是以平移法为基础，对于一般的简单线性规划问题都能够求解。但对于目标函数t=ax+by，若t，a，b经约分后仍较大时，运用第一种方法要调整多次才可能达到最优。平移近值法弥补了这种方法的不足，直接在非整点最优解附近的小范围内搜索，借用部分网格得出整点最优解。两种方法各有各的特点，因此有时要根据具体情况选择合理的方法。