基于LINGO11.0的會(huì)議籌備目標(biāo)規(guī)劃模型

林 斌

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 租借會(huì)議室和租用客車

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié) 語

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

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

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

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

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

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

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

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