會議籌備問題的多目標最優(yōu)化模型

林斌

（溫州職業(yè)技術(shù)學(xué)院 公共教學(xué)部，浙江 溫州325035）

會議籌備問題的多目標最優(yōu)化模型

林斌

（溫州職業(yè)技術(shù)學(xué)院 公共教學(xué)部，浙江 溫州325035）

利用2009年全國大學(xué)生數(shù)學(xué)建模競賽D題的會議籌備問題，通過預(yù)測與會代表總?cè)藬?shù)和合理的住宿安排方案，建立預(yù)訂賓館客房的多目標最優(yōu)化模型；在租借會議室和租用客車上采用等可能假設(shè)，并給出費用的最優(yōu)化模型。最后利用LINGO9.0得出會議籌備總費用的全局最優(yōu)解。

會議籌備；多目標最優(yōu)化；等可能假設(shè)；全局最優(yōu)解

0引 言

會議籌備問題是2009年全國大學(xué)生數(shù)學(xué)建模競賽D題，要求參賽隊伍為會議籌備組制定一個預(yù)訂賓館客房、租借會議室、租用客車的合理方案。同時，競賽D題給出了兩類數(shù)據(jù)：一是前幾屆會議代表回執(zhí)和與會情況及本屆會議代表回執(zhí)中有關(guān)住房要求的信息，包含獨住、合住、對房間的價位要求。二是會議籌備組經(jīng)過實地考察，篩選出10家備選賓館的相對位置以及各賓館客房和會議室的規(guī)格、間數(shù)、價格等數(shù)據(jù)。

通過初步分析可以發(fā)現(xiàn)，會議籌備問題的解題思路是多目標最優(yōu)化分析[1]，即預(yù)定賓館客房在滿足與會代表住房要求的前提下不僅要使空房費用最低，而且賓館數(shù)量應(yīng)該盡可能少、距離上比較靠近；會議室的安排上必須先給出各賓館間與會代表流動的合理假設(shè)。最后利用LINGO9.0簡化編程并高效求解。

1預(yù)定賓館客房

1.1預(yù)測與會代表總?cè)藬?shù)

對競賽D題給出的前幾屆會議代表回執(zhí)和與會情況數(shù)據(jù)進行統(tǒng)計發(fā)現(xiàn)，發(fā)來回執(zhí)但未與會的代表比例穩(wěn)定，為30%，未發(fā)回執(zhí)而與會的代表比例約為17.6%。與會代表比例、均值和方差見表1。

可以認為，發(fā)來回執(zhí)未與會的代表比例和未發(fā)回執(zhí)而與會的代表比例服從正態(tài)分布，并取置信度為95%，則應(yīng)取置信區(qū)間下分位點作為發(fā)來回執(zhí)未與會的代表預(yù)測數(shù)量，取置信區(qū)間上分位點作為未發(fā)回執(zhí)而與會的代表預(yù)測數(shù)量。其計算公式[2]為：

表1與會代表比例、均值和方差

將數(shù)據(jù)代入上式計算得到與會代表總數(shù)為685.25人，向上取整數(shù)為686人，其中發(fā)來回執(zhí)且與會的代表539人，未發(fā)回執(zhí)而與會的代表147人。同時對方差較大的未發(fā)回執(zhí)而與會的代表比例進行正態(tài)分布的卡方檢驗[3]（見表2），證實其假設(shè)的合理性。

表2未發(fā)回執(zhí)而與會的代表比例的卡方檢驗

1.2多目標最優(yōu)化模型的建立和求解

賓館選擇上要保證使空房費用最低，可安排先來的有獨住要求的與會代表入住各價位的高價客房，這樣可保證無獨住要求的部分不會出現(xiàn)空房。空房費用的計算只考慮發(fā)來回執(zhí)的代表中有獨住要求的人數(shù)，可取該部分預(yù)計人數(shù)的置信區(qū)間寬度作為空房數(shù)量并向上取整數(shù)；同時取各個價位的最小值來預(yù)計空房費用，得到空房費用為1 650元。要求最低價客房所在賓館至少有一個，得到6號賓館必選，2號賓館和4號賓館至少有一個。預(yù)訂客房數(shù)量上首先應(yīng)考慮男女不混住同一客房，得到預(yù)測與會代表總?cè)藬?shù)中發(fā)來回執(zhí)的代表需要預(yù)定賓館客房389間，其中，雙人間158間，單人間231間。然后，再安排未發(fā)回執(zhí)而與會的代表入住有雙人間要求的代表客房中的空床位，則可求出預(yù)測與會代表總?cè)藬?shù)中未發(fā)回執(zhí)而與會的代表至少需要預(yù)定賓館客房65間，其中雙人間至少13間。合計得出，預(yù)訂賓館客房總數(shù)最小值為454間。

預(yù)訂賓館和客房在數(shù)量上要盡量少。由于任意3個賓館的客房數(shù)最多為420間，小于需要預(yù)訂客房總數(shù)最小值的454間，那么至少需要預(yù)訂4個賓館。如果預(yù)訂4個賓館可行，還要求4個賓館之間的距離之和達到最小。

雙人間矩陣為：

低價房矩陣為：

中價房矩陣為：

高價房矩陣為：

其中，apij取非負整數(shù)，xzi取0或1。

編制LINGO程序并調(diào)試運行，得到全局唯一最優(yōu)解[5]為：選中1號、2號、6號、7號賓館，客房總數(shù)最少為454間，距離最短為2.55km。賓館選擇和各類型客房預(yù)訂數(shù)量及價格見表3。

2租借會議室和租用客車

