飛機排隊問題

問題一飛機排隊問題⑴問題機場通常都有用“先來后到”的原則分配飛機跑道.即當飛機準備離開登機口時，駕駛員電告地面控制中心，加入等候跑道的行列.假設控制塔可以從快速反應數(shù)據(jù)庫中得到每架飛機的如下信息：1） 預定離開登機口的時間；2） 實際離開登機口的時間；3） 機上乘客人數(shù)；4） 預定在下一站轉機的人數(shù)和轉機時間；5） 到達下一站的預定時間.又設共有7種飛機，載客量從100人起以50人遞增，最大的飛機載客量為400人.這7種飛機可能分屬不同的航空公司.試開發(fā)和建立一種能使乘客和航空公司雙方都滿意的數(shù)學模型，以安排飛機起飛的先后次序.（2） 假設1） 機場控制塔上有一個快速反應的數(shù)據(jù)庫，該庫中存貯著每一架飛機的正點起飛時間，正點抵達目的地的時間，乘客數(shù)量，飛行距離等信息,其他一些有用的參數(shù)，可以根據(jù)數(shù)據(jù)庫中已有數(shù)據(jù)估計出來.2） 所有飛機都在同一專用跑道上起飛，任何一種飛機在跑道上起飛所需要的時間相同，這樣可以把時間劃分成間隔為△的起飛時段.3） 標號為i的飛機在第j個時段起飛所需費用與先前起飛的飛機無關，僅與其安排的次序有關.這一假設使我們可以把總費用作為飛機調度排序的線性函數(shù).4） 所有飛機從登機口到跑道起點的時間相同.5） 記t為使飛機尚能正點到達目的地所推遲起飛的最長時間.同時假定，當飛機的誤點時間超過t時,則飛機將以最大的安全速度飛行.6） 如果飛機推遲起飛的時間超過t,則機上所有下站轉機的乘客都將耽誤轉機.7） 因誤點而要求改航的賠償費對每一個乘客都是相同的.（3） 記號及意義△：飛機起飛的時間間隔；‘0最早起飛的飛機離港時間； 'd:正點起飛的時間；ta:正點到達目的地的時間； t:晚點時間；T：最大允許晚點起飛的時間；k:各種類型的飛機因晚點起飛而引起耗油的費用常數(shù)；^仲:平均飛行速度； ymax:最大的安全飛行速度；r:要求改航的乘客的賠償費； n:下站轉機的乘客數(shù)；P:乘客總數(shù)；:由于晚點起飛所引起的乘客不滿意程度的增長率；a:全體乘客由于飛機晚點起飛所引起的不滿意度折合成美元的折合率；b:耽誤轉機的乘客不滿意度折合成美元的折合率.★分析與建模若有n架飛機都要求在時刻正點起飛，并且認為所有飛機都有直通跑道.我們以總費用最小作為目標來安排飛機起飛的次序.總費用由兩部分組成，即航空公司的費用和乘客不滿意程度所折合的費用.設°〃?為標號i的飛機在第j個起飛時段起飛的費用，引入狀態(tài)變量X，其定義為=J1,當標號為i的飛機第j個起飛七=| 0,其它則總費用為一nnZ=ZZexi=1j=1為了保證每一架飛機只安排在一個時段內起飛及每一個時段△內只有一架飛機起飛，因此對狀態(tài)變量xij增加約束條件：zx=1,i=1,2,...,n x=1,j=1,2,...,ni j=1由假設條件可知，七與*^.無關，因而總費用C是一個線性函數(shù).

