2009數(shù)學建模D題會議安排的優(yōu)化模型論文.doc

會議籌備問題的數(shù)學優(yōu)化模型摘 要此類問題屬于優(yōu)化問題，要求我們從組委會的角度出發(fā)制定出預訂客房，租借會議室，租用客車的最佳方案。我們以賓館數(shù)量少、賓館相對集中為原則，在滿足與會代表具體要求的前提下，我們得到了該類問題的相關(guān)結(jié)果。其具體解決方案如下： 首先，我們對附件數(shù)據(jù)做了必要的分析，采用平均百分比和線性回歸兩種方法分別計算出了與會代表的人數(shù)，但由于往年資料有限，我們排除了線性回歸的方法，并預測實際與會人數(shù)為661人。然后，我們按回執(zhí)中各類房間所占的不同比重來確定最終訂房類別及數(shù)量。 其次，從滿足代表住房要求的原則出發(fā)，盡量選擇所需賓館數(shù)量最少為原則并保證與會代表相對集中，我們建立整數(shù)規(guī)劃模型，并確定目標函數(shù)和約束條件，得出最優(yōu)解。最終選定了1、2、5、7四家賓館，同時，求出了與會代表的滿意度。關(guān)于會場租賃及租車問題，由于需要6個會場，且每個會場與會人數(shù)不確定，我們只考慮了一種平均意義下的結(jié)果。利用整數(shù)規(guī)劃模型并借助LINGO軟件求出最優(yōu)解，最終選擇2號賓館130人會議室2間，180人會議室1間，5號賓館150人會議室2間，180人會議室1間。根據(jù)與會代表入住每個賓館的人數(shù)情況，我們得到需要租45座車4輛，36座車4輛，33座車4輛。兩項合計總費用為30600元。關(guān)鍵詞：回執(zhí)數(shù)量、平均百分比、線性回歸、整數(shù)規(guī)劃模型、 LINGO軟件、與會代表滿意度。一、問題重述與分析某會議服務公司負責承辦一屆全國性會議，會議籌備組要為與會代表預訂賓館客房，租借會議室，并租用客車接送代表。由于預計會議規(guī)模龐大，而適于接待這次會議的幾家賓館的客房和會議室數(shù)量均有限，所以只能讓與會代表分散到若干家賓館住宿。籌備組要在10家賓館中選定幾間來為代表預定房間。為了便于管理，除了盡量滿足代表在價位等方面的需求之外，所選擇的賓館數(shù)量應該盡可能少，并且距離上比較靠近。 備選賓館的名稱用代號至表示，相對位置見附圖，有關(guān)客房及會議室的規(guī)格、間數(shù)、價格等數(shù)據(jù)見附表1。 根據(jù)附表2與附表3從以往幾屆會議情況來預訂賓館客房。而預定的客房房費由與會代表自付，但是如果預訂客房的數(shù)量大于實際用房數(shù)量，籌備組需要支付一天的空房費，而若出現(xiàn)預訂客房數(shù)量不足，則將引起代表的不滿。 會議期間有一天的上下午各安排6個分組會議，籌備組需要在代表下榻的某幾個賓館租借會議室。由于事先無法知道哪些代表準備參加哪個分組會，籌備組還要向汽車租賃公司租用客車接送代表?，F(xiàn)有45座、36座和33座三種類型的客車，租金分別是半天800元、700元和600元。 本題希望我們通過數(shù)學建模方法，從經(jīng)濟、方便、代表滿意等方面，為會議籌備組制定一個預訂賓館客房、租借會議室、租用客車的合理方案。該問題來源于實際生活，我們認為合理的方案需要考慮如下因素：1盡可能準確地估計預定客房數(shù)，盡可能地滿足與會代表要求 ；2盡可能少選賓館數(shù)，且賓館盡可能集中；3. 租會議室及租車的費用盡可能少。二、模型的假設1. 假設前四屆會議與會代表出席會議情況是相互獨立的。2. 假設未發(fā)回執(zhí)但前來與會的代表住房要求與已經(jīng)發(fā)了回執(zhí)前來與會的代表的住房要求情況是相同。3. 設每位與會代表參加任何分組會議的概率是隨機的。 4. 假設所有與會代表參加本賓館外的分組會議都需要車接送。5. 假設每輛車只走一個單程，且不考慮中途有行人上下車的情況。三、基本符號說明：分別為實際與會人數(shù)占發(fā)回執(zhí)人數(shù)比平均值及最大值。di:租借的第i類車的輛數(shù)。:第i類車的租金（表示45座的車，表示36座的車，表示33座的車）。T1j：需要預訂合住第j種類型客房數(shù)量。j=1,2,3。T2j：需要預訂獨住第j種類型客房數(shù)量。j=1,2,3。C1ij：第i家賓館第j種類型雙人房(合住或獨住)能提供的間數(shù)。C2ij ：第i家賓館第j種類型單人房(獨住)能提供的間數(shù)。x1ij：第i家賓館第j種類型雙人房(合住)間數(shù) 。x2ij ：預訂第i家賓館第j種類型單人房(獨住)間數(shù)。 Yij： 預訂第i家賓館第j種類型雙人房(改獨住)間數(shù) 。四、模型的建立及求解1關(guān)于參加會議的代表人數(shù)： 為了合理安排本屆與會代表入住賓館，我們采用平均百分比法來計算。首先，必須明確本屆代表與會的基本情況。由附表2可知本屆代表的回執(zhí)代表數(shù)量為755人；由附表3進一步分析以往幾屆會議代表的基本情況和相對應的比例后，結(jié)果如（表1）所示：表1以往幾屆會議代表回執(zhí)和與會情況第一屆 第二屆 第三屆 第四屆 第五屆發(fā)來回執(zhí)的代表數(shù)量315356408711755發(fā)來回執(zhí)但未與會的代表數(shù)量89115121213未發(fā)回執(zhí)而與會的代表數(shù)量576975104實際參加人數(shù)283310362602661（678） 實際參加數(shù)/發(fā)來回執(zhí)數(shù)0.89840.87080.88730.8467經(jīng)計算得 ，第五屆會議與會人數(shù)。 2關(guān)于入住類型： 假設未發(fā)回執(zhí)前來與會的代表住房要求與已發(fā)回執(zhí)的情況相同，且發(fā)來回執(zhí)的人住房要求與實際參加的人要求一致（概率相等）。對附表1給定的信息，我們考慮的因素進一步增加，從附表2利用Excel畫出其所反應的趨勢圖（見附錄1）看，通過假設，本屆會議發(fā)來回執(zhí)且與會代表按百分比（1-30.04%=69.96%）進行估算，得到本屆會議發(fā)來回執(zhí)且與會代表的入住情況如表2所示（計算結(jié)果以四舍五入記錄）。表2. 本屆會議發(fā)來回執(zhí)且與會代表的入住情況合住1合住2合住3獨住1獨住2獨住3男1087322754827女553412412013根據(jù)附表2，我們運用相應比例關(guān)系估算出未發(fā)來回執(zhí)而與會代表的入住情況如表3所示（計算結(jié)果以四舍五入記錄）。表3 未發(fā)來回執(zhí)而與會代表的入住情況合住1合住2合住3獨住1獨住2獨住3男2718619127女14831053由表2和表3綜合估算出：本屆會議與會代表的實際入住情況如表4所示：表4.實際房間數(shù)合住1合住2合住3獨住1獨住2獨住3男（人數(shù)）135912894 60 36女（人數(shù)）69421552 25 17總?cè)藬?shù)20413343145 84 53房間數(shù)1026722 145 84533.關(guān)于賓館的選擇 因為賓館越少，與會代表入住要求集中，而要滿足所需的客車更少，會場也更集中。我們以賓館數(shù)最少為目標，以滿足代表入住要求及10家備選賓館現(xiàn)有資源為約束，建立該問題的優(yōu)化模型來解決這個問題。考慮附件1的數(shù)據(jù)及表4的數(shù)據(jù)得到該問題的數(shù)學模型如下：目標函數(shù)： 約束條件(需求關(guān)系與供給關(guān)系)：s.t： 對于該類整數(shù)規(guī)劃問題，我們可以借助lingo軟件求解得到，但是該問題的結(jié)果不唯一。下面是給出的是幾組可行解（見表5）： 表5 房間預訂情況 賓館合1合2合 3獨1獨2獨3122將2 標2改獨一30+標改獨1620+標改獨325034標改獨35標改獨315523318標改獨7740+50（合改獨）30剩余賓館2房間數(shù)合計1026722 1458453該方案的主要特點是充分利用了賓館2與5及1與7。從表中可以看出，如果選擇1,2 5,7 及6或8共5個賓館所有預計到會的代表都能住到所要求價位的房間，即代表滿意程度為100%?？紤]到租車等問題，可以考慮代表不滿意度問題，例如選擇賓館1的2個160-200元的標間改為120-160元的單間，就可以不考慮賓其他館。不滿意度 為2/661=0.3%。4. 關(guān)于會議室選擇與車輛安排：從租用客車費用考慮，設為租借的第i類車的輛數(shù)，為第i類車的租金（表示45座的車，表示36座的車，表示33座的車），建立優(yōu)化模型如下：目標函數(shù)：約束條件：表7 各賓館人數(shù)統(tǒng)計賓館類型 賓館1 賓館2 賓館5賓館7人數(shù) 115 234 194 120由此可見，共需45座車4輛 ，36座車4輛 ，33座輛車4輛。具體用車方案如下： .1輛45座車,2輛36座車從賓館1滿載出發(fā)先至賓館2再開往賓館5。 .2輛45座車，1輛33座車從賓館7出發(fā)先到賓館5，再開往賓館2。 .2輛36座,1輛45車從賓館2開往賓館5。 .3輛33座車從賓館5開往賓館2。用LINGO軟件編程并運行（程序見附錄5），其結(jié)果得出租借客車費為：5700元。五、模型的評價與改進1、與會人員模型改進：對附表3給出的前幾屆會議代表回執(zhí)和與會情況數(shù)據(jù)進行統(tǒng)計發(fā)現(xiàn)，發(fā)來回執(zhí)但未與會的代表比例穩(wěn)定，約為30%，未發(fā)回執(zhí)而與會的代表比例約為17.6%。與會代表比例、均值和方差見表9。 表9 與會代表比例、均值和方差第一屆第二屆 第三屆 第四屆平均值 方差 人 數(shù)（人）百分比（%）人數(shù) 百分比（%） 人數(shù)百分比（%） 人 數(shù) （人）百分比（%）發(fā)來回執(zhí)但未與會的代表 89 28.25 115 32.30 12129.6621329.96 0.3004 0.0145未發(fā)回執(zhí)而與會的代表5718.10 69 19.38 75 18.38 104 14.63 0.1762 0.0179 可以認為，發(fā)來回執(zhí)未與會的代表比例和未發(fā)回執(zhí)而與會的代表比例服從正態(tài)分布，并取置信度為95%，則應取置信區(qū)間下分位點作為發(fā)來回執(zhí)未與會的代表預測數(shù)量，取置信區(qū)間上分位點作為未發(fā)回執(zhí)而與會的代表預測數(shù)量。其計算公式為： 將數(shù)據(jù)代入上式計算得到與會代表總數(shù)為708.84人，向上取整數(shù)為709人，其中發(fā)來回執(zhí)且與會的代表539人，未發(fā)回執(zhí)而與會的代表147人。用MATLAB軟件對方差較大的未發(fā)回執(zhí)而與會的代表比例進行正態(tài)分布的卡方檢驗，證明假設：未發(fā)回執(zhí)而與會的代表比例服從正態(tài)分布是合理的。同理,我們可以證明發(fā)來回執(zhí)未與會的代表比例也服從正態(tài)分布。 表10 未發(fā)回執(zhí)而與會的代表比例的卡方檢驗分段點 F值 概率 理論頻數(shù) 2 卡方值 臨界值 0.16 0.1830 0.1830 0.7318 0.0983 0.18463.84150.19 0.7789 0.5959 2.3837 0.06180.22 0.9927 0.2138 0.8552 0.02452、模型的評價與分析： 對人員的預測用兩種不同的方法進行分析，而對賓館和房間的確定也綜合考慮了經(jīng)濟、方便、數(shù)量少、代表滿意、少支付空房費等多種因素，分別建立了兩種數(shù)學基本模型求解。但也忽略了部分實際生活中的因素，模型偏于理想化。主要表現(xiàn)在： （1）、 對實際問題及現(xiàn)實的交通情況的考慮不夠，實際的情況會影響對客車的預定的問題，比如說堵車，而汽車行駛也不一定沿路直線行駛，可能會斜穿馬路。 （2）、沒有考慮萬一出現(xiàn)與會代表人數(shù)大大超出會議室規(guī)模的情況的解決方案。 （3）、 在實際問題中我們還應考慮交通問題、客車的加速行駛到減速停車過程的時間、上下車完畢的時間，將它們的總和與正常人在一定小距離內(nèi)步行的時間作比較，以此來確定在多遠的距離內(nèi)不需要客車接送代表，從而改進模型，使其更加符合要求。 （4）、 在確定會議室和安排客車方面，能夠在滿足實際需求的基礎上，更好的為籌委會節(jié)省開支，故方案更佳。但是，該模型本身還是有一些不完善的地方的，首先就是我們沒有考慮，在距離很近的時候，可以采用代表步行的方式參會，從而可以省去一大筆車費。例如之間僅有150米遠的距離，此時再采用客車接送顯得有點牽強。其次就是，我們方案中沒有給突發(fā)情況留有較大的余地，每輛車的乘坐率很高，每趟車基本僅剩下幾個空座，實際情況可能不是我們預測的那樣代表完全等可能的參加各分組會議，此時就會出現(xiàn)一些車擁擠不堪的而另外一些車剩座較多的情況。此時這個方案就顯得有些不完善。 （5）、以上模型都是利用以往數(shù)據(jù)的平均數(shù)來分析的，隨機因素對問題影響較大，比如按最大比例算，與會人員可達678人。3、該模型的優(yōu)點主要體現(xiàn)在： （1)、從建模總體來看，問題都是通過編程來解決的，這體現(xiàn)了數(shù)學建模的科學合理性。 （2)、從建立的模型來看，更好運用了數(shù)形結(jié)合的思想，這樣使得問題更清晰直觀、易于理解。 4、模型的推廣： 本文建立的模型是為了解決本屆參加會議人員的住房、開會租客車的問題，此類模型也可以運用到酒店預定客房、旅行社租車及機場預定機票等問題上。同時，該模型同樣適用于生活中其它方面路線的計算和預測，準確度較高，具有通用性。六、參考文獻1 、全國大學生數(shù)學建模競賽組委會，數(shù)學建模的實踐：2006年全國大學生數(shù) 學建模夏令營論文集，北京：高等教育出版社（2007.8）。2 、袁新生等，LINGO和Excel在數(shù)學建模中的應用，北京：科學出版社（2007）。3 、晏林，數(shù)學與實驗MATLAB與QBASIC應用，北京：科學出版社（2005）。4 、謝金星，薛毅，優(yōu)化建模與LINDO/LINGO軟件，北京：清華大學出版社， （2005.7)。 5 、楊啟帆，數(shù)學建模，北京：高等教育出版社（2005.5）。6 、熊義杰，運籌學教程，北京：國防工業(yè)出版社（2004.9）。7 、許承德，王勇，概率論與數(shù)理統(tǒng)計，北京：科學出版社（2001）。8 、王冬琳，數(shù)學建模及實驗，北京：國防工業(yè)出版社（2004.5）。七、附錄附錄1附錄2附錄3程序運行結(jié)果如下：MODEL:MIN=600*X1+1500*X2+1000*X3+1500*X4+320*X5+800*X6+1000*X7+1200*X8+300*X9;X1=2;X2=1;X3=2;X4=1;X5=3;X6=2;X7=1;X8=1;X9=661;X1+X2+X3+X4+X5+X6+X7+X8+X9=6;ENDGlobal optimal solution found. Objective value: 5600.000 Infeasibilities: 0.000000 Total solver iterations: 0 Variable Value Reduced Cost X1 0.000000 300.0000 X2 0.000000 0.000000 X3 0.000000 0.000000 X4 1.000000 0.000000 X5 0.000000 20.00000 X6 2.000000 0.000000 X7 1.000000 0.000000 X8 1.000000 0.000000 X9 1.000000 0.000000 Row Slack or Surplus Dual Price 1 5600.000 -1.000000 2 2.000000 0.000000 3 1.000000 0.000000 4 2.000000 0.000000 5 0.000000 0.000000 6 3.000000 0.000000 7 0.000000 200.0000 8 0.000000 0.000000 9 0.000000 300.0000 10 2.000000 0.000000 11 0.000000 0.000000 12 0.000000 -1200.000 13 0.000000 -700.0000 14 4939.000 0.000000 15 0.000000 -300.0000附錄4程序運行如下：MODEL:SETS:ITEMS /ITEM1,ITEM2,ITEM3/: INCLUDE,WEIGHT1,RATING;ENDSETSDATA: WEIGHT1=45,36,33; RATING=800 700 600; KNAPSACK1=237; ENDDATAmin=SUM(ITEMS:RATING*INCLUDE);SUM(ITEMS:WEIGHT1*INCLUDE)=KNAPSACK1;FOR(ITEMS:GIN(INCLUDE);ENDObjective value: 4300.000 Objective bound: 4300.000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost KNAPSACK1 237.0000 0.000000 INCLUDE( ITEM1) 3.000000 800.0000 INCLUDE( ITEM2) 1.000000 700.0000 INCLUDE( ITEM3) 2.000000 600.0000 WEIGHT1( ITEM1) 45.00000 0.000000 WEIGHT1( ITEM2) 36.00000 0.000000 WEIGHT1( ITEM3) 33.00000 0.000000 RATING( ITEM1) 800.0000 0.000000 RATING( ITEM2) 700.0000 0.000000 RATING( ITEM3) 600.0000 0.000000 Row Slack or Surplus Dual Price 1 4300.000 -1.000000 2 0.000000 0.000000附錄5經(jīng)濟最優(yōu)條件下租用客車的程序：model:min=800*x1+700*x2+600*x3+800*x4+700*x5+600*x6+800*x7+700*x8+600*x9+800*x10+700*x11+600*x12;45*x1+36*x2+33*x3=155;45*x4+36*x5+33*x6=79;45*x7+36*x8+33*x9=71;45*x10+36*x11+33*x12=104;45*x1+36*x2+33*x3+45*x4+36*x5+33*x6+45*x7+36*x8+33*x9+45*x10+36*x11+33*x12=661;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);gin(x8);gin(x9);gin(x10);gin(x11);gin(12);end運行結(jié)果為： Global optimal solution found at iteration: 50 Objective value: 5700.00 Variable Value Reduced Cost X1 0.000000 800.0000 X2 0.000000 700.0000 X3 0.000000 600.0000 X4 2.000000 800.0000 X5 0.000000 700.0000 X6 2.000000 600.0000 X7 1.000000 800.0000 X8 1.000000 700.0000 X9 0.000000 600.0000 X10 1.000000 -18.18182 X11 0.000000 45.45455 X12 1.000000 0.000000 Row Slack or Surplus Dual Price 1 5572.727 -1.000000 2 102.0000 0.000000 3 1.000000 0.000000 4 43.00000 0.000000 5 2.000000 0.000000 6 93.00000 0.000000 7 0.000000 -18.18182 8 33.00000 0.000000 9 353.0000 0.000000附表1 10家備選賓館的有關(guān)數(shù)據(jù)賓館代號客房會議室規(guī)格間數(shù)價格（天）規(guī)模間數(shù)價格(半天)普通雙標間50180元200人11500元商務雙標間30220元150人21200元普通單人間30180元 60人2 600元商務單人間20220元普通雙標