全國大學生數(shù)學建模競賽2009年D題_講解_清華大學_姜啟源 2課件

1、 題目題目 題目的背景題目的背景 問題分析和解決方法問題分析和解決方法 一種參考解法一種參考解法 對學生論文的評述對學生論文的評述 某市的一家會議服務(wù)公司負責承辦某專業(yè)領(lǐng)域的一屆全國性某市的一家會議服務(wù)公司負責承辦某專業(yè)領(lǐng)域的一屆全國性會議會議, 會議籌備組要為與會代表預(yù)訂賓館客房會議籌備組要為與會代表預(yù)訂賓館客房, 租借會議室租借會議室, 并租用并租用客車接送代表。由于預(yù)計會議規(guī)模龐大客車接送代表。由于預(yù)計會議規(guī)模龐大, 而適于接待這次會議的幾而適于接待這次會議的幾家賓館的客房和會議室數(shù)量均有限家賓館的客房和會議室數(shù)量均有限, 所以只能讓與會代表分散到若所以只能讓與會代表分散到若干家賓館住宿

2、。干家賓館住宿。為了便于管理為了便于管理, 除了盡量滿足代表在價位等方面的除了盡量滿足代表在價位等方面的需求之外需求之外, 所選擇的賓館數(shù)量應(yīng)該盡可能少所選擇的賓館數(shù)量應(yīng)該盡可能少, 并且距離上比較靠近。并且距離上比較靠近。 籌備組經(jīng)過實地考察籌備組經(jīng)過實地考察, 篩選出篩選出10家賓館作為備選家賓館作為備選, 它們的名稱它們的名稱用代號用代號至至表示表示, 相對位置見附圖相對位置見附圖, 有關(guān)客房及會議室的規(guī)格、有關(guān)客房及會議室的規(guī)格、間數(shù)、價格等數(shù)據(jù)見附表間數(shù)、價格等數(shù)據(jù)見附表1。 根據(jù)這屆會議代表回執(zhí)整理出來的有關(guān)住房的信息見附表根據(jù)這屆會議代表回執(zhí)整理出來的有關(guān)住房的信息見附表2。從以

3、往幾屆會議情況看從以往幾屆會議情況看, 有一些發(fā)來回執(zhí)的代表不來開會有一些發(fā)來回執(zhí)的代表不來開會, 同時也同時也有一些與會的代表事先不提交回執(zhí)有一些與會的代表事先不提交回執(zhí), 相關(guān)數(shù)據(jù)見附表相關(guān)數(shù)據(jù)見附表3。附表。附表2, 3都都可以作為預(yù)訂賓館客房的參考?？梢宰鳛轭A(yù)訂賓館客房的參考。題題 目目 需要說明的是，需要說明的是，雖然客房房費由與會代表自付，但是如果雖然客房房費由與會代表自付，但是如果預(yù)訂客房的數(shù)量大于實際用房數(shù)量，籌備組需要支付一天的空預(yù)訂客房的數(shù)量大于實際用房數(shù)量，籌備組需要支付一天的空房費，而若出現(xiàn)預(yù)訂客房數(shù)量不足，則將造成非常被動的局面，房費，而若出現(xiàn)預(yù)訂客房數(shù)量不足，則將造

4、成非常被動的局面，引起代表的不滿。引起代表的不滿。 會議期間有一天的上下午各安排會議期間有一天的上下午各安排6個分組會議，籌備組需要個分組會議，籌備組需要在代表下榻的某幾個賓館租借會議室。由于在代表下榻的某幾個賓館租借會議室。由于事先無法知道哪些事先無法知道哪些代表準備參加哪個分組會，代表準備參加哪個分組會，籌備組還要向汽車租賃公司租用客籌備組還要向汽車租賃公司租用客車接送代表?，F(xiàn)有車接送代表?，F(xiàn)有45座、座、36座和座和33座三種類型的客車，租金分座三種類型的客車，租金分別是半天別是半天800元、元、700元和元和600元。元。 請你們通過數(shù)學建模方法，從經(jīng)濟、方便、代表滿意等方請你們通過數(shù)

5、學建模方法，從經(jīng)濟、方便、代表滿意等方面，為會議籌備組面，為會議籌備組制定一個預(yù)訂賓館客房、租借會議室、租用制定一個預(yù)訂賓館客房、租借會議室、租用客車的合理方案?？蛙嚨暮侠矸桨?。附表1 10家備選賓館的有關(guān)數(shù)據(jù)附表2 本屆會議的代表回執(zhí)中有關(guān)住房要求的信息(單位：人)附表3 以往幾屆會議代表回執(zhí)和與會情況1000500300150200300 300700150附圖（其中附圖（其中500等數(shù)字是兩賓館間距，單位為米）等數(shù)字是兩賓館間距，單位為米）題目的背景題目的背景 20092009年年8 8月第十一屆全國數(shù)學建模教學與應(yīng)用會議在福月第十一屆全國數(shù)學建模教學與應(yīng)用會議在福州召開。這是一次規(guī)模龐