這是一個指派問題.假定每隔△時間只有一架飛機離開登機口加入到請求起飛的行列中，這樣就保證總有飛機請求起飛.每隔△時間，執(zhí)行一次程序，以安排在當前狀態(tài)下最優(yōu)的起飛次序.這里需要說明一點，該程序運行時間極短，不到一分鐘便可完成，因此，如果數(shù)據(jù)發(fā)生變化時,如飛機晚點進港等，幾乎可以立即決策.★下面來分析費用系數(shù)的確定問題.總費用應包括航空公司的費用和乘客的不滿意度所折合的費用.首先把基本費用視為0,即設飛機在正點起飛時的費用為0,僅考慮由于飛機晚點起飛所導致的額外費用.航空公司的費用主要由兩部分組成.一部分為額外的汽油費，這個費用主要是由于飛機晚點起飛時，要在空中快速飛行所額外消耗的汽油費;另一部分為耽誤了轉機的乘客需要改航時的賠償費.若飛機晚點起飛，為了正點抵達目的地,它必須在空中以更快的速度飛行,這樣由于風阻力的增大和其它因素，就要增加汽油的消耗.我們不太清楚速度的增加如何引起耗油費和增加，但當飛機加速過程結束,在空中以最大安全速度飛行時,額外的耗油費將是一個常數(shù).為簡單起見，選用線性函數(shù)來表示額外的油耗費，其公式為:kt,t<t燈,t>T其中J為飛機晚點起飛的時間，顯然當飛機正點起飛時J=0,若to為首架起飛的時刻，？為正點起飛的時刻,△為起飛的時間間隔，則第j個起飛的飛機晚點起飛的時間為:t=t+(j-1)A-10 d由于T為最長的晚點起飛時間，即當晚點起飛的時間超過T以后，即使在空中以最大速度飛行，也不能正點抵達目的地，因此e dVmaxT=T—tVmaxAd其中tA為正點抵達目的地的時刻,d為飛行距離，ymax為最大的安全飛行速度.d可用公式來表示d="匕其中七為正點起飛時刻，Vav為正點起飛時平均飛行速度.常數(shù)k與油價、單位晚點時間油耗的增加率及最大安全飛行速度有關，同時還應與飛行距離有關，當然飛行距離越長，額外的油耗就越大.由于飛行距離為Ta-td-T,乘以最大安全飛行速度,則有:F(t)=,(廠'尸*,<T\k(T-1-t)r,t>tAd下面再計算改航旅客的賠償費.為簡單起見，由假設條件，記每一個改航旅客的賠償費用為一個常數(shù)r(若賠償不同，則令r為賠償?shù)钠谕?.由于當飛機晚點起飛時，所有下站轉機的乘客都將改航,則改航的賠償費為：R(t)=rnu(t-t)n為轉機旅客總數(shù),u(t)為單位階梯函數(shù)，即'0,S<0u(s)=<、1,s>0費用系數(shù)中還應考慮乘客的不滿意程度.一般地,飛機晚點起飛的時間越長，旅客就越抱怨，其不滿意程度就越大.如果晚點時間只有1~2分鐘,旅客就不會太不滿意.但是，隨著晚點時間的增加，旅客會非常生氣，而不滿意度會急驟增加，因此我們選用指數(shù)函數(shù)描述旅客的不滿意程度.這個不滿意程度對機上每一旅客都是如此，但對下站要轉機的乘客,還需要追加另外的不滿意度，用D(t)表示總的不滿意程度所折合的費用，則D(t)=ap(eB-1)+bnu(t-t)p為機上乘客總數(shù),n為下站轉機的乘客總數(shù),為了保證在正點起飛時乘客的不滿意度為0,因而采用了(欲-1)的形式，顯然t=0時,D(0)=0.a為乘客不滿意度的

增長率,a,b為折合率，ap（伽T）代表全體乘客不滿意度折合的費用，b兀"（…）為下站轉機乘客追加的不滿意度所折合的費用,這一項只有當t>t才起作用.綜上所述，費用系數(shù)^..應為額外油耗費、賠償費、及不滿意度所折合的費用之和c=F（t）+R（t）+D（t）jgt<tcij…,d“，cij=< k(T—t—t)t+ap(e^t—1),t<tvtk(T-1-t)t+ap(e^-1)+m+b兀,t>tAdt和T由下式給出0dtmaxt=t-1+(j-1)A0dtmax2）計算實例為了執(zhí)行簡單，再作一些假設。1）至多有三架飛機等候飛行（即nW3），如果不足三架，在模型中增加一架或兩架虛擬的飛機，虛擬的飛機的費用系數(shù)視為0。2） 任何飛機起飛時間至多1分鐘，即△=1，其間，其它飛機不能占用跑道。3） 跑道上沒有飛機降落；4） 每一個改航旅客的賠償費用為350美元；5） 一個要改航乘客的不滿意度是誤點15分鐘的乘客的2倍乘客多的飛機先起飛例有A,B,C三架飛機都已離開了登機口，要求在上午6點鐘正點起飛，這三架飛機將飛往三個不同城市，但空中飛行距離都相同，正點抵達目的地的時間均為上午7點20分.另外，其乘客數(shù)量分別為350,100,400,且每架飛機上都有100名乘客將在下一站轉機.

