圖論最大流理論

在機場登機口分配中的應用教師:張金山聯系方式:zjscdut@163.com;主要參考書籍:1.數學建模與數學實驗,趙靜,但琦2.數學實驗,蕭樹鐵3.數學建模方法及其應用,韓中庚4.數學建模導論,陳理榮

數學建模簡介

理想與現實什么是數學建模?

數學建模是利用數學方法解決實際問題的一種實踐。即通過抽象、簡化、假設、引進變量等處理過程后，將實際問題用數學方式表達，建立起數學模型。數學建模所涉及的問題都是現實生活中的實際問題，范圍廣、學科多，包括工業、農業、醫學、生物學、政治、經濟、軍事、社會、管理、信息技術等方面。

1、問題的描述（背景）隨著機場航班日起降架次的增多和乘飛機出行旅客數量的迅速增長，現有的登機口資源正面臨著日益嚴峻的考驗。目前，大多數機場通過借鑒其他機場的做法，或根據以往的經驗來進行登機口分配和調度，往往導致很多載客數量較多的大中型飛機停靠在距安檢或者行李提取大廳較遠的登機口；或由于遠、近機位登機口航班密度安排不合理，使得每個登機口的航班組合沒有達到最優，從而降低了登機口的利用效率。

相關信息

根據某機場一天中部分時段的航班計劃，將各航班信息匯總表1所示

航站樓布局登機口、安檢區與行李提取大廳的位置

安檢區與行李提取大廳不同層但位置相近安檢區與行李提取大廳(不)同層但位置不同在保證機場安全、高效運行的前提下，盡可能提高登機口利用效率，體現民航旅客運輸的便捷性與舒適性。2、問題分析旅客步行距離最短模型的優化目標與約束條件優化目標1)使進、出港旅客的總步行距離最短，滿足旅客對航空運輸“便捷性”的需求；2)使現有設施使用效率達到最高，優化資源配置。約束條件1)機型與機位類型相匹配；2)分配登機口時，一個航班必須被分配且僅能被分配至一個登機口；3)應滿足最短過站時間和同機位安全間隔時問的要求；4)“航班對”的限制：由于在機場停靠的絕大部分航班既擔負著進港航班任務，又擔負著出港航班任務，因此，盡量將此類飛機盡可能安排在同一個登機口，降低航空公司運營成本。除此之外，根據各機場的性質和特點不同，還需考慮登機口分配的優先原則、航班過夜、飛機維修等約束條件。3、模型的建立與求解

3.1數據收集與整理利用表l中已知航班信息作為實例分析的數據來源，采用最廣泛的航站樓布局形式即假定安檢區和行李提取大廳分別位于航站樓的上、下兩層，位置近似相同，以此來說明該模型的構建方法和應用過程。3.2優化分配網絡模型的構建3.2.1進、出港旅客步行距離最短模型建立與實證分析對于國內大部分干線和支線機場而言，始發或終到旅客所占比例甚多，從長時間的數據統計來看，這兩部分旅客所占比例相當，因此，可將其步行距離視為近似相等。以下就是進、出港旅客步行距離最短模型的實施步驟：步驟1按照登機口啟用時間的先后順序，由左至右把每個航班作為網絡圖上的一個節點，在考慮各種約束條件的基礎上，將節點之間進行有向連線，方向為由離港時間早的航班指向晚的，由此形成一個由節點和箭頭構成的網絡圖。不難理解，網絡圖中從起點到終點的每一條有向路徑上的節點都是可以安排在一個登機口上的航班組合，如圖3所示。步驟2在圖3上，按照各節點的時間順序對其進行二次編號G(A，B)，G表示航班編號；A表示航班G的前一個航班的編號(若為起始航班，則其編號為本次航班的號碼)；B表示航班載客人數的累計，即前一個航班A的實際載客人數與本次航班G的實際載客人數之和。需要注意的是，若A前有兩個或多個已編號航班，則擇選B最大的那個航班作為G的前一個航班，如圖4所示。步驟3將每架航班的人數看成是網絡圖中的流量，從登機口結束使用的這個網絡圖的最大流量就表示可以使用同一個登機口的人數最多的航班組合。從終點開始逆向尋找一條至起點航班人數最多的路徑，并把這條路徑上的航班安排在距安檢出口最近的登機口。在圖4中，01→04→07即為網絡圖中旅客流量最大的航班組合，可將這3個航班按照登機口啟用先后順序安排至離安檢區最近的登機口。步驟4在調度網絡圖上去掉已安排過的航班節點及與其相關聯的箭線，再從新的起點開始尋找一條至終點航班人數最多的路徑，并把這條路徑上的航班安排在距安檢出口次近的登機口，如圖5所示。在圖5中，02→03→05→08為網絡圖中旅客流量最大組合，可將這4個航班按照登機口啟用先后順序安排至離安檢區次近的登機口。步驟5重復步驟4，按照上述方法直到所有的航班安排完為止。本例中剩下06號航班，可將其安排至3號登機口。3.3.1算法的復雜度分析如前所述，該模型總運算次數不會超過n，而網絡圖中航班節點的總數也不會超過n，故總運算次數不會大于n2，即其計算復雜度為o(n2)。3.3算法復雜度分析和最優性證明2.3.2算法的最優性證明為了說明算法是最優算法，現在登機口調度網絡圖上增加一個虛擬起始節點s和一個虛擬終結節點t，并將虛擬起始節點s與所有起始航班節點用箭頭相連，同樣，將所有終結節點與虛終結節點t也用箭頭相連，如圖6所示。由于各航班節點是按時間順序由左至右排列的，因此，圖6所示的網絡圖是一個具有兩端點s和t的無環路網絡圖。其中每一條從s到t的有向路徑，都是可在同一個登機口安排航班組合的可行方案。如果把各節點的航班人數作為以該節點為終點的各箭線的權值，則該網絡圖就相