《运筹学》课程设计报告

运筹学课程设计报告姓名：班级：学号：一、问题描述1、机型指派问题 众所周知，机型指派优化设计是航空公司制定航班计划的重要内容，它要求在满足航班频率和时刻安排以及各级型飞机总数的约束条件下，将各级型飞机指派给相应的航班，使运行成本最小化。本课程设计就是通过建立机型指派问题的数学模型，并应用优化软件Lindo/Lingo进行建模求解，同时给出决策建议，包括各机型执行的航班子集和相应的运行成本。2、问题描述 已知某航空公司航班频率和时刻安排如运筹学课程设计指导书中表1所示，航班需求数据和运输距离如表2所示，其中，OrignA/P表示起飞机场，Dep.T.表示起飞时间，Dest.A/P表示目标机场，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.目标函数以成本最小为求解目标。该成本包括两个部分，第一是运输成本，其表达式为：机型1的架数*每架座位数*座英里成本*该航班的飞行距离+机型2的架数*每架座位数*座英里成本*该航班的飞行距离；第二个为旅客溢出成本，表达式为：机型1旅客溢出的期望值*机型1的架数*机型1的座英里收益*该航班的飞行距离*0.85+机型2旅客溢出的期望值*机型2的架数*机型2的座英里收益*该航班的飞行距离*0.85。2.时空网络建模及其约束条件（1）节点飞机平衡条件对于每种机型，在时空网络中各节点的飞机流必须保持平衡。即对于某一机型的飞机，在某个节点上若有一个航班到达，一个航班出发，则此时该节点所拥有的飞机数目=原有飞机数+到达飞机数-离开飞机数。下面通过各个机场的具体节点进行说明。根据节点平衡条件，节点A1的约束条件：GA1,1=GA6,1-X110,1 （或者为GA1,2=GA6,2-X110,2）GA1,1代表该机场节点现存飞机数目，其中A代表机场，A1,1中前一个1代表机场A的第一个节点，第二个1代表机型1。X110,1中代表飞入或飞出飞机架数，只能为0或1，110代表航班代号，1代表第一种机型。以下约束条件具有相似的意义，将不作详细阐述。并且只详尽列出节点A的约束条件，其他节点的情况可以同理写出。13311213213111111018:0017:0513:1012:0020:358:10 A节点A2的约束条件：GA2,1=GA1,1+x131,1 （ 或者为GA2,2=GA1,2+x131,2）节点A3的约束条件：GA3,1=GA2,1-x111,1 （ 或者为GA3,2=GA2,2+x111,2）节点A4的约束条件：GA4,1=GA3,1+x132,1 （ 或者为GA4,2=GA3,2+x132,2）节点A5的约束条件：GA5,1=GA4,1-x112,1 （ 或者为GA5,2=GA4,2+x112,2）节点A6的约束条件：GA6,1=GA5,1+x133,1 （ 或者为GA6,2=GA5,2+x133,2） B I L M11513511413411312412310312210210121:3013:0515:2018:1021:100:3018:1514:3013:359:459:105:001361371381396:156:156:156:156:156:1523:006:1514:0015:0010:009:10141142119120121116140117118 J13911513010610311216:0016:3017:3018:0512712110912413613311411821:1521:3012321:0020:5520:5020:3020:0019:3019:1019:0018:1012010511110810211710411010110711611912614213512913813213414112813113712512214015:4015:3015:2515:1015:1515:0514:3510:4011:3015:209:3010:3010:3514:2012:3012:1012:0010:059:157:457:407:357:256:20113 O S1271261061251051041301091291081281077:3012:0512:2017:0517:1023:005:059:5012:5515:2521:001:30（2）飞机总数的约束由一般数量关系可知，每个基地机场各机型的过夜飞机数之和不超过该机型飞机的总数，对于B737-800型飞机的数目，有以下约束条件：GA6,1+GB6,1+GI6,1+GL6,1+GM6,1+GO6,1+GS6,1+GJ39,1=9各项的含义在时空网络建模中已经标明。同理对于B757-200型飞机的数目，有以下约束条件：GA6,2+GB6,2+GI6,2+GL6,2+GM6,2+GO6,2+GS6,2+GJ39,2=6（3）每条航线飞机数的限制数学表达式如下所示：2Xi,k=1 其中i代表某一航班，如101航班；k代表机型，只能是1和2。具体表达如： X101,1+X101,2=1，其中X101,1和X101,2只能一个取0，一个取1。k=1三.模型求解model:sets:file/ole(file.xls,flightNo)/:dist,demand,stddev,type1,type2;!引用电子表格，其属性依次包括距离，需求，标准差，机型1，机型2;airport/1.8/;!数字表示相关机场以共有8个，1,2,3,4,5,6,7,8分别表示A,B,I,J,L,M,O,S;airline/1.42/;!数字表示航班，1到42分别表示问题中的101到142航班，一共有有42个航班;!定义派生级，将机场的各个时间节点和对应机场组合成一个二维集合,!M,N分别表示机型1和机型2的机场与时空网络节点的组合;derive(airline,airport):M,N;endsetsdata:dist,demand,stddev=ole(file.xls);!把电子表格里的数据对应赋给相映的变量;enddata !目标函数，以成本最小为目标，成本包括运行成本和旅客溢出成本;min=sum(airline(i):dist(i)*0.34*162*type1(i)+dist(i)*0.36*200*type2(i)+0.85*dist(i)*type1(i)*1.2*stddev(i)*psl(162-demand(i)/stddev(i)+0.85*dist(i)*type2(i)*1.2*stddev(i)*psl(200-demand(i)/stddev(i); for(airline(i):bin(type1(i);!表示执行一个航班机型1的飞机只能取0或1架;for(airline(i):bin(type2(i);!表示执行一个航班机型2的飞机只能取0或1架;for(airline(i):type1(i)+type2(i)=1);!表示执行一个航班的机型数只可能是1;!节点约束条件，即对于每种机型在其时空网络中的各节点的飞机流必须保持平衡;!M，N后面的括号中有两个数字，其中第二个数字表示机场，而第一个数字表示该机场对应的各个时空网络节点;M(1,1)=M(6,1)-type1(10);M(2,1)=M(1,1)+type1(31);M(3,1)=M(2,1)-type1(11);M(4,1)=M(3,1)+type1(32);M(5,1)=M(4,1)-type1(12);M(6,1)=M(5,1)+type1(33);M(1,2)=M(6,2)-type1(16);M(2,2)=M(1,2)+type1(37);M(3,2)=M(2,2)-type1(17);M(4,2)=M(3,2)+type1(38);M(5,2)=M(4,2)-type1(18);M(6,2)=M(5,2)+type1(39);M(1,3)=M(6,3)+type1(40);M(2,3)=M(1,3)-type1(19);M(3,3)=M(2,3)+type1(41);M(4,3)=M(3,3)-type1(20);M(5,3)=M(4,3)+type1(42);M(6,3)=M(5,3)-type1(21);M(1,4)=M(39,4)-type1(40);M(2,4)=M(1,4)-type1(25);M(3,4)=M(2,4)-type1(22);M(4,4)=M(3,4)-type1(37);M(5,4)=M(4,4)+type1(16);M(6,4)=M(5,4)+type1(19);M(7,4)=M(6,4)+type1(7)-type1(31);M(8,4)=M(7,4)-type1(28);M(9,4)=M(8,4)+type1(1);M(10,4)=M(9,4)+type1(4)-type1(34);M(11,4)=M(10,4)+type1(10);M(12,4)=M(11,4)+type1(17);M(13,4)=M(12,4)-type1(41);M(14,4)=M(13,4)+type1(13);M(15,4)=M(14,4)-type1(38);M(16,4)=M(15,4)+type1(8);M(17,4)=M(16,4)-type1(32);M(18,4)=M(17,4)-type1(29);M(19,4)=M(18,4)-type1(35);M(20,4)=M(19,4)+type1(2)-type1(42);M(21,4)=M(20,4)+type1(5);M(22,4)=M(21,4)+type1(20);M(23,4)=M(22,4)-type1(26);M(24,4)=M(23,4)+type1(11);M(25,4)=M(24,4)-type1(23);M(26,4)=M(25,4)+type1(18);M(27,4)=M(26,4)+type1(14);M(28,4)=M(27,4)-type1(33);M(29,4)=M(28,4)-type1(36);M(30,4)=M(29,4)-type1(24);M(31,4)=M(30,4)+type1(9);M(32,4)=M(31,4)+type1(21);M(33,4)=M(32,4)-type1(27);M(34,4)=M(33,4)+type1(12);M(35,4)=M(34,4)+type1(3);M(36,4)=M(35,4)+type1(6);M(37,4)=M(36,4)-type1(30);M(38,4)=M(37,4)+type1(15);M(39,4)=M(38,4)-type1(39);M(1,5)=M(6,5)-type1(1);M(2,5)=M(1,5)-type1(2);M(3,5)=M(2,5)+type1(22);M(4,5)=M(3,5)-type1(3);M(5,5)=M(4,5)+type1(23);M(6,5)=M(5,5)+type1(24);M(1,6)=M(6,6)-type1(13);M(2,6)=M(1,6)+type1(34);M(3,6)=M(2,6)-type1(14);M(4,6)=M(3,6)+type1(35);M(5,6)=M(4,6)-type1(15);M(6,6)=M(5,6)+type1(36);M(1,7)=M(6,7)-type1(7);M(2,7)=M(1,7)+type1(28);M(3,7)=M(2,7)-type1(8);M(4,7)=M(3,7)+type1(29);M(5,7)=M(4,7)-type1(9);M(6,7)=M(5,7)+type1(30);M(1,8)=M(6,8)-type1(4);M(2,8)=M(1,8)-type1(5);M(3,8)=M(2,8)+type1(25);M(4,8)=M(3,8)-type1(6);M(5,8)=M(4,8)+type1(26);M(6,8)=M(5,8)+type1(27);!机型1过夜飞机数约束条件，过夜飞机的总数必须小于或者等于机型1的总数9;M(6,1)+M(6,2)+M(6,3)+M(39,4)+M(6,5)+M(6,6)+M(6,7)+M(6,8)=9;N(1,1)=N(6,1)-type2(10);N(2,1)=N(1,1)+type2(31);N(3,1)=N(2,1)-type2(11);N(4,1)=N(3,1)+type2(32);N(5,1)=N(4,1)-type2(12);N(6,1)=N(5,1)+type2(33);N(1,2)=N(6,2)-type2(16);N(2,2)=N(1,2)+type2(37);N(3,2)=N(2,2)-type2(17);N(4,2)=N(3,2)+type2(38);N(5,2)=N(4,2)-type2(18);N(6,2)=N(5,2)+type2(39);N(1,3)=N(6,3)+type2(40);N(2,3)=N(1,3)-type2(19);N(3,3)=N(2,3)+type2(41);N(4,3)=N(3,3)-type2(20);N(5,3)=N(4,3)+type2(42);N(6,3)=N(5,3)-type2(21);N(1,4)=N(39,4)-type2(40);N(2,4)=N(1,4)-type2(25);N(3,4)=N(2,4)-type2(22);N(4,4)=N(3,4)-type2(37);N(5,4)=N(4,4)+type2(16);N(6,4)=N(5,4)+type2(19);N(7,4)=N(6,4)+type2(7)-type2(31);N(8,4)=N(7,4)-type2(28);N(9,4)=N(8,4)+type2(1);N(10,4)=N(9,4)+type2(4)-type2(34);N(11,4)=N(10,4)+type2(10);N(12,4)=N(11,4)+type2(17);N(13,4)=N(12,4)-type2(41);N(14,4)=N(13,4)+type2(13);N(15,4)=N(14,4)-type2(38);N(16,4)=N(15,4)+type2(8);N(17,4)=N(16,4)-type2(32);N(18,4)=N(17,4)-type2(29);N(19,4)=N(18,4)-type2(35);N(20,4)=N(19,4)+type2(2)-type2(42);N(21,4)=N(20,4)+type2(5);N(22,4)=N(21,4)+type2(20);N(23,4)=N(22,4)-type2(26);N(24,4)=N(23,4)+type2(11);N(25,4)=N(24,4)-type2(23);N(26,4)=N(25,4)+type2(18);N(27,4)=N(26,4)+type2(14);N(28,4)=N(27,4)-type2(33);N(29,4)=N(28,4)-type2(36);N(30,4)=N(29,4)-type2(24);N(31,4)=N(30,4)+type2(9);N(32,4)=N(31,4)+type2(21);N(33,4)=N(32,4)-type2(27);N(34,4)=N(33,4)+type2(12);N(35,4)=N(34,4)+type2(3);N(36,4)=N(35,4)+type2(6);N(37,4)=N(36,4)-type2(30);N(38,4)=N(37,4)+type2(15);N(39,4)=N(38,4)-type2(39);N(1,5)=N(6,5)-type2(1);N(2,5)=N(1,5)-type2(2);N(3,5)=N(2,5)+type2(22);N(4,5)=N(3,5)-type2(3);N(5,5)=N(4,5)+type2(23);N(6,5)=N(5,5)+type2(24);N(1,6)=N(6,6)-type2(13);N(2,6)=N(1,6)+type2(34);N(3,6)=N(2,6)-type2(14);N(4,6)=N(3,6)+type2(35);N(5,6)=N(4,6)-type2(15);N(6,6)=N(5,6)+type2(36);N(1,7)=N(6,7)-type2(7);N(2,7)=N(1,7)+type2(28);N(3,7)=N(2,7)-type2(8);N(4,7)=N(3,7)+type2(29);N(5,7)=N(4,7)-type2(9);N(6,7)=N(5,7)+type2(30);N(1,8)=N(6,8)-type2(4);N(2,8)=N(1,8)-type2(5);N(3,8)=N(2,8)+type2(25);N(4,8)=N(3,8)-type2(6);N(5,8)=N(4,8)+type2(26);N(6,8)=N(5,8)+type2(27);!机型2过夜飞机树的条件，即过夜飞机的总数必须小于或者等于机型2的总数6;N(6,1)+N(6,2)+N(6,3)+N(39,4)+N(6,5)+N(6,6)+N(6,7)+N(6,8)=6;end四.结果分析1.通过约束条件对程序运行结果进行检验。例如，各个机场的机型1过夜航班之和是否符合约束条件：M(6,1)+M(6,2)+M(6,3)+M(40,4)+M(6,5)+M(6,6)+M(6,7)+M(6,8)=9;!过夜飞机数约束条件，具体意义见实验报告过夜航班（前面的数字代表节点，后面的代表机场） 飞机架数 M( 6, 1) 0. M( 6, 2) 1. M( 6, 3) 0. M( 39, 4) 3. M( 6, 5) 2. M( 6, 6) 0. M( 6, 7) 1. M( 6, 8) 2. 各项之和为9，符合该条件。又有约束条件如下，为各个机场的机型2过夜航班之和N(6,1)+N(6,2)+N(6,3)+N(40,4)+N(6,5)+N(6,6)+N(6,7)+N(6,8)=6;对于该约束条件，有以下测试结果： N( 6, 1) 1. N( 6, 2) 0. N( 6, 3) 0. N( 39, 4) 2. N( 6, 5) 0. N( 6, 6) 2. N( 6, 7) 0. N( 6, 8) 0. 各项之和为5，小于6，符合条件。2各个航线的机型指派如下：航班与对应的机型飞机架数 TYPE1( 101) 1. TYPE1( 102) 1. TYPE1( 103) 1. TYPE1( 104) 1. TYPE1( 105) 1. TYPE1( 106) 1. TYPE1( 107) 1. TYPE1( 108) 1. TYPE1( 109) 1. TYPE1( 110) 0. TYPE1( 111) 0. TYPE1( 112) 1. TYPE1( 113) 0. TYPE1( 114) 0. TYPE1( 115) 1. TYPE1( 116) 1. TYPE1( 117) 0. TYPE1( 118) 1. TYPE1( 119) 1. TYPE1( 120) 1. TYPE1( 121) 1. TYPE1( 122) 1. TYPE1( 123) 1. TYPE1( 124) 1.