线性规划中的整点问题求解方法(3)

数，因而t也为整数，故最大整数t可能是37。又因为直线4x 3y 37与边界直线5x 3y 40和直线6x 5y 60的交点分别为(3,

255

)和(,9)，在此两交点间直线32

4x 3y 3上没有整点，因此目标直线不7

是4x 3y 37。须再向可行域内平移一个单位成为4x 3y 36。目标直线4x 3y 36边界直线5x 3y 40和直线6x 5y 60的

20

交点分别为(4,)及（0，12）；又因为从

3

目标直线4x 3y 36可得y x 12，可

43

知若x，y为整数，则x为3的倍数；在[0，4]中满足条件只有0与3，故得最优解（0，12）及（3，8）。

当目标函数（或提取公倍数后）系数不大时可以用调整最值法，一般步骤为：①平移直线寻找非整最优解；②调整最值，确定“目标直线”③由“目标直线”方程代入约束条件，并求变量范围：④ 确定“目标直线”上整数解。

但目标直线在向可行域内平移过程中，若需平移多次才能达到目的，将十分麻烦。 方法四：缩小可行域法： 作出一组平行直线：4x 3y t（t 参数）,经过A(

4x 3y

z

为50

2060

)的直线方程为77

2601

， ＝77

我们利用B附近的网格，可在可行域内

A(

2060

,)附近找到B（3，8）这几个整点。过77

B作直线：4x 3y 36，然后检验直线4x 3y 36与边界直线5x 3y 40和直线

6x 5y 60围成的阴影区域内有无整点，经检验无整点。故直线4x 3y 36上的整点B（3，8）、C（0，12）为最优整点解。(若阴影区域内的有整点可利用解法二确定最优解)

缩小可行域方法的思路是先将题目作为一般的线性规划最优解来求,通过解出的非整数最优解来排除部分可行域,从而达到缩小可行域的目的. 可以克服在前方法三中有可能要多次平移找解的缺陷，适用范围广泛。一般步骤为：①根据非整点最优解A点的坐标在其附近寻找最近的整点B；②过B作与目标直线平行的直线，与原边界围成的阴影区域即缩小了最优解所在可行域；③找出阴影区域内的所有整点再利用解法二确定最优解。

总之，以上四种基本方法各有各的特点，因此有时要根据具体情况选择合适的方法。

3