數(shù)學(xué)建模論文會議籌備最優(yōu)化

1、2009高教社杯全國大學(xué)生數(shù)學(xué)建模競賽承 諾 書我們仔細閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則 .我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題 .我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出 .我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性 .如有違反競賽規(guī)則的行為，我們將受到嚴肅處理 .我們參賽選擇的題號是（從a/b/c/d中選擇一項填寫）： d 我們的參賽報名號為（如

2、果賽區(qū)設(shè)置報名號的話）： 所屬學(xué)校（請?zhí)顚懲暾娜?瀘州職業(yè)技術(shù)學(xué)院 參賽隊員 (打印并簽名) ：1 . 2 . 3 . 指導(dǎo)教師或指導(dǎo)教師組負責(zé)人 (打印并簽名)： 日期：2009年 9 月 14日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：2009高教社杯全國大學(xué)生數(shù)學(xué)建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號）：會議籌備最優(yōu)化一. 摘要在激烈的市場競爭中,隨著市場經(jīng)濟在中國大陸的不斷發(fā)展，各種新興行業(yè)也在悄然而起 .會議服

3、務(wù)公司通過對賓館客房、租借會議室、租用客車接送代表等幾塊服務(wù)，讓顧客覺得經(jīng)濟、方便同時使?jié)M意度達到最高，會議服務(wù)公司需要從公司的經(jīng)濟利益和社會聲譽等諸多因素來考慮,在此,我們運用線性規(guī)劃和概率統(tǒng)計的知識，來解決對賓館客房分配問題 .會議的經(jīng)濟安排從預(yù)定房間的量和安排的合理性來決定;在安排客車接送會議代表運用運籌學(xué)分成幾條路線;服務(wù)公司的社會聲譽在市場競爭中是非常重要的,在此我們用會議代表對總體的滿意度來衡量我們應(yīng)用概率統(tǒng)計的知識，得出參加會議人員大約為661人 .根據(jù)與會人員對住房的要求，我們設(shè)計了第一個模型，且有3個方案，第一個方案利用lingo軟件計算得其無解 ，同樣利用lingo軟件計算

4、得最優(yōu)解.通過調(diào)整第一類單人間住房的人數(shù)建立模型二，得出所有與會代表住房安排，此時得出住房費的最少價格為80630元 .對模型二進一步優(yōu)化，通過對賓館調(diào)整，把與會代表集中按排在、賓館 .利用“中心極限”定理，計算得出可能出現(xiàn)空床費賠償?shù)母怕蚀蠹s是12%.同樣應(yīng)用“中心地址”的算法確定開會會議賓館定為、賓館 .用運籌學(xué)的知識確定出接送與會代表路線，并安排出了接送的車輛類型和數(shù)量關(guān)鍵詞：線性規(guī)劃 概率統(tǒng)計 lingo 中心地址 運籌學(xué)二. 問題重述某市的一家會議服務(wù)公司負責(zé)承辦某專業(yè)領(lǐng)域的一屆全國性會議，會議籌備組要為與會代表預(yù)訂賓館客房，租借會議室，并租用客車接送代表 .由于預(yù)計會議規(guī)模龐大，而

5、適于接待這次會議的幾家賓館的客房和會議室數(shù)量均有限，所以只能讓與會代表分散到若干家賓館住宿 .為了便于管理，除了盡量滿足代表在價位等方面的需求之外，所選擇的賓館數(shù)量應(yīng)該盡可能少，并且距離上比較靠近 .籌備組經(jīng)過實地考察，篩選出10家賓館作為備選，它們的名稱用代號至表示，相對位置見附圖，有關(guān)客房及會議室的規(guī)格、間數(shù)、價格等數(shù)據(jù)見附表1 .根據(jù)這屆會議代表回執(zhí)整理出來的有關(guān)住房的信息見附表2 .從以往幾屆會議情況看，有一些發(fā)來回執(zhí)的代表不來開會，同時也有一些與會的代表事先不提交回執(zhí)，相關(guān)數(shù)據(jù)見附表3 .附表2，3都可以作為預(yù)訂賓館客房的參考 .需要說明的是，雖然客房房費由與會代表自付，但是如果預(yù)訂