2.1與會代表流動的等可能假設(shè)

表3賓館選擇和各類型客房預(yù)訂數(shù)量及價格

由于未知哪些代表準備參加哪個分組會議，因而根據(jù)實際經(jīng)驗，可合理假設(shè)代表的流動服從等可能假設(shè)，即任意一個代表選擇去任意一個賓館參加會議的概率只和該賓館的會議室數(shù)量成正比，而與會議內(nèi)容無關(guān)；并且在同一個賓館里，任意一個代表選擇任意一個會議室的概率只和該會議室的容量成正比。

記會議室安排變量haij（取非負整數(shù)），流動比例lbij表示從第i個賓館流向第j個賓館的比例，則lbij在等可能假設(shè)下的計算公式為：

2.2會議室費用和車輛費用最優(yōu)化模型的建立和求解

目標函數(shù)為會議室費用和車輛費用之和達到最小，約束條件有兩個：一是任意一個會議室的容量必須大于或等于流入的與會代表人數(shù)；二是任意一個賓館發(fā)出的車輛座位總數(shù)必須大于或等于該賓館流出的與會代表人數(shù)。在車輛安排上可先考慮與會代表的滿意度，即讓各賓館同時發(fā)車。

其中，haij和caij均取非負整數(shù)。

編制LINGO程序并把多目標最優(yōu)化模型得到的最優(yōu)值當(dāng)作約束條件添加進來，會議室費用和車輛費用之和最小值的全局最優(yōu)解為27 000元，會議室安排唯一，車輛安排總數(shù)唯一，即45個座位和33個座位各6輛，但各賓館發(fā)車情況不唯一，客房預(yù)訂數(shù)量也不唯一。會議室和車輛安排的結(jié)果見表4。

表4會議室和車輛安排的結(jié)果

2.3車輛安排的改進及會議籌備總費用的控制

會議籌備總費用由空房費用、會議室費用和車輛費用組成，可求得為28 650元。顯然，總費用值偏大，分析后認為是由于車輛費用偏高造成的。考慮到兩家賓館最遠的距離也不超出1km，開會準備時間很短，與會代表完全可以接受稍微延長的幾分鐘，那么不必每個賓館都要同時發(fā)車，這樣可減少車輛數(shù)量。

根據(jù)最大網(wǎng)絡(luò)流原理[6]，讓1號賓館發(fā)車去2號賓館，到2號賓館下的人數(shù)大于2號賓館去7號賓館的人數(shù)，因而2號賓館不用發(fā)車。依此類推，得到車輛安排的改進方案（見表5）。經(jīng)過改進后的車輛費用降低至7 200元，相應(yīng)的會議籌備總費用降低至19 050元。

表5車輛安排的改進方案

3結(jié)束語

會議籌備問題的最優(yōu)解依賴于多個因素，既有符合實際情況的數(shù)學(xué)假設(shè)和數(shù)學(xué)建模上的困難，如等可能假設(shè)不一定最合理；也有軟件編程和計算速度的困擾，如對LINGO9.0參數(shù)設(shè)置不熟悉，那么程序運行時間會很長。因此，選擇合理的假設(shè)和合適的容許誤差找出最優(yōu)化結(jié)果是允許的。

對會議室和車輛的安排只考慮了費用目標，對出行人數(shù)、乘車距離和與會代表滿意度等其他目標沒有進一步深入考慮；而且在車輛安排上只給出了各賓館同時發(fā)車情況下的最優(yōu)解，沒有考慮更為一般情況下的優(yōu)化模型。以上這些均存在欠缺，是今后要進一步思考和研究的方向。

[1]謝金星，薛毅.優(yōu)化建模與LINDO/LINGO軟件[M].北京:清華大學(xué)出版社，2005:322-340.

[2]盛驟，謝式千，潘承毅.概率論與數(shù)理統(tǒng)計[M].北京:高等教育出版社，2002:169-172.

[3]袁新生，邵大宏，郁時煉.LINGO和EXCEL在數(shù)學(xué)建模中的應(yīng)用[M].北京:科學(xué)出版社，2007:157-161.

[4]胡運權(quán).運籌學(xué)教程[M].北京:清華大學(xué)出版社，2003:111-114.

[5]唐煥文，秦學(xué)志.實用最優(yōu)化方法[M].3版.大連:大連理工大學(xué)出版社，2004:7-9.

[6]謝金星，邢文訓(xùn)，王振波.網(wǎng)絡(luò)優(yōu)化[M].2版.北京:清華大學(xué)出版社，2009:73-78.

[責(zé)任編輯：王瑋明]

Multi-objective Optimization Model of Conference Preparation

LIN Bin
(Public Courses Department, Wenzhou Vocational &Technical College, Wenzhou, 325035, China)

In the light of the conference preparation problems in D item of China College Students Mathematical Modeling Contest of 2009, a multi-objective optimization model of hotel reservation is built after forecasting the total number of participants and making a reasonable accommodation plan. As for renting conference rooms and cars, the equal probability hypothesis is applied and an optimization model of fare is obtained. Finally a global optimal solution of total cost is found by using LINGO9.0.

Conference preparation; Multi-objective optimization; Equal probability hypothesis; Global optimal solution

book=1,ebook=11

O 221.6

A

1671-4326(2010)01-0044-03

2009-10-07

溫州職業(yè)技術(shù)學(xué)院科研項目（WZY2009043）；溫州職業(yè)技術(shù)學(xué)院教學(xué)改革項目（WZYJG0912）

林斌（1979—），男，浙江溫嶺人，溫州職業(yè)技術(shù)學(xué)院公共教學(xué)部講師.