大學(xué)畢設(shè)論文__乘公交看奧運(yùn)數(shù)學(xué)建模論文.doc

《大學(xué)畢設(shè)論文__乘公交看奧運(yùn)數(shù)學(xué)建模論文.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

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

2、理。我們參賽選擇的題號(hào)是（從A/B/C/D中選擇一項(xiàng)填寫）：B我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）：所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜褐貞c大學(xué)參賽隊(duì)員(打印并簽名)：1.2.3.指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人(打印并簽名)：日期：年月日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：59乘公交_看奧運(yùn)高教社杯全國大學(xué)生數(shù)學(xué)建模競(jìng)賽編號(hào)專用頁賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分備注全國統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國前編號(hào)）：全國評(píng)閱編號(hào)（由全國組委會(huì)

3、評(píng)閱前進(jìn)行編號(hào)）：59乘公交_看奧運(yùn)乘公交，看奧運(yùn)【摘要】本文要解決的問題是以即將舉行的08年北京奧運(yùn)會(huì)為背景而提出的。人們?yōu)榱四墁F(xiàn)場(chǎng)觀看奧運(yùn)會(huì)，必然會(huì)面對(duì)出行方式與路線選擇的問題。因此如何快速、高效地從眾多可行路線中選出最優(yōu)路線成為了解決此問題的關(guān)鍵。鑒于公交系統(tǒng)網(wǎng)絡(luò)的復(fù)雜性，我們沒有采用常規(guī)的Dijkstra算法，而采用了高效的廣度優(yōu)先算法。其基本思想是從經(jīng)過起（始）點(diǎn)的路線出發(fā)，搜尋出轉(zhuǎn)乘次數(shù)不超過兩次的可行路線，然后對(duì)可行解進(jìn)行進(jìn)一步處理。為滿足不同查詢者要求，我們對(duì)三個(gè)問題都分別建立了以

4、時(shí)間、轉(zhuǎn)乘次數(shù)、費(fèi)用最小為目標(biāo)的優(yōu)化模型。針對(duì)問題一（只考慮公汽系統(tǒng)），我們建立了模型一并通過VC++編程得到了任意兩個(gè)站點(diǎn)間的多種最優(yōu)路線，并得出所求站點(diǎn)間最優(yōu)路線的最優(yōu)值，如下表所示：出發(fā)站終點(diǎn)站S3359S1828S1557S0481S0971S0485S0008S0073S0148S0485S0087S3676最短耗時(shí)（min）641061066710646最少轉(zhuǎn)乘次數(shù)（次）121122最少費(fèi)用（元）333233模型二是根據(jù)問題二（同時(shí)考慮公汽和地鐵系統(tǒng)）建立的，同樣用VC++編程得到所求

5、站點(diǎn)間的最優(yōu)路線，如下表所示：出發(fā)站終點(diǎn)站S3359S1828S1557S0481S0971S0485S0008S0073S0148S0485S0087S3676最短耗時(shí)（min）64106965587.533最少轉(zhuǎn)乘次數(shù)（次）121120最少費(fèi)用（元）333233對(duì)問題三（將步行考慮在內(nèi)）我們建立了模型三的優(yōu)化模型，然后在模型改進(jìn)里又建立了圖論模型。本文的主要特點(diǎn)在于，所用算法的效率十分顯著。在對(duì)原始數(shù)據(jù)僅做簡(jiǎn)單預(yù)處理的條件下，搜索任意站點(diǎn)間的最優(yōu)路線所需的平均時(shí)間不超過0.5秒。另外，本文所建

6、立的模型簡(jiǎn)單、所用算法比較清晰，易于程序?qū)崿F(xiàn)，對(duì)公交線路自主查詢計(jì)算機(jī)系統(tǒng)的實(shí)現(xiàn)具有現(xiàn)實(shí)指導(dǎo)作用。關(guān)鍵字：轉(zhuǎn)乘次數(shù)廣度優(yōu)先算法查詢效率實(shí)時(shí)系統(tǒng)59乘公交_看奧運(yùn)一問題的重述傳承華夏五千年的文明，夢(mèng)圓十三億華夏兒女的暢想，2008年8月8日這個(gè)不平凡的日子終于離我們?cè)絹碓浇?！在觀看奧運(yùn)的眾多方式之中，現(xiàn)場(chǎng)觀看無疑是最激動(dòng)人心的。為了迎接2008年奧運(yùn)會(huì)，北京公交做了充分的準(zhǔn)備，首都的公交車大都煥然一新，增強(qiáng)了交通的安全性和舒適性，公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利。但同時(shí)也面臨

7、多條線路的選擇問題。為滿足公眾查詢公交線路的選擇問題，某公司準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)。這個(gè)系統(tǒng)的核心是線路選擇的模型與算法，另外還應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求。需要解決的問題有：1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用模型算法，求出以下6對(duì)起始站到終到站最佳路線。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S

8、0148→S0485(6)、S0087→S36762、同時(shí)考慮公汽與地鐵線路，解決以上問題。3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請(qǐng)你給出任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型。二符號(hào)說明：第i條公汽線路標(biāo)號(hào),i=1,2…10400,當(dāng)時(shí),表示上行公汽路線,當(dāng)時(shí),表示與上行路線相對(duì)應(yīng)的下行公汽路線；：經(jīng)過第i條公汽路線的第g個(gè)公汽站點(diǎn)標(biāo)號(hào)；：第j條地鐵路線標(biāo)號(hào),j=1,2；：經(jīng)過第j條地鐵線路的第h個(gè)地鐵站點(diǎn)標(biāo)號(hào)；：轉(zhuǎn)乘n次的路線；：選擇第k種路線的總時(shí)間；：選擇第k種路線公汽換乘公