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

1、第六章整数规划（在图上用“X”用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域 标出）。1、 max z=3 xi+2x2.2X1+3X2W 122X1+X2W 9Xi、X2> 0解：2、min f=10 X1+9X2.5 X1+3x2> 45X1> 8X2 < 10X1、X2 > 0X XwxXXX *求解下列整数规划问题1、 min f=4 x1+3x2+2x3.2 Xi-5 X2+3X3W 44X1+X2+3X33X2+X3> 1X1、X2、X3=0 或 1解：最优解( 0，0， 1 )，最优值： 22、min f=2 X1+5X2+3X3+

2、4X3-4 X1+X2+X3+X4 > 2-2 Xi+4X2+2X2+4X2> 4X1+X2-X2+X23X1、X2、X3、X3=0 或 1解： 此模型没有可行解。3、maX Z=2 X1+3X2+5X3+6X4.5 Xi+3X2+3X3+X4< 302X1+5X2-X2+3X2W 20-Xi+3X2+5X2+3X2< 403Xi-X2+3X2+5X2< 25XI、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

3、X 12 +10 X 13+4 X 14+2 X 15+175 X 16+300 X 17+375 X 18 +500 X 19约束条件Xi + X 2+X3< 30X4+ X 5+ X 6-10 X 16 < 0X7+ X 8+ X 9-20 x 仃 < 0X10+ X 11+ X 12-30 X i8< 0X13+ X 14+ X 15-40 X 19< 0X1 + X 4+ X 7+X10+ X 13= 30X2 + X5+ X 8+X11+ X 14= 20X3 + X 6+ X 9+X12+ X 15= 20Xi为非负数(i=1,2.8 )Xi为非负整数

4、(i=9,10.15 )Xi 为为 0 1 变量(i=16,17 .19 )解：最优解( 30， 0，0，0，0，0，0，0，0，0，0，0，0，20，20，0，0，0，1)，最优值： 860一餐饮企业准备在全市范围内扩展业务， 将从已拟定的 1 4个点中确定 8个点建立分店， 由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的 1 4个店的费 用情况如下表：店名BB2B3B4&B6BB8B9B10B11B2B13B14费用(万元)公司办公会决定选择原则如下：(1) B5、B3和B7只能选择一个。(2 )选择了 B或B14就不能选B6o(3) B、Be、B、B12,最

5、多只能选两个。(4) Bs、B7、Bo、B8,最少要选两个。问应选择哪几个点，使总的建店费用为最低解：数学模型：min f = x 计 x 2+ x 3+ x 4+ x s+ x 6+ x 7+ x 8+ x 9+3 x 10+ x 11+ x 12+ x 13+ x 14X 1+X2+X3+X4+X5+Xe+X7+X8+X9+X10+X11+X12+X13+X14=8x 3+ x 5-2 x 7=2X 1+ X 6=1X6+ X 14 = 1X1+X2+X6+X12W 2X5+X7+X8+X102Xi >0 且 Xi 为 0 1 变量，i = 1, 2, 3,，14o最优解：(1, 1

6、, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1 )最优值：。即: B1, B2, B3, B4,B5,B9,B13,B14选中，建店的最低费用万元。有四个工人(甲、乙、丙、丁)，要分别指派他们完成四项不同的工作( A B、C、D), 请按以下要求求解指派问题。1、每人做各项工作所消耗的时间如下表所示，问应如何分配工作，才能使总的消耗时间为最少每人完成各项工作的所需时间小时是工作工作A工作B工作C工作D否工人甲1816-19乙-201620丙19181721丁121520-2、每人做各项工作所创的利润如下表所示，问应如何指派工作，才能使总的创利为最 多所工作创利 工人&

7、#39;、-益、工作A工作B工作C工作D甲14579乙7568丙3435丁7688解：1、消耗时间为最少问题线性规划数学模型：min f = 18xi+16x2+19x3+20x4+16x5+20x6+19x7+18x8+17x9+21 xio+12xii+15xi2+20xi3X1+X2+X3 =iX4+X5+X6=iX7+X8+X9+Xio=iXii + Xi2+Xi3=iXi+X7+Xii =iX2+X4+X8 +Xi2 =iX5+X9+Xi3 =iX3+X6+Xio =iXi> 0 且 Xi 为 0 i 变量，i = i, 2, 3,，i3。最优解：(0, i, 0, 0, i,

8、 0, 0, 0, 0, i, i , 0 , 0,),最优值：65。即:给甲分配工作 B,给乙分配工作 C,给丙分配工作 D,给丁分配工作 A,所用最少的 时间为65小时。2、总的创利为最多问题线性规划数学模型：max Z = 4i+52+73+94+75+5x6+6x7+8x8+3x9+4xi°+3xii+5xi2+7xi3+6xi4+8xi5+8xi6X i+X2+X3 +X4 =iX5+X6+X7+X8=iX9+Xi0+Xii+Xi2=iXi3+Xi4+Xi5+Xi6=iXi+X5+X9 +Xi3 =iX2+X6+Xi0+Xi4=iX3+X7+Xii+Xi5=iX4+X8+X

9、i2+Xi6=iXi> 0 且 Xi 为 0 i 变量，i = i, 2 , 3,i6最优解：(0 , 0 , 0 , i, i , 0 , 0 , 0 , 0 , i , 0 , 0 , 0 , 0,i,0 ),最优值：28。即:给甲分配工作 D,给乙分配工作 A给丙分配工作 B,给丁分配工作 C,所创最多的利润为28元。某企业在Ai地已有一个工厂，其产品的生产能力为 3万箱，为了扩大生产，打算在A2 , A, A, A地中再选择几个地方建厂。已知在A地建厂的固定成本为万元，在A地建厂的固定成本为30万元，在 A地建厂的固定成本为万元，在 A地建厂的固定成本为 50万元，另 外，五个产

