飛機(jī)排隊(duì)問(wèn)題

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

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

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

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