高級(jí)運(yùn)籌學(xué)課件--非線性

運(yùn)籌學(xué)的學(xué)科背景從狹義到廣義的管理科學(xué)狹義的管理科學(xué)指：用科學(xué)的方法，特別是定量（運(yùn)籌學(xué)）分析的方法來解決管理問題；廣義的管理科學(xué)指：有關(guān)管理的學(xué)科或?qū)W科體系管理學(xué)科分類1201管理科學(xué)與工程1202工商管理1203農(nóng)林經(jīng)濟(jì)管理1204公共管理1205

館、

與管理管理科學(xué)與工程學(xué)科簡介管理科學(xué)與工程是綜合運(yùn)用系統(tǒng)科學(xué)、管理科學(xué)、數(shù)學(xué)、經(jīng)濟(jì)和行為科學(xué)及工程方法，結(jié)合研究解決社會(huì)、經(jīng)濟(jì)、工程等方面的管理問題的一門交叉學(xué)科。1996年設(shè)立，是管理門類的一級(jí)學(xué)科，與工商管理同,1998年開始授予博士

點(diǎn)。當(dāng)時(shí)設(shè)四個(gè)二級(jí)學(xué)科：管理科學(xué)、工業(yè)工程、金融工程、工程管理。2012年有新的調(diào)整。1998年第一批授予管理科學(xué)與工程學(xué)科博士點(diǎn)的學(xué)校，大多是從原有的“系統(tǒng)工程”學(xué)科轉(zhuǎn)變而來，多是工科院校。管理科學(xué)與工程學(xué)科簡介管理科學(xué)與工程學(xué)科背景下的本科專業(yè)一般有（不同的學(xué)校設(shè)立在不同院系）–信息管理與信息工程–管理科學(xué)–工業(yè)工程–工程管理–物流管理–電子商務(wù)–。。。。。。。管理科學(xué)與工程學(xué)科簡介國外相近的系科Industrial

engineeringIndustrial

and

system

engineeringOperations

researchInformation

system

&

operation

managementManagement

science……斯坦福大學(xué)有Management

Science

&Engineering運(yùn)籌學(xué)會(huì)與雜志中國運(yùn)籌學(xué)學(xué)會(huì)(ORSC)The

Operations

Research

Society

of

China–雜志:<運(yùn)籌學(xué)學(xué)報(bào)>,<運(yùn)籌與管理>運(yùn)籌與管理學(xué)會(huì)(IFORMS)Institute

forOperations

Research

andthe

ManagementSciences

(IFORMS)：ManagementScienceOperationsResearchINFORMS

Journal

onComputingInterfacesDecision

ysisManufacturing

&

Service

Operations

ManagementMarketingScienceMathematics

of

Operations

ResearchInformation

Systems

ResearchanizationScienceTransportation

Science運(yùn)籌與管理學(xué)會(huì)11本期刊Best

jobs

of

2014:

It’s

good

to

be

an

ystUSNews

and

World

Report

just

released

its“BestJobs

of2014,”

andthe

top-100

list

was

loadedwith ystsand ytically

inclinedoccupations,

including

marketresearch

yst(No.

15)and

operations

research yst

(No.23).

Inthe

category

of“Best

Business

Jobs,”market

research yst

and

operations

researchyst

ranked

No.

1

and

No.

2,respectfully.運(yùn)籌學(xué)概述運(yùn)籌學(xué)的研究對(duì)象是各種系統(tǒng)；運(yùn)籌學(xué)的研究目的是實(shí)現(xiàn)系統(tǒng)的最優(yōu)化，求得合理利用各種資源的最優(yōu)方案；運(yùn)籌學(xué)的研究方法是運(yùn)用數(shù)學(xué)語言來描述實(shí)際系統(tǒng)，通過建立數(shù)學(xué)模型和優(yōu)化技術(shù)求得系統(tǒng)運(yùn)營的最優(yōu)解；運(yùn)籌學(xué)的研究

