Lingo---酒店客房的最优分配

客房最优分配模型摘要：本文要讨论根据一个时段内常客户提出的房间预订要求，以及当前各种价位房源的价格和剩余状况，以酒店收入最大为目标，分别针对常规策略、免费升级策略、和折扣优惠策略三种情况建立整数线性规划模型，此模型先是以每类客房客人入住的天数以及其相对应的价格为切入点，先分别求出两类客房的最优分配模型，然后再由模型二将两类客房合并共同计算出最优分配模型，最后再结合折扣优惠的策略将模型优化建立模型三。

运用LINGO软件求解模型，比较三个模型的收入状况，由此可以得出旅行社的客房分配的最优模型。

关键词：整数线性规划模型、LINGO软件、折扣优惠策略。

一、问题重述一家酒店利用网络系统为常客户开设标准间和商务间两类客房的预订服务，酒店以一周（从星期一到星期日）为一个时段处理这项业务。

现在收到旅行社提出的一个一周的预订需求单，见表1和表2。

在表1中标以“星期一”那一行数字表示；星期一入住，只预订当天的2间，预订到星期二的20间，预订到星期三的6间，……，一直预订到星期日的7间。

其他各行及表2都是类似的。

酒店对旅行社的报价见表3和表4。

表中数字的含义与表1和表2相对应，如对于表3，星期一入住，只住当天的每间888元，住到星期二的每间1680元，……，一直住到星期日的每间4973元。

从这些数字可以看出，酒店在制定客房的报价时，对居住时间越长的顾客，给予的优惠越大。

考虑到周末客房使用率高的统计规律，这两天的价格定位相对较高。

这些价格全部对外公布。

现在的任务是，根据表1至表5的信息，以酒店收入最大为目标，针对以下3种不同情况，制订旅行社的客房分配方案。

（1）完全按照客户提出的不同价位客房预订要求制订分配方案，称为常规策略。

（2）在标准间（低价位客房）不够分配、而商务间（高价位客房）有剩余的情况下，将一部分商务间按对标准间的需求进行分配并收费，称为免费升级策略。

（3）在首选价位客房无法满足需求、而其他价位客房有剩余的情况下，采用打折优惠的办法鼓励部分顾客改变原来的需求，选择其他价位客房，称为折扣优惠策略。

学号系统工程与运筹学课程设计设计说明书层次分析法应用系统最优化问题起止日期：2013年11月25 日至2013 年11月29日学生姓名班级成绩指导教师经济与管理学院2013年11月29日成绩评定表目录Ⅰ研究报告 (1)课程设计题目1：改革新形式下的大学生形象评价 (1)1.问题的提出 (1)2.分层递阶结构模型 (2)3.判断矩阵及相关计算结果 (2)4.单排序及总排序计算过程及结果 (6)5.结果分析 (6)5.1结果 (6)5.2分析 (6)课程设计题目2：人员合理分配问题 (7)1.问题的提出 (7)2.问题分析 (7)3.基本假设与符号说明 (7)4.模型的建立及求解结果 (8)5.模型评价 (9)课程设计题目3：生产调运问题 (10)1.问题的提出 (10)2.问题分析 (11)3.基本假设与符号说明 (11)4.模型的建立及求解结果 (12)5.模型评价 (18)II工作报告 (19)III 参考文献 (20)附件一：人员合理分配问题lingo程序及结果 (21)附件二：生产调运问题lingo程序及结果 (22)Ⅰ研究报告课程设计题目1：改革新形式下的大学生形象评价摘要：大学生如何塑造个人形象？首先我们要了解形象这个概念以及它的重要性，得体的塑造和维护形象，会给初次见面的人以良好第一印象。

塑造大学生形象还要关注社会，放眼世界，注重群体性，同时作为大学生形象塑造最重要主体的大学生，在平时学习、生活中就应该有意识地培养、塑造自身形象，为自己在人际交往过程中、特别是未来就业求职道路上增加重要的竞争砝码。

有的人说青春就是最好的包装，天生丽质、潇洒帅气就是大学生的理想形象。

但是，我们觉得所谓的形象，并不能简单地理解为人的外表特征，更应是人的精神和内在素质通过外表的一种自然流露和表现；大学生必须在学习和实践中不断扩展自己的知识面，掌握一定的技能，如果只重外表，不重内涵构造出来的形象，则只能是肤浅和苍白无力的。

