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

1、会议筹备问题的整数规划模型摘要 本文运用穷举法和整数规划建立了数学模型，从而为会议筹备组制定了一个预定宾馆客房，租借会议室以及租用客车的合理方案。第一，利用以往有关住房的信息，初步估计本届会议到会代表658人。第二，通过穷举法，结合会议代表的要求，在宾馆数尽可能少的前提条件下选出了与会代表下塌1，2，5，7号宾馆最为合理。第三，考虑参加会议代表的方便以及参加分组会议时各宾馆之间的用车问题，本文分六种情况建立了整数规划模型，然后运用lingo求解。模型之一如下：满足约束条件第四，分别计算六种方案租借会议室和租车费用之和，取其中最小量的对应方案作为本届会议的最优方案。即：(1) 预订宾馆的具体方案

2、为方案宾馆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元。 关键词：会议筹备；线性规划；穷举法概率一问题的提出某市的一家会议服务公司负责承办某专业领域的一届全国性会议，由于预计会议规模庞大，而适于接待这次会议的几家宾馆的客

3、房和会议室数量均有限，所以与会代表应分散到若干家宾馆住宿，会议筹备组要为与会代表预订宾馆客房，租借会议室，并租用客车接送代表。现要求根据10家备选宾馆的有关数据建立数学模型，并为会议筹备组制定一个满足下列条件的要求的合理方案。为了便于管理，选择的宾馆数量应该尽可能少，并且距离上比较靠近。由于会议期间有一天的上下午各安排6个分组会议，且事先无法知道哪些代表准备参加哪个分组会，使得租借会议室，因此要求合理安排并且租赁客车的总成本达到最低。结合经济，方便，代表满意等方面综合考虑制定一个预订宾馆客房、租借会议室、租用客车的合理方案。二模型的基本假设除分组会议外，这次会场安排以及运车情况忽略不计 每个代

4、表参加上，下午的分组会议各参加一个且参加哪个会议是等可能的，即参加任意一个会议的概率为；方便与会代表，因此在选中的每个宾馆中至少应安排1个会议室；代表去其他宾馆参加会议均要坐车并且给每个宾馆指派的车辆是专车性质的，即把本宾馆的的代表运往目的地， 而在途中不运送其他宾馆的代表；预订客房数最少且到会代表人人有房住，则优先安排双人间作为单人间使用.三问题的分析与解决（一）.宾馆的数目问题：第五届与会人数的预测问题符号约定：第届发来回执的代表数量；第届发来回执但未与会的代表数量；第届未发回执但与会的代表数量；第届实际与会代表的数量；第届实际与会代表的数量占第届发来回执的代表数量的百分比；问题的分析与解

5、决第届预测与会的代表数量为发来回执的代表数量中减去发来回执的代表数量再加上未发回执但与会的代表数量第届实际与会的代表数量占第届发来回执的代表数量的百分比即表第届会议代表预测与会情况从上表可以看出第届实际与会代表的数量占第届发来回执的代表数量的百分比。可以据此来计算出第届实际与会代表的数量占发来回执的代表数量的百分比的平均值，即则可以推测第五届实际与会代表的数量占发来回执的代表数量的百分比为又可以由表2得出第五届发来代表的回执数量为：从而预测第五届到会的代表数量为人宾馆的预订问题根据已知信息可知本届发来回执的代表人数为755，预测本届与会代表为658人。结合附表1，计算出本届与会代表预计的房间数

6、，详见表2：表2 本届预测与会的代表（单位：间）120-160161-200201-300合住单住合计考虑到既要宾馆的数量最少，又要距离上尽可能接近，以便方便管理，所以可以从中心宾馆出发，以各宾馆与宾馆的距离由远及近分别将各宾馆重新编号，结果如表3：表3现代码原代码 根据附表2的分布图在满足预测与会代表需要的房间数的情况下选取各种可行的方案，根据穷举法可得表4表4宾馆方案方案是否可行23456789101112131415161718192021222324252627282930313233343536373839404142434445由上表选取宾馆数量最少的为可行方案，即满足条件的宾馆最

