会议筹备的最优化模型

会议筹备的最优化模型

摘要：本文对会议筹划一问题利用0-1线性规划模型、MATLAB、灰色

预测GM（1,1）等方法进行讨论，从经济、方便、代表满意等方面着手，在一些合理的假设下，制定出一个预订宾馆客房，租借会议室、租用客车的合理方案。最后指出模型中没有考虑进去的因素，提出了优化改进方案，以符合实际的要求。

关键字：会议筹备，0-1线性规划，MATLAB,灰色预测GM（1,1）

1.问题重述

1.1背景

某市的一家会议服务公司负责承办某专业领域的一届全国性会议，会议筹备组要为与会代表预订宾馆客房，租借会议室，并租用客车接送代表。由于预计会议规模庞大，而适于接待这次会议的几家宾馆的客房和会议室数量均有限，所以只能让与会代表分散到若干家宾馆住宿。为了便于管理，除了尽量满足代表在价位等方面的需求之外，所选择的宾馆数量应该尽可能少，并且距离上比较靠近。 1.2 相关情况

筹备组经过实地考察，筛选出10家宾馆作为备选，它们的名称用代号①至⑩表示，相对位置见附图，有关客房及会议室的规格、间数、价格等数据见附表1。

根据这届会议代表回执整理出来的有关住房的信息见附表2。从以往几届会议情况看，有一些发来回执的代表不来开会，同时也有一些与会的代表事先不提交回执，相关数据见附表3。附表2，3都可以作为预订宾馆客房的参考。

需要说明的是，虽然客房房费由与会代表自付，但是如果预订客房的数量大于实际用房数量，筹备组需要支付一天的空房费，而若出现预订客房数量不足，则将造成非常被动的局面，引起代表的不满。

会议期间有一天的上下午各安排6个分组会议，筹备组需要在代表下榻的某几个宾馆租借会议室。由于事先无法知道哪些代表准备参加哪个分组会，筹备组还要向汽车租赁公司租用客车接送代表。现有45座、36座和33座三种类型的客车，租金分别是半天800元、700元和600元。

附表1：有关客房及会议室的规格、间数、价格等数据； 附表2：这届会议代表回执整理出来的有关住房的信息； 附表3：以往几届会议代表回执和与会情况； 附图： 10家宾馆代号①至⑩的相对位置。 1.3问题提出

从题目要求出发，主要需要解决三个问题模型： （1）对本届会议与会代表的人数进行预测；

（2）测定在哪些宾馆预订哪类客房及预订各类客房的数量，并确定需要预订各类客房的数量；

（3）测定在哪些宾馆预订哪些类型的会议室以及租车的规格和数量。

2.符号说明

Q：表示本届会议代表与会总人数；

A ：表示发来回执的代表人数；

B ：表示发来回执但未与会的代表人数；

C ：表示未发来回执而与会的代表人数；

xij：为第i宾馆满足j挡住房要求的房间数；

ci：为第i宾馆所能提供的房间总数；

：租用45座客车的数量；

：租用36座客车的数量；

：租用33座客车的数量；

yij：为i宾馆至j宾馆距离；

3.模型（1）的解答

3.1模型（1）的假设

（1）假设与会代表完全服从主办方安排

（2）假设与会代表由于无特殊原因临时无法到达 （3）假设与会代表都无其他主观原因 3.2模型（1）的分析

由于从以往几届会议情况看，有一些发来回执的代表不来开会，同时也有一些与会的代表事先不提交回执，所以要根据附表3对这届的与会代表人数进行预测。根据灰色GM（1,1）及最小二乘拟合这两种方法，对这届发来回执但未与会的代表数及未发回执但与会的代表数进行预测，进而利用包络灰预测方法可求得结果。 3.3模型（1）的建立与求解

根据往届参加会议的情况，采用灰色预测GM（1,1）模型，预测本届的实际与会人数，而且对于上述模型问题的假设可以通过下面模型求解； 采用灰色预测GM（1,1）模型:

根据附表3，按GM模型建模机理，建GM（1,1）包络灰平面和主模型。 可由附表3

(0)(0)x(k)x构成的数建立模型为1=（89,105,121,137）；2(k)=

