吳曉層博士- 數(shù)學建模競賽中的優(yōu)化問題

1、 優(yōu)優(yōu) 化化 建建 模模優(yōu)化模型優(yōu)化模型廣西大學數(shù)信學院廣西大學數(shù)信學院 吳曉層吳曉層 優(yōu)優(yōu) 化化 建建 模模 一、簡單優(yōu)化模型一、簡單優(yōu)化模型 優(yōu)優(yōu) 化化 建建 模模簡單優(yōu)化模型簡單優(yōu)化模型 1 血管分支血管分支 優(yōu)優(yōu) 化化 建建 模模 優(yōu)優(yōu) 化化 建建 模模 優(yōu)優(yōu) 化化 建建 模模 優(yōu)優(yōu) 化化 建建 模模（1）血）血 管管 分分 支支分分析析機體提供能量維持血液在血管中的流動機體提供能量維持血液在血管中的流動給血管壁以營養(yǎng)、給血管壁以營養(yǎng)、克服血液流動的阻力克服血液流動的阻力消耗能量消耗能量取決于血管的取決于血管的幾何形狀幾何形狀在長期進化中動物血管的幾何形狀在長期進化中動物血管的幾何形狀

2、已經(jīng)達到已經(jīng)達到能量最小原則能量最小原則研究在能量最小原則下，血管分支處研究在能量最小原則下，血管分支處粗細血管半徑比例和分岔角度粗細血管半徑比例和分岔角度問問題題 優(yōu)優(yōu) 化化 建建 模模模型假設模型假設一條粗血管和兩條細血管在分支點對稱地處于同一平面一條粗血管和兩條細血管在分支點對稱地處于同一平面血液流動近似于粘性流體在剛性管道中的運動血液流動近似于粘性流體在剛性管道中的運動血液給血管壁的能量隨血液給血管壁的能量隨管壁的內表面積和體積管壁的內表面積和體積的增加而增加，管壁厚的增加而增加，管壁厚度近似與血管半徑成正度近似與血管半徑成正比比qq1q1ABB CHLll1rr1 q=2q1r/r1

3、, ?考察血管考察血管AC與與CB, CB 優(yōu)優(yōu) 化化 建建 模模粘性流體在剛粘性流體在剛性管道中運動性管道中運動lprq84 pA,C壓力差，壓力差， 粘性系數(shù)粘性系數(shù)克服阻力消耗能量克服阻力消耗能量4218dlqpqE提供營養(yǎng)消耗能量提供營養(yǎng)消耗能量21,2lbrE管壁內表面積管壁內表面積 2 rl管壁體積管壁體積 (d2+2rd)l,管壁厚度管壁厚度d與與r成正比成正比模型假設模型假設qq1q1ABB CHLll1rr1 優(yōu)優(yōu) 化化 建建 模模模型建立模型建立qq1q1ABB CHLll1rr1 4218dlqpqE克服阻力消耗能量克服阻力消耗能量21,2lbrE提供營養(yǎng)消耗能量提供營養(yǎng)

4、消耗能量11412142212)/()/(lbrrkqlbrrkqEEEsin/,/1HLltgHLlsin/2)/()tan/)(/(),(14121421HbrrkqHLbrrkqrrE機體為血流提供能量機體為血流提供能量 優(yōu)優(yōu) 化化 建建 模模模型求解模型求解qq1q1ABB CHLll1rr1 0,01rErE0/40/451211521rkqrbrkqrb4114rr0E412cosrr442cos210014937,32. 1/26. 1rrsin/2)/()tan/)(/(),(14121421HbrrkqHLbrrkqrrE 優(yōu)優(yōu) 化化 建建 模模模型模型解釋解釋生物學家：結果

5、與觀察大致吻合生物學家：結果與觀察大致吻合大動脈半徑大動脈半徑rmax, 毛細血管半徑毛細血管半徑rmin大動脈到毛細血管有大動脈到毛細血管有n次分岔次分岔 4114rr4minmax4nrr5minmax41000/rr21001493732. 1/26. 1rr觀察：狗的血管觀察：狗的血管)4(5n3025n血管總條數(shù)血管總條數(shù)97302510103222n推論推論n=？ 優(yōu)優(yōu) 化化 建建 模模 二、數(shù)學規(guī)劃模型二、數(shù)學規(guī)劃模型 優(yōu)優(yōu) 化化 建建 模模 0-1規(guī)劃規(guī)劃 當決策變量要求是取當決策變量要求是取0-1值時，對應的規(guī)劃問題成為值時，對應的規(guī)劃問題成為0-1 規(guī)劃問題。規(guī)劃問題。 例

6、例1：設婚姻介紹所里有：設婚姻介紹所里有4位男士、位男士、5位女士要求服務。設位女士要求服務。設 婚姻介紹所根據(jù)各自的條件，分別為他們得出若他們相識婚姻介紹所根據(jù)各自的條件，分別為他們得出若他們相識后的預測幸福值如下：后的預測幸福值如下： W1W2W3W4W5M111257M2123710M3134910M41451010 婚姻介紹所應如何介紹他們認識，才能使總的幸福值最大？婚姻介紹所應如何介紹他們認識，才能使總的幸福值最大？ 優(yōu)優(yōu) 化化 建建 模模 解：設 ，則建立如下數(shù)學模型： 10ijMiWjx若介紹與相識否則45114151max1,1,2,.,51,1,2,3,401,1,2,3,4

7、,1,.,5ijijijijiijjijzc xxjxixij或W1W2W3W4W5M111257M2123710M3134910M41451010 直接求解無可行解，可假想一人M5 解得：x13=x25=x32（4） =x44（2）=x51=1,其它為0 zmax=25 優(yōu)優(yōu) 化化 建建 模模 例例2：某鉆井隊要從以下十個可供選擇的井位中確定五個：某鉆井隊要從以下十個可供選擇的井位中確定五個鉆井探油，使總的鉆井費用為最少。若十個井位的代號分鉆井探油，使總的鉆井費用為最少。若十個井位的代號分別為別為s1，s2，s10，相應的鉆探費分別為，相應的鉆探費分別為c1，c2，c10，并且井位選擇方面要

8、滿足下列要求：并且井位選擇方面要滿足下列要求： 1、或選擇、或選擇s1和和s7，或選擇鉆探，或選擇鉆探s8； 2、選擇了、選擇了s3或或s4就不能選就不能選s5，或反過來也一樣；，或反過來也一樣； 3、在、在s5，s6，s7，s8中最多只能選兩個。中最多只能選兩個。 解：設解：設 ，則建立如下數(shù)學模型：，則建立如下數(shù)學模型： 10jijsx若選擇鉆探第 井位否則101101835178455678max5,1,11,1,201,1,2,10jjjjjjzc xxxxxxxxxxxxxxxj或 優(yōu)優(yōu) 化化 建建 模模1. CUMCM-1995A: 一個飛行管理問題一個飛行管理問題 2. CUMC

9、M-2000B: 鋼管訂購與運輸鋼管訂購與運輸3. CUMCM-2003B：露天礦生產(chǎn)的車輛安排：露天礦生產(chǎn)的車輛安排4. CUMCM-2000D: 空洞探測空洞探測 非線性規(guī)劃非線性規(guī)劃（競賽題）（競賽題） 優(yōu)優(yōu) 化化 建建 模模1995年全國大學生數(shù)學建模競賽年全國大學生數(shù)學建模競賽A題題 一個飛行管理問題一個飛行管理問題 優(yōu)優(yōu) 化化 建建 模模一個飛行管理問題 在約10000m高空的某邊長160km的正方形區(qū)域內,經(jīng)常有若干架飛機作水平飛行,區(qū)域內每架飛機的位置和速度向量均由計算機記錄其數(shù)據(jù),以便進行飛行管理.當一架欲進入該區(qū)域的飛機到達邊界區(qū)域邊緣時, 記錄其數(shù)據(jù)后,要立即 計算并判斷

10、是否會與其區(qū)域內的飛機發(fā)生碰撞.如果會碰撞 ,則應計算如何調整各架(包括新進入的)飛機飛行的方向角,以避免碰撞.現(xiàn)假設條件如下: 1) 不碰撞的標準為任意兩架飛機的距離大于8km; 2)飛機飛行方向角調整的幅度不應超過30度; 3)所有飛機飛行速度均為每小時為800km; 4)進入該區(qū)域的飛機在到達區(qū)域邊緣時,與區(qū)域內飛機的距離應在 60km以上; 5)最多考慮6架飛機; 6)不必考慮飛機離開此區(qū)域后的狀況; 優(yōu)優(yōu) 化化 建建 模模請你對這個避免碰撞的飛行管理問題建立數(shù)學模型.列出計算步驟,對以下數(shù)據(jù)進行計算(方向角誤差不超過0.01度),要求飛機飛行方向角調整的幅度盡量小 .設該區(qū)域4個頂點

