数学建模竞赛优秀论文
-
—
2015
湖南省研究生数学建模竞赛参赛承诺书
我们仔细阅读了湖南省研究生数学建模竞赛的竞赛规则
.
我们完全明白，
在竞赛开始后参赛队员不能以任何方式（包括电话、
电子邮件、网上咨
询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题
。
我们知道，
抄袭别人的成果是违反
竞赛规则的
,
如果引用别人的成果或其他公开的资料
（包括网上查到的资料）
，必须按照规定的参考文献的表述方式在正文引
用处和参考文献中
明确列出。
我们郑
重承诺，
严格遵守竞赛规则，
以保证竞赛的公正、
公平性。
如有违反竞赛规则的
行为，我们将受到严肃
处理。
我们授权湖南省研究生数学建模竞赛组委会，
可将我们的论文以任何形式进行公开展示
（包括进行网上公示，在书籍、
期刊和其他媒体进行正式或非正式发表等）
。
我们参赛选择的题号是（从组委会提供的试题中选择一项填写）
：
我们的参赛报名号为（如果组委会设置报名号的话）
：
所属学校（请填写完整的全名）
：
参赛队员
(
打印并签名
)
：
1.
2.
3.
指导教师或指导教师组负责人
(
打印并签名
)
：
日期：
年
月
日
评阅编号（由组委会评阅前进行编号）
：
欢迎下载
—
2015
湖南省研究生数学建模竞赛
编
号
专
用
页
评阅编
号（由组委会评阅前进行编号）
：
评阅记录（可供评阅时使用）
：
评
阅
人
评
分
备
注
欢迎下载
—
湖南省首届研究生数学建模竞赛
题
目
航班计划的合理编排
摘
要
:
本文从
提高飞机利用率，
降低运行成本，
提高航空公司经济效益等角度
出发，
来研究航班计划的合理编排。我们先后建立了，相关性分析模型，
0-1
整数规划
模型，改进的
0-1
整数规划，鲁棒性评价模型等模型，并运用
matlab
，
spss
等相
关软件对各模型进行求解，进而对题中各问题给出了相应的解答。
针对问题
1
，首先对附件
1
中的数据进行了检查，并合理地更改了一些不合
理的数据，
例如对附件
1
中餐食费为
0
的数据我们进行了合理的更改
（见附录附
表
1
）
。其次，为了找到影响航班收益的主要因素，我们求出了各航线的收益，
建立了相关性分析模型，
并给出了附件
1
< br>中各因素与航班收益的相关系数。
通过
对相关系数排序，
我们找出了
8
各主要因素（见表
1
）
。同时基于这
8
个主要因
素，我们对亏损航线提出了相应的整改措施。
针对问题
2
，首先根据问题中的假设条件，我们将求解航空公司收益最大化
问题转化为了求解飞机利
用率最高的问题。
为使飞机利用率最高，
我们假设每架
飞机每天的最大飞行时间为
17.5
小时，并针
对西安、天津两个独立基地以及
A320
、
E190
两种机型分别建立了
4
个
0-1
整数规划模型，
并将其转化为<
/p>
NP-hard
问题求解。我们利用动态规划算法，通过
matlab
软件求解，计算出航空公司最
少需
要再去租
4
架
A320
机型和
2
架
E190
机型的飞机。
同时，
我们还制定了下个
月的航班计划（见附录附表
1
）
，并计算出公司的最大收益为
4237.1
万元。
针对问题
3<
/p>
，在问题
2
的基础上，我们进一步考虑了
飞机累计飞行
130
小时
就必须在维修
基地停场维修
24
小时的条件，进而建立了改进的
0-1
整数规划模
型。通过对模型进行求解，我们计
算出在问题
2
的基础上至少需要增加
A
320
机
型和
E190
机型的飞机各
2
架，
同时列出
了一份各飞机停场排班表
（见表
11-14
）
。
针对问题
4
，首先给出了评价航班计划“鲁棒性”的评判标准。
基于该评判
标准，我们对问题
2
中制定
的航班计划的“鲁棒性”进行了评价。通过评价结果
我们发现问题
2
的中制定的航班计划的
“鲁棒性”
较差。
为了提高航班计划的
“鲁
棒性”
，减少航班延误对后续航班的影响，我们根据“鲁棒性”评判标准，建立
了带有
“鲁棒性”
约束条件的新
0-1
规划整数模型。
通过
matl
ab
对该模型求解，
我们制定了具有较好“鲁棒性”的航班计划
（见附录附表
2
）
。
< br>
关键词
：相关性分析法，整数规划，动态规划
欢迎下载
—
一
问题重述
航班计划是航空公司运输生
产计划的具体实施计划，
它规定了飞行的航线、
航段、
机型、
航班号、班次和班期、
（起降）时刻等。
一个合理的航班计划应该既有助于航班的安全运行，
又能提高飞机的利用率，还可以有效
地降低运营及维护成本，提高公司的经济效益。
国内某个以客
运为主的航空公司，该公司运行指挥中心每个月的月末都会对本月各航
线、
机型的收益情况进行市场分析，
然后结合本公司现有的生产资源情况
（包括现有可飞航
线、
不同类型的飞机数量等）
编排下一个月的航班计划，
在航班计划制定之后需送给机务部<
/p>
门进行飞机排班作业（安排每架飞机执行飞行的航班）
，机务部门
在制定飞机排班计划时主
要考虑满足飞机维修的需要，
飞机排班
计划完成以后形成可执行的航班计划，
该计划需下发
到飞行总队
具体执飞。
已知该公司有两种类型的飞机，
< br>A320
飞机
2
架和
E190
飞机
4
架，维修
基地设在西安和
天津。由于航线（航权）资源是航空公司的稀缺资源，所以制定航班计划
时一般不会取消，
也不会随意拆分带有经停航点的航线。
在航班
计划制定时，
若本公司飞机数量无法满足现有
航线需要，可向专
业的飞机租赁公司申请租赁（租金：
A320
，
33
万美金
/
月架；
E190
，
25
万美金
/
月架）
；反之，若在满足现有航线需
要的前提下，本公司尚有一定数量的剩余飞机，
则可作为备用飞机在航线发生延误及飞机
出现临时故障时使用，
或者直接出租给其它航空公
司以便获取额
外利润。
附件
1
给出了该公司某月各航线单日运行成本及
（收入）
明细表，
假定每个
航线每日只安排一个班次的飞机，
附件二是航空公司航班延误统计表，
现要求通
过数学建模完
成以下任务
:
1
、对附件
1
中给出的数据进行航线收益分析，找出影响收益的主要因素，
并根据分析结果提出针对亏损航线的整改措施。
2
、为简化问题，假定各航线的航班时刻可以根据需要变动，同时假定现有
飞行航线和航空公司的营销能力是稳定的
（航线、
平
均客座率、
平均折扣率不变）
，
请为航
空公司制定一份下个月的航班计划，使航空公司的收益最大化。
3
、如果继续考虑满足飞机维修需要，即每架飞机累计飞行
1
30
个小时就必
须在维修基地停场维修一次，每次停场时间为<
/p>
24
小时。那么，在不改变问题
2
中所求航班计划的情况下，
要使航空公司正常营运，
< br>至少需要新增加两种类型的
飞机各多少架？
4
、航班计划的“鲁棒性”是生产运行过程中需要考虑的一个重要因素，即
设定一定的时间裕度以便在出现某一航班延误时能够减少对后续航班的影响。
根
据附件
2
中给出的数据
请评价问题
2
中求得的航班计划的“鲁棒性”
< br>，并重新制
定一个带有“鲁棒性”约束的最优航班计划。
二
问题分析
2.1
问题
1
的分析
< br>首先对附件
1
中的数据进行检查，
更改一些不合理的数据。
为了影响分析航
空公司收益的主要因
素，
我们可以建立相关性分析模型求解。
通过对相关系数排
序，我们可以确定出主要因素，并基于主要因素对亏损航线进行整改。
欢迎下载
—
2.2
问题
2
的分析
在假设航线、
平均客座率、
平均折扣率
不变的情况下，
再假设各类航线成本
仅与航线本身有关，
则航空公司的收益最大化就可以转化为飞机利用率最高的问
题。进而我
们可以建立
0-1
规划模型，并通过动态规划算法进行求解。<
/p>
2.3
问题
3
的分析
在问题
2
的基础上，要考虑停场维修时
间，可以通过改进问题
2
中建立的
0-
1
规划模型，在改进的模型中考虑到停场维修的约束条件，进而就可求出需要
增加的飞机数。
2.4
问题
4
的分析
要评价问题
2
中的航班计划的“鲁棒性
”
，我们首先得建立“鲁棒性”评判
标准。
然后，
我们就可以根据评判标准去评价问题
2
中的航班计划的
“鲁棒性”
，
并进而建立具有较好“鲁棒性”的航班计划。
三
模型假设与符号说明
3.1
模型假设
1.
假设飞机航行过程中不会出现意外故障。
2.
不考虑不同城市的经济水平、地理方面的差异。
3.
每个航线只安排一个班次的飞机。
4.
当重新编排航班的时候，
我们假定每条航线从一个月的一号开始运营，
一
个月以
30
天计。
3.2
符号说明
N
< br>:
所需最少的飞机架数
i
：第
i
条航线
<
/p>
j
：第
j
架飞机
T
:
一天中
航班安排的时间限制
s
：一天中飞机最大飞行时间
t
i
：飞机飞行第
i
条航线所需时间
< br>1,
第
j
架飞机飞第
i
条航线
x
ij
0
，否则
x
ij
：第
i
天第
j
架飞机是否处于停场状态，停场为
0
，否则为
1
b
：原来每天需要的飞机数
s
j
：一架飞机在一个月内处于停场状态的最少
天数
欢迎下载
—
T
j
：第
j
架飞机在原计划中的飞行时间
四
模型的建立与求解
4.1
影响收益的主要因素
4.1.1
数据的分析
首先先对附件
1
中的数据进行检查，合理地更改一
些不合理的数据。例如，
更改了附件
1
中餐食费为
0
的相关数据（见附录附表
1
）
。
4.1.2
相关性分析模型的建立与求解
相关性
分析是指对两个或多个具备相关性的变量元素进行分析，
从而衡量两
个变量因素的相关密切程度。
相关性的元素之间需要存在一定的联系或者概率才
可以进行相关性分析。
问题
1
是探索各个因素与公司收益的相关程度，
故我们可
以
采取相关分析法
[1]
。
首先我们利用更改了附件
1
提供的数据，
计算出该航空公司每条航线的总收
入，总支出，然后利用“收益
=
总收入
-
总支出”计
算出每条航线的收益，然后计
算各个因素与收益的相关系数。
相关系数的计算公式：
r
ij
(x
k
1
n
n
ki
x
< br>i
)(x
kj
x
j
)
x
i
)
2
(x
kj
x
j
)
2
<
/p>
(x
k
1
ki
为变量
x
i
与变量
x
j
的相关系数，
其中
x
i
是变量
x
i
的均值，
其中
x
j
是变量
x
j
的
均值，并且相关系数越大表示两个变量间的相关性越高。
利用
matlab
软件编程求解，我们求得各因素与收益的相关
系数，并对其从
大到小进行排序：
表
1
：影响收益因素与收益的相关系数
相关系数
0.6054
0.4862
0.4700
0.4686
0.4657
0.4437
0.4174
0.3749
收益相关因素
平均折扣率
航材维修费
全价票价格
不正常航班费用
机供品
客座率
发动机维修费
座位数
欢迎下载
—
0.2370
0.2307
0.2275
0.2181
0.0675
-0.1027
-0.2513
起降及非航空性业务费
航油费
耗油量
机组人员工资
保险费
-
旅客责任险
餐费
航材消耗
4.1.3
模型结果分析
我们选取相关系数较大的前
8
个因素作为影响航
空公司收益的主要因素。
从
上表中可以看到，
< br>主要因素中包含了平均折扣率、
航材维修费、
全价票价格
等因
素。
这些因素和我们的主观思考的结果很一致，
这就说明我们用相关性分析获得
的主要因素还是比较合理的。
为了更直观地体现出各主要因素与收益间
的关系，我们给出了下图：
欢迎下载
—
为了整改亏损航线，我们首先整理出了所有亏损航线，如下表：
表
2
：亏损
航线统计
全
不正
航材
航班
航线全称
号
机型
扣率
费
价
用
格
XX15
西安
-
天津
-
沈阳
71
XX15
沈阳
-
天津
-
西安
72
xx16
天津
-
临沂
-
福州
07
XX1
6
福州
-
临沂
-
天津
08
XX16
天津
-
阜阳
-
厦门
17
XX16
厦门
-
阜阳
-
天津
18
XX16
呼和浩特
-
西安
48
A320
0.4171
67
E190
0.4620
33
1415.
830
1
5
5
05
E190
0.5739
98
1480.
650
0
352.1
3
285.9
3
0.585
62
1710.
180
-1545.080
E190
0.5739
51
1543.
650
3
416.9
6
421.2
3
0.825
25
2386.
106
-38841.590
E190
0.4620
86
1385.
800
0
434.8
8
423.1
7
0.827
75
2489.
106
-33768.110
E190
0.4866
25
1354.
800
7
390.2
9
367.2
0
0.699
33
2233.
106
-22920.040
E190
52
1579.
800
6
381.5
4
367.0
7
0.631
10
2184.
106
-30110.340
0
0
444.7
1
375.7
1
0.884
04
2546.
106
-27788.190
0.4116
1374.
150
387.1
292
.3
0.841
2216.
106
-6909.379
平均折
维修
票
班费
品
率
修费
价
常航
机供
客座
机维
数
发动
座位
收益
欢迎下载
—
针对以上亏损的航线，基于我们选出的主要因素我们提出整改
措施如下：
西安
-
< br>天津
-
沈阳以及返航航线：从上表可以看出
,
西安
-
天津
-
沈阳以及返航
航线的收益分别是
< br>-6909.379
及
-27788.190
，均处于亏损状态。对于西安
-
天津
-
沈阳航线，
可以利用上表的数据分析出其亏损的主
要原因是平均折扣率太低，
对
于此，
我
们提出的整改措施是适当提高折扣率，
同时通过提供更好的服务或者更
< br>换机型以及其它的方式来吸引更多的顾客。
而对于返航航线与西安
-
天津
-
沈阳航
线最大的区别是全票价价格不同，
同时其平均折扣率也是非常低，
于是我们可以
认为以上两点是造成其航线亏损如此之多的关键所在。
这与我们利用相关性分析
出全票价价格也是影响收益的主要因素之一是
吻合的，
因此，
如果此航线想要减
少损
失或者说获得更多利润，
就需要适当的提高全价票价格。
同时，
通过提供更
好的服务或者更换机型以及其它的方式来吸引更多的
顾客，
进而适当提高折扣率
[2]
。<
/p>
天津
-
临沂<
/p>
-
福州以及返航航线：
天津
-
临沂
-
福州以及返航航线
的收益分别是
-30110.340
以及
-22920.040
，亏损相对来说比较严重，从表中我们可以清楚地
看到这两条航线的平均折扣率，
全价票价格以及客座率均偏低，
故早成航线亏损
严重，
这与我们的分析结果相吻合，
对于此我们给出的整改措施是改变航线机型
或
< br>
者航班时刻，提高航线服务质量，从而增高客座率。
天津
-
阜阳
-
厦门航线以及返航航线：
天津
-
阜阳
-
厦门航线以及返航航线的收益分
别是
-33768.110
以及
-38841.590
，亏损严重，通过分析我
们得出其原因是全价
票价格非常低，并且平均折扣率也偏低。整改措施：适当提高全价票
价格，同时
通
过调整航班时刻或改变航线机型促进平均折扣率的提升。
呼和浩特
-
西安航线：主要是由于折扣率较
低，造成轻微亏损。整改措施：
改变航线机型或者提供更好的服务或者采用其它方式增加
平均折扣率。
4.2
制定航班计划
4.2.1
模型的分析
问题
2
的目的是制定新的航班计划，以达到航空公司的收益最大的最终目
标。
由问题
2
的题设，航线、平均客座率、平均折扣率不变，所以如果我们假定
票价也不变
的话，
可知各航线的收入总和不变。
同时，
我们还假设附件
1
中各航
线的成本
也只跟航线本省有关，
即除了租飞机要租金外，
各航线的其他成
本也不
变。
于是，
求解公司收益最大化
的问题便转化为求解飞机利用率最大的问题。
因
此可以建立以所
需飞机数最少为目标的模型。
4.2.2
基本符号说明
N
:
所需最少的飞机架数
i
：第
i
条航线
j
：第
j
架飞机
欢迎下载
—
T
:
一架飞机每天可以飞行的最大时间
s
：一天中飞机最大飞行时间
t
i
：飞机飞行第
i
条航线所需时间
< br>1,
第
j
架飞机飞第
i
条航线
x
ij
0
，否则
4.2.3
模型建立与求解
对附件
1
的
航线进行分析可以发现，
所有航线可以分为西安、
天津两个独立
的基地。
再根据
A320
和
E190
两种机型，
我们
可以将各航线分成
4
个对立的系统
进行
求解。下面对于各个系统我们分别建立如下模型。
目标：最小
化所用飞机架数，即
N
。
约束：一架飞机每天飞行的总时间不能超过航线排班时间
则可得具体模型如下：
min
s
.
t
N
x
j
1
s
i
1
N
ij
1
T
i
1,...,
s
t
x
i
ij
j
1,...,
N
x
ij
< br>1
或
0
很显然以上模型是
0-1
整数规划模型，由
于
0-1
整数规划模型是
NP-
难题，
因此我们将原模型转化为较简单的
0-
1
整数背包问题求解
,
其转化的具体过
程如
下：
(1)
一架飞机每天可以飞行的最大
时间可以看成一个背包可装物品的总数
量。
(2)
一条航线需要的飞行时间可以看成一个物品的质量。
(3)
由题设每条航线每天飞且只飞
一次可以看成物品的价值都相等（都取为
1
）
< br>
原模型要求使用的飞机数最少，
即等价于每架飞机的利
用率越高，
也就对应
每个背包的利用率越高，其具体的执行步骤
为：
（
1
）
输入原参数集合
（航线的标号，
每条航线的
飞行时间，
每条航线的价
值）
；
（
2
）
运用动态规划算法求得一架飞机的排班计划；
（
3
）
从原参数中去除已经分配航线对应的参数；
（
4
）
判断参数集合是否为空集，
如果为空集，
输
出各飞机的分配结果，
过
程结束否则返回第
2
步继续执行。
具体程序流程图如下
:
欢迎下载
—
根据附
件
1
的数据，我们假设一架飞机每天的飞行时间最大为
17.5
个小时
[7:30,1:00]
，
利用附件
1
提供的
数据以及
MATLAB
软件对以上模型进行求解。
最
后得出在保证航线正常运行的前提下，
使得航空公
司收益最大的最少飞机架数
N
为
12<
/p>
，其中机型
A320
和机型
E190
各
6
架。具体结果
如下列各表：
首先给出符号说明：
n
：初始航线在附件
1
中对应的行标号；
s:
新的航线标号；
st
：新航线的飞行时间；
ZW:
每架飞机每天可以飞行的最长时间；
BH:
同一架飞机一天可以飞行的新的航线标号。
< br>
天津
A320
：
< br>表
3
：机型为
A320
的从天津出发的飞机的原始数据
n
s
st
15
16
19
20
31
32
39
40
41
42
47
48
49
50
51
52
1
5.7463
2
4.5563
3
4.2233
4
5.7373
5
4.3053
6
7
8
5.3933
10.4100
6.1063
将以上
数据输入到
MATLAB
，可得出以下结果：
< br>
表
4
：一架从天津出发的
A320
飞机一天飞行的时间与对应的航线之间的关系
BH
ZW
1
2
14.5260
3
4
5
15.4360
6
7
8
15.5163
欢迎下载
—
天津
E190
：
表
5
：机型为
E190
的从天津出发的飞机的原始数据
n
s
st
9
1
10
21
2
22
23
3
24
25
4
26
27
5
28
29
6
30
53
7
54
9.6880
67.246
9.0310
8.1250
7.5760
7.8940
8.7233
将以上数据输入到
MATLAB
，可得出以下结果：
< br>表
6
：一架从天津出发的
A19
0
飞机一天飞行的时间与对应的航线之间的关系
BH
ZW
西安
A320
：
1
2
3
16.6070
5
4
16.0190
6
7
8.7233
16.29340
表
7
：机型为
A320
< br>的从西安出发的飞机的原始数据
n
s
st
5
6
1
11
12
17
18
33
34
35
36
37
38
43
44
45
46
2
4.3320
3
7.4170
4
3.3193
5
3.2033
6
4.5333
7
4.3433
8
6.5770
8.2460
将以上
数据输入到
MATLAB
，可得出以下结果：
< br>
表
8
：一架从西安出发的
A320
飞机一天飞行的时间与对应的航线之间的关系
BH
ZW
西安
E190
：
1
2
15.8973
4
3
5
15.1536
6
7
8
13.1343
表
9
：机型为
E190
的从西
安出发的飞机的原始数据
n
S
St
3
1
801059
4
7
2
8
7.8820
13
3
7.7340
14
将以上数据输入到
MATLAB
，可得出以下结果
：
表
10
：
一架西安出发的
E190
飞机一天飞行的时间与对应的航线之间
的关系
BH
ZW
1
15.39870
2
3
7.7340
由表
3
到表
10<
/p>
可知，
该航空公司至少需要
12
架飞机才能保证各条航线正常
运转，即上述优化模型的最优解
N=12
，也就是说该公司还需要向租赁公司租借
4
架
A320
型飞机及
2
架
E190
型飞机。
进一步，
我们对各架飞机进行具体的
航班时刻安排。
我们在排航班时刻表的
欢迎下载