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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第二章 航空运输规划基础,网络流与整数规划,网络流问题,网络：点和连接这些点的集合。,相关术语：,结点,弧,流量,路径,网络流模型,最短路径问题,最小费用流问题,最大流问题,多商品流问题,无约束最短路问题,节点,v,1,和,v,8,分别是始发节点（源节点）和终止节点（汇节点），图中每边上权重表示长度，要求从始发节点到终止节点的这样一条路径，该路径上各边的权重之和最小（路径长度最短）。在图中，节点,v,1,到,v,8,的最短路径是,v,1,v,7,v,5,v,6,v,8,，最短路程是,9,。,最短路问题的数学模型,其中， 是边,(,i,j,),的长度， 是,0-1,型的决策变量（路径选择变量），边,(,i,j,),在最短路径上时,=1,，否则,=0,。该问题是一个易解问题，经典的标号法是多项式算法。,最小费用流问题,最小费用流问题：给定了网络的流量,d,，以及边,(,i,j,),的容量,u,ij,和单位流费用,c,ij,，要求网络流,d,在网络上的最小费用的分布模式,最小费用流问题的数学模型,多商品流问题,假设在网络上流动着,K,种商品，令,k,=1,2,.,K,表示任意第,k,种商品，在任意边,(,i,j,),上，商品流存在容量限制，各种商品的单位流都占有一个单位的容量，因此各种商品流之和不能超过该边的容量。第,k,种商品的网络流（总需求）为 ，在边,(,i,j,),上的单位流费用是 ，并进一步假设受到该种商品流容量 的限制。,多商品流问题的数学模型,整数规划问题,实例介绍,某小型航空公司一周的航班计划如表,2-1,所示，机组基地机场是,A,、,C,和,D,，现在要为该航空公司的机组人员排班。对于周一到周五每天都飞的航班，叫做每天重复的航班,(Daily Flight),。为这样的航班计划进行机组人员排班时，首先生成可供选择的航班环，其结果如表,2-2,所示。本例中我们要求在同一个航班环中，前后两航班的衔接时间间隔不小于规定的最小值，例如,40,分钟。,表,2-1,航班时刻表,航班号,出发时刻,出发机场,到达时刻,到达机场,频率,110,8:00,A,9:00,B,1,2,3,4,5,120,12:30,C,14:00,D,1,2,3,4,5,6,130,15:00,D,16:00,A,1,2,3,4,5,7,121,10:00,B,11:00,C,1,2,3,4,5,6,7,112,17:00,A,18:20,B,1,2,3,4,5,6,7,122,15:00,C,16:30,A,1,2,3,4,5,6,7,123,11:00,B,12:15,C,1,2,3,4,5,表,2-2,航班环,航班环,第一天,第二天,第三天,飞行小时,基地机场,P1,110-121-120-130,重复,重复,4.5,A,P2,110-123-120-130,重复,重复,4.25,A,P3,110-121-122,重复,重复,3.5,A,P4,110-123-122,重复,重复,3.75,A,P5,112,121-120-130,重复第一天,4.83,A,P6,112,121-122,重复第一天,3.83,A,P7,120-130-112,121,重复第一天,4.83,C,P8,122-112,123,重复第一天,4.08,C,P9,120-130-112,123,重复第一天,5.08,C,P10,122-112,121,重复第一天,3.83,C,P11,130,110-123-120,重复第一天,4.75,D,P12,130,110-121-120,重复第一天,4.5,D,P13,130,112,121-120,4.33,D,数学模型,集合分割问题,把一个含有,n,个元素的集合,A,分割成若干个子集合,A,i,，,i,=,1,2,m,，产生每个子集合,A,i,需要付出相应的成本,c,i,，现要求从这些子集合中选出若干个子集合，使 ，并使分割这些子集合的总成本最小。,集合覆盖问题,如果在集合分割问题中，允许多个子集合包含同一个元素，即允许 ，则叫做集合覆盖问题，它的数学模型是,一般整数规划描述,凡规定某些决策变量取整数值的数学规划问题都叫做整数规划问题。,其中,f,g,是的任意函数，,X,1,X,2,是决策变量矢量，,b,是约束条件的右手边矢量。,整数规划的分类和可行解集,整数规划分类,类型,条件,线性整数规划,非线性整数规划,整数规划,0-1,型整数规划,整数规划,0-1,型整数规划,纯整数规划,混合整数规划,纯整数规划,混合整数规划,纯整数规划,混合整数规划,纯整数规划,混合整数规划,变量,全部取整数,部分取整数,全部取整数,部分取整数,全部取整数,部分取整数,全部取整数,部分取整数,目标函数和约束条件,全部为线性函数,部分为非线性函数,整数可行解与可行解集,例子,松弛问题,整数可行解与可行解集,松弛问题可行域中整数点，这些点的包络叫做它的可行解集的凸包，最优解是凸包的顶点。,