【正文】 些取整數值。而且目標函數和約束條件的左邊可以是線性的，也可以是非線性的。本小節(jié)首先對整數規(guī)劃進行分類。 一、根據決策變量的取值規(guī)定進行分類 01型整數規(guī)劃：有決策變量取0或1的整數規(guī)劃。如果全部決策變量都只取0或1，則稱為純01型整數規(guī)劃，否則稱為混合01型整數規(guī)劃。 純整數規(guī)劃：所有的決策變量都取整數的整數規(guī)劃問題叫做純整數規(guī)劃問題。 混合整數規(guī)劃：有些變量取整數，有些變量取實數的規(guī)劃問題，叫做混合整數規(guī)劃。二、根據目標函數、約束條件左邊是否為線性進行分類線性整數規(guī)劃：目標函數和約束條件左邊全都是決策變量的線性函數的整數規(guī)劃叫做線性整數規(guī)劃。 非線性整數規(guī)劃：目標函數或者某些約束條件左邊是決策變量的非線性函數的整數規(guī)劃。 整數規(guī)劃各種類型和劃分標準可見表23所示。表23 整數規(guī)劃分類 類型條件線性整數規(guī)劃非線性整數規(guī)劃整數規(guī)劃01型整數規(guī)劃整數規(guī)劃01型整數規(guī)劃純整數規(guī)劃混合整數規(guī)劃純整數規(guī)劃混合整數規(guī)劃純整數規(guī)劃混合整數規(guī)劃純整數規(guī)劃混合整數規(guī)劃變量全部取整數部分取整數全部取整數部分取整數全部取整數部分取整數全部取整數部分取整數目標函數和約束條件全部為線性函數部分為非線性函數本章只討論線性整數規(guī)劃問題。線性整數規(guī)劃由于規(guī)定某些變量取整數值，大大地加大了求解難度。如果放松整數約束，則線性整數規(guī)劃問題成為線性規(guī)劃問題，叫做整數規(guī)劃的松弛線性規(guī)劃問題，簡稱為松弛線性規(guī)劃問題。如果是01型的整數規(guī)劃，整數約束將松弛成。設松弛線性規(guī)劃問題的可行域是S，則對應的整數規(guī)劃的可行域是S中整數點的集合。例如如下的整數規(guī)劃 （22）對應的松弛線性規(guī)劃問題為 （23）線性規(guī)劃（23）的可行域S是圖21中的陰影部分構成的凸集，而整數規(guī)劃的可行域是該凸集中的整數點：{(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2), (3,0),(3,1)}。求整數規(guī)劃的最優(yōu)解即是在該可行域的整數點集中尋找使目標函數最優(yōu)的點。點（3,1）即是（22）的最優(yōu)解。圖21 線性規(guī)劃和整數規(guī)劃的可行域23 高級網絡流問題 我們在運籌學課程中已經知道一些經典的網絡優(yōu)化問題，例如最小支撐樹問題、最短路問題、最大流問題和最小費用流問題。對于這些問題，已經有了有效的多項式算法。但這些經典網絡優(yōu)化模型只能解決一些比較簡單的問題。例如最短路問題只考慮邊的長度，沒有考慮路徑上其它因素的約束，如規(guī)定燃油的消耗量或規(guī)定允許的最長流動時間；最小費用流問題假設網絡上流動的是同一種“商品”，而實際情況可能存在多種“商品”，而且假設單位流的費用相同，不考慮網絡的建設投資等。因此實際問題比經典的網絡流問題要復雜得多。本節(jié)主要討論在航空運輸規(guī)劃中經常遇到的網絡優(yōu)化高級問題：約束最短路問題和多商品流問題。231 約束最短路問題 圖22是大家熟悉的最短路問題，其中節(jié)點v1和v8分別是始發(fā)節(jié)點（源節(jié)點）和終止節(jié)點（匯節(jié)點），圖中每邊上權重表示長度，要求從始發(fā)節(jié)點到終止節(jié)點的這樣一條路徑，該路徑上各邊的權重之和最?。窂介L度最短）。在圖22中，節(jié)點v1到v8 的最短路徑是v1 v7 v5 v6 v8，最短路程是9。圖22 最短路問題 可見經典的最短路問題只考慮網絡每邊的長度，可以用如下的數學模型來描述：其中，是邊(i,j)的長度，是01型的決策變量（路徑選擇變量），邊(i,j)在最短路徑上時=1，否則=0。該問題是一個易解問題，經典的標號法是多項式的算法。但在一些路徑最短問題中，不但要考慮選取最短（或成本最小的）路徑，而且沿某路徑流動時存在資源消耗。例如根據機組適航性要求，每機組在24小時內的飛行小時一般不得超過8小時，即所謂的8in24規(guī)則。此時，這8小時就成為機組航班環(huán)（配對，Pairing）問題的有限資源。確定每個機組航班環(huán)是航班網絡中的約束最短路問題。再如，在考慮飛機路線時，需要考慮飛機的飛行小時，一般要選擇日利用率在給定范圍內的航班環(huán)作為飛機的可行路線，因此飛機的飛行小時是飛機路線問題的有限資源。一般地，約束最短路問題可以描述成如下的網絡流問題：網絡的每條邊(i,j)的權重是一對數(,)，其中是該邊的“長度”，是在該邊流動時消耗的資源（可以有多個）。要求網絡的始發(fā)節(jié)點到終止節(jié)點的一條滿足資源消耗約束的最短路經。如圖23所示的網絡中，從源s到匯t有5條路經，最短路經是：s 5 t，該路徑長度是9，消耗資源量13。如果我們限制該流可消耗資源量最大為10，則約束最短路徑是：s 1 2 4 t，該路徑的長度是11（9），但資源消耗量等于10，滿足資源約束條件。圖23 約束最短路問題約束最短路問題的數學模型如下：(24a)(24b)(24c)232 多商品流問題經典的網絡流問題只涉及到一種“商品”(single modity)，即在網絡上流動的只有一種商品。請大家回顧一下單商品流的數學模型是什么樣子的。在最小費用流問題中，給定了網絡的流量d，以及每邊(i,j)的容量和單位流費用，要求網絡流d在網絡上的最小費用的分布模式，如圖24所示。圖24 最小費用流問題（網絡流b=7）最小費用流問題的數學模型如式（25）所示。其中（25a）是目標函數，要求總費用最小，(25b)是節(jié)點的流量平衡約束條件，每個節(jié)點具有一個這樣的約束條件，(25c)是邊的容量約束條件，要求每條邊的流量不大于容量。(25a)(25b)(25c)生產實際上，我們常常碰見網絡上同時流動著多種“商品”的問題，例如在航線網絡上同時流動著各種機型的飛機，一種機型的飛機就是一種“商品”，這樣的問題叫做多商品流問題（multimodity flow problem）。下面我們來為多商品流問題建模。假設在網絡上流動著K種商品，令k=1,2,...,K表示任意第k種商品，在任意邊(i,j)上，商品流存在容量限制，各種商品的單位流都是占有一個單位的容量，因此各種商品流之和不能超過該邊的容量，第k種商品的網絡流量（總需求）為，在邊(i,j)上的單位流費用是，并進一步假設受到該種商品流容量的限制。根據以上假設，多商品流問題的數學模型是(26a)(26b)(26c)(26d)可見，多商品流問題是最小費用流問題的直接推廣，其中(26a)是目標函數，要求總費用最小，(26b)是對每種商品，每個節(jié)點都必須滿足的流平衡約束條件，(26d)是對每種商品，每條邊都必須滿足的容量限制條件，(26c)表示每條邊上各種商品流之和不得大于該邊的容量。如果網絡有n個節(jié)點，m條邊，那么對于每個商品，這個模型將有m個流變量，因此共有Km個決策變量。而且模型共有Kn個節(jié)點的流守恒約束，m個邊的總容量約束，以及可能存在Km個各商品流的邊容量約束條件。第三章 機場運行規(guī)劃31 引言311 機場生產組織機場是組織航空運輸生產的重要場所。在這里，飛機起飛、著陸、停放；旅客下機、領取托運行李，辦理乘機手續(xù)、候機和登機以及轉機；到達的貨物在這里卸下和轉運，離港的貨物在這里分理、打包、裝箱和裝機。這里一片繁忙景象，人來客往，車輛穿梭，如果沒有高效的組織，很難想象這里的運輸生產可以有條不紊地進行。機場分為陸側(Landside)和空側(Airside)兩部分。航站樓和地面到達系統(tǒng)組成陸側部分，是旅客轉換交通模式的地方；跑道、滑行道和停機坪組成空側部分（也稱飛行區(qū)），是飛機活動的場所，有時也把終端區(qū)甚至進近區(qū)域（Terminal Area）劃歸機場空側部分。機場組成的示意圖如圖31所示。旅客運輸生產從旅客到達航站樓入口處開始，國內航班旅客通過值機和安檢，即可進入候機廳候機，航班出發(fā)前20分鐘左右開始登機；國際旅客則除了值機和安檢外，還需要辦理出關手續(xù)（包括海關申報、檢驗檢疫和邊防檢查）。到達目的地機場后，國內航班旅客下機到行李認領廳領取行李，然后轉乘陸路交通離開機場；國際航班旅客還必須辦理入關手續(xù)，首先通過邊防檢查，然后領取行李，接受衛(wèi)生檢驗檢疫和海關申報后，轉乘陸路交通離開機場。貨物運輸生產首先由貨代收集貨物，分理打包，向航空公司申請貨艙艙位，再運送至機坪裝機；到達目的地機場的貨物下機后運到貨站，在貨站進行分理，然后用貨車運往最終目的地。如果是國際貨物還必須辦理出入報關手續(xù)，通過海關和檢驗檢疫檢查。所以，除了運輸途中飛行以外，航空客貨運輸生產都在機場完成，運輸生產的效率主要體現為機場生產組織的效率。上述的生產組織活動將在本章作詳細討論。圖31 機場組成示意圖312 繁忙機場和航班延誤問題首先定義機場容量：機場容量指單位時間的生產能力，在不同的功能區(qū)，有服務旅客數、服務飛機數和服務行李數等。機場功能設施理論可達到的最大流量叫做極限容量。在繁忙機場，常常由于容量不足而導致飛機排隊等待起飛和降落；旅客排著長隊等待值機、安檢、領取行李。當航班不能正點起飛時，便產生航班延誤。航班延誤大小是指實際出發(fā)時間與計劃出發(fā)時間的差值，盡管航班延誤的原因有多種，但機場容量不足是重要原因。如果航空公司的機務或機組原因造成了航班延誤，則只會影響一個航班，如果機場容量不足，則將造成大面積航班延誤。一般來說，當交通需求超出機場容量時，航班延誤定將發(fā)生。如果使用平均需求來進行衡量，要特別注意：即使平均需求小于機場容量，航班延誤也可能發(fā)生。這是因為盡管平均需求不超過機場容量，但瞬時需求（即峰值需求）可能會超過（甚至大大超過）機場容量，造成一段時間內的航班擁堵和延誤?？梢娊煌ㄐ枨蟮囊?guī)模及其分布對航班延誤有重要影響。在交通需求不變的條件下，增加機場容量能減少延誤。機場容量與交通需求及航班延誤之間的關系?？勺鳛榇_定機場容量的有用方法，如圖32所示。極限容量在生產實際中是達不到的。隨著交通需求的增加，航班延誤開始時緩慢增加，當交通需求增加到某種水平時，航班延誤增長加快，當生產流量接近極限容量時延誤將趨于無窮大。對應于允許最大延誤的交通需求量定義為實際容量。延誤的增加與流量的增長成非線性關系。圖32 機場容量、交通需求和航班延誤關系圖 313 機場運行規(guī)劃及其意義機場可以分為陸路到達系統(tǒng)、航站樓系統(tǒng)和飛行區(qū)系統(tǒng)，航站樓系統(tǒng)的旅客流程又可以分成處理器、容器和連接器三種功能設施。值機柜臺、安檢通道、邊檢通道和登機門等是處理器，旅客在每個處理器處接受服務時，可能需要排隊等待，所以一般每個處理器處都配有容器，以容納等待的旅客，兩處理器之間設計有通道。飛行區(qū)又可分為跑道系統(tǒng)、滑行道系統(tǒng)和停機坪三個功能設施，飛行區(qū)功能是為飛機運行服務而建設。機場運行規(guī)劃是指為機場的生產運行所制定的計劃和規(guī)則，包括生產流程的設計和分析、生產資源的配置以及生產調度計劃的制定等內容。在進行機場運行規(guī)劃時，需要分析機場系統(tǒng)各子系統(tǒng)、各功能實施的容量和效率。容量是生產能力的體現，效率是管理水平的體現。通過運行規(guī)劃，可以幫助機場管理者掌握生產組織的各種關系，提高服務水平和改善機場運行質量。ICAO推薦了機場規(guī)劃基本步驟，如圖33所示。由圖33可以看出，容量評估是機場規(guī)劃的第一步，其基礎性作用在于機場規(guī)劃人員不僅需要正確分析現有容量水平和容量瓶頸環(huán)節(jié)，找準生產流程需要改進甚至改造的地方，提出改造方案，還要掌握未來交通流量需求下的機場容量水平。在這一過程中，交通需求被不斷反饋到機場容量的規(guī)劃中，影響容量規(guī)劃的制定和修訂。圖33 機場運行規(guī)劃流程圖32 機場運行規(guī)劃基礎321 排隊網絡由各種排隊系統(tǒng)通過串聯和并聯方式連接成的網絡，叫做排隊網絡。航站樓系統(tǒng)的旅客流程、飛行區(qū)的飛機流程是一種排隊網絡，如圖34所示。圖34 排隊網絡旅客流程作為一種排隊網絡，是一種開環(huán)網絡，叫做Jackson網絡。若排隊系統(tǒng)是M/M/c系統(tǒng)，并且利用率小于1，則它的輸出率等于輸入率。如果各同性質的排隊系統(tǒng)相互獨立，則它們構成的并行排隊系統(tǒng)的輸出率等于各排隊系統(tǒng)的輸出率之和。值機區(qū)的各值機排隊系統(tǒng)是并行的排隊系統(tǒng)。如果不實行航班和航空公司之間的公用設備模式，則可認為一個航班的值機是一個排隊系統(tǒng)，這樣的排隊系統(tǒng)旅客輸入過程是非穩(wěn)態(tài)的Poisson過程。如果值機采用公用設備模式，那么如果實現完全的公用模式，則值機區(qū)是一個排隊系統(tǒng)；如果公用模式只在局部實行，則該局部的所有值機柜臺構成一個排隊系統(tǒng)。安檢排隊系統(tǒng)盡管有許多通道，但采用完全的公用形式，因此可認為是一個排隊系統(tǒng)。國際和國內航班安檢一般是分離的排隊系統(tǒng)。值機排隊系統(tǒng)和安檢排隊系統(tǒng)是串連的，值機系統(tǒng)的輸出是安檢系統(tǒng)的輸出。因為機場目前常采用公用候機廳方式，旅客也可能去商店購物，候機登機排隊系統(tǒng)比較復雜322 累計分布曲線對于機場旅客流程以及飛機停機坪作業(yè)流程的任一排隊系統(tǒng)，非常簡單又有用的分析工具是累計分布曲線。它是排隊系統(tǒng)的累計到達/離開顧客數隨時間的變化曲線，橫軸是時間，縱軸是顧客已到達/離開累計數（或占總數的比例）。例如，對于值機排隊系統(tǒng)，該累計曲線的橫軸是航班起飛前的時間，通常是逆向的，縱軸是已到達旅客數占該航班旅客總數的比例。圖35是不同時間出發(fā)的國內航班值機旅客累計到達分布曲線。圖35 國內航班值機旅客累計到達分布曲線323 高峰小時的定義用于機場規(guī)劃基本參數是機場高峰小時需求，又叫做典型高峰小時，或設計小時、高峰小時(DPH)。高峰小時的幾種定義如下l 年度的第30或40個最繁忙的小時l 年度高峰月的平均日高峰小時l 年度兩個高峰月的日平均高峰小時l 年度每百繁忙日的第95天的高峰小時l 年度第7或15個繁忙日的高峰小時其中第一種定義