數(shù)學建模與實驗課件ch8

1、 優(yōu)化模型 v泛函優(yōu)化模型 v圖論優(yōu)化模型 v經(jīng)典等周問題 v搶渡長江 v函數(shù)優(yōu)化模型 1 2 min max . . 0,1, 0,1, :, i j n f x st gxim hxjm fDR DR 函數(shù)最優(yōu)化模型的標準形式函數(shù)最優(yōu)化模型的標準形式 LP,ILP,BILP,NLP,INLP,QP,IQP 11 22 min . . , , T n f xc x st Axb A xb xDR 線性規(guī)劃模型線性規(guī)劃模型(LP)的標準形式的標準形式 11 22 max . . , , T n f xc x st Axb A xb xDR MATLAB命令：linprog, bintprog

2、泛函優(yōu)化模型泛函優(yōu)化模型 公元前814年，腓尼基人泰爾（Tyer）王國（位于現(xiàn)今黎巴嫩南部西南海岸）的 Dido公主因其兄庇格瑪里翁（Pygmalion）在國王死后，排斥公主而獨攬大權。為免遭 迫害，Dido帶著財寶與仆人飄洋過海，在突尼斯灣登陸。她向柏柏人部落首領馬西塔尼 求借一張牛皮之地棲身，得到應允；于是她便把一張牛皮切成一根根細條，然后把細牛 皮連在一起，在緊靠海邊的山丘上圍起一塊約3.15平方公里地皮，建起了迦太基城 （Carthage） 。 迦太基假想圖200B.C. 迦太基遺址. “牛皮圈地”之臺灣版 天啟四年八月，荷人請和。許 之，與互市，乃退澎湖，而東入臺灣。 先是，海澄人顏

3、思齊居臺灣，鄭芝龍附 之。既去，而荷人來，借地于土番，不 可，紿之曰，愿得地如牛皮，多金不 惜。許之，乃剪皮為縷，周圍里許，筑 熱蘭遮城以居，駐兵二千八百人，附近 土番多服焉。 -清龔柴 臺灣小志 熱蘭遮城(Zeelandia) 1625年簡圖 v1622年，荷屬東印度公司占領了澎湖，以之作為東亞貿易的轉口基地。1623年，荷蘭人在 “一鯤鯓”建立一座簡單的砦城，這就是安平古堡的前身。1624年，在與中國明朝的軍隊激 戰(zhàn)了八個月以后，荷蘭人和中國官方達成協(xié)議，同意把設置于澎湖的要塞和炮臺毀壞，而于 1624年轉移至臺灣島，中國則不干涉荷蘭對臺灣的占領。荷蘭人Martinus Sonck占臺以后

4、， 在原來的砦城舊城址上，重新興建規(guī)模宏大的城堡“奧倫治城”（Orange），1627年以荷蘭 省名澤蘭?。ɑ蜃g熱蘭?。└慕麨椤盁崽m遮城”（Zeelandia）。 v1662年，鄭成功攻下“熱蘭遮城”，順利將荷蘭人驅逐出臺灣，建立了臺灣歷史上第一個漢 人政權。鄭氏同時也將該城改為“安平城”，這就是現(xiàn)今“安平古堡”這個名稱的由來。 v - 安 平 古 堡 里 的 鄭 成 功 像 國家一級古跡 -安平古堡 什么是變分法？ v約翰伯努利（Johann Bernoulli，16671748） “最速降線”問題（The Brachistochrone P