7、小数目为4个：1，3，4，7；原代码为，。（二）租借会议室和租赁车辆问题1. 题意分析假设： 经过运算与数据处理，本题得出宾馆号是1、2、5、7。由于会议期间有一天的上下午各安排6个分组会议，假设代表参加6个分组的概率是等同的，也就是说下榻在宾馆的代表有的在本宾馆开会。所以安排的会议规模至少有110人。 为了代表的方便，每个宾馆至少上、下午各安排一个会议，故要考虑乘车费用最少，我们假设：a. 为了减少代表坐车的费用，每个宾馆至少安排一个会议b. 为了让筹备组准备的车辆少，也就是租金最少。2.建立整数规划模型：设、分别表示需要800元45座，700元36座、600元33座来接送代表的客车数。、分

8、别表示在宾馆1、2、5、7最优下榻的代表数，用表示租金。该筹备组的目标是在尽量满足代表在价位等方面的需求的条件下，如何确定租车数、以得到最少的租金，若这时。对各个宾馆人数取最大最小值，我们有以下不等式：车座的总数应该大于需坐车人数，即。下榻人数总和为658，即需要车辆最大最小值，分别为12，17，即故建立整数规划如下：当1、2宾馆安排1个会议，5、7宾馆安排两个会议： 目标函数 满足约束条件 运用lingo，结果见附表4。当1、5宾馆安排1个会议，2、7宾馆安排两个会议：目标函数 满足约束条件 当1、7宾馆安排1个会议，2、5宾馆安排两个会议：目标函数 满足约束条件 当2、5宾馆安排1个会议，

9、1、7宾馆安排两个会议：目标函数 满足约束条件 当2、7宾馆安排1个会议，1、5宾馆安排两个会议：目标函数 满足约束条件 当5、7宾馆安排1个会议，1、2宾馆安排两个会议：目标函数 满足约束条件 的运算结果见附表4故，我们汇总各种情况的乘车费用与会议费用如表5：（半天）表5 筹备组花费总和 宾馆号1257租车费用（元）会议费用（元）总和（元）情况111228800580014600情况212218600600014600情况322118500620014700情况412128500580014300情况521218700620014900情况621128800600014800根据上表可以得出

10、，筹备组花费半天最少的筹备金为14300元。那么一天花费的租金为28600元。筹备组为代表们半天租的车辆为800元45座6辆，700元36座1辆，600元33座的5辆。详细安排如下：号安排3辆33座的车，号宾馆安排5辆45座的车，号宾馆安排2辆33座的车，号1辆45座的车，1辆36座的车。3预定宾馆的具体房间为了尽量满足大多数代表在价位方面的需求，同时为了保证人人有房可住，故优先安排双人间作为单人间使用。预订宾馆方案详细见表6：表6 预订宾馆方案 价格宾馆120160161200201300人数1普通双标间15商务双标间25112普通单人间30商务单人间202普通双标间50豪华双标间A3030

11、0商务双标间35豪华双标间B305普通双标间A34豪华商标间40767普通双标间50170商务单人间40商务套房30(三) 模型的进一步讨论.预订宾馆问题：第五届实际与会人数的计算方法同方案A，得出第五届实际与会人数为658人。 宾馆的预订问题，根据附表1，可得最佳宾馆组合符合要求初步定的有宾馆号1、2、6、7、8。2租借会议室和租赁车辆问题 （1）. 题意分析假设： 经过运算与数据处理，本题得出宾馆号是1、2、6、7、8由于会议期间有一天的上下午各安排6个分组会议，假设代表参加6个分组的概率是等同的，也就是说下榻在宾馆的代表有的在本宾馆开会。所以安排的会议规模至少有110人。 为了代表的方便

12、，每个宾馆至少上、下午各安排一个会议，故要考虑乘车费用最少，我们假设：c. 为了减少代表坐车的费用，每个宾馆至少安排一个会议d. 为了让筹备组准备的车辆少，也就是租金最少。（2）.建立整数规划模型：设、分别表示需要800元45座，700元36座、600元33座来接送代表的客车数。、分别表示在宾馆1、2、6、7、8最优下榻的代表数，用表示租金。该筹备组的目标是在尽量满足代表在价位等方面的需求的条件下，如何确定租车数、以得到最少的租金，若这时。对各个宾馆人数取最大最小值，我们有以下不等式：车座的总数应该大于需坐车人数，即。下榻人数总和为658，即需要车辆最大最小值，分别为12，17，即故建立整数规

