林 斌

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

0 引 言

2009年全國大學(xué)生數(shù)學(xué)建模競賽高職高專組的D題是會議籌備問題,題中給出了10家備選賓館的房間、會議室和相對位置等信息,并統(tǒng)計出了發(fā)來回執(zhí)代表的住房要求、以往幾屆會議的情況和租用客車等相關(guān)數(shù)據(jù),要求通過數(shù)學(xué)建模方法,從經(jīng)濟(jì)、方便、代表滿意等方面,為會議籌備組制定一個預(yù)訂賓館客房、租借會議室、租用客車的合理方案。

顯然,會議籌備問題屬于目標(biāo)規(guī)劃,解題的思路是在滿足代表住房要求、會議室容量等多個約束條件下同時達(dá)到賓館數(shù)量最少、會議費用最低以及代表滿意度最高等多個目標(biāo)。同時,應(yīng)首選優(yōu)化軟件LINGO11.0來求解,LINGO11.0擅長處理含有整數(shù)變量的優(yōu)化模型,其編程簡便、計算準(zhǔn)確并且速度快。

1 預(yù)訂賓館和客房

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

根據(jù)以往4屆代表回執(zhí)和與會情況,可知與會代表人數(shù)由發(fā)來回執(zhí)和未發(fā)回執(zhí)兩部分組成。通過統(tǒng)計,發(fā)現(xiàn)與會代表人數(shù)和發(fā)來回執(zhí)數(shù)量之間存在著比較穩(wěn)定的比例關(guān)系,這個比例約為87.58%。因此,可根據(jù)這個重要關(guān)系來預(yù)測本屆代表總?cè)藬?shù),給定置信度95%,可取平均值87.58%的置信區(qū)間上分位點89.49%作為本屆代表總?cè)藬?shù)占發(fā)來回執(zhí)數(shù)量的比例,置信區(qū)間分位點的計算公式為[1]:

再換算并向上取整可得出本屆與會代表總?cè)藬?shù)的預(yù)測值為676人,其中發(fā)來回執(zhí)代表人數(shù)為540人,未發(fā)回執(zhí)代表人數(shù)為136人,以往4屆與會代表人數(shù)占發(fā)來回執(zhí)數(shù)量的比例以及本屆總?cè)藬?shù)預(yù)測值見下表:

表1 與會代表人數(shù)占發(fā)來回執(zhí)數(shù)量的比例以及本屆總?cè)藬?shù)預(yù)測值

1.2 目標(biāo)規(guī)劃模型的建立和求解

賓館的選擇要在滿足代表住房要求前提下達(dá)到賓館和房間數(shù)量最少、空房費最低和各賓館距離最短的目標(biāo)。

考慮男女不混住,利用與會代表人數(shù)的預(yù)測值可折算出發(fā)來回執(zhí)部分的住房要求,在全部予以滿足時可得發(fā)來回執(zhí)代表所需的房間數(shù)至少為390間,其中雙人間至少159間,單人間最多231間;再假定未發(fā)回執(zhí)代表沒有住房要求,先住滿發(fā)來回執(zhí)代表的房間,得到未發(fā)回執(zhí)代表所需房間數(shù)至少60間,最多116間,且雙人間至少3間,單人間最多113間,兩部分合計得房間總數(shù)的最少值為450間。

由于任意3個賓館的房間數(shù)最多為420間,小于最少預(yù)訂數(shù)450間,可知賓館數(shù)量至少需要4個。在保證房間數(shù)量后,各賓館間的距離之和還要盡量小。

考慮空房費最低要求空房數(shù)量少且房價低的因素,可安排先來的有獨住要求的代表先住各價位的高價房,其他代表先獨住,這樣可保證無獨住要求部分不會出現(xiàn)空房?？辗抠M的計算只考慮發(fā)來回執(zhí)的代表里有獨住要求的人數(shù),可取該部分預(yù)計人數(shù)的置信區(qū)間寬度作為空房數(shù)量并向上取整;同時,取各個價位的最小值來預(yù)計空房費,得到空房費為1 790元。由最低價房間所在賓館至少有一個,得到6號賓館必選,2號賓館和4號賓館至少有一個。

記房間數(shù)量矩陣 fs10×4(行標(biāo)表示賓館,列標(biāo)表示房間規(guī)格),有要求的住房預(yù)訂數(shù)量矩陣yq2×3(行標(biāo)表示獨住或合住,列標(biāo)表示價位),賓館間距離矩陣 jl10×10(對稱陣),

該目標(biāo)規(guī)劃模型可采用序貫式算法求解[3],即按照規(guī)劃目標(biāo)的優(yōu)先級依次計算。編制LINGO程序并調(diào)試運行,得到模型的全局最優(yōu)解為[4]:賓館選擇1號、2號、6號、7號,房間數(shù)最優(yōu)值450間,距離最短2 550 m,但房間預(yù)訂不唯一,其中一個解為:

表2 賓館房間預(yù)訂結(jié)果

2 租借會議室和租用客車

2.1 代表流動的等概率假設(shè)和最優(yōu)化模型

會議室和客車的安排要在滿足會議室容量和客車運力的約束下達(dá)到上下午會議總費用最低。

