運(yùn)籌學(xué)課設(shè)(航空運(yùn)輸).docx

運(yùn)籌學(xué)課程設(shè)計(jì)報(bào)告姓名：梁盛陽 班級：0709201班 學(xué)號：070920123 一、問題描述1、機(jī)型指派問題 機(jī)型指派優(yōu)化設(shè)計(jì)是航空公司制定航班計(jì)劃的重要內(nèi)容，他要求在滿足航班頻率和時(shí)刻安排同時(shí)不超出飛機(jī)總數(shù)的約束條件下，將各級型飛機(jī)指派給相應(yīng)的航班，使運(yùn)行成本最小化。該設(shè)計(jì)要求先建立機(jī)型指派問題的數(shù)學(xué)模型，然后應(yīng)用優(yōu)化軟件Lingo進(jìn)行建模求解，得出決策結(jié)果，并進(jìn)行合理的分析，包括各機(jī)型執(zhí)行的航班子集和相應(yīng)的運(yùn)行成本。2、問題描述 已知某航空公司航班頻率和時(shí)刻安排和航班需求數(shù)據(jù)和運(yùn)輸距離見課程設(shè)計(jì)指導(dǎo)書，其中，Orign A/P表示起飛機(jī)場，Dep.T.表示起飛時(shí)間，Dest.A/P表示目標(biāo)機(jī)場，Dist表示輪擋距離，Demand表示航班需求量，Std Dev.表示需求的標(biāo)準(zhǔn)差。該航空公司的機(jī)隊(duì)有兩種機(jī)型：9架B737-800，座位數(shù)162；6架B757-200，座位數(shù)200。飛八個(gè)機(jī)場：A、 B、 I、J、L、 M、O、 S。 B737-800的CASM(座英里成本)是0.34元，B757-200是0.36元。 兩種機(jī)型的 RASM（座英里收益）都是 1.2元。以成本最小為目標(biāo)進(jìn)行機(jī)型指派，在成本方面不僅考慮運(yùn)行成本，還必須考慮旅客溢出成本，否則將偏向于選取小飛機(jī)，使航空公司損失許多旅客。 旅客溢出成本是指旅客需求大于航班可提供座位數(shù)時(shí)，旅客流失到其他航空公司造成的損失。旅客需求服從N(,)的正態(tài)分布。如果機(jī)票工作做得好，溢出旅客并不全部損失，有部分溢出旅客將該成本航空公司其他航班，這種現(xiàn)象叫做“再獲得（Recapture）”。設(shè)有15%的溢出旅客被再獲得。將飛機(jī)指派到航班上去，并使飛機(jī)總成本最小。 二、分析建模 1建立時(shí)空網(wǎng)絡(luò)圖根據(jù)航空公司航班時(shí)刻安排表，繪制時(shí)空網(wǎng)絡(luò)，橫軸方向給出航班飛行涉及的機(jī)場，縱軸為時(shí)間軸，每個(gè)機(jī)場一根時(shí)間線，從上到下標(biāo)出每天第一個(gè)航班到最后一個(gè)航班之間的各時(shí)間點(diǎn)，時(shí)間線上的圓圈便是節(jié)點(diǎn)，標(biāo)示的時(shí)間為該時(shí)間線上航班的出發(fā)時(shí)間或到達(dá)時(shí)間。網(wǎng)絡(luò)圖如下頁。 2確定決策變量經(jīng)過對問題描述的分析得出，要解決飛機(jī)機(jī)型指派問題，我設(shè)定了兩類變量：（1） 針對各條航線的機(jī)型，令B737-800和B757-200分別為機(jī)型1和機(jī)型2，設(shè)變量Xi,j.其中101i142,j=1或2。且對于變量Xi, j=0或1，當(dāng)Xi,j=1，表示第i條航線由第j種飛機(jī)運(yùn)營。例如，X101，1=1，則第101號航班由第1種機(jī)型飛行，且X101，2=0。（2）針對機(jī)場時(shí)間節(jié)點(diǎn)飛機(jī)流的變量，設(shè)變量Gm,j.表示對于第m個(gè)節(jié)點(diǎn)上第j種機(jī)型的數(shù)量，例如，GA1，1表示A機(jī)場第1個(gè)節(jié)點(diǎn)上第1種機(jī)型的數(shù)量。以下是時(shí)空網(wǎng)絡(luò)圖：機(jī)場A機(jī)場B機(jī)場I機(jī)場J機(jī)場L機(jī)場M機(jī)場O機(jī)場S5:005:056:156:207:207:257:307:357:407:458:108:159:109:159:309:459:5010:0010:0510:3010:3510:4011:3012:0012:0512:1012:2012:3012:5513:0013:0513:1013:3514:0014:2014:2514:3014:3515:0015:0515:1015:15機(jī)場A機(jī)場B機(jī)場I機(jī)場J機(jī)場L機(jī)場M機(jī)場O機(jī)場S15:2015:2515:3015:4016:0016:1516:3017:0517:1017:3018:0018:0518:1018:1518:3019:0019:1019:3020:0020:3020:3520:5020:5521:0021:1021:1521:3023:000:301:303建立目標(biāo)函數(shù) 機(jī)型指派問題的目標(biāo)是使飛機(jī)總成本最小，而總成本分為兩部分： （1）營運(yùn)成本 B737-800 ：C1= 101i142B757-200 ：C2= 101i142 CASM表示飛機(jī)座英里成本，S表示飛機(jī)座位數(shù)，Dist（i）表示第i條航線的輪擋距離 （2）旅客溢出成本B737-800 ：C1=旅客溢出數(shù)期望值*機(jī)票價(jià)格 = 101i142B757-200 : C2=旅客溢出數(shù)期望值*機(jī)票價(jià)格 = 101i142 RASM表示飛機(jī)座英里收益 其中，對于兩種機(jī)型的旅客溢出期望值 E（d）= =e-(x2/2)dx 表示航班需求量的期望，表示需求的標(biāo)準(zhǔn)差， c表示飛機(jī)的座位數(shù) （3）建立目標(biāo)函數(shù) Min C=C1+C2+C1+C24尋找約束條件（1）節(jié)點(diǎn)飛機(jī)流平衡條件對于每種機(jī)型，在時(shí)空網(wǎng)絡(luò)各節(jié)點(diǎn)的飛機(jī)流必須保持平衡，可將上述時(shí)空網(wǎng)絡(luò)分解為單個(gè)機(jī)場，以A機(jī)場為例，其時(shí)間線如右圖：則對于機(jī)型1，有如下約束條件：GA1，1=GA6，1-X110，1 GA2，1=GA1，1+X131，1 GA3，1=GA2，1-X111,1 GA4，1=GA3，1+X132,1 GA5，1=GA4，1-X112,1 GA6，1=GA5，1+X133,1 對于機(jī)型2，有如下約束條件：GA1，2=GA6，2-X110，2GA2，2=GA1，2+X131，2 GA3，2=GA2，2-X111,2 GA4，2=GA3，2+X132,2GA5，2=GA4，2-X112,2 GA6，2=GA5，2+X133,2同理，可對機(jī)場B，I，J，L，M，O，S也可列出如上的約束條件，其中除了J機(jī)場有40個(gè)節(jié)點(diǎn)外，其余每個(gè)機(jī)場都有6個(gè)節(jié)點(diǎn)。（2）飛機(jī)總數(shù)約束每基地機(jī)場各機(jī)型過夜飛機(jī)數(shù)之和不超過該型飛機(jī)的總數(shù)對于機(jī)型1，有如下的總數(shù)約束： GA6，1+GB6，1+GI6，1+GJ40，1+GL6，1+GM6，1+GO6，1+GS6，19對于機(jī)型2，有如下的總數(shù)約束： GA6，2+GB6，2+GI6，2+GJ40，2+GL6，2+GM6，2+GO6，2+GS6，26（3）對每條航線飛機(jī)數(shù)的限制： Xi,k=1 （i代表航線，如101；k代表機(jī)型，只能是1和2。）具體表達(dá)如：X101,1+X101,2=1，并且X101,1和X101,2只能一個(gè)取0，一個(gè)取1。三.模型求解Model:sets:flight/OLE(data.xls,Flight_No)/:Dist,Demand,std_dev,Orign_AP,Dist_AP;Airport/1.8/; airline/1.42/; !控制變量;Timenode/1.6/; !對于除基地機(jī)場外的7個(gè)機(jī)場，每個(gè)均有6個(gè)節(jié)點(diǎn);Planetype/1,2/:seat,casm; !兩種機(jī)型及其座位數(shù)和座英里成本;flight_assign(flight,Planetype):x; !由航線和機(jī)型組成的指派二維變量;Airparking(Airport,airline,Planetype):G; !由機(jī)場，節(jié)點(diǎn)和機(jī)型組成的三維變量;link/1.84/:flightno,flag; endsetsdata:Dist,Demand,std_dev,Orign_AP,Dist_AP=OLE(data.xls); !用OLE函數(shù)從外部引入數(shù)據(jù)輪擋距離、航班需求量、需求標(biāo)準(zhǔn)差、起飛機(jī)場以及降落機(jī)場;flightno,flag=ole(data2.xls);seat=162,200; casm=0.34,0.36;rasm=1.2; !座英里收益;Recapture=0.15; ！溢出旅客再獲得率;enddata!objective 目標(biāo)函數(shù);min=sum(flight_assign(i,j):x(i,j)*casm(j)*seat(j)*Dist(i)+x(i,j)*rasm*Dist(i)*std_dev(i)*(1-Recapture)*psl(seat(j)-Demand(i)/std_dev(i); !運(yùn)輸成本和旅客溢出成本之和最小;!constraint 約束條件;for(flight_assign:bin(x); !對每條航線的機(jī)型，賦值為二進(jìn)制;for(flight(i):sum(Planetype(j):x(i,j)=1);!各機(jī)場的節(jié)點(diǎn)飛機(jī)流平衡條件如下：G(1,1,1)=G(1,6,1)-x(10,1); G(1,1,2)=G(1,6,2)-x(10,2); ！對兩種機(jī)型過夜節(jié)點(diǎn)與第一個(gè)節(jié)點(diǎn)聯(lián)系；for(planetype(k):for(Timenode(j)|j#ge#2:G(1,j,k)=G(1,j-1,k)+x(flightno(j)-100,k)*flag(j); ！按時(shí)間線上的節(jié)點(diǎn)順序，建立平衡條件；G(2,1,1)=G(2,6,1)-x(16,1);G(2,1,2)=G(2,6,2)-x(16,2);for(planetype(k):for(Timenode(j)|j#ge#2:G(2,j,k)=G(2,j-1,k)+x(flightno(j+6)-100,k)*flag(j+6);G(3,1,1)=G(3,6,1)+x(40,1);G(3,1,2)=G(3,6,2)+x(40,2);for(planetype(k):for(Timenode(j)|j#ge#2:G(3,j,k)=G(3,j-1,k)+x(flightno(j+12)-100,k)*flag(j+12);G(4,1,1)=G(4,42,1)-x(40,1);G(4,1,2)=G(4,42,2)-x(40,2);for(planetype(k):for(airline(j)|j#ge#2:G(4,j,k)=G(4,j-1,k)+x(flightno(j+18)-100,k)*flag(j+18);G(5,1,1)=G(5,6,1)-x(1,1);G(5,1,2)=G(5,6,2)-x(1,2);for(planetype(k):for(Timenode(j)|j#ge#2:G(5,j,k)=G(5,j-1,k)+x(flightno(j+60)-100,k)*flag(j+60);G(6,1,1)=G(6,6,1)-x(13,1);G(6,1,2)=G(6,6,2)-x(13,2);for(planetype(k):for(Timenode(j)|j#ge#2:G(6,j,k)=G(6,j-1,k)+x(flightno(j+66)-100,k)*flag(j+66);G(7,1,1)=G(7,6,1)-x(7,1);G(7,1,2)=G(7,6,2)-x(7,2);for(planetype(k):for(Timenode(j)|j#ge#2:G(7,j,k)=G(7,j-1,k)+x(flightno(j+72)-100,k)*flag(j+72);G(8,1,1)=G(8,6,1)-x(4,1);G(8,1,2)=G(8,6,2)-x(4,2);for(planetype(k):for(Timenode(j)|j#ge#2:G(8,j,k)=G(8,j-1,k)+x(flightno(j+78)-100,k)*flag(j+78);! 每種機(jī)型的飛機(jī)總數(shù)構(gòu)成的過夜飛機(jī)約束條件如下:G(1,6,1)+G(2,6,1)+G(3,6,1)+G(4,42,1)+G(5,6,1)+G(6,6,1)+G(7,6,1)+G(8,6,1)=9;G(1,6,2)+G(2,6,2)+G(3,6,2)+G(4,42,2)+G(5,6,2)+G(6,6,2)+G(7,6,2)+G(8,6,2)=6;end四.結(jié)果分析（1） Xi,j均符合二進(jìn)制數(shù)要求。（2） 對飛機(jī)總數(shù)的約束： 機(jī)型一:G( 1, 6, 1)+G( 2, 6, 1) +G( 3, 6, 1) +G( 4, 42, 1) +G( 5, 6, 1) +G( 6, 6, 1) +G( 7, 6, 1) +G( 8, 6, 1)=1+3+2+1+2=9 滿足約束條件機(jī)型二：G( 1, 6, 2)G( 2, 6, 2)G( 3, 6, 2)G( 4, 42, 2)G( 5, 6, 2)G( 6, 6, 2) G( 7, 6, 2G( 8, 6, 2)=1+2+2=6 滿足約束條件（3） 節(jié)點(diǎn)平衡：G(1,1,1)=G(1,6,1)-x(10,1); G(1,2,1)=G(1,1,1)x(31,1) G(1,3,1)=G(1,1)-x(11,1)0=0-0G(1,4,1)=G(1,3,1)x(32,1) 1=0+1G(1,5,1)=G(1,4,1)-x(12,1) 0=1-1G(1,6,1)=G(1,5,1)+x(33,1) 0=1-1五結(jié)論1. 飛機(jī)機(jī)型指派結(jié)果用第一種機(jī)型，即B737-800,執(zhí)行的航線為：101,102,103,104,105,106,107,108,109,112,115,116,118,1