6、客房的數(shù)量大于實際用房數(shù)量，籌備組需要支付一天的空房費，而若出現(xiàn)預(yù)訂客房數(shù)量不足，則將造成非常被動的局面，引起代表的不滿 .會議期間有一天的上下午各安排6個分組會議，籌備組需要在代表下榻的某幾個賓館租借會議室 .由于事先無法知道哪些代表準備參加哪個分組會，籌備組還要向汽車租賃公司租用客車接送代表 .現(xiàn)有45座、36座和33座三種類型的客車，租金分別是半天800元、700元和600元 . 我們通過數(shù)學(xué)建模方法，從經(jīng)濟、方便、代表滿意等方面，為會議籌備組制定一個預(yù)訂賓館客房、租借會議室、租用客車的合理方案 .附表1 10家備選賓館的有關(guān)數(shù)據(jù)賓館代號客房會議室規(guī)格間數(shù)價格（天）規(guī)模間數(shù)價格(半天)普

7、通雙標間50180元200人11500元商務(wù)雙標間30220元150人21200元普通單人間30180元 60人2 600元商務(wù)單人間20220元普通雙標間50140元130人21000元商務(wù)雙標間35160元180人11500元豪華雙標間a30180元 45人3 300元豪華雙標間b35200元 30人3 300元普通雙標間50150元200人11200元商務(wù)雙標間24180元100人2800元普通單人間27150元150人11000元60人3320元普通雙標間50140元150人2900元商務(wù)雙標間45200元50人3300元普通雙標間a35140元150人21000元普通雙標間b3516

8、0元180人11500元豪華雙標間40200元50人3 500元普通單人間40160元160人11000元普通雙標間40170元180人11200元商務(wù)單人間30180元精品雙人間30220元普通雙標間50150元140人2 800元商務(wù)單人間40160元 60人3 300元商務(wù)套房（1床）30300元200人11000元普通雙標間a40180元160人11000元普通雙標間b40160元130人2 800元高級單人間45180元普通雙人間30260元160人11300元普通單人間30260元120人2800元豪華雙人間30280元200人11200元豪華單人間30280元經(jīng)濟標準房（2床）5

9、5260元180人11500元標準房（2床）45280元140人21000元附表2 本屆會議的代表回執(zhí)中有關(guān)住房要求的信息（單位：人）合住1合住2合住3獨住1獨住2獨住3男154104321076841女784817592819說明：表頭第一行中的數(shù)字1、2、3分別指每天每間120160元、161200元、201300元三種不同價格的房間 .合住是指要求兩人合住一間 .獨住是指可安排單人間，或一人單獨住一個雙人間 .附表3 以往幾屆會議代表回執(zhí)和與會情況第一屆 第二屆 第三屆 第四屆 發(fā)來回執(zhí)的代表數(shù)量315356408711發(fā)來回執(zhí)但未與會的代表數(shù)量89115121213未發(fā)回執(zhí)而與會的代表

10、數(shù)量576975104附圖(其中500等數(shù)字是兩賓館的距離)（與間距300米） （與間距300米） （與間距300米） （與間距300米） （與間距300米） （與間距300米） （與間距300米） 1000500300150200300（與間距300米） （與間距300米） （與間距300米） 300700150三. 模型假設(shè) 1. 假設(shè)模型一中滿足所有與會代表的回執(zhí)要求；2. 假設(shè)與會代表參加每組會議是隨機的；3. 假設(shè)本屆與會代表參加會議人數(shù)服從往屆參加會議人數(shù)規(guī)律；4. 假設(shè)每個與會代表每半天只開一次會議，且會議地點相同；5. 假設(shè)每半天所開會議的主題都一致；7假設(shè)每條路線車輛只搭載同

11、一條路線的與會代表 . 四. 符號說明為第i個賓館所住的與會代表的第j種類型住房人數(shù)；為參加會議人數(shù)的總頻率； 為回執(zhí)且與會代表的頻率（i取1，2，3，4）；為未回執(zhí)且與會代表的比例（i取1，2，3，4）；m為找賓館中心地址問題的矩陣；表示a賓館到b賓館c會議室的與會人數(shù) .五建立與分析模型一：通過觀察附表2可以得到本屆回執(zhí)人數(shù)總共為755人，由往屆會議代表的回執(zhí)和與會情況可得知本屆與會人數(shù)的概率 .因此我們假定模型如下：設(shè)為與會的總頻率為回執(zhí)且與會的頻率（i取1，2，3，4）為未回執(zhí)且與會的比例（i取1，2，3，4）與會人數(shù)的頻率：有回執(zhí)且與會人數(shù)的頻率 未回執(zhí)且與會人數(shù)的比例 通過以往一、