是為決策者提供科學(xué)決策的依據(jù)。最優(yōu)化方法的應(yīng)用金融和最優(yōu)化金融數(shù)學(xué)已成為一個(gè)熱門研究課題。而金融數(shù)學(xué)的一個(gè)重要方面是與優(yōu)化理論及算法相聯(lián)系的。經(jīng)濟(jì)學(xué)獎(jiǎng)得主提出組合選擇的均值--方差模型(MV模型)便是一個(gè)二次規(guī)劃問題。這個(gè)模型使得 組合選擇方法實(shí)現(xiàn)了從定性描述到定量描述質(zhì)的飛躍,使得人們可以更加科學(xué)地分析與選擇投資策略。物流網(wǎng)絡(luò)的設(shè)計(jì)優(yōu)化隨著我國物流業(yè)的快速發(fā)展，不同類型的物流系統(tǒng)的設(shè)計(jì)，物流園區(qū)的設(shè)計(jì)有很大的實(shí)際需求。這些系統(tǒng)設(shè)計(jì)中有很多優(yōu)化問題，比如：–多個(gè)倉庫位置的選定，–倉庫容量的確定，– 方式和 工具的選擇，–車輛路徑的規(guī)劃(VRP,

Vehicle Route

Problem)–。。。。。供應(yīng)鏈中的多級(jí)

系統(tǒng)的運(yùn)行優(yōu)化供應(yīng)鏈的運(yùn)行中也有很多優(yōu)化的問題–分銷網(wǎng)絡(luò)中的多級(jí)庫存系統(tǒng)的庫存補(bǔ)充計(jì)劃–安全庫存的分級(jí)配置優(yōu)化–考慮缺貨或事故情況的處理–順應(yīng)價(jià)格波動(dòng)的 計(jì)劃–車輛 計(jì)劃和路徑優(yōu)化–。。。。。。港口集裝箱調(diào)度的優(yōu)化現(xiàn)代化港口和鐵路集裝箱中心站的集裝箱中有很多的優(yōu)化問題。比如：–船舶的泊次計(jì)劃–集裝箱的裝/卸載計(jì)劃–堆場的空間計(jì)劃–車輛的作業(yè)計(jì)劃–貨場的堆放計(jì)劃–碼頭起重機(jī)的調(diào)度計(jì)劃,等等制造系統(tǒng)的生產(chǎn)計(jì)劃與調(diào)度優(yōu)化制造系統(tǒng)的生產(chǎn)計(jì)劃與調(diào)度經(jīng)典的數(shù)學(xué)規(guī)劃方法有很多的成功案例。但是，這類系統(tǒng)當(dāng)考慮到細(xì)節(jié)時(shí)，比如求解車間作業(yè)調(diào)度問題JSP（Job-shop

problem）時(shí)，一旦考慮托盤的調(diào)度，裝設(shè)時(shí)間和運(yùn)輸時(shí)間等等，問題將遠(yuǎn)比一般的經(jīng)典JSP更為復(fù)雜。定量分析的過程定性分析–定量分析的前奏應(yīng)當(dāng)是一個(gè)充分的定性分析表達(dá)問題–列出表達(dá)問題的基本要素：決策變量、不可控量、限制條件等；建立模型–列出表達(dá)這些要 間關(guān)系的數(shù)學(xué)方程式求解模型與分析–運(yùn)用算法求解所構(gòu)建的模型得到最佳方案或滿意方案–對(duì)輸入數(shù)據(jù)和模型結(jié)構(gòu)作靈敏度分析執(zhí)行決定或修改模型–在實(shí)際應(yīng)用過程中不斷完善模型建立模型的重要性建立模型是運(yùn)籌學(xué)方法的精髓–建立模型有助于把決策問題所遇到的復(fù)雜性和可能的不確定性，轉(zhuǎn)變?yōu)檫m于綜合分析的邏輯結(jié)構(gòu)；–模型是一種媒介，借以認(rèn)識(shí)現(xiàn)實(shí)世界。模型是現(xiàn)實(shí)的近似表達(dá)，要能抓住決策問題的關(guān)鍵，在真實(shí)性和可用性之間取得適當(dāng)?shù)钠胶?。例：城市交通系統(tǒng)建?；締栴}：如果已知了起訖點(diǎn)之間的流量，道路網(wǎng)絡(luò)上的流量是如何分布的？–路徑如何選擇？（暢通，擁擠）例：城市交通系統(tǒng)建模路段阻抗函數(shù)BPR

