运筹学课程设计.doc

运筹学课程设计报告姓名： 班级： 学号：1、 问题描述1.机型指派问题机型指派优化设计是航空公司制定航班计划的重要内容，它要求在满足航班频率和时刻安排以及各机型飞机总数约束的条件下，将各机型飞机指派给相应的航班，使运行成本最小化。本课程设计要求建立机型指派问题的数学模型，应用优化软件Lindo/Lingo进行建模求解，给出决策建议，包括各机型执行的航班子集和相应的运行成本。2.问题描述已知某航空公司航班频率和时刻安排表如表1所示，航班需求数据和运输距离如表2所示，其中，Orign A/P表示起飞机场，Dep.T. 表示目标机场，Dist 表示轮挡距离，Demand表示航班需求量，Std Dev.表示需求的标准差。该航空公司的机队有两种机型：9架B737-800，座位数162；6架B757-200，座位数200.飞八个机场：A,B,I,J,L,M,O,S。B737-800的CASM（座英里成本）是0.34元，B757-200是0.36元。两种机型的RASM（座英里收益）都是1.2元。以成本最小为目标进行机型指派，在成本方面不仅考虑运行成本，还必须考虑旅客溢出成本，否则将偏向于选取小飞机，使航空公司损失许多旅客。旅客溢出成本是指旅客需求大于航班可提供座位数时，旅客流失到其他航空公司造成的损失。旅客需求服从N(，)的正态分布。如果机票推销工作做得好，溢出旅客并不全部损失，有部分溢出旅客将改乘本航空公司其他航班，这种现象叫做“再获得”(Recapture)。设有15%的溢出旅客被再获得。将飞机指到航班上去，并使飞机总成本最小。2、 分析建模1建立时空网络图根据航空公司航班时刻安排表，绘制时空网络，横轴方向给出航班飞行涉及的机场，纵轴为时间轴，每个机场一根时间线，从上到下标出每天第一个航班到最后一个航班之间的各时间点，时间线上的圆圈便是节点，标示的时间为该时间线上航班的出发时间或到达时间。 2确定决策变量经过对问题描述的分析得出，要解决飞机机型指派问题，需设定两类变量：（1）针对各条航线的机型，令B737-800和B757-200分别对应机型1和机型2。设变量Xij，其中101i142,j=1或2，变量Xij=0或1，当Xij=1时，表示第i条航线由第j种飞机运营。例如：X101，1=1，则第101号航班由第1种机型飞行，且X101，2=0（2）针对机场时间节点飞机流的变量，设变量GMm,j.表示对于M机场第m个节点上第j种机型的数量，例如，GA1，1表示A机场第1个节点上第1种机型的数量。则建立的时空网络模型如下图所示： 机场A 机场B 机场I 机场J 机场L 机场M 机场O 机场S05:0005:0506:1506:2007:2007:2507:3007:3507:4007:4508:1008:1509:1009:1509:3009:4509:5010:0010:0510:3010:3510:4011:3012:0012:0512:1012:2012:3012:5513:0013:0513:1013:3514:0014:2015:1515:2015:40 机场A 机场B 机场I 机场J 机场L 机场M 机场O 机场S14:2514:3014:3515:0015:0515:1015:1515:2015:2515:3016:0016:1516:3017:0517:1017:3018:0018:0518:1018:1518:3019:0019:1019:3020:0020:3020:3520:5020:5521:0021:1021:1521:3023:0000:3001:303.建立目标函数机型指派问题的目标是使飞机总成本最小（总成本=运行成本+旅客运输成本）（1）运行成本 B737-800 ：C1= （101i142） B757-200 ：C2= （101i142） CASM表示飞机座英里成本，S表示飞机座位数，Dist（i）表示第i条航线的轮挡距离（2）旅客溢出成本B737-800 ：C1=旅客溢出成本*（1再获得概率） =（101i142）B757-200 : C2=旅客溢出成本*（1再获得概率） = （101i142） RASM表示飞机座英里收益 其中，对于两种机型的旅客溢出期望值 E（d）= =e-(x2/2)dx表示航班需求量的期望，表示需求的标准差， c表示飞机的座位数 （3）建立目标函数 Min C=C1+C2+C1+C2 4. 寻找约束条件（1）节点飞机流平衡条件对于每种机型，在时空网络各节点的飞机流必须保持平衡，可将上述时空网络分解为单个机场，以A机场为例，其时间线如下图，则有如下约束条件：GA1，i=GA6，i-X110，i GA2，i=GA1，i+X131，i GA3，i=GA2，i-X111,i GA4，i=GA3，i+X132,i GA5，i=GA4，i-X112,i GA6，i=GA5，i+X133,i 其中，i=1或2同理，可对机场B，I，J，L，M，O，S也可列出如上的约束条件。其中除了J机场有42个节点外，其余每个机场都有6个节点。A18:10A212：00A313：10A417:05A518:00A620:35110131111133112132 对于A机场，其时间线如左图 则对于机型B737-800,有如下约束条件：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 则对于机型B737-800,有如下约束条件：GA1，2=GA6，2-X110，2 GA2，2=GA1，2+X131，2 GA3，2=GA2，2-X111, 2 GA4，2=GA3，2+X132, 2 GA5，2=GA4，2-X112, 2 GA6，2=GA5，2+X133, 2（2）飞机总数约束每基地机场各机型过夜飞机数之和不超过该型飞机的总数对于机型B737-800，有如下的总数约束： GA6，1+GB6，1+GI6，1+GJ42，1+GL6，1+GM6，1+GO6，1+GS6，19对于机型B757-200，有如下的总数约束： GA6，2+GB6，2+GI6，2+GJ42，2+GL6，2+GM6，2+GO6，2+GS6，26（3）对每条航线飞机数的限制(任何一个航班有且只有一个机型执行飞行任务)Xi,k=1 ( i代表航线，如101；k代表机型，只能是1和2。) 具体表达如：X101,1+X101,2=1，并且X101,1和X101,2只能一个取0，一个取1。三、模型求解model:!航空公司机型指派问题;sets:!飞机机型说明（属性为：座英里成本、客英里成本、座位数和飞机总架数）;plane_style/B737,B757/:Casm,Rasm,Num_seat,Num_plane;!航班说明（属性为：轮挡距离、旅客需求量和旅客需求函数标准差）;Flight/1.42/:Dist,Demand,Std_Dev;!机型指派说明，由机型和航班派生而成（属性为决策变量）;assignment(plane_style,Flight):x;!时间节点说明（属性为：航班和飞离或到达信号）;time_node/1.84/:Airline,Flag;!机场节点说明，由时间节点和机型派生而成（属性为：某时间节点某机型的飞机总数）;airport_node(time_node,plane_style):G;endsets!数据;data:Casm,Rasm,Num_seat,Num_plane=0.34,1.2,162,90.36,1.2,200,6;Dist,Demand,Std_Dev=ole(D:071020134_data1.xls);Airline,Flag=ole(D:071020134_data2.xls);enddata!目标函数;min=sum(assignment(I,J): (Casm(I)*Dist(J)*Num_seat(I)+Std_Dev(J)*psl(Num_seat(I)-Demand(J)/Std_Dev(J)*Rasm(I)*Dist(J)*(1-0.15)*x);!约束条件;!将节点飞机数限定为整数;for(airport_node(I,J):gin(G(I,J);!将决策变量限定为0或1;for(assignment(I,J):bin(x(I,J);!每一个航班有且仅有一种机型飞;for(Flight(J):sum(plane_style(I):x(I,J)=1);!过夜边飞机总数限制;for(plane_style(I):G(6,I)+G(12,I)+G(18,I)+G(60,I)+G(66,I)+G(72,I)+G(78,I)+G(84,I)=Num_plane(I);!时间节点平衡约束; for(airport_node(J,K)|J#ne#1#and#J#ne#7#and#J#ne#13#and#J#ne#19#and#J#ne#61#and#J#ne#67#and#J#ne#73#and#J#ne#79:for(Flight(I)|I#eq#airline(J): G(J,K)=G(J-1,K)+Flag(J)*x(K,I);); !部分特殊节点约束; for(plane_style(I):for(Flight(J)|J#eq#Airline(1):G(1,I)=G(6,I)+Flag(1)*x(I,J);for(Flight(J)|J#eq#Airline(7):G(7,I)=G(12,I)+Flag(7)*x(I,J);for(Flight(J)|J#eq#Airline(13):G(13,I)=G(18,I)+Flag(13)*x(I,J);for(Flight(J)|J#eq#Airline(19):G(19,I)=G(60,I)+Flag(19)*x(I,J);for(Flight(J)|J#eq#Airline(61):G(61,I)=G(66,I)+Flag(61)*x(I,J);for(Flight(J)|J#eq#Airline(67):G(67,I)=G(72,I)+Flag(67)*x(I,J);for(Flight(J)|J#eq#Airline(73):G(73,I)=G(78,I)+Flag(73)*x(I,J);for(Flight(J)|J#eq#Airline(79):G(79,I)=G(84,I)+Flag(79)*x(I,J); );end 四、结果分析1.程序运行结果检验（1）节点飞机流平衡条件检查对于每种机型，在时空网络各节点的飞机流必须保持平衡，可将上述时空网络分解为单个机场，（2）过夜飞机总数约束每基地机场各机型过夜飞机数之和不超过该型飞机的总数。对机型1，过夜航班之和是否符合约束条件：G(6,1)+G(12,1)+G(18,1)+G(60,1)+G(66,1)+G(72,1)+G(78,1)+G(84,1)=9; 对机型2过夜航班之和是否满足：G(6,2)+G(12,2)+G(18,2)+G(60,2)+G(66,2)+G(72,2)+G(78,2)+G(84,2)=6;2各个航线的机型指派如下： 机型及航班 决策变量 成本X( B737, 1) 1.000000 190385.7 X( B737, 2) 1.000000 203280.3 X( B737, 3) 1.000000 148950.9 X( B737, 4) 1.000000 204151.8 X( B737, 5) 1.000000 240873.0 X( B737, 6) 1.000000 176110.4 X( B737, 7) 1.000000 51869.45 X( B737, 8) 1.000000 60778.74 X( B737, 9) 1.000000 54298.64 X( B737, 10) 0.000000 68118.39 X( B737, 11) 0.000000 56230.29 X( B737, 12) 1.000000 53271.32 X( B737, 13) 0.000000 104235.6 X( B737, 14) 0.000000 89525.44 X( B737, 15) 1.000000 78250.82 X( B737, 16) 1.000000 10333.09 X( B737, 17) 0.000000 11308.37 X( B737, 18) 1.000000 10374.00 X( B737, 19) 1.000000 13081.39 X( B737, 20) 1.000000 12567.33 X( B737, 21) 1.000000 12558.67 X( B737, 22) 1.000000 153775.3 X( B737, 23) 1.000000 148950.9 X( B737, 24) 1.000000 138258.6 X( B737, 25) 1.000000 157978.0 X( B737, 26) 1.000000 149736.3 X( B737, 27) 1.000000 143571.3 X( B737, 28) 1.000000 41968.56 X( B737, 29) 1.000000 41582.42 X( B737, 30) 1.000000 40924.69 X( B737, 31) 0.000000 54560.21 X( B737, 32) 1.000000 51001.24 X( B737, 33) 0.000000 68118.39 X( B737, 34) 1.000000 76402.29 X( B737, 35) 0.000000 91126.75 X( B737, 36) 0.000000 98564.66 X( B737, 37) 0.000000 11364.93 X( B737, 38) 1.000000 10729.03 X( B737, 39) 1.000000 11308.37 X( B737, 40) 1.000000 12563.18 X( B737, 41) 1.000000 12598.63 X( B737, 42) 1.000000 12615.40 X( B757, 1) 0.000000 190521.9 X( B757, 2) 0.000000 196176.1 X( B757, 3) 0.000000 179016.6 X( B757, 4) 0.000000 201053.0 X( B757, 5) 0.000000 220974.1 X( B757, 6) 0.000000 191050.1 X( B757, 7) 0.000000 55126.59 X( B757, 8) 0.000000 58654.69 X( B757, 9) 0.000000 55941.81 X( B757, 10) 1.000000 63311.56 X( B757, 11) 1.000000 57603.21 X( B757, 12) 0.000000 56616.50 X( B757, 13) 1.000000 94689.16 X( B757, 14) 1.000000 86396.77 X( B757, 15) 0.000000 81717.31 X( B757, 16) 0.000000 13464.12 X( B757, 17) 1.000000 13531.44 X( B757, 18) 0.000000 13464.51 X( B757, 19) 0.000000 16432.70 X( B757, 20) 0.000000 16416.01 X( B757, 21) 0.000000 16416.00 X( B757, 22) 0.000000 179701.6 X( B757, 23) 0.000000 179016.6 X( B757, 24) 0.000000 178224.1 X( B757, 25) 0.000000 187303.1 X( B757, 26) 0.000000 186455.6 X( B757, 27) 0.000000 186200.3 X( B757, 28) 0.000000 53307.35 X( B757, 29) 0.000000 53292.54 X( B757, 30) 0.000000 53280.65 X( B757, 31) 1.000000 56977.20 X( B757, 32) 0.000000 55974.88 X( B757, 33) 1.000000 63311.56 X( B757, 34) 0.000000 8