12、二、三、四會議代表回執(zhí)和與會情況，利用統(tǒng)計分析法，可計算出以往幾屆參加會議人數(shù)的的平均概率，通過平均概率推算本屆與會代表的總?cè)藬?shù) .本屆與會人數(shù)：為了使預(yù)定的房間數(shù)達到最優(yōu)，使得空房數(shù)量最小，支付空房會達到最小優(yōu)化 .我們以661人來進行預(yù)定房間，我們假設(shè)有三種方案 .方案一:我們?yōu)榱藵M足各代表的要求,且達到經(jīng)濟，結(jié)合表一: 表一客房價格范圍合住1120-161x21 x22 x31 x41 x51 x52 x71 x83房間數(shù)50 35 50 50 35 35 50 40合住2161-202x11 x23 x24 x32 x42 x53 x62 x83 房間數(shù)50 30 35 24 45 4

13、0 40 40合住3201-300x12 x64 x73 x91 x93 x101 x102房間數(shù)30 30 30 30 30 55 45單住1120-160x33 x61 x72房間數(shù)27 40 40單住2161-200x13 x63 x83房間數(shù)30 30 45單住3201-300x14 x92 x94房間數(shù)20 30 30 利用表一我們建立模型并求解 約束條件：單人間： 兩人間：s.t. 運用計算機計算出結(jié)果，并對解進行數(shù)據(jù)分析發(fā)現(xiàn)方案一無解 .因為第一種價格范圍的單間數(shù)和與會人員的回執(zhí)信息矛盾 .例如在約束條件下則不能滿足與會人員的要求 . 賓館的單間數(shù)在代表要求的房間數(shù)數(shù)量上不能滿足

14、,則我們在考慮到經(jīng)濟和盡量使與會代表滿意的情況下,建議代表住雙人間,即方案二:將的118人在滿足了40人之后,考慮到與會人員對賓館的品質(zhì)要求 .把剩下的78名分到和,這樣在品質(zhì)要求方面讓與會人員達到最大的滿意，建立模型:約束條件：單人間： 兩人間：s.t. 運用計算機軟件計算，計算結(jié)果見附錄表一，并對解進行數(shù)據(jù)分析。在盡量使與會代表滿意同時使經(jīng)濟可以接受的情況下，我們考慮使離會議室相對集中以及使會議室與預(yù)定賓館在距離上較近，利用“中心地址”進行預(yù)定賓館 。由于、賓館在距離上都較遠，我們?yōu)榱朔奖闩c會代表參加會議采用就近原則，只在、中選取 .即方案三：約束條件：單人間： 兩人間：s.t. 運用計算

15、機軟件計算，并對解進行數(shù)據(jù)分析?？紤]到與會人員滿意問題，我們可以預(yù)算床位數(shù) .考慮實際到會人數(shù)在預(yù)計人數(shù)661人左右，而造成無賓館床位可以下塌，引起與會人員的不滿，造成會議籌備處的社會聲譽受損，可以多定一些床位，以保證到會人員能安心下榻的概率不小于0 .90 .因為實際到會人數(shù)是一個隨機變量，服從二項分布，設(shè)預(yù)定床位數(shù)為k .由于755太大，可以考慮用中心極限定理，用正態(tài)分布去逼近，的近似分布為，所以有，查表得，得 故可以考慮預(yù)定673個床位 .如果籌備處允許的空床床位數(shù)在5床以內(nèi),則在預(yù)定床位673的情況下,至少應(yīng)該到達的人數(shù)668人,則出現(xiàn)空床的概率為則籌備處出現(xiàn)空床賠償?shù)母怕蚀蠹s為12%

16、 .模型二：應(yīng)用圖論的方法找出其圖形的中心點 . .用floyd算法求出距離矩陣 .計算在各點設(shè)立與會人員接送的最大量服務(wù)距離 . .求出頂點 .使 . 則就是建立會議場的最佳選擇 .，根據(jù)7，8賓館的會議室的設(shè)置，各選三個會議室，具體為7賓館的價格為800元，規(guī)模是140人，兩個；價格為1000元，規(guī)模為200人，一個 .8賓館價格為1000元，規(guī)模為160人，一個；價格為800元，規(guī)模為130人，兩個 .對于方案二，為了考慮各賓館的與會代表到會議地點的距離長短，來建立一個總距離目標函數(shù)的線性規(guī)劃模型：對該模型我們設(shè)表示a賓館到b賓館的c會議室的人數(shù)，則目標函數(shù)為： s.t. 運用計算機軟件

