基于LINGO11.0的会议筹备目标规划模型

林 斌

(温州职业技术学院 公共教学部,浙江 温州 325035)

0 引 言

2009年全国大学生数学建模竞赛高职高专组的D题是会议筹备问题,题中给出了10家备选宾馆的房间、会议室和相对位置等信息,并统计出了发来回执代表的住房要求、以往几届会议的情况和租用客车等相关数据,要求通过数学建模方法,从经济、方便、代表满意等方面,为会议筹备组制定一个预订宾馆客房、租借会议室、租用客车的合理方案。

显然,会议筹备问题属于目标规划,解题的思路是在满足代表住房要求、会议室容量等多个约束条件下同时达到宾馆数量最少、会议费用最低以及代表满意度最高等多个目标。同时,应首选优化软件LINGO11.0来求解,LINGO11.0擅长处理含有整数变量的优化模型,其编程简便、计算准确并且速度快。

1 预订宾馆和客房

1.1 预测与会代表总人数

根据以往4届代表回执和与会情况,可知与会代表人数由发来回执和未发回执两部分组成。通过统计,发现与会代表人数和发来回执数量之间存在着比较稳定的比例关系,这个比例约为87.58%。因此,可根据这个重要关系来预测本届代表总人数,给定置信度95%,可取平均值87.58%的置信区间上分位点89.49%作为本届代表总人数占发来回执数量的比例,置信区间分位点的计算公式为[1]:

再换算并向上取整可得出本届与会代表总人数的预测值为676人,其中发来回执代表人数为540人,未发回执代表人数为136人,以往4届与会代表人数占发来回执数量的比例以及本届总人数预测值见下表:

表1 与会代表人数占发来回执数量的比例以及本届总人数预测值

1.2 目标规划模型的建立和求解

宾馆的选择要在满足代表住房要求前提下达到宾馆和房间数量最少、空房费最低和各宾馆距离最短的目标。

考虑男女不混住,利用与会代表人数的预测值可折算出发来回执部分的住房要求,在全部予以满足时可得发来回执代表所需的房间数至少为390间,其中双人间至少159间,单人间最多231间;再假定未发回执代表没有住房要求,先住满发来回执代表的房间,得到未发回执代表所需房间数至少60间,最多116间,且双人间至少3间,单人间最多113间,两部分合计得房间总数的最少值为450间。

由于任意3个宾馆的房间数最多为420间,小于最少预订数450间,可知宾馆数量至少需要4个。在保证房间数量后,各宾馆间的距离之和还要尽量小。

考虑空房费最低要求空房数量少且房价低的因素,可安排先来的有独住要求的代表先住各价位的高价房,其他代表先独住,这样可保证无独住要求部分不会出现空房。空房费的计算只考虑发来回执的代表里有独住要求的人数,可取该部分预计人数的置信区间宽度作为空房数量并向上取整;同时,取各个价位的最小值来预计空房费,得到空房费为1 790元。由最低价房间所在宾馆至少有一个,得到6号宾馆必选,2号宾馆和4号宾馆至少有一个。

记房间数量矩阵 fs10×4(行标表示宾馆,列标表示房间规格),有要求的住房预订数量矩阵yq2×3(行标表示独住或合住,列标表示价位),宾馆间距离矩阵 jl10×10(对称阵),

该目标规划模型可采用序贯式算法求解[3],即按照规划目标的优先级依次计算。编制LINGO程序并调试运行,得到模型的全局最优解为[4]:宾馆选择1号、2号、6号、7号,房间数最优值450间,距离最短2 550 m,但房间预订不唯一,其中一个解为:

表2 宾馆房间预订结果

2 租借会议室和租用客车

2.1 代表流动的等概率假设和最优化模型

会议室和客车的安排要在满足会议室容量和客车运力的约束下达到上下午会议总费用最低。

会议室的位置和容量取决于代表的选择,所以需要对各宾馆间代表的流动作出合理假设。由于事先未知哪些代表准备参加哪个分组会议,可认为各代表对各分组会议的偏好程度相同,从而得出代表流动的等概率假设:任意一位代表选择去任意一个宾馆参加会议的概率只和该宾馆的会议室租借数量成正比,而与会议内容无关;并且在同一个宾馆里,任意一位代表选择任意一个会议室的概率只和该会议室的容量成正比。