会议筹划模型摘要：在会议服务公司承办专业领域全国性会议中，会议筹备组要为与会代表预定宾馆客房、租借会议室、并租用客车接送与会代表。

为了便于管理和满足代表在价位上的要求，本文采用线性规划建立会议筹划模型。

依据以往四届的回执与与会情况，通过二次拟合估计出本届与会人员数目为636人。

再根据附表2回执信息中要求合住与独住所占比例，得到与会人员对各种类型客房的需求间数。

在以上基础上，用0-1整数线性规划的方法以宾馆数最少为目标函数建立最优化模型，用lingo编程求解，得到需要预定的宾馆代号分别为1、2、5、7，而且得到入住该4个宾馆的总人数为636，与通过推算得到本届预测与会总人数636相符合。

其次，以客房总花费最少为原则，考虑到房间数不超过可供给的客房间数，以及与会人员对各种类型房间的要求，用同样的方法建模求解，得到最少花费为7978.00元，同时给出了客房安排的方案，经检验，四个宾馆的房间种类满足附表2提供的代表回执中有关住房的要求。

然后在得到的宾馆之中租借会议室，考虑到半天开6场会议需6间会议室，以租借各种类型会议室的总费用最小为目标函数。

由附表1提供的会议室的价格、间数、规模建立线性规划模型，用lingo求解得到需要租借的6间会议室都在7号宾馆。

最后由于所有会议室都在7号宾馆，故1、2、5号宾馆只需向7号宾馆接送代表。

在与会代表都能准时到达7号宾馆开会并且所有与会人员都有座位的前提下，对车辆进行合理安排。

在此基础上，以客车租借花费的最小值为目标函数，用线性规划，得到共需租借13辆客车，总花费为19400元。

依此该会议筹备组可安排入住1、2、5、7号宾馆,与会人员需要自付的住房总花费为79780元/天；会议室安排12个，上、下午都在7号宾馆，花费7000元/天；每天租借客车13辆，总费用19400元/天。

于是该公司的总花费为26400元/天。

关键词：0-1规划最优化费用 lingo一问题重述某市的一家会议筹备组负责承办某专业领域的一届全国性会议，会议筹备组要为与会代表预订宾馆客房，租借会议室，并租用客车接送代表。

摘要现阶段许多酒店都充分利用网络预订系统，根据预订需求进行客房的最优分配成为酒店提高经济效益的关键。

本文针对题中的3种不同情况，建立整数线性规划模型，利用LINGO软件求解，找出不同策略酒店客房的最优分配。

问题（1）中，首先利用旅行社提出的标准间、商务间需求单，统计一周内每日两类客房各自需求量，并将其与酒店当日客房可供量对比。

分析得出一周内商务间总有剩余，而标准间出现房源紧张；然后根据常规策略将商务间完全按照预订要求分配，以分配标准间数为决策量、收入最大为目标建立整数规划模型，寻求最优分配（见表4、表5）。

常规策略下酒店的最大收入是1374103元。

问题（2）中，首先根据是否优先满足商务间预订需求将免费升级策略分二种情况讨论：①优先满足商务间预订需求、②不优先满足商务间预订需求；然后分别建立与两种情况对应的模型一和模型二，二者均是以分配两类客房数为决策量、收入最大为目标的整数线性规划模型。

免费升级策略在情况①时标准间最优分配见表7，在情况②时商务间、标准间的最优分配见表8、表9。

二种情况下免费升级策略的最大收入分别是：1443977元和1448613元，后者改变了客户对商务间的预订需求，收入增加0.3211%。

问题（3）中，首先同问题（2），将折扣优惠策略分两种情况讨论：①优先满足商务间预订需求、②不优先满足商务间预订需求；然后以分配客房数为决策量、最大收入为目标分别建立对应的整数线性规划模型。

折扣优惠策略在情况①时标准间最优分配见表10，在情况②时商务间、标准间的最优分配见表11、表12。

折扣优惠策略在二种情况下的最大收入分别是：1468762元和1516658元，后者同样改变了客户对商务间的预订需求，收入增加3.261%。

最后本文选取客房利用、客户满意度、收入作为三个指标对常规策略、免费升级策略、折扣优惠策略下的最优分配方案进行评价分析（如表16）。

得出结论：不优先满足商务间客户需求的折扣优惠策略，分配最少的客房（除常规策略），获得了最大收入，同时客户满意度也较好。