11、坐標為(0,0),(160,0),(160,160),(0,160).記錄數(shù)據(jù)為: 飛機編號 橫坐標x 縱坐標y 方向角(度) 1 150 140 243 2 85 85 236 3 150 155 220.5 4 145 50 159 5 130 150 230 新進入 0 0 52注: 方向角指飛行方向與x軸正向的夾角 優(yōu)優(yōu) 化化 建建 模模兩架飛機不碰撞的條件兩架飛機不碰撞的條件222)()()(tjttjtijyyxxtrii,sin,cos00iitiitivtyyvtxxi064)()(2trtfijij（0 t Tij） Ti為第為第i架飛機飛出區(qū)域的時刻架飛機飛出區(qū)域的時刻不碰

12、撞條件不碰撞條件000),(iiiyxiii0 初始位置 時刻t飛機的位置兩架飛機的距離（平方） 優(yōu)優(yōu) 化化 建建 模模),min(jiijTTT 00000000000000000000tan,223tan,23,sin,tan,23tan,2,cos,tan,2tan,20,sin,tan,223tan,20,cosiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiixDyorxyifvyxyorxyDifvxxyDorxDyDifvxDxDyorxDyDifvxDT不必考慮在區(qū)域外的碰撞兩架飛機都在區(qū)域中的時間具體來看，第i架飛機在區(qū)域內的時間飛機飛出區(qū)域的

13、時刻飛機飛出區(qū)域的時刻 優(yōu)優(yōu) 化化 建建 模模.)(2ijijijijijczbztf整理： fij(t)的最小值 (- bij2 / 4 + cij ) ；此時其中： .2sin4*jiijijvbt 優(yōu)優(yōu) 化化 建建 模模不碰撞條件的等價表述不碰撞條件的等價表述 最后，優(yōu)化模型為最后，優(yōu)化模型為 0*ijt若fij(t)大于等于肯定成立ijijTt *若fij(t)大于等于等價于0)(ijijTfijijTt *0若fij(t)大于等于等價于0)(*ijtfij, 042ijijcb 優(yōu)優(yōu) 化化 建建 模模LINGOLINGO求解求解283. 0800/2160/2maxvDT一個簡化的數(shù)

14、學模型一個簡化的數(shù)學模型任何一架飛機在區(qū)域中停留最長時間 放松到任兩架飛機在這段時間不碰撞甚至放松到任兩架飛機永遠不碰撞 優(yōu)優(yōu) 化化 建建 模模000),(iiiyxiii0.61iiMin其他目標調整后的方向角 總的調整量最小總的調整量最小 |max6,.,1iiMin最大調整量最小最大調整量最小 初始位置與方向角 優(yōu)優(yōu) 化化 建建 模模基于相對運動觀點的模型 優(yōu)優(yōu) 化化 建建 模模)22sin(),22(cos(2sin2)2cos,2sin(2sin2)2cos2sin,2sin2sin(2)sinsin,coscos(jijijijijijijijijijiijijvvvvvvvvvi

15、jijr基于相對運動觀點的模型,8sin1ijijr 優(yōu)優(yōu) 化化 建建 模模于是 . 6 , 1,30, 6 , 1,)(. .21612ijijitsMiniijjiijii數(shù)學規(guī)劃模型 優(yōu)優(yōu) 化化 建建 模模2000年全國大學生數(shù)學建模競賽年全國大學生數(shù)學建模競賽B題題 鋼管訂購與運輸鋼管訂購與運輸 優(yōu)優(yōu) 化化 建建 模模問題描述問題描述 由鋼管廠訂購鋼管，經(jīng)鐵由鋼管廠訂購鋼管，經(jīng)鐵路、公路運輸，鋪設一條路、公路運輸，鋪設一條鋼管管道鋼管管道1521AAAA1325801010312012427010881070627030202030450104301750606194205201680

16、480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道鐵路公路S1S7 鋼管廠火車站450 里程（km)（沿管道建有公路） 優(yōu)優(yōu) 化化 建建 模模鋼 廠 i1234567產(chǎn) 量 上 限 is80080010002000200020003000銷 價ip（ 萬 元 ）160155155160155150160鋼廠的產(chǎn)量和銷價（1單位鋼管=1km管道鋼管）鋼廠產(chǎn)量的下限：500單位鋼管里程(km)3003

17、01350351400401450451500運價(萬元)2023262932里程(km)5016006017007018008019009011000運價(萬元)37445055601單位鋼管的鐵路運價1000km以上每增加1至100km運價增加5萬元1單位鋼管的公路運價：0.1萬元/km（不足整公里部分按整公里計） 優(yōu)優(yōu) 化化 建建 模模（1）制定鋼管的訂購和運輸計劃，使總費用最?。┲贫ㄤ摴艿挠嗁徍瓦\輸計劃，使總費用最小.（2）分析對購運計劃和總費用影響：哪個鋼廠鋼管銷價的）分析對購運計劃和總費用影響：哪個鋼廠鋼管銷價的變化影響最大；哪個鋼廠鋼管產(chǎn)量上限的變化影響最大？變化影響最大；哪個鋼

18、廠鋼管產(chǎn)量上限的變化影響最大？A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（3）討論管道為樹形圖的情形）討論管道為樹形圖的情形 優(yōu)優(yōu) 化化 建建 模模問題問題1的基本模型和解法的基本模型和解法總費用最小

19、的優(yōu)化問題總費用：訂購，運輸（由各廠Si經(jīng)鐵路、公路至各點Aj, i=1,7; j=1, 15 ），鋪設管道Aj Aj+1 （j=1, 14)由Si至Aj的最小購運費用路線及最小費用cij 由Si至Aj的最優(yōu)運量xij由Aj向Aj Aj-1段鋪設的長度yj及向Aj Aj+1段鋪設的長度zj最優(yōu)購運計劃最優(yōu)購運計劃約束約束條件條件鋼廠產(chǎn)量約束：上限和下限（如果生產(chǎn)的話）運量約束：xij對i求和等于zj 加yj； zj與 yj+1之和等于Aj Aj+1段的長度ljyj zjAj-1 Aj Aj+1 優(yōu)優(yōu) 化化 建建 模?；灸Ｐ突灸Ｐ陀葾j向Aj Aj-1段鋪設的運量為 1+ +yj= yj(

20、yj+1)/2由Aj向Aj Aj+1段鋪設的運量為 1+ +zj= zj( zj+1)/2)6(0, 0) 5(15, 2 , 1, 7 , 2 , 10, 0, 0)4(14, 2 , 1) 3(15, 2 , 1)2(7 , 2 , 1,5000. .) 1 ()1() 1(21 . 0min15117115171151151zyjiyzxjlyzjyzxisxtsyyzzxcjjijjjjjjiijijijijjjjjjijij二次規(guī)劃? 優(yōu)優(yōu) 化化 建建 模模求解步驟求解步驟1）求由Si至Aj的最小購運費用路線及最小費用cij 難點：公路運費是里程的線性函數(shù)，而鐵路運費是里程的分段階躍

21、函數(shù)，故總運費不具可加性。因而計算最短路常用的Dijkstra算法、Floyd算法失效。7010881070627030202030300220210420500170690462160320160110290A10A11A12A13A14A15S4S5S6S7需要對鐵路網(wǎng)和公路網(wǎng)進行預處理，才能使用常用需要對鐵路網(wǎng)和公路網(wǎng)進行預處理，才能使用常用算法，得到最小購運費用路線。算法，得到最小購運費用路線。- 至少求至少求3次最短路次最短路如S7至A10的最小費用路線先鐵路1130km，再公路70km, 運費為77（萬元）先公路（經(jīng)A15）40km, 再鐵路1100km，再公路70km, 運費為7

22、6（萬元） 優(yōu)優(yōu) 化化 建建 模模任意兩點之間最短路的任意兩點之間最短路的Floyd-Warshall算法算法 1）求由Si至Aj的最小購運費用路線及最小費用cij ., 1,min, 0)()()()1()1()1(nkjiuuuujiwuukkjkikkijkijijijiiuij(k) 是任意兩個節(jié)點是任意兩個節(jié)點i，j之間距離的臨時標號，即從節(jié)點之間距離的臨時標號，即從節(jié)點i到到j但不允許經(jīng)過其他節(jié)點但不允許經(jīng)過其他節(jié)點k，k+1，, n時的最短距離時的最短距離 優(yōu)優(yōu) 化化 建建 模模的的處處理理約約束束條條件件)7 , 2 , 1(,5000)2151 isxijij問問題題求求解解