（66,115,164,213）；

根据GM（1,1）模型求解：

累加得x

(0)

(1)

(k)=（89,194,315,452），求得均值为z(k)=（141.5,254.4,383.5）。

(1)(0)(1)

z(k)+b=x(0)(k) x(k)z(k)根据灰微分方程+a=b-a

令数据向量Y=（105；121；137），系数矩阵B=[-141.5,1；-254.5,1；-383.5,1]，

参数向量U=[a；b]；由此可得Y=BU。

ˆ=（BTB）BTY，再由MATLAB软件可计算出 由最小二乘法可到得到的U

ˆ）=（-0.1320 86.6919） ˆ=（aˆ bU

(1)(1)

根据白微分方程dt+ax(t)=u得

ˆ(k1)x(1)ex

由此得出

(1)(0)

ˆa

ak



ˆ （k=0 1 2 3 4） a

ˆ(1)(2)=149.2325；xˆ(1)（3）=314.3142；xˆ(1)（4）=451.3404；xˆ(1)（5）ˆ(1)(1)89；xx

ˆ(1)（k）-xˆ(1) （k=2 3 4） ˆ(0)（1）=x=607.7021经过一次减法运算x

ˆ(0)（1）=89；xˆ(0)（2）=105.23205；xˆ(0)（3）=120.0871；xˆ(0)（4）=137.0262；x

ˆ(0)（5）=285.4969 x

既可以得到预测区间（156 285）；

1(0)(0)(0)

由包络中轴组成的数列x中=（x1(0)+x2）得：x中=（77.5,110,142.5,175）

2

(0)

根据上述求解预测值的步骤可得x中（5）=219.4055

ˆ(0)(k)x(0)(k)x由残差ε（k）=检验可得： (0)

x(k)

当k=1,2,3,4时，ε（k）均

ˆ(0)（5）=126，经检验精确度相对较高； 直接采用GM(1,1)模型求解得x

结果分析：根据A-B+C=Q，既可以得出这届会议的实际与会代表人数Q=629.

4、模型（2）的解答 2.1模型的假设

（1）假设未发回执的代表对住房没有要求。

（2）假设对单独住的代表可以接受住双人间。 （3）假设代表对住房的价格没有要求。 2.2模型的分析

（1）通过以往几届的会议住房记录，有些代表对住房的单双人的要求有出路，导致我们预定的单双人间，导致浪费，产生很多空房，导致会议的预算超出，所以我们希望通过0——1线性规划模型来改善这个问题。0——1线性规划顾名思义即规划的决策变量X的值只取0或1.

（2）模型说明：这是0——1规划问题，当我们面对的对象只有两总结果时，通常引入0——1变量来考虑。

（3）用0——1变量Xij表示分配情况，Xij=1表示指派第i个同学完成第j项任务，

Xij=0表示不派任务。则可以建立如右所示模型： MinZ=

10



xij1,j1,2,3,4,5,6,7,8,9,10,i1

10S.t。

x1,i1,2,3,4,5,6,7,8,9,10,x0,1;ijijj1

cx

i1j1

1010

ijij

2.3模型建立与求解

（1）确定需预定的宾馆个数以及对应的宾馆x的0—1线性规划模型

在线性规划问题中，有些最优解必需是整数，即为整数规则。整数规划与组合最优化从广泛的意义上说，两者的领域是一致的，都是在有限个可供选择的方案中，寻找满足一定标准的最好方案。 针对本问题有以下原则：

原则1：从已有10个宾馆中选取最少数量的宾馆，能安排所有参会代表入住。 原则2：所选择宾馆要能够满足有住房需要的参会代表入住各档次房间。其中4,5,6

元三种不同价格的房间。合住是指要求两人合住一间。独住是指可安排单人间，或一人单独住一个双人间(注4,5，6为独住，1，2,3为合住)

原则3：所选择宾馆有足够床位能安排全部参会代表入住。 在此将问题描述为一个0——1线性规划模型：

0,当i宾馆未选中时

选择决策变量bi=

1，当i宾馆选中时目标函数：minbi

i110

10



bixijdi,j1,2,3

i1