(Bureau

of

PublicRoads)Function:0xt(x)

t

(1

(

)

)c例：城市交通系統(tǒng)建模Wardrop用戶均衡原理：–在道路網(wǎng)絡(luò)擁擠的情形下，在所有實(shí)際使用的路徑上出行成本相等，且小于任何未使用路徑上的出行成本油庫和

地理分布油品配送路線一次配送二次配送22油品供應(yīng)鏈原油供應(yīng)商煉油廠油庫工業(yè)客戶/潤滑油廠社會(huì)客戶分油庫工業(yè)客戶中國石油上海銷售公司地區(qū)嘉興地區(qū)蘇州地區(qū)湖州地區(qū)17個(gè)油庫，300個(gè)，1000多個(gè)固定大客戶，分4個(gè)銷售區(qū)域2003年銷售和柴油200

萬噸，物流成本近1

億元迫切需要解決的決策問題油品配送決策支持系統(tǒng)決策戰(zhàn)術(shù)決策銷售區(qū)域劃分油品供應(yīng)分配新建油庫選址新建油庫規(guī)模日配送調(diào)度多艙位油車調(diào)度跨區(qū)域集中調(diào)度緊急調(diào)度……供應(yīng)鏈問題油品配送決策系統(tǒng)結(jié)構(gòu)與特點(diǎn)先進(jìn)的信息和控制技術(shù)Web、液位儀、GIS大規(guī)模、復(fù)雜的OR問題巨大數(shù)量的數(shù)據(jù)處理實(shí)時(shí)決策和人機(jī)交互系統(tǒng)要求與特點(diǎn)油品配送決策系統(tǒng)日配送調(diào)度計(jì)劃油品供應(yīng)分配油庫選址物流信息系統(tǒng)GIS系統(tǒng)Internet油庫車隊(duì)液位儀車站1油庫2油庫1車站21#車輛的配送路線2#車輛的配送路線油品配送路線示意圖配送調(diào)度模型(超大型混合整數(shù)規(guī)劃)N1

車站集

N2

油庫集

N3

:V

車輛集

K:

油品,集:βvjkαvk:

車輛v的g

最大裝載油品種數(shù)v

:

車輛v的p

最佳運(yùn)載量v

:

車輛v的q

最大裝載量321{(

Nj}i)i,,j|,

