2009高教社杯全国大学生数学建模竞赛
会议筹备的目标混合整数线性规划模型
四川信息职业技术学院
指导老师:数学建模教练组
参赛队员:张 波
张山川
刘 健
2009年9月14日
2009高教社杯全国大学生数学建模竞赛
承 诺 书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。
我们知道,抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。如有违反竞赛规则的行为,我们将受到严肃处理。
我们参赛选择的题号是(从A/B/C/D中选择一项填写): D
我们的参赛报名号为(如果赛区设置报名号的话):
所属学校(请填写完整的全名): 四川信息职业技术学院
参赛队员 (打印并签名) :1. 张 波
2. 张山川
3. 刘 健
指导教师或指导教师组负责人 (打印并签名): 宋秀英
日期: 2009 年 9 月 14 日
赛区评阅编号(由赛区组委会评阅前进行编号):
2009高教社杯全国大学生数学建模竞赛
编 号 专 用 页
赛区评阅编号(由赛区组委会评阅前进行编号):
赛区评阅记录(可供赛区评阅时使用):
评
阅
人
评
分
备
注
全国统一编号(由赛区组委会送交全国前编号):
全国评阅编号(由全国组委会评阅前进行编号):
会议筹备的多目标混合整数线性规划模型
摘要
本文讨论了筹备会议时合理预订宾馆客房、租借会议室、租用客车问题。
以最小化与会代表支付费用,最小化筹备方支付费用,最小化预定宾馆数量,最小化预定宾馆之间的距离,以入住人数约束,最大可订客房数约束,选择宾馆入住的条件约束,会议选择的约束,租用客车满足要求约束,建立了会议筹备中预定客房、租借会议室、租用客车问题的
多目标混合整数线性规划模型,
并分别通过单目标优化和多目标分层序列优化方法,
解决了这一复杂的问题。
首先整理题目所给出的数据。我们建立了灰色预测模型对本届与会人数进行预测,然后对数据取整。用MATLAB软件编程计算得出本届与会率为84.468%,与会总人数为644人。其次,建立了4个目标
函数
excel方差函数excelsd函数已知函数 2 f x m x mx m 2 1 4 2拉格朗日函数pdf函数公式下载
,即与会人员客房花费最小、筹备方支出费用最少、总入住宾馆最少、宾馆间距离最短。针对第一个目标,我们根据与会人员的住房要求建立与会人员客房花费最少的模型;第二个目标,通过对筹备方的租借会议室和租车的经费求取最小值建立模型,这里我们对开会的形式做了假设,即上下午各安排6个会议室,各位与会代表将分别参加上下午的会议,且只能上午和下午的任意一个会议;第三个目标我们取预定宾馆数最小;第四个目标取预定宾馆间的欧几里得距离和最小。最后通过单目标优化,多目标分层求解的方法对该多目标规划进行简化,运用LINGO编程求解得到:
1、筹备组选择租赁①、②、③、⑦号宾馆;
2、宾馆的客房和会议室租赁
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
为:①号宾馆所有房间全部租赁,并租1间200人的会议室;②号宾馆的普通双标间、商务双标间、豪华双标间A、豪华双标间B分别租赁50、23、30、13间,并租3间180人的会议室;③号宾馆的普通双标间、商务双标间、普通单人间分别租赁50、24、27间,并租1间150人的会议室;⑦号宾馆的普通双标间、商务单人间、商务套房(1床)分别租赁50、40、324间,并租1间200人的会议室;
3、筹备组可以不用租赁客车来接送与会人员,从而与会人员直接在下榻的宾馆租借的会议室开会
。
本文主要研究了会议筹备的规划问题。主要优点是:本题通过建立多目标混合线性整数规划模型来建模求解。但本文将问题分解,对模型中的目标函数和约束条件分别建立了相应的模型。思路清晰,且使得最终优化时能得到满意的最佳会议筹备方案
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
。主要缺点是:因专业知识匮乏,数据资料的不完整,我们做了较合理的假设,这可能会造成小部分结果的细微偏差,但不影响整体结果。
关键词:会议筹备;多目标混合整数线性规划;灰色预测;单目标优化;分层序列算法
一、问题的提出
某市的一家会议服务公司负责承办某专业领域的一届全国性会议,会议筹备组要为与会代表预订宾馆客房,租借会议室,并租用客车接送代表。由于预计会议规模庞大,而适于接待这次会议的几家宾馆的客房和会议室数量均有限,所以只能让与会代表分散到若干家宾馆住宿。为了便于管理,除了尽量满足代表在价位等方面的需求之外,所选择的宾馆数量应该尽可能少,并且距离上比较靠近。
筹备组经过实地考察,筛选出10家宾馆作为备选,它们的名称用代号①至⑩表示,相对位置见附图,有关客房及会议室的规格、间数、价格等数据见附表1。
根据这届会议代表回执整理出来的有关住房的信息见附表2。从以往几届会议情况看,有一些发来回执的代表不来开会,同时也有一些与会的代表事先不提交回执,相关数据见附表3。附表2,3都可以作为预订宾馆客房的参考。
需要说明的是,虽然客房房费由与会代表自付,但是如果预订客房的数量大于实际用房数量,筹备组需要支付一天的空房费,而若出现预订客房数量不足,则将造成非常被动的局面,引起代表的不满。
会议期间有一天的上下午各安排6个分组会议,筹备组需要在代表下榻的某几个宾馆租借会议室。由于事先无法知道哪些代表准备参加哪个分组会,筹备组还要向汽车租赁公司租用客车接送代表。现有45座、36座和33座三种类型的客车,租金分别是半天800元、700元和600元。
请你们通过数学建模方法,从经济、方便、代表满意等方面,为会议筹备组制定一个预订宾馆客房、租借会议室、租用客车的合理方案。
二、模型假设
1、假设题目所提供所有数据真实可信。
2、假设每个宾馆能提供足量的房间。
3、假设宾馆所住代表尽量参加该宾馆的分组会议。
4、假设每个代表上午下午都参加分组会,并且每半天只能参加一个组的会议。
5、假设车辆租借只能满足一个宾馆的代表乘坐(不能中途上客,但可以将不同代表送至不同的宾馆,费用不变)。
三、符号说明及概念引入
3.1
概念引入
(1)宾馆客房与会议室的编号:为了方便
论文
政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载
的叙述,我们对每个宾馆的客房与会议室进行编号为1、2、3、4,如果不足4个即将其参数定义为0即可。
(2)住房档次要求的编号:为了方便叙述,我们将合住1、合住2、合住3、独住1、独住2、独住3分别标号为1档次房、2档次房……6档次房。
(3)对性别
进行编号:记男性为0,女性为1。
3.2
符号说明
-------表示所订
宾馆
客房提供给
档次
性别的数量
-------表示从
宾馆到
宾馆
会议室参加会议的人数
-------表示所订
宾馆
会议室数量
-------表示
宾馆
客房的费用
-------表示
宾馆
会议室的费用
-------表示
宾馆
房间的最大订房数
-------表示
宾馆
会议室的最大预订数
-------表示
宾馆
会议室的最大容纳人数
、
、
-------分别表示租800、700、600三种类型客车数量
-------表示
性别住
档次房的实际人数
-------表示
宾馆
客房是否满足
参会代表的
档次住房要求(为0,1变量,0表示不满足,1表示满足)
-------表示
宾馆是否有人入住(为0,1变量,0表示未入住,1表示入住)
-------表示
宾馆到
宾馆的距离
四、问题分析
题目要求从经济、方便、代表满意等方面,为会议筹备组制定一个预订宾馆客房、租借会议室、租用客车的合理方案。“方便”、“代表满意”以及“空房问题”等均为模糊概念。对于空房问题,主要是由于代表真实到会人数无法确定所造,在此数据信息有限,只能考虑通过过去4届的历史数据对到会人数进行预测,以便尽量减少空房数和预订客房数量不足情况。对于问题中对客房、会议室等安排,直接采用所预测的到会人数进行计算分析。对于“方便”这一概念,我通过对宾馆数以及所订宾馆之间的距离尽量短来进行刻画。由于数据有限,代表的满意度问题只能根据代表所需自付的房费来进行刻画,而又由于每个代表有自己的要求价格区间,所以我们将满意度定义为在满意要求的情况下价格越低满意度越高。
对于会议筹备组来说,在筹备整个会议时,既要考虑到与会代表的意愿,又要使开支最小。在充分满足参会代表的意愿的前提下,要想开支尽可能的小。而筹备组的经费主要由会议室租借费与汽车租借费用组成,所以应该尽量使得费用总和最少。对于乘车问题,在题目中未给出详细说明,所以我们只能假设车辆的租借是只能服务于单个宾馆,不能出现一辆车反复运送乘客的情况。
综上分析可知,问题即转化为一个数据预测问题和以顾客满意度最大、费用最小、宾馆数尽量少、宾馆距离尽量靠近的一个多目标优化问题。
五、数据处理
根据附表3以往四届会议代表回执和与会情况可转化为表1:
表1与会情况
第一届
第二届
第三届
第四届
回执人数
315
356
408
711
与会人数
283
310
362
602
与会率
0.898413
0.870787
0.887255
0.846695
根据题目资料,会议筹备组经过实地考察,筛选出10家宾馆作为备选,已知了相邻宾馆间的距离,如(附录【图】)所示,但没有给出10家宾馆间的相互距离,为了满足模型构建的需要,这里假设下图中纵向道路宽度为200米,横向道路宽度为150米,两宾馆间的相互距离采用欧几里德距离,经过数据处理,得到10家宾馆间的相互距离如表2所示。
表2 宾馆相互距离表
①
②
③
④
⑤
⑥
⑦
⑧
⑨
⑩
①
0
150
900
650
600
600
300
500
650
1300
②
150
0
750
500
750
750
450
650
800
1450
③
900
750
0
250
1500
1500
1200
1000
1150
2200
④
650
500
250
0
1250
1250
950
1150
1300
1950
⑤
600
750
1500
1250
0
600
300
500
650
1300
⑥
600
750
1500
1250
600
0
300
500
350
700
⑦
300
450
1200
950
300
300
0
200
350
1000
⑧
500
650
1000
1150
500
500
200
0
150
1200
⑨
650
800
1150
1300
650
350
350
150
0
850
⑩
1300
1450
2200
1950
1300
700
1000
1200
850
0
附表2中给出了代表回执中有关住房要求的信息,结合附表1给出的10家备选宾馆的有关数据,设
和
分别代表
宾馆
客房是否满足男性(女性)参会代表的
档次住房要求,若满足,取值为1,否则为0;该项数据统计情况如表3所示。
表3 R系数矩阵
宾
馆
客房规格
男性参与代表
女性参会代表
合住1
合住2
合住3
独住1
独住2
独住3
合住1
合住2
合住3
独住1
独住2
独住3
①
普通双标间
0
1
0
0
1
0
0
1
0
0
1
0
商务双标间
0
0
1
0
0
1
0
0
1
0
0
1
普通单人间
0
0
0
0
1
0
0
0
0
0
1
0
商务单人间
0
0
0
0
0
1
0
0
0
0
0
1
②
普通双标间
1
0
0
1
0
0
1
0
0
1
0
0
商务双标间
1
0
0
1
0
0
1
0
0
1
0
0
豪华双标间A
0
1
0
0
1
0
0
1
0
0
1
0
豪华双标间B
0
1
0
0
1
0
0
1
0
0
1
0
③
普通双标间
1
0
0
1
0
0
1
0
0
1
0
0
商务双标间
0
1
0
0
1
0
0
1
0
0
1
0
普通单人间
0
0
0
1
0
0
0
0
0
1
0
0
④
普通双标间
1
0
0
1
0
0
1
0
0
1
0
0
商务双标间
0
1
0
0
1
0
0
1
0
0
1
0
⑤
普通双标间A
1
0
0
1
0
0
1
0
0
1
0
0
普通双标间B
1
0
0
1
0
0
1
0
0
1
0
0
豪华双标间
0
1
0
0
1
0
0
1
0
0
1
0
⑥
普通单人间
0
0
0
1
0
0
0
0
0
1
0
0
普通双标间
0
1
0
0
1
0
0
1
0
0
1
0
商务单人间
0
0
0
0
1
0
0
0
0
0
1
0
精品双人间
0
0
1
0
0
1
0
0
1
0
0
1
⑦
普通双标间
1
0
0
1
0
0
1
0
0
1
0
0
商务单人间
0
0
0
1
0
0
0
0
0
1
0
0
商务套房(1床)
0
0
0
0
0
1
0
0
0
0
0
1
⑧
普通双标间A
0
1
0
0
1
0
0
1
0
0
1
0
普通双标间B
1
0
0
1
0
0
1
0
0
1
0
0
高级单人间
0
0
0
0
1
0
0
0
0
0
1
0
⑨
普通双人间
0
0
1
0
0
1
0
0
1
0
0
1
普通单人间
0
0
0
0
0
1
0
0
0
0
0
1
豪华双人间
0
0
1
0
0
1
0
0
1
0
0
1
豪华单人间
0
0
0
0
0
1
0
0
0
0
0
1
⑩
经济
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
房(2床)
0
0
1
0
0
1
0
0
1
0
0
1
标准房(2床)
0
0
1
0
0
1
0
0
1
0
0
1
六、模型的建立
6.1 预测模型的建立与求解
从表1可以看出以往四届参加会议人员虽然在增加,但与会率却在减小。针对与会率数据量少,在数据波动不大的情况下,我们使用灰色GM(1,1)模型预测。(1)GM(1,1)模型的建立:
设时间序列
,对各项值进行累加,得到新的累加数新的序列
:
那么GM(1,1)模型相应微分方程为:
对微分方程求解,即可得预测模型:
(2)GM(1,1)模型求解
使用MATLAB 软件编程,预测出第五届会议代表的到会率为84.468%,百分绝对误差为0.011842%;
由附表2,本届会议的代表回执中有关住房要求的信息,按照预测出第五届会议代表的与会比率,得到实际与会人员的住房要求,采用Excel中的ROUNDUP函数
来近似数据取整,即不管尾数多大,均进位取整,如表4所示:
表4 本届会议的代表与会人员有关住房要求的信息(单位:人)
合住1
合住2
合住3
独住1
独住2
独住3
男
131
88
28
91
58
35
女
66
41
15
50
24
17
(说明:表头第一行中的数字1、2、3分别指每天每间120~160元、161~200元、201~300元,三种不同价格的房间。合住是指要求两人合住一间。独住是指可安排单人间,或一人单独住一个双人间。)
计算得出本届会议与会人员的总数为A:
A=131+88+28+91+58+35+66+41+15+50+24+17=644人,
其中男性431人,女性213人。
6.2 优化模型的建立
6.2.1目标函数的确定
筹备方为了便于管理,除了尽量满足代表在价位等方面的需求之外,所选择的宾馆数量应该尽可能少,并且距离上比较靠近。从经济方面考虑,筹备方花费越少越好。
(1) 目标一:代表满意度
代表满意度主要根据代表所要求的订房价格区间越便宜越好
满意度评价函数
其中令f(120)=1,f(160)=0.1,f(161)=1,f(200)=0.1,f(201)=1,f(300)=0
求得
所以满意度评价函数为:
满意度最小:
(2)目标二:筹备费用
会议期间一天的上下午各安排6个分组会议,筹备组需要在代表下榻的某几个宾馆租借会议室。由于事先无法知道哪些代表准备参加哪个分组会,筹备组要向汽车租赁公司租用客车接送代表。那么,需要筹备组支付的费用就分为租借会议室的费用
,和租赁客车的费用
(客车车型有三种用
表示)。对于筹备方来说,租借会议室和租赁客车的费用越少越好,即:
(3)目标三:宾馆数量选择
对于宾馆的选择只有两种(选与不选),所以在引进一个0-1函数
,
。选择的宾馆数量越少,筹备方在安排客车接送代表时,所花的费用就越小。那么就要求宾馆的数量越少越好,即:
(4)目标四:宾馆之间的距离
在选择宾馆的时候,考虑到交通的方便性,就需要选择的宾馆之间的距离比较近。
设:
表示
宾馆到
宾馆的距离。选择的宾馆与宾馆之间的距离越近越好,即:
6.2.2约束条件的确定
(1)入住人数的约束:
要求必须把所有的代表都安排进宾馆,那么安排入住人数要大于等于参会代表总人数。引入一个0-1函数
,来确定某位代表是否入住
宾馆
客房。
设:
,则:
其中,
表示
住
档次住房的实际人数。
(2) 入住约束:
由于合住者入住有可能落单,但在此我们忽略其影响,所以入住人数等于参会人数:
其中,
表示从
宾馆到
宾馆
会议室参加会议的人数。
(3) 最大可订客房数约束:
筹备方在选订客房时,不可能超过宾馆所能提供的客房数量,即:
其中,
表示
宾馆
房间的最大订房数。
(4)会议室选择的约束:
进入会议室的代表人数,不得超过会议室的容量,即:
其中,
表示
宾馆
会议室的最大容纳人数,
表示所订
宾馆
会议室数量。
(5) 会议室数量约束:
会议期间一天的上下午各安排6个分组会议,那就在有代表下榻的宾馆中租借6个会议室。
(6)在租借会议室时,同样要注意宾馆所能提供的数量,则:
其中,
表示所订
宾馆
会议室数量,
表示
宾馆
会议室的最大预订数。
(7)租车满足要求约束:
其中,
表示从
宾馆到
宾馆
会议室参加会议的人数,
、
、
分别表示租800、700、600三种类型客车数量。
(8)会议室必须要代表下榻的某几个宾馆租借
(9)
约束
为0,1变量,且满足:
(10)非负整数约束
人数、订房间数、订会议室数和租车数均为非负整数
、
、
EMBED Equation.DSMT4 、
、
均为非负整数
综上,最终模型建立如下:
、
、
EMBED Equation.DSMT4 、
、
均为非负整数
七、模型求解
7.1
模型求解分析
显然,上面所建模型中会议室必须要代表下榻的某几个宾馆租借的约束为一个非线性约束,但为了计算方便,在此采用线性化处理,将约束条件适当放宽:
以上约束改为线性约束如下:
7.2 模型求解
首先,在无法得知目标之间的相对重要性权重,而且四个目标采用分层求解效果不好的情况下,我们采用对每个目标进行单独优化后,得到每种目标下的优化方案,供决策者参考。
1、以与会代表支付费用C为目标函数,约束条件见前面模型,进行单目标优化,利用LINGO软件编程(程序见附录【2】的model 1-1)进行求解,解得结果如表5所示:
表5 目标函数C的优化结果
宾馆房间
宾馆会议室
租车
ⅰ
ⅱ
ⅲ
ⅳ
Ⅰ
Ⅱ
Ⅲ
Ⅳ
45座
36座
33座
①
50
30
30
20
0
1
0
0
2
2
0
②
50
23
30
13
1
1
1
0
1
0
0
③
50
24
27
0
1
0
0
0
2
1
0
⑦
50
40
24
0
0
0
1
0
1
1
1
2、以会议筹备方支付费用F为目标函数,约束条件见前面模型,进行单目标优化,利用LINGO软件编程(程序见附录2的model 1-2)进行求解,解得结果如表6所示:
表6 目标函数F的优化结果
宾馆房间
宾馆会议室
租车
ⅰ
ⅱ
ⅲ
ⅳ
Ⅰ
Ⅱ
Ⅲ
Ⅳ
45座
36座
33座
①
50
28
30
20
1
0
0
0
0
0
0
②
50
24
30
14
0
0
3
0
0
0
0
③
49
24
27
0
0
0
1
0
0
0
0
⑦
50
40
26
0
0
0
1
0
0
0
0
3、以预定宾馆数G为目标函数,约束条件见前面模型,进行单目标优化,利用LINGO软件编程(程序见附录【2】的model 1-3)进行求解,解得结果如表7所示:
表7 目标函数G的优化结果
宾馆房间
宾馆会议室
租车
ⅰ
ⅱ
ⅲ
ⅳ
Ⅰ
Ⅱ
Ⅲ
Ⅳ
45座
36座
33座
①
22
30
30
19
0
0
0
0
2
1
0
②
50
35
30
35
1
1
1
0
1
0
0
⑤
35
35
40
0
1
1
0
0
0
0
0
⑦
50
39
30
0
1
0
0
0
0
0
0
4、以最小化预定宾馆间距离D为目标函数,约束条件见前面模型,进行单目标优化,利用LINGO软件编程(程序见附录【2】的model 1-4)进行求解,解得结果如表8所示:
表8 目标函数D的优化结果
宾馆房间
宾馆会议室
租车
ⅰ
ⅱ
ⅲ
ⅳ
Ⅰ
Ⅱ
Ⅲ
Ⅳ
45座
36座
33座
①
50
30
30
20
0
2
0
0
4
0
0
②
50
23
30
13
0
1
0
0
5
0
0
⑤
50
24
27
0
0
0
0
0
2
0
0
⑦
50
40
24
0
0
3
0
0
0
0
0
根据计算结果,宾馆数量和宾馆距离在每个目标下变化不大,可对参会代表预定客房费用最小和会议筹备方支付费用最小进行双目标优化,为了避免目标函数四的非线性使得模型求解困难,这里把目标函数三,即最小预定宾馆数4作为约束条件,这时,我们利用分层序列算法来选取最优解。
7.3 与会代表支付费用最小与会议筹备支付费用最小的分层序列算法求解
根据每个单目标优化结果,为了简化计算,我们可以只求C和F两个目标,对这两个目标我们可以采取分层序列法,首先设min C和min F分别代表第1个和第2个目标在各自单目标优化时的最优解;首先只求C,并将F的最优解min F作为约束放在约束条件里求解;类似可求解F,并将目标C的最优解min C放在约束条件里求解。即分别求解以下两个规划:
子规划一:
子规划二:
对以上的两个单目标子规划,进行了逐一的求解,最后对其结果进行分析得出一下结果如表9所示:
表9 分层序列求解结果
C
F
G
D
C
81050
4400
4
3750
F
81050
4400
4
3750
以C为目标函数,把F目标的最优目标函数值作为约束,见子规划一,利用LINGO对优化求解模型(程序见附录3的model 2-1),得到到优化结果表10所示:
表10 以C为目标函数,以F为约束条件优化结果
宾馆房间
宾馆会议室
租车
ⅰ
ⅱ
ⅲ
ⅳ
Ⅰ
Ⅱ
Ⅲ
Ⅳ
45座
36座
33座
①
50
30
30
20
1
0
0
0
0
0
0
②
50
23
30
13
0
0
3
0
0
0
0
③
50
24
27
0
0
0
1
0
0
0
0
⑦
50
40
324
0
0
0
1
0
0
0
0
以F为目标函数,以把C目标的最优目标函数值作为约束,见子规划二,利用LINGO对优化求解模型(程序见附录3的model 2-2),得到到优化结果表11所示:
表11 以F为目标函数,以C为约束条件
宾馆房间
宾馆会议室
租车
ⅰ
ⅱ
ⅲ
ⅳ
Ⅰ
Ⅱ
Ⅲ
Ⅳ
45座
36座
33座
①
50
30
30
20
1
0
0
0
0
0
0
②
50
23
30
13
0
0
3
0
0
0
0
③
50
24
27
0
0
0
1
0
0
0
0
⑦
50
40
324
0
0
0
1
0
0
0
0
综上所述,两次的运行结果是一样的,所以我们的出以下结论:
1、筹备组选择租赁①、②、③、⑦号宾馆;
2、①号宾馆所有房间全部租赁,并租1间200人的会议室;②号宾馆的普通双标间、商务双标间、豪华双标间A、豪华双标间B分别租赁50、23、30、13间,并租3间45人的会议室;③号宾馆的房间全部租赁,并租1间150人的会议室;⑦号宾馆的普通双标间、商务单人间、商务套房(1床)分别租赁50、40、24间,并租1间200人的会议室;
3、筹备组可以不用租赁客车来接送与会人员;
4、男女性与会代表客房安排分别如表12和表13所示:
表12 男性与会代表客房安排
①
②
③
⑦
ⅰ
ⅱ
ⅲ
ⅳ
ⅰ
ⅱ
ⅲ
ⅳ
ⅰ
ⅱ
ⅲ
ⅳ
ⅰ
ⅱ
ⅲ
ⅳ
合住1
49
17
合住2
27
17
合住3
14
独住1
11
21
1
27
2
29
独住2
2
30
2
24
独住3
11
24
表13 女性与会代表客房安排
①
②
③
⑦
ⅰ
ⅱ
ⅲ
ⅳ
ⅰ
ⅱ
ⅲ
ⅳ
ⅰ
ⅱ
ⅲ
ⅳ
ⅰ
ⅱ
ⅲ
ⅳ
合住1
2
31
合住2
21
合住3
8
独住1
39
11
独住2
11
13
独住3
8
9
7.4 结果分析
通过上述的计算,求解结果可以看出宾馆数量和宾馆距离在每个目标下变化不大,求解得到的宾馆为①、②、③、⑤、⑦,其中宾馆③、⑤在单目标函数C与F的变化下,宾馆选择发生变化。出现筹备组可以不用租赁客车来接送与会人员的结果,主要是由于题目要求筹备组租借会议室尽量在代表下榻的某几个宾馆、宾馆数量尽可能少、宾馆间距离尽可能近、筹备方经费尽可能少,在这样的条件约束下不用租赁客车来接送与会人员成为最优结果。
根据每个单目标优化结果,为了简化计算,只对C和F这两个目标采用分层序列算法求得一样的宾馆选择为①、②、③、⑦,。优越性在于将所有目标按其重要性程度依次排序,先求出第一个最重要的目标的最优解,然后在保证前一目标最优解的前提下依次求下一目标的最优解,一直求到最后一个目标为止。经过计算求解出这两组最优解是一样的,从而得出最优解。
八、模型的评价与改进
8.1 模型的评价
本文主要研究了会议筹备的规划问题。文章的主要优点是:
1、本题通过建立混合线性整数规划模型来建模求解。但本文将问题分解,对模型中的目标函数和约束条件分别建立了相应的模型。思路清晰,且使得最终优化时能得到满意的最佳会议筹备方案设计。
2、我们在模型求解过程中,采用多目标转化为单目标的求解方法,充分考虑到各个目标的在模型求解上的影响力大小。
3、文章考虑到模型的实际应用,对问题作出了更深更现实的讨论。能让筹备方确定最佳筹备方案,给筹备方带来实际的经济效益。
主要缺点是:题目所给出数据资料不完整,为解决具体问题上所做出的假设,可能会造成小部分结果的细微偏差,但不影响整体结果。
8.2 模型的改进
在模型中,我们只能通过仅有的4届数据来预测到会人数,而我们可以改进引入到会人数为随机变量,建立出同时考虑空房与住房不够的情况下的优化模型。另一方面,在计算中由于不知道每个代表参加哪个分组会,所以我们假设了,代表参会都采用尽量就近参会原则,但并不能满足实际需求。所以考虑引入参数表示不同人将参加的分组会议,以便求解结论更加符号现实情况。
九、参考文献
[1] 姜启源等编,数学模型[M](第3版),北京:高等教育出版社, 2003.8;
[2] 韩中庚编,数学建模方法及其应用[M],北京:高等教育出版社,2005.6;
[3] 姜启源等编,大学数学实验[M],北京:清华大学出版社,2005.2;
[4]《运筹学》教材编写组编,运筹学(第三版),北京:清华大学出版社,2005.6;
[5] “采用Excel中的ROUNDUP函数”摘自于WPSoffice中文办公软件专家,http://www.wps.cn/knowledge/knowledgeshow/tid-21828847.htm,2009年9月12日;
[6]谢金星等编,优化建模与LINDO/LINGO软件,北京:清华大学出版社,2005.7。
十、附录
附录【图】
图1 宾馆位置示意图
附录【1】 灰色模型matlab 程序
function []=greymodel(y)
% 本程序主要用来计算根据灰色理论建立的模型的预测值。
% 应用的数学模型是 GM(1,1)。
% 原始数据的处理方法是一次累加法。
y=input('请输入数据 ');
n=length(y);
yy=ones(n,1);
yy(1)=y(1);
for i=2:n
yy(i)=yy(i-1)+y(i);
end
B=ones(n-1,2);
for i=1:(n-1)
B(i,1)=-(yy(i)+yy(i+1))/2;
B(i,2)=1;
end
BT=B';
for j=1:n-1
YN(j)=y(j+1);
end
YN=YN';
A=inv(BT*B)*BT*YN;
a=A(1);
u=A(2);
t=u/a;
i=1:n+2;
yys(i+1)=(y(1)-t).*exp(-a.*i)+t;
yys(1)=y(1);
for j=n+2:-1:2
ys(j)=yys(j)-yys(j-1);
end
x=1:n;
xs=2:n+2;
yn=ys(2:n+2);
plot(x,y,'^r',xs,yn,'*-b');
det=0;
for i=2:n
det=det+abs(yn(i)-y(i));
end
det=det/(n-1);
disp(['百分绝对误差为:',num2str(det),'%']);
disp(['下个拟合值为 ',num2str(ys(n+1))]);
disp(['再下个拟合值为',num2str(ys(n+2))]);
附录【2】
model 1-1源程序
model:
sets:
AA/1..10/:t,m1,m2,m3;
BB/1..4/;
CC/1..6/:q0,q1;
DD(AA,BB):a,c,f,b,d,z,ff,NN;
EE(CC,AA,BB):x0,x1;
AAB(AA,AA,BB):y;
FFF(AA,AA):l;
BBB/1..40/;
EEEE(CC,BBB):r0,r1;
endsets
data:
q0=132
88
28
91
58
35;
q1=66 42
16
50
24
17;
a=180 220 180
220
140 160 180
200
150 180 150
0
140 200 0
0
140 160 200
0
160 170 180
220
150 160 300
0
180 160 180
0
260 260 280
280
260 280 0
0;
c=50
30
30
20
50
35
30
35
50
24
27
0
50
45
0
0
35
35
40
0
40
40
30
30
50
40
30
0
40
40
45
0
30
30
30
30
55
45
0
0;
f=200
150
60
0
130
180
45
30
200
100
150
60
150
50
0
0
150
180
50
0
160
180
0
0
140
60
200
0
160
130
0
0
160
120
200
0
180
140
0
0;
b=1500
1200
600
0
1000
1500
300
300
1200
800
1000
320
900
300
0
0
1000
1500
500
0
1000
1200 0
0
800
300
1000
0
1000
800
0
0
1300
800
1200
0
1500
1000 0
0;
d=1
2
2
0
2
1
3
3
1
2
1
3
2
3
0
0
2
1
3
0
1
1
0
0
2
3
1
0
1
2
0
0
1
2
1
0
1
2
0
0;
r0=0
0
0
0
1
1
0
0
1
0
0
0
1
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
1
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
0
1
1
0
0
1
0
1
0
1
0
0
0
1
1
0
0
1
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
1
0
1
0
0
0
1
0
0
0
0
1
0
0
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
1
1
1
1
1
0 0;
r1=0
0
0
0
1
1
0
0
1
0
0
0
1
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
1
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
0
1
1
0
0
1
0
1
0
1
0
0
0
1
1
0
0
1
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
1
0
1
0
0
0
1
0
0
0
0
1
0
0
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
1
1
1
1
1
0 0;
l=0
150
900
650
600
600
300
500
650
1300
150
0
750
500
750
750
450
650
800
1450
900
750
0
250
1500
1500
1200
1000
1150
2200
650
500
250
0
1250
1250
950
1150
1300
1950
600
750
1500
1250
0
600
300
500
650
1300
600
750
1500
1250
600
0
300
500
350
700
300
450
1200
950
300
300
0
200
350
1000
500
650
1000
1150
500
500
200
0
150
1200
650
800
1150
1300
650
350
350
150
0
850
1300
1450
2200
1950
1300
700
1000
1200
850
0;
enddata
min=@sum(CC(k):@sum(AA(i):@sum(BB(j):a(i,j)*(x0(k,i,j)+x1(k,i,j)))));
@for(CC(k)|k#ge#1 #and# k#le#3:@sum(AA(i):@sum(BB(j):2*r0(k,(4*(i-1)+j))*x0(k,i,j)))>=q0(k));
@for(CC(k)|k#ge#4 #and# k#le#6:@sum(AA(i):@sum(BB(j):r0(k,(4*(i-1)+j))*x0(k,i,j)))>=q0(k));
@for(CC(k)|k#ge#1 #and# k#le#3:@sum(AA(i):@sum(BB(j):2*r1(k,(4*(i-1)+j))*x1(k,i,j)))>=q1(k));
@for(CC(k)|k#ge#4 #and# k#le#6:@sum(AA(i):@sum(BB(j):r1(k,(4*(i-1)+j))*x1(k,i,j)))>=q1(k));
@for(AA(i):@for(BB(j):@sum(CC(k):x0(k,i,j)+x1(k,i,j))<=c(i,j)));
@for(AA(i):@sum(CC(k)|k#ge#1 #and# k#le#3:@sum(BB(j):2*(x0(k,i,j)+x1(k,i,j))))+@sum(CC(k)|k#ge#4 #and# k#le#6:@sum(BB(j):x0(k,i,j)+x1(k,i,j)))=@sum(AA(p):@sum(BB(q):y(i,p,q))));
@for(AA(p):@for(BB(q):@sum(AA(i):y(i,p,q))<=z(p,q)*f(p,q)));
@sum(AA(p):@sum(BB(q):z(p,q)))=6;
@for(AA(p):@for(BB(q):z(p,q)<=d(p,q)));
@for(AA(i):@sum(AA(p)|p#ne#i:@sum(BB(q):y(i,p,q)))<=45*m1(i)+36*m2(i)+33*m3(i));
@for(AA(i):45*m1(i)+36*m2(i)+33*m3(i)<@sum(AA(p):@sum(BB(q):y(i,p,q))));
@for(AA(i):@sum(CC(k):@sum(BB(j):x0(k,i,j)+x1(k,i,j)))<=@sum(CC(k):q0(k)+q1(k))*t(i));
@for(AA(p):@sum(BB(q):z(p,q))<=@sum(BB(q):d(p,q))*t(p));
@sum(AA(i):t(i))<=4;
@for(AA(i):@bin(t(i));
@gin(m1(i));
@gin(m2(i));
@gin(m3(i)));
@for(AA(p):@for(BB(q):@gin(z(p,q))));
@for(CC(k):@for(AA(i):@for(BB(j):@gin(x0(k,i,j));
@gin(x1(k,i,j)))));
@for(AA(i):@for(AA(p):@for(BB(q):@gin(y(i,p,q)))));
obj2=@sum(AA(p):@sum(BB(q):b(p,q)*z(p,q)))+@sum(AA(i):800*m1(i)+700*m2(i)+600*m3(i));
obj3=@sum(AA(i):t(i));
@for(AA(i):@for(BB(j):NN(i,j)=@sum(CC(k):x0(k,i,j)+x1(k,i,j))));
!obj4=@sum(AA(i)|i#le#(@size(AA)-1):@sum(AA(s)|s#gt#i:l(i,s)*t(i)*t(s)));
end
model 1-2源程序
model:
sets:
AA/1..10/:t,m1,m2,m3;
BB/1..4/;
CC/1..6/:q0,q1;
DD(AA,BB):a,c,f,b,d,z,ff,NN;
EE(CC,AA,BB):x0,x1;
AAB(AA,AA,BB):y;
FFF(AA,AA):l;
BBB/1..40/;
EEEE(CC,BBB):r0,r1;
endsets
data:
q0=132
88
28
91
58
35;
q1=66 42
16
50
24
17;
a=180 220 180
220
140 160 180
200
150 180 150
0
140 200 0
0
140 160 200
0
160 170 180
220
150 160 300
0
180 160 180
0
260 260 280
280
260 280 0
0;
c=50
30
30
20
50
35
30
35
50
24
27
0
50
45
0
0
35
35
40
0
40
40
30
30
50
40
30
0
40
40
45
0
30
30
30
30
55
45
0
0;
f=200
150
60
0
130
180
45
30
200
100
150
60
150
50
0
0
150
1