第六章 运筹学 整数规划案例.doc

第六章 整数规划6.1 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“”标出)。1、 max z=3x1+2x2 s.t. 2x1+3x2122x1+x29x1、x20解：2、 min f=10x1+9x2 s.t. 5x1+3x245x1 8x2 10x1、x206.2 求解下列整数规划问题1、 min f=4x1+3x2+2x3 s.t. 2x1-5x2+3x344x1+x2+3x33 x2+x31x1、x2、x3=0或1 解：最优解（0，0，1），最优值：22、 min f=2x1+5x2+3x3+4x3 s.t. -4x1+x2+x3+x42-2x1+4x2+2x2+4x24 x1+x2-x2+x23x1、x2、x3、x3=0或1 解： 此模型没有可行解。3、max z=2x1+3x2+5x3+6x4 s.t. 5x1+3x2+3x3+x4302x1+5x2-x2+3x220-x1+3x2+5x2+3x2403x1-x2+3x2+5x225x1、x2、x3、x3=正整数 解：最优解（0，3，4，3），最优值：474、 min z =8x1 +4 x2+3 x3+5 x4+2 x53 x64 x73 x8+4 x9+9 x10+7 x11+ 5 x12 +10 x13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19 约束条件 x1 + x2+x330x4+ x5 x6-10 x160x7+ x8 x9-20 x170x10+ x11 x12-30 x180x13+ x14 x15-40 x190x1 + x4+ x7+x10+ x1330x2 + x5+ x8+x11+ x1420x3 + x6+ x9+x12+ x1520xi为非负数（i=1,2.8）xi为非负整数（i=9,10.15）xi为为01变量（i=16,17.19）解：最优解（30，0，0，0，0，0，0，0，0，0，0，0，0，20，20，0，0，0，1），最优值：8606.3 一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表： 店名b1b2b3b4b5b6b7b8b9b10b11b12b13b14费用(万元)1.21.51.72.13.31.22.82.51.93.02.42.42.11.6公司办公会决定选择原则如下：（1）b5、b3和b7只能选择一个。（2）选择了b1或b14就不能选b6。（3）b2、b6、b1、b12，最多只能选两个。（4）b5、b7、b10、b8，最少要选两个。问应选择哪几个点，使总的建店费用为最低？ 解：数学模型： min f1.2 x1+1.5 x2+1.7 x3+2.1 x4+3.3 x5+1.2 x6+2.8 x7+2.5 x8+1.9 x9+3 x10+2.4 x11+2.4 x12+2.1 x13+1.6 x14s.t. x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14=8 x3+ x5-2 x7=2 x1+ x6=1 x6+ x14=1 x1+x2+x6+x122 x5+x7+x8+x102 xi0且xi 为01变量，i1，2，3，14。最优解：（1，1，1，1，1，0，0，0，1，0，0，0，1，1）最优值：15.4。即：b1，b2，b3，b4,b5,b9,b13,b14选中，建店的最低费用15.4万元。6.4有四个工人（甲、乙、丙、丁），要分别指派他们完成四项不同的工作（a、b、c、d），请按以下要求求解指派问题。1、每人做各项工作所消耗的时间如下表所示，问应如何分配工作，才能使总的消耗时间为最少？ 每人完成各项工作的所需时间 小时是工作否分 工人 配工作a工作b工作c工作d甲1816 -19乙-201620丙19181721丁121520-2、每人做各项工作所创的利润如下表所示，问应如何指派工作，才能使总的创利为最多？所工作创利 工人 益工作a工作b工作c工作d甲4579乙7568丙3435丁7688解：1、消耗时间为最少问题线性规划数学模型：min f= 18x1+16x2+19x3+20x4+16x5+20x6+19x7+18x8+17x9+21x10+12x11+15x12+20x13s.t. x1+x2+x3 =1 x4+x5+x6=1x7+x8+x9+x10=1x11+x12+x13=1x1+x7+x11 =1x2+x4+x8 +x12 =1x5+x9+x13 =1x3+x6+x10 =1xi0且xi 为01变量，i1，2，3，13。最优解：（0，1，0，0，1，0，0，0，0，1，1，0，0，），最优值：65。即：给甲分配工作b，给乙分配工作c，给丙分配工作d，给丁分配工作a，所用最少的时间为65小时。2、总的创利为最多问题线性规划数学模型：max z = 41+52+73+94+75+5x6+6x7+8x8+3x9+4x10+3x11+5x12+7x13+6x14+8x15+8x16s.t. x1+x2+x3 +x4 =1 x5+x6+x7+x8=1x9+x10+x11+x12=1x13+x14+x15+x16=1x1+x5+x9 +x13 =1 x2+x6+x10+x14=1x3+x7+x11+x15=1x4+x8+x12+x16=1xi0且xi 为01变量，i1，2，3，16最优解：（0，0，0，1，1，0，0，0，0，1，0，0，0，0,1,0），最优值：28。即：给甲分配工作d，给乙分配工作a，给丙分配工作b，给丁分配工作c，所创最多的利润为28元。6.5 某企业在a1地已有一个工厂，其产品的生产能力为3万箱，为了扩大生产，打算在a2，a3，a4，a5地中再选择几个地方建厂。已知在a2地建厂的固定成本为17.5万元，在a3地建厂的固定成本为30万元，在a4地建厂的固定成本为37.5万元，在a5地建厂的固定成本为50万元，另外，五个产地建成后的产量、销地的销量以及产地到销地的单位运价（万元/万箱）如下表所示。运销地输价 产地 格b1b2b3固定成本（万元）产量（万箱）a184 303a252 317.51a343 4302a497 537.53a51042504销量（箱）322（1）问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小；（2）如果由于政策要求必须在a2，a3地建一个厂，应在哪几个地方建厂？解 （1）整数规划数学模型： min z =8x1 +4 x2+3 x3+5 x4+2 x53 x64 x73 x8+4 x9+9 x40+7 x11+ 5 x12 +10 x13+4 x14+2 x15+17.5 x16+30x17+37.5 x18 +50 x19 s.t. x1 + x2+x33x4+ x5 x6- x160x7+ x8 x9-2x170x10+ x11 x12-3x180x13+ x14 x15-4x190x1 + x4+ x7+x10+ x133x2 + x5+ x8+x11+ x142x3 + x6+ x9+x12+ x152xi为非负整数(i=1,2.15)xi为01变量(i=16,17.19) 最优解：（3，0，0，0，0，0，0，0，0，0，0，0，0，2，2，0，0，0，1）最优值：86。即：安排a1地到b1地3万箱，a5地到b2，b3地各2万箱，选中a5地。(2) 我们只要在以上模型上加上一个约束条件：x16+ x17=1，就得到了问题（2）的数学模型： min z =8x1 +4 x2+3 x3+5 x4+2 x53 x64 x73 x8+4 x9+9 x40+7 x11+ 5 x12 +10 x13+4 x14+2 x15+17.5 x16+30x17+37.5 x18 +50 x19 s.t. x1 + x2+x33x4+ x5 x6- x160x7+ x8 x9-2x170x10+ x11 x12-3x180x13+ x14 x15-4x190x1 + x4+ x7+x10+ x133x2 + x5+ x8+x11+ x142x3 + x6+ x9+x12+ x152x16+ x17=1xi为非负整数(i=1,2.15)xi为01变量(i=16,17.19)最优解：（0，1，2，0，1，0，0，0，0，3，0，0，0，0，0，1，0，1，0）最优值：94。即：安排a1地到b2地1万箱，b3地2万箱a2地到b2地1万箱a4地到b1地3万箱a4地到b1地3万箱选中a2，a4两地。6.6某航空公司经营兰州、北京、广州三个城市之间的航线，其中兰州北京飞行时间为2小时；北京广州飞行时间为3小时；广州兰州飞行时间为3小时；这些航线每天班机起飞与到达时间如下表：航班号起飞城市起飞时间到达城市到达时间1011兰州6:00北京8:001012兰州12:00北京14:001013兰州18:00北京20:002011兰州7:00广州10:002012兰州9:00广州12:001021北京7:00兰州9:001022北京10:00兰州12:001023北京17:00兰州19:002021广州14:00兰州17:002022广州17:00兰州20:003011北京5:00广州8:003012北京9:00广州12:003013北京13:00广州16:003014北京18:00广州22:003021广州6:00北京9:003022广州10:00北京13:003023广州14:00北京17:003024广州18:00北京21:00设飞机在机场停留期间的费用与停留时间的平方成正比，又每架飞机从降落到再起飞至少需要2小时的时间准备。确定一个使总的停留费用损失为最小的方案。解：现在有两本题需注意的两个问题 1、三个城市间的飞行，航班的安排分别是在三个城市中完成的； 2、到站的航班必须2小时后才能起飞。这是一个指派问题， （1）城市 兰州效益表：到达起飞10112011201210121013起飞2021 102220211023 1023 441 306169 121100 484361 196 144 121 536 441 256 196 169 9 536 361 289 256 81 36 625529 484 11111到达11111 指派结果：到达起飞10112011201210121013起飞2021 102220211023 1023 - -1 - - 1 - - - - 11- 1- - 11111到达11111 用的最少时间为527 a。（2）城市 北京效益表：到达起飞3011102130121022301310233014起飞1011 302130221012 3023 10133024441 400256 225144 8164529484 324 289 196121100 625 576 400 361 256 1691444 625 441 400 289196169 25 16 576576400289256 81 64 16165764414001008125815294844411111111 到达1111111指派结果：到达起飞3011102130121022301310233014起飞1011 302130221012 3023 10133024- - -1- -1- -11- -1- - -1-1-1111111 到达1111111用的最少时间为476 a。（3）城市 广州收益表：到达起飞302130222021302320223024起飞3011 201120123012 3013 3014484 324324 324196 644576 576 576 324144 36 16 4 4 484 25636 16 4 4 484256 81 49 2525625361 100 64 36364400111111到达111111指派结果：到达起飞302130222021302320223024起飞3011 201120123012 3013 3014- - -11- - - -1-1- - - - - 1- - - -1-111111到达111111用的最少时间为117 a。6.7 某地区有两个镇，它们每周分别产生700吨和1200吨固体废物。现拟用三种方式（焚烧、填海、掩埋）分别在三个场地对这些废物进行处理。两城镇至各处理场所的运输费用、应处理量、各处理场的处理能力及每个场所的处理废物的固定成本和可变成本如下表：焚烧填海掩埋应处理量（吨）城镇1运费（元/吨）7.5515700城镇257.512.51200固定成本（元/周）3850011501920变动成本（元/周）12166处理能力（吨/周）10005001300试求使两城镇处理固体废物总的费用最小的方案。解：混合整数规划问题数学模型： min f=19.5x1+21x2+21x3+17x4+23.5x5+18.5x6+3850y1+1150y2+1920y3 s.t. x1+x2+x3=700 x4+x5+x6=1200x1+x4-1000y10x2+x5-500y20x3+x6-1300y30xi (i=1,2.6) y1、y2、y3=01结果：焚烧填海掩埋应处理量（吨）城镇1运费（元/吨）1000600700城镇205007001200固定成本（元/周）385011501920111变动成本（元/周）12166处理能力（吨/周）10005001300即两城镇处理固体废物的方案城镇1焚烧100吨，掩埋600吨城镇2填海500吨，掩埋700吨总的最小费用：46170元。6.8 某建设公司有四个正在建设的项目，按目前所配给的人力、设备和材料，这四个项目将分别可以在15、20、18和25周内完成，管理部门希望提前完工，决定追加35000元资金分配给这四个项目，并规定追加资金只能以5000元为单位进行分配。对于各个项目，资金追加后的工期变化情况如下表：追加资金（千元）项目完工时间项目1项目2项目3项目401520182551216152110101312181581110162079914256881230577113547610 试求能使总的完工时间最短的资金分配方案。解：本问题的0-1整数规划数学型： min f = 15x1+20x2+18x3+25x4+12x5+16x6+15x7+21x8+10x9+13x10+12x11 +18x12+8x13+11x14+10x15+16x16+7x17+9x18+9x19+14x20+6x21 +8x22+8x23+12x24+5x25+7x26+7x27+11x28+4x29+7x30+6x31+10x32 s.t. x1+x5+x9+x13+x17+x21+x25+x29=1 x2+x6+x10+x14+x18+x22+x26+x30=1