會議室的位置和容量取決于代表的選擇,所以需要對各賓館間代表的流動作出合理假設(shè)。由于事先未知哪些代表準(zhǔn)備參加哪個分組會議,可認(rèn)為各代表對各分組會議的偏好程度相同,從而得出代表流動的等概率假設(shè):任意一位代表選擇去任意一個賓館參加會議的概率只和該賓館的會議室租借數(shù)量成正比,而與會議內(nèi)容無關(guān);并且在同一個賓館里,任意一位代表選擇任意一個會議室的概率只和該會議室的容量成正比。

記會議室安排變量 haij(取非負(fù)整數(shù)),流動比例lbij表示從第i個賓館流向第j個賓館的代表人數(shù)占第i個賓館代表人數(shù)的比例,則 lbij在等概率假設(shè)下的計算式為:

會議室和客車安排的約束條件有兩個,一是任意一個會議室的容量必須大于等于流入的與會代表人數(shù),二是任意一個賓館發(fā)出的客車座位總數(shù)必須大于等于該賓館流出的代表人數(shù)。但滿足客車安排約束條件的方案不唯一,各賓館的始發(fā)客車和中途?？靠蛙嚩际强尚薪?可先考慮代表滿意度最高,即讓各賓館同時發(fā)車。

記會議室容量矩陣 hr10×4,會議室數(shù)量矩陣hs10×4,會議室價格矩陣 hj10×4,客車座位矩陣cz1×3(按座位多到少),客車價格矩陣 cj1×3,并引入客車安排變量caij表示從第i個賓館發(fā)出的第j種類型的客車數(shù) (取非負(fù)整數(shù)),建立起代表流動等概率假設(shè)下的會議室和客車安排最優(yōu)化模型如下:

把賓館和房間安排的最優(yōu)值作為約束條件添加到會議室和客車安排的最優(yōu)化模型中,編制LINGO程序并設(shè)置合理的優(yōu)化參數(shù),求解得到會議室費用和客車費用之和最小值的全局最優(yōu)解為26 800元,會議室安排結(jié)果唯一,客車安排總數(shù)唯一即45座5輛、36座1輛、33座6輛,但各賓館發(fā)車情況不唯一,房間預(yù)訂結(jié)果也不唯一,會議室和客車安排結(jié)果見下表:

表3 會議室和客車安排結(jié)果

2.2 總費用和客車安排的改進(jìn)

會議籌備的總費用由空房費、會議室費用、客車費用組成,由前面兩步計算結(jié)果可得會議籌備的總費用值為28 590元。

由于客車費用占總費用的比例最大,有必要對客車安排進(jìn)行改進(jìn)。注意到客車租用數(shù)量較多,而兩賓館最遠(yuǎn)的距離也不超出1 km,開車時間很短,完全不必要每個賓館同時發(fā)車。如果讓其中幾個賓館發(fā)出的客車在其他賓館?？可舷驴?開會準(zhǔn)備時間延長不了多久,代表們是能接受的,這樣可大大減少客車數(shù)量。

根據(jù)前面的客車安排結(jié)果,6號賓館始發(fā)客車的運力是最大網(wǎng)絡(luò)流[5],因此可讓6號賓館發(fā)車去2號賓館,到2號賓館下的代表人數(shù)大于2號賓館去7號賓館的代表人數(shù),所以2號賓館不用發(fā)車。如果讓6號賓館發(fā)出客車多走幾趟,那么其他賓館也可不用發(fā)車,但應(yīng)控制開會準(zhǔn)備時間最大值不超出半小時。制定合理的客車路線可滿足時間要求,只安排6號賓館發(fā)車是其中一種改進(jìn)方案,得到客車安排的改進(jìn)方案如下:

表4 客車安排的改進(jìn)方案

經(jīng)過改進(jìn)后的客車費用降低到4 800元,會議籌備的總費用降低到16 790元。

會議結(jié)束時的客車安排是會議開始時客車安排的反問題,下午會議的客車安排是上午會議客車安排的重復(fù),這些不再累述。

3 結(jié) 語

會議籌備問題的目標(biāo)規(guī)劃模型在求解上應(yīng)采用序貫式算法,按各目標(biāo)的優(yōu)先級從高到低逐步計算,前一步的最優(yōu)值要作為約束條件添加到后一步的程序中。同時,模型的LINGO程序運行時間較長可通過設(shè)置合理的優(yōu)化參數(shù)來解決,在 “Integer Solver”里調(diào)整絕對誤差值為1、相對誤差值0.003并延時300秒,在 “Global Solver”里設(shè)定容許誤差0.05,還有閥值等[6]。

在會議室和客車的安排上使用了代表流動的等概率假設(shè)來尋找最優(yōu)解,但等概率假設(shè)和實際情況不完全符合,如代表在不知道會議內(nèi)容時可能會選擇離自己最近的賓館去參加會議,還有代表可能偏向于把所有賓館都參觀一遍等,這些都要求目標(biāo)函數(shù)和約束條件的更合理構(gòu)造。另外,在客車安排上還應(yīng)考慮所有代表的總體滿意度,設(shè)計更好的方案使得各代表乘車時間的方差盡量小。這些方面都存在不足和遺漏,需要今后進(jìn)一步思考和深入研究。

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

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

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

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

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

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