第14講飛行管理問題

1、信息與計算科學(xué)系信息與計算科學(xué)系飛行管理問題飛行管理問題數(shù)學(xué)建模算法與應(yīng)用數(shù)學(xué)建模算法與應(yīng)用信息與計算科學(xué)系信息與計算科學(xué)系3數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系4數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系5數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系6數(shù)學(xué)數(shù)學(xué)建模建模 * 對問題仔細閱讀對問題仔細閱讀, 首先抓住題目中的關(guān)鍵詞首先抓住題目中的關(guān)鍵詞“管管理理”進行聯(lián)想進行聯(lián)想. * * 抓住諸如抓住諸如“碰撞碰撞”、“調(diào)整調(diào)整”、“避免碰撞避免碰撞”、“立即立即”、“判斷判斷”等等詞語等等詞語. . * * 聯(lián)系解決問題的方案聯(lián)系解決問題的方案, ,不加約束繼續(xù)聯(lián)想，再

2、不加約束繼續(xù)聯(lián)想，再將關(guān)鍵詞搭配起來將關(guān)鍵詞搭配起來. . 信息與計算科學(xué)系信息與計算科學(xué)系7數(shù)學(xué)數(shù)學(xué)建模建模立即立即 判斷判斷 碰碰撞撞 條件條件 實時實時 算法算法 避免避免 碰撞碰撞 調(diào)整調(diào)整 方向角方向角 實時實時 幅度盡量小幅度盡量小 相對相對距離距離優(yōu)化問題優(yōu)化問題優(yōu)化算法優(yōu)化算法優(yōu)化調(diào)整方案優(yōu)化調(diào)整方案信息與計算科學(xué)系信息與計算科學(xué)系8數(shù)學(xué)數(shù)學(xué)建模建模VIIIIIIIVIV160km160km飛行位置示意圖飛行位置示意圖信息與計算科學(xué)系信息與計算科學(xué)系9數(shù)學(xué)數(shù)學(xué)建模建模這表面上是一個有這表面上是一個有6個控制對象的最優(yōu)控制問題，控制個控制對象的最優(yōu)控制問題，控制方案太多，似乎很難

3、尋優(yōu)。方案太多，似乎很難尋優(yōu)。但仔細分析這并不是空間優(yōu)化問題，只考慮但仔細分析這并不是空間優(yōu)化問題，只考慮1000010000米高米高空的面包片空的面包片；因而是；因而是平面平面問題。而實際上對每架飛機問題。而實際上對每架飛機而言是而言是一維問題一維問題，因為只有，因為只有旋轉(zhuǎn)角度旋轉(zhuǎn)角度問題，故有可能問題，故有可能簡化。簡化。信息與計算科學(xué)系信息與計算科學(xué)系10數(shù)學(xué)數(shù)學(xué)建模建模 這個有六個控制對象的這個有六個控制對象的最優(yōu)控制問題最優(yōu)控制問題可以利用可以利用平面幾何的知識平面幾何的知識證明兩個簡單結(jié)論證明兩個簡單結(jié)論, ,從而轉(zhuǎn)化為非從而轉(zhuǎn)化為非線性線性優(yōu)化優(yōu)化問題。問題。信息與計算科學(xué)系信

4、息與計算科學(xué)系11數(shù)學(xué)數(shù)學(xué)建模建模 早調(diào)整一定優(yōu)于晚調(diào)整。這樣第六架飛機剛早調(diào)整一定優(yōu)于晚調(diào)整。這樣第六架飛機剛進入正方形時就調(diào)整，由于時刻確定，問題進入正方形時就調(diào)整，由于時刻確定，問題就簡化為優(yōu)化問題。就簡化為優(yōu)化問題。結(jié)論一信息與計算科學(xué)系信息與計算科學(xué)系12數(shù)學(xué)數(shù)學(xué)建模建模A(甲飛機)F(較后調(diào)整方向)EC(較早調(diào)整后方向)DB(原來方向)飛行AD段再較后調(diào)整分析圖形: CDBA,且甲飛機不能通過二次調(diào)整到C點,要保證不碰撞,必調(diào)整到E點, 但EDBCDB A,更糟糕的結(jié)果!信息與計算科學(xué)系信息與計算科學(xué)系13數(shù)學(xué)數(shù)學(xué)建模建模 可根據(jù)數(shù)學(xué)歸納法證明可根據(jù)數(shù)學(xué)歸納法證明:如果發(fā)生碰撞，多

