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

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

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

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

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

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

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

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

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

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

11、yorTyDTxorTxDTyorTyDTxorTxijjijjijjijjijiijiijiiji歸結起來不在區域內碰撞的條件為歸結起來不在區域內碰撞的條件為 信息與計算科學系信息與計算科學系26數學數學建模建模000),(iiiyxiii0.),(121NiiNF., 1,6, 1,64)(. .,),(min2121NijiNjitttrtsFiijijNiiN數學模型數學模型初始位置與方向角初始位置與方向角調整后的方向角調整后的方向角 總的調整量總的調整量 優化數學模型優化數學模型 信息與計算科學系信息與計算科學系27數學數學建模建模.0)(, 0, 0,6. .,),(min)3(.

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

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

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

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

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

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

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