《线性规划中的整点问题求解方法》由会员分享，可在线阅读，更多相关《线性规划中的整点问题求解方法（5页珍藏版）》请在金锄头文库上搜索。
1、示，今需要 A、 B、 C 三种规152 x + y 15x + 2 y 18x + 3y 27，作出可行x 0y 0域（如图所示），目标函数为z = x + y，作张钢板 y 张，则A（寫）2x+y=15x+2y=18x+y=4x+y=11x+y=12+3y=27线性规划中的整点问题求解方法宜昌市一中 祝海燕线性规划是运筹学的一个重要分支，在实际生活中有着广泛的应用。新教材中增加了 线性规划的内容，充分体现了数学的实际应用，发展了学生的数学应用意识。由于实际问 题中线性规划问题的最优解多为整数解，也是学生学习线性规划的难点，因而求线性规划 的整数最优解的方法就显得尤为重要了。但教材中对此类问
2、题却一带而过，对于具体的验 算过程并没有作必要的描述，以致学生在解题过程中对于具体的验算过程掌握还不够清 晰。以下为教材（人教版必修第二册上，2006 年第 2 版）第 69 页的例 4：钢板类型一一一一规格类型A规格B规格C规格第一种钢板211第二种钢板123要将两种大小不同的的 钢板截成A、B、C三种规格, 每张钢板可同时截得三种规 格的小 钢板的块数如表所 I 格的成品分别为15, 18, 27块，问各截这 两种钢板多少张可得所需三种规格成品， 且使所用钢板张数最少。解：设需要截第一种钢板x张，第二出在一组平行直线x + y = /中（t为参数）经过可行域内的点且和原点距离最近的直线，此
3、直线经过直线x + 3 y二27和直线2 x + y二15的交点川驚），直线方程为x + y = 557 = 11|，由于18和晋都不是整数，而最优解（x,y）中，x，y必须都是整数，所以可行域内点4呼罟） 不是最优解。经过可行域内的整点（横坐标和纵坐标都是整数的点）且与原点距离最近的直线是x + y = 12且经过的整点是B（3，9）和C（4，8），它们都是最优解。答：要截得所需三种规格的钢板，且使所截两种钢板的张数最少的方法有两种，第一 种截法是截第一种钢板3张、第二种钢板9张；第二种截法是截第一种钢板4张、第二种 钢板 8 张。两种方法都最少要截两种钢板共12 张。线性规划问题中的整点最
4、优解是教学中的一个难点，教材中利用图解法比较直观有效 地突破了这一难点，但其中有两个问题需要弄清楚：直线x + y = 12是怎样确定的？整点B （3， 9）和 C（4， 8）又是怎样确定的？在求最优解时，我们是将平行直线l: x + y二t向可行域内平移，在向右上方平移时，t的值是增加的而经过A（18,39）点的直线为x + y = 57 = 115，当t值增加的过程中其最小值是12,所以与原点距离最近的直线可能是x + y二12。若在可行域内直线x + y二12上有整点 则均是最优解。而直线x + y = 12与边界直线2x + y = 15及x + 3y = 27的交点坐标为（3，9）、
5、 （4.5, 7.5）,因此直线x + y = 12在可行域内的整点只有B（3, 9）和C（4, 8），即为所求 问题的最优解。如果问题更复杂一点该怎么办？下面以课本第71 页习题7.4第4题为例介绍最优整 数解问题的求解方法。某人有楼房一幢，室内面积共1 80 m2 ，拟分隔成两类房间作为旅游客房，大房间每间 面积为18 m2，可住游客5名，每名游客每天住宿费为40元，小房间每间面积为15 m2， 可住游客3名，每名游客每天住宿费为50元，装修大房间每间需要1000元，装修小房间每间需要600元，如果他们只能筹8000元用于装修，且游客能住满客房，它应隔出大房间和小房间各多少间，能获最大利益
6、？方法一：网格法： 设应隔出大房间 x 间和小房间 y18x +15 y 勺80茴/、 mJ 1000x +)00 y S300间(x, y g N丿，则 06x + 5 y 60 即：5x + 3y 0y0y0标函数为z - 5X 40x + 3X50y，作出可行域如图：根据目标函数z - 200+ 1 5y0作出一组平行线 2 0 0+ 1同。当此线经过直线18x + 1 - 18和直线10OG + 60妇800的交点畤严此直线方程为200x +150y =130007由于（20,60）不是整数，所以经过整77点（3， 8）时，才是最优解，同时直线上的整点（0,12）也是最优解，即应隔大房
7、间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 x 40x + 3 x 50y得整点（3, 8）和（0, 12 ）是最优解。当可行域较小、边界附近的整点较少时可以用整
8、点验证法；先找出可行域内非整最优 解一侧边界附近所有的整点，再将每个整点代入目标函数确定最优解。当可行域较大、边 界附近的整点较多时这种方法运算量较大。方法三:调整最值法：目标函数为： z=200x+150y =50（4x+3y） 作出在一组平行直线：4x+3y=t （t=50为参数）5经过A孚）的直线方程为4x+3y=号=3771，目标直线4x + 3y = t在向可行域内平移的过程中，t的值是减少的，在减少的过程中因x，y都是整数，因而t也为整数，故最大整数t可能是 37。又因为直线4x + 3y = 37与边界直线 5x + 3y - 40和直线6x + 5y - 60的交点分别 为（3
9、,25）和（5,9），在此两交点间直线324 x + 3= 3上没有整点，因此目标直线不 是4x + 3y - 37。须再向可行域内平移一个 单位成为4x + 3y - 36。目标直线4x + 3y - 36 边界直线5x + 3y - 40和直线6x + 5y - 60的 交点分别为（4,号）及（0，12）;又因为从 目标直线4x + 3y = 36可得y = 3 x +15，可 知若x，y为整数，则x为3的倍数；在0, 4中满足条件只有0与3,故得最优解（0, 12 ）及（ 3 ， 8 ）。当目标函数（或提取公倍数后）系数不大时可以用调整最值法，一般步骤为：平移 直线寻找非整最优解；调整最
10、值，确定“目标直线”由“目标直线”方程代入约束条 件，并求变量范围：确定“目标直线”上整数解。但目标直线在向可行域内平移过程中，若需平移多次才能达到目的，将十分麻烦。方法四：缩小可行域法：作出一组平行直线：4x + 3y = t（ t亠为 50参数）,经过4（乙0的直线方程为35 6 037 = h=我们利用 B 附近的网格，可在可行域内77A（50,60）附近找到B （3, 8）这几个整点。过77B作直线：4x + 3y = 36，然后检验直线4x + 3y = 36与边界直线5x + 3y = 40和直线6x + 5y = 60围成的阴影区域内有无整点，经检验无整点。故直线4x + 3y = 36上的整点B （3，8）、C （0，15）为最优整点解。（若阴影区 域内的有整点可利用解法二确定最优解）缩小可行域方法的思路是先将题目作为一般的线性规划最优解来求,通过解出的非整 数最优解来排除部分可行域,从而达到缩小可行域的目的. 可以克服在前方法三中有可能 要多次平移找解的缺陷，适用范围广泛。一般步骤为：根据非整点最优解A点的坐标在 其附近寻找最近的整点B过B作与目标直线平行的直线，与原边界围成的阴影区域即 缩小了最优解所在可行域；找出阴影区域内的所有整点再利用解法二确定最优解。总之，以上四种基本方法各有各的特点，因此有时要根据具体情况选择合适的方法。
