也谈线性规划中整点最优解的一种处理方法*

2017-06-15甘肃省会宁县第二中学730799李平

中学数学研究(广东) 2017年9期

甘肃省会宁县第二中学(730799) 李平

甘肃省会宁县第二中学(730799) 李平

线性规划是解决现实生产、生活中遇到的资源利用、人力调配、生产安排等问题的一种数学思想方法.高中人教A版数学书中,将其安排在必修5第三章.在对线性规划的教学中,我发现学生对最优解是整数点的这类问题的解答存在困难,教科书对这类问题的解答也比较模糊(主要是最优解产生过程),通过查阅资料,笔者发现解决整点问题的方法也比较多,但这些方法有的简单而适用范围窄(如文献[2]中的解法,要求目标函数也取整数),有的适用范围大但却比较麻烦(如文献[3]中的方法,网格法和筛选法),那么有没有一种适用性广,且简单易于理解的方法呢?笔者通过仔细琢磨,发现了一种方法,下面通过两个题目做一说明.

在介绍方法之前,我们先做一点准备工作—清楚下面的结论.

结论:对于平面内两条平行直线l1,l2,设两线间的距离为d,则:

①l1(l2)上的任意一点,到l2(l1)的距离等于d;

②夹在两平行线之间的点,到两平行线的距离都小于d;

③不夹在两平行线之间也不在线上的点,到离它较远的平行线的距离大于d.

图1

用图形(图1)和代数式子表示如下:

在同一平面内,直线l1//l2,它们之间的距离为d,则:AD=d,BE＜d,BF＜d,CG＞d.

下面我们看如何求线性规划中的整点问题:

题目1(高中数学人教A版必修5,第89页例6)要将两种大小不同的钢板截成A,B,C三种规格,每张钢板可同时截得三种规格的小钢板的块数如下表所示:

A规格B规格C规格第一种钢板2 1 1第二种钢板1 2 3

今需要A,B,C三种规格的成品分别15,18,27块,问各截这两种钢板多少张可得所需A,B,C三种规格成品,且使所用钢板数最少?

解析设需截第一种钢板x张,第二种钢板y张,可得

且x,y都是整数.

图2

求目标函数z=x+y取最小值时的x,y.将目标函数变形为y=−x+z,则z表示直线y=−x+z在y轴上的截距.作出由不等式组确定的区域及直线y=−x,如图2:平移直线y=−x,在平移过程中(由图2)在不等式表示的区域内碰到的第一个(或同时几个)整数点,就是此题的最优整点,即最优整点是所有可行解中到直线y=−x距离最小的.

如果不考虑x,y都是整数这一条件,则平移直线y=−x,当其过点A时,z的值最小,但A是方程组的解,其坐标为不是整数点.

在A点(非整点最优解)附近(越近越好)找到一个整点B(在不等式组确定的区域内):因为A点横坐标满足:我取B的横坐标为4(本题也可取3),将4代入区域边界线方程得为了让B是整点且在不等式组确定的区域内,取B的纵坐标为8,这样确定B(4,8).

图3

平移直线y=−x,让其过点B,这样确定一条直线l:x+y−12=0,如图3,直线x+y−12=0会和不等式表示的区域边界交于D,C两点,现在我们能确定最优解必定落在△ACD(包括边界)表示的区域内(由前面给的结论可知,在直线x+y−12=0右上方区域内的所有点到y=−x的距离大于点B到直线y=−x距离,所以到直线y=−x距离最小的整点必在△ACD(包括边界)表示的区域内).

题目2某人有楼房一幢,室内面积共180m2,拟分隔成两类房间作为旅游客房.大房间每间面积为18m2,可住游客5名,每名游客每天住宿费为40元;小房间每间面积15m2,可住游客3名,每名游客每天住宿费为50元;装修大房间每间需1000元,装修小房间每间需600元.如果他只能筹款8000元用于装修,且游客能住满客房,他应隔出大房间和小房间各多少间,能获得最大收益?