1、優化模型v泛函優化模型v圖論優化模型v經典等周問題v搶渡長江v函數優化模型 12min max . . 0,1, 0,1, :,ijnf xst gximhxjmfDR DR函數最優化模型的標準形式函數最優化模型的標準形式LP,ILP,BILP,NLP,INLP,QP,IQP 1122min . . , , Tnf xc xst AxbA xbxDR線性規劃模型線性規劃模型(LP)的標準形式的標準形式 1122max . . , , Tnf xc xst AxbA xbxDRMATLAB命令：linprog, bintprog泛函優化模型泛函優化模型 公元前814年，腓尼基人泰爾泰爾（Tyer

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

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

4、重新興建規模宏大的城堡“奧倫治城”（Orange），1627年以荷蘭省名澤蘭省澤蘭省（或譯熱蘭省）改建命名為“熱蘭遮城”（Zeelandia）。v1662年，鄭成功攻下“熱蘭遮城”，順利將荷蘭人驅逐出臺灣，建立了臺灣歷史上第一個漢人政權。鄭氏同時也將該城改為“安平城”，這就是現今“安平古堡”這個名稱的由來。 - 安平古堡里的鄭成功像國家一級古跡 -安平古堡什么是變分法？v約翰伯努利（Johann Bernoulli，16671748）“最速降線”問題（The Brachistochrone Problem）v歐拉（Euler Lonhard，1707

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

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

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