AN集,:

)(Nj3,k

K否0

則

油1

站對(duì)油品kj有最佳配送量要求,否0

則

車1

輛v可

油品

,

KV,kvk

定義網(wǎng)絡(luò)配送調(diào)度模型1次配送經(jīng)配

1車輛v

能行駛行駛

r,vV,rR0

否則εvr

2

,

l

5i,

rR,iNriδl3

,5lrjγl2，kKd

jkj,kejk,f

1

路線rl第

次配送經(jīng)過油庫

,jrR,jN0

否則路線rl第0

否則R

:可行路線集)(:第j個(gè)油站對(duì)油品k的(最,,)

小

最佳

最大

需求量，jN

3,k

Ksiik

:油庫的最大供應(yīng)量,iN定義網(wǎng)絡(luò)30萬條可行路線配送調(diào)度模型zlvrjkzlvrjkyl

1vrkxvr

1

車輛v

走路線r

在第l

次配送時(shí)為

j

配送油品k

的量,v

V,

r

R,j

N3,

k

K,

l

5

車輛v

走路線r

在第l

次配送時(shí)從油庫i

裝載油品k

的量,v

V,

r

R,j

N2

,

k

K,

l

5車輛v

走路線r,v

V,

r

R0

否則車輛v

走路線r

在第l

次配送時(shí)有油品

k,

v

V,

r

R,

k

K,

l

50

否則決策變量配送調(diào)度模型l

vrjkvvkKlvrjkjkjkkKlz

a

p

vVb

c

zzckK

,l

5vV

,rRl

5

r

lvrjkrRl

5rR

,

jN3jN3vV

,

jN3目標(biāo)函數(shù)成本未達(dá)最佳配送量的懲罰未達(dá)最佳運(yùn)載量的懲罰配送調(diào)度模型

x

,

v

V,

r

R,

k

K,

l

5δvrylvrkiN2lriylvrkvk0

yl

αvrkkK

yl

g

,

v

V,

r

R,

l

5vrk

v

xvr

1,

v

VrR0

xvr

εvr

,

v

V,

r

R每車至多行駛一條可行路線車輛對(duì)路線的限制車輛對(duì)配送油品種數(shù)的限制車輛裝載油品限制約束條件配送調(diào)度模型(超大型混合整數(shù)規(guī)劃)233,

v

V,

r

R,

k

K,

l

5r

R,

j

N

,

l

5v

V,

l

5z

q

,i

N

,

k

Kz

s

,z

z

,

v

V,

r

R,

k

K,

l

5j

N

,

k

K,

l

5z

f

,d

Mylvrkzlvrjk

Mγl

,rjzlvrjkkKjN3l

vrjk

vvV

,rRl5l

vrik

ikjN3iN2

l

lvrik

vrjkvV

,rRl5ljk

vrjk

jk約束條件需求約束供需平衡供應(yīng)約束車輛裝載限制配送調(diào)度的人機(jī)交互界面路線鎖定/按鈕解的序列表示區(qū)備注區(qū)點(diǎn)重新定位按鈕待重新定位點(diǎn)列表解的矢圖表示區(qū)油庫列表油庫出油臨時(shí)限制縮放功能系統(tǒng)效果該系統(tǒng)完全改變了公司傳統(tǒng)的調(diào)度管理方式，顯著提高了配送調(diào)度的響應(yīng)速度、決策的正確性和科學(xué)性，適應(yīng)公司的扁平化管理的目標(biāo)。承運(yùn)商配送決策系統(tǒng)提貨單/發(fā)貨憑證油庫液位儀業(yè)務(wù)接口管理主管公司管理系統(tǒng)提貨單Internet設(shè)備接口管理發(fā)貨憑證系統(tǒng)效果通過使用該系統(tǒng)，銷售公司的物流在產(chǎn)品資源分布、產(chǎn)品庫存、

成本、

車輛、

和管理人工等五個(gè)方面得到了改善，節(jié)省成本。根據(jù)該公司財(cái)務(wù)部估計(jì)，該系統(tǒng)可使該公司全年的物流成本下降

1000余萬元

，節(jié)省物流成本10%

以上。各種散裝品的配送調(diào)度油品配送決策系統(tǒng)各種業(yè)態(tài)的實(shí)時(shí)配送調(diào)度第物流、郵政、快遞的配送調(diào)度配送決策系統(tǒng)應(yīng)用推廣大型連鎖超市的配送調(diào)度家電、乳品等專業(yè)銷售的配送調(diào)度可視化集成式油品銷售物流決策系統(tǒng)運(yùn)籌學(xué)主要分支數(shù)學(xué)規(guī)劃√–線性規(guī)劃–非線性規(guī)劃–整數(shù)規(guī)劃

√–動(dòng)態(tài)規(guī)劃

√圖與網(wǎng)絡(luò)流√網(wǎng)絡(luò)計(jì)劃√庫存論排隊(duì)論對(duì)策論決策論。。。。。本課程的主要內(nèi)容非線性規(guī)劃（一維無約束極值問題）決策論博弈論排隊(duì)論庫存論本課程成績構(gòu)成平時(shí)30%+期末考試70%平時(shí)成績=到課率+作業(yè)+或創(chuàng)新項(xiàng)目期末考試:閉卷筆試非線性規(guī)劃問題一般數(shù)學(xué)描述目標(biāo)函數(shù)或約束函數(shù)中至少有一個(gè)是非線性的應(yīng)用背景–有著最廣泛的應(yīng)用，應(yīng)該說所有現(xiàn)實(shí)問題都是非線性的，線性模型都是經(jīng)過簡化而來的。機(jī)械、電子等行業(yè)的器件最優(yōu)設(shè)計(jì)問題，如飛行器的結(jié)構(gòu)優(yōu)化設(shè)計(jì)等；管理科學(xué)中的應(yīng)用問題更是不勝枚舉；系統(tǒng)控制問題。nn..,(

21,...,,(

21,i...,,(

21,j...,0)

2,1..,

mi0)

2,1..,

lj決策論（decision

theory)“決策”一詞本身可以是一個(gè)廣義的概念，著名

有一句名言：“管理就是決策”。本課程介紹的是針對(duì)在不確定或隨機(jī)環(huán)境下的決策分析方法，是狹義的概念。應(yīng)用背景：產(chǎn)品開發(fā)決策問題、風(fēng)險(xiǎn)投資決策問題等等博弈論（Game

Theory)嘀嘀打車PK快的打車從起，嘀嘀打車與

