一道线性规划题的求解历程

《一道线性规划题的求解历程》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《福建中学数学》2010.05一道线性规划题的求解历程葛文明、蔡丹、朱　丹　　（江苏省扬州市新华中学）邮编225009笔者在日前的高三复习课上给出了一道线性规划中求整数解的题目，引起学生热烈地讨论．在一整课的“吵吵嚷嚷”声中，大家七嘴八舌，各抒己见，最终去伪存真，统一了认识，得到了较为科学的一般性解法．题目本身并不算难，但讨论的过程充分体现了以学生为主体、教师为主导的新课程理念，体现了素质教育的基本思想．讨论过程中，教师将大部分时间“交给”学生，让学生自主探求，充分暴露自己的思维质态，教师在尊重学生意见的同时并给予必要的修正和引导．这种民主、平等、和谐的交流方式极大地调动了学生的参与

2、热情，激发了他们的思维智慧，给学生主动加入到求解的行列中来并毫无保留地发表观点、施展才华提供了平台，学生在思考中争辩，在争辩中升华．学生学得轻松，教师教得不累．下面将这节课的教学过程介绍如下．题目：要将甲、乙两种长短不同的钢管截成A,B,C三种规格，每根钢管可同时截得三种规格的钢管的根数如下表所示：规格类型钢管类型A规格B规格C规格甲种钢管214乙种钢管231今需A,B,C三种规格的钢管各13，16，18根，问各截这两种钢管多少根可得所需三种规格钢管，且使所用钢管根数最少。6解：设需截甲种钢管根，乙种钢管根，则，设所用钢管根数为，本题要求的就是使目标函数最小的正整数解．作出可行域（如

3、图1）：　　　　　　　　按常规，过可行域中的点作出一组平行线（为参数），位置最低的直线经过的点就是最优解．由图可知，最优解应该是点，但由于都不是整数，所以不是最优解．那么，最优解是什么呢？（图1）一、众里寻他学生１：最优解是．很多学生点头赞成学生１的答案．师：为何是？行吗？行吗？学生１：因为，，所以是．不行，因为；也不行，因为．这时，许多学生笑了起来，因为他们发现，、、都在可行域中而且，所以，那么、就都行．师：学生1认为最优解的横纵坐标都要比的横纵坐标大，这个理由显然是站不住脚的．这从、也在可行域中就能看出这一点．有没有比更优的整数解呢？6学生2：最优整数解应该是．师：什么理由？学生

4、2：因为，并且也在可行域中．师：很好，至少比更优．那你是怎么得到这个结果的？学生2：看出来的．众：笑！师：点（0，8），（1，7），（2，6），（3，5），（5，3），（6，2），（7，1），（0，8）的横纵坐标之和也是８，那么这些点是不是最优解呢？学生2：不是，因为这些点都不在可行域中．师：看来学生２观察得比较细致．大家认可他的做法吗？没有人提出质疑．二、雾里看花师：以上的讨论大概告诉我们，是唯一的最优解．但是只凭感觉解题肯定是不严密的，有时还会出现错误．有没有更有说服力的解法？学生３：网格法．通过打网格（见图２），就能发现是最优解．学生基本赞成．师：网格法在许多情况下确实能帮助我

5、们找到最优解，但这个方法有它的缺陷——“找”的痕迹太浓，而且结果并不可靠．如果画图质量不高，或因为画笔的粗细，或因（图２）为观察得不仔细等因素，都能造成判断的误差，比如就很难从网格中看出（3，5）究竟在不在可行域中．用网格法找点，就好似雾里看花，似有若无，似无若有．事实上，仅凭观察，也很难判断是否在可行域中．所以我不赞成用网格法“求”整数解，我只认可用网格法帮助“寻找”6整数解．学生４：在点的周围有四个点（如图３）：（3，4），（4，4），（3，5），（4，5），其中（3，4），（3，5）不在可行域中，尽管（4，5）在，但由于4+5>4+4，　　　　　　　　（图３）所以（4，4）为最

6、优解．此时，有部分同学在下面议论了起来．师：大家有什么意见？有学生说：这还是网格法．师：对．其实他的解法还是网格法，只是将图２局部放大，网格少画了一些，少做了些无用功，有点掩耳盗铃的意味，求解过程中“找”的痕迹依然较浓，而且对于解的唯一性没有进行说明．学生５：因为，所以最优解应满足，不但满足这个等式，而且也在可行域中，所以最优解是．学生６：最优解应该是直线上到原点距离最近的整数点，这个点就是．师：学生５、学生６的解法更进了一步，因为他们都将最优解锁定在直线上，这是本题求解过程中的重大进步，这比前面盲目“找”点的方法显得理性和严谨．但不知道我们有没有发现，他们在认定最优解是满足的的时候

7、，有没有验证直线上是否还有其他整数解？也就是解的个数问题没有解决．我们能否再进一步找到一种行之有效的方法，使得求出来的解不重不漏呢？片刻以后，有学生举手．三.云开月朗学生7：设直线与交于点，直线6与交于点．分析图像（如图4）可知，最优解一定在线段上，线段上有几个整数点，就有几个最优解，线段上没有整数点，那就到直线上去求．　　　　　　　　　　　　　　　　　　　　　（图4）故先解方程组，得，再解，得，所以，其中只有４这个整数，所以最终的最优解是．师：太好了！这