《对线性规划整点问题的探究(蒋政)》由会员分享,可在线阅读,更多相关《对线性规划整点问题的探究(蒋政)(3页珍藏版)》请在金锄头文库上搜索。
1、对线性规划整点问题的探究对线性规划整点问题的探究一、精确图解法求整数最优解 ( 课本 P88 习题 16 ) 某运输公司有 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+25
2、2y. 0x7 0y4 xy9 6 8 x10 6y360 x,yZ 0x7 0y4 xy9 4x5y30 x,yZ 如图可行域是 ABCD 围成的区域, 作直线 160x+252y=0,图形中两直线 160x+252y=0 和 4x+5y=30 接近平行,比较直线斜率 k=-,160 2524 5平移直线 160x+252y=0,由图可知在 A(7,)处取到最小值,但 A 不是整数解。2 5 在可行域内共有(3,4) , (4,3) , (4,4) , (5,2) , (5,3) , (6,2) , (6,3) , (7,1) , (7,2)整数 解,经检验只有(5,2)是最优解,此时 z=
3、1605+2522=1304 元。 这种方法适用于区域是封闭区域,且区域内的整数点可数,坐标网络画出来容易在图上识别哪些整点在 可行域内。 二、利用近似解估算整数最优解 (课本 P63 例 4) 要将两种不同的钢板截成 A、B、C 三种规格,每张钢板可同时截得三种规格的小钢板的块数如下表所示:今需要 A、B、C 三种规格的成品分别为 15、18、27 块, 问各截这两种钢板多少张可得所需的三种规格成品,且所 使用钢板张数最少。解:设需截取第一种钢板 x 张,第 二种钢板 y 张,则2xy15x2y18x3y27x,y0,x,yN 目标函数 z=x+y, 如图可行域是阴影部分,目标函数 在 A
4、点取到最优解。解方程组得 A(,)x3y27 2xy15 18 539 5但不是整数解,规格类型钢板类型A 规格B 规格C 规格第一种钢板211第二种钢板1232018161412108642-15-10-551015x+y=12x+3y=27x+2y=182x+y=15ABCDExOyx+y= 94x+5y=3 0160x+252y=0 ABCD此时,z=+=,18 539 557 5 则在可行域内取到整数解的 z=12. 即经过可行域内的整点,且与原点距离最近的直线是 x+y=12,则整点一定在 B、C 之间。解方程组,得 B(3,9) ;xy12 2xy15 解方程组,得 C(,) ;则
5、整点的横坐标 3x,xy12 x3y27 9 215 29 2所以满足条件的最优解是(3,9) , (4,8).本来近似解 z=,而=11.4 也不约等于 12,学生不理解为什么 z=12。这不是近似解约等于多少的问57 557 5题,而是由于不是可行域内的整数解,可行域内的整数解至少要大于。57 557 5 这种方法先由图解法观察出最优解在哪个点处取到,再由精确值估算出整数解,一定注意整数解的估算 不是四舍五入取整,而是在可行域内的整数解。三、利用解不定方程的原理求整数最优解例 2求下列区域内整数点的个数x0 y0 3x4y96. 解:如图区域是阴影部分的直角三角形,把它补为矩形。则矩形区域
6、内的整点有 3325=825 个。 而线段 AB 上的整点(含端点)是不定方程 3x+4y=96 的非负整数解。又 x=32-,则 y 一定被 3 整除,满足条件的 y 有 0,3,6,24 共 9 个,即线段 AB 上的整点有 9 个。4y 3则阴影部分区域内的整点有=417 个。825992四、利用穷举法求整数最优解 课本 P65 习题 7.4 第 4 题 某人有楼房一幢,室内面积共 180m2,拟分隔成两类房间作为旅游客房,大房间每间面积为 18m2,可住 游客 5 名,每名游客每天住宿费为 40 元;小房间每间面积为 15m2,可住游客 3 名,每名游客每天住宿费 为 50 元;装修大
7、房间每间需 1000 元,装修小房间每间需 600 元。如果他只能筹款 8000 元用于装修,且 游客能住满客房,他应隔出大房间和小房间各多少间,能获得最大收益? 解:设隔出大房间 x 间,小房间 y 间,收益为 z 元,则 x,y 满足18x15y180 1000x600y8000 x,y0,x,yZ z=200x+150y 如图可行域是阴影部分, 作直线 L:200x+150y=0,即 4x+3y=0, 将直线 L 平移到 A 点时与原点距离最大。 解方程组1412108642-2-551015xyO18x+15y=1801000x+600y=8000A 200x+150y=1800xOy
8、3224 AB得 A() ,但不是整数解。6x5y60 5x3y40 20 60,77此时 z=200=。2060150771300018577又 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+5y60,舍去; (4,7)不满足 5x+3y40,舍去; (7,3)不满足 5x+3y40,舍去。 所以 z 的最大值不可能是 1850。则 z 的最大值可能是 1800、1750、1700,直到在可行域内找到满足条 件的最优解。 若 z=1800,即 4x+3y=36,又 4x+3y=36 的所有整数解是(0,12) , (3,8) (6,4) , (9,0) ,经检验只有 (0,12) , (3,8)在可行域内,所以当 x=0,y=12 或 x=3,y=8 时,z 取到最大值 1800。 这种方法就是穷举法,首先对 z 的可能取到的整数解进行尝试,对所有可能的整数解验证它是否在可行 域内,才能准确不漏的找到所有的最优解。