《2009数学建模D题会议安排的优化模型论文.doc》由会员分享,可在线阅读,更多相关《2009数学建模D题会议安排的优化模型论文.doc(14页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、会议筹备问题的数学优化模型摘 要此类问题属于优化问题,要求我们从组委会的角度出发制定出预订客房,租借会议室,租用客车的最佳方案。我们以宾馆数量少、宾馆相对集中为原则,在满足与会代表具体要求的前提下,我们得到了该类问题的相关结果。其具体解决方案如下: 首先,我们对附件数据做了必要的分析,采用平均百分比和线性回归两种方法分别计算出了与会代表的人数,但由于往年资料有限,我们排除了线性回归的方法,并预测实际与会人数为661人。然后,我们按回执中各类房间所占的不同比重来确定最终订房类别及数量。 其次,从满足代表住房要求的原则出发,尽量选择所需宾馆数量最少为原则并保证与会代表相对集中,我们建立整数规划模型
2、,并确定目标函数和约束条件,得出最优解。最终选定了1、2、5、7四家宾馆,同时,求出了与会代表的满意度。关于会场租赁及租车问题,由于需要6个会场,且每个会场与会人数不确定,我们只考虑了一种平均意义下的结果。利用整数规划模型并借助LINGO软件求出最优解,最终选择2号宾馆130人会议室2间,180人会议室1间,5号宾馆150人会议室2间,180人会议室1间。根据与会代表入住每个宾馆的人数情况,我们得到需要租45座车4辆,36座车4辆,33座车4辆。两项合计总费用为30600元。关键词:回执数量、平均百分比、线性回归、整数规划模型、 LINGO软件、与会代表满意度。一、问题重述与分析某会议服务公司
3、负责承办一届全国性会议,会议筹备组要为与会代表预订宾馆客房,租借会议室,并租用客车接送代表。由于预计会议规模庞大,而适于接待这次会议的几家宾馆的客房和会议室数量均有限,所以只能让与会代表分散到若干家宾馆住宿。筹备组要在10家宾馆中选定几间来为代表预定房间。为了便于管理,除了尽量满足代表在价位等方面的需求之外,所选择的宾馆数量应该尽可能少,并且距离上比较靠近。 备选宾馆的名称用代号至表示,相对位置见附图,有关客房及会议室的规格、间数、价格等数据见附表1。 根据附表2与附表3从以往几届会议情况来预订宾馆客房。而预定的客房房费由与会代表自付,但是如果预订客房的数量大于实际用房数量,筹备组需要支付一天
4、的空房费,而若出现预订客房数量不足,则将引起代表的不满。 会议期间有一天的上下午各安排6个分组会议,筹备组需要在代表下榻的某几个宾馆租借会议室。由于事先无法知道哪些代表准备参加哪个分组会,筹备组还要向汽车租赁公司租用客车接送代表。现有45座、36座和33座三种类型的客车,租金分别是半天800元、700元和600元。 本题希望我们通过数学建模方法,从经济、方便、代表满意等方面,为会议筹备组制定一个预订宾馆客房、租借会议室、租用客车的合理方案。该问题来源于实际生活,我们认为合理的方案需要考虑如下因素:1尽可能准确地估计预定客房数,尽可能地满足与会代表要求 ;2尽可能少选宾馆数,且宾馆尽可能集中;3
5、. 租会议室及租车的费用尽可能少。二、模型的假设1. 假设前四届会议与会代表出席会议情况是相互独立的。2. 假设未发回执但前来与会的代表住房要求与已经发了回执前来与会的代表的住房要求情况是相同。3. 设每位与会代表参加任何分组会议的概率是随机的。 4. 假设所有与会代表参加本宾馆外的分组会议都需要车接送。5. 假设每辆车只走一个单程,且不考虑中途有行人上下车的情况。三、基本符号说明:分别为实际与会人数占发回执人数比平均值及最大值。di:租借的第i类车的辆数。:第i类车的租金(表示45座的车,表示36座的车,表示33座的车)。T1j:需要预订合住第j种类型客房数量。j=1,2,3。T2j:需要预
6、订独住第j种类型客房数量。j=1,2,3。C1ij:第i家宾馆第j种类型双人房(合住或独住)能提供的间数。C2ij :第i家宾馆第j种类型单人房(独住)能提供的间数。x1ij:第i家宾馆第j种类型双人房(合住)间数 。x2ij :预订第i家宾馆第j种类型单人房(独住)间数。 Yij: 预订第i家宾馆第j种类型双人房(改独住)间数 。四、模型的建立及求解1关于参加会议的代表人数: 为了合理安排本届与会代表入住宾馆,我们采用平均百分比法来计算。首先,必须明确本届代表与会的基本情况。由附表2可知本届代表的回执代表数量为755人;由附表3进一步分析以往几届会议代表的基本情况和相对应的比例后,结果如(表
7、1)所示:表1以往几届会议代表回执和与会情况第一届 第二届 第三届 第四届 第五届发来回执的代表数量315356408711755发来回执但未与会的代表数量89115121213未发回执而与会的代表数量576975104实际参加人数283310362602661(678) 实际参加数/发来回执数0.89840.87080.88730.8467经计算得 ,第五届会议与会人数。 2关于入住类型: 假设未发回执前来与会的代表住房要求与已发回执的情况相同,且发来回执的人住房要求与实际参加的人要求一致(概率相等)。对附表1给定的信息,我们考虑的因素进一步增加,从附表2利用Excel画出其所反应的趋势图(
8、见附录1)看,通过假设,本届会议发来回执且与会代表按百分比(1-30.04%=69.96%)进行估算,得到本届会议发来回执且与会代表的入住情况如表2所示(计算结果以四舍五入记录)。表2. 本届会议发来回执且与会代表的入住情况合住1合住2合住3独住1独住2独住3男1087322754827女553412412013根据附表2,我们运用相应比例关系估算出未发来回执而与会代表的入住情况如表3所示(计算结果以四舍五入记录)。表3 未发来回执而与会代表的入住情况合住1合住2合住3独住1独住2独住3男2718619127女14831053由表2和表3综合估算出:本届会议与会代表的实际入住情况如表4所示:表
9、4.实际房间数合住1合住2合住3独住1独住2独住3男(人数)135912894 60 36女(人数)69421552 25 17总人数20413343145 84 53房间数1026722 145 84533.关于宾馆的选择 因为宾馆越少,与会代表入住要求集中,而要满足所需的客车更少,会场也更集中。我们以宾馆数最少为目标,以满足代表入住要求及10家备选宾馆现有资源为约束,建立该问题的优化模型来解决这个问题。考虑附件1的数据及表4的数据得到该问题的数学模型如下:目标函数: 约束条件(需求关系与供给关系):s.t: 对于该类整数规划问题,我们可以借助lingo软件求解得到,但是该问题的结果不唯一。
10、下面是给出的是几组可行解(见表5): 表5 房间预订情况 宾馆合1合2合 3独1独2独3122将2 标2改独一30+标改独1620+标改独325034标改独35标改独315523318标改独7740+50(合改独)30剩余宾馆2房间数合计1026722 1458453该方案的主要特点是充分利用了宾馆2与5及1与7。从表中可以看出,如果选择1,2 5,7 及6或8共5个宾馆所有预计到会的代表都能住到所要求价位的房间,即代表满意程度为100%。考虑到租车等问题,可以考虑代表不满意度问题,例如选择宾馆1的2个160-200元的标间改为120-160元的单间,就可以不考虑宾其他馆。不满意度 为2/66
11、1=0.3%。4. 关于会议室选择与车辆安排:从租用客车费用考虑,设为租借的第i类车的辆数,为第i类车的租金(表示45座的车,表示36座的车,表示33座的车),建立优化模型如下:目标函数:约束条件:表7 各宾馆人数统计宾馆类型 宾馆1 宾馆2 宾馆5宾馆7人数 115 234 194 120由此可见,共需45座车4辆 ,36座车4辆 ,33座辆车4辆。具体用车方案如下: .1辆45座车,2辆36座车从宾馆1满载出发先至宾馆2再开往宾馆5。 .2辆45座车,1辆33座车从宾馆7出发先到宾馆5,再开往宾馆2。 .2辆36座,1辆45车从宾馆2开往宾馆5。 .3辆33座车从宾馆5开往宾馆2。用LIN
12、GO软件编程并运行(程序见附录5),其结果得出租借客车费为:5700元。五、模型的评价与改进1、与会人员模型改进:对附表3给出的前几届会议代表回执和与会情况数据进行统计发现,发来回执但未与会的代表比例稳定,约为30%,未发回执而与会的代表比例约为17.6%。与会代表比例、均值和方差见表9。 表9 与会代表比例、均值和方差第一届第二届 第三届 第四届平均值 方差 人 数(人)百分比(%)人数 百分比(%) 人数百分比(%) 人 数 (人)百分比(%)发来回执但未与会的代表 89 28.25 115 32.30 12129.6621329.96 0.3004 0.0145未发回执而与会的代表571
13、8.10 69 19.38 75 18.38 104 14.63 0.1762 0.0179 可以认为,发来回执未与会的代表比例和未发回执而与会的代表比例服从正态分布,并取置信度为95%,则应取置信区间下分位点作为发来回执未与会的代表预测数量,取置信区间上分位点作为未发回执而与会的代表预测数量。其计算公式为: 将数据代入上式计算得到与会代表总数为708.84人,向上取整数为709人,其中发来回执且与会的代表539人,未发回执而与会的代表147人。用MATLAB软件对方差较大的未发回执而与会的代表比例进行正态分布的卡方检验,证明假设:未发回执而与会的代表比例服从正态分布是合理的。同理,我们可以证
14、明发来回执未与会的代表比例也服从正态分布。 表10 未发回执而与会的代表比例的卡方检验分段点 F值 概率 理论频数 2 卡方值 临界值 0.16 0.1830 0.1830 0.7318 0.0983 0.18463.84150.19 0.7789 0.5959 2.3837 0.06180.22 0.9927 0.2138 0.8552 0.02452、模型的评价与分析: 对人员的预测用两种不同的方法进行分析,而对宾馆和房间的确定也综合考虑了经济、方便、数量少、代表满意、少支付空房费等多种因素,分别建立了两种数学基本模型求解。但也忽略了部分实际生活中的因素,模型偏于理想化。主要表现在: (1
15、)、 对实际问题及现实的交通情况的考虑不够,实际的情况会影响对客车的预定的问题,比如说堵车,而汽车行驶也不一定沿路直线行驶,可能会斜穿马路。 (2)、没有考虑万一出现与会代表人数大大超出会议室规模的情况的解决方案。 (3)、 在实际问题中我们还应考虑交通问题、客车的加速行驶到减速停车过程的时间、上下车完毕的时间,将它们的总和与正常人在一定小距离内步行的时间作比较,以此来确定在多远的距离内不需要客车接送代表,从而改进模型,使其更加符合要求。 (4)、 在确定会议室和安排客车方面,能够在满足实际需求的基础上,更好的为筹委会节省开支,故方案更佳。但是,该模型本身还是有一些不完善的地方的,首先就是我们
16、没有考虑,在距离很近的时候,可以采用代表步行的方式参会,从而可以省去一大笔车费。例如之间仅有150米远的距离,此时再采用客车接送显得有点牵强。其次就是,我们方案中没有给突发情况留有较大的余地,每辆车的乘坐率很高,每趟车基本仅剩下几个空座,实际情况可能不是我们预测的那样代表完全等可能的参加各分组会议,此时就会出现一些车拥挤不堪的而另外一些车剩座较多的情况。此时这个方案就显得有些不完善。 (5)、以上模型都是利用以往数据的平均数来分析的,随机因素对问题影响较大,比如按最大比例算,与会人员可达678人。3、该模型的优点主要体现在: (1)、从建模总体来看,问题都是通过编程来解决的,这体现了数学建模的
17、科学合理性。 (2)、从建立的模型来看,更好运用了数形结合的思想,这样使得问题更清晰直观、易于理解。 4、模型的推广: 本文建立的模型是为了解决本届参加会议人员的住房、开会租客车的问题,此类模型也可以运用到酒店预定客房、旅行社租车及机场预定机票等问题上。同时,该模型同样适用于生活中其它方面路线的计算和预测,准确度较高,具有通用性。六、参考文献1 、全国大学生数学建模竞赛组委会,数学建模的实践:2006年全国大学生数 学建模夏令营论文集,北京:高等教育出版社(2007.8)。2 、袁新生等,LINGO和Excel在数学建模中的应用,北京:科学出版社(2007)。3 、晏林,数学与实验MATLAB
18、与QBASIC应用,北京:科学出版社(2005)。4 、谢金星,薛毅,优化建模与LINDO/LINGO软件,北京:清华大学出版社, (2005.7)。 5 、杨启帆,数学建模,北京:高等教育出版社(2005.5)。6 、熊义杰,运筹学教程,北京:国防工业出版社(2004.9)。7 、许承德,王勇,概率论与数理统计,北京:科学出版社(2001)。8 、王冬琳,数学建模及实验,北京:国防工业出版社(2004.5)。七、附录附录1附录2附录3程序运行结果如下:MODEL:MIN=600*X1+1500*X2+1000*X3+1500*X4+320*X5+800*X6+1000*X7+1200*X8+
19、300*X9;X1=2;X2=1;X3=2;X4=1;X5=3;X6=2;X7=1;X8=1;X9=661;X1+X2+X3+X4+X5+X6+X7+X8+X9=6;ENDGlobal optimal solution found. Objective value: 5600.000 Infeasibilities: 0.000000 Total solver iterations: 0 Variable Value Reduced Cost X1 0.000000 300.0000 X2 0.000000 0.000000 X3 0.000000 0.000000 X4 1.000000 0
20、.000000 X5 0.000000 20.00000 X6 2.000000 0.000000 X7 1.000000 0.000000 X8 1.000000 0.000000 X9 1.000000 0.000000 Row Slack or Surplus Dual Price 1 5600.000 -1.000000 2 2.000000 0.000000 3 1.000000 0.000000 4 2.000000 0.000000 5 0.000000 0.000000 6 3.000000 0.000000 7 0.000000 200.0000 8 0.000000 0.0
21、00000 9 0.000000 300.0000 10 2.000000 0.000000 11 0.000000 0.000000 12 0.000000 -1200.000 13 0.000000 -700.0000 14 4939.000 0.000000 15 0.000000 -300.0000附录4程序运行如下:MODEL:SETS:ITEMS /ITEM1,ITEM2,ITEM3/: INCLUDE,WEIGHT1,RATING;ENDSETSDATA: WEIGHT1=45,36,33; RATING=800 700 600; KNAPSACK1=237; ENDDATAmi
22、n=SUM(ITEMS:RATING*INCLUDE);SUM(ITEMS:WEIGHT1*INCLUDE)=KNAPSACK1;FOR(ITEMS:GIN(INCLUDE);ENDObjective value: 4300.000 Objective bound: 4300.000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost KNAPSACK1 237.0000 0.000000 INCLUDE( ITEM1) 3.00000
23、0 800.0000 INCLUDE( ITEM2) 1.000000 700.0000 INCLUDE( ITEM3) 2.000000 600.0000 WEIGHT1( ITEM1) 45.00000 0.000000 WEIGHT1( ITEM2) 36.00000 0.000000 WEIGHT1( ITEM3) 33.00000 0.000000 RATING( ITEM1) 800.0000 0.000000 RATING( ITEM2) 700.0000 0.000000 RATING( ITEM3) 600.0000 0.000000 Row Slack or Surplus
24、 Dual Price 1 4300.000 -1.000000 2 0.000000 0.000000附录5经济最优条件下租用客车的程序:model:min=800*x1+700*x2+600*x3+800*x4+700*x5+600*x6+800*x7+700*x8+600*x9+800*x10+700*x11+600*x12;45*x1+36*x2+33*x3=155;45*x4+36*x5+33*x6=79;45*x7+36*x8+33*x9=71;45*x10+36*x11+33*x12=104;45*x1+36*x2+33*x3+45*x4+36*x5+33*x6+45*x7+36
25、*x8+33*x9+45*x10+36*x11+33*x12=661;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);gin(x8);gin(x9);gin(x10);gin(x11);gin(12);end运行结果为: Global optimal solution found at iteration: 50 Objective value: 5700.00 Variable Value Reduced Cost X1 0.000000 800.0000 X2 0.000000 700.0000 X3 0.000000 600
26、.0000 X4 2.000000 800.0000 X5 0.000000 700.0000 X6 2.000000 600.0000 X7 1.000000 800.0000 X8 1.000000 700.0000 X9 0.000000 600.0000 X10 1.000000 -18.18182 X11 0.000000 45.45455 X12 1.000000 0.000000 Row Slack or Surplus Dual Price 1 5572.727 -1.000000 2 102.0000 0.000000 3 1.000000 0.000000 4 43.000
27、00 0.000000 5 2.000000 0.000000 6 93.00000 0.000000 7 0.000000 -18.18182 8 33.00000 0.000000 9 353.0000 0.000000附表1 10家备选宾馆的有关数据宾馆代号客房会议室规格间数价格(天)规模间数价格(半天)普通双标间50180元200人11500元商务双标间30220元150人21200元普通单人间30180元 60人2 600元商务单人间20220元普通双标间50140元130人21000元商务双标间35160元180人11500元豪华双标间A30180元 45人3 300元豪华双标间B
28、35200元 30人3 300元普通双标间50150元200人11200元商务双标间24180元100人2800元普通单人间27150元150人11000元60人3320元 普通双标间50140元150人2900元商务双标间45200元50人3300元普通双标间A35140元150人21000元普通双标间B35160元180人11500元豪华双标间40200元50人3 500元普通单人间40160元160人11000元普通双标间40170元180人11200元商务单人间30180元精品双人间30220元普通双标间50150元140人2 800元商务单人间40160元 60人3 300元商务套房
29、(1床)30300元200人11000元普通双标间A40180元160人11000元普通双标间B40160元130人2 800元高级单人间45180元普通双人间30260元160人11300元普通单人间30260元120人2800元豪华双人间30280元200人11200元豪华单人间30280元经济标准房(2床)55260元180人11500元标准房(2床)45280元140人21000元附表2 本届会议的代表回执中有关住房要求的信息(单位:人)合住1合住2合住3独住1独住2独住3男154104321076841女784817592819附表3 以往几届会议代表回执和与会情况第一届 第二届 第三届 第四届 发来回执的代表数量315356408711发来回执但未与会的代表数量89115121213未发回执而与会的代表数量576975104附图(其中500等数字是两宾馆间距,单位为米)(与间距300米) (与间距300米) (与间距300米) (与间距300米) (与间距300米) (与间距300米) (与间距300米) 1000500300150200300(与间距300米) (与间距300米) (与间距300米) 30070015014
限制150内