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

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

------清·龔柴

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

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

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

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

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

稱為J的容許集。泛函最簡(jiǎn)形式

泛函極值

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

泛函增量

如果線性項(xiàng)＋高次項(xiàng)線性項(xiàng)就稱為泛函J的變分

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

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

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

對(duì)右端第二項(xiàng)做分部積分，

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

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

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

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

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

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

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

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

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

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

是y的函數(shù)，則最優(yōu)路徑的偏角取：若u,v

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

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

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

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

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

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

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

ReviewTechnique/CriticalPathMethod

）

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

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