记会议室安排变量 haij(取非负整数),流动比例lbij表示从第i个宾馆流向第j个宾馆的代表人数占第i个宾馆代表人数的比例,则 lbij在等概率假设下的计算式为:

会议室和客车安排的约束条件有两个,一是任意一个会议室的容量必须大于等于流入的与会代表人数,二是任意一个宾馆发出的客车座位总数必须大于等于该宾馆流出的代表人数。但满足客车安排约束条件的方案不唯一,各宾馆的始发客车和中途停靠客车都是可行解,可先考虑代表满意度最高,即让各宾馆同时发车。

记会议室容量矩阵 hr10×4,会议室数量矩阵hs10×4,会议室价格矩阵 hj10×4,客车座位矩阵cz1×3(按座位多到少),客车价格矩阵 cj1×3,并引入客车安排变量caij表示从第i个宾馆发出的第j种类型的客车数 (取非负整数),建立起代表流动等概率假设下的会议室和客车安排最优化模型如下:

把宾馆和房间安排的最优值作为约束条件添加到会议室和客车安排的最优化模型中,编制LINGO程序并设置合理的优化参数,求解得到会议室费用和客车费用之和最小值的全局最优解为26 800元,会议室安排结果唯一,客车安排总数唯一即45座5辆、36座1辆、33座6辆,但各宾馆发车情况不唯一,房间预订结果也不唯一,会议室和客车安排结果见下表:

表3 会议室和客车安排结果

2.2 总费用和客车安排的改进

会议筹备的总费用由空房费、会议室费用、客车费用组成,由前面两步计算结果可得会议筹备的总费用值为28 590元。

由于客车费用占总费用的比例最大,有必要对客车安排进行改进。注意到客车租用数量较多,而两宾馆最远的距离也不超出1 km,开车时间很短,完全不必要每个宾馆同时发车。如果让其中几个宾馆发出的客车在其他宾馆停靠上下客,开会准备时间延长不了多久,代表们是能接受的,这样可大大减少客车数量。

根据前面的客车安排结果,6号宾馆始发客车的运力是最大网络流[5],因此可让6号宾馆发车去2号宾馆,到2号宾馆下的代表人数大于2号宾馆去7号宾馆的代表人数,所以2号宾馆不用发车。如果让6号宾馆发出客车多走几趟,那么其他宾馆也可不用发车,但应控制开会准备时间最大值不超出半小时。制定合理的客车路线可满足时间要求,只安排6号宾馆发车是其中一种改进方案,得到客车安排的改进方案如下:

表4 客车安排的改进方案

经过改进后的客车费用降低到4 800元,会议筹备的总费用降低到16 790元。

会议结束时的客车安排是会议开始时客车安排的反问题,下午会议的客车安排是上午会议客车安排的重复,这些不再累述。

3 结 语

会议筹备问题的目标规划模型在求解上应采用序贯式算法,按各目标的优先级从高到低逐步计算,前一步的最优值要作为约束条件添加到后一步的程序中。同时,模型的LINGO程序运行时间较长可通过设置合理的优化参数来解决,在 “Integer Solver”里调整绝对误差值为1、相对误差值0.003并延时300秒,在 “Global Solver”里设定容许误差0.05,还有阀值等[6]。

在会议室和客车的安排上使用了代表流动的等概率假设来寻找最优解,但等概率假设和实际情况不完全符合,如代表在不知道会议内容时可能会选择离自己最近的宾馆去参加会议,还有代表可能偏向于把所有宾馆都参观一遍等,这些都要求目标函数和约束条件的更合理构造。另外,在客车安排上还应考虑所有代表的总体满意度,设计更好的方案使得各代表乘车时间的方差尽量小。这些方面都存在不足和遗漏,需要今后进一步思考和深入研究。

[1]盛骤,谢式千,潘承毅.概率论与数理统计[M].北京:高等教育出版社,2002.

[2]胡运权.运筹学教程[M].北京:清华大学出版社,2003.

[3]谢金星,薛毅.优化建模与LINDO/LINGO软件[M].北京:清华大学出版社,2005.

[4]唐焕文,秦学志.实用最优化方法[M].大连:大连理工大学出版社,2004.

[5]谢金星,邢文训,王振波.网络优化[M].北京:清华大学出版社,2009.

[6]袁新生,邵大宏,郁时炼.LINGO和EXCEL在数学建模中的应用[M].北京:科学出版社,2007