1010bixijbixij3didj3,j1,2,3i1i1

10约束条件：s。t bici423i1

bi0,1

应用Matlab求解结果为

Optimization terminated.

b=0 1 0 0 0 1 1 1 0 0 Fval= 4

由此可见，目标函数在最优解处的值为4，即表示至少需要4问宾馆。 （2）考虑宾馆距离并改进后的0——1非线性规划模型 依题意得宾馆距离领接矩阵：

，其中yij为i宾馆至j宾馆距离，见表1：

Yij=（yij）

在模型二基础上添加原则4：在不改变宾馆数目的前提下，使得所选宾馆两两间距离之和最小。

在此将问题描述为一个0——1非线性规划模型：

0,当i宾馆未选中时

选择决策变量bi=

1，当i宾馆选中时 目标函数：min

bi

i1

10

min约束条件：

bby

ij

i1j1

1010

ij

10



bixijdi,j1,2,3

i1

1010bixijbixij3didj3,j1,2,3i1i1

10

S.t

bc423iii1

bi0,1

这是一个具有多个0——1决策变量的多目标非线性整数规划，我们用遗传算

法求解。

首先，使用对目标函数加权的方法将多目标优化问题转化问题，转化后模型为：

目标函数：min bibibjyij，其中为惩罚因子，为一个较大的正数。

i1

i1j1

10

10

10

约束条件：

10



bixijdi,j1,2,3

i1

1010bixijbixij3didj3,j1,2,3i1i1

10S.t bici423i1

bi0,1

对此模型应用MATLAB的遗传算法即可求解，求解结果为： b=1 1 0 0 0 0 1 1 0 0 Fval= 4

5、模型（3）的解答

5.1模型（3）的假设

（1）假设每天的上下午6个会议都在相同的会议室。

（2）假设每个会议代表参加哪个分组会的可能性是相等的。

（3）假设出租车在接送会议代表的过程中不会出现长时间的交通阻塞。 （4）假设会议人员到与会场所是否通过路口不会影响到会议宾馆的安排。

（5）假设被安排住在宾馆的代表不会无故缺席会议，即住在宾馆的代表人数近似为参加会议的人数。 5.2模型（3）的分析

会议日程中分组会议时每个人等概率参加分组，因此需要预定会议室6个，每个会议室参加的人数为105人左右，因此6个会议因在4个宾馆内预定。由于排除了其他主观及客观原因，上一个模型已经确定了合理的宾馆，所以对会议室及车辆的安排以车辆最省时间、会议室足够大和接送与会代表用时最少为原则。 5.3模型（3）的建立与求解

在这届会议期间，由模型的假设，只考虑半天的安排，在预定宾馆的基础上，对分组会议人数的确定分两种情况进行考虑。 （1）与会代表参加会议人数以会议规模为准

租用客车的半天租金比租赁会议室的半天费用要高很多，因此不租车应是最优安排。我们在1、2、5、7每个宾馆都租赁会议室，在这个宾馆住的就在这个宾馆开会。 可以设：

h11：表示宾馆1价格为1500元/半天会议室的租赁间数；

h12：表示宾馆1价格为1200元/半天会议室的租赁间数；

h13：表示宾馆1价格为600元/半天会议室的租赁间数；

h21：表示宾馆2价格为1000元/半天会议室的租赁间数； h22：表示宾馆2价格为1500元/半天会议室的租赁间数；

h23：表示宾馆2价格为300元/半天并容纳45人的会议室的租赁间数；

h24：表示宾馆2价格为300元/半天并容纳30人的会议室的租赁间数；

h51：表示宾馆5价格为1000元/半天会议室的租赁间数； h52：表示宾馆5价格为1500元/半天会议室的租赁间数； h53：表示宾馆5价格为500元/半天会议室的租赁间数；

h71：表示宾馆7价格为800元/半天会议室的租赁间数；

h72：表示宾馆7价格为300元/半天会议室的租赁间数；

h73：表示宾馆7价格为1000元/半天会议室的租赁间数； 以租赁会议室半天的总费用最少为目标，可得整数规划：