支付發(fā)起“立減/獎(jiǎng)10元”。從2月10日開始，嘀嘀打車結(jié)束了支付返現(xiàn)10元的，降為5元。但是2月17日零時(shí)起，嘀嘀打車與

支付合作開始第三輪，將

支付返現(xiàn)漲回到10元。隨即下午起，阿里巴巴宣布快的打車方案，2月18日起，用快的打車和支付寶付款，每單立減11元。還宣稱

比同行多1元。博弈論博弈論研究的問題是：當(dāng)一個(gè)主體，如一個(gè)人或一個(gè)企業(yè)的選擇，受到其他人、其他企業(yè)選擇的影響，而且反過來又影響到其他人、其他企業(yè)選擇時(shí)的決策問題和均衡問題。博棄論又稱為“對(duì)策論”.博弈論可以解釋一些經(jīng)濟(jì)和社會(huì)現(xiàn)象，比如價(jià)格戰(zhàn)、國家之間的軍備競賽、“劣幣逐良幣”等等現(xiàn)象,解決競爭環(huán)境下的決策問題。排隊(duì)論銀行、醫(yī)院、機(jī)場跑道、港口碼頭、理發(fā)店、通信設(shè)備、交通路口等等的排隊(duì)現(xiàn)象；排隊(duì)論是運(yùn)籌學(xué)的又一個(gè)分支，又叫做隨機(jī)服務(wù)系統(tǒng)理論。它的研究目的是要回答如何改進(jìn)服務(wù)機(jī)構(gòu)、或組織被服務(wù)的對(duì)象，使得某種指標(biāo)達(dá)到最優(yōu)的問題。比如一個(gè)港口應(yīng)該有多少個(gè)碼頭，一個(gè)工廠應(yīng)該有多少維修等。庫存論物品的現(xiàn)象是為了解決供應(yīng)（生產(chǎn)）與需求（消費(fèi)）之間的不協(xié)調(diào)的一種措施；由此帶來一些需要決策的問題：庫存量、進(jìn)貨量（如報(bào)童問題）、補(bǔ)貨的時(shí)間等等決策量。庫存問題也一直是供應(yīng)鏈管理研究中的熱點(diǎn)問題。非線性規(guī)劃Nonlinear

Programming1.1相關(guān)的數(shù)學(xué)知識(shí)一、一般數(shù)學(xué)描述nn..,(

21,...,,(

21,i...,,(

21,j...,0)

2,1..,

mi0)

2,1..,

lj可行域

ni

|

{()0,()0;1,2

j

RXEh,.g..m,

X;i1Xlj

,...,

}特別當(dāng)R=En,稱為無約束優(yōu)化問題1.1相關(guān)的數(shù)學(xué)知識(shí)二、解的定義全局最優(yōu)解、嚴(yán)格全局最優(yōu)解

局部最優(yōu)解（極值點(diǎn)、極小點(diǎn)）三、多元函數(shù)的偏導(dǎo)偏導(dǎo)數(shù)：指函數(shù)沿某個(gè)坐標(biāo)軸方向的變化率；梯度：由各個(gè)坐標(biāo)軸方向組成的向量；方向?qū)?shù)：指函數(shù)沿某個(gè)給定方向的變化率；特例：給定一個(gè)點(diǎn)x0，沿著一個(gè)給定的方向P0變化的函數(shù)f(x0+tP0).1.1相關(guān)的數(shù)學(xué)知識(shí)四、Hessian

