| 航空器供油问题中完全逆序类中的多项式时间可解类 |
| |
| 引用本文： | 王丽丽,崔晋川.航空器供油问题中完全逆序类中的多项式时间可解类[J].运筹与管理,2019,28(1):1-5. |
| |
| 作者姓名： | 王丽丽 崔晋川 |
| |
| 作者单位： | 中国科学院 数学与系统科学研究院,北京 100190 |
| |
| 摘 要： | 航空器供油问题是一类非线性组合优化问题,其目标函数为分式形式,该问题目前不存在多项式时间算法,也未被证明是NP完全问题。一般可以用置换来刻画n架飞机的一个供油顺序。该问题中有一类实例被称为“完全逆序类”,“完全逆序类”用动态规划算法求解计算时间为O(n2n),具有指数时间复杂度。本文通过对该“完全逆序类”问题做进一步分析,发现在“完全逆序类”中也存在着多项式时间可解的情况。定理1研究一类一次可解的情况,若问题满足定理1的条件,则求解一次即可找到其最优解;定理2研究一类多项式时间可解的情况,当问题满足定理2的条件时,其最优解可在多项式时间内获得。
|
| 关 键 词： | 航空器供油问题 最优解必要条件 唯一解类 排序 |
| 收稿时间： | 2017-02-26 |
A class of Completely Reverse Order which can be Solved in Polynomial Time in Airplane Refueling Problem |
| |
| WANG Li-li,CUI Jin-chuan.A class of Completely Reverse Order which can be Solved in Polynomial Time in Airplane Refueling Problem[J].Operations Research and Management Science,2019,28(1):1-5. |
| |
| Authors: | WANG Li-li CUI Jin-chuan |
| |
| Affiliation: | Academy of mathematics and systems science, Chinese academy of sciences, Beijing 100190, China |
| |
| Abstract: | The Airplane Refueling Problem(ARP)is a nonlinear combinatorial optimization problem with a fractional objective function and its complexity is still open. We use a permutation to model the precedence relations between pairwise jobs. One kind of this problem is called “Completely Reverse Order Class”. The Completely Reverse Order Class of the N-Vehicle Explore Problem(NVEP)is considered is considered one of the most difficult scenarios that consume exponential time in Dynamic Programming algorithm. In this paper, we analyze data structure of this problem and find two kinds of special structure in the “Completely Reverse Order Class”. Theorem 1 describes a kind of special structure, and states that there is a unique solution that satisfies the necessary condition of this kind of special structure, and it is optimal as well. Theorem 2 describes a kind of structure which can be solved in polynomial time. When relationship between fuel loading and fuel consumption rate satisfies the conditions of theorem 2, the corresponding instance can be solved in polynomial time. |
| |
| Keywords: | airplane refueling problem necessary condition of optimal solution unique solution scheduling problem |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹与管理》浏览原始摘要信息 |
|
点击此处可从《运筹与管理》下载全文 |
|
