《运筹学课程设计》由会员分享，可在线阅读，更多相关《运筹学课程设计（11页珍藏版）》请在金锄头文库上搜索。
1、运筹学课程设计报告姓名： 班级： 学号：1、问题描述1.机型指派问题机型指派优化设计是航空公司制定航班计划的重要内容，它要求在满足航班频率和时刻安排以及各机型飞机总数约束的条件下，将各机型飞机指派给相应的航班，使运行成本最小化。本课程设计要求建立机型指派问题的数学模型，应用优化软件 Lindo/Lingo 进行建模求解，给出决策建议，包括各机型执行的航班子集和相应的运行成本。2.问题描述已知某航空公司航班频率和时刻安排表如表 1 所示，航班需求数据和运输距离如表 2所示，其中，Orign A/P 表示起飞机场，Dep.T. 表示目标机场，Dist 表示轮挡距离，Demand 表示航班需求量，S
2、td 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(，)的正态分布。如果机票推销工作
3、做得好，溢出旅客并不全部损失，有部分溢出旅客将改乘本航空公司其他航班，这种现象叫做“再获得”(Recapture)。设有 15%的溢出旅客被再获得。将飞机指到航班上去，并使飞机总成本最小。2、分析建模1建立时空网络图根据航空公司航班时刻安排表，绘制时空网络，横轴方向给出航班飞行涉及的机场，纵轴为时间轴，每个机场一根时间线，从上到下标出每天第一个航班到最后一个航班之间的各时间点，时间线上的圆圈便是节点，标示的时间为该时间线上航班的出发时间或到达时间。2确定决策变量经过对问题描述的分析得出，要解决飞机机型指派问题，需设定两类变量：（1）针对各条航线的机型，令 B737-800 和 B757-200
4、 分别对应机型 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:200
5、7: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
6、:1518:3019:0019:1019:3020:0020:3020:3520:5020:5521:0021:1021:1521:3023:0000:3001:30i XiDistSCAM2,*)(i 1,3.建立目标函数机型指派问题的目标 是使飞机总成本最小（总成本=运行成本+旅客运输成 本）（1）运行成本B737-800 ：C1= （101i 142）B757-200 ：C2= （101i 142）CASM 表示飞机 座英里成本，S 表示飞机座位数，Dist（i）表示第 i 条航线的轮挡距离（2）旅客溢出成本B737-800 ：C1= 旅客溢出成本*（1再获得概率）=（101i 142）
7、B757-200 : C2=旅客溢出成本 *（1再获得概率）= （101i142） RASM 表示飞机座英里收益其中，对于两种机型的旅客溢出期望值E（d）= cdf)(= e-(x2/2)dx/)( )2/1ccx 表示航班需求量的期望， 表示需求的标准差， c 表示飞机的座位数（3）建立目标函数Min C=C1+C2+C1+C2 4.寻找约束条件（1）节点飞机流平衡条件对于每种机型，在时空网络各节点的飞机流必须保持平衡，可将上述时空网络分解为单个机场，以 A 机场为例，其时间线如下图，则有如下约束条件：GA1，i =GA6，i -X110，iGA2，i =GA1，i +X131，iGA3，i
8、 =GA2，i -X111,iGA4，i =GA3，i +X132,ii XiDistRASdE1,*)(*)(%15(i iistM2,)()( GA5，i =GA4，i -X112,iGA6，i =GA5，i +X133,i其中，i=1 或 2同理，可对机场 B，I，J，L，M，O，S 也可列出如上的约束条件。其中除了 J 机场有42 个节点外，其余每个机场都有 6 个节点。对于 A 机场，其时间线如左图则对于机型 B737-800,有如下约束条件：GA1，1 =GA6，1 -X110，1GA2，1 =GA1，1 +X131，1GA3，1 =GA2，1 -X111, 1GA4，1 =GA3
9、，1 +X132, 1GA5，1 =GA4，1 -X112, 1GA6，1 =GA5，1 +X133, 1则对于机型 B737-800,有如下约束条件：GA1，2 =GA6，2 -X110，2GA2，2 =GA1，2 +X131，2GA3，2 =GA2，2 -X111, 2GA4，2 =GA3，2 +X132, 2GA5，2 =GA4，2 -X112, 2GA6，2 =GA5，2 +X133, 2（2）飞机总数约束每基地机场各机型过夜飞机数之和不超过该型飞机的总数对于机型 B737-800，有如下的总数约束：GA6，1 +GB6，1 +GI6，1 +GJ42，1 +GL6，1 +GM6，1 +
10、GO6，1 +GS6，1 9对于机型 B757-200，有如下的总数约束：GA6，2 +GB6，2 +GI6，2 +GJ42，2 +GL6，2 +GM6，2 +GO6，2 +GS6，2 6（3）对每条航线飞机数的限制(任何一个航班有且只有一个机型执行飞行任务)Xi,k=1 ( i 代表航线，如 101；k 代表机型，只能是 1 和 2。) 具体表达如：X101,1+X101,2=1，并且 X101,1 和 X101,2 只能一个取 0，一个取 1。A18:10A212：00A313：10A417:05A518:00A620:35110131111133112132三、模型求解model:!航空
11、公司机型指派问题;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;!机场节点说明，由时间节点和机型派生而成
12、（属性为：某时间节点某机型的飞机总数）;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
13、(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
14、)+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);
15、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
16、(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
