飛行管理

??????????? ?????????????????

?

一．?? 問題描述

§1．引?? 言

?

在約10000米高空的一個(gè)邊長(zhǎng)160千米的正方形區(qū)域內(nèi)，經(jīng)常有若干架飛機(jī)作水平飛行．為對(duì)其進(jìn)行飛行管理，現(xiàn)采用計(jì)算機(jī)記錄每架飛機(jī)的位置和當(dāng)前飛行角度，當(dāng)一架飛機(jī)欲進(jìn)入時(shí)，記錄其數(shù)據(jù)并判斷是否與區(qū)域內(nèi)的飛機(jī)發(fā)生碰撞，若碰撞，即調(diào)整其方向角，且使方向角調(diào)整的幅度盡量?。疄榧俣l件如下：

⒈ 不碰撞的標(biāo)準(zhǔn)為任意了兩架飛機(jī)的距離不小于８千米；

⒉ 飛機(jī)飛行方向角調(diào)整的幅度均不超過30度；

⒊ 所有飛機(jī)調(diào)整前后均作勻速直線運(yùn)動(dòng)，飛行速度為每小時(shí)800千米；

⒋ 進(jìn)入該區(qū)域的飛機(jī)在到達(dá)區(qū)域邊緣時(shí)，與區(qū)域內(nèi)的飛機(jī)的距離應(yīng)在60千米以上；

⒌ 不必考慮飛機(jī)離開此區(qū)域后的狀況；

⒍ 最多需考慮6架飛機(jī)；

⒎ 對(duì)所有飛機(jī)的調(diào)整為一次完成，調(diào)整后不再發(fā)生碰撞.

請(qǐng)你對(duì)這個(gè)避免碰撞的飛行管理問題建立數(shù)學(xué)模型，列出計(jì)算步驟，對(duì)以下數(shù)據(jù)舉行計(jì)算（方向角誤差不超過0.01o）,要求飛機(jī)飛行方向角調(diào)整幅度盡量小。

表1給出了區(qū)域內(nèi)現(xiàn)有的5架飛機(jī)與新進(jìn)入的第6架飛機(jī)的坐標(biāo)（x,y）和方向角α（飛行方向ｘ軸的正向夾角）．

?

表１　限定區(qū)域內(nèi)的飛機(jī)的坐標(biāo)和方向角

坐標(biāo)

架次

x

y

　　　　

1

150

140

243

?

2

85

85

236

3

150

155

220.5

4

145

50

159

5

130

150

230

6

0

0

52

?

?

二．?? 變量描述及名詞解釋

：第i架飛機(jī)的初始飛行方向角；

：第i架飛機(jī)飛行方向角調(diào)整幅度；

：第i架飛機(jī)的飛行速率；

：第i架飛機(jī)的初始坐標(biāo)；

：t時(shí)刻第i架飛機(jī)的坐標(biāo)；

：t時(shí)刻第i架飛機(jī)與第j架飛機(jī)的距離；

：第i架飛機(jī)與第j架飛機(jī)相距最近的時(shí)刻，即；

S：新進(jìn)入的飛機(jī)對(duì)原飛行系統(tǒng)的擾動(dòng)因子；

（其中，i =1，2，…，6 ；j=1，2，…，6。）? ?

???

三．?? 模型建立

我們將本題的目標(biāo)函數(shù)設(shè)定為飛機(jī)飛行方向角調(diào)整幅度的加權(quán)平方和。

建立目標(biāo)函數(shù)：

??????????? （1）

約束條件為：

飛行控制區(qū)內(nèi)，的最小值大于8km，即：

（km）?????? （2）

其中，

?；

? (i =1,2,…,5；j=i+1,…,6)

?? ；? (i =1,2,…,6)

?? ；? (i =1,2,…,6)

；(i =1,2,…,6)

若要嚴(yán)格表示兩架位于該區(qū)域內(nèi)的飛機(jī)的距離大于8km，則需考慮每架飛機(jī)在該區(qū)域內(nèi)的飛行時(shí)間長(zhǎng)度，記為第i架飛機(jī)飛出區(qū)域的時(shí)刻，即：

??? （3）

又設(shè)，則不相碰撞的條件就可表為：

約束條件（2）的具體實(shí)施為：

?????????? （4）

其中，

此外，經(jīng)計(jì)算可得：

為關(guān)于的一個(gè)二次函數(shù)。

?（5）

易知，當(dāng)時(shí)，即時(shí)函數(shù)達(dá)最小，取最小值為。注意到（初始時(shí)刻不碰撞），若，則約束條件（4）必成立。故對(duì)（4），只需考慮兩種情形：

（1） ，則只需要在右端點(diǎn)的函數(shù)值非負(fù)即可，既

?????????????? （6）

（2） ，則只需要的最小值非負(fù)即可，既

???????????????????? （7）

實(shí)際上，（6）在（7）的條件下也是該成立的，故得優(yōu)化模型：

?min???

s.t.???

???????

?????? , 當(dāng)時(shí)

?(i =1,2,…,5；j=i+1,…,6)? 各參數(shù)由（5）定義。

四．?? 模型求解

上面規(guī)劃問題是非常復(fù)雜的，因有許多復(fù)雜的邏輯關(guān)系，故需簡(jiǎn)化模型。

考慮的簡(jiǎn)化：

注意到（對(duì)角線時(shí)），從而強(qiáng)化了約束，即有些飛機(jī)已經(jīng)飛出了該區(qū)域，但我們?nèi)圆辉试S他們相碰撞。

故得簡(jiǎn)化模型的lingo程序

?

MODEL:

TITLE 飛行管理問題的非線性規(guī)劃模型;

SETS:

Plane/1..6/: x0, y0, cita0, cita1, d_cita;

