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

福建中学数学2010.05一道线性规划题的求解历程葛文明 、 蔡 丹、 朱丹（江苏省扬州市新华中学）邮编225009笔者在日前的高三复习课上给出了一道线性规划中求整数解的题目，引起学生热烈地讨论在一整课的“吵吵嚷嚷”声中，大家七嘴八舌，各抒己见，最终去伪存真，统一了认识，得到了较为科学的一般性解法题目本身并不算难，但讨论的过程充分体现了以学生为主体、教师为主导的新课程理念，体现了素质教育的基本思想讨论过程中，教师将大部分时间“交给”学生，让学生自主探求，充分暴露自己的思维质态，教师在尊重学生意见的同时并给予必要的修正和引导这种民主、平等、和谐的交流方式极大地调动了学生的参与热情，激发了他们的思维智慧，给学生主动加入到求解的行列中来并毫无保留地发表观点、施展才华提供了平台，学生在思考中争辩，在争辩中升华学生学得轻松，教师教得不累下面将这节课的教学过程介绍如下题目：要将甲、乙两种长短不同的钢管截成A,B,C三种规格，每根钢管可同时截得三种规格的钢管的根数如下表所示： 规格类型钢管类型A规格B规格C规格甲种钢管214乙种钢管231今需A,B,C三种规格的钢管各13，16，18根，问各截这两种钢管多少根可得所需三种规格钢管，且使所用钢管根数最少。解：设需截甲种钢管根，乙种钢管根，则，设所用钢管根数为，本题要求的就是使目标函数最小的正整数解作出可行域（如图1）：按常规，过可行域中的点作出一组平行线（为参数），位置最低的直线经过的点就是最优解由图可知，最优解应该是点，但由于都不是整数，所以不是最优解那么，最优解是什么呢？ （图1）一、众里寻他学生：最优解是很多学生点头赞成学生的答案师：为何是？行吗？行吗？学生：因为，所以是不行，因为；也不行，因为这时，许多学生笑了起来，因为他们发现，、都在可行域中而且，所以，那么、就都行师：学生1认为最优解的横纵坐标都要比的横纵坐标大，这个理由显然是站不住脚的这从、也在可行域中就能看出这一点有没有比更优的整数解呢？学生2：最优整数解应该是师：什么理由？学生2：因为，并且也在可行域中师：很好，至少比更优那你是怎么得到这个结果的？学生2：看出来的众：笑！师：点（0，8），（1，7），（2，6），（3，5），（5，3），（6，2），（7，1），（0，8）的横纵坐标之和也是，那么这些点是不是最优解呢？学生2：不是，因为这些点都不在可行域中师：看来学生观察得比较细致大家认可他的做法吗？ 没有人提出质疑二、雾里看花师：以上的讨论大概告诉我们，是唯一的最优解但是只凭感觉解题肯定是不严密的，有时还会出现错误有没有更有说服力的解法？学生：网格法通过打网格（见图），就能发现是最优解学生基本赞成师：网格法在许多情况下确实能帮助我们找到最优解，但这个方法有它的缺陷“找”的痕迹太浓，而且结果并不可靠如果画图质量不高，或因为画笔的粗细，或因 （图）为观察得不仔细等因素，都能造成判断的误差，比如就很难从网格中看出（3，5）究竟在不在可行域中用网格法找点，就好似雾里看花，似有若无，似无若有事实上，仅凭观察，也很难判断是否在可行域中所以我不赞成用网格法“求”整数解，我只认可用网格法帮助“寻找”整数解学生：在点的周围有四个点（如图）：（3，4），（4，4），（3，5），（4，5），其中（3，4），（3，5）不在可行域中，尽管（4，5）在，但由于4+54+4，（图）所以（4，4）为最优解此时，有部分同学在下面议论了起来 师：大家有什么意见？有学生说：这还是网格法师：对其实他的解法还是网格法，只是将图局部放大，网格少画了一些，少做了些无用功，有点掩耳盗铃的意味，求解过程中“找”的痕迹依然较浓，而且对于解的唯一性没有进行说明学生：因为，所以最优解应满足，不但满足这个等式，而且也在可行域中，所以最优解是学生：最优解应该是直线上到原点距离最近的整数点，这个点就是师：学生、学生的解法更进了一步，因为他们都将最优解锁定在直线上，这是本题求解过程中的重大进步，这比前面盲目“找”点的方法显得理性和严谨但不知道我们有没有发现，他们在认定最优解是满足的的时候，有没有验证直线上是否还有其他整数解？也就是解的个数问题没有解决我们能否再进一步找到一种行之有效的方法，使得求出来的解不重不漏呢？片刻以后，有学生举手三. 云开月朗学生7：设直线与交于点，直线与交于点分析图像（如图4）可知，最优解一定在线段上，线段上有几个整数点，就有几个最优解，线段上没有整数点，那就到直线上去求（图4）故先解方程组，得，再解，得， 所以，其中只有这个整数，所以最终的最优解是 师：太好了！这样处理以后，不但找到了一个最优解，而且说明了不再有其它的整数解了其实，这就是我们今天要寻求的求整数解的最佳方法：先确定最优解所在的直线，通过解方程组求出最优解所在的线段，确定一个变量的范围，再由目标函数和约束条件来确定最后的整数解一般地，线段上有几个整数点，最终就有几个最优整数解这样的方法可以克服网格法、观察法等不规范的方法所带来的弊端，做到了不重复不遗漏，是最科学的方法，而且解题过程逻辑简单，层次分明至此，这道题的求解历程圆满完成点评：这节课虽然没有太多“靓点”，显得比较“平淡”，但笔者认为这是一节富有成效的课，理由如下：这节课有明确的教学目标，即如何获得求整问题的一般性方法因此，所有教学行为都有的放矢，时间利用率高；教师有意识地将课堂“交”给学生，充分调动了学生的参与热情和探求欲望，教师对学生意见的尊重和恰到好处的引导使学生在探求中彻底地打开了思维的闸门并不断闪现出智慧的火花，大家在争辩中