13、划如下：情形一：当1、2、6、7宾馆安排1个会议，8宾馆安排两个会议： 目标函数 满足约束条件 运用lingo，结果见附表5。情形二：当1、2、7、8宾馆安排1个会议，6宾馆安排两个会议： 目标函数 满足约束条件 情形三：当1、2、6、8宾馆安排1个会议，7宾馆安排两个会议：目标函数 满足约束条件 情形四：当1、6、7、8宾馆安排1个会议，2宾馆安排两个会议：目标函数 满足约束条件 情形五：当2、6、7、8宾馆安排1个会议，1宾馆安排两个会议：目标函数 满足约束条件 情形二情形五运算结果见附表5；故，我们汇总各种情况的乘车费用与会议费用如表7：（半天）表7 筹备组花费总和宾馆号12678租车费

14、用（元）会议费用（元）总和（元）情况1211119200600015200情况2121119400580015200情况3112119200580015000情况4111219000560014600情况5111129300560014900根据上表可以得出，筹备组花费半天最少的费用为14600元。那么一天花费的租金为29200元。筹备组为代表们半天租的车辆为800元45座0辆，700元36座0辆，600元33座的12辆。可以看出，选取五个宾馆费用并不节省，从而验证了，在假设条件成立的情况下，选取四个宾馆1、2、5、7比较合理。参考文献（1）蔡锁章，数学建模原理与方法，北京：海洋出版社，200