8、( , ( )( ), ( )( ) ( , , )( , , )tttxxtdJJ x tx tddF t x tx tx tx tdtdF t x xxF t x xx dt歐拉方程推導歐拉方程推導 對右端第二項做分部積分，并利用 12( )( )0 x tx t利用泛函極值的變分表示，得210txxtdFFxdtdt12( )( )0 xx tx t任意，根據變分法的基本引理變分法的基本引理以及條件以及條件221121 ( , , )( , , ) ttxxtttxxtdF t x xxdtF t x xxdtdtdFFxdtdt歐拉方程可以推廣到含多個未知函數歐拉方程可以推廣到含多個未

9、知函數（可視為（可視為向量值函數向量值函數）的情況，如假設）的情況，如假設則其則其歐拉方程組歐拉方程組為為21121212( ),( )( ,( ),( ),( ),( )ttJ x tx tF t x tx tx tx t dt泛函極值泛函極值與與函數極值函數極值的比較的比較( ), ( ( )()( )( )xx tU xS JJ xxtttJ, ( )()( )fx Uf xxfxDx( )( )xx tx txxx ( )()JJ xJ x ( )( )ff xf x 0d()()dJ xJ xxd(),dff xx ()0J x( ) 0f xd0dxxFFtd0dxxRRtd ()

10、0f x0R TRFGTRfg駐留函數駐點泛函變分函數全微分極值函數極值函數極值點極值點等周問題（特殊條件極值問題）等周問題（特殊條件極值問題）v目標泛函目標泛函v約束條件（約束條件（等周條件等周條件）21, ,d()ttJG t x xtL L， 為常數(2),FC等周問題解法等周問題解法（條件極值問題轉化為無條件極值問題條件極值問題轉化為無條件極值問題）RFG設x(t)是等周問題（F,G）的極值函數，但不是約束條件泛函的駐留函數，則必存在常數 ，使得x(t)是Lagrange函數 對應的輔助泛函定理定理8.38.3的駐留函數。即經典等周問題經典等周問題v目標泛函目標泛函v約束條件（約束條件

11、（等周條件等周條件） 122,1122( ), ( )( ),( ),)( ),(t tx ty tx tSx ty txtyyCv容許函數集容許函數集21, , , ,dttJ x yF t x y x yt 221122ddttttttLGxy1222FxGxxyyyR作作Lagrange函數函數xyDDQP dxdyPdx Qdy對應的歐拉方程歐拉方程為 dd0,1,2jjxxtRRj2112,dttJ x ytxyxy對應的歐拉方程歐拉方程為 dd0,1,2jjxxtRRj2222d0dd0dxytxyyxtxy 022yxxxy 022xyyxy22200 xxyy2122dttxy

12、tL222002Lxxyy24LS泛函極（大）值為泛函極（大）值為用變分法證明偏角引理用變分法證明偏角引理)0,()(vtv設游泳者的速度而流速，其中 u 為常數, = (y)為游泳偏角。于是游泳者的路線 (x(t), y(t) 滿足(0)0, ( ),(0)0, ( )xx TLyy TH)sincos()(uutu，)(sin)()(cosyuyyvyux最優偏角的求法最優偏角的求法( (變分法變分法) )v目標泛函目標泛函v約束條件約束條件等周條件等周條件 0012,0,HSyCHv容許函數集容許函數集 0sn miinHdyTyuy1cossinsinvuRFGuu作作Lagrange

13、函數函數對應的歐拉方程為對應的歐拉方程為 0R0( )cossinHv yudyLu2cos(cos )0sinuvu即即( sec)1 uv+= -00( sec)1uv ()00(secsec)uvv-= -偏角引理偏角引理若若 u 為常數為常數, v 是是 y 的函數，則最優路徑的偏角取：的函數，則最優路徑的偏角取：( )( )()000cosarccoscosu yuv yv=-若若 u,v 為常數，則最優路徑的偏角始終不變！為常數，則最優路徑的偏角始終不變！()00(secsec)uvv-= -0最優路徑就是連接起點與終點的直線段！最優路徑就是連接起點與終點的直線段！ 0121211

14、120 0010 (,),( , ),( ,),;,.iinijiiiiiiPyPPL HijnHHSnSSSSv yvyyyiSvyyyyiSx水流速分布函數為水流速分布函數為n段常數、光滑函數間隔的模型段常數、光滑函數間隔的模型8.2最短路問題1、圖、圖 論論 的的 基基 本本 概概 念念2、最、最 短短 路路 問問 題題 及及 其其 算算 法法3、最、最 短短 路路 的的 應應 用用4、建模案例：調度問題、建模案例：調度問題5、實驗作業、實驗作業2、會用、會用LINGO、Matlab軟件求優化問題軟件求優化問題1、了解最短路問題與調度的算法及其應用、了解最短路問題與調度的算法及其應用圖圖

15、 論論 的的 基基 本本 概概 念念一、一、 圖圖 的的 概概 念念1、圖的定義、圖的定義2、頂點的度、頂點的度 3、子圖、子圖二、二、 圖圖 的的 矩矩 陣陣 表表 示示1、 關聯矩陣關聯矩陣2、 鄰接矩陣鄰接矩陣返回返回定義定義有序二元組G=(V,E )稱為一個圖圖.圖的定義圖的定義12,nVv vvV的元素為G的頂點，V稱為頂點集。EEG的元素為連接頂點的邊， 稱為 的邊集。( ) |( ) |GGVGGE記 的頂點數， 的邊數如果如果G G的邊有方向，則稱為圖的有向邊，否則稱為無向邊，的邊有方向，則稱為圖的有向邊，否則稱為無向邊，每條邊都是有向邊的圖稱為每條邊都是有向邊的圖稱為，每條邊

16、都是無向邊的，每條邊都是無向邊的圖稱為圖稱為，既有有向邊又有無向邊的圖稱為，既有有向邊又有無向邊的圖稱為。將圖的每一條邊都賦以一個數字，稱為該邊的將圖的每一條邊都賦以一個數字，稱為該邊的權權，每個邊，每個邊都賦權的圖稱為都賦權的圖稱為賦權圖賦權圖。1.端點相同的邊稱為環環2.若一對頂點之間有兩條以上的邊聯結，則這些邊稱為重邊重邊3.有邊聯結的兩個頂點稱為相鄰的頂點相鄰的頂點，有一個公共端點的邊稱為相鄰的邊相鄰的邊4.邊和它的端點稱為互相關聯互相關聯的5.既沒有環也沒有重邊的圖，稱為簡單圖簡單圖子圖子圖頂點的度頂點的度44dv5)(3)(2)(444vdvdvd(1)在在圖圖中，頂點中，頂點v關

17、聯的邊的數目關聯的邊的數目(環算兩次環算兩次)稱為稱為v的的度度，記為，記為d(v)。(2)在在有向圖有向圖中，以頂點中，以頂點v為起點的邊的數目稱為為起點的邊的數目稱為v的的出度出度，記為，記為d+(v), 以頂點以頂點v為終點的邊的數目稱為為終點的邊的數目稱為v的的入度入度，記為，記為d-(v)。鄰接矩陣鄰接矩陣注：假設圖為簡單圖12341234 0101101101011110vvvvvvAvv返回返回G,A=,ijv va對有向賦權圖其鄰接矩陣其中無向賦權圖的鄰接矩陣可類似定義無向賦權圖的鄰接矩陣可類似定義12341234 02720838057350vvvvvvAvv關聯矩陣關聯矩陣

18、注：假設圖為簡單圖返回返回()110ijijijijijMmvemveve 對有向圖，其關聯矩陣，其中：若 是 的起點若 是 的終點若 與 不關聯()1,10,0ijijijijGMmvemve 對無向圖 ，其關聯矩陣，其中：若 與 相關聯若 與 不關聯最最 短短 路路 問問 題題 及及 其其 算算 法法一、一、 基基 本本 概概 念念二、固二、固 定定 起起 點點 的的 最最 短短 路路返回返回基基 本本 概概 念念返回返回定義定義1.任意兩點均有路徑的圖稱為連通圖連通圖2.起點與終點重合的路徑稱為圈圈3.連通而無圈的圖稱為樹樹 4.若G的生成子圖T是樹，則T稱為G的生成樹生成樹。定義定義

19、設P(u,v)是賦權圖G中從u到v的路徑，則路徑上全體邊的權之和 稱為路徑P的權權最短路問題（最短路問題（SRP: Shortest Route Problem） 在賦權圖G中，從頂點u到頂點v的具有最小權的路，稱為u到v的最短路最短路最小生成樹問題最小生成樹問題(MSTP: Minimum Spanning Tree Problem) 在賦權圖G中，求權最小的生成樹。計劃評審技術計劃評審技術/關鍵路徑方法（關鍵路徑方法（PERT/CPM: Program Evaluation and Review Technique/Critical Path Method ） 在無回路有向賦權圖G中，從頂點u到頂點v的具有最大權的路，稱為u到v的 關鍵路徑關鍵路徑計劃評審方法和關鍵路徑法PERT/CPMv如下圖，某個項目由4個事件（邊）完成，每個事件需要一定時間（邊的權值）完成，并且每個事件都需要在一定的狀態（頂點）下才能開始，即要完成所有先行事件（所有進入該頂點的邊）。求完成這個項目的最短時間。v無回路有向賦權圖中的最長路徑：關鍵路徑。142312137100固固 定定 起起 點點 的的 最最 短短 路路（最短路的無后效性）（最短路的