第六章 整数规划.docx

《第六章 整数规划.docx》由会员分享，可在线阅读，更多相关《第六章 整数规划.docx（23页珍藏版）》请在课桌文档上搜索。

1、第六章整数规划6.1用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域（在图上用“X”标出）。1、maxz=3x2x2S.T.2x+3x2122xi+X29x.M20解：X28-A62、mini=10xi+9x2S.T.5x+3m245Xi28X210x.M206.2求解下列整数规划问题1、minf=4x3x22x3S.T.2x-5x23x344xi+m+3x323x2+x3.1x1.x2.x3=0或1解：将模型代入求解模板求解0-1整数规划模板返回首页我总荥IW结果妁虫备件*孰暴漕然幽一，可高足所有的妁束及最忧约栗条村为束约束条件冬际的美系窠利通O恢复为网的(Q)I睚i【IBifl1

2、|供存方案0).I硒()J即：最优解(0,0,1),最优值：22、minf=2x+5M+3x3+4x3S.T.-4+x2+x3+x4.2-2x+4x2+224x224x+x2-x2+x23XLX2、X3、X3=0或1解：此模型没有可行解。3、maxZ=2x+3x2+5%3+4S.T.5x+3x2+3%3+X4302x+5X2-X23X220-XI+345111I26I14-0*03k90100biOE0Gbll1204bl21304t)131404bl41120bl5160b!60t17180bl8190t)19200一 L妁条件或，约束条件约束约束条件实际值美系客数吸最优解：(0,0,0,1

3、,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乙7

4、568丙3435T7688解：1、消耗时间为最少问题（1）确定决策变量设0-1变量如下表，各变量表示是否分配给工作，0为不分配，1为分配。所工作需工人工作A工作B工作C工作D甲XiXi-X3乙-XaX5X6丙Xj即X9-VioT-VllX2.5-(2)确定目标函数本问题的目标是所用总的时间为最少，而总时间为：18x+16x219-3+20416xs+2Ch+19力+18+17x92Lvo12,i+15x220xi3所以目标函数为：minJ=18x+l6x2+193+2x4+16x5+2(h+19幻+18+17x9+2lxo12xn+15x2+20x3(3)确定约束条件因为每人只能分配一项工作所

5、以对于每人而言X+42+X3=1x4+5+x6=1X7+X8+X9+X1O=1Xll+X12+X13=l又每项工作只能分配给一个人人，所以对于每项工作X+X7X11=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=1

6、Xix)且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由。孙X12T13XI4X5Xl

7、S(2)确定目标函数本问题的目标是所得总的创利为最多，而总创利为：4+5273+94755X66X7+8X8+3X94xio+3xll+5X!27X136X148xi58xi6所以目标函数为：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+6Xl+X14=lX3+7+Xl+X5

8、i4+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,3160-1静数规划模板约皴条由约力约金条行Holnna代人求解模板得结果：最优解：(0,0,0,1,1,0,0,0,0,1,0,0,

9、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.

10、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二、确定目标函数则此问题的固定成本及总运输

11、费最小的目标可写为minZ=8ai+4垃+3冷+5以+2xs34x73+4通+9xo+7x+5x2+10x34X4+2x57.5J+30f2+37.5J3+50*其中后4项为固定投资额，前15项为运输费用。三、确定约束条件对Al厂来说其产量的限制的约束条件可写成x+x2+33（Al的产量）但是对A2,A3,A4,A5准备选址建设的新厂来说，只有当选为厂址建设，才会有生产量，所以它们的产量限制的约束条件写成X4X5X6lyi（A2的产量），X7X8X92j2（A3的产量），Xl+Xl+x23j3（A4的产量），X1314154j4（A5的产量），至于满足销量的约束条件可写为Xl+松+X7Xl+箝

12、3=3（Bl的销量），X2+Xs+X8Jfll+Jf|4=2（B2的销量），X3+X6+X9+Xi2+X5=2（B3的销量），再加上此为非负整数及8为01变量的约束就得到了此问题的数学模型。目标函数minz=8x14m+3刈+5x+2必+3抵+4和+3a+4期）+9心）+7+5x2+10x3+4X14+2x517.5630x737.5xs+50X19S.T.x+X2+X33X4+X5X6-X60X7+X89-2X17Oo+XlIXl2-3x80X3X45-4x90Xl+X4+X7+Xi0+X13=3X2+Xi+X8+X11+X4=2X3+X6+X9+Xi2+X5=2为为非负整数（i=l,215

13、）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=8x4&+3不+54+2玲+3抵+4*7+3+4为+9X4o+7m+5Xi?10Xi34xu2x5l7.5x630xi737.5Xis+50X19S.T.X1+x2+x33X4+X5+Afe-X16OX7X8X9-2x70XIo+x+x2-3x80Xl3X14X

14、5-4X190X+x+X7Xl+X3=3Xl+X5+X8X1+X4=2工3+X6X9+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小时；这些航线每天班机起飞与到达时间

15、如下表：航班号起飞城市起飞时间到达城市到达时间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:00

16、3023广州14:00北京17:003024广州18:00北京21:00设飞机在机场停留期间的费用与停留时间的平方成正比，又每架飞机从降落到再起飞至少需要2小时的时间准备。确定一个使总的停留费用损失为最小的方案。解：现在有两注意的两个问题1、三个城市间的飞行，航班的安排分别是在三个城市中完成的；2、到站的航班必须2小时后才能起飞。下面先看三个城市航班情况：城市兰州停留时4到起航班号10112011201210121013起习时间6：007：OO9：0012：OO18：OO航班号到达时I京*10219：OO21222439102212：OO181921246202117：OO1314161925

17、102319：OO1112141723202220：OOIO11131622城市北京xK起停留时I品、飞航班号3011102130121022301310233014起习时间579IO131718航班号到达时间101182123252591030219202224254893022131618202124451012141517192023343023171214161720242310132091113141721223024218101213162021城市广州起停留时俞飞到:航班号302130222021302320223024起习时间61014141718航班号到达时而30118222

18、669IO2011IO1824447820121218222256301212182222563013161418222225230142191317172021再看三个城市的效益表:城市兰州01120112012101210131021441a484a536a9a81a1022306a361a441a536a36a2021169a196a256a361a625a1023121a144a196a289a529a2022100a121a169a256a484a5J0112011201210121013起飞10214414845369811102230636144153636120211691962563616251102312114419628952912022IOO1211692564841到达11111代入指派模板求解得结果:AIBICID即:e,0X2+X5-500y,20X3+X6-I3y3Xi(i=l,2.6)yV、Jj=O1返回首页代入混合整数模板求解如卜结果,埃划求爵唁果盅合整数规划模板9献屿也可由最优报IW保存螺1出5点结果姆OBffl（）I I I取霸）I保存方案9 J （砧助如1焚烧填海掩埋应处理量（吨）城镇1运费（元/吨）1000600700城镇2()500