17、計算，模型求解見附錄表二 類似地方案三所用的總距離：目標函數(shù)為：s.t.運用計算機軟件計算，模型求解見附錄表三方案二所用車費模型:通過對各賓館會議室路線進行分析，分為到7，8兩賓館的兩條路線 .發(fā)現(xiàn)對3賓館的與會代表全部到8賓館參加會議；5賓館的與會代表全部到7賓館參加會議 .分別對3，5的與會人數(shù)安排乘車，5賓館與會代表到7賓館會議只需安排一輛3類車和一輛1類車；3賓館與會代表到8賓館會議室只需一輛3類車，所需總費用是2000元 .設(shè)為第類型車（）表示住在第m賓館與會代表到第n賓館會議人數(shù):根據(jù)模型和使用lingo計算得具體數(shù)據(jù)，見附錄表四分析求解數(shù)據(jù)得：需要4輛1類車，但不經(jīng)濟，我們進行人

18、為優(yōu)化，需要3輛1類車，1輛3類車；需要費用3000元需要4輛1類車，但不經(jīng)濟，我們進行人為優(yōu)化，需要3輛1類車，1輛3類車,需要費用3000元需要三輛1類車，但不經(jīng)濟，我們進行人為優(yōu)化，需要2輛一類車和1輛三類車: 需要2200元；需要3輛1類車，但不經(jīng)濟，我們進行人為優(yōu)化，需要2輛一類車和1輛三類車: 需要費用2200元；需要1輛一類車和1輛三類車:所需總費用1400元五模型求解方案二的最優(yōu)解：global optimal solution found at iteration: 17 objective value: 81600 .00 variable value reduced co

19、st x11 0 .000000 0 .000000 x12 43 .00000 0 .000000 x13 9 .000000 0 .000000 x14 20 .00000 0 .000000 x21 33 .00000 0 .000000 x22 0 .000000 10 .00000 x23 53 .00000 0 .000000 x24 0 .000000 10 .00000 x31 0 .000000 75 .00000 x32 0 .000000 0 .000000 x33 27 .00000 0 .000000 x41 100 .0000 0 .000000 x42 0 .00

20、0000 10 .00000 x51 70 .00000 0 .000000 x52 0 .000000 10 .00000 x53 0 .000000 10 .00000 x61 118 .0000 0 .000000 x62 80 .00000 0 .000000 x63 30 .00000 0 .000000 x64 0 .000000 0 .000000 x71 0 .000000 5 .000000 x72 0 .000000 0 .000000 x73 0 .000000 190 .0000 x81 0 .000000 0 .000000 x82 0 .000000 10 .000

21、00 x83 45 .00000 0 .000000 x91 0 .000000 20 .00000 x92 30 .00000 0 .000000 x93 0 .000000 30 .00000 x94 3 .000000 0 .000000 x101 0 .000000 20 .00000 x102 0 .000000 30 .00000 row slack or surplus dual price 1 81600 .00 -1 .000000 2 0 .000000 -160 .0000 3 0 .000000 -180 .0000 4 0 .000000 -280 .0000 5 0

22、 .000000 -70 .00000 6 0 .000000 -90 .00000 7 0 .000000 -110 .0000 8 100 .0000 0 .000000 9 17 .00000 0 .000000 10 21 .00000 0 .000000 11 0 .000000 60 .00000 12 67 .00000 0 .000000 13 70 .00000 0 .000000 14 7 .000000 0 .000000 15 70 .00000 0 .000000 16 100 .0000 0 .000000 17 48 .00000 0 .000000 18 0 .

23、000000 10 .00000 19 0 .000000 0 .000000 20 90 .00000 0 .000000 21 0 .000000 0 .000000 22 70 .00000 0 .000000 23 40 .00000 0 .000000 24 0 .000000 5 .000000 25 0 .000000 0 .000000 26 60 .00000 0 .000000 27 100 .0000 0 .000000 28 40 .00000 0 .000000 29 30 .00000 0 .000000 30 80 .00000 0 .000000 31 80 .

24、00000 0 .000000 32 0 .000000 0 .000000 33 60 .00000 0 .000000 34 0 .000000 20 .00000 35 80 .00000 0 .000000 36 27 .00000 0 .000000 37 110 .0000 0 .000000 38 90 .00000 0 .000000 對方案二求解,把x61調(diào)至x93,x91,其余不變 .81600-78160+30280+9260=79860(元)但還需加車費用10400元,會議費10400元,所以總費用為:79860+10400+10400=100660(元)同樣利用方案二

