航空运输规划学（第二章航空运输规划基础）

第二章航空运输规划基础

——网络流与整数规划网络流问题网络：点和连接这些点的集合。相关术语：结点弧流量路径网络流模型最短路径问题最小费用流问题最大流问题多商品流问题无约束最短路问题节点v1和v8分别是始发节点（源节点）和终止节点（汇节点），图中每边上权重表示长度，要求从始发节点到终止节点的这样一条路径，该路径上各边的权重之和最小（路径长度最短）。在图中，节点v1到v8的最短路径是v1

v7

v5

v6

v8，最短路程是9。

最短路问题的数学模型

其中，是边(i,j)的长度，是0-1型的决策变量（路径选择变量），边(i,j)在最短路径上时=1，否则=0。该问题是一个易解问题，经典的标号法是多项式算法。最小费用流问题最小费用流问题：给定了网络的流量d，以及边(i,j)的容量uij和单位流费用cij，要求网络流d在网络上的最小费用的分布模式最小费用流问题的数学模型

多商品流问题假设在网络上流动着K种商品，令k=1,2,...,K表示任意第k种商品，在任意边(i,j)上，商品流存在容量限制，各种商品的单位流都占有一个单位的容量，因此各种商品流之和不能超过该边的容量。第k种商品的网络流（总需求）为，在边(i,j)上的单位流费用是，并进一步假设受到该种商品流容量的限制。多商品流问题的数学模型

整数规划问题实例介绍某小型航空公司一周的航班计划如表2-1所示，机组基地机场是A、C和D，现在要为该航空公司的机组人员排班。对于周一到周五每天都飞的航班，叫做每天重复的航班(DailyFlight)。为这样的航班计划进行机组人员排班时，首先生成可供选择的航班环，其结果如表2-2所示。本例中我们要求在同一个航班环中，前后两航班的衔接时间间隔不小于规定的最小值，例如40分钟。

表2-1航班时刻表航班号出发时刻出发机场到达时刻到达机场频率1108:00A9:00B1,2,3,4,512012:30C14:00D1,2,3,4,5,613015:00D16:00A1,2,3,4,5,712110:00B11:00C1,2,3,4,5,6,711217:00A18:20B1,2,3,4,5,6,712215:00C16:30A1,2,3,4,5,6,712311:00B12:15C1,2,3,4,5表2-2航班环航班环第一天第二天第三天飞行小时基地机场P1110-121-120-130重复重复4.5AP2110-123-120-130重复重复4.25AP3110-121-122重复重复3.5AP4110-123-122重复重复3.75AP5112121-120-130重复第一天4.83AP6112121-122重复第一天3.83AP7120-130-112121重复第一天4.83CP8122-112123重复第一天4.08CP9120-130-112123重复第一天5.08CP10122-112121重复第一天3.83CP11130110-123-120重复第一天4.75DP12130110-121-120重复第一天4.5D1204.33D数学模型集合分割问题把一个含有n个元素的集合A分割成若干个子集合Ai，i=1,2,…,m，产生每个子集合Ai需要付出相应的成本ci，现要求从这些子集合中选出若干个子集合，使，并使分割这些子集合的总成本最小。集合覆盖问题如果在集合分割问题中，允许多个子集合包含同一个元素，即允许，则叫做集合覆盖问题，它的数学模型是一般整数规划描述凡规定某些决策变量取整数值的数学规划问题都叫做整数规划问题。其中f,g是的任意函数，X1,X2是决策变量矢量，b是约束条件的右手边矢量。整数规划的分类和可行解集整数规划分类

类型条件线性整数规划非线性整数规划整数规划0-1型整数规划整数规划0-1型整数规划纯整数规划混合整数规划纯整数规划混合整数规划纯整数规划混合整数规划纯整数规划混合整数规划变量全部取整数部分取整数全部取整数部分取整数全部取整数部分取整数