第六章 整数规划.docx

第六章整数规划6.1用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域（在图上用“X”标出）。1、maxz=3x÷2x2S.T.2x+3x2122xi+X29x.M20解：X28-A62、mini=10xi+9x2S.T.5x+3m245Xi28X210x.M206.2求解下列整数规划问题1、minf=4x÷3x2÷2x3S.T.2x-5x2÷3x344xi+m+3x323x2+x3.1x1.x2.x3=0或1解：将模型代入求解模板求解0-1整数规划模板返回首页我总荥IW结果妁虫备件*孰暴漕然幽一，可高足所有的妁束及最忧约栗条村为束约束条件冬际的美系窠利通O恢复为网的(Q)I睚i【IBifl1|供存方案0).I硒()J即：最优解(0,0,1),最优值：22、minf=2x+5M+3x3+4x3S.T.-4+x2+x3+x4.2-2x+4x2+22÷4x224x+x2-x2+x23XLX2、X3、X3=0或1解：此模型没有可行解。3、maxZ=2x+3x2+5%3+4S.T.5x+3x2+3%3+X4302x+5X2-X2÷3X220-XI+3<v2+52+32403x-X2+3x2+5x225Xl.初、43、X3=正整数解：代入模板求解返回首页纯整数规划模板约束条件妁束约束条件I£_3_, 567 8 elonE且 H15J6171819204发组应252627282930E理空Sl即：最优解(0,3,4,3),最优值：474、minZ=8x+4刈+3X3÷5xa+2总+3抵+4为+3+4后+9Xlo+7XIl+5x2÷0x3÷4xi4÷2X15+175x6÷300x+375x+5009约束条件Xl+X2÷X330X4+X5÷X6-10x60X7+X8÷X9-20x7OXl+XiI÷2-30x80X13+X14+X15-40X190Xl+X+X7÷Xi0+XI3=30Xl+X5+Xg+Xll+X4=20Xy+x+X9+X12+X5=20为为非负数(i=l,28)H为非负整数(i=9,10.15)H为为01变量G=16,1719)解：代入模板求解正合整数规划模板33村严六si“'FJ直返回首页I即：最优解(30,0,0,0,0,0,0,0,0,0,0,0,0,20,20,0,0,0,1),最优值：8606.3一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表：店名BiB2B3B4B5B6B7B8B9BioBnBl2B13Bi4费用（万元）1.21.51.72.13.31.22.82.51.93.02.42.42.11.6公司办公会决定选择原则如下：（I）B2、B3和B7只能选择一个°（2）选择了Bl或Bm就不能选B6。（3）B2、B6、BrBi2,最多只能选两个。（4）B5、B7、Bio、B8,最少要选两个。问应选择哪几个点，使总的建店费用为最低？解：1、确定决策变量设01变量Xi=1,当Bj点被选用；0,当Bj点没被选用。这里i=l,2142、确定目标函数这样我们可建立如下的数学模型：minf=1.2j+1.5x2+l7xj÷2.1A4+3.3X5+L2a+2.8x÷2.5's÷l.9乃+3xo+2.4x+2.4XI2+2.1x3+l.6x43、确定约束条件x+x2+x3+x4+x5+46+x7+x8+x9+x)+T+412+x13+x14=8共选8个%2÷X3+X7=1或选Bs和Ba»或选择B?Xl+X6=l选择了Bl或Bm就不能选BbX6÷Xi4=1选择了B或BM就不能选BbX2+.t6+Xl+,22B2、B6、Bl、BI2、最多只能选两个X5+M+X8+Xo22B5、B、Bn）、B8、最少要选两个minf=1.2x+1.5也+1.7幻+2.1&+3.3x5÷1.2抵+2.8x+2.5xs+1.9刈+3XlO+2.4x+2.4x2+2.lx3+l.6x4S.T.X+X2+X3+X4+X5+fe+X7+X8+X9+X+X!l+X12+X3÷X14=8x2+x3+x7=l工+X6=16÷X4=1X2+X6+Xh+X22X5+X7+X8+X02X1,0KXi为01变量，/=1,2,3,14o代入模板求解I19 4|×1x2«3x4x5x)x7×9xlxll 1x12x14×151x16I 12I J5173 32 5192 4| 2 41 6 I0-1整数规划模板返回首页I1111111118bl11111I 31111:111t>45111I26I14-0*03k90100biOE0Gbll1204bl21304t)131404bl41120bl5160b!60t>17180¼bl8190t)19200一 L妁条件或，约束条件约束约束条件实际值美系客数吸最优解：(0,0,0,1,1,1,1,1,0,1,1,0,1,0)最优值：19.4。即：B4,B5,B6,B7,B8,B10,BlbB13选中,建店的最低费用19.4万元。6.4有四个工人（甲、乙、丙、丁），要分别指派他们完成四项不同的工作（A、B、C、D）,请按以下要求求解指派问题。1、每人做各项工作所消耗的时间如下表所示，问应如何分配工作，才能使总的消耗时间为最少？每人完成各项工作的所需时间小时是工作工作A工作B工作C工作D甲1816-19乙-201620丙19181721T121520-2、每人做各项工作所创的利润如下表所示，问应如何指派工作，才能使总的创利为最多？所工作创工作A工作B工作C工作D甲4579乙7568丙3435T7688解：1、消耗时间为最少问题（1）确定决策变量设0-1变量如下表，各变量表示是否分配给工作，0为不分配，1为分配。所工作需工人工作A工作B工作C工作D甲XiXi-X3乙-XaX5X6丙Xj即X9-VioT-VllX2.5-(2)确定目标函数本问题的目标是所用总的时间为最少，而总时间为：18x+16x2÷19-3+204÷16xs+2Ch+19力+18+17x9÷2Lvo÷12,i+15x2÷20xi3所以目标函数为：minJ=18x+l6x2+193+2x4+16x5+2(h+19幻+18+17x9+2lxo÷12xn+15x2+20x3(3)确定约束条件因为每人只能分配一项工作所以对于每人而言X+42+X3=1x4+5+x6=1X7+X8+X9+X1O=1Xll+X12+X13=l又每项工作只能分配给一个人人，所以对于每项工作X+X7÷X11=1X2+-V4+X8+X2=lx5+x9+x13=1x3+x6+x0=1为20且为为01变量，Z=1,2,3,，13。即得本问题的线性规划数学模型：minj=18x+16x2+19冷+2(1口+16x5+2x6+19&+18刖+17刈+2lxo+12x+15x2+2x3S.T.x+x2+x3X4+X5+X6=lX7+X8+X9+x0=l)÷X2+X13=x+x7+x=IM+X4+X8+X12=1x5+x9+x13=1力+北+处0=1Xix)且Xj为O-I变量，/=1,2,3,，13。代入求解模板得结果：0-1整改规划模板Jp】1Qla11。101UU01UmII1取日Im杼方*0.II帝勒3I拗片解掂到一解可观足用有的虻施及ttC伎直力”值Q)最优解：(0,1,0,0,1,0,0,0,0,1,1,0,0,),最优值：65O即：给甲分配工作B,给乙分配工作C,给丙分配工作D,给丁分配工作A,所用最少的时间为65小时。2、总的创利为最多问题(1)确定决策变量设0-1变量如下表，各变量表示是否分配给工作，0为不分配，I为分配。是工作工作A工作B工作C工作D甲XiX2X3.V4乙玲AXlX8丙X9由。孙X12T13XI4X5XlS(2)确定目标函数本问题的目标是所得总的创利为最多，而总创利为：4+52÷73+94÷75÷5X6÷6X7+8X8+3X9÷4xio+3xll+5X!2÷7X13÷6X14÷8xi5÷8xi6所以目标函数为：maxZ=4+52+73+94+75+5x6+6r7+8+3x9+4xo+3x1+52+713+6x14+8x5+8xi6(3)确定约束条件因为每人只能分配一项工作所以对于每人而言X+X2+X3+X4=lX5+X6+X7+X8=lX9+1O+Xll+Xl2=lXl3+X14+Xl5+Xl6=l又每项工作只能分配给一个人人，所以对于每项工作X+X5+X9÷-V3=lX2+6÷Xl+X14=lX3+7+Xl+X5i4+X8+X2+Xl6=lxl0Xi为01变量，i=l,2,3,»16即得本问题的线性规划数学模型：rnaxZ=4i+52+73+94+75+5+6A17+8x8+3x9+4xo+3x+5x2+7.r3+6x4+8x5+8l6S.T.X1+X2+X4=1X5+X6+X7+X8=lX9+l+Xl+X2=lX3+X14+X5+X6=lXl+X5+X9+X3=lX2+X6÷+X14=lX3+X7+Xl+X5=lX+X8+X2+X16=lx,20且为为01变量，=1,2,3»160-1静数规划模板约皴条由约力约金条行Holnna代人求解模板得结果：最优解：(0,0,0,1,1,0,0,0,0,1,0,0,0,0,1,0),最优值：28。即：给甲分配工作D,给乙分配工作A,给丙分配工作B,给丁分配工作C,所创最多的利润为28元。6.5某企业在Al地已有一个工厂，其产品的生产能力为3万箱，为了扩大生产，打算在A2,A3,A4,As地中再选择几个地方建厂。已知在Az地建厂的固定成本为17.5万元，在A3地建厂的固定成本为30万元，在A4地建厂的固定成本为37.5万元，在As地建厂的固定成本为50万元，另外，五个产地建成后的产量、销地的销量以及产地到销地的单位运价（万元/万箱）如下表所示。运销地输BiB2B3固定成本（万元）产量（万箱）Ai84303A252317.51A3434302A497537.53A51042504销量（箱）322（1）问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小：（2）如果由于政策要求必须在A2,A3地建一个厂，应在哪几个地方建厂？解、确定变量设即为从A运往B的运输量（单位：千箱），方为选址变量，如下表:变销地BB2B3固定成本产量（万箱）AiXlX2X33A2X4X5X6y1A3XlX8X9),22A4AlO刈X2y33A5A'?X4X5%4销量（千箱）302020其中芍为整数；选址变量有以下特征：b当Ai厂址被选中时；IO,当Aj厂址没被选中时。j=l,2,15,i=1.2.3.4二、确定目标函数则此问题的固定成本及总运输费最小的目标可写为minZ=8ai+4垃+3冷+5以+2xs÷3÷4x7÷3+4通+9xo+7x+5x2+10x3÷4X4+2x5÷7.5J+30>f2+37.5J3+50*其中后4项为固定投资额，前15项为运输费用。三、确定约束条件对Al厂来说其产量的限制的约束条件可写成x+x2+33（Al的产量）但是对A2,A3,A4,A5准备选址建设的新厂来说，只有当选为厂址建设，才会有生产量，所以它们的产量限制的约束条件写成X4÷X5÷X6lyi（A2的产量），X7÷X8÷X92j2（A3的产量），Xl+Xl+x23j3（A4的产量），X13÷14÷154j4（A5的产量），至于满足销量的约束条件可写为Xl+松+X7÷Xl+箝3=3（Bl的销量），X2+Xs+X8÷Jfll+Jf|4=2（B2的销量），X3+X6+X9+Xi2+X5=2（B3的销量），再加上此为非负整数及8为01变量的约束就得到了此问题的数学模型。目标函数minz=8x1÷4m+3刈+5x+2必+3抵+4和+3a+4期）+9心）+7+5x2+10x3+4X14+2x5÷17.56÷30x7÷37.5xs+50X19S.T.x+X2+X33X4+X5÷X6-X60X7+X8÷9-2X17Oo+XlI÷Xl2-3x80X3÷X4÷5-4x90Xl+X4+X7+Xi0+X13=3X2+Xi+X8+X11+X4=2X3+X6+X9+Xi2+X5=2为为非负整数（i=l,215）Xi为Of变量（i=16,l719）代入模板求解得结果：最优解：(3,O,O,0,0,0,0,0,0,0,0,0,0,2,2,0,0,0,1)最优值：86o即：安排Al地到Bl地3万箱，A5地到B2,B3地各2万箱，选中A5地。(2)我们只要在以上模型上加上一个约束条件：Xg+总7=1，就得到了问题(2)的数学模型：目标函数minz=8x÷4&+3不+54+2玲+3抵+4*7+3+4为+9X4o+7m+5Xi?÷10Xi3÷4xu÷2x5÷l7.5x6÷30xi7÷37.5Xis+50X19S.T.X1+x2+x33X4+X5+Afe-X16OX7÷X8÷X9-2x70XIo+x+x2-3x80Xl3÷X14÷X5-4X190X+x+X7÷Xl+X3=3Xl+X5+X8÷X1+X4=2工3+X6÷X9+X2+X15=2X+X17=l为为非负整数(i=l,2.15)为为01变量(i=16,1719)代入模板求解得结果：最优解：(0,1,2,0,1,0,0,0,0,3,0,0,0,0,0,1,0,1,0)最优值：94。即：安排AI地至JB2地1万箱，B3地2万箱A2地到B2地1万箱A4地到Bl地3万箱A4地到Bl地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广州21:003021广州6:00北京9:003022广州10:00北京13:003023广州14:00北京17:003024广州18:00北京21:00设飞机在机场停留期间的费用与停留时间的平方成正比，又每架飞机从降落到再起飞至少需要2小时的时间准备。确定一个使总的停留费用损失为最小的方案。解：现在有两注意的两个问题1、三个城市间的飞行，航班的安排分别是在三个城市中完成的；2、到站的航班必须2小时后才能起飞。下面先看三个城市航班情况：城市兰州停留时4到起航班号10112011201210121013起习时间6：007：OO9：0012：OO18：OO航班号到达时I京*10219：OO21222439102212：OO181921246202117：OO1314161925102319：OO1112141723202220：OOIO11131622城市北京xK起停留时I品、飞航班号3011102130121022301310233014起习时间579IO131718航班号到达时间101182123252591030219202224254893022131618202124451012141517192023343023171214161720242310132091113141721223024218101213162021城市广州起停留时俞飞到:航班号302130222021302320223024起习时间61014141718航班号到达时而30118222669IO2011IO1824447820121218222256301212182222563013161418222225230142191317172021再看三个城市的效益表:城市兰州<01120112012101210131021441a484a536a9a81a1022306a361a441a536a36a2021169a196a256a361a625a1023121a144a196a289a529a2022100a121a169a256a484a5J½<0112011201210121013起飞10214414845369811102230636144153636120211691962563616251102312114419628952912022IOO1211692564841到达11111代入指派模板求解得结果:AIBICID即:e<0112011201210121013起飞1021-1-11022-1120211-11023-1-12022-1-1到达11111用的最少时间为527a0城市北京沌1021301210223013102330141011441a529a625a4a25a81a100a3021400a484a576a625a16a64a81a3022256a324a400a441a576a16a25a1012225a289a361a400a576a16a81a3023144a196a256a289a400a576a529a101381a12la169a196a289a441a484a302464aIOOa144a169a256a400a441a102130121022301310233014起飞1011441529625425811001302140048457662516648113022256324400441576162511012225289361400576168113023144196256289400576529110138112116919628944148413024641001441692564004411到达1111111返回首页代入指派模板求伸解2-I*WHW%alif8!s!al½lllffllJd海102130121022301310233014起飞IOll-1-13021-1-13022-1I1012-I-I30231-I1013-1-I3024-1-1到达1111111用的最少时间为476a。城市广州302220213023202230243011484a4a36a36a81a100a2011324a576a16a16a49a64a2012324a576a4a4a25a36a3012324a576a4a4a25a36a3013196a324a484a484a625a4a301481a169a289a289a400a441a商Q2130222021302320223024起飞301148443636811001201132457616164964120123245764425361301232457644253613013196324484484625413014811692892894004411到达111111代入指派模板求解得结果:返回首页产销平衡的运输目题求解模板123456789101112产旱148443636811001232457616164964133245764425361432457644253615196324484484625416811692892894004411708090100110120130销量111111000000销电运价赛实际产$关系产能量/小成本I国10100000000001=10001000000001S100010000000001S1000100000001S10000010000001-1I000000000001=10000000000000二00000000000000:00000000000000Z0000000000000000000000000000-00000000000000Z00000000000000S0111111000000二二二-I-111111000000最优解实际销量关系销篇且12dAJ工£781一910I正12113ijaj1sji1lj18I一191201211221231241251盆辽28I一29130131132133134135136IM即:-32130222021302320223024起飞3011-1-12011-1-12012-1-13012-1-13013-1130141-1到达111111用的最少时间为134a。6.7某地区有两个镇，它们每周分别产生700吨和1200吨固体废物。现拟用三种方式（焚烧、填海、掩埋）分别在三个场地对这些废物进行处理。两城镇至各处理场所的运输费用、应处理量、各处理场的处理能力及每个场所的处理废物的固定成本和可变成本如下表：焚烧填海掩埋应处理量（吨）城镇1运费（元/吨）7.5515700城镇257.512.51200固定成本（元/周）3850011501920变动成本（元/周）12166处理能力（吨/周）10005001300试求使两城镇处理固体废物总的费用最小的方案。1、确定决策变量设方为两个城镇要别用三种不同方式处理固体废物的数量,乃为三种处理方式量否采用。如下表：焚烧填海掩埋应处理量（吨）城镇1运费（元/吨）XiX2XJ700城镇2X4X5X61200固定成本（元/周）385011501920y及变动成本（元/周）12166处理能力（吨/周）100050013002、确定目标函数本问题目标是总的处理费用为最小，而总的处理费为:f=运输费+固定成本+变动成本=7.5x+5x2+15x3÷5x+7.5xs+12.5历+3850y+1150yz+1920”+12(x+x4)+16(x2+x5)+6(x3+x6)所以目标函数为：min/=7.5x/+5x?+15xj+5x+7.5必+12.5+385Qy/+1150/2+1920)y+12(x+x)÷l6(x2+x5)+6(x3+M3、确定约束条件对于每个城镇，产生的废物都要处理掉xi+x2+xj=700X4+X5+X6=i2对于每个处理场，其处理废物的数量不能超过其处理能力。x+x1000yX2+X5W500/2X3+X61300yj即得混合整数规划问题数学模型：min/=19.5x+2lx2+2lxj+17x+23.5xs+18.5北+3850#+1150/2+1920”S.T.Xl+x2+m=700+x5+x6=1200jf+x-1000>,0X2+X5-500y,20X3+X6-I3y3Xi(i=l,2.6)y>V、Jj=O1返回首页代入混合整数模板求解如卜结果,埃划求爵唁果盅合整数规划模板9献屿也可由最优报IW保存螺1出5点结果姆OBffl（）I I I取霸）I保存方案9 J （砧助如1焚烧填海掩埋应处理量（吨）城镇1运费（元/吨）1000600700城镇2()500