! cita0表示初始角度，cita1為調(diào)整后的角度,d_cita為調(diào)整的角度;

link(plane, plane)|&1 #LT# &2: b,c;

ENDSETS

DATA:

x0 y0 cita0 =

150

140

243

85

85

236

150

155

220.5

145

50

159

130

150

230

0

0

52

;

max_cita = 30;

T_max = 0.283;

V=800;

ENDDATA

INIT:

d_cita = 0 0 0 0 0 0;

ENDINIT

@for(plane: cita1 - cita0 = d_cita);

@for(link(i,j):

?b(i,j) = -2*(x0(i) -x0(j))*@sin ((cita1(i)+cita1(j))*3.14159265/360)?

???????? +2*(y0(i) -y0(j))*@cos ((cita1(i)+cita1(j))*3.14159265/360);

?c(i,j) = (x0(i) -x0(j)) ^2 + (y0(i) -y0(j)) ^2 - 64;

);

! 避免碰撞的條件;

! 右端點(diǎn)非負(fù);

@for(link(i,j): [Right]

?(2*V*T_max*@sin((cita1(i)-cita1(j))*3.14159265/360))^2

?????????? + b(i,j)*(2*V*T_max*@sin((cita1(i)-cita1(j))*3.14159265/360))

????????????? + c(i,j) > 0);

! 最小點(diǎn)非負(fù);

@for(link(i,j): [Minimum] @if(

?????????????? ?????-b(i,j)/4/V/@sin((cita1(i)-cita1(j))*3.14159265/360) #gt#0 #and#

??????????????????? -b(i,j)/4/V/@sin((cita1(i)-cita1(j))*3.14159265/360) #lt#T_max ,

?????????????????????????? b(i,j)^2-4*c(i,j),-1) < 0);

@for(link: @free(b));

!調(diào)整角度上下限，單位為角度;

@for(plane: @bnd( - max_cita, d_cita, max_cita));

[obj] MIN = @SUM(plane: (d_cita)^2);?

END

?

解答：

OBJ??????? 451.9266?????????? -1.000000

?

D_CITA( 1)????? -0.4772313E-06??????? 0.000000

???????????????????? D_CITA( 2)?????? -17.35147??????????? 0.000000

????????? ???????????D_CITA( 3)????? -0.3818156E-06??????? 0.000000

???????????????????? D_CITA( 4)????? -0.2057040E-06??????? 0.000000

???????????????????? D_CITA( 5)??????? 9.071291??????????? 0.000000

???????????????????? D_CITA( 6)?????? -8.280374??????????? 0.000000

?

以上解為局部最優(yōu)解，將約束30o 改為10o，得更優(yōu)的解：

?

?????????????????? ?OBJ??????? 84.90153?????????? -1.000000

D_CITA( 1)????? -0.1225291E-06??????? 0.000000

???????????????????? D_CITA( 2)????? -0.1253829E-06??????? 0.000000

???????????????????? D_CITA( 3)????? -0.1284325E-07??????? 0.000000

???????????????????? D_CITA( 4)??????? 6.515440??????????? 0.000000

???????????????????? D_CITA( 5)?????? 0.6616931E-07??????? 0.000000

????????? D_CITA( 6)??????? 6.515411??????????? 0.000000

用全局最優(yōu)求解：

?

?

? ???????????????????OBJ??????? 6.954677?????????? -1.000000

D_CITA( 1)????? -0.2922876E-07??????? 0.000000

???????????????????? D_CITA( 2)????? -0.7364397E-08??????? 0.000000

???????????????????? D_CITA( 3)??????? 2.062456??????????? 0.000000

???????????????????? D_CITA( 4)???? ?-0.4954298??????????? 0.000000

???????????????????? D_CITA( 5)????? -0.4460314E-07??????? 0.000000

???????????????????? D_CITA( 6)??????? 1.567004??????????? 0.000000

?

?

?

五．?? 模型驗(yàn)證及模型討論

對(duì)該方案跟蹤其飛行軌道檢驗(yàn)，另外隨機(jī)生成其它數(shù)據(jù)檢驗(yàn)。又給出不同的第六架飛機(jī)進(jìn)入數(shù)據(jù)，檢驗(yàn)方案的可行性。

討論：實(shí)際調(diào)度中，由于計(jì)算時(shí)間、指令發(fā)出時(shí)間等因素，應(yīng)該考慮反應(yīng)滯后的時(shí)間，也就是說，如果反應(yīng)時(shí)間是10秒，則計(jì)算中應(yīng)該采用飛機(jī)沿當(dāng)前方向角飛行10秒以后的位置作為計(jì)算的基礎(chǔ)，即：

?

?

六．?? 模型評(píng)價(jià)

?

七．?? 模型推廣

根據(jù)實(shí)際情況，可給出更一般的模型：目標(biāo)函數(shù)設(shè)定為飛機(jī)飛行方向角調(diào)整幅度絕對(duì)值的加權(quán)k次方和。

建立目標(biāo)函數(shù)：

? ????（k>0）

根據(jù)已有的經(jīng)驗(yàn)進(jìn)行嘗試：

嘗試1：k=1,Si=1(i=1,2,…,6),即飛機(jī)飛行方向角調(diào)整幅度的絕對(duì)值和模型，求得：

????????????? ，，其余為0；

嘗試2：k=4,Si=1(i=1,2,…,6),即飛機(jī)飛行方向角調(diào)整幅度的4次方和模型，求得：

?，，，

?，?，

嘗試1中，雖然第三架飛機(jī)犧牲較大，但使得被管理的六架飛機(jī)中只有兩架飛機(jī)

需要調(diào)整航向，非常值得。

?? 嘗試2中，雖然各飛機(jī)航向的調(diào)整比較平均，但增加了管理的難度，事實(shí)上是不

可取的。