前后两航班的衔接时间间隔不小于40分钟。关于如何由航班时刻表生成航班环，请参见第八章。
表2-1 某小航空公司的航班时刻表 航班号 110 120 130 121 112 122 123 出发时刻 8:00 12:30 15:00 10:00 17:00 15:00 11:00 出发机场 A C D B A C B 到达时刻 9:00 14:00 16:00 11:00 18:20 16:30 12:15 到达机场 B D A C B A C 频率 1,2,3,4,5 1,2,3,4,5,6 1,2,3,4,5,7 1,2,3,4,5,6,7 1,2,3,4,5,6,7 1,2,3,4,5,6,7 1,2,3,4,5 在表2-2中P1-P4这四个航班环的周期是一天，P5-P12这八个航班环的周期是两天，P13的周期则是三天，没有周期超过三天的航班环。对于周期是两天的航班环，每天应执行两个（两架飞机来飞），三天周期的航班环每天需执行三个，需要三架飞机来飞。
表2-2 可选择的航班环 航班环 P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 P13 第一天 110-121-120-130 110-123-120-130 110-121-122 110-123-122 112 112 120-130-112 122-112 120-130-112 122-112 130 130 130 第二天 重复 重复 重复 重复 121-120-130 121-122 121 123 123 121 110-123-120 110-121-120 112 第三天 重复 重复 重复 重复 重复第一天 重复第一天 重复第一天 重复第一天 重复第一天 重复第一天 重复第一天 重复第一天 121-120 飞行小时 4.5 4.25 3.5 3.75 4.83 3.83 4.83 4.08 5.08 3.83 4.75 4.5 4.33 基地机场 A A A A A A C C C C D D D 设决策变量xi?0,1，等于0表示不飞航班环Pi，等于1表示飞航班环Pi。如果根据航班环Pi的飞行小时计算出机组成本是ci，则表2-1的航班计划的机组执行总成本是
z??cixi
i?113我们希望这个总成本越小越好。
对于每个航班，每天必须有一个航班环执行，而且只能有一个航班环执行。例如对于航班110，航班环P1、P2、P3、P4、P11、P12都包含它，这些航班环只能执行一个，不能同
时都执行，否则航班110将被执行多次。因此
x1?x2?x3?x4?x11?x12?1
对于其他航班，也有类似的约束条件，对于本问题一共有7个同类的约束条件。综合上述讨论，我们可以给出该机组航班环问题的规划模型如下：
minz??cixii?113s.t.x1?x2?x3?x4?x11?x12?1x1?x3?x5?x6?x7?x10?x12?x13?1x1?x2?x5?x7?x9?x11?x12?x13?1x3?x4?x6?x8?x10?1x1?x2?x5?x7?x9?x11?x12?x13?1x5?x6?x7?x8?x9?x10?x13?1x2?x4?x8?x9?x11?1xi?0,1;i?1,2,?,13这是一个0-1型整数规划模型，目标函数是机组飞行总成本最小，每个航班一个约束条件，表示每个航班能且只能执行一次。这是一个集合分割问题，即将航班集合分割成若干子集合，任意航班属于某一子集合，每两两子集合的交集为空，使分割的总代价最小。这里每个航班子集就是一个航班环。有时由于航班计划在时间上的安排协调不够，导致某些航班在当地机场没有机组去执行，这时上述模型无可行解。实践中，常采用加机组（又叫空飞，Deadhead）的办法，即从别的机场调机组跟随某航班飞来本机场。如果允许机组空飞（加机组）,则约束条件的等号应改为大于等于号，此时是集合覆盖问题。
集合分割问题和集合覆盖问题是航空运输规划经常遇见的数学模型，它们的一般描述是：
集合分割问题：把一个含有n个元素的集合A分割成若干个子集合Ai，i=1,2,?,m，产生每个子集合Ai需要付出相应的成本ci，现要求从这些子集合中选出若干个子集合，使得Ai?Aj??,i?j,i,j?1,2,?,m;m
?Ai?1mi?A，并使分割这些子集合的总成本最小。
集合分割问题可以用数学模型表述如下：
minz??cixii?1s.t.?aj?1mijxj?1,i?1,2,?,n
(2-1)
xi?0,1;i?1,2,?,m其中aij=0或1，是一个示性算子，即当子集合Aj 含有元素i时为1，否则为0。xi是决策变量，等于1时表示Ai 被选中，等于0时表示不选择Ai。上述模型的约束条件共有n个，每个元素一个，表示每个元素必须且只能包含在一个子集合中。
集合覆盖问题：如果在集合分割问题中，允许多个子集合包含同一个元素，即允许
Ai?Aj??,i?j，则叫做集合覆盖问题，它的数学模型是
minz??cixii?1ms.t.?aj?1mijxj?1,i?1,2,?,n
xi?0,1;i?1,2,?,m 上述的集合分割问题和集合覆盖问题的决策变量是特殊的整数，因此它们是特殊的整数规划。一般的整数规划问题可以这样定义：
定义2-1 凡规定某些决策变量取整数值的数学规划问题都叫做整数规划问题。 例如
minz?f(X1,X2)s.t.g(X1,X2)?bX1,X2?0,X1取整数其中f,g是X1,X2的任意函数，X1,X2是决策变量矢量，b是约束条件的右手边矢量。
2-2-2 整数规划的分类和可行解集
定义2-1告诉我们，只要某数学规划问题的某些决策变量规定为整数，就是整数规划。这就告诉我们，整数规划中可以规定变量取0或1，也可以规定取其它整数值。有些整数规划甚至允许某些决策变量取实数值，某些取整数值。而且目标函数和约束条件的左边可以是线性的，也可以是非线性的。本小节首先对整数规划进行分类。 一、根据决策变量的取值规定进行分类
1、0-1型整数规划：有决策变量取0或1的整数规划。如果全部决策变量都只取0或1，则称为纯0-1型整数规划，否则称为混合0-1型整数规划。
2、纯整数规划：所有的决策变量都取整数的整数规划问题叫做纯整数规划问题。 3、混合整数规划：有些变量取整数，有些变量取实数的规划问题，叫做混合整数规划。
二、根据目标函数、约束条件左边是否为线性进行分类
1、线性整数规划：目标函数和约束条件左边全都是决策变量的线性函数的整数规划叫做线性整数规划。
2、非线性整数规划：目标函数或者某些约束条件左边是决策变量的非线性函数的整数规划。
整数规划各种类型和划分标准可见表2-3所示。
表2-3 整数规划分类
类型 线性整数规划 非线性整数规划 条件 变量 目标函数和约束条件 整数规划 0-1型整数规划 整数规划 0-1型整数规划 纯整数规混合整数纯整数规混合整数纯整数规混合整数纯整数规混合整数划 规划 划 规划 划 规划 划 规划 全部取整部分取整全部取整部分取整全部取整部分取整全部取整部分取整数 数 数 数 数 数 数 数 全部为线性函数 部分为非线性函数 本章只讨论线性整数规划问题。线性整数规划由于规定某些变量取整数值，大大地加大了求解难度。如果放松整数约束，则线性整数规划问题成为线性规划问题，叫做整数规划的松弛线性规划问题，简称为松弛线性规划问题。如果是0-1型的整数规划，整数约束xi?0,1将松弛成0?xi?1。
设松弛线性规划问题的可行域是S，则对应的整数规划的可行域是S中整数点的集合。
例如如下的整数规划
maxz?7x1?5x2s.t.24x1?11x2?88
2x1
?3x2?10x1,x2?0,整数
对应的松弛线性规划问题为
（2-2）
maxz?7x1?5x2s.t.24x1?11x2?882x1?3x2?10x1,x2?0线性规划（2-3）的可行域S是图2-1中的阴影部分构成的凸集，而整数规划的可行域是该
凸集中的整数点：{(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2), (3,0),(3,1)}。求整数规划的最优解即是在该可行域的整数点集中寻找使目标函数最优的点。点（3,1）即是（2-2）的最优解。
（2-3）
8765432100x2x112345 图2-1 线性规划和整数规划的可行域
2-3 高级网络流问题
我们在运筹学课程中已经知道一些经典的网络优化问题，例如最小支撑树问题、最短路问题、最大流问题和最小费用流问题。对于这些问题，已经有了有效的多项式算法。但这些经典网络优化模型只能解决一些比较简单的问题。例如最短路问题只考虑边的长度，没有考虑路径上其它因素的约束，如规定燃油的消耗量或规定允许的最长流动时间；最小费用流问题假设网络上流动的是同一种“商品”，而实际情况可能存在多种“商品”，而且假设单位流的费用相同，不考虑网络的建设投资等。因此实际问题比经典的网络流问题要复杂得多。本节主要讨论在航空运输规划中经常遇到的网络优化高级问题：约束最短路问题和多商品流问题。
2-3-1 约束最短路问题
图2-2是大家熟悉的最短路问题，其中节点v1和v8分别是始发节点（源节点）和终止节点（汇节点），图中每边上权重表示长度，要求从始发节点到终止节点的这样一条路径，该路径上各边的权重之和最小（路径长度最短）。在图2-2中，节点v1到v8 的最短路径是v1 v7 v5 v6 v8，最短路程是9。
v23624v324v11v52v623v4410v7v8