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

《线性规划中的整点问题求解方法》由会员分享，可在线阅读，更多相关《线性规划中的整点问题求解方法（3页珍藏版）》请在装配图网上搜索。

1、线性规划中的整点问题求解方法线性规划是运筹学的一个重要分支，在实际生活中有着广泛的应用。新教材中增加了线性规划的内容，充分体现了数学的实际应用，发展了学生的数学应用意识。由于实际问题中线性规划问题的最优解多为整数解，也是学生学习线性规划的难点，因而求线性规划的整数最优解的方法就显得尤为重要了。但教材中对此类问题却一带而过，对于具体的验算过程并没有作必要的描述，以致学生在解题过程中对于具体的验算过程掌握还不够清晰。例1：钢板类型 规格类型A规格B规格C规格第一种钢板211第二种钢板123要将两种大小不同的的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如表所示，今需要A、B

2、、C三种规格的成品分别为15，18，27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。解：设需要截第一种钢板x张，第二张钢板y张，则，作出可行域（如图所示）,目标函数为，作出在一组平行直线中（为参数）经过可行域内的点且和原点距离最近的直线，此直线经过直线和直线的交点，直线方程为，由于都不是整数，而最优解中，必须都是整数，所以可行域内点 不是最优解。经过可行域内的整点（横坐标和纵坐标都是整数的点）且与原点距离最近的直线是且经过的整点是B（3，9）和C（4，8），它们都是最优解。答：要截得所需三种规格的钢板，且使所截两种钢板的张数最少的方法有两种，第一种截法是截第一种钢板3

3、张、第二种钢板9张；第二种截法是截第一种钢板4张、第二种钢板8张。两种方法都最少要截两种钢板共12张。线性规划问题中的整点最优解是教学中的一个难点，教材中利用图解法比较直观有效地突破了这一难点，但其中有两个问题需要弄清楚：直线是怎样确定的？整点B（3，9）和C（4，8）又是怎样确定的？在求最优解时，我们是将平行直线向可行域内平移，在向右上方平移时，的值是增加的，而经过点的直线为，当值增加的过程中，其最小值是12，所以与原点距离最近的直线可能是。若在可行域内直线上有整点则均是最优解。而直线与边界直线及的交点坐标为（3，9）、（4.5，7.5），因此直线在可行域内的整点只有B（3，9）和C（4，8

4、），即为所求问题的最优解。如果问题更复杂一点该怎么办？下面以课本第71页习题7.4第4题为例介绍最优整数解问题的求解方法。某人有楼房一幢，室内面积共180，拟分隔成两类房间作为旅游客房，大房间每间面积为18，可住游客5名，每名游客每天住宿费为40元，小房间每间面积为15，可住游客3名，每名游客每天住宿费为50元，装修大房间每间需要1000元，装修小房间每间需要600元，如果他们只能筹8000元用于装修，且游客能住满客房，它应隔出大房间和小房间各多少间，能获最大利益？1055oxy4x+3y=365x+3y=406x+5y=60方法一：网格法： 设应隔出大房间间和小房间间()，则即：，目标函数为

5、，作出可行域如图：根据目标函数，作出一组平行线。当此线经过直线和直线的交点，此直线方程为，由于不是整数，所以经过整点（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

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

7、别为及（0，12）；又因为从目标直线可得，可知若，为整数，则为3的倍数；在0，4中满足条件只有0与3，故得最优解（0，12）及（3，8）。当目标函数（或提取公倍数后）系数不大时可以用调整最值法，一般步骤为：平移直线寻找非整最优解；调整最值，确定“目标直线”由“目标直线”方程代入约束条件，并求变量范围： 确定“目标直线”上整数解。但目标直线在向可行域内平移过程中，若需平移多次才能达到目的，将十分麻烦。方法四：缩小可行域法： 作出一组平行直线：（为参数）,经过的直线方程为，我们利用B附近的网格，可在可行域内附近找到B（3，8）这几个整点。过B作直线：，然后检验直线与边界直线和直线围成的阴影区域内有无整点，经检验无整点。故直线上的整点B（3，8）、C（0，12）为最优整点解。(若阴影区域内的有整点可利用解法二确定最优解)缩小可行域方法的思路是先将题目作为一般的线性规划最优解来求,通过解出的非整数最优解来排除部分可行域,从而达到缩小可行域的目的. 可以克服在前方法三中有可能要多次平移找解的缺陷，适用范围广泛。一般步骤为：根据非整点最优解A点的坐标在其附近寻找最近的整点B；过B作与目标直线平行的直线，与原边界围成的阴影区域即缩小了最优解所在可行域；找出阴影区域内的所有整点再利用解法二确定最优解。总之，以上四种基本方法各有各的特点，因此有时要根据具体情况选择合适的方法。3