Min=1500h11+1200h12+600h13+1000h21+1500h22+300h23+300h24+1000h51+1500h52+500h53+800h71+300h72+1000h73 s.t.

200h11+150h12+60h13+130h21+180h22+45h23+30h24+150h51+180h52+50h53+140h71+60

h72+200h73655

200h11+150h12+60h13178 130h21+180h52+45h23+30h24174 150h51+180h52+50h53166 140h71+60h72+200h73137

h11+ h12+ h13+h21+h22+h23+h24+h51+h52+h53+h71+h72+h73=6

h11+ h12+ h131, h21+h22+h23+h241, h51+h52+h531, h71+h72+h731, h111, h12, h13,h212, h221, h23,h243, h512, h521, h533, h712,h723,h731

h11,h12,h13,h21,h22,h23,h24,h51,h52,h53,h71,h72,h73为非负整数。

解得h11 +h21 +h23+ h51+ h53 +h71=1，其余为0，即在宾馆1租借一个价格为1500/半天的会议室，在宾馆2租借一个价格为1000/半天的会议室、一个价格300元/半天并容纳45人的会议室，在宾馆5租借一个价格1000/半天的会议室和一个价格500元/半天的会议室，在宾馆7租借一个价格800/半天的会议室此时不需要租车，半天租借会议室的总费用为5100元，一天为10200元。

（2）会议人数平均分配

根据本届会议可能参加的人数为655人，计算出每个分组会议的人数大约为109人，即每个会议室的规模应大于109人。若还是在1、2、5、7每个宾馆都租借会议室，则必定有一个宾馆将租借2个会议室，这样到此宾馆开会的大约有220人，

而这4个宾馆居住的人数都不超过180人，因此筹备组必须要租用客车接送代表。 虽然租用客车的租金是以半天计算，但是考虑时间问题，问了避免代表迟到，假设每辆客车每半天只送两趟，并尽量让客车坐满，一个宾馆没载满可到其他宾馆载满，一趟可以送代表去不同的目的地。

如果6个会议室分别租借在4个宾馆，则有2个宾馆要租2个会议室或有1个宾馆要租3个会议室，用排列组合算出共有10种情况。

以宾馆1、2各租两个会议室，宾馆5、7各租1个会议室为例，建立模型： min=1500 h11+1200 h12+1000 h21 +1500 h22+1000 h51+1500 h52+800 h71+1000 h73 s．t

200 h11+150 h12+130 h21+180 h22+150 h51+180 h52+140 h71+200 h73655 h11+ h12+ h21+h22+h51+h52+h71+h73=6 h11+ h12=2，h21+h22=2，h51+h52=1，h71+h73=1

h111, h12, h212, h221, h512, h521，h712，h731 h11,h12, h21,h22, h51,h52, h71,h73为非负整数。

得h12=h21=2，h51=h52=1，其余的为0，目标函数最优解为6200元。但在宾馆5租借了一个会议室，须把166-109=57人送到宾馆1或2参加会议，同样也须把宾馆7的137-109=28送到宾馆1或2参加会议，于是又建立如下模型：

min=1500 h11+1200 h12+1000 h21 +1500 h22+1000 h51+1500 h52+800 h71+1000 h73+800+700+600 s．t

200h11+ 150h12+130h21+180h22+150h51+180h52+140h71+200h73655 h11+ h12+ h21+h22+h51+h52+h71+h73=6 h11+ h12=2，h21+h22=2，h51+h52=1，h71+h73=1 90+72+6657+28

h111, h12, h212, h221, h512, h521，h712，h731

h11,h12, h21,h22, h51,h52, h71,h73为非负整数。得h12=h21=2，h51= h71 =1，其余的为0，目标函数最优解为7000元。

其余9种情况同样建立规划可得，起计算结果见表5。

表5 在4个宾馆都租借会议室以及客车租用的情况

如果6个会议室租借在3个宾馆，则有4种情况，对于每一种情况，先不考虑要送的代表人数，求出租用会议室和租用客车至少所需的总费用，见表6.

如果6个会议室租借在两个宾馆，则至少有137+166=303位代表要送，租用客车至少需=2辆，=22辆，即需租金2800元，而不考虑任何限制，租6个规模

