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

值是增加的，而经过A(,

1839572

)点的直线为x y 11，当t值增加的过程中，其最小值5555

是12，所以与原点距离最近的直线可能是x y 12。若在可行域内直线x y 12上有整点

则均是最优解。而直线x y 12与边界直线2x y 15及x 3y 27的交点坐标为（3，9）、（4.5，7.5），因此直线x y 12在可行域内的整点只有B（3，9）和C（4，8），即为所求问题的最优解。

如果问题更复杂一点该怎么办？下面以课本第71页习题7.4第4题为例介绍最优整数解问题的求解方法。

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

方法一：网格法： 设应隔出大房间x间和小房间y180 18x 15y

1000x 600y8000

间(x,y N)，则

x 0 y 0

6x 5y 60

5x 3y 40 即： ，目

x 0 y 0

标函数为z 5 40x 3 50y，作出可行域如图：

根据目标函数z 200，作出一组平行线x 15y0

。当此线经过直线18x 15和直线20x0 15y 0ty 180

1000x 600y

的交点A(8000

2060

,)，此直线方程为77

130002060

，由于(,)不是整数，所以经过整200x 150y 777

点（3，8）时，才是最优解，同时直线上的整点(0,12)也是最优解，即应隔大房间3间，

小房间8间，或者隔大房间0间，小房间12间，所获利益最大。如果考虑到不同客人的需要，应隔大房间3间，小房间8间。

对图形的精度要求不高的可以用网格法，实际应用中常利用坐标纸作图；先作出可行域内的网格，再平移目标直线确定最优解。

方法二：整点验证法：找出可行域内靠近非整点最优解一侧边界附近所有的整点:（0，12）、（1，10）、（2，9）、（3，8）、（4，6）、（5，5）、（6，3）、（7，1）、（8，0），分别代入目标函数为z 5 40x 3 50y得整点（3，8）和（0，12）是最优解。

当可行域较小、边界附近的整点较少时可以用整点验证法；先找出可行域内非整最优解一侧边界附近所有的整点，再将每个整点代入目标函数确定最优解。当可行域较大、边界附近的整点较多时这种方法运算量较大。

方法三:调整最值法：目标函数为：z 200x 150y 50(4x 3y) 作出在一组平行直线：

4x 3y t（t

z20602601为参数）,经过A(,)的直线方程为4x 3y ＝，目标直线507777

4x 3y t在向可行域内平移的过程中，t的值是减少的，在减少的过程中因x，y都是整

2