23、。，分分解解為為上上述述形形式式的的子子的的那那些些求求解解，再再對對解解中中滿滿足足先先松松弛弛為為ixisxbjijijij5000)7, 1(0)151151 個個子子問問題題共共和和分分解解為為71511512)7, 1(5000) isxxaijijjij實際上只有S4和S7需要分解成子問題求解每個子問題是標準的二次規(guī)劃，決策變量為xij,yj,zj, 不超過135個 。0, 0,0. .)(05.0min1511711512151271151zyzyxlyzzyxsxtsyyzzxcjjijjjjjijijjiijjjjjjijijij 優(yōu)優(yōu) 化化 建建 模模fi表示鋼廠表示鋼廠i

24、是否使用；是否使用；xij是從鋼廠是從鋼廠i運到節(jié)點運到節(jié)點j的鋼管量的鋼管量yj是從節(jié)點是從節(jié)點j向左鋪設的鋼管量；向左鋪設的鋼管量；zj是向右鋪設的鋼管量是向右鋪設的鋼管量 c) 比較好的方法：引入比較好的方法：引入0-10-1變量變量. 7,.,1, 1 , 0, 0.14,.,1.15,.,1,. 7,.,1,500. .)1 ()1(21 . 0)(151171151151,ifzyjbzyjzyxifSxftszzyyxcpMinijjjjjiijiijijijjjjjjiijijiyj zjAj 優(yōu)優(yōu) 化化 建建 模模問題問題2: 分析對購運計劃和總費用影響分析對購運計劃和總費用

25、影響(哪個鋼廠銷價變哪個鋼廠銷價變化影響最大；哪個鋼廠產(chǎn)量上限變化影響最大化影響最大；哪個鋼廠產(chǎn)量上限變化影響最大)規(guī)劃問題的靈敏度分析問題問題3：管道為樹形圖管道為樹形圖701088107062300220210170690462160320160A10A11A12S4S5S6130A17A18A19A20190260100, 0,500 , 0. .)(05.0min71)(2112211)(71211 jkijjkkjjkijkEjkijjiijjkjkjEjkijijijyxbyyyxsxtsyyxc(jk)是連接Aj,Ak的邊，E是樹形圖的邊集， ljk是(jk)的長度， yjk是由

26、Aj沿(jk)鋪設的鋼管數(shù)量 優(yōu)優(yōu) 化化 建建 模模2003年全國大學生數(shù)學建模競賽年全國大學生數(shù)學建模競賽B題題 露天礦生產(chǎn)的車輛安排露天礦生產(chǎn)的車輛安排 優(yōu)優(yōu) 化化 建建 模模露天礦里鏟位已分成礦石和巖石露天礦里鏟位已分成礦石和巖石: 平均鐵含量不低于平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個鏟位至多安置一臺電鏟，電鏟平均裝車時間每個鏟位至多安置一臺電鏟，電鏟平均裝車時間5分鐘分鐘卡車在等待時所耗費的能量也是相當可觀的，原則

27、上卡車在等待時所耗費的能量也是相當可觀的，原則上在安排時在安排時不應發(fā)生卡車等待不應發(fā)生卡車等待的情況。的情況。 露天礦生產(chǎn)的車輛安排露天礦生產(chǎn)的車輛安排 礦石卸點需要的鐵含量要求都為礦石卸點需要的鐵含量要求都為29.5% 1%(品位限品位限制），搭配量在一個班次（制），搭配量在一個班次（8小時）內滿足品位限制即小時）內滿足品位限制即可。卸點在一個班次內不變?？ㄜ囕d重量為可。卸點在一個班次內不變?？ㄜ囕d重量為154噸，平噸，平均時速均時速28km,平均卸車時間為平均卸車時間為3分鐘。分鐘。問題：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛問題：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛卡車，分別在哪

28、些路線上各運輸多少次卡車，分別在哪些路線上各運輸多少次 ? 優(yōu)優(yōu) 化化 建建 模模平面示意圖 優(yōu)優(yōu) 化化 建建 模模問題數(shù)據(jù)問題數(shù)據(jù) 距離鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏5.265.194.214.002.952.742.461.900.641.27倒裝1.900.991.901.131.272.251.482.043.093.51巖場5.895.615.614.563.513.652.462.461.060.57巖石漏0.641.761.271.832.742.604.213.725.056.10倒裝4.423.863.723.162.252.810.78

29、1.621.270.50鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石量095105100105110125105130135125巖石量125110135105115135105115135125鐵含量30%28%29%32%31%33%32%31%33%31% 優(yōu)優(yōu) 化化 建建 模模問題分析問題分析 與典型的運輸問題明顯有以下不同：與典型的運輸問題明顯有以下不同：這是運輸?shù)V石與巖石兩種物資的問題；這是運輸?shù)V石與巖石兩種物資的問題；屬于產(chǎn)量大于銷量的不平衡運輸問題；屬于產(chǎn)量大于銷量的不平衡運輸問題；為了完成品位約束，礦石要搭配運輸；為了完成品位約束，礦石要搭配運輸；產(chǎn)地、