5、roblem） v歐拉（Euler Lonhard，17071783）和拉格朗日(Lagrange, Joseph Louis，1736-1813)確立了變分學 v現(xiàn)實中很多現(xiàn)象可以表達為泛函極值問題，我們稱之為變分 問題。求解方法通常有兩種：古典變分法和最優(yōu)控制論。 變分法基本知識變分法基本知識 定定 義義 泛函泛函 設S 為一函數(shù)集合，若對于每個函數(shù) Stx)( 都有一個實數(shù) J 與之對應， 則稱 J 是定義在 S 上的泛函，記 為 ，S 稱為 J 的容許集。( ( )J x t 泛函最簡形式泛函最簡形式 泛函極值泛函極值 ( ), ( ( )()( )( )xx tU xS JJ xxt

6、ttJ 則稱泛函 J 在 有極小值（極大值）。( )x t 函數(shù)變分函數(shù)變分 ( )( )( )x tx tx t ( )( )( )JJ x tx tJ x t 泛函增量泛函增量 2 1 ( ( ), ,d t t J x tF t x xt 如果如果 線性項高次項 ( ( )( ( ),( )J x tL x tx t 線性項就稱為泛函線性項就稱為泛函 J 的變分的變分 泛函變分的一個重要形式是可以表示為對參數(shù)的導數(shù)： 極值與變分極值與變分 若泛函 J 在 取得極值，則( )x t 變分法的基本引理變分法的基本引理 1 21 2 2 1 2 , , 12 12 ( ),( ), ( )(

7、)0, ( ) ( )0 ( )0, , t tt t t t f tCg tCg tg t f t g t dtf ttt t ( ),( )( ),( )JL x tx th x tx t 泛函極值的必要條件泛函極值的必要條件 2 1 1122 ( ( )( , ( ), ( ) ( ), ( ) t t J x tF t x tx t dt x tx x tx (2) ,FC 容許函數(shù)集S取為滿足端點條件的二階可微函數(shù)集合。 則泛函 J 在 取極值的必要條件為 滿足歐拉方程( )x t( )x t 歐拉方程的解稱為泛函J的駐留函數(shù)，容許函數(shù)集S內的駐留函數(shù) 通常就是使泛函取極值的函數(shù)。

8、2 1 2 1 0 0 ( ( )( ) ( , ( )( ), ( )( ) ( , , )( , , ) t t t xx t d JJ x tx t d d F t x tx tx tx tdt d F t x xxF t x xx dt 歐拉方程推導歐拉方程推導 對右端第二項做分部積分， 并利用 12 ( )( )0 x tx t 利用泛函極值的變分表示，得 2 1 0 t xx t d FFxdt dt 12 ( )( )0 xx tx t任意， 根據(jù)變分法的基本引理以及條件 22 11 2 1 ( , , )( , , ) tt xx tt t xx t d F t x xxdtF

9、 t x xxdt dt d FFxdt dt 歐拉方程可以推廣到含多個未知函數(shù)歐拉方程可以推廣到含多個未知函數(shù) （可視為向量值函數(shù)）的情況，如假設（可視為向量值函數(shù)）的情況，如假設 則其歐拉方程組為則其歐拉方程組為 2 1 121212 ( ),( )( ,( ),( ),( ),( ) t t J x tx tF t x tx tx tx t dt 泛函極值與函數(shù)極值的比較泛函極值與函數(shù)極值的比較 ( ), ( ( )()( )( )xx tU xS JJ xxtttJ , ( )()( )fx Uf xxfxDx ( )( )xx tx t xxx ( )()JJ xJ x ( )( )

10、ff xf x 0 d ()() d J xJ xx d(),dff xx ()0J x ( ) 0f x d 0 d xx FF t d 0 d xx RR t d ()0f x 0R T RFG T Rfg 駐留函數(shù)駐點 泛函變分函數(shù)全微分 極值函數(shù)極值函數(shù)極值點極值點 等周問題（特殊條件極值問題）等周問題（特殊條件極值問題） v目標泛函目標泛函 v約束條件（等周條件）約束條件（等周條件） 2 1 , ,d() t t JG t x xtL L ， 為常數(shù) (2) ,FC 等周問題解法等周問題解法 （條件極值問題轉化為無條件極值問（條件極值問題轉化為無條件極值問 題）題） RFG 設x(t

11、)是等周問題（F,G）的極值函數(shù)，但不是約束 條件泛函的駐留函數(shù)，則必存在常數(shù) ，使得x(t) 是Lagrange函數(shù) 對應的輔助泛 函 定理定理8.38.3 的駐留函數(shù)。 0 xx d RR dt 即 經(jīng)典等周問題經(jīng)典等周問題 v目標泛函目標泛函 v約束條件（等周條件）約束條件（等周條件） 12 2 ,1122 ( ), ( )( ),( ),)( ),( t t x ty tx tSx ty txtyyCv容許函數(shù)集容許函數(shù)集 2 1 , , , ,d t t J x yF t x y x yt 22 11 22 dd tt tt ttLGxy 1 2 22 FxGxxyyyR 作作Lag

12、range函數(shù)函數(shù) xy D D QP dxdyPdx Qdy 對應的歐拉方程為 d d 0,1,2 jj xxt RRj 2 1 1 2 ,d t t J x ytxyxy 對應的歐拉方程為 d d 0,1,2 jj xxt RRj 22 22 d 0 d d 0 d x y t xy y x t xy 0 22 y xx xy 0 22 x yy xy 22 2 00 xxyy 2 1 22d t t xytL 2 22 00 2 L xxyy 2 4 L S 泛函極（大）值為泛函極（大）值為 用變分法證明偏角引理用變分法證明偏角引理 )0,()(vtv 設游泳者的速度 而流速 ，其中 u

13、 為常數(shù), = (y)為游泳偏角。 于是游泳者的路線 (x(t), y(t) 滿足 (0)0, ( ), (0)0, ( ) xx TL yy TH )sincos()(uutu， )(sin )()(cos yuy yvyux 最優(yōu)偏角的求法最優(yōu)偏角的求法( (變分法變分法) ) v目標泛函目標泛函 v約束條件約束條件 等周條件等周條件 001 2 , ,0, H SyCH v容許函數(shù)集容許函數(shù)集 0 s n mi in H dy Ty uy 1cos sinsin vu RFG uu 作作Lagrange函數(shù)函數(shù) 對應的歐拉方程為對應的歐拉方程為 0R 0 ( )cos sin H v y

14、u dyL u 2 cos(cos ) 0 sin uv u 即即 ( sec)1 uv+= - 00 ( sec)1uv () 00 (secsec)uvv-= - 偏角引理偏角引理 若若 u 為常數(shù)為常數(shù), v 是是 y 的函數(shù)，則最優(yōu)路徑的偏角?。旱暮瘮?shù)，則最優(yōu)路徑的偏角?。?( ) ( )() 0 00 cos arccos cos u y uv yv = - 若若 u,v 為常數(shù)，則最優(yōu)路徑的偏角始終不變！為常數(shù)，則最優(yōu)路徑的偏角始終不變！ () 00 (secsec)uvv-= - 0 最優(yōu)路徑就是連接起點與終點的直線段！最優(yōu)路徑就是連接起點與終點的直線段！ 0 ( ) ( )()

15、 00 arccos sec u y uv yv = - 2 00 00 cos sec yy u x yuv ydyv ydy uv yv 2 0 00 sec H u x Hv ydyL uv yv 0 1212 11 12 0 0 0 1 0 (,),( , ),( ,) , ,; ,. iin ij iii i i i PyPPL H ijnHH SnSSSS v yvyyyiS vyyyyiS x 水流速分布函數(shù)為水流速分布函數(shù)為n段常數(shù)、光滑函數(shù)間隔的模型段常數(shù)、光滑函數(shù)間隔的模型 8.2最短路問題 1、圖、圖 論論 的的 基基 本本 概概 念念 2、最、最 短短 路路 問問 題題

16、 及及 其其 算算 法法 3、最、最 短短 路路 的的 應應 用用 4、建模案例：調度問題、建模案例：調度問題 5、實驗作業(yè)、實驗作業(yè) 2、會用、會用LINGO、Matlab軟件求優(yōu)化問題軟件求優(yōu)化問題 1、了解最短路問題與調度的算法及其應用、了解最短路問題與調度的算法及其應用 圖圖 論論 的的 基基 本本 概概 念念 一、一、 圖圖 的的 概概 念念 1、圖的定義、圖的定義 2、頂點的度、頂點的度 3、子圖 二、二、 圖圖 的的 矩矩 陣陣 表表 示示 1、 關聯(lián)矩陣關聯(lián)矩陣 2、 鄰接矩陣鄰接矩陣 返回返回 定義定義有序二元組G=(V,E )稱為一個圖. 圖的定義圖的定義 12 , n V

17、v vvV的元素為的元素為G的頂點，的頂點，V稱為頂點集。稱為頂點集。 EEG的元素為連接頂點的邊， 稱為 的邊集。 ( ) |( ) |GGVGGE記 的頂點數(shù)， 的邊數(shù) 如果如果G G的邊有方向，則稱為圖的有向邊，否則稱為無向邊，的邊有方向，則稱為圖的有向邊，否則稱為無向邊， 每條邊都是有向邊的圖稱為有向圖，每條邊都是無向邊的每條邊都是有向邊的圖稱為有向圖，每條邊都是無向邊的 圖稱為無向圖，既有有向邊又有無向邊的圖稱為混合圖。圖稱為無向圖，既有有向邊又有無向邊的圖稱為混合圖。 將圖的每一條邊都賦以一個數(shù)字，稱為該邊的權，每個邊將圖的每一條邊都賦以一個數(shù)字，稱為該邊的權，每個邊 都賦權的圖稱

18、為賦權圖。都賦權的圖稱為賦權圖。 1.端點相同的邊稱為環(huán) 2.若一對頂點之間有兩條以上的邊聯(lián)結，則這些邊稱為重邊 3.有邊聯(lián)結的兩個頂點稱為相鄰的頂點，有一個公共端點的邊稱為相鄰的邊 4.邊和它的端點稱為互相關聯(lián)的 5.既沒有環(huán)也沒有重邊的圖，稱為簡單圖 子圖子圖 頂點的度頂點的度 4 4dv 5)( 3)( 2)( 4 4 4 vd vd vd (1)在圖中，頂點在圖中，頂點v關聯(lián)的邊的數(shù)目關聯(lián)的邊的數(shù)目(環(huán)算兩次環(huán)算兩次)稱為稱為v的度，記為的度，記為d(v)。 (2)在有向圖中，以頂點在有向圖中，以頂點v為起點的邊的數(shù)目稱為為起點的邊的數(shù)目稱為v的出度，記為的出度，記為 d+(v), 以

19、頂點以頂點v為終點的邊的數(shù)目稱為為終點的邊的數(shù)目稱為v的入度，記為的入度，記為d-(v)。 鄰接矩陣鄰接矩陣 注：假設圖為簡單圖 1234 1 2 3 4 0101 1011 0101 1110 vvvv v v A v v 返回返回 G,A=, ij v v a 對有向賦權圖其鄰接矩陣其中 無向賦權圖的鄰接矩陣可類似定義無向賦權圖的鄰接矩陣可類似定義 1234 1 2 3 4 027 2083 805 7350 vvvv v v A v v 關聯(lián)矩陣關聯(lián)矩陣 注：假設圖為簡單圖 返回返回 () 1 1 0 ij ij ijij ij Mm ve mve ve 對有向圖，其關聯(lián)矩陣，其中： 若

20、 是 的起點 若 是 的終點 若 與 不關聯(lián) () 1,1 0,0 ij ij ij ij GMm ve m ve 對無向圖 ，其關聯(lián)矩陣，其中： 若 與 相關聯(lián) 若 與 不關聯(lián) 最最 短短 路路 問問 題題 及及 其其 算算 法法 一、一、 基基 本本 概概 念念 二、固二、固 定定 起起 點點 的的 最最 短短 路路 返回返回 基基 本本 概概 念念 返回返回 定義定義1.任意兩點均有路徑的圖稱為連通圖任意兩點均有路徑的圖稱為連通圖 2.起點與終點重合的路徑稱為圈起點與終點重合的路徑稱為圈 3.連通而無圈的圖稱為樹連通而無圈的圖稱為樹 4.若若G的生成子圖的生成子圖T是樹，則是樹，則T稱為

21、稱為G 的生成樹。的生成樹。 定義定義 設設P(u,v)是賦權圖是賦權圖G中從中從u到到v的路徑，則路徑上的路徑，則路徑上 全體邊的權之和全體邊的權之和 稱為路徑稱為路徑P的權的權 最短路問題（最短路問題（SRP: Shortest Route Problem） 在賦權圖在賦權圖G中，從頂點中，從頂點u到頂點到頂點v的具有最小權的路，稱的具有最小權的路，稱 為為u到到v的最短路的最短路 最小生成樹問題最小生成樹問題(MSTP: Minimum Spanning Tree Problem) 在賦權圖在賦權圖G中，求權最小的生成樹。中，求權最小的生成樹。 計劃評審技術計劃評審技術/關鍵路徑方法（關

22、鍵路徑方法（PERT/CPM: Program Evaluation and Review Technique/Critical Path Method ） 在無回路有向賦權圖在無回路有向賦權圖G中，從頂點中，從頂點u到頂點到頂點v的具有最大權的具有最大權 的路，稱為的路，稱為u到到v的的 關鍵路徑關鍵路徑 計劃評審方法和關鍵路徑法 PERT/CPM v如下圖，某個項目由4個事件（邊）完成，每個事 件需要一定時間（邊的權值）完成，并且每個事件 都需要在一定的狀態(tài)（頂點）下才能開始，即要完 成所有先行事件（所有進入該頂點的邊）。求完成 這個項目的最短時間。 v無回路有向賦權圖中的最長路徑：關鍵路

23、徑。 1 4 2 3 12 13 7 100 固固 定定 起起 點點 的的 最最 短短 路路 （最短路的無后效性）最短路的任意一段也是最短路（最短路的無后效性）最短路的任意一段也是最短路 求指定頂點到其余頂點的最短路可采用樹生長的過程來實現(xiàn) 12112111kkkk Pu uuuuPu uuuu 若是從 到 的最短路，則必定是從 到的最短路 Dijkstra算法（計算從算法（計算從S到到T的最短路）的最短路） v（1）從點S出發(fā)，因LSS=0 ,將此值標注在S旁的小方 框內，表示S點已標號； v （2）從S點出發(fā)找出與S相鄰的點中距離最小的一個， 設為r，將 Lsr=Lss+dsr的值標注在r

24、的小方框內，表明 r也已標號； v （3）從已標號的的點出發(fā)，找出與這些點相鄰的所 有未標號點p，若有Lsp=minLss+dsp;Lsr+drp,則對 p點標號，并將Lsp的值標注在p點旁的小方框內； v （4）重復第3步，一直到T點得到標號為止. Dijkstra算法（標號法）演示算法（標號法）演示 Dijkstra算法（標號法）演示算法（標號法）演示 Dijkstra算法（標號法）演示算法（標號法）演示 Dijkstra算法（標號法）演示算法（標號法）演示 Dijkstra算法（標號法）演示算法（標號法）演示 最短路問題(SRP)的Lingo/Matlab解決方案 轉化為0-1整數(shù)規(guī)劃(

25、BILP) 引入0-1決策變量xij： 若邊eij在最短路上，則取值1，否則取值0 ij Pp 為鄰接矩陣 111dd 起點: 1dndn 終點: 0dndn 中間點: 問題：假設圖有問題：假設圖有n個頂點，求頂點個頂點，求頂點1到頂點到頂點n的最短路。的最短路。 解法解法 ,1 11 min 1,1 :1, 0,1, 0,1 n ijij i j nn ijji jj ij zp x i stxxin in x logO ee 最小生成樹的實現(xiàn)最小生成樹的實現(xiàn) 2 O n 欲建設一個連接欲建設一個連接5個城市的光纖通信網(wǎng)絡。各城市間線路的造個城市的光纖通信網(wǎng)絡。各城市間線路的造 價如圖所示，

26、求一個使總造價最少的線路建設方案。價如圖所示，求一個使總造價最少的線路建設方案。 例例 通信網(wǎng)絡的建設問題通信網(wǎng)絡的建設問題 解：采用解：采用Kruskal算法算法 解：采用解：采用Prim算法算法 欲建設一個連接欲建設一個連接6個城市的光纖通信網(wǎng)絡。各城市間線路的造個城市的光纖通信網(wǎng)絡。各城市間線路的造 價如圖所示，求一個使總造價最少的線路建設方案。價如圖所示，求一個使總造價最少的線路建設方案。 例例8.4通信網(wǎng)絡的建設問題通信網(wǎng)絡的建設問題 解：采用解：采用Prim算法算法 54 管梅谷（）。我國著名數(shù)學家，曾任山東師范大學校長。中 國運籌學會第一、二屆常務理事，第六屆全國政協(xié)委員。從事運

27、籌學及其應 用的研究，對最短投遞路線問題的研究取得成果 ，冠名為中國郵路問題，該 問題被列入經(jīng)典圖論教材和著作。 補充材料：管梅谷的破圈法 在克魯斯克爾算法基礎上，我國著名數(shù)學家管梅谷教授于1975年提出 了最小生成樹的破圈法。 破圈法求最小生成樹的求解過程是：從賦權圖G的任意圈開始，去掉該 圈中權值最大的一條邊，稱為破圈。不斷破圈，直到G中沒有圈為止，最后 剩下的G的子圖為G的最小生成樹。 55 3 1 2 2 3 4 3 6 6 7 10 解： 過程如下： 3 1 2 2 3 4 6 6 7 103 1 2 2 3 6 6 7 10 3 1 2 2 6 6 7 10 3 1 2 2 6 6

28、 7 3 1 2 2 6 6 3 1 2 2 3 4 3 6 6 7 9 10 例用破圈法求下圖G的最小生成樹。 ,1 1 1 1 min :1 1,1 0,1 n ijij i j n j j n ji j ij zp x stx xi x 1）根結點至少有一個子節(jié)點 2）除根外,每個點有且僅有 一個父節(jié)點 最小生成樹問題(MSTP)的Lingo/Matlab解決方案 轉化為0-1整數(shù)規(guī)劃(BILP) 引入0-1決策變量xij： 若邊eij在最小生成樹上，則取值1，否則取值0 問題：假設圖有問題：假設圖有n個頂點，設頂點個頂點，設頂點1為生成樹的根，求最為生成樹的根，求最 小生成樹。小生成樹。 解法解法 1 , min :, 0, n jiiji j i zSS stSSteE SiV 設1和n分別是最初和最終事件; Si是事件i的開始時間, tij是事件(i,j)的計劃（正常）時間。 問題：求最后一個事件的最早開始時間。問題：求最后一個事件的最早開始時間。 PERT/CPM的的Lingo/Matlab解決方案解決方案 轉化為線性規(guī)劃轉化為線性規(guī)劃(LP) 解法解法 l關鍵路徑也可以看成最長路，可用求最短路徑 l 的方