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

《对线性规划整点问题的探究(蒋政)》由会员分享，可在线阅读，更多相关《对线性规划整点问题的探究(蒋政)（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 的可能取到的整数解进行尝试，对所有可能的整数解验证它是否在可行 域内，才能准确不漏的找到所有的最优解。