6、大的系列性學術(shù)會議州召開。這是一次規(guī)模龐大的系列性學術(shù)會議, , 據(jù)以據(jù)以往幾屆會議的情況看往幾屆會議的情況看, , 有以下共同的、明顯的特點：有以下共同的、明顯的特點： 與會代表多達數(shù)百人，而適于接待的賓館容量有限與會代表多達數(shù)百人，而適于接待的賓館容量有限,只能讓與會代表分散到若干家賓館住宿；只能讓與會代表分散到若干家賓館住宿； 有一些發(fā)來回執(zhí)的代表不來開會有一些發(fā)來回執(zhí)的代表不來開會, 也有一些與會代表也有一些與會代表事先不提交回執(zhí)事先不提交回執(zhí), 給預(yù)訂賓館客房數(shù)量造成了困難；給預(yù)訂賓館客房數(shù)量造成了困難； 雖然客房房費由與會代表自付雖然客房房費由與會代表自付, 但如預(yù)訂客房數(shù)量大但如

7、預(yù)訂客房數(shù)量大于實際數(shù)量于實際數(shù)量, 籌備組需要支付一天的空房費籌備組需要支付一天的空房費, 而若預(yù)訂而若預(yù)訂客房數(shù)量不足客房數(shù)量不足, 則將引起代表的強烈不滿；則將引起代表的強烈不滿； 若內(nèi)容不同的分組會分散在幾個賓館若內(nèi)容不同的分組會分散在幾個賓館, 而代表要參加而代表要參加哪個分組會無法預(yù)知哪個分組會無法預(yù)知, 因此需要派車在賓館間接送代表。因此需要派車在賓館間接送代表。 一些會議的籌備者和賓館的管理人員反映一些會議的籌備者和賓館的管理人員反映, 諸如上述諸如上述這些情況普遍存在、時常發(fā)生。這些情況普遍存在、時常發(fā)生。 通過數(shù)學建模方法通過數(shù)學建模方法, 從經(jīng)濟、方便、代表滿意等方面從經(jīng)

8、濟、方便、代表滿意等方面,為會議籌備者制定一個預(yù)訂賓館客房、租借會議室、為會議籌備者制定一個預(yù)訂賓館客房、租借會議室、租用客車的合理方案租用客車的合理方案, 是非常現(xiàn)實且很有實際意義的課是非?，F(xiàn)實且很有實際意義的課題題, 并且這方面的研究過去幾乎沒有。并且這方面的研究過去幾乎沒有。 為了保持問題的原汁原味為了保持問題的原汁原味, 賽題中所列賽題中所列10家賓館的家賓館的基本數(shù)據(jù)和相對位置基本數(shù)據(jù)和相對位置, 以及本屆會議代表回執(zhí)中有關(guān)以及本屆會議代表回執(zhí)中有關(guān)住房要求的信息都是真實的住房要求的信息都是真實的, 只是對一些賓館客房和只是對一些賓館客房和會議室的數(shù)量略作改動。關(guān)于前幾屆會議的代表回

9、執(zhí)會議室的數(shù)量略作改動。關(guān)于前幾屆會議的代表回執(zhí)和與會情況也基本上參考了歷史數(shù)據(jù)。和與會情況也基本上參考了歷史數(shù)據(jù)。題目的背景題目的背景 問題分析和解決方法問題分析和解決方法 從題目要求出發(fā)，主要需要解決三個問題：從題目要求出發(fā)，主要需要解決三個問題：1）預(yù)測本屆會議與會代表的數(shù)量）預(yù)測本屆會議與會代表的數(shù)量, 并確定需要并確定需要預(yù)訂各類客房的數(shù)量；預(yù)訂各類客房的數(shù)量；2）確定在哪些賓館預(yù)訂客房及預(yù)訂各類客房的）確定在哪些賓館預(yù)訂客房及預(yù)訂各類客房的數(shù)量；數(shù)量；3）確定在哪些賓館預(yù)訂哪些類型的會議室以及）確定在哪些賓館預(yù)訂哪些類型的會議室以及租車的規(guī)格和數(shù)量。租車的規(guī)格和數(shù)量。 問題問題1是

