数学建模竞赛2009年D题姜启源讲解

清华大学姜启源[e-mail]会议筹备全国大学生数学建模竞赛2009年D题•题目•题目的背景•问题分析和解决方法•一种参考解法•对学生论文的评述某市的一家会议服务公司负责承办某专业领域的一届全国性会议,会议筹备组要为与会代表预订宾馆客房,租借会议室,并租用客车接送代表。由于预计会议规模庞大,而适于接待这次会议的几家宾馆的客房和会议室数量均有限,所以只能让与会代表分散到若干家宾馆住宿。为了便于管理,除了尽量满足代表在价位等方面的需求之外,所选择的宾馆数量应该尽可能少,并且距离上比较靠近。筹备组经过实地考察,筛选出10家宾馆作为备选,它们的名称用代号①至⑩表示,相对位置见附图,有关客房及会议室的规格、间数、价格等数据见附表1。根据这届会议代表回执整理出来的有关住房的信息见附表2。从以往几届会议情况看,有一些发来回执的代表不来开会,同时也有一些与会的代表事先不提交回执,相关数据见附表3。附表2,3都可以作为预订宾馆客房的参考。题目需要说明的是，虽然客房房费由与会代表自付，但是如果预订客房的数量大于实际用房数量，筹备组需要支付一天的空房费，而若出现预订客房数量不足，则将造成非常被动的局面，引起代表的不满。会议期间有一天的上下午各安排6个分组会议，筹备组需要在代表下榻的某几个宾馆租借会议室。由于事先无法知道哪些代表准备参加哪个分组会，筹备组还要向汽车租赁公司租用客车接送代表。现有45座、36座和33座三种类型的客车，租金分别是半天800元、700元和600元。请你们通过数学建模方法，从经济、方便、代表满意等方面，为会议筹备组制定一个预订宾馆客房、租借会议室、租用客车的合理方案。附表110家备选宾馆的有关数据宾馆代号客房会议室规格间数价格(天)规模间数价格(半天)①普通双标间50180元200人11500元商务双标间30220元150人21200元普通单人间30180元60人2600元商务单人间20220元………………⑩经济标准房(2床）55260元180人11500元标准房（2床）45280元140人21000元附表2本届会议的代表回执中有关住房要求的信息(单位：人)合住1合住2合住3独住1独住2独住3男154104321076841女784817592819附表3以往几届会议代表回执和与会情况第一届第二届第三届第四届发来回执的代表数量315356408711发来回执但未与会的代表数量89115121213未发回执而与会的代表数量576975104⑤⑦⑧②④③1000500300150200300⑨⑥⑩300700150①附图（其中500等数字是两宾馆间距，单位为米）题目的背景2009年8月第十一届全国数学建模教学与应用会议在福州召开。这是一次规模庞大的系列性学术会议,据以往几届会议的情况看,有以下共同的、明显的特点：•与会代表多达数百人，而适于接待的宾馆容量有限,只能让与会代表分散到若干家宾馆住宿；•有一些发来回执的代表不来开会,也有一些与会代表事先不提交回执,给预订宾馆客房数量造成了困难；•虽然客房房费由与会代表自付,但如预订客房数量大于实际数量,筹备组需要支付一天的空房费,而若预订客房数量不足,则将引起代表的强烈不满；•若内容不同的分组会分散在几个宾馆,而代表要参加哪个分组会无法预知,因此需要派车在宾馆间接送代表。一些会议的筹备者和宾馆的管理人员反映,诸如上述这些情况普遍存在、时常发生。通过数学建模方法,从经济、方便、代表满意等方面,为会议筹备者制定一个预订宾馆客房、租借会议室、租用客车的合理方案,是非常现实且很有实际意义的课题,并且这方面的研究过去几乎没有。为了保持问题的原汁原味,赛题中所列10家宾馆的基本数据和相对位置,以及本届会议代表回执中有关住房要求的信息都是真实的,只是对一些宾馆客房和会议室的数量略作改动。关于前几届会议的代表回执和与会情况也基本上参考了历史数据。题目的背景问题分析和解决方法从题目要求出发，主要需要解决三个问题：1）预测本届会议与会代表的数量,并确定需要预订各类客房的数量；2）确定在哪些宾馆预订客房及预订各类客房的数量；3）确定在哪些宾馆预订哪些类型的会议室以及租车的规格和数量。问题1是求解问题2，3的前提，首先应该根据附表2，3的数据对本届会议与会代表的数量进行预测。确定预订客房总量时，应使会议筹备组在订房上的损失尽量小，损失包括：预订客房数超过实际用量时需要支付的一天空房费；预订客房数不够时引起代表不满的“费用”，后者要用适当的数学表达式加以量化。根据附表2数据中本届会议的代表所需要6种类型的客房的比例，可由预订客房的总量得到预定各类客房的数量。问题分析和解决方法问题2主要应考虑筹备组管理的方便及代表的满意，如满足代表在合住或独住及价位方面的需求、预订的宾馆总数尽量少、距离上尽量靠近等。若建立优化模型，可以用宾馆总数最少为目标函数，以满足代表在合住或独住及价位方面的需求，及各宾馆拥有客房数量等为约束条件，以在哪几家宾馆订房及各类客房订多少间为决策变量。以宾馆总数最少为目标的优化模型其最优解一般不唯一，可以再考虑宾馆间的距离、客房价格等因素，从几个解中选出相对较好的一个。问题分析和解决方法问题3主要应考虑租用会议室和客车的总费用尽量小、会议室所在的宾馆总数尽量少、距离上尽量靠近等。租车要考虑多少代表参加哪个分组会议,题目中没有这方面的信息,可以按照平均的、随机的方式处理。当建立优化模型时,可用租借会议室和客车的总费用最少为目标函数,以满足对会议室数量、大小及租车的需要为约束条件,以租用会议室和车辆的规格、数量为决策变量。将问题2,3统一建立模型并求解有一定困难,可在问题2几个解的基础上解问题3，通过比较得出最后结果。问题分析和解决方法一种参考解法设有n届同类型会议的历史数据可利用(n较小,本题n=4)第i届发来回执的代表数量ai第i届发来回执但未与会的代表数量bi第i届未发回执而与会的代表数量ci本届发来回执数量A第i届与会代表数量di=ai-bi+ci第i届与会代表占发来回执数量的比例ei=di/ai预测本届会议与会代表数量Nmean=AemeanNmax=Aemax=661=678•比例法预测1.预测本届会议的与会代表数量确定需要预订各类客房的数量emean，emax300350400450500550600650700750250300350400450500550600650•建立di对ai的回归模型用线性模型预测本届会议与会代表数量N=638确定预订客房的总量考虑两种可能的损失：空房费；代表不满的量化“费用”•适当提高预测的与会代表数量•对未发回执而与会的代表另作安排•参考“航空公司的预订票策略”模型（姜启源等：《数学模型（第三版）第284页》1.预测本届会议的与会代表数量确定需要预订各类客房的数量1.预测本届会议的与会代表数量确定需要预订各类客房的数量预订客房的总量本届会议要求合住、独住各s(=3)种价位(类型)代表数量及所占比例(合住考虑性别)预订各类客房的数量需要预订合住第j种类型客房数量T1j需要预订独住第j种类型客房数量T2j第i家宾馆第j种类型单人房(独住)能提供的间数C2ij第i家宾馆第j种类型双人房(合住或独住)能提供的间数C1ij2.确定在哪些宾馆预订客房及预订各类客房的数量以宾馆总数最少为目标，以满足代表在合住、独住及价位方面的需求，及各宾馆拥有客房数量等为约束条件，建立优化模型.预订第i家宾馆第j种类型单人房(独住)间数x2ij预订第i家宾馆第j种类型双人房(合住)间数x1ij预订第i家宾馆第j种类型双人房(改独住)间数yij决策变量第i家宾馆的选择变量ki(ki=0,1)设共有r家宾馆双人、单人房各s种类型目标函数riikz1min约束条件sjTyxkjijriiji,,2,1,)(212sjTxkjriiji,,2,1,111满足需求sjriCyxijijij,,2,1;,,2,1,11sjriCxijij,,2,1;,,2,1,22满足供给2.确定在哪些宾馆预订客房及预订各类客房的数量求解整数规划模型（LINGO）最优解一般不唯一，可得到多个解可考虑距离因素、价格因素等确定最终方案或者在这些解的基础上进入下一步，根据租借会议室和租车情况确定最终方案.2.确定在哪些宾馆预订客房及预订各类客房的数量3.确定在哪些宾馆预订哪些类型的会议室以及租车的规格和数量预订会议室的原则：•每个会议室的容量至少为与会总人数的1/6•会议室位于预订客房的宾馆内租车的原则：•与会总人数1/6的代表不需接送•宾馆距离在一定范围内的代表不需接送•一辆车每次会议最多接送2趟以会议室和客车的租费最小为目标建立优化模型求解对学生论文的评述基本情况•绝大多数同学都能根据对问题的理解和掌握的数学知识，给出解决问题的方法，并得到所要求的结果。•不少同学建立了在课堂上没有学过的数学规划模型，并用数学软件求解.•对于高职高专学生来说，无论从题型还是所用的数学知识都是适合的。•在解决主要问题之前，都做了一些准备工作，如按照代表对住房类型、价位的需求将各宾馆的客房分类整理，将宾馆按照能满足代表需求的多少排列，并事先排除几个满足需求较少、价位又高的宾馆。•多数同学先确定在哪些宾馆预订客房及其数量，再在此条件下确定租用会议室和客车的方案。•有的先确定在哪些宾馆租借会议室，再预订客房。•还有的将宾馆总数最少和宾馆间的距离最短结合起来，建立双目标规划模型。•一些同学用分析方法先排除一些宾馆,或是依次在某些宾馆安排代表(先安排容纳人多的),虽然得到的结果不错,但偏向于经验,从数学建模的角度来说不提倡。•给出客车在宾馆之间接送代表的具体办法,如行车路线、始发地和目的地,中途经什么宾馆等，值得鼓励。基本情况存在的问题1）预测本届会议的与会代表数量时，用往届实际到会人数对发来回执人数的回归模型，若用线性或二次模型，结果通常偏低，如不加调整，会有问题。11.522.533.54250300350400450500550600650还有的建立实际到会人数关于以往会议届数的回归模型。对学生论文的评述明显错误！2）在用比例法预测本届会议的与会代表数量时，取第i届与会代表占发来回执数量的比例ei=di/ai的平均值，没有考虑预订客房数不够实际用量时引起代表不满造成的损失，未给预测值留出余量。iiiiad/个别同学这样计算ei=di/ai的平均值：3）题目中已明确说明客房房费由与会代表自付,筹备组只需满足代表对住房价位类型的需求。客房价格不应成为优化的目标,而只能是兼顾的因素。一些同学没有完全把握这些要求，过分注意了客房价位，而对空房费和不满引起的“费用”关注不够。存在的问题4）将宾馆间距离最短作为优化的一个目标,有其合理性,但很多是先选定一家宾馆(比如处于中心位置的),以其他宾馆与其距离之和最短为标准,来预订客房。对于本题所给数据可以得到合理的结果,但是这种方法不具普遍性,因为不能排除有另外几个宾馆(不包含上面选定的)也能满足代表的需求,且其他指标更优。5）题目说明是上下午各安排6个分组会议，并且事先无法知道哪些代表准备参加哪个分组会。一些同学理解为各个分组会内容相同,于是只要求6个会议室的总容量大于与会人数。还有的认为上下午会议内容相同，于是上下午各只安排总数的一半即可。存在的问题6）考虑租车方案时,如果在假设中说明宾馆距离不远就不用接送,及每辆车可接送两个来回等,当然可以。但如果规定不接送的距离太远,或只租用一两辆车,在各宾馆间来回多次地接送，就不符合实际了。还有些同学没有考虑会有1/6的代表留在其下榻宾馆所在的会议室开会，不需要迁移。7）层次分析法常用于确定不易量化的因素对某些目标的权重，用于本题只能起不大的辅助作用，用它对宾馆进行排序或评估，是不恰当的。8）许多同学在数学符号、公式的表述上,存在不严格、不规范,甚至错误之处,如下标不注明含义,求和号不注明求和范围,甚至整个数学符号都不给出定义。存在的问题•近年的赛题•题目的特点•征