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

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

2、目做一说明.在介绍方法之前，我们先做一点准备工作一一清楚下面的结论.结论:对于平面内两条平行直线11,12，设两线间的距离为d，则：I。）上的任意一点，到l （/）的距离等于d ； 1221夹在两平行线之间的点，到两平行线的距离都小于d ；不夹在两平行线之间也不在线上的点，到离它较远的平行线的距离大于d .用图形（图1）和代数式子表示如下：图1在同一平面内，直线11/12，它们之间的距离为d，则：AD = d, BE d, BF d .下面我们看如何求线性规划中的整点问题：题目1 （高中数学人教A版必修5,第89页例6）要将两种大小不同的钢板截成A,B,C三种规格，每张钢板可同时截得三种规格的

3、小钢板的块数如下表所示：第一种钢板211第二种钢板123今需要A,B,C三种规格的成品分别15,18,27块,问各截这两种钢板多少张可得所需A,B,C三种规格成品，且使所用钢板数最少？解析设需截第一种钢板x张，第二种钢板y张，可得2 x + y 15,x + 2y 18,且x, y都是整数.X + 3y 27,x 0, y 0,求目标函数z = x + y取最小值时的x,y .将目标函数变形为y = -x + z，则z表示直线 y = -x + z在y轴上的截距.作出由不等式组确定的区域及直线y = -x，如图2：平移直线 y = -x，在平移过程中（由图2）在不等式表示的区域内碰到的第一个（

4、或同时几个）整数点 就是此题的最优整点，即最优整点是所有可行解中到直线y = - x距离最小的.|2 x + y -15 = 0 人是方程组x + 3 y - 27二0|2 x + y -15 = 0 人是方程组x + 3 y - 27二0（18 39）的解，其坐标为,，不是整数点.I 5 5 7在A点（非整点最优解）附近（越近越好）找到一个整点B （在不等式组确定的区域内）:一 18因为A点横坐标满足：3 匚 4,我取B的横坐标为4 （本题也可取3）,将4代入区域边_ 23 一一界线方程x + 3y- 27 = 0得,y = 可工7.7，为了让B是整点且在不等式组确定的区域内，取B的纵坐标为

5、8,这样确定B（4,8）.平移直线y = - ,让其过点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距离最小的x + y -12 = 0（ 9 15 ）x + y -12 = 0解方程组q ”_八，得C点坐标-,，解方程组_八，得D点坐x + 3y 27 0卜 2 2 ）2x + y 15 0标（3

6、,9 ）.所以在AACD （包括边界）表示的区域内的整点横坐标在区间3,9内，即整点横坐标只能取3和4两个,对应到AACD （包括边界）表示的区域的整点,正好是B,D两个点, 由前面结论知,B, D到直线y x距离相等,所以,B, D两点对应的坐标都是此题的最优解,即当x 4,y 8或x 3,y 9 时,乙最小,乙,3 + 9 12.min题目2某人有楼房一幢，室内面积共180m2,拟分隔成两类房间作为旅游客房.大房间 每间面积为18m2,可住游客5名，每名游客每天住宿费为40元;小房间每间面积15m2,可住 游客3名，每名游客每天住宿费为50元;装修大房间每间需1000元，装修小房间每间需6

7、00元. 如果他只能筹款8000元用于装修,且游客能住满客房,他应隔出大房间和小房间各多少间，能 获得最大收益？解析 设隔出大房间x间,小房间y间时收益为工元，则x, y满足,x, y g Z，且 z - 200 x +150y18x,x, y g Z，且 z - 200 x +150y、y - 0,将不等式组等价化为6x将不等式组等价化为6x + 5 y 60, 5x + 3 y 40, x - 0,、y - 0,一4 z目标函数化为y = - 3 x+瓦,.（20 60.（20 60）,得A ,（非整点最优解），在A附近的区域内找一个 I 7 7 J4 z要使z最大,则直线y - -3x

8、+回 在y轴上的截距最大,作出不等式组表示的区域及44直线y-3x （如图4）：平移直线y-3x，在平移过程中（由图4）在不等式表示的区域 内碰到的最后一个（或同时几个）整数点，就是此题的最优整点,即最优整点是所有可行解中 到直线y-4 x距离最大的.16 x + 5 y - 60 - 0 解方程组L15 x + 3 y - 40 - 0整点B（3,8），过B作4x + 3y - 0的平行线4x + 3y - 36 - 0,如图5：14 x + 3 y 36 = 0则直线4 3 y - 36 = 0与5 3 y = 40交于点解方程组5x + 3 y - 40 = 0,得/ 20 1一 一一

9、一 一 一一C 4,；直线4x + y - 3=6与6x + 5 y - 60 = 0交于点D ,解方程组I 3 )4 x + y 3=6 0 /6x + 5 6=0 ,得0（0/2艮据题意要使z最大,则整点到直线4 3尸0距离最远,最优整点落在AAC。（包括边界）表示的区域内，根据C,D两点横坐标取值来确定在AACD （包括边界）表示区域内的整点：当横坐标取0时，在AACD （包括边界）表示区域内有整 点（0,12）,当横坐标取1时，根据边界线方程6 x + 5 y - 60 = 0得，在上边界上的纵坐标为,一 _ 3232 54根据边界线方程4x + 3y -36 = 0得，在下边界上的纵

10、坐标为y，而在y和y之间没有整 数,所以在AACD （包括边界）表示区域内没有横坐标是1的整数点，同理得出在AACD （包 括边界）表示区域内没有横坐标是2的整数点，横坐标是3的整数点是B（3,8）,没有横坐标是4的整数点.故在不等式表示的区域内，到直线4x + 3y = 0距离最远的整数点有（0,12）和（3,8）两个,因此使z最大的最优整数解是（0,12）或（3,8），代入z = 200 x +150y得,z诙=1800根据以上题目的解答可见，对于目标函数是形如z =以+ by的整点线性规划问题，我们可以通过下面几步求得整点最优解:.作出不等式组所约束的区域（能将不等式组化简的先化简再作图）,将目标函数变形成a.作出直线工一尸，平移找到非整点最优解A，在其附近找一个整点解B (在不等式约束的区域内).a,.过B作直线y二-小的平行线拼求出其方程IJ会缩