25、的解，解答方案三則住房費用為:81600-781602715050140+50150+27160+30280+9260=80630(元)會議費10400元 .而在方案三中,去掉了3,4,10之后距離就很近了,則為了經(jīng)濟節(jié)約,就不需要派車接送與會代表了,可省去車費,所以總費用為:80630+10400=91030(元)六模型檢驗通過對模型的求解,由于方案一對第一類房間單人間要求人數(shù)共有166人,而符合這個價位的房間數(shù)只有107間,因此方案一無解,所以我們通過對x61的約束條件取消，得到模型一的第二種方案,得x61要求住118人，而房間數(shù)只有40間，所以我們對多余的78人分到x91,x93，以達到

26、分配的合理 .為了滿足賓館數(shù)盡量減少和距離集中的條件下，我們對3，4，賓館的人數(shù)進行調(diào)整，x33有27人，將其全部調(diào)置到x72中；x41有100人，將其全部調(diào)置到x71中，得到第三套方案 .對于第三套方案的是從經(jīng)濟，方便和使代表滿意三方面來考慮建立最優(yōu)模型，但美中不足的是第三套方案會有部分單人間的代表要被安排到雙人間獨住 .七模型評價對于方案一，由于賓館單人間第一類房間少于與會代表的要求數(shù)量，所以模型無解 .對于方案二，從最優(yōu)經(jīng)濟的角度考慮，是最優(yōu)模型，但沒有從距離考慮，且有少數(shù)代表不能達到要求 .對于方案三，是從經(jīng)濟，方便和使代表滿意三方面綜合來考慮建立最優(yōu)模型，但美中不足的是第三套方案會有

27、部分單人間的代表要被安排到雙人間獨住 .由于各賓館的距離最多在450米，所以此方案可以省去租車接送代表的費用，更加的經(jīng)濟 .八是從經(jīng)濟，方便和使代表滿意三方面來考慮建立最優(yōu)模型，但美中不足的是第三套方案會有部分單人間的代表要被安排到雙人間獨住 .八參考文獻陶謙坎 汪應(yīng)洛 運籌學(xué)與系統(tǒng)分析 全國高等教育自學(xué)考試指導(dǎo)委員會 機械工業(yè)出版社 1999年7月楊啟帆等 數(shù)學(xué)建模 高等教育出版社 2004年12月王兵團 數(shù)學(xué)建模基礎(chǔ) 清華大學(xué)出版社九附錄附表一zmin=90*x11+110*x12+180*x13+220*x14+70*x21+80*x22 +90*x23+100*x24+75*x31+9

28、0*x32+150*x33+70*x41 +100*x42+70*x24+75*x31+90*x32+150*x33+70*x41 +180*x63+110*x64+75*x71+160*x72+300*x73+90*x94 +130*x101+140*x102 x33+x61+x72=145 x13+x63+x83=84 x14+x92+x94=53x21+x22+x41+x51+x52+x71+x82=203x11+x23+x24+x32+x42+x53+x62+x81=133x12+x64+x73+x91+x93+x101+x102=43x11=100x12=60x13=30x14=20

29、x21=100x22=70x23=60x24=70x31=100x32=48x33=27x41=100x42=90x51=70x52=70x53=40x62=80x63=30x71=100x72=40x73=30x81=80x82=80x83=45x91=60x92=30x93=60x94=30x101=110x102=90global optimal solution found at iteration: 17 objective value: 81600 .00 variable value reduced cost x11 0 .000000 0 .000000 x12 43 .000

30、00 0 .000000 x13 9 .000000 0 .000000 x14 20 .00000 0 .000000 x21 33 .00000 0 .000000 x22 0 .000000 10 .00000 x23 53 .00000 0 .000000 x24 0 .000000 10 .00000 x31 0 .000000 75 .00000 x32 0 .000000 0 .000000 x33 27 .00000 0 .000000 x41 100 .0000 0 .000000 x42 0 .000000 10 .00000 x51 70 .00000 0 .000000 x52 0 .000000 10 .00000 x53 0 .000000 10 .00000 x61 118 .0000 0 .000000 x62 80 .00000 0 .000000 x63 30 .00000 0 .000000 x64 0 .000000