數(shù)模優(yōu)化問題

第8章優(yōu)化模型優(yōu)化模型泛函優(yōu)化模型圖論優(yōu)化模型經(jīng)典等周問題搶渡長江函數(shù)優(yōu)化模型函數(shù)最優(yōu)化模型的標準形式LP,ILP,BILP,NLP,INLP,QP,IQP線性規(guī)劃模型(LP)的標準形式MATLAB命令：linprog,bintprog泛函優(yōu)化模型Dido傳奇公元前814年，腓尼基人泰爾（Tyer）王國（位于現(xiàn)今黎巴嫩南部西南海岸）的Dido公主因其兄庇格瑪里翁（Pygmalion）在國王死后，排斥公主而獨攬大權(quán)。為免遭迫害，Dido帶著財寶與仆人飄洋過海，在突尼斯灣登陸。她向柏柏人部落首領(lǐng)馬西塔尼求借一張牛皮之地棲身，得到應(yīng)允；于是她便把一張牛皮切成一根根細條，然后把細牛皮連在一起，在緊靠海邊的山丘上圍起一塊約3.15平方公里地皮，建起了迦太基城（Carthage）。迦太基假想圖200B.C.迦太基遺址.“牛皮圈地”之臺灣版天啟四年八月，荷人請和。許之，與互市，乃退澎湖，而東入臺灣。先是，海澄人顏思齊居臺灣，鄭芝龍附之。既去，而荷人來，借地于土番，不可，紿之曰，愿得地如牛皮，多金不惜。許之，乃剪皮為縷，周圍里許，筑熱蘭遮城以居，駐兵二千八百人，附近土番多服焉。

------清·龔柴

《臺灣小志》熱蘭遮城(Zeelandia)

1625年簡圖1622年，荷屬東印度公司占領(lǐng)了澎湖，以之作為東亞貿(mào)易的轉(zhuǎn)口基地。1623年，荷蘭人在“一鯤鯓”建立一座簡單的砦城，這就是安平古堡的前身。1624年，在與中國明朝的軍隊激戰(zhàn)了八個月以后，荷蘭人和中國官方達成協(xié)議，同意把設(shè)置于澎湖的要塞和炮臺毀壞，而于1624年轉(zhuǎn)移至臺灣島，中國則不干涉荷蘭對臺灣的占領(lǐng)。荷蘭人MartinusSonck占臺以后，在原來的砦城舊城址上，重新興建規(guī)模宏大的城堡“奧倫治城”（Orange），1627年以荷蘭省名澤蘭?。ɑ蜃g熱蘭省）改建命名為“熱蘭遮城”（Zeelandia）。1662年，鄭成功攻下“熱蘭遮城”，順利將荷蘭人驅(qū)逐出臺灣，建立了臺灣歷史上第一個漢人政權(quán)。鄭氏同時也將該城改為“安平城”，這就是現(xiàn)今“安平古堡”這個名稱的由來。-------------安平古堡里的鄭成功像國家一級古跡-----安平古堡什么是變分法？約翰·伯努利（JohannBernoulli，1667－1748）

“最速降線”問題（TheBrachistochroneProblem）歐拉（EulerLonhard，1707～1783）和拉格朗日(Lagrange,JosephLouis，1736-1813)確立了變分學現(xiàn)實中很多現(xiàn)象可以表達為泛函極值問題，我們稱之為變分問題。求解方法通常有兩種：古典變分法和最優(yōu)控制論。變分法基本知識定義泛函設(shè)S為一函數(shù)集合，若對于每個函數(shù)都有一個實數(shù)J

與之對應(yīng)，則稱J

是定義在S上的泛函，記為，S

稱為J的容許集。泛函最簡形式

泛函極值

則稱泛函J在有極小值（極大值）。函數(shù)變分

泛函增量

如果線性項＋高次項線性項就稱為泛函J的變分

泛函變分的一個重要形式是可以表示為對參數(shù)的導(dǎo)數(shù)：極值與變分

若泛函J在取得極值，則變分法的基本引理

泛函極值的必要條件容許函數(shù)集S取為滿足端點條件的二階可微函數(shù)集合。則泛函J在取極值的必要條件為滿足歐拉方程歐拉方程的解稱為泛函J的駐留函數(shù)，容許函數(shù)集S內(nèi)的駐留函數(shù)通常就是使泛函取極值的函數(shù)。歐拉方程推導(dǎo)

對右端第二項做分部積分，

并利用利用泛函極值的變分表示，得根據(jù)變分法的基本引理以及條件歐拉方程可以推廣到含多個未知函數(shù)

（可視為向量值函數(shù)）的情況，如假設(shè)則其歐拉方程組為泛函極值與函數(shù)極值的比較泛函函數(shù)極值點自變量增量因變量增量因變量增量的線性主部取極值的必要條件無條件極值的必要條件輔助函數(shù)條件極值的必要條件駐留函數(shù)駐點泛函變分函數(shù)全微分極值函數(shù)極值點等周問題（特殊條件極值問題）目標泛函約束條件（等周條件）等周問題解法

（條件極值問題轉(zhuǎn)化為無條件極值問題）設(shè)x(t)是等周問題（F,G）的極值函數(shù)，但不是約束條件泛函的駐留函數(shù)，則必存在常數(shù)，使得x(t)是Lagrange函數(shù)對應(yīng)的輔助泛函定理8.3的駐留函數(shù)。即經(jīng)典等周問題目標泛函約束條件（等周條件）容許函數(shù)集邊界條件作Lagrange函數(shù)對應(yīng)的歐拉方程為

