《第六章运筹学整数规划案例》由会员分享，可在线阅读，更多相关《第六章运筹学整数规划案例（10页珍藏版）》请在金锄头文库上搜索。
1、第六章整数规划6.1 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域（在图上用x标出）。1、 max z=3 x1+2x2S.T.2xi+3x2 122xi+x2 0解：2、 min f=10 x1+9x2S.T.5x+3x245x18x2 W 10x1 x2 06.2 求解下列整数规划问题1、 min f=4 xi+3x2+2x3S.T.2xi-5x2+3x3 1 xi x2 x3=0 或 1 解：最优解(0, 0, 1),最优值：22、min f=2 x什5x2+3x3+4x3S.T.-4 x1+x2+x3+x4 2-2 x1+4x2+2x2+4x2 4 x1 + x2-x2+
2、x2 3 x1 x2 x3 x3=0 或 1 解：此模型没有可行解。3、max Z=2 x+3x2+5x3+6x4S.T.5x1+3x2+3x3+x4 302x1+5x2-x2+ 3x2& 20 -x1+3x2+5x2+3x2W 40 3x1-x2+3x2+5x2W 25 x1 x2 x3 x3=正整数 解：最优解(0, 3, 4, 3),最优值：474、 min z =8x1 +4 x2+3 x3+5 x4+2 x5+ 3 x6+ 4 x7+3 xs+4 x9+9 x10+7 xn+5 x12 +10 xi3+4 xi4+2 xi5+175 xi6+300 xi7+375 xi8 +500
3、x19约束条件x1 + x2+x3 30x4+ x5+ x6-10 x16 0 x7+ x8 + x9-20 x17 0 x10+ x11+ x12-30 x18 0 x13+ x14+ x15-40 x19 2Xi0 且 Xi 为 01 变量，i=1, 2, 3,，14。最优解：(1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1)最优值：15.4。即：Bi, B2, B3, B4,B5,B9,B13,B14选中，建店的最低费用15.4万元。6.4有四个工人(甲、乙、丙、丁)，要分别指派他们完成四项不同的工作(A、B、C、D),请按以下要求求解指派问题。1、每人
4、做各项工作所消耗的时间如下表所示，问应如何分配工作，才能使总的消耗时 间为最少？每人完成各项工作的所需时间小时是工作工人工作A工作B工作C工作D甲1816-19乙-201620丙 一19181721丁121520-2、每人做各项工作所创的利润如下表所示，问应如何指派工作，才能使总的创利为最 多？所工作创工人工作A工作B工作C工作D甲14579乙7568丙3435丁7688解：1、消耗时间为最少问题 线性规划数学模型：min f= 18xi+16x2+19x3+20x4+16x5+20x6+19x7+18x8+17x9+21xi0+12xii+15xi2+20xi3S.T.xi+x2+x3 =i
5、x4+x5+x6=ix7+x8+x9+xi0=ixii+xi2+xi3=ixi + x7+xii =ix2+x4+x8 + xi2=ix5+x9+xi3 =ix3+x6+xi0 =ixi0 且 xi 为 0i 变量，i=i, 2, 3,，i3。最优解：（0, i, 0, 0, i, 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+4xi0+3xii+5xi2+
6、7xi3+6xi4+8xi5+8xi6S.T.xi + x2+x3+x4=ix5+x6+x7+x8=ix9+xi0 + xii + xi2=1xi3+xi4+xi5+xi6 = 1xi + x5+x9 + xi3=1x2+x6+xi0+xi4=1x3+x7+xii+xi5=1x4+x8+xi2+xi6=1xi0 且 xi 为 01 变量，i=1, 2, 3,，16最优解：（0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0,1,0 ）,最优值：28。即：给甲分配工作 D,给乙分配工作 A给丙分配工作 B,给丁分配工作 C,所创最多的 禾I润为28元。6.5某企业在
7、Ai地已有一个工厂，其产品的生产能力为3万箱，为了扩大生产，打算在A2, A3, A4, A5地中再选择几个地方建厂。已知在A2地建厂的固定成本为17.5万元，在A3地建厂的固定成本为 30万元，在A4地建厂的固定成本为 37.5万元，在A5地建厂的 固定成本为50万元，另外，五个产地建成后的产量、销地的销量以及产地到销地的单位运 价（万元/万箱）如下表所示。运销地,输产地BiB2B3固定成本 （万元）产量（万箱）Ai84303A252317.51A3434302A497537.53A51042504销量（箱）322(1)问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运
8、输费用之和最小；(2)如果由于政策要求必须在A2, A3地建一个厂，应在哪几个地方建厂？解(1)整数规划数学模型：min z =8x1 +4 X2+3 X3+5 X4+2 X5+ 3 X6+ 4 X7+ 3 X8+4 X9+9 X40+7 xii+5 X12 +10 X13+4 X14+2 X15+17.5 X16+30X17+37.5 Xi8 +50 Xi9S.T.X1 + X2+X3 3X4+ X5+ X6- X16 0X7+ X8 + X9-2X17 0X10+ X11+ X12-3X18 0X13+ X14+ X15-4X19 0X1 + X4+ X7+X10+ X13 = 3X2 +
9、 X5+ X8+X11+ X14= 2X3 + X6+ X9+X12+ X15 = 2Xi为非负整数(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地至ij B1地3万箱，A5地到B2, B3地各2万箱，选中A5地。(2)我们只要在以上模型上加上一个约束条件：X16+ X17=1,就得到了问题(2)的数学模型：min z =8x1 +4 X2+3 X3+5 X4+2 X5 + 3 X6+ 4 X7+ 3 X8+4 X9+9 X4
10、0+7 xii +5 X12 +10 X13+4 X14+2 X15+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+ X13 = 3X2 + X5+ X8+X11+ X14= 2X3 + X6+ X9+X12+ X15 = 2X16+ X17=1xi为非负整数(i=1,2.15)xi 为 01 变量(i=16,17 .19)最优解：(0, 1, 2, 0, 1, 0,
11、 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小时；北京一广少M飞行时间为 3小叱广州一兰小M飞行时间为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广州
