会议筹备问题的整数规划模型

1会议筹备问题的整数规划模型摘要本文运用穷举法和整数规划建立了数学模型，从而为会议筹备组制定了一个预定宾馆客房，租借会议室以及租用客车的合理方案。第一，利用以往有关住房的信息，初步估计本届会议到会代表658人。第二，通过穷举法，结合会议代表的要求，在宾馆数尽可能少的前提条件下选出了与会代表下塌1，2，5，7号宾馆最为合理。第三，考虑参加会议代表的方便以及参加分组会议时各宾馆之间的用车问题，本文分六种情况建立了整数规划模型，然后运用lingo求解。模型之一如下：321600700800minxxxz满足约束条件为正整数4321321432132143214321321,,,,,,170115220753001151871121217658)621()611()611()621(333645yyyyxxxyyyyxxxyyyyyyyyxxx第四，分别计算六种方案租借会议室和租车费用之和，取其中最小量的对应方案作为本届会议的最优方案。即：(1)预订宾馆的具体方案为方案宾馆123①普通双标间15商务双标间25普通单人间30商务单人间20②普通双标间50豪华双标间A30商务双标间35豪华双标间B30⑤普通双标间A34豪华商标间40⑦普通双标间50商务单人间40商务套房30(2)①、②、⑤、⑦号宾馆分别租借1、2、1、2个会议室，租金合计为5800元；(3)①安排3辆33座的车，②号宾馆安排5辆45座的车，⑤号宾馆安排2辆33座的车，⑦号1辆45座的车，1辆36座的车；(4)这届全国性会议举办一天需花费28600元。关键词：会议筹备；线性规划；穷举法概率2一．问题的提出某市的一家会议服务公司负责承办某专业领域的一届全国性会议，由于预计会议规模庞大，而适于接待这次会议的几家宾馆的客房和会议室数量均有限，所以与会代表应分散到若干家宾馆住宿，会议筹备组要为与会代表预订宾馆客房，租借会议室，并租用客车接送代表。现要求根据10家备选宾馆的有关数据建立数学模型，并为会议筹备组制定一个满足下列条件的要求的合理方案。)1(为了便于管理，选择的宾馆数量应该尽可能少，并且距离上比较靠近。)2(由于会议期间有一天的上下午各安排6个分组会议，且事先无法知道哪些代表准备参加哪个分组会，使得租借会议室，因此要求合理安排并且租赁客车的总成本达到最低。)3(结合经济，方便，代表满意等方面综合考虑制定一个预订宾馆客房、租借会议室、租用客车的合理方案。二．模型的基本假设)1(除分组会议外，这次会场安排以及运车情况忽略不计)2(每个代表参加上，下午的分组会议各参加一个且参加哪个会议是等可能的，即参加任意一个会议的概率为61；)3(方便与会代表，因此在选中的每个宾馆中至少应安排1个会议室；)4(代表去其他宾馆参加会议均要坐车并且给每个宾馆指派的车辆是专车性质的，即把本宾馆的的代表运往目的地，而在途中不运送其他宾馆的代表；)5(预订客房数最少且到会代表人人有房住，则优先安排双人间作为单人间使用.三．问题的分析与解决（一）.宾馆的数目问题：)1(第五届与会人数的预测问题①符号约定：ia——第i届发来回执的代表数量；ib——第i届发来回执但未与会的代表数量；ic——第i届未发回执但与会的代表数量；id——第i届实际与会代表的数量；ip——第i届实际与会代表的数量占第i届发来回执的代表数量的百分比；②问题的分析与解决第i届预测与会的代表数量为发来回执的代表数量中减去发来回执的代表数量再加上未发回执但与会的代表数量idiiicba第i届实际与会的代表数量占第i届发来回执的代表数量的百分比即iiiadp3表1第i届会议代表预测与会情况i1234ia315356408711ib89115121213ic576975104id283310362602ip89.087.088.084.0从上表可以看出第i届实际与会代表的数量占第i届发来回执的代表数量的百分比。可以据此来计算出第i届实际与会代表的数量占发来回执的代表数量的百分比的平均值，即441iiipp87.0则可以推测第五届实际与会代表的数量占发来回执的代表数量的百分比为24232221415)()()()(4iiiiiipppppppppp2222)87.084.0()87.088.0()87.087.0()87.089.0(87.087.00014.08714.0又可以由表2得出第五届发来代表的回执数量为：75560961664915223261iijx从而预测第五届到会的代表数量为6588714.0755人)2(宾馆的预订问题根据已知信息可知本届发来回执的代表人数为755，预测本届与会代表为658人。结合附表1，计算出本届与会代表预计的房间数，详见表2：表2本届预测与会的代表（单位：间）120-160161-200201-300合住1016722单住1448353合计24515075考虑到既要宾馆的数量最少，又要距离上尽可能接近，以便方便管理，所以可以从中心宾馆⑦出发，，以各宾馆与宾馆⑦的距离由远及近分别将各宾馆重新编号，结果如表3：表3现代码12345678910原代码⑦⑧⑤①⑥⑨②④⑩③根据附表2的分布图在满足预测与会代表需要的房间数的情况下选取各种可行的方案，根据穷举法可得表44表412345678910方案是否可行1▲▲▲▲▲▲√2▲▲▲▲▲▲√3▲▲▲▲▲▲×4▲▲▲▲▲▲√5▲▲▲▲▲▲√6▲▲▲▲▲▲×7▲▲▲▲▲▲▲×8▲▲▲▲▲▲√9▲▲▲▲▲▲√10▲▲▲▲▲▲×11▲▲▲▲▲▲×12▲▲▲▲▲▲√13▲▲▲▲▲▲√14▲▲▲▲▲▲×15▲▲▲▲▲▲√16▲▲▲▲▲▲×17▲▲▲▲▲▲×18▲▲▲▲▲▲×19▲▲▲▲▲×20▲▲▲▲▲×21▲▲▲▲▲×22▲▲▲▲▲×23▲▲▲▲▲×24▲▲▲▲▲×25▲▲▲▲▲×26▲▲▲▲▲×27▲▲▲▲▲×28▲▲▲▲▲×29▲▲▲▲▲×30▲▲▲▲▲×31▲▲▲▲▲√32▲▲▲▲▲√33▲▲▲▲▲×34▲▲▲▲▲×35▲▲▲▲×36▲▲▲▲×37▲▲▲▲×宾馆方案538▲▲▲▲√39▲▲▲▲×40▲▲▲▲×41▲▲▲▲×42▲▲▲▲×43▲▲▲▲×44▲▲▲▲×45▲▲▲▲×由上表选取宾馆数量最少的为可行方案，即满足条件的宾馆最小数目为4个：1，3，4，7；原代码为①，②，⑤，⑦。（二）租借会议室和租赁车辆问题1.题意分析假设：①经过运算与数据处理，本题得出宾馆号是1、2、5、7。由于会议期间有一天的上下午各安排6个分组会议，假设代表参加6个分组的概率是等同的，也就是说下榻在宾馆的代表有61的在本宾馆开会。所以安排的会议规模至少有110人。○2为了代表的方便，每个宾馆至少上、下午各安排一个会议，故要考虑乘车费用最少，我们假设：a.为了减少代表坐车的费用，每个宾馆至少安排一个会议b.为了让筹备组准备的车辆少，也就是租金最少。2.建立整数规划模型：设x、2x、3x分别表示需要800元45座，700元36座、600元33座来接送代表的客车数。1y、2y、3y、4y分别表示在宾馆1、2、5、7最优下榻的代表数，用z表示租金。①该筹备组的目标是在尽量满足代表在价位等方面的需求的条件下，如何确定租车数1x、2x、3x以得到最少的租金，若这时z321600700800xxx。②对各个宾馆人数取最大最小值，我们有以下不等式：1871121y3001152y220753y1701154y③车座的总数应该大于需坐车人数，即4321321)621()621()611()611(333645yyyyxxx。④下榻人数总和为658，即6584321yyyy⑤需要车辆最大最小值，分别为12，17，即12.17321xxx故建立整数规划如下：○1当1、2宾馆安排1个会议，5、7宾馆安排两个会议：6目标函数min321600700800xxxz满足约束条件为正整数4321321432132143214321321,,,,,,1701152207530011518711212.17658)621()621()611()611(333645yyyyxxxyyyyxxxyyyyyyyyxxx运用lingo，结果见附表4。○2当1、5宾馆安排1个会议，2、7宾馆安排两个会议：目标函数min321600700800xxxz满足约束条件为正整数4321321432132132143214321321,,,,,,170115220753001151871121712658)621()611()621()611(333645yyyyxxxyyyyxxxxxxyyyyyyyyxxx○3当1、7宾馆安排1个会议，2、5宾馆安排两个会议：目标函数321600700800minxxxz满足约束条件7为正整数4321321432132132143214321321,,,,,,170115220753001151871121712658)611()621()621()611(333645yyyyxxxyyyyxxxxxxyyyyyyyyxxx○4当2、5宾馆安排1个会议，1、7宾馆安排两个会议：目标函数min321600700800xxxz满足约束条件为正整数4321321432132132143214321321,,,,,,170115220753001151871121712658)621()611()611()621(333645yyyyxxxyyyyxxxxxxyyyyyyyyxxx○5当2、7宾馆安排1个会议，1、5宾馆安排两个会议：目标函数min321600700800xxxz满足约束条件为正整数4321321432132132143214321321,,,,,,170115220753001151871121712658)611()621()611()621(333645yyyyxxxyyyyxxxxxxyyyyyyyyxxx○6当5、7宾馆安排1个会议，1、2宾馆安排两个会议：8目标函数min321600700800xxxz满足约束条件为正整数4321321432132132143214321321,,,,,,170115220753001151871121712658)611()611()621()621(333645yyyyxxxyyyyxxxxxxyyyyyyyyxxx○2~○6的运算结果见附表4故，我们汇总各种情况的乘车费用与会议费用如表5：（半天）表5筹备组花费总和宾馆号1257租车费用（元）会议费用（元）总和（元）情况111228800580014600情况212218600600014600情况322118500620014700情况412128500580014300情况521218700620014900情况621128800600014800根据上表可以得出，筹备组花费半天最少的筹备金为14300元。那么一天花费的租金为28600元。筹备组为代表们半天租的车辆为800元45座6辆，700元36座1辆，600元33座的5辆。详细安排如下：①号安排3辆33座的车，②号宾馆安排5辆45座的车，⑤号宾馆安排