對應(yīng)的歐拉方程為

泛函極（大）值為駐留函數(shù)對應(yīng)曲線為圓極值函數(shù)對應(yīng)曲線用變分法證明偏角引理設(shè)游泳者的速度而流速，其中

u為常數(shù),=(y)為游泳偏角。于是游泳者的路線

(x(t),y(t))滿足求最優(yōu)路線

(x(t),y(t))等價于求最優(yōu)偏角策略，可以化為等周問題最優(yōu)偏角的求法(變分法)目標泛函約束條件

等周條件容許函數(shù)集作Lagrange函數(shù)對應(yīng)的歐拉方程為

即駐留函數(shù)偏角引理若u為常數(shù),v

是y的函數(shù)，則最優(yōu)路徑的偏角?。喝魎,v

為常數(shù)，則最優(yōu)路徑的偏角始終不變！最優(yōu)路徑就是連接起點與終點的直線段！水流速分布函數(shù)為n段常數(shù)、光滑函數(shù)間隔的模型8.2最短路問題1、圖論的基本概念2、最短路問題及其算法3、最短路的應(yīng)用4、建模案例：調(diào)度問題5、實驗作業(yè)2、會用LINGO、Matlab軟件求優(yōu)化問題1、了解最短路問題與調(diào)度的算法及其應(yīng)用圖論的基本概念一、圖的概念1、圖的定義2、頂點的度

3、子圖二、圖的矩陣表示1、關(guān)聯(lián)矩陣2、鄰接矩陣返回定義有序二元組G=(V,E)稱為一個圖.圖的定義V的元素為G的頂點，V稱為頂點集。如果G的邊有方向，則稱為圖的有向邊，否則稱為無向邊，每條邊都是有向邊的圖稱為有向圖，每條邊都是無向邊的圖稱為無向圖，既有有向邊又有無向邊的圖稱為混合圖。將圖的每一條邊都賦以一個數(shù)字，稱為該邊的權(quán)，每個邊都賦權(quán)的圖稱為賦權(quán)圖。1.端點相同的邊稱為環(huán)．2.若一對頂點之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為重邊．3.有邊聯(lián)結(jié)的兩個頂點稱為相鄰的頂點，有一個公共端點的邊稱為相鄰的邊．4.邊和它的端點稱為互相關(guān)聯(lián)的．5.既沒有環(huán)也沒有重邊的圖，稱為簡單圖．圖的有關(guān)概念子圖頂點的度(1)在圖中，頂點v關(guān)聯(lián)的邊的數(shù)目(環(huán)算兩次)稱為v的度，記為d(v)。(2)在有向圖中，以頂點v為起點的邊的數(shù)目稱為v的出度，記為d+(v),

以頂點v為終點的邊的數(shù)目稱為v的入度，記為d-(v)。鄰接矩陣注：假設(shè)圖為簡單圖返回無向賦權(quán)圖的鄰接矩陣可類似定義．關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖返回最短路問題及其算法一、基本概念二、固定起點的最短路返回基本概念返回定義２1.任意兩點均有路徑的圖稱為連通圖．2.起點與終點重合的路徑稱為圈．3.連通而無圈的圖稱為樹．

4.若G的生成子圖T是樹，則T稱為G的生成樹。定義３設(shè)P(u,v)是賦權(quán)圖G中從u到v的路徑，則路徑上全體邊的權(quán)之和

稱為路徑P的權(quán)．最短路問題（SRP:ShortestRouteProblem）

在賦權(quán)圖G中，從頂點u到頂點v的具有最小權(quán)的路，稱為u到v的最短路．最小生成樹問題(MSTP:MinimumSpanningTreeProblem)

在賦權(quán)圖G中，求權(quán)最小的生成樹。計劃評審技術(shù)/關(guān)鍵路徑方法（PERT/CPM:ProgramEvaluationand

ReviewTechnique/CriticalPathMethod

）

在無回路有向賦權(quán)圖G中，從頂點u到頂點v的具有最大權(quán)的路，稱為u到v的

關(guān)鍵路徑．計劃評審方法和關(guān)鍵路徑法PERT/CPM如下圖，某個項目由4個事件（邊）完成，每個事件需要一定時間（邊的權(quán)值）完成，并且每個事件都需要在一定的狀態(tài)（頂點）下才能開始，即要完成所有先行事件（所有進入該頂點的邊）。求完成這個項目的最短時間。無回路有向賦權(quán)圖中的最長路徑：關(guān)鍵路徑。142312137100固定起點的最短路（最短路的無后效性）最短路的任一段也是最短路．求指定頂點到其余頂點的最短路可采用樹生長的過程來實現(xiàn)．Dijkstra算法（計算從S到T的最短路）（1）從點S出發(fā)，因LSS=0,將此值標注在S旁的小方框內(nèi)，表示S點已標號；（2）從S點出發(fā)找出與S相鄰的點中距離最小的一個，設(shè)為r，將Lsr=Lss+dsr的值標注在r的小方框內(nèi)，表明r也已標號；（3）從已標號的的點出發(fā)，找出與這些點相鄰的所有未標號點p，若有Lsp=min｛Lss+dsp;Lsr+drp｝,則對p點標號，并將Lsp的值標注在p點旁的小方框內(nèi)；（4）重復(fù)第3步，一直到T點得到標