如何选取线性规划问题中的最优整数解

摘要：线性规划是运筹学的一个重要组成部分，是辅助人们进行科学管理的一种数学方法，在实际生活中有着广泛的应用。本文就线性规划问题中的最优整数解给出了若干可操作的方法，使学生在学习中胸有成竹，有的放矢，从而激发学生兴趣，激活学生思维，培养学生创新精神和实践能力，达到应用和优化的目的。

关键词：线性规划；最优解；整数解；数学

所谓线性规划问题是在线性约束条件下，求目标函数的最值问题，它是优化的数学模型之一，通过二元一次不等式刻画平面区域直观地解决实际生活中的数学问题。它融入了金融、教育投资、工厂生产、饮食营养等，体现数学源于生活，让学生感受生活中的二元一次不等关系。通过平面区域的直观联系，让学生去解决资源利用，人力调整，生产安排等方面的优化问题。然而既然是生活中的数学，那就必须考虑问题的可行性，如人员的分配中，人数必须是非负整数等等。

如：要将两种大小不同的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如表所示。今需要A、B、C三种规格的成品分别为15、18、27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少？

规格类型钢板类型规格A规格B规格C

第一种钢板211

第二种钢板123

教材中作了如下解答

解：设需截第一种钢板x张，第二种钢板y张，则线性约束条件为

2x+y≥15x+2y≥18x+3y≥27x≥0，x∈Ny≥0，y∈N可行域如图

目标函数为z=x+y，把它变形为y=-x+z，得到斜率为-1，在y轴上的截距为z的一簇平行直线，由图可知，当直线经过可行域内的点M时，截距最小。

解方程组x+3y=272x+y=15得M185，395

由于185，395都不是整数，而此问题中的最优解（x，y）中的x，y必须是整数，所以点185，395不是最优解。经过可行域内的整点（横坐标和纵坐标都是整数的点）且截距z最小的直线是x+y=12，经过的整点是B（3，9）和C（4，8），它们是最优解。zmin=12。

答：要截得所需三种规格的钢板，且使所截两种钢板的张数最少的方法有两种，第一种截法是截第一种钢板3张、第二种钢板9张；第二种截法是截第一种钢板4张、第二种钢板8张。两种方法都最少要截这两种钢板共12张。

在这里，问題处理是笼统的，学生对于所取的这两个最优整数解是心存疑虑的，首先它们是怎么被找到的，其次最优整数解是否找全，当整数点位于可行域的边界时是否可行，问题的发现源于笔者布置的一题课后作业题：

求z=5x+4y的最大值，使x，y满足约束条件3x+4y<10x+4y≤11x≥0，x∈Ny≥0，y∈N

下面以此题为例就如何调整最优整数解加以详细说明。

解：根据线性约束条件画出可行域，

把目标函数z=5x+4y变形为y=-54x+z4，它表示斜率为-54的一簇平行直线，当直线经过可行域内的点M时，截距z4最大，即z最大，解方程组

3x+2y=10x+4y=11得M（1.8，2.3）

Zmax=5×1.8+4×2.3=18.2。

显然1.8N，2.3N，而此题需要得到整数解。笔者就此给出了3种较可操作的方法：

一、 打网格法

利用坐标轴中的刻度画出网格线，凡整数点都位于小方格的顶点上，那么对于可行域中的整数点，哪些是最优的整数点呢？我们可以先画出经过原点的直线y=-54x，然后利用直角三角尺和直尺平移，由于任一条斜率为-54的直线上，y轴上截距都是固定的，所以我们要找截距最大的直线，又要获得整数解，只要在与可行域有公共点的平移直线中，找与直线y=-54x+18.24最近的平移直线，它们之间的整数点，即为最优整数解。此题易得最优整数解为（3，0）。

用网格法求最优整数解的要求是作图必须精确，这样得到的结论才是准确的。由于学生都是手工作图，所以要求学生在作图过程中最好以厘米为单位打网格线，对于边界的整点，可以借助计算进行检验是否在可行域内。若是平时作业可以借助厘米纸，刻度较为精确。此方法的特点是直观。

二、 调整优值法

先求得理论最优值，然后根据需要，适当调整，也可以是多次调整，直到找到理想的最优结论，称为调整优值法。上题中z=18.2是理论最优值，由于x∈N，y∈N，所以实际的情况只可能是比18.2小的整数，所以我们从18开始调整，即

（1）5x+4y=18则y=18-5x4代入3x+2y<10x+4y≤1174≤x<2，显然在x∈N中无解，需继续调整。

（2）5x+4y=17则y=17-5x4代入3x+2y<10x+4y≤1132≤x<3，x∈N，则x=2代入得y=74，显然yN，需继续调整。

（3）5x+4y=16则y=16-5x4代入3x+2y<10x+4y≤1154≤x<4，x∈N，则x=2或x=3，当x=2时代入得y=32，显然yN，当x=3时代入得y=14，显然yN，需继续调整。

（4）5x+4y=15则y=15-5x4代入3x+2y<10x+4y≤111≤x<5，x∈N，则x=1或2或3或4，从而得到4组解。依次为x=1y=52，x=2y=54，x=3y=0，x=4y=-54，由于x∈N，y∈N，所以只有x=3y=0符合条件，于是停止调整，得zmax=15。

用调整优值法求最优整数解有时会计算量较大，但其结果是最精确的，学生也感觉这种方法最为可靠。

三、 代数列举法

由不等式组3x+4y<10x+4y≤11x≥0，x∈Ny≥0，y∈N可以粗略地得0≤x≤3，0≤y≤2，所以x=0，1，2，3，y=0，1，2，所以所有的整数解可能是

从右下角的（3，2）开始，分别沿图示的三个方向同时一一代入目标函数 进行检验，当把（3，2）代入目标函数时，得z=23，此时z的值超出理想最优值18.2，显然不可能，那是由于不在可行域而引起的，（3，1）亦然，于是继续沿图示的三个方向代入目标函数，注意三个方向轮换进行检验，若z的值小于理想最优值18.2时，需检验是否满足不等式组的条件，如（2，2）代入得z=18，但（2，2）不满足不等式（1），通过这种方法，找到合适的条件停止，否则向里层继续寻找。按照这种顺序寻找可以减少计算量，易得最优整数解为（3，0），从而zmax=15。

用代数列举法求最优整数解过程中，根据不等式，粗略地解出整数解范围，会导致超出可行域，应在三个方向同时进行，然后把三个方向中使取得最大值的那个整数点x，y的值代入不等式检验，若满足不等式，则找到最优解，否则继续检验。若找目标函数取最小值的最优整数解，检验的方向需反之。

上述三种方法求最优整数解，各有其优势，对于不同的题目及题目类型，学生可以根据自己的实际水平和熟练程度，合理选择。

参考文献：

[1]刘继宽.谈新教材中简单线性规划的认识[J].基教瞭望，2008.

[2]廖宇波.《线性规划》课程教学的实践与体会[J].华东交通大学学报，2007（12）.

[3]田继安，王国立.线性规划问题中的整点最优解[J].商丘职业技术学院学报，2007，6（5）：20-22.

作者简介：

朱玲娣，浙江省绍兴市，绍兴市技工学校。