10、求解問題是求解問題2，3的前提，首先應(yīng)該根據(jù)附表的前提，首先應(yīng)該根據(jù)附表2，3的數(shù)據(jù)對本屆會議的數(shù)據(jù)對本屆會議與會代表的數(shù)量與會代表的數(shù)量進行預(yù)測。進行預(yù)測。 確定預(yù)訂確定預(yù)訂客房總量客房總量時，應(yīng)使會議籌備組在訂房上的時，應(yīng)使會議籌備組在訂房上的損失盡量小，損失包括：預(yù)訂客房數(shù)超過實際用量時損失盡量小，損失包括：預(yù)訂客房數(shù)超過實際用量時需要支付的一天空房費；預(yù)訂客房數(shù)不夠時引起代表需要支付的一天空房費；預(yù)訂客房數(shù)不夠時引起代表不滿的不滿的“費用費用”，后者要用適當?shù)臄?shù)學表達式加以量，后者要用適當?shù)臄?shù)學表達式加以量化。化。 根據(jù)附表根據(jù)附表2數(shù)據(jù)中本屆會議的代表所需要數(shù)據(jù)中本屆會議的代表所需要

11、6種類型種類型的客房的比例，可由預(yù)訂客房的總量得到預(yù)定的客房的比例，可由預(yù)訂客房的總量得到預(yù)定各類客各類客房的數(shù)量房的數(shù)量。問題分析和解決方法問題分析和解決方法 問題問題2主要應(yīng)考慮籌備組管理的方便及代表的滿意，主要應(yīng)考慮籌備組管理的方便及代表的滿意，如滿足代表在合住或獨住及價位方面的需求、預(yù)訂如滿足代表在合住或獨住及價位方面的需求、預(yù)訂的賓館總數(shù)盡量少、距離上盡量靠近等。的賓館總數(shù)盡量少、距離上盡量靠近等。 若建立優(yōu)化模型，可以用賓館總數(shù)最少為若建立優(yōu)化模型，可以用賓館總數(shù)最少為目標函目標函數(shù)數(shù)，以滿足代表在合住或獨住及價位方面的需求，以滿足代表在合住或獨住及價位方面的需求，及各賓館擁有客房

12、數(shù)量等為及各賓館擁有客房數(shù)量等為約束條件約束條件，以在哪幾家，以在哪幾家賓館訂房及各類客房訂多少間為賓館訂房及各類客房訂多少間為決策變量決策變量。 以賓館總數(shù)最少為目標的優(yōu)化模型其最優(yōu)解一般以賓館總數(shù)最少為目標的優(yōu)化模型其最優(yōu)解一般不唯一，可以再考慮賓館間的距離、客房價格等因不唯一，可以再考慮賓館間的距離、客房價格等因素，從幾個解中選出相對較好的一個。素，從幾個解中選出相對較好的一個。 問題分析和解決方法問題分析和解決方法 問題問題3主要應(yīng)考慮租用會議室和客車的總費用盡量小、主要應(yīng)考慮租用會議室和客車的總費用盡量小、會議室所在的賓館總數(shù)盡量少、距離上盡量靠近等。會議室所在的賓館總數(shù)盡量少、距離

13、上盡量靠近等。 租車要考慮多少代表參加哪個分組會議租車要考慮多少代表參加哪個分組會議, 題目中沒有題目中沒有這方面的信息這方面的信息, 可以按照可以按照平均的、隨機的平均的、隨機的方式處理。方式處理。 當建立優(yōu)化模型時當建立優(yōu)化模型時, 可用租借會議室和客車的總費用可用租借會議室和客車的總費用最少為目標函數(shù)最少為目標函數(shù), 以滿足對會議室數(shù)量、大小及租車的以滿足對會議室數(shù)量、大小及租車的需要為約束條件需要為約束條件, 以租用會議室和車輛的規(guī)格、數(shù)量為以租用會議室和車輛的規(guī)格、數(shù)量為決策變量。決策變量。 將問題將問題2, 3統(tǒng)一建立模型并求解有一定困難統(tǒng)一建立模型并求解有一定困難, 可可在問在問

14、題題2幾個解的基礎(chǔ)上解問題幾個解的基礎(chǔ)上解問題3，通過比較得出最后結(jié)果。，通過比較得出最后結(jié)果。 問題分析和解決方法問題分析和解決方法一種參考解法一種參考解法設(shè)有設(shè)有n屆同類型會議的歷史數(shù)據(jù)可利用屆同類型會議的歷史數(shù)據(jù)可利用 (n較小較小, 本題本題n=4) 第第i屆屆發(fā)來回執(zhí)的代表數(shù)量發(fā)來回執(zhí)的代表數(shù)量ai 第第i屆發(fā)來回執(zhí)但未與會的代表數(shù)量屆發(fā)來回執(zhí)但未與會的代表數(shù)量bi 第第i屆屆未發(fā)回執(zhí)而與會的代表數(shù)量未發(fā)回執(zhí)而與會的代表數(shù)量ci 本屆發(fā)來回執(zhí)數(shù)量本屆發(fā)來回執(zhí)數(shù)量A第第i屆屆與會代表數(shù)量與會代表數(shù)量di= ai- bi+ ci 第第i屆屆與會代表占發(fā)來回執(zhí)數(shù)量的比例與會代表占發(fā)來回執(zhí)數(shù)

