【正文】 1的整數(shù)規(guī)劃。 純整數(shù)規(guī)劃：所有的決策變量都取整數(shù)的整數(shù)規(guī)劃問題叫做純整數(shù)規(guī)劃問題。二、根據(jù)目標函數(shù)、約束條件左邊是否為線性進行分類線性整數(shù)規(guī)劃：目標函數(shù)和約束條件左邊全都是決策變量的線性函數(shù)的整數(shù)規(guī)劃叫做線性整數(shù)規(guī)劃。 整數(shù)規(guī)劃各種類型和劃分標準可見表23所示。線性整數(shù)規(guī)劃由于規(guī)定某些變量取整數(shù)值，大大地加大了求解難度。如果是01型的整數(shù)規(guī)劃，整數(shù)約束將松弛成。例如如下的整數(shù)規(guī)劃 （22）對應的松弛線性規(guī)劃問題為 （23）線性規(guī)劃（23）的可行域S是圖21中的陰影部分構成的凸集，而整數(shù)規(guī)劃的可行域是該凸集中的整數(shù)點：{(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2), (3,0),(3,1)}。點（3,1）即是（22）的最優(yōu)解。對于這些問題，已經(jīng)有了有效的多項式算法。例如最短路問題只考慮邊的長度，沒有考慮路徑上其它因素的約束，如規(guī)定燃油的消耗量或規(guī)定允許的最長流動時間；最小費用流問題假設網(wǎng)絡上流動的是同一種“商品”，而實際情況可能存在多種“商品”，而且假設單位流的費用相同，不考慮網(wǎng)絡的建設投資等。本節(jié)主要討論在航空運輸規(guī)劃中經(jīng)常遇到的網(wǎng)絡優(yōu)化高級問題：約束最短路問題和多商品流問題。在圖22中，節(jié)點v1到v8 的最短路徑是v1 v7 v5 v6 v8，最短路程是9。該問題是一個易解問題，經(jīng)典的標號法是多項式的算法。例如根據(jù)機組適航性要求，每機組在24小時內(nèi)的飛行小時一般不得超過8小時，即所謂的8in24規(guī)則。確定每個機組航班環(huán)是航班網(wǎng)絡中的約束最短路問題。一般地，約束最短路問題可以描述成如下的網(wǎng)絡流問題：網(wǎng)絡的每條邊(i,j)的權重是一對數(shù)(,)，其中是該邊的“長度”，是在該邊流動時消耗的資源（可以有多個）。如圖23所示的網(wǎng)絡中，從源s到匯t有5條路經(jīng)，最短路經(jīng)是：s 5 t，該路徑長度是9，消耗資源量13。圖23 約束最短路問題約束最短路問題的數(shù)學模型如下：(24a)(24b)(24c)232 多商品流問題經(jīng)典的網(wǎng)絡流問題只涉及到一種“商品”(single modity)，即在網(wǎng)絡上流動的只有一種商品。在最小費用流問題中，給定了網(wǎng)絡的流量d，以及每邊(i,j)的容量和單位流費用，要求網(wǎng)絡流d在網(wǎng)絡上的最小費用的分布模式，如圖24所示。其中（25a）是目標函數(shù)，要求總費用最小，(25b)是節(jié)點的流量平衡約束條件，每個節(jié)點具有一個這樣的約束條件，(25c)是邊的容量約束條件，要求每條邊的流量不大于容量。下面我們來為多商品流問題建模。根據(jù)以上假設，多商品流問題的數(shù)學模型是(26a)(26b)(26c)(26d)可見，多商品流問題是最小費用流問題的直接推廣，其中(26a)是目標函數(shù)，要求總費用最小，(26b)是對每種商品，每個節(jié)點都必須滿足的流平衡約束條件，(26d)是對每種商品，每條邊都必須滿足的容量限制條件，(26c)表示每條邊上各種商品流之和不得大于該邊的容量。而且模型共有Kn個節(jié)點的流守恒約束，m個邊的總容量約束，以及可能存在Km個各商品流的邊容量約束條件。在這里，飛機起飛、著陸、停放；旅客下機、領取托運行李，辦理乘機手續(xù)、候機和登機以及轉機；到達的貨物在這里卸下和轉運，離港的貨物在這里分理、打包、裝箱和裝機。機場分為陸側(Landside)和空側(Airside)兩部分。機場組成的示意圖如圖31所示。到達目的地機場后，國內(nèi)航班旅客下機到行李認領廳領取行李，然后轉乘陸路交通離開機場；國際航班旅客還必須辦理入關手續(xù)，首先通過邊防檢查，然后領取行李，接受衛(wèi)生檢驗檢疫和海關申報后，轉乘陸路交通離開機場。如果是國際貨物還必須辦理出入報關手續(xù)，通過海關和檢驗檢疫檢查。上述的生產(chǎn)組織活動將在本章作詳細討論。機場功能設施理論可達到的最大流量叫做極限容量。當航班不能正點起飛時，便產(chǎn)生航班延誤。如果航空公司的機務或機組原因造成了航班延誤，則只會影響一個航班，如果機場容量不足，則將造成大面積航班延誤。如果使用平均需求來進行衡量，要特別注意：即使平均需求小于機場容量，航班延誤也可能發(fā)生?？梢娊煌ㄐ枨蟮囊?guī)模及其分布對航班延誤有重要影響。機場容量與交通需求及航班延誤之間的關系?？勺鳛榇_定機場容量的有用方法，如圖32所示。隨著交通需求的增加，航班延誤開始時緩慢增加，當交通需求增加到某種水平時，航班延誤增長加快，當生產(chǎn)流量接近極限容量時延誤將趨于無窮大。延誤的增加與流量的增長成非線性關系。值機柜臺、安檢通道、邊檢通道和登機門等是處理器，旅客在每個處理器處接受服務時，可能需要排隊等待，所以一般每個處理器處都配有容器，以容納等待的旅客，兩處理器之間設計有通道。機場運行規(guī)劃是指為機場的生產(chǎn)運行所制定的計劃和規(guī)則，包括生產(chǎn)流程的設計和分析、生產(chǎn)資源的配置以及生產(chǎn)調度計劃的制定等內(nèi)容。容量是生產(chǎn)能力的體現(xiàn)，效率是管理水平的體現(xiàn)。ICAO推薦了機場規(guī)劃基本步驟，如圖33所示。在這一過程中，交通需求被不斷反饋到機場容量的規(guī)劃中，影響容量規(guī)劃的制定和修訂。航站樓系統(tǒng)的旅客流程、飛行區(qū)的飛機流程是一種排隊網(wǎng)絡，如圖34所示。若排隊系統(tǒng)是M/M/c系統(tǒng)，并且利用率小于1，則它的輸出率等于輸入率。值機區(qū)的各值機排隊系統(tǒng)是并行的排隊系統(tǒng)。如果值機采用公用設備模式，那么如果實現(xiàn)完全的公用模式，則值機區(qū)是一個排隊系統(tǒng)；如果公用模式只在局部實行，則該局部的所有值機柜臺構成一個排隊系統(tǒng)。國際和國內(nèi)航班安檢一般是分離的排隊系統(tǒng)。因為機場目前常采用公用候機廳方式，旅客也可能去商店購物，候機登機排隊系統(tǒng)比較復雜322 累計分布曲線對于機場旅客流程以及飛機停機坪作業(yè)流程的任一排隊系統(tǒng)，非常簡單又有用的分析工具是累計分布曲線。例如，對于值機排隊系統(tǒng)，該累計曲線的橫軸是航班起飛前的時間，通常是逆向的，縱軸是已到達旅客數(shù)占該航班旅客總數(shù)的比例。圖35 國內(nèi)航班值機旅客累計到達分布曲線323 高峰小時的定義用于機場規(guī)劃基本參數(shù)是機場高峰小時需求，又叫做典型高峰小時，或設計小時、高峰小時(DPH)。高峰小時不是一年中最繁忙的小時，但超過高峰小時（超負荷）的運轉次數(shù)只有很少幾天。因此高峰小時的需求可以用年度預測需求近似計算，%%之間的某個值，%。反之，機場的年吞吐量越小，峰值越顯著，轉換系數(shù)取較大值。但已有一些推薦標準，比較常用的有IATA標準。詳細資料還可以參考本章的附錄1。服務水平等級ABCDE極少旅客托運行李，不用行李車（）每旅客12件行李，不用行李車（）多數(shù)旅客使用行李車（）每旅客帶有2件及以上的重行李，絕大多數(shù)旅客使用行李車（）表33 IATA航站樓處理器時間標準服務水平最短—可接受可接受—最長經(jīng)濟艙值機012(分鐘)1230(分鐘)公務艙值機0335到達護照查驗07715出發(fā)護照查驗05510行李認領0121218安檢0337325 動態(tài)排隊系統(tǒng)分析 排隊論研究了穩(wěn)態(tài)排隊系統(tǒng)的平均指標計算方法，穩(wěn)態(tài)排隊系統(tǒng)要求到達率和服務率在平均意義上是不隨時間變化的常數(shù)。圖36表示了顧客到達率不變，服務率變化情況下隊列長度的變化。隊列存在了Tq=[(nl)/(hn)+1]T=(hl)/(hn)T的時間。 我們再來看這種情況下的旅客到達累計曲線和旅客離開累計曲線，如圖37所示。由于服務率是分段常數(shù)，因此旅客離開累計曲線是分段直線。可以計算出t=a+lT/n到來的第(na+lT)為旅客的延誤時間最長，延誤時間為T(nl)/n。 一般情況下，不但服務率可能變化，而且顧客到達率也會發(fā)生變化。 圖37 圖36情況下的累計曲線a+l/nTT(nl)/nT(nl)/hbab+(nl)/(hn)Tt延誤時間 圖38 旅客延誤分布圖39 一般情況下的顧客累計曲線把累計曲線進行分段線性近似，可以計算出各分段時間區(qū)間端點的顧客排隊長度和相應的排隊時間。 33 航站樓運行規(guī)劃331 旅客的進離港流程我們已知，航站樓是旅客和行李轉換運輸方式的場所，其功能就是要經(jīng)濟有效地讓旅客舒適、方便和快速地實現(xiàn)地面和航空運輸方式的轉換，行李可靠、安全、及時地和旅客同步實現(xiàn)運輸方式的轉換。從圖310可以看出，航站樓內(nèi)旅客進離港路線比較復雜，包含了國內(nèi)出發(fā)、國際出發(fā)、國內(nèi)到達、國內(nèi)到達、過境和中轉流程等多種流程。圖310 機場航站樓作業(yè)流程圖3311值機值機流程分析涉及到以下內(nèi)容：l 值機資源—柜臺的分配方式l 旅客隊列形狀l 航班值機開放時間和關閉時間值機柜臺的分配有兩種方式：專用式和公用式。采用哪種方式取決于以下兩個因素：機場管理當局的資源分配政策。航空公司租用的值機柜臺，也可采用各航班之間公用的形式。有時由于基地航空公司使用了不同的離港系統(tǒng)，值機柜臺只能租給航空公司專用。至于旅客隊列形狀，柜臺采用專用方式時，值機一般采用一個柜臺一個隊列的排隊形狀，形成一個個單服務臺單隊列排隊系統(tǒng)；采用公用方式時，旅客值機隊列有兩種形式： 一個柜臺一個隊列 多個柜臺一個隊列對于第二種隊列形狀，在值機剛開放時，隊列常常較長。排隊論已經(jīng)指出，第二種隊形比第一種隊形更有效率。實際上這種隊列看上去長，旅客的平均排隊時間比單隊列要短許多。有三個運行問題受開放時間規(guī)定的直接影響：行李分揀廳的人力安排。可能造成候機廳座位緊張。對登機門和停機位指派要求高。如果值機時間開放較早，就需要對航班的到港時間做出準確預測，否則難以做到準確指派登機口和停機位，可能造成登機口的更換，因而引起旅客不滿。海關申報完后，進入隔離區(qū)。發(fā)生國際性流行病時，則必須接受規(guī)定的檢查。3314 邊防檢查國際航班旅客必須接受邊防檢查。到達邊檢柜臺時，提交護照查驗。3315 候機和登機安檢結束后，旅客就可以進入候機大廳候機，等待航班登機通知。登機門電子牌顯示開始登機和/或登機廣播后，旅客開始排隊通過登機門登機，在登機口（包括遠機位登機口）處的工作人員掃描旅客登機牌，將旅客信息錄入系統(tǒng)，用于核查是否每位旅客都已登機，如果有已值機的旅客未登機，應通過廣播通知，催其盡快登機。IATA的標準規(guī)定95%的旅客通過廊橋登機。3316 行李認領國內(nèi)航班到港旅客根據(jù)機場行李認領大廳內(nèi)的電子信息屏提供的行李轉盤號，找到和確認自己的行李后取下，通過地面服務人員確認無誤后離開。領取行李后再通過海關和檢驗檢疫檢查后即可離開?！昂ｊP”是旅客報關的地方，出、入境旅客的攜帶物品應當向海關申報。另外還有一些違禁物品是不允許出入境的。檢驗檢疫是對出入境旅客本人及其攜帶的動植物進行檢驗檢疫。邊防檢查是查驗旅客身份，核對是否符合出、入境條件，防止非法出、入境。對于國際旅客，以上三方面的檢查以法不能缺少，但給旅客帶來不便，大大延長了旅客登機準備時間，降低了旅客流程的效率。333旅客流程規(guī)劃 為統(tǒng)一處理旅客流程，可以將航站樓旅客流程劃分為：服務器、容器和連接器三種功能實施，服務器是為旅客辦理登機手續(xù)的場所，如值機柜臺、安檢通道等；容器是旅客排隊和等待休息的場所，如值機大廳、安檢前的安檢排隊場所、候機廳和行李認領廳等；連接器是連接服務器供旅客行走的通道。旅客流程的規(guī)劃可以針對這三種實施分別進行。值機柜臺數(shù)的確定確定值機柜臺的數(shù)量是機場航站樓規(guī)劃中的重要內(nèi)容，這里給出兩種開放式值機柜臺數(shù)量的計算方法。當航班計劃時刻表和值機柜臺旅客到達分布不可獲得時，可以令：X=PHP180。F2其中：PHP=高峰小時經(jīng)濟艙出發(fā)旅客數(shù)；F1=高峰半小時旅客數(shù)占高峰小時旅客總數(shù)比例，可通過表35查得；F2=高峰小時前后的出發(fā)航班所產(chǎn)生的額外值機需求，可通過表36查得。430%25%表36 高峰小時前后的出發(fā)航班所產(chǎn)生的值機需求高峰小時前后一小時旅客量占高峰小時總人數(shù)比例的平均值國內(nèi)申根（Schengen）/短途國際旅客長途國際旅客90%80%70%60%50%40%30%20%10%第二步 根據(jù)X和允許最長排隊時間（Maximum Queuing Time, MQT）查圖317，得標準曲線下X對應的值機柜臺數(shù)的參考值（S）。TP/120 (31)其中TP為平均值機服務時間（秒）。CIY是公務艙旅客需要的值機柜臺數(shù)。2）簡易計算方法第一步 獲得高峰半小時內(nèi)需要提供值機服務的經(jīng)濟艙旅客數(shù)（X）第二步 計算開放式的經(jīng)濟艙值機柜臺數(shù)量（CIY） (33)TMQ為最長排隊時間（分鐘），該式中TP的單位也是分鐘。CIY。最長排隊等待時間20分鐘，高峰小時之前一小時的旅客流量為1900名（占PHP約80%），高峰小時之后的一小時內(nèi)的旅客流量為1500名（占PHP60%），航班值機平均服務時間為150秒，所有的值機服務為開放式值機。解：首先采用IATA計算方法。由于沒有特定的關于高峰半小時的航班信息和旅客到達值機柜臺的分布信息，需要按照IATA提供的計算公式來進行高峰半小時需要接受值機服務的旅客數(shù)量。又高峰小時前后一小時的旅客流量的平均值為1/2（80%+60%）=70，從表36查得F2=，因此高