矩陣（二階導(dǎo)數(shù)矩陣）f(x0+tP0)的二階導(dǎo)數(shù)五、正定矩陣定義正定二次函數(shù)六、多元函數(shù)的Taylor展開1.1相關(guān)的數(shù)學(xué)知識(shí)七、凸函數(shù)、凸規(guī)劃凸集(convex

set)：凸函數(shù)(convex)、凹函數(shù)(concave)：定義幾何意義性質(zhì)判別條件特別：線性函數(shù)既是凸函數(shù)也是凹函數(shù)凸規(guī)劃(convex

programming)如何求解無約束優(yōu)化問題？NP)( ,(

21,...,Exn1.2無約束問題解的最優(yōu)性條件一階必要條件在極值點(diǎn)的梯度=0二階充分條件二階導(dǎo)數(shù)矩陣為正定矩陣特別，對(duì)于凸規(guī)劃，最優(yōu)解的充分必要條件是其梯度等于零。1.3下降搜索算法算法：給定一個(gè)初始點(diǎn)X0，然后按照一定的規(guī)則產(chǎn)生一個(gè)點(diǎn)列{Xk}，這種產(chǎn)生點(diǎn)列的規(guī)則稱為算法；下降算法的規(guī)則：給定一個(gè)初始點(diǎn)X0

，在點(diǎn)Xk選擇一個(gè)方向

(向量)Pk,并沿此方向選擇一點(diǎn)Xk+1=Xk+tkPk使得f(Xk+1)<f(Xk)。X0P0P1X1X2P2P3X3X*X41.3下降搜索算法算法步驟中的關(guān)鍵要素：初始點(diǎn)；確定尋優(yōu)方向；確定一個(gè)步長；算法終止條件下降搜索算法(向量)下降算法的規(guī)則：–給定一個(gè)初始點(diǎn)X0

，在點(diǎn)Xk選擇一個(gè)方向

Pk,并沿此方向選擇一點(diǎn)Xk+1=Xk+tkPk使得

f(Xk+1)<f(Xk)。不同的尋優(yōu)方向選擇方法構(gòu)成不同的算法；有兩類方法：解析法——利用函數(shù)的梯度來構(gòu)造尋優(yōu)方向；直接法——利用函數(shù)值來構(gòu)造尋優(yōu)方向；1.3下降搜索算法目標(biāo)函數(shù)的等值線（二維，等高線）對(duì)二次函數(shù)，等值線是一族同心的橢圓；對(duì)于非二次函數(shù)，在極小點(diǎn)附近，等值線近似一族同心橢圓；具有不同值的等值線不相交；等值線稠 目標(biāo)函數(shù)變化快，稀疏處變化慢；等值線上一點(diǎn)的梯度與該點(diǎn)的的等值線切線方向相互垂直。X0P0P1X1X2P2P3X3X*X41.4

一維尋優(yōu)方法The

One-Dimensional

SearchProcedure優(yōu)選法他數(shù)學(xué)家解析數(shù)論、典型群、矩陣幾何學(xué)、自守函數(shù)論與多復(fù)變函數(shù)論等很多方面研究的創(chuàng)始人與開拓者。也是國內(nèi)運(yùn)籌學(xué)研究和應(yīng)用的開拓者，是優(yōu)選法的倡導(dǎo)者。優(yōu)選法是快速尋找最佳方案的科學(xué)方法。具體的優(yōu)選法有很多，如黃金分割法、分?jǐn)?shù)法、對(duì)分法等。如在煉鋼時(shí)需加入某種元素來增加鋼材強(qiáng)度，若將試驗(yàn)點(diǎn)取在這一元素用量區(qū)間的0.618處，獲得理想用量的試驗(yàn)次數(shù)將大大減少。實(shí)驗(yàn)證明，對(duì)一個(gè)因素的優(yōu)化問題，用優(yōu)選法做16次試驗(yàn)，就可達(dá)到“對(duì)分法”做2000余次試驗(yàn)的效果。一、“成功-失敗”法基本思想“成功”則大步向前，“失敗”則小步后退框圖特點(diǎn)簡單易行，對(duì)初始點(diǎn)選擇無嚴(yán)格限制；適用于不可微的函數(shù)；在極小點(diǎn)附近收斂慢；可用此方法來確定一個(gè)搜索區(qū)間。二、

法（切

