非线性的整数规划问题

2019-09-03 2434

    (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,可见模拟退火法求解这类问题具有很 高的效率,达到了实用化的程度。 这个实例分析表明,非线性的整数规划问题,目前没有好的精确解法,采用启发式算法,是可行且适用的。


电话咨询
咨询留言
在 线 客 服 X

QQ咨询

微信二维码

客户服务热线

18824138009