30、銷地均有單位時間的流量限制；產(chǎn)地、銷地均有單位時間的流量限制；運輸車輛只有一種，每次滿載運輸，運輸車輛只有一種，每次滿載運輸，154噸噸/車次；車次；鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于7個個產(chǎn)地作為最后結果中的產(chǎn)地；產(chǎn)地作為最后結果中的產(chǎn)地；1. 最后求出各條路線上的派出車輛數(shù)及安排。最后求出各條路線上的派出車輛數(shù)及安排。近似處理：近似處理：先求出產(chǎn)位、卸點每條線路上的運輸量先求出產(chǎn)位、卸點每條線路上的運輸量(MIP模型模型)然后求出各條路線上的派出車輛數(shù)及安排然后求出各條路線上的派出車輛數(shù)及安排 優(yōu)優(yōu) 化化 建建 模模模型假設模型假設 卡車在一個

31、班次中不應發(fā)生等待或熄火后再啟動卡車在一個班次中不應發(fā)生等待或熄火后再啟動的情況；的情況； 在鏟位或卸點處由兩條路線以上造成的沖突問題在鏟位或卸點處由兩條路線以上造成的沖突問題面前，我們認為只要平均時間能完成任務，就認面前，我們認為只要平均時間能完成任務，就認為不沖突。我們不排時地進行討論；為不沖突。我們不排時地進行討論； 空載與重載的速度都是空載與重載的速度都是28km/h，耗油相差很大；，耗油相差很大； 卡車可提前退出系統(tǒng)，等等?？ㄜ嚳商崆巴顺鱿到y(tǒng)，等等。如理解為嚴格不等待，難以用數(shù)學規(guī)劃模型來解如理解為嚴格不等待，難以用數(shù)學規(guī)劃模型來解 個別參數(shù)隊找到了可行解個別參數(shù)隊找到了可行解 （略