15、量的比例ei= di/ai 預(yù)測本屆會議與會代表數(shù)量預(yù)測本屆會議與會代表數(shù)量Nmean=AemeanNmax=Aemax=661=678 比例法預(yù)測比例法預(yù)測1. 1. 預(yù)測本屆會議的與會代表數(shù)量預(yù)測本屆會議的與會代表數(shù)量 確定需要預(yù)訂各類客房的數(shù)量確定需要預(yù)訂各類客房的數(shù)量emean ，emax300350400450500550600650700750250300350400450500550600650 建立建立di對對ai的回歸模型的回歸模型用線性模型預(yù)測本屆會議用線性模型預(yù)測本屆會議與會代表數(shù)量與會代表數(shù)量 N=638確定預(yù)訂客房的總量確定預(yù)訂客房的總量 考慮兩種可能的損失：空房費；

16、代表不滿的量化考慮兩種可能的損失：空房費；代表不滿的量化“費用費用” 適當提高預(yù)測的與會代表數(shù)量適當提高預(yù)測的與會代表數(shù)量 對未發(fā)回執(zhí)而與會的代表另作安排對未發(fā)回執(zhí)而與會的代表另作安排 參考參考“航空公司的預(yù)訂票策略航空公司的預(yù)訂票策略”模型模型（姜啟源等：（姜啟源等：數(shù)學模型（第三版）第數(shù)學模型（第三版）第284頁頁1. 1. 預(yù)測本屆會議的與會代表數(shù)量預(yù)測本屆會議的與會代表數(shù)量 確定需要預(yù)訂各類客房的數(shù)量確定需要預(yù)訂各類客房的數(shù)量1. 1. 預(yù)測本屆會議的與會代表數(shù)量預(yù)測本屆會議的與會代表數(shù)量 確定需要預(yù)訂各類客房的數(shù)量確定需要預(yù)訂各類客房的數(shù)量預(yù)訂客房的總預(yù)訂客房的總量量本屆會議要求合住

17、、獨住各本屆會議要求合住、獨住各s(=3)種價位種價位(類型類型)代表數(shù)量及所占比代表數(shù)量及所占比例例 (合住考慮性別合住考慮性別) 預(yù)訂各類客房的數(shù)量預(yù)訂各類客房的數(shù)量需要預(yù)訂合住第需要預(yù)訂合住第j種類型客房數(shù)量種類型客房數(shù)量T1j需要預(yù)訂獨住第需要預(yù)訂獨住第j種類型客房數(shù)量種類型客房數(shù)量T2j第第i家賓館第家賓館第j種類型單人房種類型單人房(獨住獨住)能提供的間數(shù)能提供的間數(shù)C2ij 第第i家賓館第家賓館第j種類型雙人房種類型雙人房(合住或獨住合住或獨住)能提供的間數(shù)能提供的間數(shù)C1ij2. 2. 確定在哪些賓館預(yù)訂客房及預(yù)訂各類客房的數(shù)量確定在哪些賓館預(yù)訂客房及預(yù)訂各類客房的數(shù)量 以賓館

18、總數(shù)最少為目標，以滿足代表在合住、獨以賓館總數(shù)最少為目標，以滿足代表在合住、獨住及價位方面的需求，及各賓館擁有客房數(shù)量等為住及價位方面的需求，及各賓館擁有客房數(shù)量等為約束條件，建立約束條件，建立優(yōu)化模型優(yōu)化模型 . 預(yù)訂第預(yù)訂第i家賓館第家賓館第j種類型單人房種類型單人房(獨住獨住)間數(shù)間數(shù) x2ij 預(yù)訂第預(yù)訂第i家賓館第家賓館第j種類型雙人房種類型雙人房(合住合住)間數(shù)間數(shù) x1ij預(yù)訂第預(yù)訂第i家賓館第家賓館第j種類型雙人房種類型雙人房(改獨住改獨住)間數(shù)間數(shù) yij決策變量決策變量第第i家賓館的選擇變量家賓館的選擇變量 ki (ki=0,1)設(shè)共有設(shè)共有r家賓館雙人、單人房各家賓館雙人、單人房各s種類型種類型目標函數(shù)目標函數(shù)riikz1min約束條件約束條件sjTyxkjijriiji, 2 , 1,)(212sjTxkjriiji, 2 , 1,111滿足需求滿足需求s