航空器供油問題中完全逆序類中的多項式時間可解類

王麗麗， 崔晉川

(中國科學(xué)院 數(shù)學(xué)與系統(tǒng)科學(xué)研究院，北京 100190)

0 引言

1 航空器供油問題的性質(zhì)

1.1 數(shù)學(xué)模型[2]

設(shè)有n架飛機(jī){V1,V2,…,Vn}，飛機(jī)Vi(i=1,2,…,n)載油量為ai(L)，耗油率為bi(L/Km)，按照退出飛行的順序σ，第i架退出飛行的飛機(jī)已經(jīng)飛行的距離表示為

航空器供油問題的示意圖如圖1所示，O為出發(fā)點，Aπ(i)為飛機(jī)Vπ(i)行駛的最遠(yuǎn)點(i=1,2,…,n)，同時Aπ(1)是n架飛機(jī)在該排序下行駛的最遠(yuǎn)點。其中xπ(i)表示Vπ(i)比Vπ(j+1)多行駛的距離(i=1,2,…,n-1)，xπ(n)表示Vπ(n)行駛的距離。

圖1 架飛機(jī)的飛行順序及飛行距離示意圖

Vásquez等[5]把該問題看做一類形如minΣωjf(Cj)的特殊的工件排序問題，因為

1.2 航空器供油問題最優(yōu)解的必要條件

梁莉莉用鄰位對換的方法得出了航空器供油問題的最優(yōu)解的必要條件[12]，描述如下：

下文提到的最優(yōu)排序均指飛機(jī)飛行距離由遠(yuǎn)及近的排序。

1.3 航空器供油問題最優(yōu)解的必要條件

2 航空器供油問題的唯一解類

定理1給定屬于“完全逆序類”的n架飛機(jī){V1,V2,…,Vn}，其中Vi的載油量為ai(L)，耗油率為bi(L/km)，若滿足條件:

則該航空器供油問題滿足引理1的解只有一個，最優(yōu)排序為π=(1,2,…,n)。

下證除排序π=(1,2,…,n)以外，其他排序都不滿足引理1。

設(shè)排序θ=(θ(1),θ(2),…,θ(n))為不同于π=(1,2,…,n)的任意排序，下證相鄰兩架飛機(jī)不滿足引理1。

由題意，排序θ中必存在i,i∈(1,2,…,n)，使得θ(i)>θ(i+1)，下證該相鄰兩架飛機(jī)不滿足引理1。

考慮函數(shù)

根據(jù)條件

故有g(shù)θ(i),θ(i+1)(B)<0，即排序θ不滿足必要條件。

綜上所述，滿足必要條件的排序只有一種，即為π=(1,2,…,n)。

證明設(shè)最優(yōu)排序為π=(π(1),π(2),…,π(n))。

下面證明當(dāng)π(1)選定以后，其余n-1架飛機(jī)的排序是唯一確定的。

令π(1)=k,(k∈N,k≠n)，則π=(k,n,n-1,…,k+1,k-1,…,1)。

下證該排序滿足引理1。

當(dāng)i≥2時，構(gòu)造函數(shù)

化簡得

下證gπ(i),π(i+1)(t)>0,(i=2,3,…,n-1)成立。

即排序π=(k,n,n-1,…,k+1,k-1,…,1)滿足引理1。

設(shè)最優(yōu)排序表示為π=(bk,A)，k∈N,k≠n,A為排序子序列。

下證除A=(n,n-1,…,k+1,k-1,…,1)外，其他排序都不滿足引理1。

假設(shè)排序θ=(θ(1),θ(2),…,θ(n))為任意不同于A的排序，下證該排序不滿足引理1。

由題意，排序θ中必存在m,m∈{1,2,…,n-2}，使得θ(m)<θ(m+1)>，下證該相鄰兩架飛機(jī)不滿足引理1。

考慮函數(shù)

綜上所述，該類問題的最優(yōu)解，采用枚舉法有n-1種情況。

故該類航空器供油問題可在多項式時間內(nèi)求得最優(yōu)解。

3 實例分析

例1假定機(jī)隊共有10架飛機(jī)，每架飛機(jī)所攜帶的燃油量ai(L)與耗油量bi(L/km)如下表。求該機(jī)隊的最遠(yuǎn)行駛距離。

解在該實例中，a/b遞增排列，a/b2遞減排列，屬于“完全逆序類”，由于該實例滿足本文定理的條件：

有512.3<740，所以最優(yōu)排序為

1?2?3?4?5?6?7?8?9?10

4 結(jié)論

文中主要研究了航空器供油問題的“完全逆序類”，“完全逆序類”具有指數(shù)時間復(fù)雜度。對大部分的難問題，人們通常用最壞情況的計算復(fù)雜度來刻畫其難度，“完全逆序類”是航空器供油問題中最難解的一類，當(dāng)規(guī)模較大時，計算時間較長，人們往往放棄利用精確算法尋找精確解，轉(zhuǎn)而利用啟發(fā)式算法或近似算法，但是按照本文定理的結(jié)論，“完全逆序類”中也存在實例可以在非常短的時間內(nèi)求得精確解。本文通過對其數(shù)據(jù)特征的分析，發(fā)現(xiàn)其中也存在著多項式時間可解的特殊結(jié)構(gòu)。定理1描述一類特殊的航空器供油問題，該類問題在求解前即可判定其滿足最優(yōu)解必要條件的排序是唯一的。定理2所描述的一類特殊結(jié)構(gòu)也可在多項式時間內(nèi)求得最優(yōu)解。