32、）（略） 優(yōu)優(yōu) 化化 建建 模模符號符號 xij ：從：從i鏟位到鏟位到j號卸點的石料運量號卸點的石料運量 （車）（車） 單位：單位： 噸；噸； cij ：從：從i號鏟位到號鏟位到j號卸點的距離號卸點的距離 公里；公里； Tij :從從i號鏟位到號號鏟位到號j卸點路線上運行一個周期平均時間卸點路線上運行一個周期平均時間 分；分； Aij ：從號鏟位到號卸點最多能同時運行的卡車數(shù)：從號鏟位到號卸點最多能同時運行的卡車數(shù) 輛；輛； Bij ：從號鏟位到號卸點路線上一輛車最多可運行的次數(shù)：從號鏟位到號卸點路線上一輛車最多可運行的次數(shù) 次；次； pi：i號鏟位的礦石鐵含量號鏟位的礦石鐵含量 p=(30

33、,28,29,32,31,33,32,31,33,31) % qj : j號卸點任務需求，號卸點任務需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 噸噸 cki ：i號鏟位的鐵礦石儲量號鏟位的鐵礦石儲量 萬噸萬噸 cyi ：i號鏟位的巖石儲量號鏟位的巖石儲量 萬噸萬噸 fi :描述第描述第i號鏟位是否使用的號鏟位是否使用的0-1變量，取變量，取1為使用；為使用；0為關閉。為關閉。532平均速度距離到jiTij5ijijTAijijijTAB5) 1(608(近似近似) 優(yōu)優(yōu) 化化 建建 模模優(yōu)化模型cxijijij10151min5 , 1,10, 1,jiBAxijijij

34、10, 1, 5/60851ifxijij5 , 1,208101jiijx10, 1,154/10000154/1000043521icyxxckxxxiiiiiii（1）道路能力道路能力(卡車數(shù)卡車數(shù))約束約束（2）電鏟能力約束（3）卸點能力約束（4）鏟位儲量約束（5）產(chǎn)量任務約束（6）鐵含量約束（7）電鏟數(shù)量約束（8）整數(shù)約束 5 , 1,154/101jqxjiij5 , 2 , 1,0)5 .28(0)5 .30(101101jpxpxiiijiiij.7101iifxij為非負整數(shù)fi 為0-1整數(shù) 優(yōu)優(yōu) 化化 建建 模模計算結果（計算結果（LINGOLINGO軟件）軟件）鏟位1鏟

35、位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦漏131354541111倒42424343巖場70701515巖漏81814343倒13132 27070鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏0.8671.8620.314倒場1.0771.162巖場1.8920.326巖石漏1.8411.229倒場0.6840.11.489注注: LINGO8.0本來是可以得到最優(yōu)解的，但有些本來是可以得到最優(yōu)解的，但有些 LINGO8.0可能出現(xiàn)系統(tǒng)錯誤可能出現(xiàn)系統(tǒng)錯誤, 可能是系統(tǒng)可能是系統(tǒng)BUG 優(yōu)優(yōu) 化化 建建 模模計算結果（派車）計算結果（派車）鏟位1鏟位2鏟

36、位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏1 (29)倒場1 (39)1 (37)巖場1 (37)巖石漏1(44)1 (35)倒場1 (47)結論：結論：鏟位鏟位1、2、3、4、8、9、10處各放置一臺電鏟。處各放置一臺電鏟。一共使用了一共使用了13輛卡車；總運量為輛卡車；總運量為85628.62噸公里；噸公里；巖石產(chǎn)量為巖石產(chǎn)量為32186噸；礦石產(chǎn)量為噸；礦石產(chǎn)量為38192噸。噸。此外：此外：6輛聯(lián)合派車（方案略）輛聯(lián)合派車（方案略） 優(yōu)優(yōu) 化化 建建 模模最大化產(chǎn)量最大化產(chǎn)量結論：結論：（略）（略）目標函數(shù)變化目標函數(shù)變化此外：車輛數(shù)量（此外：車輛數(shù)量（20輛）限制（其實上

37、面的模型也輛）限制（其實上面的模型也應該有）應該有） 優(yōu)優(yōu) 化化 建建 模模2000年全國大學生數(shù)學建模競賽年全國大學生數(shù)學建模競賽D題題 空洞探測空洞探測 優(yōu)優(yōu) 化化 建建 模模山體隧道壩體等的某些內部結構可用彈性波測量來確定。簡化問題可敘述為，一塊均勻介質構成的矩形平板內有一些充滿空氣的空洞。在平板的兩個鄰邊分別等距地設置若干波源，在他們的對邊對等地安放同樣多的接收器，記錄彈性波由每個波源到達對邊上每個接收器的時間。根據(jù)彈性波在介質和在空氣中不同的傳播速度來確定板內空洞的位置 優(yōu)優(yōu) 化化 建建 模模具體問題：一塊240(米)240(米)的平板ABCD， 在AB 邊等距地設置7個波源Pi (

38、i=1,7),在 CD 邊等距地設置7個接收器Qj (j=1,7), 記錄由 Pi 發(fā)出的彈性波到達 Qj 的時間 tij(秒) ; 在AD 邊等距地設置7個波源 Ri (i=1,7),在 BC 邊等距地設置7個接收器Sj (j=1,7), 記錄由 Ri 發(fā)出的彈性波到達 Sj 的時間 ij(秒)。 已知彈性波在介質和空氣中的傳播速度分別為2880(米/秒)和320(米/秒), 且彈性波沿板邊緣的傳播速度與在介質中的傳播速度相同 優(yōu)優(yōu) 化化 建建 模模CBADP2Q4R3S6 優(yōu)優(yōu) 化化 建建 模模TP=(tij)tij Q1 Q2 Q3 Q4 Q5 Q6 Q7P1 .0611 .0895 .

39、1996 .2032 .4181 .4923 .5646P2 .0989 .0592 .4413 .4318 .4770 .5242 .3805P3 .3052 .4131 .0598 .4153 .4156 .3563 .1919P4 .3221 .4453 .4040 .0738 .1789 .0740 .2122P5 .3490 .4529 .2263 .1917 .0839 .1768 .1810P6 .3807 .3177 .2364 .3064 .2217 .0939 .1031P7 .4311 .3397 .3566 .1954 .0760 .0688 .1042 優(yōu)優(yōu) 化化 建

40、建 模模TR=(ij)ij S1 S2 S3 S4 S5 S6 S7R1 .0645 .0602 .0813 .3516 .3867 .4314 .5721R2 .0753 .0700 .2852 .4341 .3491 .4800 .4980R3 .3456 .3205 .0974 .4093 .4240 .4540 .3112R4 .3655 .3289 .4247 .1007 .3249 .2134 .1017R5 .3165 .2509 .3214 .3256 .0904 .1874 .2130R6 .2749 .3891 .5895 .3016 .2058 .0841 .0706R7

41、 .4434 .4919 .3904 .0786 .0709 .0914 .0583 優(yōu)優(yōu) 化化 建建 模模要求：(1) 確定該平面內空洞的位置。(2) 只根據(jù)Pi發(fā)出的彈性波到達Qj的時間tij 能確定空洞的位置嗎？討論在同樣能夠確定空洞位置的前提下，減少波源和接收器的方法。 優(yōu)優(yōu) 化化 建建 模模分析: 彈性波沿平板邊緣的理論傳播時間 t=240/2880=0.0833(秒) 彈性波沿平板邊緣的實際傳播時間 t11=.0611, t77=.1042, 11=.0645, 77=.0583 題目中已假設“彈性波沿板邊緣的傳播速度與在介質中的傳播速度相同”觀測數(shù)據(jù)的最大絕對誤差為d=0.025

42、秒.可以認為，可以認為，0.025*360 =9(米）以下的空洞是米）以下的空洞是探測不出的探測不出的 優(yōu)優(yōu) 化化 建建 模模假設1. 觀測數(shù)據(jù)有測量誤差。觀測數(shù)據(jù)除測量誤差外是可靠的。2. 波在傳播過程中沿直線單向傳播，且不考慮波的反射、折射以及干涉等現(xiàn)象。3.空氣密度和介質密度都均勻 優(yōu)優(yōu) 化化 建建 模模4.“彈性波”在傳播過程中沒有能量損失。其波速僅與介質有關，且在同一均勻介質中波速不變。彈性波沿板邊緣的傳播速度與在介質中的傳播速度相同。5.假設平板可劃分化為網(wǎng)格，空洞定位于每個網(wǎng)格單元內,空洞大小大致相同. 優(yōu)優(yōu) 化化 建建 模模波線與網(wǎng)格交線長度的計算波線與網(wǎng)格交線長度的計算 (k

43、,l) ; 52120,; 711,40kjikjikjikjikbijkl，且或如果或如果記波源記波源Pi與接收器與接收器Qj 決定的決定的波線與每個單元（波線與每個單元（k，l）的交線長度為的交線長度為bijkl i=j 時時123456654321 優(yōu)優(yōu) 化化 建建 模模波線與網(wǎng)格交線長度的計算波線與網(wǎng)格交線長度的計算 PiQj 決定的直線方程：決定的直線方程：(j - i）y = 6(x-40(i-1) i=j 以外的情況以外的情況單元單元(k,l)左邊緣直線方程左邊緣直線方程 x = 40(k-1)波線與波線與單元單元(k,l)左邊緣左邊緣對應交點的對應交點的y坐標為坐標為 y1ij

44、kl = 240(k-i)/(j-i)， 其中其中 l-1 6(k-i)/(j-i) l (k,l) 優(yōu)優(yōu) 化化 建建 模模波線與網(wǎng)格交線長度的計算波線與網(wǎng)格交線長度的計算 PiQj 決定的直線方程：決定的直線方程：(j - i）y = 6(x-40(i-1) i=j 以外的情況以外的情況單元單元(k,l)右邊緣直線方程右邊緣直線方程 x = 40k波線與波線與單元單元(k,l)右邊緣右邊緣對應交點的對應交點的y坐標為坐標為 y2ijkl = 240(k+1-i)/(j-i)， 其中其中 l-1 6(k+1-i)/(j-i) l (k,l) 優(yōu)優(yōu) 化化 建建 模模波線與網(wǎng)格交線長度的計算波線與

45、網(wǎng)格交線長度的計算 PiQj 決定的直線方程：決定的直線方程：(j - i）y = 6(x-40(i-1) i=j 以外的情況以外的情況單元單元(k,l)下邊緣直線方程下邊緣直線方程 y = 40(l-1)波線與波線與單元單元(k,l)下邊緣下邊緣對應交點的對應交點的y坐標為坐標為 y3ijkl = 40(l-1)， 其中其中 0 6(i-k)-(i-j)(l-1) 6 (k,l) 優(yōu)優(yōu) 化化 建建 模模波線與網(wǎng)格交線長度的計算波線與網(wǎng)格交線長度的計算 PiQj 決定的直線方程：決定的直線方程：(j - i）y = 6(x-40(i-1) i=j 以外的情況以外的情況單元單元(k,l)上邊緣直

46、線方程上邊緣直線方程 y = 40l波線與波線與單元單元(k,l)上邊緣上邊緣對應交點的對應交點的y坐標為坐標為 y4ijkl = 40l， 其中其中 0 6(i-k)-(i-j)l 6 (k,l) 優(yōu)優(yōu) 化化 建建 模模波線與網(wǎng)格交線長度的計算波線與網(wǎng)格交線長度的計算 交線在交線在y軸的投影長度軸的投影長度(交點條件最多只有交點條件最多只有2個成立個成立)i=j 以外的情況以外的情況dyijkl= max(y1ijkl ,y2ijkl,y3ijkl,y4ijkl) - min(y1ijkl ,y2ijkl,y3ijkl,y4ijkl)由相似三角形關系由相似三角形關系QjABCDPiRiSjP

47、jdyijkl(k,l)bijklEFGbijkl = aij dyijkl / 240 240624022jiaiji=j 也成立也成立 優(yōu)優(yōu) 化化 建建 模模波線與網(wǎng)格交線長度的計算波線與網(wǎng)格交線長度的計算 由對稱性，由對稱性，RiSj與單元與單元(k,l)的交線長度的交線長度ci,j,k,l= bj,i,l,7-k 優(yōu)優(yōu) 化化 建建 模模參量、變量：參量、變量：xkl：單元：單元(k,l)是否為空洞是否為空洞(1：是；：是；0：否：否)aij：波源：波源Pi與接收器與接收器Qj （同樣，（同樣，Ri與與Sj）之間的距離）之間的距離pij經(jīng)過介質的長度經(jīng)過介質的長度, qij經(jīng)過空氣的長度

48、經(jīng)過空氣的長度tij (同樣同樣 ij): 傳播時間觀測值傳播時間觀測值優(yōu)化模型（擬合回歸）優(yōu)化模型（擬合回歸）71k,lklijklijijijijxbaqap71k,lklijklijxbq 優(yōu)優(yōu) 化化 建建 模模若沒有誤差：tij =pij /v1+qij/v2優(yōu)化模型（擬合回歸）優(yōu)化模型（擬合回歸）271171/vxbvxbatk,lklijklk,lklijklijij同理：271171/vxcvxcak,lklijklk,lklijklijij模型：22711712271171/minvxcvxcavxbvxbatk,lklijklk,lklijklijijk,lklijklk,l

49、klijklijij 優(yōu)優(yōu) 化化 建建 模模 三三 動態(tài)優(yōu)化模型動態(tài)優(yōu)化模型 (姜啟源等姜啟源等數(shù)學模型數(shù)學模型（第四版）第（第四版）第13章）章） 優(yōu)優(yōu) 化化 建建 模模 連續(xù)動態(tài)過程的優(yōu)化歸結為求泛函的極值連續(xù)動態(tài)過程的優(yōu)化歸結為求泛函的極值. 求泛函極值的常用方法求泛函極值的常用方法: 變分法、變分法、最優(yōu)控制論最優(yōu)控制論. 離散動態(tài)過程的優(yōu)化離散動態(tài)過程的優(yōu)化 動態(tài)規(guī)劃模型動態(tài)規(guī)劃模型.靜態(tài)優(yōu)化問題靜態(tài)優(yōu)化問題優(yōu)化目標是數(shù)值優(yōu)化目標是數(shù)值最優(yōu)策略是數(shù)值最優(yōu)策略是數(shù)值 函數(shù)對應的數(shù)值稱為泛函函數(shù)對應的數(shù)值稱為泛函(函數(shù)的函數(shù)函數(shù)的函數(shù)).動態(tài)優(yōu)化問題動態(tài)優(yōu)化問題優(yōu)化目標是數(shù)值優(yōu)化目標是數(shù)

50、值最優(yōu)策略是最優(yōu)策略是函數(shù)函數(shù) 優(yōu)優(yōu) 化化 建建 模模3.1 速降線與短程線速降線與短程線 通過兩個古典問題介紹變分法的基本概念通過兩個古典問題介紹變分法的基本概念, 給出主要結果給出主要結果. 速速降降線線問問題題 給定豎給定豎直直平面內不在一條垂直線上的兩個點平面內不在一條垂直線上的兩個點A, B, 求連接求連接A, B的光滑曲線，使質的光滑曲線，使質點在重力作用下沿該曲線以點在重力作用下沿該曲線以最最短時間短時間從從A滑到滑到B (摩擦力不計摩擦力不計). A. B若沿陡峭曲線下滑若沿陡峭曲線下滑, 雖路徑加長，但速度增長很快雖路徑加長，但速度增長很快.若沿直線段若沿直線段AB下滑下滑,

51、 路徑雖短路徑雖短, 但速度增長慢但速度增長慢; 優(yōu)優(yōu) 化化 建建 模模速速降降線線問問題題 . A. B建立坐標系建立坐標系xOy, xyy=y(x)O曲線弧長曲線弧長 2d1dsyx能量守恒能量守恒21d()2dsmmgyt質點在曲線質點在曲線y(x)上的速度上的速度ds/dt 21dd2ytxgy質點沿曲線質點沿曲線y(x)從從A到到B的時間的時間 1201( ( )d2xyJ y xxgy11)(, 0)0(yxyy求求y(x) 使使 J(y(x) 達到最小達到最小. m質點質量，質點質量，g重力加速度重力加速度 A(0,0), B(x1,y1), 曲線曲線AB y=y(x) 滿足條件

52、滿足條件 優(yōu)優(yōu) 化化 建建 模模短短程程線線問問題題 . A. Bxyzo給定曲面上的兩個點給定曲面上的兩個點A, B, 求曲面上連接求曲面上連接A, B的最短曲線的最短曲線. 建立坐標系建立坐標系 A(x0, y0, z0 ), B(x1, y1 , z1 )曲線的弧長曲線的弧長 22d1dsyzx曲線的長度曲線的長度 1022( ( ), ( )1dxxJ y x z xyzx求求y =y(x), z =z(x) 使使J(y(x) , z(x)達到最小達到最小. 0)(),(,(xzxyxf滿足條件滿足條件曲面方程曲面方程f(x,y,z)=0 f(x,y,z)=0曲面上連接曲面上連接A,

53、B的曲線的曲線 y =y(x), z =z(x) y =y(x) z =z(x) 優(yōu)優(yōu) 化化 建建 模模泛函、泛函的變分和極值泛函、泛函的變分和極值自變量自變量t，函數(shù)，函數(shù)x(t), y(t) 函數(shù)、函數(shù)的微分和極值函數(shù)、函數(shù)的微分和極值 泛函、泛函的變分和極值泛函、泛函的變分和極值 1. 對于對于t在某域的任一個值在某域的任一個值, 有有y的一個值與之對應的一個值與之對應, 稱稱y是是t的函數(shù)，記作的函數(shù)，記作y=f(t) 1.對于某函數(shù)集合的每一個函對于某函數(shù)集合的每一個函數(shù)數(shù)x(t), 有有J的一個值與之對應的一個值與之對應, 稱稱J是是x(t)的泛函的泛函, 記作記作J(x(t) 2

54、. t在在t0的增量記作的增量記作 t= t- t0, 微分微分dt= t 2. x(t)在在x0(t)的增量記作的增量記作 x(t)= x(t)-x0(t)， x(t)稱稱x(t)的變分的變分 3. y在在t0的增量記作的增量記作 f= f(t0+ t) - f(t0)， f的線性主部是函數(shù)的線性主部是函數(shù)的微分的微分, 記作記作dy，dy = f (t0)dt 3. 泛函泛函J(x(t)在在x0(t)的增量記的增量記作作 J = J(x0(t)+ x(t)- J(x0(t), J的線性主部稱的線性主部稱泛函的變分泛函的變分,記作記作 J(x0(t) 優(yōu)優(yōu) 化化 建建 模模泛函、泛函的變分和

55、極值泛函、泛函的變分和極值函數(shù)、函數(shù)的微分和極值函數(shù)、函數(shù)的微分和極值 泛函、泛函的變分和極值泛函、泛函的變分和極值 4. 若函數(shù)若函數(shù)y在域內在域內t點達到極點達到極值，則在值，則在t點的微分點的微分dy(t)=0 4. 若泛函若泛函J(x(t)在函數(shù)集合內的在函數(shù)集合內的x(t)達到極值達到極值, 則在則在x(t)的的變分變分 J(x(t)=0 0d ( )()y tf tt 5. y在在t的微分的另一表達式的微分的另一表達式5. 泛函泛函J(x(t)在在x(t)的變分可以表為的變分可以表為0)()()(txtxJtxJ泛函泛函J(x(t)在在x(t)達到極值的必要條件達到極值的必要條件

56、0)()(0txtxJ 優(yōu)優(yōu) 化化 建建 模模歐拉方程歐拉方程( (最簡泛函極值的必要條件最簡泛函極值的必要條件) )21( ( )( , ( ), ( )dttJ x tF t x tx tt最簡泛函最簡泛函F具有二階連續(xù)偏導數(shù)，具有二階連續(xù)偏導數(shù)，x(t)為二階可微函數(shù)為二階可微函數(shù) 固定端點條件下的泛函固定端點條件下的泛函 J(x(t)在在x(t)達到極值的必要條件達到極值的必要條件: x(t)滿足二階微分方程滿足二階微分方程d0dxxFFt0 xFxFFFxxxxx tx 2211)(,)(xtxxtx兩個任意常數(shù)由兩個任意常數(shù)由 確定確定 歐拉方程歐拉方程 優(yōu)優(yōu) 化化 建建 模模用歐

57、拉方程解速降線問題用歐拉方程解速降線問題0 xFxFFFxxxxx tx 11)(, 0) 0(yxyy1201( ( )d2xyJ y xxgy求求y(x) 使使 達到最小達到最小 , 且且歐拉方程歐拉方程yyyyF21),(0 yFyFFFyyyyyxyd()0dyFy FxcFyFycyyyyy)1 (122222/1)1 (cyy)cos1 ()sin(121tcycttcx圓滾線方程圓滾線方程 c2=0, c1由由y(x1)=y1確定確定. 優(yōu)優(yōu) 化化 建建 模模橫截條件橫截條件( (變動端點問題變動端點問題) )容許函數(shù)容許函數(shù) x(t)的一個端點固定的一個端點固定: x(t1)=

58、x1，另一個端點，另一個端點在給定曲線在給定曲線 x= (t) 上變動上變動: x(t2)= (t2) (t2可變可變).x(t). A. Bx= (t)txot2歐拉方程在歐拉方程在變動端點的定解條件變動端點的定解條件0)(2ttxFxF x= (t)垂直于橫軸垂直于橫軸 (t2固定固定)02 ttxF x= (t)平行于橫軸平行于橫軸02 ttxFxF 優(yōu)優(yōu) 化化 建建 模模包含多個未知函數(shù)泛函的歐拉方程包含多個未知函數(shù)泛函的歐拉方程21( ( ), ( )( , ( ), ( ), ( ), ( )dttJ x tu tF t x tx tu tu ttdd0,0ddxxuuFFFFtt

59、歐拉方程歐拉方程泛函的條件極值泛函的條件極值21( ( )( , ( ), ( )dttJ u tF t x tu tt)(),(,()(tutxtftx求求u(t) U (容許集合容許集合) 使使J(u(t)在條件在條件下達到極值下達到極值, 且且x(t) X (容許集合容許集合) 最優(yōu)控制問題最優(yōu)控制問題: u(t)控制函數(shù)控制函數(shù), x(t)狀態(tài)函數(shù)狀態(tài)函數(shù)(軌線軌線). 優(yōu)優(yōu) 化化 建建 模模泛函的條件極值泛函的條件極值21( ( )( , ( ), ( )dttJ u tF t x tu tt)(),(,()(tutxtftx用拉格朗日乘子化為無條件極值用拉格朗日乘子化為無條件極值2

60、1( ( ), ( )( , , )( )( , , )dttI x tu tF t x utf t x uxt),()(),(),(uxtftuxtFuxtH21()dttHxt歐拉方程歐拉方程d()()0dd()()0dxxuuHxHxtHxHxt00)(uHtxH),(0)(uxtfxuHxHt由方程組和端點條件解出最優(yōu)控制由方程組和端點條件解出最優(yōu)控制u(t)和最優(yōu)軌線和最優(yōu)軌線x(t).Hamilton函數(shù)函數(shù) 優(yōu)優(yōu) 化化 建建 模模3.2 生產(chǎn)計劃的制訂生產(chǎn)計劃的制訂問題問題 生產(chǎn)任務是在一定時間內提供一定數(shù)量的產(chǎn)品生產(chǎn)任務是在一定時間內提供一定數(shù)量的產(chǎn)品. 生產(chǎn)費用隨著生產(chǎn)率生產(chǎn)