5、如果發(fā)生碰撞，多次調(diào)整不如在第一次調(diào)整時調(diào)整到位好。次調(diào)整不如在第一次調(diào)整時調(diào)整到位好。結(jié)論二信息與計算科學(xué)系信息與計算科學(xué)系14數(shù)學(xué)數(shù)學(xué)建模建模H(角度調(diào)整太大,不是最佳)A(甲飛機)DFC(不會碰撞方向)EB(飛機原飛行方向)GO(第一次調(diào)整方向)ODC+ BAOBAO+DAC= BAC,同時,經(jīng)過兩次調(diào)整飛機仍不能達到C點,而只能到F點,要到達AC方向,只能增大調(diào)整到E點.信息與計算科學(xué)系信息與計算科學(xué)系15數(shù)學(xué)數(shù)學(xué)建模建模這樣原問題的調(diào)整時刻確定，無須考慮時間因素，這樣原問題的調(diào)整時刻確定，無須考慮時間因素，問題轉(zhuǎn)化為一般優(yōu)化問題。問題轉(zhuǎn)化為一般優(yōu)化問題。信息與計算科學(xué)系信息與計算科學(xué)

6、系16數(shù)學(xué)數(shù)學(xué)建模建模 一般優(yōu)化問題的數(shù)學(xué)模型都是由兩部分組成，一般優(yōu)化問題的數(shù)學(xué)模型都是由兩部分組成，即即優(yōu)化的目標函數(shù)優(yōu)化的目標函數(shù)和和必須滿足的約束條件必須滿足的約束條件。 目標函數(shù)可以根據(jù)實際問題作出多種選擇。目標函數(shù)可以根據(jù)實際問題作出多種選擇。信息與計算科學(xué)系信息與計算科學(xué)系17數(shù)學(xué)數(shù)學(xué)建模建模符號定義符號定義信息與計算科學(xué)系信息與計算科學(xué)系18數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系19數(shù)學(xué)數(shù)學(xué)建模建模幅度最小用數(shù)學(xué)語言精確表示，至少有四種函數(shù)611.miniisign612.minii163.minmaxii 6214.miniii表示第表示第i架飛機的調(diào)整方向角。架飛