10、地建成后的产量、销地的销量以及产地到销地的单位运价（万元/万箱）如下表所示。运销地输、'、价 产地、'、格BB2B3固定成本（万元）产量（万箱）A84303A5231A434302A9753A1042504销量（箱）322(1) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运 输费用之和最小；(2) 如果由于政策要求必须在A?，A地建一个厂，应在哪几个地方建厂解(1)整数规划数学模型：minz =8 xi +4 x ?+3 x 3+5 x 4+2 X5+ 3 x 6+ 4 X7+ 3 x 8+4 x 9+9 x 40+7 x 11+5x 12 +10 x

11、 13+4 x 14+2 x 15+ x 16+30x仃+ x 18 +50 x 19.X1 + x 2+X3W 3X4+ x 5+ x 6- x 16< 0X7+ x 8+ x 9-2 X17W 0X10+ x 11+ x 12-3 X18< 0X13+ X 14+ X 15-4 X19< 0X1 + X 4+ X 7+X10+ X 13= 3X2 + X5+ X 8+X11+ X 14= 2X3 + X 6+ X 9+X12+ X 15= 2Xi为非负整数(i=1,2.15)Xi 为 0 1 变量(i=16,17 .19)最优解：(3, 0, 0, 0, 0, 0, 0,

12、 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 =8 X1 +4 x 2+3 x 3+5 x 4+2 x 5 + 3 x 6+ 4 x 7+ 3 x 8+4 x 9+9 x 4o+7 x 11+5x 12 +10 x 13+4 x 14+2 x 15+ x 16+30x 17+ x 18 +50 x 19.X1 + x 2+X3W 3X4+ X 5+ X 6- X 16<

13、; 0X7+ x 8+ x 9-2 x 仃w 0X10+ x 11+ x 12-3 X18< 0X13+ X 14+ X 15-4 X19< 0X1 + X 4+ X 7+X10+ X 13= 3X2 + X5+ X 8+X11+ X 14= 2X3 + X 6+ X 9+X12+ X 15= 2 X16+ X 17=1Xi为非负整数(i=1,2.15) Xi 为 0 1 变量(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地

14、2万箱A2地到B2地1万箱A4地到B1地3万箱A4地到B1地3万箱 选中A, A两地。某航空公司经营兰州、北京、广州三个城市之间的航线，其中兰州一北京飞行时间为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:

15、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小时后才能起飞

16、。 这是一个指派问题，(1)城市兰州效益表：到达110112011201210121013起飞202110222021102310234413061691211004843611961441215364412561961699536361289256813662552948411111到达11111指派结果:起 到达飞"t10112011201210121013起飞2021-1-11022-1120211-11023-1-11023-1-1到达11111用的最少时间为527 a。(2)城市北京效益表：311102130121022301310233014起飞1011441529625

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

18、302320223024起飞301148443636811001201132457616164964120123245764425361301232457644253613013196324484484625413014641442562563614001到达111111指派结果:到达?己；302130222021302320223024起飞3011-1-12011-1-12012-1-13012-1-13013-1130141-1到达111111用的最少时间为117 a 。某地区有两个镇，它们每周分别产生 700吨和1200吨固体废物。现拟用三种方式（焚 烧、填海、掩埋）分别在三个场地对这些

19、废物进行处理。两城镇至各处理场所的运输费用、 应处理量、各处理场的处理能力及每个场所的处理废物的固定成本和可变成本如下表：焚烧填海掩埋应处理量（吨）城镇1运费（兀/吨）515700城镇251200固定成本（元/周）3850011501920变动成本（元/周）12166处理能力（吨/周）10005001300试求使两城镇处理固体废物总的费用最小的方案。解:混合整数规划问题数学模型：min f =+21X2+21X3+17x4+3850yi+1150y2+1920y3Xi+X2+X3=700X4+X5+X6=1200Xi+X4-1000 yi< 0X2+X5-500 y2< 0X3+X

20、6-1300 y3< 0Xi(i=i,2.6) yi、y2、y3=0 i结果：焚烧填海掩埋应处理量（吨）城镇i运费（元/吨）i000600700城镇20500700i200固定成本（元/周）3850ii50i920iii变动成本（元/周）i2i66处理能力（吨/周）i000500i300即两城镇处理固体废物的方案城镇i焚烧i00吨，掩埋600吨 城镇2填海500吨，掩埋700吨 总的最小费用：46i70元。某建设公司有四个正在建设的项目，按目前所配给的人力、设备和材料，这四个项目将分别可以在i5、20、i8和25周内完成，管理部门希望提前完工，决定追加35000元资金分配给这四个项目，并

21、规定追加资金只能以5000元为单位进行分配。对于各个项目，资金追加后的工期变化情况如下表：追加资金（千元）项目完工时间项目i项目2项目3项目40i520i8255i2i6i52ii0i0i3i2i8i58iii0i620799i425688i230577ii35476i0试求能使总的完工时间最短的资金分配方案。解：本问题的0-i整数规划数学型:minf = i5 Xi +20X2+i8X3+25X4+i2X5+i6X6+i5X7+2iX8+i0X9+i3Xi0+i2Xii+i8xi2+8xi3+iixi4+i0xi5+i6xi6+7xi7+9xi8+9xi9+i4X20+6x2i + 8X22+8X23+i2X24+5X25+7X26+7X27+ii X28+4X29+7X30 + 6X3i + i0X32X1+X5+X9+X13+X