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

《线性规划中的整点问题求解方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、线性规划中的整点问题求解方法宜昌市一中祝海燕线性规划是运筹学的一个重要分支，在实际生活中有着广泛的应用。新教材中增加了线性规划的内容，充分体现了数学的实际应用，发展了学生的数学应用意识。由于实际问题中线性规划问题的最优解多为整数解，也是学生学习线性规划的难点，因而求线性规划的整数最优解的方法就显得尤为重要了。但教材中对此类问题却一带而过，对于具体的验算过程并没有作必要的描述，以致学生在解题过程中对于具体的验算过程掌握还不够清晰。以下为教材（人教版必修第二册上，2006年第2版）第69页的例4：钢板类型规格

2、类型A规格B规格C规格第一种钢板211第二种钢板123要将两种大小不同的的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如表所示，今需要A、B、C三种规格的成品分别为15，18，27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。解：设需要截第一种钢板x张，第二张钢板y张，则，作出可行域（如图所示）,目标函数为，作出在一组平行直线中（为参数）经过可行域内的点且和原点距离最近的直线，此直线经过直线和直线的交点，直线方程为，由于都不是整数，而最优解中，，必须都是整数

3、，所以可行域内点不是最优解。经过可行域内的整点（横坐标和纵坐标都是整数的点）且与原点距离最近的直线是且经过的整点是B（3，9）和C（4，8），它们都是最优解。答：要截得所需三种规格的钢板，且使所截两种钢板的张数最少的方法有两种，第一种截法是截第一种钢板3张、第二种钢板9张；第二种截法是截第一种钢板4张、第二种钢板8张。两种方法都最少要截两种钢板共12张。线性规划问题中的整点最优解是教学中的一个难点，教材中利用图解法比较直观有效地突破了这一难点，但其中有两个问题需要弄清楚：直线是怎样确定的？整点B（3，9）

4、和C（4，8）又是怎样确定的？在求最优解时，我们是将平行直线向可行域内平移，在向右上方平移时，3的值是增加的，而经过点的直线为，当值增加的过程中，其最小值是12，所以与原点距离最近的直线可能是。若在可行域内直线上有整点则均是最优解。而直线与边界直线及的交点坐标为（3，9）、（4.5，7.5），因此直线在可行域内的整点只有B（3，9）和C（4，8），即为所求问题的最优解。如果问题更复杂一点该怎么办？下面以课本第71页习题7.4第4题为例介绍最优整数解问题的求解方法。某人有楼房一幢，室内面积共180，拟分隔成

5、两类房间作为旅游客房，大房间每间面积为18，可住游客5名，每名游客每天住宿费为40元，小房间每间面积为15，可住游客3名，每名游客每天住宿费为50元，装修大房间每间需要1000元，装修小房间每间需要600元，如果他们只能筹8000元用于装修，且游客能住满客房，它应隔出大房间和小房间各多少间，能获最大利益？1055oxy4x+3y=365x+3y=406x+5y=60方法一：网格法：设应隔出大房间间和小房间间()，则即：，目标函数为，作出可行域如图：根据目标函数，作出一组平行线。当此线经过直线和直线的交点，

6、此直线方程为，由于不是整数，所以经过整点（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、7，1）、（8，0），分别代入目标函数为得整点（3，8）和（0，12）是最优解。当可行域较小、边界附近的整点较少时可以用整点验证法；先找出可行域内非整最优解一侧边界附近所有的整点，再将每个整点代入目标函数确定最优解。当可行域较大、边界附近的整点较多时这种方法运算量较大。方法三:调整最值法：目标函数为：作出在一组平行直线：（为参数）,经过的直线方程为，目标直线在向可行域内平移的过程中，的值是减少的，在减少的过程中因，都是整3数，因而也为整数，故最大整数可能是37。又因为直线与边界直线和直线的交点分别为，在此

8、两交点间直线上没有整点，因此目标直线不是。须再向可行域内平移一个单位成为。目标直线边界直线和直线的交点分别为及（0，12）；又因为从目标直线可得，可知若，为整数，则为3的倍数；在[0，4]中满足条件只有0与3，故得最优解（0，12）及（3，8）。当目标函数（或提取公倍数后）系数不大时可以用调整最值法，一般步骤为：①平移直线寻找非整最优解；②调整最值，确定“目标直线”③由“目标直线”方程代入约束条件，并求变量范围：④确定“目标直