大学生数学建模竞赛D题讲解清华大学姜启源市公开课一等奖百校联赛特等奖课件.pptx

清华大学清华大学 姜启源姜启源 会会 议议 筹筹 备备全国大学生数学建模竞赛D题第1页 题目题目 题目标背景题目标背景 问题分析和处理方法问题分析和处理方法 一个参考解法一个参考解法 对学生论文评述对学生论文评述第2页 某市一家会议服务企业负责承接某专业领域一届全国性会议某市一家会议服务企业负责承接某专业领域一届全国性会议,会议筹备组要为与会代表预订宾馆客房会议筹备组要为与会代表预订宾馆客房,租借会议室租借会议室,并租用客车并租用客车接送代表。因为预计会议规模庞大接送代表。因为预计会议规模庞大,而适于接待这次会议几家宾馆而适于接待这次会议几家宾馆客房和会议室数量都有限客房和会议室数量都有限,所以只能让与会代表分散到若干家宾馆所以只能让与会代表分散到若干家宾馆住宿。住宿。为了便于管理为了便于管理,除了尽可能满足代表在价位等方面需求之外除了尽可能满足代表在价位等方面需求之外,所选择宾馆数量应该尽可能少所选择宾馆数量应该尽可能少,而且距离上比较靠近。而且距离上比较靠近。筹备组经过实地考查筹备组经过实地考查,筛选出筛选出10家宾馆作为备选家宾馆作为备选,它们名称用它们名称用代号代号至至表示表示,相对位置见附图相对位置见附图,相关客房及会议室规格、间数、相关客房及会议室规格、间数、价格等数据见附表价格等数据见附表1。依据这届会议代表回执整理出来相关住房信息见附表依据这届会议代表回执整理出来相关住房信息见附表2。从以。从以往几届会议情况看往几届会议情况看,有一些发往返执代表不来开会有一些发往返执代表不来开会,同时也有一些同时也有一些与会代表事先不提交回执与会代表事先不提交回执,相关数据见附表相关数据见附表3。附表。附表2,3都能够作为都能够作为预订宾馆客房参考。预订宾馆客房参考。题题 目目第3页 需要说明是，需要说明是，即使客房房费由与会代表自付，不过假如预即使客房房费由与会代表自付，不过假如预订客房数量大于实际用房数量，筹备组需要支付一天空房费，订客房数量大于实际用房数量，筹备组需要支付一天空房费，而若出现预订客房数量不足，则将造成非常被动局面，引发代而若出现预订客房数量不足，则将造成非常被动局面，引发代表不满。表不满。会议期间有一天上下午各安排会议期间有一天上下午各安排6个分组会议，筹备组需要在个分组会议，筹备组需要在代表下榻某几个宾馆租借会议室。因为代表下榻某几个宾馆租借会议室。因为事先无法知道哪些代表事先无法知道哪些代表准备参加哪个分组会，准备参加哪个分组会，筹备组还要向汽车租赁企业租用客车接筹备组还要向汽车租赁企业租用客车接送代表。现有送代表。现有45座、座、36座和座和33座三种类型客车，租金分别是半座三种类型客车，租金分别是半天天800元、元、700元和元和600元。元。请你们经过数学建模方法，从经济、方便、代表满意等方请你们经过数学建模方法，从经济、方便、代表满意等方面，为会议筹备组面，为会议筹备组制订一个预订宾馆客房、租借会议室、租用制订一个预订宾馆客房、租借会议室、租用客车合理方案。客车合理方案。第4页附表1 10家备选宾馆相关数据宾馆代号客房会议室规格间数价格(天)规模间数价格(半天)普通双标间50180元200人11500元商务双标间30220元150人21200元普通单人间30180元 60人2 600元商务单人间20220元 经济标准房(2床）55260元180人11500元标准房（2床）45280元140人21000元第5页附表2 本届会议代表回执中相关住房要求信息(单位：人)合住1合住2合住3独住1独住2独住3男154104321076841女784817592819附表3 以往几届会议代表回执和与会情况第一届 第二届 第三届 第四届 发往返执代表数量315356408711发往返执但未与会代表数量89115121213未发回执而与会代表数量576975104第6页1000500300150200300 300700150附图（其中附图（其中500等数字是两宾馆间距，单位为米）等数字是两宾馆间距，单位为米）第7页题目背景 8月第十一届全国数学建模教学与应用会议在福州召开。这是一次规模庞大系列性学术会议,据以往几届会议情况看,有以下共同、显著特点：与会代表多达数百人，而适于接待宾馆容量有限与会代表多达数百人，而适于接待宾馆容量有限,只只能让与会代表分散到若干家宾馆住宿；能让与会代表分散到若干家宾馆住宿；有一些发往返执代表不来开会有一些发往返执代表不来开会,也有一些与会代表事也有一些与会代表事先不提交回执先不提交回执,给预订宾馆客房数量造成了困难；给预订宾馆客房数量造成了困难；即使客房房费由与会代表自付即使客房房费由与会代表自付,但如预订客房数量大但如预订客房数量大于实际数量于实际数量,筹备组需要支付一天空房费筹备组需要支付一天空房费,而若预订而若预订客房数量不足客房数量不足,则将引发代表强烈不满；则将引发代表强烈不满；若内容不一样分组会分散在几个宾馆若内容不一样分组会分散在几个宾馆,而代表要参加而代表要参加哪个分组会无法预知哪个分组会无法预知,所以需要派车在宾馆间接送代表。所以需要派车在宾馆间接送代表。第8页 一些会议筹备者和宾馆管理人员反应一些会议筹备者和宾馆管理人员反应,诸如上述这些诸如上述这些情况普遍存在、时常发生。情况普遍存在、时常发生。经过数学建模方法经过数学建模方法,从经济、方便、代表满意等方面从经济、方便、代表满意等方面,为会议筹备者制订一个预订宾馆客房、租借会议室、租为会议筹备者制订一个预订宾馆客房、租借会议室、租用客车合理方案用客车合理方案,是非常现实且很有实际意义课题是非常现实且很有实际意义课题,而而且这方面研究过去几乎没有。且这方面研究过去几乎没有。为了保持问题原汁原味为了保持问题原汁原味,赛题中所列赛题中所列10家宾馆基本家宾馆基本数据和相对位置数据和相对位置,以及本届会议代表回执中相关住房以及本届会议代表回执中相关住房要求信息都是真实要求信息都是真实,只是对一些宾馆客房和会议室数只是对一些宾馆客房和会议室数量略作改动。关于前几届会议代表回执和与会情况也量略作改动。关于前几届会议代表回执和与会情况也基本上参考了历史数据。基本上参考了历史数据。题目背景 第9页问题分析和处理方法问题分析和处理方法 从题目要求出发，主要需要处理三个问题：从题目要求出发，主要需要处理三个问题：1）预测本届会议与会代表数量）预测本届会议与会代表数量,并确定需要预并确定需要预订各类客房数量；订各类客房数量；2）确定在哪些宾馆预订客房及预订各类客房数）确定在哪些宾馆预订客房及预订各类客房数量；量；3）确定在哪些宾馆预订哪些类型会议室以及租）确定在哪些宾馆预订哪些类型会议室以及租车规格和数量。车规格和数量。第10页 问题问题1是求解问题是求解问题2，3前提，首先应该依据附表前提，首先应该依据附表2，3数据对本届会议数据对本届会议与会代表数量与会代表数量进行预测。进行预测。确定预订确定预订客房总量客房总量时，应使会议筹备组在订房上损时，应使会议筹备组在订房上损失尽可能小，损失包含：预订客房数超出实际用量时失尽可能小，损失包含：预订客房数超出实际用量时需要支付一天空房费；预订客房数不够时引发代表不需要支付一天空房费；预订客房数不够时引发代表不满满“费用费用”，后者要用适当数学表示式加以量化。，后者要用适当数学表示式加以量化。依据附表依据附表2数据中本届会议代表所需要数据中本届会议代表所需要6种类型客房种类型客房百分比，可由预订客房总量得到预定百分比，可由预订客房总量得到预定各类客房数量各类客房数量。问题分析和处理方法问题分析和处理方法第11页 问题问题2主要主要应应考考虑虑筹筹备组备组管理方便及代表管理方便及代表满满意，如意，如满满足代表在合住或独住及价位方面需求、足代表在合住或独住及价位方面需求、预订宾馆预订宾馆总总数尽可能少、距离上尽可能靠近等。数尽可能少、距离上尽可能靠近等。若建立优化模型，能够用宾馆总数最少为若建立优化模型，能够用宾馆总数最少为目标函目标函数数，以满足代表在合住或独住及价位方面需求，及，以满足代表在合住或独住及价位方面需求，及各宾馆拥有客房数量等为各宾馆拥有客房数量等为约束条件约束条件，以在哪几家宾，以在哪几家宾馆订房及各类客房订多少间为馆订房及各类客房订多少间为决议变量决议变量。以宾馆总数最少为目标优化模型其最优解普通不以宾馆总数最少为目标优化模型其最优解普通不唯一，能够再考虑宾馆间距离、客房价格等原因，唯一，能够再考虑宾馆间距离、客房价格等原因，从几个解中选出相对很好一个。从几个解中选出相对很好一个。问题分析和处理方法问题分析和处理方法第12页 问题问题3主要应考虑租用会议室和客车总费用尽可能小、主要应考虑租用会议室和客车总费用尽可能小、会议室所在宾馆总数尽可能少、距离上尽可能靠近等。会议室所在宾馆总数尽可能少、距离上尽可能靠近等。租车要考虑多少代表参加哪个分组会议租车要考虑多少代表参加哪个分组会议,题目中没有题目中没有这方面信息这方面信息,能够按照能够按照平均、随机平均、随机方式处理。方式处理。当建立优化模型时当建立优化模型时,可用租借会议室和客车总费用最可用租借会议室和客车总费用最少为目标函数少为目标函数,以满足对会议室数量、大小及租车需要以满足对会议室数量、大小及租车需要为约束条件为约束条件,以租用会议室和车辆规格、数量为决议变以租用会议室和车辆规格、数量为决议变量。量。将问题将问题2,3统一建立模型并求解有一定困难统一建立模型并求解有一定困难,可可在问在问题题2几个解基础上解问题几个解基础上解问题3，经过比较得出最终结果。，经过比较得出最终结果。问题分析和处理方法问题分析和处理方法第13页一个参考解法一个参考解法设有设有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.1.预测本届会议与会代表数量预测本届会议与会代表数量 确定需要预订各类客房数量确定需要预订各类客房数量emean，emax第14页 建立建立di对对ai回归模型回归模型用线性模型预测本届会议用线性模型预测本届会议与会代表数量与会代表数量 N=638确定预订客房总量确定预订客房总量 考虑两种可能损失：空房费；代表不满量化考虑两种可能损失：空房费；代表不满量化“费用费用”适当提升预测与会代表数量适当提升预测与会代表数量 对对未未发发回回执执而与会代表另作安排而与会代表另作安排 参考参考“航空企航空企业预订业预订票策略票策略”模型模型（姜启源等：数学模型（第三版）第（姜启源等：数学模型（第三版）第284页页1.1.预测本届会议与会代表数量预测本届会议与会代表数量 确定需要预订各类客房数量确定需要预订各类客房数量第15页1.1.预测本届会议与会代表数量预测本届会议与会代表数量 确定需要预订各类客房数量确定需要预订各类客房数量预订客房总量预订客房总量本届会议要求合住、独住各本届会议要求合住、独住各s(=3)种价位种价位(类型类型)代表数量及所占百代表数量及所占百分比分比(合住考虑性别合住考虑性别)预订各类客房数量预订各类客房数量需要预订合住第需要预订合住第j种类型客房数量种类型客房数量T1j需要预订独住第需要预订独住第j种类型客房数量种类型客房数量T2j第第i家宾馆第家宾馆第j种类型单人房种类型单人房(独住独住)能提供间数能提供间数C2ij 第第i家宾馆第家宾馆第j种类型双人房种类型双人房(合住或独住合住或独住)能提供间数能提供间数C1ij第16页2.2.确定在哪些宾馆预订客房及预订各类客房数量确定在哪些宾馆预订客房及预订各类客房数量 以宾馆总数最少为目标，以满足代表在合住、独以宾馆总数最少为目标，以满足代表在合住、独住及价位方面需求，及各宾馆拥有客房数量等为约住及价位方面需求，及各宾馆拥有客房数量等为约束条件，建立束条件，建立优化模型优化模型.预订第预订第i家宾馆第家宾馆第j种类型单人房种类型单人房(独住独住)间数间数 x2ij 预订第预订第i家宾馆第家宾馆第j种类型双人房种类型双人房(合住合住)间数间数 x1ij预订第预订第i家宾馆第家宾馆第j种类型双人房种类型双人房(改独住改独住)间数间数 yij决议变量决议变量第第i家宾馆选择变量家宾馆选择变量 ki(ki=0,1)设共有设共有r家宾馆双人、单人房各家宾馆双人、单人房各s种类型种类型第17页目标函数目标函数约束条件约束条件满足需求满足需求满足供给满足供给2.2.确定在哪些宾馆预订客房及预订各类客房数量确定在哪些宾馆预订客房及预订各类客房数量第18页求解整数规划模型求解整数规划模型（LINGO）最优解普通不唯一，可得到多个解最优解普通不唯一，可得到多个解可考虑距离原因、价格原因等确定最终方案可考虑距离原因、价格原因等确定最终方案或者在这些解基础上进入下一步，依据租或者在这些解基础上进入下一步，依据租借会议室和租车情况确定最终方案借会议室和租车情况确定最终方案.2.2.确定在哪些宾馆预订客房及预订各类客房数量确定在哪些宾馆预订客房及预订各类客房数量第19页3.3.确定在哪些宾馆预订哪些类型会议室确定在哪些宾馆预订哪些类型会议室 以及租车规格和数量以及租车规格和数量预订会议室标准：预订会议室标准：每个会议室容量最少为与会总人数每个会议室容量最少为与会总人数1/6 会议室位于预订客房宾馆内会议室位于预订客房宾馆内租车标准：租车标准：与会总人数与会总人数1/6代表不需接送代表不需接送 宾馆距离在一定范围内代表不需接送宾馆距离在一定范围内代表不需接送 一辆车每次会议最多接送一辆车每次会议最多接送2趟趟以会议室和客车租费最小为目标建立优化模型求解以会议室和客车租费最小为目标建立优化模型求解第20页对学生论文评述对学生论文评述 基本情况基本情况 绝大多数同学都能依据对问题了解和掌握数学知识，绝大多数同学都能依据对问题了解和掌握数学知识，给出处理问题方法，并得到所要求结果。给出处理问题方法，并得到所要求结果。不少同学建立了在课堂上没有学过数学规划模型，并不少同学建立了在课堂上没有学过数学规划模型，并用数学软件求解用数学软件求解.对于高职高专学生来说，不论从题型还是所用数学对于高职高专学生来说，不论从题型还是所用数学知识都是适合。知识都是适合。在处理主要问题之前，都做了一些准备工作，如按照在处理主要问题之前，都做了一些准备工作，如按照代表对住房类型、价位需求将各宾馆客房分类整理，将代表对住房类型、价位需求将各宾馆客房分类整理，将宾馆按照能满足代表需求多少排列，并事先排除几个满宾馆按照能满足代表需求多少排列，并事先排除几个满足需求较少、价位又高宾馆。足需求较少、价位又高宾馆。第21页 多数同学先确定在哪些宾馆预订客房及其数量，多数同学先确定在哪些宾馆预订客房及其数量，再在此条件下确定租用会议室和客车方案。再在此条件下确定租用会议室和客车方案。有先确定在哪些宾馆租借会议室，再预订客房。有先确定在哪些宾馆租借会议室，再预订客房。还有将宾馆总数最少和宾馆间距离最短结合起来，还有将宾馆总数最少和宾馆间距离最短结合起来，建立双目标规划模型。建立双目标规划模型。一些同学用分析方法先排除一些宾馆一些同学用分析方法先排除一些宾馆,或是依次在一或是依次在一些宾馆安排代表些宾馆安排代表(先安排容纳人多先安排容纳人多),即使得到结果不即使得到结果不错错,但偏向于经验但偏向于经验,从数学建模角度来说不提倡。从数学建模角度来说不提倡。给出客车在宾馆之间接送代表详细方法给出客车在宾馆之间接送代表详细方法,如行车路线、如行车路线、始发地和目标地始发地和目标地,中途经什么宾馆等，值得勉励。中途经什么宾馆等，值得勉励。基本情况基本情况 第22页存在问题存在问题 1）预测本届会议与会代表数量时，用往届实际到会）预测本届会议与会代表数量时，用往届实际到会人数对发往返执人数回归模型，若用线性或二次模型，人数对发往返执人数回归模型，若用线性或二次模型，结果通常偏低，如不加调整，会有问题。结果通常偏低，如不加调整，会有问题。还有建立实际到会还有建立实际到会人数关于人数关于以往会议届以往会议届数数回归模型。回归模型。对学生论文评述对学生论文评述显著错误！显著错误！第23页2）在用）在用百分比法百分比法预测预测本届会本届会议议与会代表数量与会代表数量时时，取，取第第i届届与会代表占与会代表占发发往返往返执执数量百分比数量百分比ei=di/ai平均值，平均值，没有没有考考虑预订虑预订客房数不客房数不够实际够实际用量用量时时引引发发代表不代表不满满造造成成损损失，未失，未给预测值给预测值留出余量。留出余量。个个别别同学同学这这么么计计算算ei=di/ai平均值：平均值：3）题目中已明确说明客房房费由与会代表自付）题目中已明确说明客房房费由与会代表自付,筹备筹备组只需满足代表对住房价位类型需求。组只需满足代表对住房价位类型需求。客房价格不应客房价格不应成为优化目标成为优化目标,而只能是兼顾原因。而只能是兼顾原因。一些同学没有完全把握这些要求，过分注意了客房一些同学没有完全把握这些要求，过分注意了客房价位，而对空房费和不满引发价位，而对空房费和不满引发“费用费用”关注不够。关注不够。存在问题存在问题第24页4）将宾馆间距离最短作为优化一个目标）将宾馆间距离最短作为优化一个目标,有其合理性有其合理性,但很多是先但很多是先选定一家宾馆选定一家宾馆(比如处于中心位置比如处于中心位置),以其以其它宾馆与其距离之和最短为标准它宾馆与其距离之和最短为标准,来预订客房。来预订客房。对于本题所给数据能够得到合理结果对于本题所给数据能够得到合理结果,不过这种方法不过这种方法不具普遍性不具普遍性,因为不能排除有另外几个宾馆因为不能排除有另外几个宾馆(不包含上不包含上面选定面选定)也能满足代表需求也能满足代表需求,且其它指标更优。且其它指标更优。5）题目说明是上下午各安排）题目说明是上下午各安排6个分组会议，而且事先个分组会议，而且事先无法知道哪些代表准备参加哪个分组会。无法知道哪些代表准备参加哪个分组会。一些同学了解为各个分组会内容相同一些同学了解为各个分组会内容相同,于是只要求于是只要求6个会议室个会议室总容量总容量大于与会人数。还有认为上下午会议内大于与会人数。还有认为上下午会议内容相同，于是上下午容相同，于是上下午各只安排总数二分之一各只安排总数二分之一即可。即可。存在问题存在问题第25页6）考虑租车方案时）考虑租车方案时,假如在假设中说明宾馆距离不远假如在假设中说明宾馆距离不远就不用接送就不用接送,及每辆车可接送两个往返等及每辆车可接送两个往返等,当然能够。当然能够。但假如要求不接送距离太远但假如要求不接送距离太远,或只租用一两辆车或只租用一两辆车,在在各宾馆间各宾馆间往返屡次往返屡次地接送，就不符合实际了。地接送，就不符合实际了。还有些同学没有考虑会有还有些同学没有考虑会有1/6代表留在其下榻宾馆代表留在其下榻宾馆所在会议室开会，不需要迁移。所在会议室开会，不需要迁移。7）层次分析法层次分析法惯用于确定不易量化原因对一些目标权惯用于确定不易量化原因对一些目标权重，用于本题只能起不大辅助作用，用它对宾馆进行重，用于本题只能起不大辅助作用，用它对宾馆进行排序或评定，是不恰当。排序或评定，是不恰当。8）许多同学在数学符号、公式表述上）许多同学在数学符号、公式表述上,存在不严格、存在不严格、不规范不规范,甚至错误之处甚至错误之处,以下标不注明含义以下标不注明含义,求和号不求和号不注明求和范围注明求和范围,甚至整个数学符号都不给出定义。甚至整个数学符号都不给出定义。存在问题存在问题第26页 近年赛题近年赛题 题目标特点题目标特点 征集题目素材征集题目素材第27页年份年份A题题B题题C题题D题题SARS传输露天矿生产车辆安排SARS传输抢渡长江抢渡长江奥运会暂时超市网点设计电力市场输电阻塞管理饮酒驾车饮酒驾车公务员招聘公务员招聘长江水质评价和预测DVD在线租赁在线租赁雨量预报方法评价DVD在线租在线租赁赁出版社资源配置艾滋病疗法评价和疗效预测易拉罐形状和尺寸最优设计煤矿瓦斯和煤尘监测与控制中国人口增加预测 乘公交，看奥乘公交，看奥运运手机手机“套餐套餐”优惠几何优惠几何 体能测试时体能测试时间安排间安排 数码相机定位数码相机定位高等教育收费高等教育收费标准探讨标准探讨地面搜索地面搜索NBA赛程分析与评价制动器试验台控制方法分析眼科病床合理安排卫星和飞船跟踪测控会议筹备会议筹备第28页题目特点题目起源题目起源:实际研究课题简化、改编；有实际背景实际研究课题简化、改编；有实际背景问题编撰；适当社会热点（或兴趣）问题问题编撰；适当社会热点（或兴趣）问题题目背景尽可能通俗易懂，包括专业知识不深题目背景尽可能通俗易懂，包括专业知识不深题目需要数学知识普通不超出本科三门主干课题目需要数学知识普通不超出本科三门主干课（非数学专业）内容及统计、优化、计算等基本方（非数学专业）内容及统计、优化、计算等基本方法；专科题目力争少用大学数学内容法；专科题目力争少用大学数学内容解题所用数学方法尽可能多元化、综合化解题所用数学方法尽可能多元化、综合化能够查阅到一些参考材料，不过无法照搬现成文件能够查阅到一些参考材料，不过无法照搬现成文件兼顾数据处理与数据搜集兼顾数据处理与数据搜集第29页征集题目素材征集题目素材1.题目背景（如实际课题简化，社会关心问题，有实题目背景（如实际课题简化，社会关心问题，有实际背景问题等）；际背景问题等）；2.要学生处理主要问题；要学生处理主要问题；3.假如需要提供（或让学生搜集）数据，指出能够得假如需要提供（或让学生搜集）数据，指出能够得到数据起源；到数据起源；4.网上相关资料大致情况。网上相关资料大致情况。第30页谢谢大家谢谢大家!扩大受益面、确保公正性、促进教学改革扩大受益面、确保公正性、促进教学改革提升质量、推进科研、走向世界提升质量、推进科研、走向世界大学生数学建模竞赛大学生数学建模竞赛第31页