《飛機排隊模型數(shù)學建模.ppt》由會員分享，可在線閱讀，更多相關(guān)《飛機排隊模型數(shù)學建模.ppt（38頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、MCM-89題機場安排最優(yōu)排隊調(diào)度問題,機場通常是用“先到先服務”的原則來分配飛機跑道，即當飛機準備好離開登機口時，駕駛員電告地面控制中心，加入等候跑道的隊伍。假設(shè)控制塔可以快速在線數(shù)據(jù)庫中得到每架飛機的如下信息： 1、預定離開登機口的時間； 2、實際離開登機口的時間； 3、機上乘客人數(shù)； 4、預定在下一站轉(zhuǎn)機的人數(shù)和轉(zhuǎn)機時間； 5、到達下一站的預定時間。 又設(shè)共有七種飛機，載客從100人起以50人遞增，載客最多的一種是400人。試開發(fā)和分析一種能使乘客和各航空公司雙方都滿意的數(shù)學模型。（注：七種飛機可能分屬于不同的航空公司）,在目前的各國機場，一般都使用“先到先服務
2、”的排隊系統(tǒng)，這一系統(tǒng)雖一直延用，但效率不高，且不能調(diào)節(jié)意外情況的發(fā)生。在這里將要給出一個利用數(shù)據(jù)庫系統(tǒng)快速排隊的模型，以使機場高效的服務，并使航空公司在盡量小的花費情況下，達到顧客滿意的目的。,模型的基本假設(shè),機場上所有要起飛的飛機，都必須使相同一條跑道，并且任何一架飛機在起飛的時候都需要完全地占有整條跑道，每架飛機占用的時間是一樣長的。這一假設(shè)可把整個時間分割成離散的等長的小時間段（也稱為起飛窗口寬度），在每個小時間段上可容納一架飛機完成起飛操作。 第i架飛機由第j個時間段上起飛時，其所需費用僅與該飛機和時間位置有關(guān)，而與它前面是哪架飛機無關(guān)。即費用不是前面飛機的函數(shù)，因此這一假設(shè)可把對應
3、于不同排序的總費用都統(tǒng)一描述為一個線性函數(shù)。 任何飛機從離開自己的通道口到達跑道入口處所需要的時間假定都一樣。同時為了避免有一大堆飛機擠在跑道入口處等待飛機（一般機場也不太可能這樣），這時如有另一架飛機需要緊急起飛，這就須將所有排在前面的飛機擠到一邊來騰地方，因此假設(shè)每架飛機都有立即進入跑道口的通道。這樣在須要調(diào)整次序時，只須在數(shù)據(jù)庫中的次序上進行調(diào)整，而不必對飛機實地重排。并且飛機須在為其指定的小時間段上才準許離開自己的通道口。,模型設(shè)計與可行性分析,如果在t0時刻僅有一架飛機或沒有要求起飛的飛機，則機場就直接安排其起飛或閑置 。因此設(shè)在t0有n架飛機同時要求起飛。由假設(shè)1，可將n架飛機起飛
4、所需要的總時間分成n個等長的小時間段（如長）。下面如何安排哪架飛機在哪個時段上起飛要依賴于實際航班的花費和顧客的滿意程度來確定。 設(shè)為Cij第i架飛機從第j個小時間段上起飛時所需一切費用之和，于是所有可能的排序帶來的費用計算有如下的費用距陣表示：,（1）,并設(shè)Xij=0或1，當?shù)趇架飛機在第j個時段上起飛時Xij=1，否則Xij=0,于是相應地安排方案距陣為 ：,即第一架飛機排第2個窗口起飛，第2架排第一個窗口起飛，最后一架排最后起飛。并由上表的安排結(jié)構(gòu)，知道（2）中的距陣滿足每行中僅有一個元素為1，即每個窗口上僅有一架飛機占用；該陣每列中也有一個元素為1，即每架飛機占用n個窗口中的一個。即變
5、量Xij須滿足約束：,對于分派問題，已有專門為此種特殊結(jié)構(gòu)而設(shè)計的有效的解題算法，它被稱為GraverThrall primal算法。對于1個隨機產(chǎn)生的具有16個變量的分派問題，最多只須2.9秒即可完成求解，而使用現(xiàn)代的計算機，對任意適當個變量的指派問題，只須不到一秒鐘即可求得解。,同時，由于模型中費用系數(shù)陣（1）須要經(jīng)過量化，而他們可由下一段四中的公式求得。并由數(shù)據(jù)庫中的數(shù)據(jù)進行計算，這一量化模型的過程須要另一個不到一秒鐘。因此整個模型的建立與求解所用時間是以秒為數(shù)量級的，故當機場控制塔在面臨一串連珠炮一樣的起飛請求時都可幾乎立即對排序作出響應。而飛機的起飛間隔遠不是以秒為數(shù)量級的。一般至少
6、幾分鐘，因此模型是可行的。 更重要的是。在設(shè)有意外發(fā)生的情況下，還可利用機場的原有時間表，由數(shù)據(jù)庫事先安排好起飛順序，并讓飛機安排起飛順序起飛，而唯一需要重新安排的情況僅僅發(fā)生在有飛機晚點或緊急的情況，而這時的運算也會在一秒鐘左右解決問題。而且由假設(shè)（3），也不會因改變而產(chǎn)生臨時的擁擠情況。,四、模型中費用系數(shù)陣的量化,由于（1）中的Cij 是第i架飛機從第j個時間段上起飛的費用，它與一架航班的型號及運行費用和其上載客情況和他們的滿意程度有關(guān)，為簡化運算，把基本運行費設(shè)置為費用零點，而只考慮由于飛機延遲起飛而引起的費用。這一費用包括由于晚點而不再以最經(jīng)濟的速度而是以較快或最快速度飛行帶來的燃料
7、損失；及乘客因耽誤下站轉(zhuǎn)機而重新安排旅途的損失；以及顧客因各種延遲帶來的不愉快而轉(zhuǎn)化的損失。將這三者分別歸入費用計算并簡記為： 費用: 1.燃料附加費 2.乘客誤機費 3.乘客不滿意的損失 下面分別建立幾個費用的計算公式,1.燃料附加費,由于晚點，飛機必須以盡可能快的速度飛行，故燃料隨晚點的時間長短而變化，然而既使晚點，只要為達到最大時限，就可以以低于最大安全速度飛行。并在起飛后就可近似地保持常速，因此燃料消耗在時間內(nèi)應恒定，由于不知道燃料消耗如何隨飛行速度變化，選用了近似的線性函數(shù)，即單位時間增加油耗的費用函數(shù)為：,由此公式看出，飛機晚點越久，則耗油越多，直至它在離開時即以最大速度起飛（
8、假設(shè)4）。 下面為了建模討論的方便，將上述公式中及以后要用到的一些參數(shù)給出一個總表：,,2.乘客誤機費,設(shè)為乘客耽誤了轉(zhuǎn)機而必須補償?shù)馁M用，這里取為常數(shù)（假設(shè)5）。如果對各人的補償費確實不同，則取為各人費用的數(shù)學期望----平均值，且重新安排旅程只發(fā)生在飛機晚點時間超過了時限時才發(fā)生，故費用如下計算,3.乘客不滿意的損失,由于飛機晚點越多，則乘客會越不滿意，如果僅晚點一兩分鐘，則顧客不會太不愿意；但如果晚點到誤了轉(zhuǎn)乘班機，則該乘客會頓時變得焦躁不安并且非常憤怒，這一情況可以適當?shù)卣鰹橐粋€指數(shù)增長函數(shù)附加一個階躍函數(shù)，則總的費用函數(shù)為：,但是只要將要到達的飛機一準備好降落，就可以準許其降落的
9、話，這模型仍適用，這只要將,為了防止那些還未準備好的飛機，在就緒之前就對其發(fā)出起飛的命令，置一架飛機在它預定起飛時間以前的某窗口起飛的損失為無窮大，并假如考慮1，2，3中的費用，得到計算費用的通式：,4.排隊模型小結(jié)：,2)求解線性規(guī)劃模型（指派模型）的最優(yōu)解，則可確定哪架飛機在什么時刻起飛；,在正常運行情況下，上述小結(jié)中1），2）步驟僅須做一次即可按部就班地運行，只有當意外發(fā)生時才啟用3）部分。,五.模型檢驗,最重要的模型檢驗即在于檢驗此模型是否具有意義，編了一個用單純形法解線性規(guī)劃的程序以及幾個簡單的例子來檢查模型運行的良好性，在后面第六部分中的具體結(jié)果中，可以看出所有結(jié)果都與所期待的直觀
10、判斷相吻合。隨后，又進行了更徹底的檢驗；變動其中的參數(shù)，測試更為復雜的例子，以至實際運作此系統(tǒng)，如果實際運行的結(jié)果顯示出為航空公司節(jié)省了開支，同時又能維持顧客滿意度在一個可接受的水平，則此模型將取得圓滿成功。,下面先進行的是變動其中參數(shù)的檢驗，即在參數(shù)受到擾動的情況下模型是否穩(wěn)定的檢驗，如果這個模型中一個或幾個參數(shù)有輕微的偏離真值，而模型結(jié)果不致有太大的偏離最優(yōu)解，則可認為模型是穩(wěn)定的。另外,如果參數(shù)的微小變化帶來模型的劇烈變化，則希望確定哪個參數(shù)更敏感。這樣確定它時將利用更多的信息，以達到準確。,下面將指派模型（4）表運輸模型：,由運輸模型的有關(guān)理論知：運輸問題有可行解，并對（9）這樣的運輸
11、模型，一定有一個最優(yōu)且此最優(yōu)的所有分量都取整數(shù)值。又注意到約束條件（9）的限制，則可能的整數(shù)解一定非0即1，因此運輸問題等價于原問題（4）。將（9）式由目標函數(shù)的向量形式（見（4）式定義）表出：,六、計算機模擬模型,為了了解模型運行的良好性，以及本模型的特點，用下述幾個計算機模擬例子來進行演示。,顯然；理論模型要比計算機模型要少受限制。為了編程簡單并說明問題，在原有的基本假定基礎(chǔ)上，再添加如下具體假定：,1.1、在每一窗口至多有三架飛機已準備好可以起飛，當僅有兩架飛機準備好的情況發(fā)生時，可加入一個虛擬變量，以其對相應的費用系數(shù)都為0即可。,2、憑直觀給模型指定了參數(shù)值，在實際中，這些值應該通過
12、實驗室或調(diào)查獲得：,每一個起飛窗口為一分鐘長，即任何飛機起飛需要至多一分鐘，而且其他飛機不準在一分鐘內(nèi)占用跑道；,設(shè)有飛機降落情況；,誤轉(zhuǎn)機的賠償費為每人350；,誤了轉(zhuǎn)機的乘客的憤怒長度等價于被耽誤了15分鐘的乘客的兩倍。,例1 （具有使最多乘客的飛機先走的功能）,考慮在早晨6：00，三架飛機同時要求起飛設(shè)他們的型號相同，有距此機場相同距離的終點機場，（但可能飛往不同城市的機場）。設(shè)三架飛機為A，B，C。并且他們都預定在7：20到達終點，但A飛機上有350名乘客；B飛機上有100名；C飛機上有400名。且每架飛機上都有100名乘客要求轉(zhuǎn)機，計算結(jié)果見表1。,例2 （具有使晚點飛機最久者先走的
13、功能 ）,當飛機C準備離開之際，飛機D要求緊急起飛。飛機D已經(jīng)晚點18分鐘，它若想按時在7：06分到達終點，就必須在2分鐘內(nèi)起飛。其上有200名乘客，150人要求轉(zhuǎn)機，表2給出了結(jié)果,例3（具有按情況決定先后的功能）,假設(shè)又過了兩分鐘，這時D和A已走，剩下B已經(jīng)晚點3分鐘，而另一架飛機E在此刻要求起飛。設(shè)E有如下條件： 1）按時準備就緒； 2）在可按時到達終點（7：42）之前，還富余42分鐘可以閑置； （ 3）機上有122名乘客，89人要求轉(zhuǎn)機； （ 4）晚點增加的費用為每分鐘450。,編程序來解此題，如所設(shè)引入一個虛擬變量，飛機X，這一飛機的一切費用系數(shù)都為0。得到如下結(jié)果：,在直觀上不明顯誰應先走，事實上，似乎應讓B先走好些，但可能由于E在高速飛行時增加的運行費用太昂貴及機上乘客的緣故，使模型選定讓E先走。,七、總結(jié),模型有易實施的特點，可結(jié)合于數(shù)據(jù)庫中使用。它可對數(shù)目很大的機場、任意可裝載的乘客數(shù)及轉(zhuǎn)機的乘客數(shù)，都可實現(xiàn)快速最優(yōu)排序，并可處理同時要求起飛的請求、照顧晚點飛機很久的先走功能，及可對不同型號和不同油耗的飛機進行適當?shù)淖们榭紤]。,模型雖不能對起飛和降落同時達到優(yōu)化，但卻可達到在起飛的間隙中安排降落。,可以確信此模型是既可達到使航空公司節(jié)省費用，又可達到使顧客滿意的理想模型。,
飛機排隊模型數(shù)學建模.ppt