）基本思想：–適合二階連續(xù)可微的函數(shù)，求導(dǎo)數(shù)為0的方程根。迭代公式算法步驟特點(diǎn)適用于二階可微函數(shù)；最快的收斂速度，二階收斂速度；初始點(diǎn)要求接近極小點(diǎn)；可與“成功-失敗”法聯(lián)合使用。序貫實(shí)驗(yàn)法單峰函數(shù)（Unimodal

Function,下單峰、單谷)定義（在極小點(diǎn)左邊單調(diào)下降，右邊單調(diào)上升）性質(zhì)(Unimodality，單峰性)基本思想：通過選擇實(shí)驗(yàn)點(diǎn)，計(jì)算其函數(shù)值，比較實(shí)驗(yàn)點(diǎn)的函數(shù)值大小，縮小包含極值點(diǎn)的區(qū)間二分搜索法The

Dichotomy

Method

without

Derivatives基本思想–對(duì)稱取點(diǎn)，等比例縮小區(qū)間特點(diǎn)：簡單對(duì)稱取點(diǎn)，不論取哪個(gè)區(qū)間，其長度相等；每次要計(jì)算兩次函數(shù)值黃金分割法（0.618法)b0a01t

11t

2b1a1The

Golden

SectionSear

ethod基本思想：–對(duì)稱取點(diǎn)，等比例的縮小區(qū)間，除第一次外，每次只需計(jì)算一次函數(shù)值，可使區(qū)間縮小。f(t

1)<f(t

2)1

1t21

t22黃金分割法（0.618法)ethodThe

Golden

SectionSear實(shí)驗(yàn)點(diǎn)的計(jì)算公式算法步驟特點(diǎn)：具有相同的區(qū)間縮短率0.618；精度不如Fobonacci分?jǐn)?shù)法；–適用于不可微、不連續(xù)函數(shù)，可以先用“成功-失敗”法搜索到一個(gè)包含極小點(diǎn)的區(qū)間。Fibonacci分?jǐn)?shù)法The

Fibonacci

Sear

ethod問題：–如何選擇實(shí)驗(yàn)點(diǎn)，計(jì)算n次函數(shù)值能得到多大的區(qū)間縮短率？–換句話說，計(jì)算n次函數(shù)值能將多大的區(qū)間縮短到1。答案：–若對(duì)稱取點(diǎn)，利用上次已有的實(shí)驗(yàn)點(diǎn)的函數(shù)值，計(jì)算n次函數(shù)值可獲得1/Fn區(qū)間縮短率。Fibonacci分?jǐn)?shù)法Fibonacci

數(shù)列(Fibonacci

Sequence)F0=1,

F1=1,

F2=2,

F3=3,

F4=5,……Fk=Fk-1+Fk-2實(shí)驗(yàn)點(diǎn)的計(jì)算公式計(jì)算步驟算例Fibonacci

分?jǐn)?shù)法特點(diǎn)：–需要預(yù)先確定迭代次數(shù)n;–在計(jì)算n次函數(shù)值情況下，該方法獲得最大的區(qū)間縮短率，精度最高；–適用于不可微、不連續(xù)函數(shù)。作業(yè)P196,

6.12,

6.13,

6.141.5無約束尋優(yōu)算法簡介The

Multi-Dimensional

SearchProcedure最速下降法（梯度法）The

Steepest

descent

methodThe

Gradient

Method基本思想：以負(fù)梯度方向作為尋優(yōu)方向算法步驟：特點(diǎn)：–迭代過程簡單，

量少，計(jì)算量小；–即使是正定二次函數(shù)也不能有限步收斂；–相鄰兩次尋優(yōu)方向是垂直的;–尋優(yōu)路線呈鋸齒狀（Zig-Zag)，在極小點(diǎn)附近收斂緩慢;X0P0P1X1X2P2P3X3X*X4其他解析算法共軛梯度法(Conjugate

gradient

method)法（Newton’s

method)變尺度法（Variable

Metric

Method)（擬

法Quasi-Newton

method）有約束優(yōu)化問題的算法解的最優(yōu)性條件Karush-Kuhn-Tucker

