會議籌備問題的多目標最優化模型

林斌

（溫州職業技術學院 公共教學部，浙江 溫州325035）

會議籌備問題的多目標最優化模型

林斌

（溫州職業技術學院 公共教學部，浙江 溫州325035）

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

會議籌備；多目標最優化；等可能假設；全局最優解

0引 言

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

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

1預定賓館客房

1.1預測與會代表總人數

對競賽D題給出的前幾屆會議代表回執和與會情況數據進行統計發現，發來回執但未與會的代表比例穩定，為30%，未發回執而與會的代表比例約為17.6%。與會代表比例、均值和方差見表1。

可以認為，發來回執未與會的代表比例和未發回執而與會的代表比例服從正態分布，并取置信度為95%，則應取置信區間下分位點作為發來回執未與會的代表預測數量，取置信區間上分位點作為未發回執而與會的代表預測數量。其計算公式[2]為：

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

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

表2未發回執而與會的代表比例的卡方檢驗

1.2多目標最優化模型的建立和求解

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

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

雙人間矩陣為：

低價房矩陣為：

中價房矩陣為：

高價房矩陣為：

其中，apij取非負整數，xzi取0或1。

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

2租借會議室和租用客車

2.1與會代表流動的等可能假設

表3賓館選擇和各類型客房預訂數量及價格

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

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

2.2會議室費用和車輛費用最優化模型的建立和求解

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

其中，haij和caij均取非負整數。

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

表4會議室和車輛安排的結果

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

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

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

表5車輛安排的改進方案

3結束語

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

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

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

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

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

[4]胡運權.運籌學教程[M].北京:清華大學出版社，2003:111-114.

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

[6]謝金星，邢文訓，王振波.網絡優化[M].2版.北京:清華大學出版社，2009:73-78.

[責任編輯：王瑋明]

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

溫州職業技術學院科研項目（WZY2009043）；溫州職業技術學院教學改革項目（WZYJG0912）

林斌（1979—），男，浙江溫嶺人，溫州職業技術學院公共教學部講師.