非线性的整数规划问题

    （1)每一个航班必须指派且仅能指派一个停机位即式中，W表示指派周期开始时已在位航班的集合，同时也表示在位航班停靠的停 机位的集合，对于航班iEM可以将W分成两个子集，一个是航班i进港时仍然在 位的航班集合：W1(2)={k|D>A，kEW)，D，和A，分别是航班k的出发和航班 i的到达时刻；另一个是航班i进港时已出发的子集W2。并且使用0-1型参数yw 表示使用机位的信息，在指派周期开始时，当航班kEW停靠机位p时等于1，否 则等于0。要记住，。是已知参数。约束条件（2-91）表示当航班i进港时，仍然被 占用的停机位p不能分配给航班i，如果W为空，则约束条件(2-91）也将为空。约 束条件(2-92）表示在指派周期开始时已经空闲的机位最多可指派给一个航班。 

    （2）停机位类型与机型的匹配约束 式中，P。和L，分别表示停机位p的类型和航班i的机型，该约束表示机位类型可 向下兼容，这一点与2.7.1节和2.7.2节相同。如果在航班波运作，给航班波指派 的机位不受机型限制，可以略去这一约束条件。 上述停机位指派问题是二次指派问题，是非线性的。为降低非线性带来的求 解困难，可以将目标函数转化为线性的。为此引人新的决策变量yg=xpxm，目 标函数（2-89）变为 引人新变量后，目标函数（2-94)已转化为线性的，为保证新的线性整数规划 与原非线性整数规划等价，应满足以下条件： 此时需要增加以下等价约束条件： 上述停机位指派问题可以直接用ILOG/CPLEX求解，但求解时间较长，对于 稍大规模的问题（如一个航班波的航班数超过10个)，它几乎不能完成求解任务。 

     此时需要设计宏启发式算法，如模拟退火法、遗传算法等。下面介绍一个应用模拟 退火法求解上述问题的实例。 解陈欣(207）详细研究了这个问题的求解。将表2-20与表2-21的对应数 据相乘然后代人目标函数（2-89）或（2-94)，即构成本问题的目标函数，W是空集目 停机位无机型限制，因此不需要约束条件(2-91）和(2-93)，式(2-90）和式（2-92）是 最基本的约束条件，很容易构成。为节省篇幅，这里不再给出该停机位指派问题数 学模型的细节。 如果采用目标函数(2-89），应用ILOG/CPLEX在一般台式计算机上求解本 问题，超过10h也不能给出结果，将问题规模缩小到8个航班，应用非线性模型和 线性模型，在同一台计算机上分别花费了2h和22min才解出结果，线性模型的求解速度显然快了不少。但增加一个航班，即9个航班时，线性模型的求解时间也增 加到6h，其计算复杂度是指数型的，而非线性模型则计算了10h仍然没有结果。 

      如果采用启发式算法，如模拟退火法，在同一台计算机上求解该问题（10个航 班）则只需0.3s即可给出结果，收敛速度很快。为了了解模拟退火法求解结果的精度，这里对一个航班波中有8个航班、9个航班和10个航班的三种情况应用模 拟退火法进行求解，发现在前两种情况下，模拟退火法给出了与ILOG/CPLEX求 解线性模型相同的结果，第三种情况下模拟退火法很快给出结果，但ILOG/ CPLEX则未能给出结果。表2-22给出了三种情况下模拟退火法求解得到的停机位最佳指派结果，表中F表示第i个航班。计算中，限制8个航班和9个航班的航班波只分别使用1~8号和1~9号停机位。

     进一步研究发现，即使一个航班波到达25个航班，使用模拟退火法求解航班波停机位指派问题，计算时间也只有123s，可见模拟退火法求解这类问题具有很 高的效率，达到了实用化的程度。 这个实例分析表明，非线性的整数规划问题，目前没有好的精确解法，采用启发式算法，是可行且适用的。