執(zhí)行結果為:標號乘客數(shù)/轉機乘客數(shù)費用系數(shù)解A350/10000.480.97010B100/10000.410.83001C400/10000.51100其最小費用為1.31,起飛的次序為C,A,B.這一結果與我們的直覺完全一致，即在其它條件相同的情況下，乘客數(shù)量多的飛機優(yōu)先起飛.誤點時間最長的飛機優(yōu)先起飛接著上面問題，飛機C正在起飛的同時，飛機D已經(jīng)離開了登機口請求起飛.已知飛機D載有200名乘客，其中150名將在下站轉機，這架飛機已經(jīng)晚點18分鐘，要使飛機D正點抵達目的地,必須在2分鐘內起飛（即必須在6點02分或6點03分兩個起飛時段內起飛）.執(zhí)行結果如下表.標號乘客數(shù)/轉機乘客數(shù)已晚點時間（min）費用系數(shù)解D200/150180.280.911100B100/10010.070.150.22001A350/10010.090.170.26010這個例子中的總費用為1.22，最優(yōu)的起飛次序為D,A,B.這一結果與直覺相符，即晚點時間最長的飛機優(yōu)先起飛.優(yōu)先權相差不明顯的情形當系統(tǒng)時鐘指向6點03分，此時C,D,A三架飛機已先后起飛，飛機B已晚點3分鐘，而又有一架飛機E離開登機口，請求起飛.對飛機E,我們知道如下信息:總乘客數(shù)不122名，其中89名乘客在下站轉機，晚點1分鐘的費用為450美元;最長的晚點時間為45分鐘.在求解時,須增加一架虛擬飛機X,對應于飛機X的所有參數(shù)為0.結果如下:標號乘客數(shù)/轉機乘客數(shù)已晚點時間（min）費用系數(shù)解B100/10030.60.81010E122/89000.280.56100X0/00000000從上表可以看到，總費用之差0.88-0.8=0.08,這個數(shù)目不太大，因而究竟哪架飛機應該先起飛不甚明顯.事實上，由于飛機E有較多的富裕時間，因而應先安排飛機B起飛.但是，由于飛機E在飛行時費用較大，以及有更多的乘客，因而飛機E應先起飛，這與模型的結果一致.問題二生產(chǎn)計劃鑄鐵廠要生產(chǎn)一種規(guī)格的鑄件共10t.其成分要求為：錳含量至少達到0.45%,硅含量允許在3.25%~5.5%，市場有充分的錳和三種不同型號的生鐵可供作鑄件的爐料使用，它們價格是錳每千克75元，A種生鐵每噸1700元，B種生鐵每噸1900元，C種生鐵每噸1400元.三種生鐵含錳和硅的成分百分比(％)如表所示ABC錳0.40.50.35硅410.5若不計冶煉鑄造過程中的損耗，問工廠怎樣選擇爐料能使成本最低？解：建立模型設用A種生鐵x1噸，用B種生鐵%2噸，用C種生鐵x3噸，用錳%4噸，且由題知每千克錳75元，則每噸錳要75000元，z為最低成本，于是有關系式：z=1700氣+1900x2+1400%+75000七我們稱其為目標函數(shù)，生產(chǎn)條件可以表示為：‘0.0004尤+0.0005x+0.00035x+0.1x>0.00450.004x+0.001x+0.0005x>0.0325' 0.004x1+0.001x2+0.0005x3<0.055x,x,xx>0I 1 2 3,4此問題是一個優(yōu)化問題，解決此問題的過程就是優(yōu)化的建模過程。然后求出X1,X2,X3，^4，使得生產(chǎn)成本最小。下面是求目標函數(shù)的程序的詳細過程，以及氣，%2'%3'%4的具體值。min=1700*x1+1900*x2+1400*x3+75000*x4;0.0004*x1+0.0005*x2+0.00035*x3+0.1*x4>=0.0045;0.004*x1+0.001*x2+0.0005*x3>=0.0325;0.004*x1+0.001*x2+0.0005*x3<=0.055;x1>=0;x2>=0;x3>=0;x4>=0;Globaloptimalsolutionfound.Objectivevalue:Totalsolveriterations:14750.003VariableValueReducedCostX18.1250000.000000X20.0000001175.000X30.000000962.5000X40.1250000E-010.000000RowSlackorSurplusDualPrice114750.00-1.00000020.00000