高教社杯全国大学生数学
建模竞赛d题
Prepared on 22 November 2020
2009高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则 .
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题 .
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出 .
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性 .如有违反竞赛规则的行为，我们将受到严肃处理 .
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： D 我们的参赛报名号为（如果赛区设置报名号的话）：
所属学校（请填写完整的全名）： XXXXXX
参赛队员 (打印并签名) ：1 . XXXXX
2 . XXXXX
3 .
指导教师或指导教师组负责人 (打印并签名)： XXXXXX
日期：2009年 9 月 14日赛区评阅编号（由赛区组委会评阅前进行编号）：
2009高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号（由赛区组委会评阅前进行编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
会议筹备最优化
一.摘要
在激烈的市场竞争中,随着市场经济在中国大陆的不断发展，各种新兴行业也在悄然而起 .会议服务公司通过对宾馆客房、租借会议室、租用客车接送代表等几块服务，让顾客觉得经济、方便同时使满意度达到最高，会议服务公司需要从公司的经济利益和社会声誉等诸多因素来考虑,在此,我们运用线性规划和概率统计的知识，来解决对宾馆客房分配问题 .会议的经济安排从预定房间的量和安排的合理性来决定;在安排客车接送会议代表运用运筹学分成几条路线;服务公司的社会声誉在市场竞争中是非常重要的,在此我们用会议代表对总体的满意度来衡量．我们应用概率统计的知识，得出参加会议人员大约为661人 .根据与会人员对住房的要求，我们设计了第一个模型，且有3个方案，第一个方案利用Lingo软件计算得其无解，同样利用Lingo软件计算得最优解.通过调整第一类单人间住房的人数建立模型二，得出所有与会代表住房安排，此时得出住房费的最少价格为80630元 .对模型二进一步优化，通过对宾馆调整，把与会代表集中按排在①、②、⑤、⑥、⑦、⑧、⑨宾馆 .利用“中心极限”定理，计算得出可能出现空床费赔偿的概率大约是12%.同样应用“中心地址”的算法确定开会会议宾馆定为⑦、⑧宾馆 .用运筹学的知识确定出接送与会代表路线，并安排出了接
送的车辆类型和数量
关键词：线性规划概率统计 Lingo 中心地址运筹学
二.问题重述
某市的一家会议服务公司负责承办某专业领域的一届全国性会议，会议筹备组要为与会代表预订宾馆客房，租借会议室，并租用客车接送代表 .由于预计会议规模庞大，而适于接待这次会议的几家宾馆的客房和会议室数量均有限，所以只能让与会代
表分散到若干家宾馆住宿 .为了便于管理，除了尽量满足代表在价位等方面的需求之外，所选择的宾馆数量应该尽可能少，并且距离上比较靠近 .
筹备组经过实地考察，筛选出10家宾馆作为备选，它们的名称用代号①至⑩表示，相对位置见附图，有关客房及会议室的规格、间数、价格等数据见附表1 .
根据这届会议代表回执整理出来的有关住房的信息见附表2 .从以往几届会议情况看，有一些发来回执的代表不来开会，同时也有一些与会的代表事先不提交回执，相关数据见附表3 .附表2，3都可以作为预订宾馆客房的参考 .
需要说明的是，虽然客房房费由与会代表自付，但是如果预订客房的数量大于实际用房数量，筹备组需要支付一天的空房费，而若出现预订客房数量不足，则将造成非常被动的局面，引起代表的不满 .
会议期间有一天的上下午各安排6个分组会议，筹备组需要在代表下榻的某几个宾馆租借会议室 .由于事先无法知道哪些代表准备参加哪个分组会，筹备组还要向汽车租赁公司租用客车接送代表 .现有45座、36座和33座三种类型的客车，租金分别是半天800元、700元和600元 .
我们通过数学建模方法，从经济、方便、代表满意等方面，为会议筹备组制定一个预订宾馆客房、租借会议室、租用客车的合理方案 .
附表1 10家备选宾馆的有关数据
附表2 本届会议的代表回执中有关住房要求的信息（单位：人）
说明：表头第一行中的数字1、2、3分别指每天每间120~160元、161~200元、201~300元三种不同价格的房间 .合住是指要求两人合住一间 .独住是指可安排单人间，或一人单独住一个双人间 .
附表3 以往几届会议代表回执和与会情况
附图(其中500等数字是两宾馆的距离)
三.模型假设
1.假设模型一中满足所有与会代表的回执要求；
2.假设与会代表参加每组会议是随机的；
3. 假设本届与会代表参加会议人数服从往届参加会议人数规律；
4. 假设每个与会代表每半天只开一次会议，且会议地点相同；
5. 假设每半天所开会议的主题都一致；
7．假设每条路线车辆只搭载同一条路线的与会代表 .
四. 符号说明
ij x 为第i 个宾馆所住的与会代表的第j 种类型住房人数；
p 为参加会议人数的总频率；
)(i a p 为回执且与会代表的频率（i 取1，2，3，4）；
)(i b p 为未回执且与会代表的比例（i 取1，2，3，4）；
M 为找宾馆中心地址问题的矩阵；
abc x 表示a 宾馆到b 宾馆c 会议室的与会人数 .
五．建立与分析
模型一：
通过观察附表2可以得到本届回执人数总共为755人，由往届会议代表的回执和与会情况可得知本届与会人数的概率p .因此我们假定模型如下：
设p 为与会的总频率
)(i a p 为回执且与会的频率（i 取1，2，3，4）
)(i b p 为未回执且与会的比例（i 取1，2，3，4）
与会人数的频率：()()b p a p p +=
有回执且与会人数的频率)(i a p
未回执且与会人数的比例()i b p
通过以往一、二、三、四会议代表回执和与会情况，利用统计分析法，可计算出以往几届参加会议人数的的平均概率，通过平均概率推算本届与会代表的总人数 .
本届与会人数：
为了使预定的房间数达到最优，使得空房数量最小，支付空房会达到最小优化 .我们以661人来进行预定房间，我们假设有三种方案 .
方案一:我们为了满足各代表的要求,且达到经济，结合表一:
表一
利用表一我们建立模型并求解
约束条件：
单人间：
两人间：
.
运用计算机计算出结果，并对解进行数据分析发现方案一无解 .
x在约束条件下则不因为第一种价格范围的单间数和与会人员的回执信息矛盾 .例如
61
能满足与会人员的要求 .
宾馆61x 的单间数在代表要求的房间数数量上不能满足,则我们在考虑到经济和尽量使与会代表满意的情况下,建议代表住双人间,即方案二:将61x 的118人在满足了40人之后,考虑到与会人员对宾馆的品质要求 .把剩下的78名分到91x 和93x ,这样在品质要求方面让与会人员达到最大的满意，建立模型:
约束条件：
单人间：
两人间：
.
运用计算机软件计算，计算结果见附录表一，并对解进行数据分析。
在尽量使与会代表满意同时使经济可以接受的情况下，我们考虑使离会议室相对集中以及使会议室与预定宾馆在距离上较近，利用“中心地址”进行预定宾馆 。由于③、④、⑩宾馆在距离上都较远，我们为了方便与会代表参加会议采用就近原则，只在①、②、⑤、⑥、⑦、⑧、⑨中选取 .即方案三：
约束条件：
单人间：
两人间：
.
运用计算机软件计算，并对解进行数据分析。
考虑到与会人员满意问题，我们可以预算床位数 .
考虑实际到会人数在预计人数661人左右，而造成无宾馆床位可以下塌，引起与会人员的不满，造成会议筹备处的社会声誉受损，可以多定一些床位，以保证到会人员能安心下榻的概率不小于0 .90 .因为实际到会人数是一个随机变量 ，服从二项分布
ξ～)1242.08758.0755,8758.0755(???B ，设预定床位数为k .由于755太大，可以考虑用中心极限定理，用正态分布去逼近，ξ的近似分布为
)062.9,661()1242.08758.0755,8758.0755(2N N =???， 所以有90.0)062.9661()(≥-Φ=≤k k P ξ，查表得28.1062
.9661≥-k ， 得 6.672062.928.1661≥?+≥k 故可以考虑预定673个床位 .
如果筹备处允许的空床床位数在5床以内,,则在预定床位673的情况下,至少应该到达的人数668人,则出现空床的概率为
则筹备处出现空床赔偿的概率大约为12% .
模型二：
应用图论的方法找出其图形的中心点 .
<1> .用Floyd 算法求出距离矩阵()v v ij m M ?=
<2> .计算在各点i v 设立与会人员接送的最大量服务距离()i v s .
<3> .求出顶点k v .使()(){}i v
i k v s v S ≤≤=1min . 则k v 就是建立会议场的最佳选择 . ()()120087==v S v S ，根据7，8宾馆的会议室的设置，各选三个会议室，具体为7宾馆的价格为800元，规模是140人，两个；价格为1000元，规模为200人，一个 .8宾馆价格为1000元，规模为160人，一个；价格为800元，规模为130人，两个 .
对于方案二，为了考虑各宾馆的与会代表到会议地点的距离长短，来建立一个总距离目标函数的线性规划模型：对该模型我们设abc x 表示a 宾馆到b 宾馆的c 会议室的人数，则目标函数为：
.
运用计算机软件计算，模型求解见附录表二
类似地方案三所用的总距离：目标函数为：
.
运用计算机软件计算，模型求解见附录表三
方案二所用车费模型:通过对各宾馆会议室路线进行分析，分为到7，8两宾馆的两条路线 .发现对3宾馆的与会代表全部到8宾馆参加会议；5宾馆的与会代表全部到7宾馆参加会议 .分别对3，5的与会人数安排乘车，5宾馆与会代表到7宾馆会议只需安排一辆3类车和一辆1类车；3宾馆与会代表到8宾馆会议室只需一辆3类车，所需总费用是2000元 .设i x 为第i 类型车（3,2,1=i ）
mn θ表示住在第m 宾馆与会代表到第n 宾馆会议人数
67θ:
根据模型和使用LINGO 计算得具体数据，见附录表四
分析求解数据得：
67θ需要4辆1类车，但不经济，我们进行人为优化，67θ需要3辆1类车，1辆3类车；需要费用3000元
172747,,θθθ需要4辆1类车，但不经济，我们进行人为优化，172747,,θθθ需要3辆1类车，1辆3类车,需要费用3000元
2818,θθ需要三辆1类车，但不经济，我们进行人为优化，2818,θθ需要2辆一类车和1辆三类车: 需要2200元；
98θ需要3辆1类车，但不经济，我们进行人为优化，98θ需要2辆一类车和1辆三类车: 需要费用2200元；
57θ需要1辆一类车和1辆三类车:所需总费用1400元
五．模型求解
方案二的最优解：
Global optimal solution found at iteration: 17
Objective value: 81600 .00
Variable Value Reduced Cost
X11 0 .000000 0 .000000 X12 43 .00000 0 .000000 X13 9 .000000 0 .000000 X14 20 .00000 0 .000000 X21 33 .00000 0 .000000 X22 0 .000000 10 .00000 X23 53 .00000 0 .000000 X24 0 .000000 10 .00000 X31 0 .000000 75 .00000 X32 0 .000000 0 .000000 X33 27 .00000 0 .000000 X41 100 .0000 0 .000000 X42 0 .000000 10 .00000 X51 70 .00000 0 .000000 X52 0 .000000 10 .00000 X53 0 .000000 10 .00000 X61 118 .0000 0 .000000 X62 80 .00000 0 .000000 X63 30 .00000 0 .000000 X64 0 .000000 0 .000000 X71 0 .000000 5 .000000 X72 0 .000000 0 .000000 X73 0 .000000 190 .0000 X81 0 .000000 0 .000000 X82 0 .000000 10 .00000 X83 45 .00000 0 .000000 X91 0 .000000 20 .00000 X92 30 .00000 0 .000000 X93 0 .000000 30 .00000 X94 3 .000000 0 .000000 X101 0 .000000 20 .00000 X102 0 .000000 30 .00000 Row Slack or Surplus Dual Price
1 81600 .00 -1 .000000
2 0 .000000 -160 .0000
3 0 .000000 -180 .0000
4 0 .000000 -280 .0000
5 0 .000000 -70 .00000
6 0 .000000 -90 .00000
7 0 .000000 -110 .0000
8 100 .0000 0 .000000
9 17 .00000 0 .000000
10 21 .00000 0 .000000
11 0 .000000 60 .00000
12 67 .00000 0 .000000
13 70 .00000 0 .000000
14 7 .000000 0 .000000
15 70 .00000 0 .000000
16 100 .0000 0 .000000
17 48 .00000 0 .000000
18 0 .000000 10 .00000
19 0 .000000 0 .000000
20 90 .00000 0 .000000
21 0 .000000 0 .000000
22 70 .00000 0 .000000
23 40 .00000 0 .000000
24 0 .000000 5 .000000
25 0 .000000 0 .000000
26 60 .00000 0 .000000
27 100 .0000 0 .000000
28 40 .00000 0 .000000
29 30 .00000 0 .000000
30 80 .00000 0 .000000
31 80 .00000 0 .000000
32 0 .000000 0 .000000
33 60 .00000 0 .000000
34 0 .000000 20 .00000
35 80 .00000 0 .000000
36 27 .00000 0 .000000
37 110 .0000 0 .000000
38 90 .00000 0 .000000
对方案二求解,把x61调至x93,x91,其余不变 .
81600-78×160+30×280+9×260=79860(元)
但还需加车费用10400元,会议费10400元,所以总费用为:
79860+10400+10400=100660(元)
同样利用方案二的解，解答方案三
则住房费用为:81600-78×160－27×150－50×140+50×150+27×160+30×280+9×
260=80630(元)
会议费10400元 .而在方案三中,去掉了3,4,10之后距离就很近了,则为了经济节约,就不需要派车接送与会代表了,可省去车费,所以总费用为:
80630+10400=91030(元)
六．模型检验
通过对模型的求解,由于方案一对第一类房间单人间要求人数共有166人,而符合这个价位的房间数只有107间,因此方案一无解,所以我们通过对x61的约束条件取消，得到模型一的第二种方案,得x61要求住118人，而房间数只有40间，所以我们对多余的78人分到x91,x93，以达到分配的合理 .为了满足宾馆数尽量减少和距离集中的条件下，我们对3，4，宾馆的人数进行调整，x33有27人，将其全部调置到x72中；x41有100人，将其全部调置到x71中，得到第三套方案 .对于第三套方案的是从经济，方便和使代表满意三方面来考虑建立最优模型，但美中不足的是第三套方案会有部分单人间的代表要被安排到双人间独住 .
七．模型评价
对于方案一，由于宾馆单人间第一类房间少于与会代表的要求数量，所以模型无解 .
对于方案二，从最优经济的角度考虑，是最优模型，但没有从距离考虑，且有少数代表不能达到要求 .
对于方案三，是从经济，方便和使代表满意三方面综合来考虑建立最优模型，但美中不足的是第三套方案会有部分单人间的代表要被安排到双人间独住 .由于各宾馆的距离最多在450米，所以此方案可以省去租车接送代表的费用，更加的经济 .
八是从经济，方便和使代表满意三方面来考虑建立最优模型，但美中不足的是第三套方案会有部分单人间的代表要被安排到双人间独住 .
八．参考文献
陶谦坎汪应洛《运筹学与系统分析》全国高等教育自学考试指导委员会机械工业出版社 1999年7月
杨启帆等《数学建模》高等教育出版社 2004年12月
王兵团《数学建模基础》清华大学出版社
九．附录
附表一
Zmin=90*x11+110*x12+180*x13+220*x14+70*x21+80*x22
+90*x23+100*x24+75*x31+90*x32+150*x33+70*x41
+100*x42+70*x24+75*x31+90*x32+150*x33+70*x41
+180*x63+110*x64+75*x71+160*x72+300*x73+90*x94
+130*x101+140*x102
x33+x61+x72=145
x13+x63+x83=84
x14+x92+x94=53
x21+x22+x41+x51+x52+x71+x82=203
x11+x23+x24+x32+x42+x53+x62+x81=133
x12+x64+x73+x91+x93+x101+x102=43
x11<=100
x12<=60
x13<=30
x14<=20
x21<=100
x22<=70
x23<=60
x24<=70
x31<=100
x32<=48
x33<=27
x41<=100
x42<=90
x51<=70
x52<=70
x53<=40
x62<=80
x63<=30
x71<=100
x72<=40
x73<=30
x81<=80
x82<=80
x83<=45
x91<=60
x92<=30
x93<=60
x94<=30
x101<=110
x102<=90
Global optimal solution found at iteration: 17
Objective value: 81600 .00
Variable Value Reduced Cost
X11 0 .000000 0 .000000 X12 43 .00000 0 .000000 X13 9 .000000 0 .000000 X14 20 .00000 0 .000000 X21 33 .00000 0 .000000 X22 0 .000000 10 .00000 X23 53 .00000 0 .000000 X24 0 .000000 10 .00000 X31 0 .000000 75 .00000 X32 0 .000000 0 .000000 X33 27 .00000 0 .000000 X41 100 .0000 0 .000000 X42 0 .000000 10 .00000 X51 70 .00000 0 .000000 X52 0 .000000 10 .00000 X53 0 .000000 10 .00000 X61 118 .0000 0 .000000 X62 80 .00000 0 .000000 X63 30 .00000 0 .000000 X64 0 .000000 0 .000000 X71 0 .000000 5 .000000 X72 0 .000000 0 .000000 X73 0 .000000 190 .0000 X81 0 .000000 0 .000000 X82 0 .000000 10 .00000 X83 45 .00000 0 .000000 X91 0 .000000 20 .00000 X92 30 .00000 0 .000000 X93 0 .000000 30 .00000 X94 3 .000000 0 .000000 X101 0 .000000 20 .00000 X102 0 .000000 30 .00000 Row Slack or Surplus Dual Price
1 81600 .00 -1 .000000
2 0 .000000 -160 .0000
3 0 .000000 -180 .0000
4 0 .000000 -280 .0000
5 0 .000000 -70 .00000
6 0 .000000 -90 .00000
7 0 .000000 -110 .0000
8 100 .0000 0 .000000
9 17 .00000 0 .000000
10 21 .00000 0 .000000
11 0 .000000 60 .00000
12 67 .00000 0 .000000
13 70 .00000 0 .000000
14 7 .000000 0 .000000
15 70 .00000 0 .000000
16 100 .0000 0 .000000
17 48 .00000 0 .000000
18 0 .000000 10 .00000
19 0 .000000 0 .000000
20 90 .00000 0 .000000
21 0 .000000 0 .000000
22 70 .00000 0 .000000
23 40 .00000 0 .000000
24 0 .000000 5 .000000
25 0 .000000 0 .000000
26 60 .00000 0 .000000
27 100 .0000 0 .000000
28 40 .00000 0 .000000
29 30 .00000 0 .000000
30 80 .00000 0 .000000
31 80 .00000 0 .000000
32 0 .000000 0 .000000
33 60 .00000 0 .000000
34 0 .000000 20 .00000
35 80 .00000 0 .000000
36 27 .00000 0 .000000
37 110 .0000 0 .000000
38 90 .00000 0 .000000
附表二
min=300*x171+300*x172+300*x173+500*x181+500*x182+500*x183+450* x271+450*x272+450*x273+650*x281+650*x282+650*x283+1200*x371+12 00*x372+1200*x373+1000*x381+1000*x382+1000*x383+950*x471+950*x 472+950*x473+1150*x481+1150*x482+1150*x483+300*x571+300*x572+3 00*x573+500*x581+500*x582+500*x583+300*x671+300*x672+300*x673+ 500*x681+500*x682+500*x683+200*x781+200*x782+200*x783+200*x871
+200*x872+200*x873+350*x971+350*x972+350*x973+150*x981+150*x98 2+150*x983;
x171+x172+x173+x181+x182+x183=72;
x271+x272+x273+x281+x282+x283=86;
x371+x372+x373+x381+x382+x383=27;
x471+x472+x473+x481+x482+x483=100;
x571+x572+x573+x581+x582+x583=70;
x671+x672+x673+x681+x682+x683=150;
x771+x772+x773+x781+x782+x783=0;
x871+x872+x873+x881+x882+x883=45;
x971+x972+x973+x981+x982+x983=111;
x171+x271+x371+x471+x571+x671+x771+x871+x971<=140;
100<=x171+x271+x371+x471+x571+x671+x771+x871+x971;
x172+x272+x372+x472+x572+x672+x772+x872+x972<=140;
100<=x172+x272+x372+x472+x572+x672+x772+x872+x972;
x173+x273+x373+x473+x573+x673+x773+x873+x973<=200;
100<=x173+x273+x373+x473+x573+x673+x773+x873+x973;
x181+x281+x381+x481+x581+x681+x781+x881+x981<=130;
100<=x181+x281+x381+x481+x581+x681+x781+x881+x981;
x182+x282+x382+x482+x582+x682+x782+x882+x982<=130;
100<=x182+x282+x382+x482+x582+x682+x782+x882+x982;
x183+x283+x383+x483+x583+x683+x783+x883+x983<=160;
100<=x183+x283+x383+x483+x583+x683+x783+x883+x983;
Global optimal solution found at iteration: 17
Objective value: 288350 .0
Variable Value Reduced Cost
X171 17 .00000 0 .000000
X172 0 .000000 0 .000000
X173 0 .000000 0 .000000
X181 55 .00000 0 .000000
X182 0 .000000 0 .000000
X183 0 .000000 0 .000000
X271 24 .00000 0 .000000
X272 0 .000000 0 .000000
X273 0 .000000 0 .000000
X281 0 .000000 0 .000000
X282 0 .000000 0 .000000
X283 62 .00000 0 .000000
X371 0 .000000 400 .0000
X372 0 .000000 400 .0000
X373 0 .000000 400 .0000
X381 0 .000000 0 .000000
X382 0 .000000 0 .000000
X383 27 .00000 0 .000000
X471 29 .00000 0 .000000