大于109人会议室最优点是h21+ h51+ h71=2，租金为5600元，这样半天总费用至少要8400元。

如果6个会议室都租借在同一个宾馆里，这是不能安排。

综上所述，要使总费用最少，应在宾馆1租借两个价格为1200/半天的会议室，应在宾馆2租借两个价格为1000/半天会议室，在宾馆5租借一个价格为1000/半天的会议室，在宾馆7租借一个价格为800/半天的会议室，并租用45座类型的客车一辆；或在宾馆1租借选择一个价格为1200元/半天的会议室，在宾馆2租借一个价格为1000元/半天的会议室，

在宾馆5租借一个价格为1000元/半天的会议室，在宾馆7租借两个价格为800元/半天的会议室，并租用33座类型的客车车辆，此时半天总费用都为7000元，一天就为14000元。

6.模型误差分析

在使用0—1规划模型时考虑只有两两宾馆之间的距离，没有考虑租用客车在红绿灯汽车花费的时间以后，车的停车，还有在短距离，可以考虑代表不用坐客车，与选用步行，可能花费的时间会更少，节约预算成本。还有在使用0—1线性规划模型中，的约束条件太少，不能全部正确仔细的反应出来的情况。

7.模型的评价与推广

7.1模型的评价

1.优点

（1）通过利用数学工具和 matlab编程的方法，严格地对模型求解，具有科学性。

（2）模型（一）中用到的灰色系统模型能够较好的对本届未发回执而与会的代表数量进行预测，且得到比较好的结果。

（3）建立的模型能与实际紧密联系，结合实际情况对所提出的问题进行求解，使模型更贴近实际，通用性、推广性较强。

2.不足

（1）一些数据中，我们对数据进行了必要的处理，如：取整数据、舍弃数据，这些方法可能会带来一定的误差。

（2）模型虽然考虑到了很多因素，但是为了建立模型，理想化了许多影响因素，具有一定的局限性，得到的最优方案可能与实际有一定的出入。

（3）回归分析是研究因变量与自变量之间变动比例关系的一种方法，最终结果一般是建立某种经验性的回归方程，使计算结果与实际数据存在一定误差。

7.2模型的推广

本文建立的三个模型解决了由多个因素决定的基本会议筹备的确定问题，采用了多因素分层解决问题的方法。因此，本模型还可应用与其他类似的由多个因素决定的解决方案问题，如：大学生寝室分配问题、市场评估、工程预算、城市最低生活保障、人口预测、国民生产总值的预测等，尤其对费用的预测方面的问题，更是简便易行，效果明显。

参考文献

[1] 姜启源，《数学模型》，北京：高等教育教育出版社，2003.

[2] 吴建国，《数学建模案例精编》，北京：中国水利水电出版社，2005.

[3] 韩中庚，《灰色预测模型【M】,数学建模方法及其应用》，北京：高等教育出版社，2005.

[4] 张志涌，《精通MATLAB6.5版》，北京：北京航空航天大学出版社，2003.

[5] 柬金龙 ，闻人凯《线性规划理论与模型应用》北京，科学出版社，2004.

附录1：模型（1）的程序：

>> y=[315 356 408 711];

>> x=[89 115 121 213];

>> plot(x,y,'*')

>> a=polyfit(x,y,1)

a =

3.3009 3.5353

>> hold on

>> plot(x,y,'*')

>> hold on

>> a=polyfit(x,y,1)

a = 附录

3.3009 3.5353

>> x1=polyval(a,x)

x1 =

297.3112 383.1334 402.9385 706.6169

>> hold on

>> plot(x,y,'*r',x,x1)

模型（2）的程序：

model:

sets:

house/1..10/:a;

room/1..6/:;

links(house,room)/1,6 1,3 1,1 1,2 2,6 2,3 2,4 2,5 3,6 3,3 3,1 4,6 4,3 5,4 5,5 5,6 6,1 6,6 6,2 6,4 7,6 7,2 7,1 8,4 8,5 8,1 9,6 9,1 9,4 9,2 10,4 10,5/:x,y,d,q,c,g,z;

link(house,house)

/1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9 1,10