7、機的調(diào)整方向角。其中，其中，信息與計算科學(xué)系信息與計算科學(xué)系20數(shù)學(xué)數(shù)學(xué)建模建模222)()()()(tytytxtxrjijiij),(00iiyx),(00jjyx),(,sin)(,cos)(00jiivtytyvtxtxiiiiii,)()()sin)(sin()cos)(cos(2)(sin)cos(cos200200000022222jijijijijijijijiijyyxxtyyxxvtvr 初初始位置始位置 時刻時刻t飛機的位置飛機的位置兩架飛機的距離兩架飛機的距離信息與計算科學(xué)系信息與計算科學(xué)系21數(shù)學(xué)數(shù)學(xué)建模建模),sin)(sin()cos)(cos(2,)(sin)c

8、os(cos0000222jijijijiijjijiijyyxxvbva).0()(222ijijijijrtbtatr.64)0()(222ijijijijrtbtatr引入記號引入記號 距離表示為距離表示為 兩架飛機不碰撞條件兩架飛機不碰撞條件 信息與計算科學(xué)系信息與計算科學(xué)系22數(shù)學(xué)數(shù)學(xué)建模建模 2264ijijx tx ty ty t,0,min,ijij tT T /6,1,2,.,6ii 0800cosiiix txt 0800siniiiy tytiT表示第表示第i i架飛機飛出正方形區(qū)域的時刻。架飛機飛出正方形區(qū)域的時刻。其中，其中，6 , 1,)0(iiii信息與計算科學(xué)系

9、信息與計算科學(xué)系23數(shù)學(xué)數(shù)學(xué)建模建模0|)(02ijtijbtrdtd0ijb.64)0()(222ijijijijrtbtatr64)0(2ijijrc. 0)(22ijijijijctbtatr, 042ijijijcab不碰撞條件的另一表述不碰撞條件的另一表述： 初始不碰初始不碰, 距離增加距離增加距離減少可能碰撞距離減少可能碰撞 發(fā)生碰撞必須發(fā)生碰撞必須引入記號引入記號 無實根無實根,不不可能碰撞可能碰撞, ,條件為條件為 信息與計算科學(xué)系信息與計算科學(xué)系24數(shù)學(xué)數(shù)學(xué)建模建模, 042ijijijcabijijijijijijacabbT22)(),(),(),(ijjijjijiij

10、iTyTxTyTx,)(0)(,)(0)(,)(0)(,)(0)(DTyorTyDTxorTxDTyorTyDTxorTxijjijjijjijjijiijiijiiji即使有實根即使有實根, 碰撞也不必考慮碰撞也不必考慮 (不在區(qū)域內(nèi)碰撞不在區(qū)域內(nèi)碰撞),有實根條件有實根條件 符合條件的實根為符合條件的實根為 可能碰撞的位置可能碰撞的位置 碰撞不在區(qū)域內(nèi)的條件碰撞不在區(qū)域內(nèi)的條件信息與計算科學(xué)系信息與計算科學(xué)系25數(shù)學(xué)數(shù)學(xué)建模建模,04,0)3(04,0)2(;0)1(22ijijijijijijijijijcabbcorcabbcorbc,)(0)(,)(0)(,)(0)(,)(0)(DT

11、yorTyDTxorTxDTyorTyDTxorTxijjijjijjijjijiijiijiiji歸結(jié)起來不在區(qū)域內(nèi)碰撞的條件為歸結(jié)起來不在區(qū)域內(nèi)碰撞的條件為 信息與計算科學(xué)系信息與計算科學(xué)系26數(shù)學(xué)數(shù)學(xué)建模建模000),(iiiyxiii0.),(121NiiNF., 1,6, 1,64)(. .,),(min2121NijiNjitttrtsFiijijNiiN數(shù)學(xué)模型數(shù)學(xué)模型初始位置與方向角初始位置與方向角調(diào)整后的方向角調(diào)整后的方向角 總的調(diào)整量總的調(diào)整量 優(yōu)化數(shù)學(xué)模型優(yōu)化數(shù)學(xué)模型 信息與計算科學(xué)系信息與計算科學(xué)系27數(shù)學(xué)數(shù)學(xué)建模建模.0)(, 0, 0,6. .,),(min)3(.

12、0, 0,6. .,),(min)2(.0,6. .,),(min) 1 (212112121121ijiijijijijiNiiNijijijijiNiiNijiNiiNTxcabbtsFcabbtsFbtsF對應(yīng)兩架飛機不碰撞條件的另一表述的優(yōu)化模型對應(yīng)兩架飛機不碰撞條件的另一表述的優(yōu)化模型信息與計算科學(xué)系信息與計算科學(xué)系28數(shù)學(xué)數(shù)學(xué)建模建模 這個非線性優(yōu)化問題可以利用物理上的相對運這個非線性優(yōu)化問題可以利用物理上的相對運動原理化為一族線性優(yōu)化問題，動原理化為一族線性優(yōu)化問題，即把一個物體看成即把一個物體看成不動，另一物體對它作相對運動不動，另一物體對它作相對運動。 因為目標函數(shù)是分段線性

13、的，約束條件是關(guān)于坐因為目標函數(shù)是分段線性的，約束條件是關(guān)于坐標的平方，并不是標的平方，并不是 的非線性函數(shù)，因此有可能的非線性函數(shù)，因此有可能轉(zhuǎn)化為線性優(yōu)化問題。轉(zhuǎn)化為線性優(yōu)化問題。i信息與計算科學(xué)系信息與計算科學(xué)系29數(shù)學(xué)數(shù)學(xué)建模建模PiijPj8iVjVijV相對運動及相對速度示意圖相對運動及相對速度示意圖 （注意與課本不同！注意與課本不同?。╋w機 視為不動，坐標系定義在 上。ji信息與計算科學(xué)系信息與計算科學(xué)系30數(shù)學(xué)數(shù)學(xué)建模建模利用相對運動原理相對運動原理可以將坐標的非線性約束等價轉(zhuǎn)換為飛行方向角的線性約束。 任給兩架飛機 和 ，讓坐標系固定在 上， 在新坐標系下的運動即 對 的相對

14、運動，顯然， 與 在相撞（不考慮正方形區(qū)域限制）的充要條件是 的方向見上圖，其中相對速度方向不落在這個扇形內(nèi)，就一定是安全的。0tiPjPiPiPiPjPjPjP88arcsin,arcsinijijijijijdd1222( (0)(0)(0)(0) ijijijdxxyyijV信息與計算科學(xué)系信息與計算科學(xué)系31數(shù)學(xué)數(shù)學(xué)建模建模對飛行速度矢量vi ，由題目條件有，|vi=|vi=800 =a(km)飛行方向角為i用復(fù)數(shù)表示vi得。iiivae信息與計算科學(xué)系信息與計算科學(xué)系32數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系33數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系34數(shù)學(xué)數(shù)學(xué)建

15、模建模非線性規(guī)劃化為線性規(guī)劃圖示非線性規(guī)劃化為線性規(guī)劃圖示jvivjivvX軸ijji易得到：易得到： )( )(22)(22jijijijijiij無方向信息與計算科學(xué)系信息與計算科學(xué)系35數(shù)學(xué)數(shù)學(xué)建模建模相對速度方向相對速度方向 ()22ijijijsign信息與計算科學(xué)系信息與計算科學(xué)系36數(shù)學(xué)數(shù)學(xué)建模建模當當P Pj j的飛行方向不變時，因為的飛行方向不變時，因為V Vi i=V=Vj j=800km/h=800km/h，所以，所以相對速度相對速度V Vijij方向由方向由P Pi i的飛行方向角的飛行方向角i i唯一決定，且唯一決定，且根據(jù)矢量法則是根據(jù)矢量法則是i i的線性函數(shù)的線

16、性函數(shù)(0)(0),(0)(0)22(0)(0),(0)(0)(1)22(0)(0)iijjiijjiijjiijjijiijj 無方向信息與計算科學(xué)系信息與計算科學(xué)系37數(shù)學(xué)數(shù)學(xué)建模建模因此原來關(guān)于坐標的非線性約束轉(zhuǎn)化為飛行方向角增量的線性約束：ij(0)(0)(0)(0)8arcsin(0)(0)22iijjiijjjjiiijd(0)(0)1,2,1, ,iijjinnji或者或者jjiijjiijjiiijijd)0()0()0()0(22)0()0(8arcsin信息與計算科學(xué)系信息與計算科學(xué)系38數(shù)學(xué)數(shù)學(xué)建模建模目標函數(shù)可以從前三個任選一個。這樣線性規(guī)劃模型其中一個如下：61min

17、|.|,1,2,66(0)(0)8arcsin2( (0)(0)21,2,5;1,6iiiiijjijijiijjstidsigniji 信息與計算科學(xué)系信息與計算科學(xué)系39數(shù)學(xué)數(shù)學(xué)建模建模課本表示方法課本表示方法信息與計算科學(xué)系信息與計算科學(xué)系40數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系41數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系42數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系43數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系44數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系45數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系46數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與

18、計算科學(xué)系47數(shù)學(xué)數(shù)學(xué)建模建模arg()()nmiimmnneexiyxiyq qq q-=+-+信息與計算科學(xué)系信息與計算科學(xué)系48數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系49數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系50數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系51數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系52數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系53數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系54數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系55數(shù)學(xué)數(shù)學(xué)建模建模信息與計算科學(xué)系信息與計算科學(xué)系56數(shù)學(xué)數(shù)學(xué)建模建模本題簡化有三大步：本題簡化有三大步： 第一步第一步，最優(yōu)控制轉(zhuǎn)化為，最優(yōu)控制轉(zhuǎn)化為非線性優(yōu)化問題非線性優(yōu)化問題，這，這只利用了平面幾何的兩個簡單結(jié)論，總是成立的。只利用了平面幾何的兩個簡單結(jié)論，總是成立的。 第二步第二步，利用相對運動原理，將非線性優(yōu)化問，利