15、0年。（2）白其峥，数学建模案例分析，北京：海洋出版社，1999年。（3）钱颂迪，运筹学，北京：清华大学出版社，1993年。附表1 本届实际与会的代表中有关住房要求的信息（单位：人）9128935936 其中，( 符号约定 表示合住房间的种类； 表示独住房间的种类 预测本届与会代表数量中要求合住类房间的男代表的数量；预测本届与会代表数量中要求合住类房间的女代表的数量；预测本届与会代表数量中要求独住类房间的男代表的数量；预测本届与会代表数量中要求独住类房间的女代表的数量。 本届发来回执的代表数量中要求合住类房间的男代表的数量；本届发来回执的代表数量中要求合住类房间的女代表的数量；本届发来回执的代

16、表数量中要求独住类房间的男代表的数量；本届发来回执的代表数量中要求独住类房间的女代表的数量。附表23（与间距300米） 1（与间距300米） 2（与间距300米） 4（与间距300米） 77与间距300米） 8间距300米） 10（与间距300米） 10005003001502003006（与间距300米） 5（与间距300米） 9（与间距300米） 300700150附表3I区间内各宾馆的房间数 价格区间宾馆 房间 1双人间50单人间4030合计90302双人间4040单人间45合计4085303双人间7040合计70404双人间5030单人间3020合计80505双人间4030单人间403

17、0合计4070306双人间60单人间60合计1207双人间8565合计85658双人间5045合计50459双人间100合计10010双人间5024单人间27合计5067附表4：程序一min= 800*a+700*b+600*c;270*a+216*b+198*c-5*e-4*f-4*j-5*h=0;e+f+j+h=658;e=112;f=115;j=75;h=115;a+b+c=12;gin (a);gin (b);gin (c);gin (e);gin (f);gin (j);gin (h);End运行结果一Global optimal solution found. Objective

18、value: 8600.000 Extended solver steps: 0 Total solver iterations: 7 Variable Value Reduced Cost A 7. 800.0000 B 0. 700.0000 C 5. 600.0000 E 112.0000 0. F 226.0000 0. J 205.0000 0. H 115.0000 0. Row Slack or Surplus Dual Price 1 8600.000 -1. 2 21.00000 0. 3 0. 0. 4 75.00000 0. 5 0. 0. 6 74.00000 0. 7

19、 111.0000 0. 8 15.00000 0. 9 130.0000 0. 10 55.00000 0. 11 0. 0. 12 5. 0. 13 0. 0.程序二min= 800*a+700*b+600*c;270*a+216*b+198*c-5*e-4*f-5*j-4*h=0;e+f+j+h=658;e=112;f=115;j=75;h=115;a+b+c=12;gin (a);gin (b);gin (c);gin (e);gin (f);gin (j);gin (h);End运行结果二Global optimal solution found. Objective value:

20、8500.000 Extended solver steps: 0 Total solver iterations: 2 Variable Value Reduced Cost A 6. 800.0000 B 1. 700.0000 C 5. 600.0000 E 112.0000 0. F 300.0000 0. J 76.00000 0. H 170.0000 0. Row Slack or Surplus Dual Price 1 8500.000 -1. 2 6. 0. 3 0. 0. 4 75.00000 0. 5 0. 0. 6 0. 0. 7 185.0000 0. 8 144.

21、0000 0. 9 1. 0. 10 0. 0. 11 55.00000 0. 12 5. 0. 13 0. 0.程序三min= 800*a+700*b+600*c; 270*a+216*b+198*c-5*e-5*f-4*j-4*h=0;e+f+j+h=658;e=112;f=115;j=75;h=115;a+b+c=12;gin (a);gin (b);gin (c);gin (e);gin (f);gin (j);gin (h);End运行结果三 Global optimal solution found. Objective value: 8800.000 Extended solve

22、r steps: 0 Total solver iterations: 4 Variable Value Reduced Cost A 8. 800.0000 B 0. 700.0000 C 4. 600.0000 E 112.0000 0. F 156.0000 0. J 220.0000 0. H 170.0000 0. Row Slack or Surplus Dual Price 1 8800.000 -1. 2 52.00000 0. 3 0. 0. 4 75.00000 0. 5 0. 0. 6 144.0000 0. 7 41.00000 0. 8 0. 0. 9 145.000

23、0 0. 10 0. 0. 11 55.00000 0. 12 5. 0. 13 0. 0.程序四min= 800*a+700*b+600*c; 270*a+216*b+198*c-4*e-4*f-5*j-5*h=0;e+f+j+h=658;e=112;f=115;j=75;h=115;a+b+c=12;gin (a);gin (b);gin (c);gin (e);gin (f);gin (j);gin (h);End运行结果四Global optimal solution found. Objective value: 8500.000 Extended solver steps: 0 T

24、otal solver iterations: 2 Variable Value Reduced Cost A 6. 800.0000 B 1. 700.0000 C 5. 600.0000 E 187.0000 0. F 281.0000 0. J 75.00000 0. H 115.0000 0. Row Slack or Surplus Dual Price 1 8500.000 -1. 2 4. 0. 3 0. 0. 4 0. 0. 5 75.00000 0. 6 19.00000 0. 7 166.0000 0. 8 145.0000 0. 9 0. 0. 10 55.00000 0

25、. 11 0. 0. 12 5. 0. 13 0. 0.程序五min= 800*a+700*b+600*c; 270*a+216*b+198*c-4*e-4*f-4*j-5*h=0;e+f+j+h=658;e=112;f=115;j=75;h=115;a+b+c=12;gin (a);gin (b);gin (c);gin (e);gin (f);gin (j);gin (h);End运行结果五Global optimal solution found. Objective value: 8300.000 Extended solver steps: 0 Total solver iterat

26、ions: 2 Variable Value Reduced Cost A 5. 800.0000 B 1. 700.0000 C 6. 600.0000 E 167.0000 0. F 300.0000 0. J 76.00000 0. H 115.0000 0. Row Slack or Surplus Dual Price 1 8300.000 -1. 2 7. 0. 3 0. 0. 4 20.00000 0. 5 55.00000 0. 6 0. 0. 7 185.0000 0. 8 144.0000 0. 9 1. 0. 10 55.00000 0. 11 0. 0. 12 5. 0. 13 0. 0.程序六min= 800*a+700*b+600*c; 270*a+216*b+198*c-4*e-5*f-5*j-4*h=0;e+f+j+h=658;e=112;f=115;j=75