2,1 2,2 2,3 2,4 2,5 2,6 2,7 2,8 2,9 2,10

3,1 3,2 3,3 3,4 3,5 3,6 3,7 3,8 3,9 3,10

4,1 4,2 4,3 4,4 4,5 4,6 4,7 4,8 4,9 4,10

5,1 5,2 5,3 5,4 5,5 5,6 5,7 5,8 5,9 5,10

6,1 6,2 6,3 6,4 6,5 6,6 6,7 6,8 6,9 6,10

7,1 7,2 7,3 7,4 7,5 7,6 7,7 7,8 7,9 7,10

8,1 8,2 8,3 8,4 8,5 8,6 8,7 8,8 8,9 8,10

9,1 9,2 9,3 9,4 9,5 9,6 9,7 9,8 9,9 9,10

10,1 10,2 10,3 10,4 10,5 10,6 10,7 10,8 10,9 10,10

/:s;

endsets

data:

x=50 30 30 20 50 35 30 35 50 24 27 50 45 35 35 40 40 40 30 30 50 40 30 40 40 45 30 30 30 30 55 45;

y=180 220 180 220 140 160 180 200 150 180 150 140 200 140 160 200 160 170 180 220 150 160 300 180 160 180 260 260 280 280 260 280;

s=0 150 700 650 600 600 300 500 650 1300 150 0 550 500 750 750 450 650 800 1450 700 550 0 200 1500 1300 1200 1000 1150 2000 650 500 200 0 1250 1250 950 1150 1300 1950 600 750 1500 1250 0 600 300 500 650 1300 600 750 1300 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 2000 1950 1300 700 1000 1200 850 0; enddata

min=@sum(house:a)+t;

t=@sum(link(i,j):a(i)*s(i,j)*a(j));

@for(house:@bin(a));

@for(links:@gin(d));

@for(links:@bin(c));

@for(links:@bnd(0,d,x));

@sum(links(i,j)|j #gt# 2 #and# y(i,j)#ge#120 #and# y(i,j)#le#160 : a(i)*c(i,j)*x(i,j))>=105;

@sum(links(i,j)|j #gt# 2 #and# y(i,j)#ge#120 #and# y(i,j)#le#160 : a(i)*c(i,j)*d(i,j))=105;

@sum(links(i,j)|j #gt# 2 #and# y(i,j)#ge#161 #and# y(i,j)#le#200 : a(i)*c(i,j)*x(i,j))>=69;

@sum(links(i,j)|j #gt# 2 #and# y(i,j)#ge#161 #and# y(i,j)#le#200 : a(i)*c(i,j)*d(i,j))=69;

@sum(links(i,j)|j #gt# 2 #and# y(i,j)#ge#201 #and# y(i,j)#le#300 : a(i)*c(i,j)*x(i,j))>=23;

@sum(links(i,j)|j #gt# 2 #and# y(i,j)#ge#201 #and# y(i,j)#le#300 : a(i)*c(i,j)*d(i,j))=23;

@for(links:@bin(g));

@for(links:@gin(z));

@for(links:@bnd(0,z,x));

@for(links(i,j):q(i,j)=@if(j #gt#

2,(x(i,j)-(d(i,j)*c(i,j))),x(i,j))); @sum(links(i,j)|y(i,j)#ge#120

y(i,j)#le#160 :a(i)*g(i,j)*q(i,j))>=149; @sum(links(i,j)|y(i,j)#ge#120 #and# a(i)*g(i,j)*z(i,j))=149;

@sum(links(i,j)|y(i,j)#ge#161 #and# a(i)*g(i,j)*q(i,j))>=86;

@sum(links(i,j)|y(i,j)#ge#161

y(i,j)#le#200 :a(i)*g(i,j)*z(i,j))=86; @sum(links(i,j)|y(i,j)#ge#201 #and# a(i)*g(i,j)*q(i,j))>=54;

@sum(links(i,j)|y(i,j)#ge#201 #and# a(i)*g(i,j)*z(i,j))=54;

@sum(links:c*d+z*g)=594;

end #and# y(i,j)#le#160 : y(i,j)#le#200 : #and# y(i,j)#le#300 : y(i,j)#le#300 :