线性规划
浅谈“线性规划中的整点最优解”的几种求法
湖州中学 顾钰萍
《简单的线性规划问题》是高中数学教材必修5第三章《不等式》的内容。求线性目标函数的最值问题是本节的重点，也是本节的难点。课本给出了三个典型例题来介绍实际的线性规划问题。其中例5和例6代表了第一类线性规划问题：给定一项任务，问怎样统筹安排，能使完成这项任务的人力、物力资源最小。例7代表了第二类线性规划问题：给定一定数量的人力、物力资源，问怎样安排运用这些资源，能使完成的任务量最大。其中例6是一个求整点最优解的问题，更是线性规划问题的一个难点中的难点。
在实际教学过程中我发现学生很难理解教材给出的解答过程，不知道课本给出的最优解是如何得到的。经过实际的教学研究和资料查阅我得到几种寻求“线性规划中的整点最优解”的方法。
一、网格法寻找整点最优解
网格法寻找整点最优解是最容易让学生理解接受的一种方法。该方法的本质是直线的平移，但它并非一步一步的平移，而是在非整点最优解附近搜索，同时结合网格，直接找出附近的整点来减小搜索范围，从而求出整点最优解。
例 某人有楼房一幢，室内面积共1802m ，拟分隔成两类房间作为旅游客房，大房间每间面积为182m ，可住游客5名，每名游客每天住宿费为40元；小房间每间面积为152m ，可住游客3名，每名游客每天住宿费为50元；装修大房间每间需1000元，装修小房间每间需600元。如果他只能筹款8000元用于装修，且游客能住满客房，他应隔出大房间和小房间各多少间，能获得最大收益？
解：设隔出大房间x 间，小房间y 间，收益为z 元，则 ??
?
??∈≥≤+≤+Z y x y x y x y x ,,0,800060010001801518 其中 y x z 150200+=
0150=+y
A 点时与原=8000 但不是整数
，我们利用
A 附近找
到（0，12），（1，10），（2，9），（3，8），（4，6），（5，5），（6，3），（7，1）（8，0）这几个整点。经检验，（0，12）和（3，8）都是最优解，此时1800=z 。
这种方法适用于区域是封闭区域，且区域内的整数点可数，坐标网络画出来容易在图上识别哪些整点在可行域内。 二、穷举法寻找整点最优解
如果我们对z 的所有可能取到的整数解进行尝试，验证它是否在可行域内，也可以找到我们想要的整点最优解。
下面我们以穷举法来求解上面的例题。
解：设隔出大房间x 间，小房间y
??
?
??∈≥≤+≤+Z y x y x y x y x ,,0,800060010001801518 其中 y x z 150200+= 如图可行域是阴影部分， 作直线L ：0150200=+y x
将直线L 平移到A 点时与原点距离最大。 解方程组
??
?=+=+8000
6001000180
1518y x y x 得A （2060,7
7
），但不是整数解。此时z =200×206015077+?=
13000
18577
≈。 又)34(50150200y x y x z +=+=，
故z 取到的最优解一定被50整除，则z 的最大值可能是1850。
即3734=+y x ，又3734=+y x 的所有整数解是（1，11），（4，7）（7，3）， 而（1，11）不满足6056≤+y x ，舍去； （4，7）不满足4035≤+y x ，舍去； （7，3）不满足4035≤+y x ，舍去。
所以z 的最大值不可能是1850。则z 的最大值可能是1800、1750、1700…，直到在可行域内找到满足条件的最优解。
若z =1800，即3634=+y x ，又3634=+y x 的所有整数解是（0，12），（3，8）（6，4），（9，0），经检验只有（0，12），（3，8）在可行域内，所以当12,0==y x 或8,3==y x 时，
z 取到最大值1800。
这种方法利用z 的可能取值来寻找最优解，只要计算正确，就能准确不漏的找到所有的
整点最优解。
三、换元法寻找整点最优解
类似穷举法，换元法也是利用z 的所有可能取值，但是并不是找出所有可能的整数解，而是利用换元来减少线性约束条件的元数，以得出参数的范围，从而确定出变量x ，y 的取值，再来确定最优解的可能值。
下面我们以换元法来求解上面的例题。
解：设隔出大房间x 间，小房间y
??
?
??∈≥≤+≤+Z y x y x y x y x ,,0,800060010001801518 其中 y x z 150200+= 如图可行域是阴影部分， 作直线L ：0150200=+y x
将直线L 平移到A 点时与原点距离最大。 解方程组
?
?
?=+=+80006001000180
1518y x y x 得A （2060,7
7
），但不是整数解。此时z =200×206015077+?=
13000
18577
≈。 又)34(50150200y x y x z +=+=，
故z 取到的最优解一定被50整除，则z 的最大值可能是1850。 则3734=+y x ，即3
437x
y -=，将其代入约束条件得：
???
???
?
≤-?
+≤-?+8000
3
4376001000180
34371518x x x x
可得
32
5≤≤x 。又x 为整数，故3=x ，此时y 为非整数，故在直线3734=+y x 时，即
1850=z 无最优解。
那么z 的最大值可能是1800，则3634=+y x ，即3
436x y -=
，将其代入约束条件得：
???
???
?≤-?
+≤-?+8000
3
4366001000180
34361518x x x x
可得40≤≤x ，又x 为整数，故=x 0，1，2，3或4，代入3634=+y x 得它们对应的=y 12，
3
32，
3
28，8，
3
20。故可得最优解为（0，12）和（3，8），此时z =1800。
这种方法利用换元来得到参数的范围，相对来说不会因为画图不准确等原因而遗漏掉个别不太明显的整点最优解。
三种方法各有各的特点，因此解题要根据具体情况选择合理的方法。但总得来说本质都是以平移法为基础，对于一般的简单线性规划问题都能够求解。