用“小范围搜索法”求“线性规划问题”的最优整数解，本文主要内容关键词为：线性规划论文,整数论文,最优论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
“简单线性规划”是新增加的教学内容，也是培养学生探索能力，加强数学应用的很好素材，如何把握好这一新内容的尺度，又如何实施教学是广大教师十分关心的问题.
笔者认为线性规划的教学，如果教师人为地超出教科书的要求，教得太深太难，是不对的.反之，低于教科书的要求，马马虎虎，一带而过，也是不对的.教师应该认真钻研教材，在教学过程中把教科书的内容落实好，使学生学懂教科书上的知识，学会做教科书上的题目.在理解原理的基础上掌握解题的技能，达到大纲要求的“简单会用”的目的.
笔者对教科书中的全部7个线性规划的实际应用问题进行了研究和分类.其中1个问题（教科书第61页例3）的最优解不是整数解，最优解有且只有一个，最优解显然在边界折线的顶点处，此为第一类问题；有3个问题（教科书第64页练习第2题、第65页习题7.4第3题，第66页研究课题与实习作业）的最优解为整数解，最优整数解有且只有一个，最优解整点显然在边界折线的顶点处，此为第二类问题；另有3个问题（教科书第63页例4、第65页习题7.4第4题、第87页复习参考题七A组第16题）的最优解为整数解，最优整数解可能不止一个，最优解整点不在边界折线的顶点处，或虽在边界折线的顶点处但并不显然，此为第三类问题.第一、第二类问题的最优解可以通过解一个二元一次方程组直接得到，学生比较容易掌握.第三类问题的最优解不能通过解一个二元一次方程组直接得到，必须通过观察图形或计算检验去寻找，学生不容易掌握，学习困难比较大.
为了解决这类寻找最优整数解的困难，笔者采用“小范围搜索法”进行教学.该方法的优点在于，把在大范围同寻找最优整数解转化为在小范围内寻找最优整数解，而且在通过观察图形作出准确判断有困难的情况下，通过计算检验作出准确判断的工作量比较小.其步骤为（1）在边界折线顶点附近的小范围内搜索一个可行域内的整点；（2）过该点作一条斜率为-A/B（其中A，B分别为目标函数中变量x，y的系数）的直线，与可行域边界折线相交得到一个小范围的区域；（3）在这个小范围区域内继续搜索全部最优整数解.
用“小范围搜索法”成功解题的关键是分析，要把分析贯彻于解题的全过程，观察图形要分析，计算检验也要分析，通过分析充分发掘线性约束条件和线性目标函数的特殊性，使搜索范围缩到最小，计算的工作量减到最小.下面以教科书中的题目为例，说明“小范围搜索法”的运用.
例1 教科书第65页习题7.4题，题目略.
本题的线性约束条件
线性目标函数z=200x+150y，其中x，y分别为大房间与小房间的间数.作出可行域如图1.
（1）搜索一个可行域内邻近边界折线顶点的整点.
得到点A（20/7，60/7）由于点A坐标不是整数，故不是最优解.由于要使目标函数取最大值，因此要寻找可行域右上侧靠近边界或边界上的整点.与点A邻近的整点共有4个（2，8），（2，9），（3，8）与（3，9），显然点（2，8）是可行域内的整点，点（3，9）不是可行域内的整点.记点（a，b）处的目标函数的值为z（a，b）.由于z（2，9）＞z（2，8），所以还应检验点（2，9）与（3，8）是否在可行域内.注意到目标函数z=200x+150y=150（z+y）+50x，而2+9=3+8，所以必有z（3，8）＞z（2，9），所以应先检验点（3，8）是否在可行域内.观察与计算都表明该点在可行域内.记点（3，8）为B，B即为搜索到的可行域内邻近边界折线顶点的整点.
（2）作出可行域内的小范围搜索区域.
算出z（3，8）=1800，过B作直线200x+
得到点D（4，20/3），△ACD即是新的搜索区域，在S△ACD（包括边）内可以搜索到全部最优解整点，该搜索区域比可行域大大缩小，如图2.
（3）在△ACD（包括边）内搜索最优解整点.
通过观察图形可知△ACD（包括边）内整点只有B（3，8）与C（0，12），由于B，C在一直线上，所以z（0，12）=z（3，8）=1800，B，C均为最优解整点，1800为目标函数的最大值.若要通过计算检验在△ACD（包括边）内搜索，由于x∈[o，4），y∈（20/3，12]，所以选择x的整数值检验可使计算量小些，令x=0，1，2，3，即可得到△ACD（包括边）内的全部整点只有B（3，8）与C（0，12）.显然，“小范围搜索法”的计算量要比把可行域内的整点逐一代入计算检验大大减少.
至此用“小范围搜索法”解题已全部完成，但在此解题过程中还可以有新的发现.注意到点C（0，12）即为直线6x+5y=50与y轴的交点，直线5z+3y=40与x轴的交点为（8，0），这两个点都在可行域内，且都是可行域边界折线的顶点，又z（8，0）；1600＜z（0，12），所以在以实施“小范围搜索法”的第一步操作时，即可选定点C，再过点C作直线200x+150y=1800
4x+3y=36，同样可以得到△ACD.这就是第二种搜索方法.显然第二种搜索方法比前面的第一种搜索方法更简便.只是第二种搜索方法在观察图形时不易发现，因为观察图1总让人觉得应该在点A（20/7，60/7）附近找一个整点比较好.这正是观察的局限性.观察是认识事物的开端和基础，其重要性是不容忽视的.但观察不容易深入事物的本质，总不如思维的深刻严密，也不如计算的准确可靠.
例2 教科书第85页复习参考题七A组第16题，题目略.
本题的线性约束条件
线性目标函数z=160x+252y，其中x，y分别为A型车和B型车的辆数.
作出可行域如图3.
（1）搜索一个可行域内邻近边界折线顶点的整点.
A，B两点都是可行域边界折线的顶点，但它们都不是整点，所以不是最优解.由于要使目标函数取最小值，因此要寻找可行域左下侧靠近边界上的整点.显然点（7，1）与（3，4）都是可行域内的整点，又z（7，1）=160×7+252×1=1372，z（3，4）=160×3+252×4=1488，z（7，1）＜，z（3，4），故点（7，1）优于点（3，4）.记点（7，1）为C，点C即为搜索到的可行域内邻近边界折线顶点的整点.
（2）作出可行域内的小范围搜索区域.
设点（3.4，3.3）为D，得到△ACD，在△ACD（包括边）内可以搜索到全部最优解整点，该搜索范围比可行域大大缩小，如图4.
（3）在△ACD（包括边）内搜索最优解整点.
通过观察图形可知在AACD（包括边）内，整点只有（7，1）与（5，2），由于点（5，2）在线段CD的下方，故必有z（5，2）＜z（7，1），记点（5，2）为E，E即为最优解整点.z（5，2）=160×5+252×2=1304即为目标函数的最小值.若要通过计算检验在△ACD（包括边）内搜索，由于x∈（3.4，7]，y∈[1，3.3），所以选择y的整数值检验可以使计算量小些，令y=1，2，3，即可得到△ACD（包括边）内的全部整点只有C（7，1）与E（5，2）.显然，“小范围搜索法”的计算量比将可行域内的整点逐一代入计算检验大大减少.
从上面的两个例子中可以看到，用“小范围搜索法”解线性规划应用问题，目标明确，思路清晰，步骤简明，操作性强，计算量小，准确可靠，既不会增解也不会失解，且不怕作图和观察的误差.笔者在用此法进行“简单线性规划”教学时，收到了较好的效果，学生感到容易理解接受，操作运用也方便.事实上，这种逐步缩小目标范围的搜索法是一种具有普遍意义的方法，对培养学生的探索精神，进行思维训练，提高分析问题、解决问题的能力很有好处，是一种有价值的好方法.