LINGO的使用简介LINGO软件是美国的LINGO系统公司开发的一套专门用于求解最优化问题的软件包．LINGO除了能够用于求解线性规划和二次规划外，还可以用于非线性规划求解、以及一些线性和非线性方程(组）的求解等．LINGO软件的最大特色在于它允许优化模型中的决策变量为整数,即可以求解整数规划，而且执行速度快．LINGO是用来求解线性和非线性优化问题的简易工具．LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果．在这里仅简单介绍LINGO的使用方法．LINGO(Linear INteractive and General Optimizer )的基本含义是交互式的线性和通过优化求解器．它是美国芝加哥大学的 Linus Schrage 教授于1980年开发了一套用于求解最优化问题的工具包,后来经过完善成何扩充，并成立了LINDO系统公司．这套软件主要产品有：LINDO,LINGO，LINDO API和What’sBest．它们在求解最优化问题上，与同类软件相比有着绝对的优势．软件有演示版和正式版．正式版包括:求解包(solver suite）、高级版(super)、超级版（hyper)、工业版(industrial)、扩展版(extended）．不同版本的LINGO对求解问题的规模有限制，如附表３-1所示．附表３-1 不同版本LINGO对求解规模的限制版本类型总变量数整数变量数非线性变量数约束数演示版 300 30 30 150求解包 500 50 50 250高级版 2000 200 200 1000超级版 8000 800 800 4000工业版 32000 3200 32000 16000扩展版无限无限无限无限3.1 LINGO程序框架LINGO可以求解线性规划、二次规划、非线性规划、整数规划、图论及网络最优化问题和最大最小求解问题，以及排队论模型中最优化等问题．一个LINGO程序一般会包括以下几个部分：（1) 集合段:集部分是LINGO模型的一个可选部分．在LINGO模型中使用集之前，必须在集部分事先定义．集部分以关键字“sets：”开始，以“endsets”结束．一个模型可以没有集部分，或有一个简单的集部分,或有多个集部分．一个集部分可以放置于模型的任何地方，但是一个集及其属性在模型约束中被引用之前必须先定义．（2）数据段：在处理模型的数据时，需要为集部分定义的某些元素在LINGO求解模型之前为其指定值．数据部分以关键字“data:”开始，以关键字“enddata"结束．（3) 目标和约束段：这部分用来定义目标函数和约束条件等．该部分没有开始和结束的标记．主要是要用到LINGO的内部函数，尤其是与集合有关的求和与循环函数等．（4)初始段:这个部分要以关键字“INIT：”开始，以关键字“ENDINIT"结束，它的作用是对集合的属性定义一个初值．在一般的迭代算法中，如果可以给一个接近最优解的初始值，会大大减少程序运行的时间．（5）数据预处理段：这一部分是以关键字“CALC:”开始，以关键字“ENDCALC”结束．它的作用是把原始数据处理成程序模型需要的数据，它的处理是在数据段输入完以后、开始正式求解模型之前进行的，程序语句是按顺序执行的．3.2 LINGO中集合的概念在对实际问题建模的时候，总会遇到一群或多群相联系的对象，比如工厂、消费者群体、交通工具和雇工等等．LINGO允许把这些相联系的对象聚合成集（sets）．一旦把对象聚合成集，就可以利用集来最大限度地发挥LINGO建模语言的优势．现在将深入介绍如何创建集，并用数据初始化集的属性．3.2。

酒店房客的最优分配1. 常规策略1.1模型建立记两类房客分别为k=1(标准间）和k=2（商务间），星期一到星期日为i （或j ，l ）=1到i （或j,l ）=7,k 类房客的需求单上（表1和表2）从第i 天入住到第j 天的房间数为j i k d ,,，k 类客房的报价单上（表3和表4）从第i 天入住到第j 天的价格为j i k R ,,，k 类房间第l 天的可提供量（表5）为l k C ,。

设分配k 类客房从第i 天入住到第j 天的房间数为j i k X ,,，这是问题的决策变量。

以酒店收入为最大目标，可以建立如下的整数线性规划模型。

,,,,,,,max j i k ki k j i k X R ∑,7,...,2,1,.;2,1,,,,,==≤j i d tX S K j i k j i k 9∑∈),(),,(,l k s j i k j i =≤),(,,,,l k S C X l k j i k ｛(k,i,j)/i ≤l ≤j ｝,k=1,2;l=1,2, (7),2,1,;2,1,2,1,0,,===≥j i j i k X j i k ；整数，…,7首先对这个模型做几点解释，第一个约束表示两类客房的分配量都不应超出各自的需求量，当然，由于分配量越大收入越大，所以当以收入最大为目标时，分配会尽量满足需求；第2个约束要求在连续若干天入住时，每天分配的房间数都不应超过当天房间的提供量，其中S(k,l)表示这样一些从i 到j 的集合，如S （1,3）=｛（1,1,3），（1,1,4），（1,1,5），（1,1,6）,(1,1,7),(1,2,3),(1,2,4)（1,2,5）（1,2,6）（1,2,7）,(1,3,3),(1,3,4),(1,3,5),(1,3,6），（1,3,7）｝，另外，按照符号下标的定义应有i ≤j,但是考虑到编程计算简单起见，不做这样的规定,而只需当i>j 时令j i k d ,,=0，按照约束条件自然就有)(0,,j i X j i k 〉=。

例7.7 分配问题（指派问题，Assignment Problem ）这是个给n 个人分配n 项工作以获得某个最高总效果的问题。

第i 个人完成第j 项工作 需要平均时间c ij 。

要求给每个人分配一项工作，并要求分配完这些工作，以使完成全部任 务的总时间为最小。

该问题可表示如下：minij ni ij x c ∑=1s.t. ∑==⋯=n i ij x 1n;,1,2,j ,1∑==⋯=n j ij x 1n;,1,2,i ,1 i ij x n;,1,2,j ,1,0⋯==显然，此问题可看作是运输问题的特殊情况。

可将此问题看作具有n 个源和n 个汇的问 题，每个源有1 单位的可获量，而每个汇有1 单位的需要量。

从表面看，这问题要求用整数规划以保证xij 能取0 或1。

然而，幸运的是，此问题是运输问题的特例，因此即使不限制xij取0 或1 ，最优解也将取0 或1。

如果把婚姻看作分配问题，丹茨证明，整数性质证明一夫一妻会带来最美满幸福的生活！显然，分配问题可以作为线性规划问题来求解，尽管模型可 能很大。

例如，给100 人分配100 项工作将使所得的模型具有10000 个变量。

这时，如采用专门算法效果会更好。

时间复杂度为O(n3) 的匈牙利算法便是好选择，这是由Kuhu （1955） 提出的。

现举一例： 若某单位指派工人做某工作的完成时间表如下：问应如何指派任务，使完成任何的总时间最少？model:!7 个工人，7 个工作的分配问题;sets:workers/w1..w7/;jobs/j1..j7/;links(workers,jobs): cost,volume;endsets!目标函数;min=@sum(links: cost*volume);!每个工人只能有一份工作;@for(workers(I):@sum(jobs(J): volume(I,J))=1;);!每份工作只能有一个工人;@for(jobs(J):@sum(workers(I): volume(I,J))=1;);data:cost= 6 2 6 7 4 2 54 95 3 8 5 85 2 1 9 7 4 37 6 7 3 9 2 72 3 9 5 7 2 65 5 2 2 8 11 49 2 3 12 4 5 10;enddataend计算的部分结果为：Global optimal solution found at iteration: 14Objective value: 18.00000Variable Value Reduced Cost COST( W1, J1) 6.000000 0.000000 COST( W1, J2) 2.000000 0.000000 COST( W1, J3) 6.000000 0.000000 COST( W1, J4) 7.000000 0.000000 COST( W1, J5) 4.000000 0.000000 COST( W1, J6) 2.000000 0.000000 COST( W1, J7) 5.000000 0.000000 COST( W2, J1) 4.000000 0.000000 COST( W2, J2) 9.000000 0.000000 COST( W2, J3) 5.000000 0.000000 COST( W2, J4) 3.000000 0.000000COST( W2, J6) 5.000000 0.000000 COST( W2, J7) 8.000000 0.000000 COST( W3, J1) 5.000000 0.000000 COST( W3, J2) 2.000000 0.000000 COST( W3, J3) 1.000000 0.000000 COST( W3, J4) 9.000000 0.000000 COST( W3, J5) 7.000000 0.000000 COST( W3, J6) 4.000000 0.000000 COST( W3, J7) 3.000000 0.000000 COST( W4, J1) 7.000000 0.000000 COST( W4, J2) 6.000000 0.000000 COST( W4, J3) 7.000000 0.000000 COST( W4, J4) 3.000000 0.000000 COST( W4, J5) 9.000000 0.000000 COST( W4, J6) 2.000000 0.000000 COST( W4, J7) 7.000000 0.000000 COST( W5, J1) 2.000000 0.000000 COST( W5, J2) 3.000000 0.000000 COST( W5, J3) 9.000000 0.000000 COST( W5, J4) 5.000000 0.000000 COST( W5, J5) 7.000000 0.000000 COST( W5, J6) 2.000000 0.000000 COST( W5, J7) 6.000000 0.000000 COST( W6, J1) 5.000000 0.000000 COST( W6, J2) 5.000000 0.000000 COST( W6, J3) 2.000000 0.000000 COST( W6, J4) 2.000000 0.000000 COST( W6, J5) 8.000000 0.000000 COST( W6, J6) 11.00000 0.000000 COST( W6, J7) 4.000000 0.000000 COST( W7, J1) 9.000000 0.000000 COST( W7, J2) 2.000000 0.000000 COST( W7, J3) 3.000000 0.000000 COST( W7, J4) 12.00000 0.000000 COST( W7, J5) 4.000000 0.000000 COST( W7, J6) 5.000000 0.000000 COST( W7, J7) 10.00000 0.000000 VOLUME( W1, J1) 0.000000 4.000000 VOLUME( W1, J2) 0.000000 0.000000 VOLUME( W1, J3) 0.000000 3.000000 VOLUME( W1, J4) 0.000000 4.000000 VOLUME( W1, J5) 1.000000 0.000000 VOLUME( W1, J6) 0.000000 0.000000VOLUME( W2, J1) 0.000000 2.000000 VOLUME( W2, J2) 0.000000 7.000000 VOLUME( W2, J3) 0.000000 2.000000 VOLUME( W2, J4) 1.000000 0.000000 VOLUME( W2, J5) 0.000000 4.000000 VOLUME( W2, J6) 0.000000 3.000000 VOLUME( W2, J7) 0.000000 3.000000 VOLUME( W3, J1) 0.000000 5.000000 VOLUME( W3, J2) 0.000000 2.000000 VOLUME( W3, J3) 0.000000 0.000000 VOLUME( W3, J4) 0.000000 8.000000 VOLUME( W3, J5) 0.000000 5.000000 VOLUME( W3, J6) 0.000000 4.000000 VOLUME( W3, J7) 1.000000 0.000000 VOLUME( W4, J1) 0.000000 5.000000 VOLUME( W4, J2) 0.000000 4.000000 VOLUME( W4, J3) 0.000000 4.000000 VOLUME( W4, J4) 0.000000 0.000000 VOLUME( W4, J5) 0.000000 5.000000 VOLUME( W4, J6) 1.000000 0.000000 VOLUME( W4, J7) 0.000000 2.000000 VOLUME( W5, J1) 1.000000 0.000000 VOLUME( W5, J2) 0.000000 1.000000 VOLUME( W5, J3) 0.000000 6.000000 VOLUME( W5, J4) 0.000000 2.000000 VOLUME( W5, J5) 0.000000 3.000000 VOLUME( W5, J6) 0.000000 0.000000 VOLUME( W5, J7) 0.000000 1.000000 VOLUME( W6, J1) 0.000000 4.000000 VOLUME( W6, J2) 0.000000 4.000000 VOLUME( W6, J3) 1.000000 0.000000 VOLUME( W6, J4) 0.000000 0.000000 VOLUME( W6, J5) 0.000000 5.000000 VOLUME( W6, J6) 0.000000 10.00000 VOLUME( W6, J7) 0.000000 0.000000 VOLUME( W7, J1) 0.000000 7.000000 VOLUME( W7, J2) 1.000000 0.000000 VOLUME( W7, J3) 0.000000 0.000000 VOLUME( W7, J4) 0.000000 9.000000 VOLUME( W7, J5) 0.000000 0.000000 VOLUME( W7, J6) 0.000000 3.000000 VOLUME( W7, J7) 0.000000 5.000000Row Slack or Surplus Dual Price1 18.00000 -1.0000002 0.000000 -5.0000003 0.000000 -5.0000004 0.000000 -3.0000005 0.000000 -5.0000006 0.000000 -5.0000007 0.000000 -4.0000008 0.000000 -5.0000009 0.000000 3.00000010 0.000000 3.00000011 0.000000 2.00000012 0.000000 2.00000013 0.000000 1.00000014 0.000000 3.00000015 0.000000 0.000000 00000。