对线性规划整点问题的探究(蒋政)

《对线性规划整点问题的探究(蒋政)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、对线性规划整点问题的探究一、精确图解法求整数最优解(课本P88习题16)x+y=94x+5y=30160x+252y=0ABCD某运输公司有7辆载重量为6t的A型卡车与4辆载重量为10t的B型卡车，有9名驾驶员。在建筑某段高速公路中，此公司承包了每天至少搬运360t沥青的任务。已知每辆卡车每天往返的次数为A型卡车8次，B型卡车6次，每辆卡车每天往返的成本费A型车160元，B型车252元。每天派出A型车和B型车各多少辆公司所花的成本费最低？解：设每天派出A型车x辆、B型车y辆，公司所花的成本为z元，则即z=160x+252y.如

2、图可行域是ABCD围成的区域，作直线160x+252y=0，图形中两直线160x+252y=0和4x+5y=30接近平行，比较直线斜率k=>-,平移直线160x+252y=0，由图可知在A（7，）处取到最小值，但A不是整数解。在可行域内共有（3，4），（4，3），（4，4），（5，2），（5，3），（6，2），（6，3），（7，1），（7，2）整数解，经检验只有（5，2）是最优解，此时z=160×5+252×2=1304元。这种方法适用于区域是封闭区域，且区域内的整数点可数，坐标网络画出来容易在图上识别哪些整点在可行域内。二、

3、利用近似解估算整数最优解(课本P63例4)要将两种不同的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：规格类型钢板类型A规格B规格C规格第一种钢板211第二种钢板123今需要A、B、C三种规格的成品分别为15、18、27块，问各截这两种钢板多少张可得所需的三种规格成品，且所使用钢板张数最少。xOy解：设需截取第一种钢板x张，第二种钢板y张，则目标函数z=x+y,如图可行域是阴影部分，目标函数在A点取到最优解。解方程组得A（，）但不是整数解，此时,z=+=,则在可行域内取到整数解的z=12.即经

4、过可行域内的整点，且与原点距离最近的直线是x+y=12，则整点一定在B、C之间。解方程组，得B（3，9）；解方程组，得C（，）；则整点的横坐标3≤x≤，所以满足条件的最优解是（3，9），（4，8）.本来近似解z=，而=11.4也不约等于12，学生不理解为什么z=12。这不是近似解约等于多少的问题，而是由于不是可行域内的整数解，可行域内的整数解至少要大于。这种方法先由图解法观察出最优解在哪个点处取到，再由精确值估算出整数解，一定注意整数解的估算不是四舍五入取整，而是在可行域内的整数解。xOy3224AB三、利用解不定方程的原理求

5、整数最优解例2．求下列区域内整数点的个数解：如图区域是阴影部分的直角三角形，把它补为矩形。则矩形区域内的整点有33×25=825个。而线段AB上的整点（含端点）是不定方程3x+4y=96的非负整数解。又x=32-,则y一定被3整除，满足条件的y有0，3，6…，24共9个，即线段AB上的整点有9个。则阴影部分区域内的整点有=417个。四、利用穷举法求整数最优解课本P65习题7.4第4题某人有楼房一幢，室内面积共180m2，拟分隔成两类房间作为旅游客房，大房间每间面积为18m2，可住游客5名，每名游客每天住宿费为40元；小房间每间

6、面积为15m2，可住游客3名，每名游客每天住宿费为50元；装修大房间每间需1000元，装修小房间每间需600元。如果他只能筹款8000元用于装修，且游客能住满客房，他应隔出大房间和小房间各多少间，能获得最大收益？xyO18x+15y=1801000x+600y=8000解：设隔出大房间x间，小房间y间，收益为z元，则x,y满足A200x+150y=1800z=200x+150y如图可行域是阴影部分，作直线L：200x+150y=0，即4x+3y=0,将直线L平移到A点时与原点距离最大。解方程组得A（），但不是整数解。此时z=2

7、00×=。又z=200x+150y=50（4x+3y），则z取到的最优解一定被50整除，则z的最大值是1850。即4x+3y=37，又4x+3y=37的所有整数解是（1，11），（4，7）（7，3），而（1，11）不满足6x+5y≤60，舍去；（4，7）不满足5x+3y≤40，舍去；（7，3）不满足5x+3y≤40，舍去。所以z的最大值不可能是1850。则z的最大值可能是1800、1750、1700…，直到在可行域内找到满足条件的最优解。若z=1800，即4x+3y=36，又4x+3y=36的所有整数解是（0，12），（3，8

8、）（6，4），（9，0），经检验只有（0，12），（3，8）在可行域内，所以当x=0,y=12或x=3,y=8时，z取到最大值1800。这种方法就是穷举法，首先对z的可能取到的整数解进行尝试，对所有可能的整数解验证它是否在可行域内，才能准确不漏的找到所有的最优解。