條件求解算法直接法：可行方向法，梯度投影法等間接法：將有約束問題轉(zhuǎn)換成一系列的無約束問題來求解，如懲罰函數(shù)法，乘子法等1.6

最優(yōu)化技術(shù)的新發(fā)展最優(yōu)化技術(shù)的發(fā)展1940s－1970s：數(shù)學(xué)規(guī)劃階段——目標(biāo)和約束是解析函數(shù)；1970s—2000s：智能優(yōu)化階段——目標(biāo)和約束可以放寬為含有判斷邏輯的計(jì)算機(jī)程序；2000s—未來：基于仿真優(yōu)化階段——用大量仿真的統(tǒng)計(jì)數(shù)據(jù)來進(jìn)行性能評(píng)價(jià)。最優(yōu)化技術(shù)的基本步驟搜索：在定義域內(nèi)尋找最優(yōu)解；評(píng)估：按照問題的目標(biāo)對(duì)解的質(zhì)量進(jìn)行評(píng)價(jià)；選擇：對(duì)獲得的解進(jìn)行比較，判斷，選擇。對(duì)于迭代算法還要判斷終止條件。數(shù)學(xué)規(guī)劃方法數(shù)學(xué)規(guī)劃---線性規(guī)劃，非線性規(guī)劃，動(dòng)態(tài)規(guī)劃，……數(shù)學(xué)規(guī)劃的基本步驟—三步曲–

選一個(gè)初始解；①LP:大M，二階段法②NLP:任意點(diǎn)或一個(gè)內(nèi)點(diǎn)數(shù)學(xué)規(guī)劃方法（2）停止判據(jù)——停止規(guī)則最優(yōu)性檢驗(yàn)；當(dāng)∏≥0時(shí)有可能減小–

NLP:B

N

CT

B

1

N

CT–

LP:檢驗(yàn)數(shù)A

B

|

N

TB

NC

C

|

Cf

(x)

0數(shù)學(xué)規(guī)劃方法（3）向改進(jìn)方向移動(dòng)——改進(jìn)解LP:

轉(zhuǎn)軸變換(進(jìn)基、退基)NLP:

向負(fù)梯度方向移動(dòng)(共軛梯度方向、

方向)數(shù)學(xué)規(guī)劃方法（4）停機(jī)啟動(dòng)Y停止準(zhǔn)則N選擇一個(gè)初始解評(píng)估解向改進(jìn)方向移動(dòng)評(píng)估解問題：解的評(píng)估呢？數(shù)學(xué)規(guī)劃方法（5）數(shù)學(xué)規(guī)劃方法的局限性對(duì)問題中目標(biāo)函數(shù)、約束函數(shù)有很高的要求——有顯式表達(dá)，線性、連續(xù)、可微，且高階可微;只從一個(gè)初始點(diǎn)出發(fā)，難以進(jìn)行并行、網(wǎng)絡(luò)計(jì)算，難以提高計(jì)算效率；最優(yōu)性達(dá)到的條件太苛刻——問題的目標(biāo)函數(shù)為凸函數(shù)，可行域?yàn)橥辜?；在非雙凸條件下，沒有跳出局部最優(yōu)解的能力。實(shí)際優(yōu)化問題往往不滿足雙凸條件智能優(yōu)化方法智能優(yōu)化方法的產(chǎn)生對(duì)問題的描述要寬松(目標(biāo)和約束函數(shù))——可以用一段程序來描述(程序中帶判斷、循環(huán))，函數(shù)可以非連續(xù)、非凸、非可微、非顯式；并不苛求最優(yōu)解——通常滿意解、理想解就可以了；計(jì)算快速、高效,可隨時(shí)終止(根據(jù)時(shí)間定解的質(zhì)量)。智能優(yōu)化方法（2）智能優(yōu)化方法的好多名字：ligentOptimization)ligentComputation)高級(jí)啟發(fā)式(Advanced

Heuristics)智能優(yōu)化(In計(jì)算智能(In進(jìn)化計(jì)算(Evolutionary

computation)軟計(jì)算(Soft

Computation)自然計(jì)算(Natural

Computation)智能優(yōu)化方法（3）智能優(yōu)化的主流算法：1975年Holland提出遺傳算法(Genetic

Algorithm)---

GA1977年Glover提