1完整的论文-先看看-会议筹备的多目标混合整数线性规划

2009高教社杯全国大学生数学建模竞赛会议筹备的目标混合整数线性规划模型四川信息职业技术学院指导老师：数学建模教练组参赛队员：张波张山川刘健2009年9月14日2009高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：D我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：四川信息职业技术学院参赛队员(打印并签名)：1.张波2.张山川3.刘健指导教师或指导教师组负责人(打印并签名)：宋秀英日期：2009年9月14日赛区评阅编号（由赛区组委会评阅前进行编号）：2009高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1会议筹备的多目标混合整数线性规划模型摘要本文讨论了筹备会议时合理预订宾馆客房、租借会议室、租用客车问题。以最小化与会代表支付费用，最小化筹备方支付费用，最小化预定宾馆数量，最小化预定宾馆之间的距离，以入住人数约束，最大可订客房数约束，选择宾馆入住的条件约束，会议选择的约束，租用客车满足要求约束，建立了会议筹备中预定客房、租借会议室、租用客车问题的多目标混合整数线性规划模型，并分别通过单目标优化和多目标分层序列优化方法，解决了这一复杂的问题。首先整理题目所给出的数据。我们建立了灰色预测模型对本届与会人数进行预测，然后对数据取整。用MATLAB软件编程计算得出本届与会率为84.468%，与会总人数为644人。其次，建立了4个目标函数，即与会人员客房花费最小、筹备方支出费用最少、总入住宾馆最少、宾馆间距离最短。针对第一个目标，我们根据与会人员的住房要求建立与会人员客房花费最少的模型；第二个目标，通过对筹备方的租借会议室和租车的经费求取最小值建立模型，这里我们对开会的形式做了假设，即上下午各安排6个会议室，各位与会代表将分别参加上下午的会议，且只能上午和下午的任意一个会议；第三个目标我们取预定宾馆数最小；第四个目标取预定宾馆间的欧几里得距离和最小。最后通过单目标优化，多目标分层求解的方法对该多目标规划进行简化，运用LINGO编程求解得到：1、筹备组选择租赁①、②、③、⑦号宾馆；2、宾馆的客房和会议室租赁方案为：①号宾馆所有房间全部租赁，并租1间200人的会议室；②号宾馆的普通双标间、商务双标间、豪华双标间A、豪华双标间B分别租赁50、23、30、13间，并租3间180人的会议室；③号宾馆的普通双标间、商务双标间、普通单人间分别租赁50、24、27间，并租1间150人的会议室；⑦号宾馆的普通双标间、商务单人间、商务套房（1床）分别租赁50、40、324间，并租1间200人的会议室；3、筹备组可以不用租赁客车来接送与会人员，从而与会人员直接在下榻的宾馆租接的会议室开会。本文主要研究了会议筹备的规划问题。主要优点是：本题通过建立多目标混合线性整数规划模型来建模求解。但本文将问题分解，对模型中的目标函数和约束条件分别建立了相应的模型。思路清晰，且使得最终优化时能得到满意的最佳会议筹备方案设计。主要缺点是：因专业知识匮乏，数据资料的不完整，我们做了较合理的假设，这可能会造成小部分结果的细微偏差，但不影响整体结果。关键词：会议筹备；多目标混合整数线性规划；灰色预测；单目标优化；分层序列算法；2一、问题的提出某市的一家会议服务公司负责承办某专业领域的一届全国性会议，会议筹备组要为与会代表预订宾馆客房，租借会议室，并租用客车接送代表。由于预计会议规模庞大，而适于接待这次会议的几家宾馆的客房和会议室数量均有限，所以只能让与会代表分散到若干家宾馆住宿。为了便于管理，除了尽量满足代表在价位等方面的需求之外，所选择的宾馆数量应该尽可能少，并且距离上比较靠近。筹备组经过实地考察，筛选出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）对性别s进行编号：记男性为0，女性为1。3.2符号说明kijsx-------表示所订i宾馆j客房提供给k档次s性别的数量ipqy-------表示从i宾馆到p宾馆q会议室参加会议的人数3pqz-------表示所订p宾馆q会议室数量ija-------表示i宾馆j客房的费用pqb-------表示p宾馆q会议室的费用ijc-------表示i宾馆j房间的最大订房数pqd-------表示p宾馆q会议室的最大预订数pqf-------表示p宾馆q会议室的最大容纳人数1im、2im、3im-------分别表示租800、700、600三种类型客车数量kse-------表示s性别住k档次房的实际人数kijsR-------表示i宾馆j客房是否满足s参会代表的k档次住房要求（为0，1变量，0表示不满足，1表示满足）iT-------表示i宾馆是否有人入住（为0，1变量，0表示未入住，1表示入住）'iil-------表示i宾馆到'i宾馆的距离四、问题分析题目要求从经济、方便、代表满意等方面，为会议筹备组制定一个预订宾馆客房、租借会议室、租用客车的合理方案。“方便”、“代表满意”以及“空房问题”等均为模糊概念。对于空房问题，主要是由于代表真实到会人数无法确定所造，在此数据信息有限，只能考虑通过过去4届的历史数据对到会人数进行预测，以便尽量减少空房数和预订客房数量不足情况。对于问题中对客房、会议室等安排，直接采用所预测的到会人数进行计算分析。对于“方便”这一概念，我通过对宾馆数以及所订宾馆之间的距离尽量短来进行刻画。由于数据有限，代表的满意度问题只能根据代表所需自付的房费来进行刻画，而又由于每个代表有自己的要求价格区间，所以我们将满意度定义为在满意要求的情况下价格越低满意度越高。对于会议筹备组来说，在筹备整个会议时，既要考虑到与会代表的意愿，又要使开支最小。在充分满足参会代表的意愿的前提下，要想开支尽可能的小。而筹备组的经费主要由会议室租借费与汽车租借费用组成，所以应该尽量使得费用总和最少。对于乘车问题，在题目中未给出详细说明，所以我们只能假设车辆的租借是只能服务于单个宾馆，不能出现一辆车反复运送乘客的情况。综上分析可知，问题即转化为一个数据预测问题和以顾客满意度最大、费用最小、宾馆数尽量少、宾馆距离尽量靠近的一个多目标优化问题。4五、数据处理根据附表3以往四届会议代表回执和与会情况可转化为表1：表1与会情况第一届第二届第三届第四届回执人数315356408711与会人数283310362602与会率0.8984130.8707870.8872550.846695根据题目资料，会议筹备组经过实地考察，筛选出10家宾馆作为备选，已知了相邻宾馆间的距离，如（附录【图】）所示，但没有给出10家宾馆间的相互距离，为了满足模型构建的需要，这里假设下图中纵向道路宽度为200米，横向道路宽度为150米，两宾馆间的相互距离采用欧几里德距离，经过数据处理，得到10家宾馆间的相互距离如表2所示。表2宾馆相互距离表①②③④⑤⑥⑦⑧⑨⑩①01509006506006003005006501300②15007505007507504506508001450③9007500250150015001200100011502200④650500250012501250950115013001950⑤6007501500125006003005006501300⑥600750150012506000300500350700⑦300450120095030030002003501000⑧5006501000115050050020001501200⑨650800115013006503503501500850⑩13001450220019501300700100012008500附表2中给出了代表回执中有关住房要求的信息，结合附表1给出的10家备选宾馆的有关数据，设1kijR和2kijR分别代表i宾馆j客房是否满足男性(女性)参会代表的k档次住房要求，若满足，取值为1，否则为0；该项数据统计情况如表3所示。表3R系数矩阵宾馆客房规格男性参与代表女性参会代表合住1合住2合住3独住1独住2独住3合住1合住2合住3独住1独住2独住3①普通双标间010010010010商务双标间001001001001普通单人间000010000010商务单人间000001000001②普通双标间100100100100商务双标间1001001001005豪华双标间A010010010010豪华双标间B010010010010③普通双标间100100100100商务双标间010010010010普通单人间000100000100④普通双标间100100100100商务双标间010010010010⑤普通双标间A100100100100普通双标间B100100100100豪华双标间010010010010⑥普通单人间000100000100普通双标间010010010010商务单人间000010000010精品双人间001001001001⑦普通双标间100100100100商务单人间000100000100商务套房（1床）000001000001⑧普通双标间A010010010010普通双标间B100100100100高级单人间000010000010⑨普通双人间001001001001普通单人间000001000001豪华双人间001001001001豪华单人间000001000001⑩经济标准房（2床）001001001001标准房（2床）001001001001六、模型的建立6.1预测模型的建立与求解从表1可以看出以往四届参加会议人员虽然在增加，但与会率却在减小。针对与会率数