第六章运筹学整数规划案例教材

1、( 在图上用第六章 整数规划6.1 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域 ×”标出 ) 。1、 max z=3 x1+2x2S.T. 2x1+3x2 12 2x1+x29 x1、x20 解：2、 min f=10 x1+9x2S.T.5x1+3x2 45x1 8x2 10 x1、x206.2 求解下列整数规划问题1、 min f=4 x1+3x2+2x3S.T. 2x1-5x2+3x3 44x1+x2+3x3 3x2+x3 1x1、x2 、x3=0 或 1解：最优解( 0，0， 1)，最优值： 22、 min f=2 x1+5x2+3x3+4x3S.T. -4

2、x1+x2+x3+x4 2-2 x1+4x2+2x2+4x2 4 x1+x2-x2+x23 x1、x2、x3、x3=0 或 1 解： 此模型没有可行解。 3、 max Z=2 x1+3x2+5x3+6x4 S.T. 5x1+3x2+3x3+x4 302x1+5x2-x2+3x220- x1+3x2+5x2+3x2 403x1-x2+3x2+5x225 x1、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+

3、2 x15+175 x16+300 x17+375 x18 +500 x19约束条件x1 + x2+x3 30x4+ x5 x6-10 x16 0x7+ x8 x9-20 x17 0x10+ x11 x12-30 x18 0x13+ x14 x15-40 x19 0x1 + x4+ x7+x10+ x1330x2 + x5+ x8+x11+ x14 20x3 + x6+ x9+x12+ x1520 xi为非负数( 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，2

4、0，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，最少

5、要选两个。 问应选择哪几个点，使总的建店费用为最低？解：数学模型：min f 1.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=8x3+ x5-2 x7=2x1+ x6=1x6+ x14=1x1+x2+x6+x122x5+x7+x8+x102xi0 且 xi 为 01 变量， i1， 2， 3， 14。 最优解：（1，1，1，1，1，0，0，0

6、，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、每人做各项工作所创的利润如下表所示，问应如何指派工作，才能使总的创利为最 多？所创工人工作利益工

7、作 A工作 B工作 C工作 D甲4579乙7568丙3435丁7688解： 1、消耗时间为最少问题 线性规划数学模型：min f= 18x1+16x2+19x3+20x4+16x5+20x6+19x7+18x8+17x9+21x10+12x11+15x12+20x13 S.T.x1+x2+x3 =1x4+x5+x6=1 x7+x8+x9+x10=1 x11+x12+x13=1 x1+x7+x11 =1 x2+x4+x8 +x12 =1 x5+x9+x13 =1 x3+x6+x10 =1 xi0且xi 为 01变量， i1，2，3，13。最优解：（0， 1，0，0，1，0，0，0，0，1，1，0

8、，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+8x16 S.T.x1+x2+x3 +x4 =1x5+x6+x7+x8=1 x9+x10+x11+x12=1 x13+x14+x15+x16=1 x1+x5+x9 +x13 =1 x2+x6+x10+x14=1 x3+x7+x11+x15=1 x4+x8+x12+x16=1 xi

9、0 且 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 某企业在 A 1地已有一个工厂，其产品的生产能力为3 万箱，为了扩大生产，打算在 A 2， A 3， A 4，A 5地中再选择几个地方建厂。已知在A2地建厂的固定成本为 17.5 万元，在 A 3地建厂的固定成本为 30 万元，在 A4 地建厂的固定成本为 37.5 万元，在 A 5地建厂的 固定成本为 50 万元，另外，五个产

10、地建成后的产量、销地的销量以及产地到销地的单位运 价（万元 /万箱）如下表所示。运 销地 输价产地 格B1B2B3固定成本（万元）产量（万箱）A184303A252317.51A3434302A497537.53A51042504销量（箱）322（1）问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运 输费用之和最小；（ 2）如果由于政策要求必须在A2，A 3地建一个厂，应在哪几个地方建厂？解 ( 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

11、x14+2 x15+17.5 x16 +30 x17+37.5 x18 +50 x19 S.T.x1 + x2+x3 3x4+ x5 x6- x16 0x7+ x8 x9-2x17 0x10+ x11 x12-3x18 0x13+ x14 x15-4x19 0x1 + x4+ x7+x10+ x133x2 + x5+ x8+x11+ x14 我们只要在以上模型上加上一个约束条件：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 x1

12、5+17.5 x16+30x17+37.5 x18 +50 x19S.T.x1 + x2+x3 3x4+ x5 x6- x16 0x7+ x8 x9-2x17 0x10+ x11 x12-3x18 0x13+ x14 x15-4x19 0x1 + x4+ x7+x10+ x133x2 + x5+ x8+x11+ x14 2 x3 + x6+ x9+x12+ x152 x16+ x17=1 xi为非负整数 (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)x3 + x6+ x9+x12+

13、x152 xi为非负整数 (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地。最优值： 94。即：安排 A1地到 B2地 1万箱， B3地 2万箱A2地到 B2地 1万箱A4地到 B1地 3万箱A4地到 B1地 3万箱 选中 A2，A4 两地。6.6 某航空公司经营兰州、北京、广州三个城市之间的航线，其中兰州北京飞行时间为2 小时；北京广州飞行时间为3 小时；广州兰州飞行时间为 3

14、小时；这些航线每天班机起飞与到达时间如下表：航班号起飞城市起飞时间到达城市到达时间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:00

15、3022广州10:00北京13:003023广州14:00北京17:003024广州18:00北京21:00设飞机在机场停留期间的费用与停留时间的平方成正比， 又每架飞机从降落到再起飞至 少需要 2 小时的时间准备。确定一个使总的停留费用损失为最小的方案。解：现在有两本题需注意的两个问题1、三个城市间的飞行，航班的安排分别是在三个城市中完成的；2、到站的航班必须 2小时后才能起飞。这是一个指派问题，（ 1）城市 兰州效益表：到达飞10112011201210121013起飞2021102220211023102344130616912110048436119614412153644125619

16、61699536361289256813662552948411111到达11111指派结果：起 到达飞10112011201210121013起飞2021-1-11022-1120211-11023-1-11023-1-1到达11111用的最少时间为 527 a。2）城市 北京效益表：到达飞起3011102130121022301310233014起飞10114415296254258110013021400484576625166481130222563244004415761625110122252893614005761681130231441962562894005765291101

17、38112116919628944148413024641001441692564004411到达1111111指派结果：到达飞起3011102130121022301310233014起飞1011-1-13021-1-13022-111012-1-130231-11013-1-13024-1-1到达1111111用的最少时间为 476 a。（ 3）城市 广州收益表：起 到达飞起302130222021302320223024起飞30114844363681100120113245761616496412012324576442536130123245764425361301319632448

18、4484625413014641442562563614001到达111111指派结果：起 到达飞起302130222021302320223024起飞3011-1-12011-1-12012-1-13012-1-13013-1130141-1到达111111用的最少时间为 117 a。6.7 某地区有两个镇， 它们每周分别产生 700 吨和 1200 吨固体废物。 现拟用三种方式 （焚烧、填海、 掩埋） 分别在三个场地对这些废物进行处理。两城镇至各处理场所的运输费 用、应处理量、各处理场的处理能力及每个场所的处理废物的固定成本和可变成本如下表：焚烧填海掩埋应处理量（吨）城镇 1运费（元 /

19、吨）7.5515700城镇 257.512.51200固定成本（元 / 周）3850011501920变动成本（元 / 周）12166处理能力（吨 / 周）10005001300试求使两城镇处理固体废物总的费用最小的方案。解：混合整数规划问题数学模型：min f =19.5 x1+21x2+21x3+17x4+23.5x5+18.5x6+3850y1+1150y2+1920y3S.T.x1+x2+x3=700x4+x5+x6=1200x1+x4-1000 y1 0x2+x5-500 y20x3+x6-1300 y3 0xi (i=1,2 .6)y1、 y2、 y3=0 1结果：焚烧填海掩埋应处

20、理量（吨）城镇 1运费（元 / 吨）1000600700城镇 205007001200固定成本（元 / 周）385011501920111变动成本（元 / 周）12166处理能力（吨 / 周）10005001300即两城镇处理固体废物的方案城镇 1焚烧 100吨，掩埋 600 吨城镇 2填海 500吨，掩埋 700 吨 总的最小费用： 46170 元。6.8 某建设公司有四个正在建设的项目，按目前所配给的人力、设备和材料，这四个 项目将分别可以在 15、20、 18 和 25 周内完成，管理部门希望提前完工，决定追加 35000 元资金分配给这四个项目， 并规定追加资金只能以 5000 元为单

21、位进行分配。 对于各个项目， 资金追加后的工期变化情况如下表：追加资金（千元）项目完工时间项目 1项目 2项目 3项目 401520182551216152110101312181581110162079914256881230577113547610试求能使总的完工时间最短的资金分配方案。解：本问题的 0-1 整数规划数学型：min f = 15 x1+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+10x32S.T.x1+x5+x9+x13+x17+x21+x25+x29=1x2+x6+x10+x14+x18+x22+x26+x30=1x3+x7+x