基础数学 02 整点规划问题的打开方法-《中学生数理化》高考版·自主招生 2019年9月刊（理化）

中学生数理化 基础数学名师讲座 自主招生2019年9月 整点规划问题的打开方法 ■王洪民 人教版高中数学必修5“简单的线性规 根据线性规划问题的构成,要找整点最 划问题”中有这样一道例题: 优解,可以从整点和最值两个方面入手分析。 例题要将两种大小不同的钢板截成 方法一:整点验证法 B、C三种规格,每张钢板可同时截得三种 找整点最优解,自然要考虑可行域内坐 规格的小钢板的块数如表1所示: 标都是整数的点,有时可行域内的整点无限 表1 多,没办法也没必要一一求出对应的目标函 规格类型 数值,往往只是有选择性地验证部分点。如 钢板类型 例题,找出可行域上与直线x+y=-距离最 第一种 1839 近的点,一般是取非整点最优解 123 55 今需A,B,C三种规格的成品分别为近的点进行验证。因为5」=3,3 15,18,27块,问:各截这两种钢板多少张可 7,7<<8,所以先考虑点(3,7) 得所需三种规格成品且使所用钢板张数最 (3,8),(4,7),(4,8),其中点(4,8)在可行域 解:设需要第一种钢板x张,第二种钢板上,对应z=12,因12是大于的最小整数 张,钢板总数为z张,则约東条件为 故点(4,8)就是最优解,zm=12。整点验证 2x+y≥15 x+2y≥18, 目标函数为z 法的优点是思维简单自然,缺点是容易漏解。 x+3y≥27,x≥0,y≥0。 如本例进一步求解可知点(3,9)也是整点最 优解 根据图 方法二:调整最值法 25 20) 换个角度,从目标函数的最值入手,通过 划问题得 调整最值并观察相应目标函数图像寻求整点 最优解。对于当x,y都是整数时,z也是整 202530 数的情况,如例题,z=x+y,且x≥且z∈ +3y=27 先考虑x+y=12,直线x+y=12与边界 线2x+y=15和x+3y=27的交点是(3,9) 最小等于57,但是x,y必须都是整数,故点和(22),不定方程x+y=12在x∈ 5,5)不是最优解。经过可行域内的整点 3,。的整数解为(3,9)和(4,8),故整点最 (横纵坐标都是整数的点),且使截距x最小优解是(3,9)和(4,8),zm=12。如果x+ 的直线是x+y=12。经过的整点是(3,9和=12在可行域上无整数解,再依次考虑x (4,8),它们是最优解,zm=12。 y=13,x+y=14,………调整最值法的优点是 这一解答容易让人一头雾水,直线x+y不易漏解,缺点是无法预知哪条直线才经过 12是怎么确定的?整点(3,9)和(4,8)又可行域上的整点 是怎么得到的?这类问题有没有一般解法? 作者单位:河南省开封市第二十五中学