运筹学-整数规划

上页下页返回整数规划（integerprogramming)1.几个实例2.整数规划的算法—分支定界法和割平面方法3.Lingo/Lindo求解整数规划上页下页返回例1。人员安排问题整数规划某宾馆一天各时段需要的人数如下所示。按规定，服务员连续工作八小时为一班。现要求安排服务员的工作时间，使所需服务员总数最少。上页下页返回时段始末时间所需服务员人数16:00~8:00628:00~10:0012310:00~12:0010412:00~14:008514:00~16:009616:00~18:0014718:00~20:008820:00~22:006922:00~24:004某宾馆一天各时段需要的人数如下所示。按规定，服务员连续工作八小时为一班。现要求安排服务员的工作时间，使所需服务员总数最少。上页下页返回解：设xj表示第j时段开始上班的服务员人数。由于每两小时为一时段，所以第j时段开始上班的服务员将在第j+3时段结束时下班。因此只考虑6,...,3,2,1xxxx相应的模型为：61miniixz)1(61时段x)2(1221时段xx)3(10321时段xxx时段始末时间所需服务员人数16:00~8:00628:00~10:0012310:00~12:0010412:00~14:008514:00~16:009616:00~18:0014718:00~20:008820:00~22:006922:00~24:004上页下页返回6,...,1,0468146656546543ixxxxxxxxxxxi84321xxxx95432xxxx时段始末时间所需服务员人数16:00~8:00628:00~10:0012310:00~12:0010412:00~14:008514:00~16:009616:00~18:0014718:00~20:008820:00~22:006922:00~24:004第4阶段5阶段6阶段7阶段7阶段9阶段上页下页返回621...minxxxz6,...,2,10468149810126..665654654354324321321211ixxxxxxxxxxxxxxxxxxxxxxxxxtsi且为整数，整数规划上页下页返回利用数学软件lingo可求得一个最优解为：X1=12.000000X2=0.000000X3=6.000000X4=2.000000X5=1.000000X6=5.000000最优值为26，具体过程如下：上页下页返回求解程序为Liti1aMIN=x1+x2+x3+x4+x5+x6;x16;x1+x212;x1+x2+x310;x1+x2+x3+x48;x2+x3+x4+x59;x3+x4+x5+x614;x4+x5+x68;x5+x66;x64;@gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(x6);end6,...,2,10468149810126..665654654354324321321211ixxxxxxxxxxxxxxxxxxxxxxxxxtsi且为整数，621...minxxxz上页下页返回OBJECTIVEFUNCTIONVALUE(1)26.00000VARIABLEVALUEX112.000000X20.000000X36.000000X42.000000X51.000000X65.000000另一最优解为OBJECTIVEFUNCTIONVALUE1)26.00000VARIABLEVALUEX16.000000X26.000000X30.000000X40.000000X53.000000X611.000000最优解不唯一liti1b上页下页返回OBJECTIVEFUNCTIONVALUE1)26.00000VARIABLEVALUEREDUCEDCOSTX112.0000001.000000X20.0000001.000000X36.0000001.000000X42.0000001.000000X51.0000001.000000X65.0000001.000000上页下页返回例2（布线问题）解决某市消防站的布线问题。该城市共有6个区，每个区都可以建立消防站，市政府希望设置的消防站最少，但必须满足在城市任何地方发生火警时，消防车要在15分钟之内赶到现场，根据实地考察，各区之间消防车行驶的时间见下表请帮助该市制定一个最节省的计划。上页下页返回地区1地区2地区3地区4地区5地区6地区101016282720地区210024321710地区316240122721地区428321201525地区527172715014地区620102125140各区之间消防车行驶的时间表上页下页返回解：每个地区是否设消防站可用一个0-1变量来表示。令不设消防站，地区设消防站地区iixi0,1i=1,2,…,6本题要求消防站的个数最少，故目标函数为：654321minxxxxxxz约束条件为：上页下页返回1612xxx143xx1534xxx1645xxx1526xxx6,...,110ixi，或时间123456地区101016282720地区210024321710地区316240122721地区428321201525地区527172715014地区620102125140各区之间消防车行驶的时间表约束条件为：)1(121确保地区xx上页下页返回111111..5266455344362121xxxxxxxxxxxxxxxxts6,...,110ixi，或654321minxxxxxxz时间123456地区101016282720地区210024321710地区316240122721地区428321201525地区527172715014地区620102125140OBJECTIVEFUNCTIONVALUE1)2.000000VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X21.0000001.000000X30.0000001.000000X41.0000001.000000X50.0000001.000000X60.0000001.000000min=x1+x2+x3+x4+x5+x6;x1+x21;x1+x2+x61;x3+x41;x3+x4+x51;x4+x5+x61;x2+x5+x61;@bin(x1);@bin(x2);@bin(x3);@bin(x4);@bin(x5);@bin(x6);end计算程序为求解报告为最优方案为x2=x4=1,即在第2区和第4区设置消防站即可。liti3@bin(x)-表示x取值为0或1上页下页返回例3（最优装载问题）例3（美国1988年大学生建摸竞赛B题)要把七种规格的包装箱装到两辆平板车上去，箱子的宽、高、相同，而厚度和重量不同。下表给出了他们的厚度和重量及数量。第i种箱子1234567厚度t（厘米）48.752.061.372.048.752.064.0重量w（千克）200030001000500400020001000数量n8796648上页下页返回每辆平板车有10.2米的地方用于装箱，载重40吨。由于货物的限制，对于第5、6、7三种包装箱的装载有如下约束：它们所占的空间（厚度）不得超过302.7厘米，试把这些包装箱装到平板车上去，使浪费的空间最小。解：容易计算出所有的包装箱的厚度为27.495米，而两俩平板车共有20.4米长的地方，所以不可能都装上。记表中所给出的第i种箱子的厚度、重量和数量分别为ti、wi和ni（i=1,2,..,7),又记第i种箱子装到第1、2辆平板车上的数量分别为xi1,xi2（i=1,2,..,7)上页下页返回第i种箱子1234567厚度ti（厘米）48.752.061.372.048.752.064.0重量wi(吨）2310.5421数量ni8796648上页下页返回问题要求浪费的空间最小，即装载所占的空间最大，故目标函数为：7121maxijijixtz约束条件为：厚度约束：2,1,102071jxtiiji重量约束：712,1,40iijijxw第i种箱子1234567厚度ticm48.752.061.372.048.752.064.0重量wi(t）2310.5421数量ni8796648每辆平板车有10.2米的地方用于装箱，载重40吨记第i种箱子装到第1、2辆平板车上的数量分别为（i=1,2,..,7)21,iixx上页下页返回数量约束：217,..,2,1,jiijinx特殊约束：7521,7.302)(iiiixxt2,1,7.30275jxtiiji或第i种箱子1234567厚度ticm48.752.061.372.048.752.064.0重量wi(t）2310.5421数量ni8796648第5、6、7三种包装箱的装载有如下约束：它们所占的空间（厚度）不得超过302.7厘米，(每辆平板车不超过302.7cm)上页下页返回7121maxijijixtz71752121712,1,10207.302)(7,..,2,1,2,1,40..iijiiiiijiijiijijxtxxtinxjxwts为整数,2,1,7,..,1i,0jxij故得到两个整数规划模型为：(IP1)(IP2)7121maxijijixtz717521712,1,10202,1,7.3027,..,2,1,2,1,40..iijijijijiijiijijxtjxtjnxjxwts为整数,2,1,7,..,1i,0jxij上页下页返回现解第一个问题：(IP1)7121maxijijixtz71752121712,1,10207.302)(7,..,2,1,2,1,40..iijijiiijiijiijijxtxxtjnxjxwts为整数,2,1,7,..,1i,0jxijLiti3.ltxLiti3.txt上页下页返回利用lindo求解得到最优解为：平板车1平板车2箱子类型c1c2c3c4c5c6c7c1c2c3c4c5c6c7最优值解1056000082702002039.4解2856000002363302039.4解3069003081063002039.4解4519120036051302039.4上页下页返回MAX48.7x11+48.7x12+52.0x21+52.0x22+61.3x31+61.3x32+72.0x41+72.0x42+48.7x51+48.7x52+52.0x61+52.0x62+64x71+64x72st48.7x11+52x21+61.3x31+72x41+48.7x51+52x61+64x71102048.7x12+52x22+61.3x32+72x42+48.7x52+52x62+64x7210242x11+3x21+x31+0.5x41+4x51+2x61+x71402x12+3x22+x32+0.5x42+4x52+2x62+x7240x11+x128x21+x227x31+x329x11+x128x21+x227x31+x329x41+x426x51+x526x61+x624x71+x72848.