《現(xiàn)代優(yōu)化技術(shù)-靳志宏》第2講：現(xiàn)代優(yōu)化技術(shù)基礎(chǔ)之?dāng)?shù)學(xué)基礎(chǔ)

現(xiàn)代優(yōu)化技術(shù)第2講：現(xiàn)代優(yōu)化技術(shù)基礎(chǔ)之?dāng)?shù)學(xué)基礎(chǔ)編輯ppt第2講：主要內(nèi)容高等數(shù)學(xué)基礎(chǔ)運(yùn)籌學(xué)基礎(chǔ)高等數(shù)學(xué)基礎(chǔ)

集合、排列與組合

凸集、凸函數(shù)

凸組合、凸規(guī)劃……運(yùn)籌學(xué)基礎(chǔ)

窮舉法、分枝定界法、

動態(tài)規(guī)劃法、……編輯ppt高等數(shù)學(xué)基礎(chǔ)基本概念編輯ppt高等數(shù)學(xué)基礎(chǔ)基本概念編輯ppt高等數(shù)學(xué)基礎(chǔ)基本概念編輯ppt高等數(shù)學(xué)基礎(chǔ)基本概念凸組合凸組合性質(zhì)編輯ppt高等數(shù)學(xué)基礎(chǔ)基本概念編輯ppt高等數(shù)學(xué)基礎(chǔ)基本概念編輯ppt高等數(shù)學(xué)基礎(chǔ)基本概念編輯ppt高等數(shù)學(xué)基礎(chǔ)基本性質(zhì)編輯ppt高等數(shù)學(xué)基礎(chǔ)基本性質(zhì)編輯ppt高等數(shù)學(xué)基礎(chǔ)基本概念編輯ppt高等數(shù)學(xué)基礎(chǔ)基本性質(zhì)編輯ppt高等數(shù)學(xué)基礎(chǔ)基本性質(zhì)凸規(guī)劃例：凸可行域編輯ppt高等數(shù)學(xué)基礎(chǔ)基本性質(zhì)凸規(guī)劃例：凸目標(biāo)函數(shù)編輯ppt高等數(shù)學(xué)基礎(chǔ)基本性質(zhì)編輯ppt高等數(shù)學(xué)基礎(chǔ)基本概念非凸規(guī)劃編輯ppt高等數(shù)學(xué)基礎(chǔ)基本性質(zhì)非凸規(guī)劃編輯ppt高等數(shù)學(xué)基礎(chǔ)基本性質(zhì)非凸規(guī)劃編輯ppt高等數(shù)學(xué)基礎(chǔ)基本性質(zhì)非凸規(guī)劃編輯ppt運(yùn)籌學(xué)基礎(chǔ)

運(yùn)籌學(xué)的方法論基礎(chǔ)：窮舉法（完全枚舉法、列舉樹法）分枝定界法（分支限定法、B&B法）動態(tài)規(guī)劃法、……編輯ppt運(yùn)籌學(xué)基礎(chǔ)列舉樹法：現(xiàn)實(shí)中的問題例：旅行商問題（歐洲7日游）現(xiàn)在的位置：瑞士的蘇黎士下一步要觀光去的地方：西班牙的馬德里；英國的倫敦；意大利的羅馬；德國的柏林。目的地：返回蘇黎士．問題：以怎樣的順序觀光，旅行的總距離最短？編輯ppt運(yùn)籌學(xué)基礎(chǔ)列舉樹法：現(xiàn)實(shí)中的問題各都市間的距離（miles）B7848527741154434894736408569476LZMR編輯ppt列舉樹法：現(xiàn)實(shí)中的問題運(yùn)籌學(xué)基礎(chǔ)BRLRBBLRLBRLBLRMBRMRBBMRMBRMBBRLBLMLBBMLMBLMBMLRRLMLRRMLMRLMRMLBZ304730473407348534853596329734973407382540343256329737844034367438253584329736743784349732563596旅行商問題的列舉樹編輯ppt列舉樹法：現(xiàn)實(shí)中的問題運(yùn)籌學(xué)基礎(chǔ)Zurich(Z)Rome(R)Madrid(M)London(L)Berlin(B)434+852+784+569+408巡回路＝可行解=3047目標(biāo)函數(shù)值總距離最小的旅行路線＝最優(yōu)巡回路（最優(yōu)解）最優(yōu)解（之一）編輯ppt列舉樹法：理論升華運(yùn)籌學(xué)基礎(chǔ)編輯ppt列舉樹法：理論升華運(yùn)籌學(xué)基礎(chǔ)編輯ppt列舉樹法：理論升華運(yùn)籌學(xué)基礎(chǔ)資金預(yù)算問題的列舉樹編輯ppt列舉樹法：理論升華運(yùn)籌學(xué)基礎(chǔ)資金預(yù)算問題的列舉樹編輯ppt分枝定界法：現(xiàn)實(shí)中的問題運(yùn)籌學(xué)基礎(chǔ)例：背包問題制約條件：背包的容量目標(biāo)函數(shù)：背走盡可能高價(jià)值的東西編輯ppt分枝定界法：現(xiàn)實(shí)中的問題運(yùn)籌學(xué)基礎(chǔ)分枝定界法:

不是生成所有可能的分枝,僅僅取其中的一部分

探索效率高分枝操作（branch）：基本上與列舉樹的生成操作相同．限定操作（bound）：對列舉樹上的某點(diǎn)以后沒有必要再進(jìn)行探索

判斷依據(jù)：探索時(shí)點(diǎn)的目標(biāo)函數(shù)的上下界值編輯ppt分枝定界法：現(xiàn)實(shí)中的問題運(yùn)籌學(xué)基礎(chǔ)分枝操作：黒點(diǎn)表示背包無法容納（非可行解）每一步都分兩種情形考慮背走極小熊

放棄極小熊背走小熊背走中熊背走大熊決策點(diǎn)

放棄小熊

放棄中熊

放棄大熊編輯ppt分枝定界法：現(xiàn)實(shí)中的問題運(yùn)籌學(xué)基礎(chǔ)定界操作：上界與下界值的利用下界值及其作用：因?yàn)楸嘲鼏栴}是極大值問題，任一可行解都是其下界值．

（例如，僅僅背走小熊時(shí)背包完全可以容納,因而是可行解．小熊的價(jià)值為19萬元,故其現(xiàn)時(shí)點(diǎn)的下界為19）．上界值及其作用:

有必要導(dǎo)入背包問題的松弛問題編輯ppt分枝定界法：現(xiàn)實(shí)中的問題運(yùn)籌學(xué)基礎(chǔ)背包問題的松弛問題：取而代之為線性制約（線性松弛）線性松弛問題的最優(yōu)解可能不是整數(shù)．＜可以解釋為將物品分解后背走也行＞背包問題的線性松弛問題可以用貪婪算法求得最優(yōu)解．（即根據(jù)単位重量的價(jià)值vi/si大小順序裝包）編輯ppt分枝定界法：現(xiàn)實(shí)中的問題運(yùn)籌學(xué)基礎(chǔ)線性松弛問題的最優(yōu)解=

背包問題的上界值単位重量的價(jià)值86.3335.755.6

xi110.50以此順序裝包最優(yōu)値=16+19+23/2=46.5編輯ppt分枝定界法：現(xiàn)實(shí)中的問題運(yùn)籌學(xué)基礎(chǔ)分枝定界法的探索原理：如某一探索時(shí)點(diǎn)的上界（如放棄極小熊時(shí)為42萬）小于某一個(gè)可行解（背走大熊和極小熊時(shí)的44萬）時(shí)，從該點(diǎn)以后沒有必要再探索下去.編輯ppt分枝定界法：現(xiàn)實(shí)中的問題運(yùn)籌學(xué)基礎(chǔ)分枝定界法的探索效率：2.取決于分枝方法（分枝原則）

例如，以熊的重量從小到大的順序分枝．

其他的分枝方法有:以熊的重量從大到小的順序;以熊的價(jià)值從大到小的順序;以（價(jià)值÷重量）從大到小的順序．取決于下界及上界的強(qiáng)度

->松弛問題的上界（最小化問題是下界）

->近似解法所取得的下界（最小化問題是上界）

的及早獲取3.取決于分枝點(diǎn)的選取順序(分枝子問題優(yōu)先原則)

如從具有較大上界的點(diǎn)開始分枝（該點(diǎn)下存在較好解的可能性大）編輯ppt分枝定界法：理論升華運(yùn)籌學(xué)基礎(chǔ)編輯ppt分枝定界法：理論升華運(yùn)籌學(xué)基礎(chǔ)編輯ppt分枝定界法：理論升華運(yùn)籌學(xué)基礎(chǔ)編輯ppt分枝定界法：理論升華運(yùn)籌學(xué)基礎(chǔ)編輯ppt分枝定界法：理論升華運(yùn)籌學(xué)基礎(chǔ)編輯ppt分枝定界法：理論升華運(yùn)籌學(xué)基礎(chǔ)編輯ppt分枝定界法：理論升華運(yùn)籌學(xué)基礎(chǔ)編輯ppt分枝定界法：理論升華運(yùn)籌學(xué)基礎(chǔ)編輯ppt分枝定界法：理論升華運(yùn)籌學(xué)基礎(chǔ)編輯ppt分枝定界法：理論升華運(yùn)籌學(xué)基礎(chǔ)分枝定界法總結(jié)：編輯ppt動態(tài)規(guī)劃法：現(xiàn)實(shí)中的問題運(yùn)籌學(xué)基礎(chǔ)小熊有4種每種有大量庫存．滿足背包的重量制約條件的前提下，帶走盡可能高價(jià)值的物品！編輯ppt動態(tài)規(guī)劃法：現(xiàn)實(shí)問題運(yùn)籌學(xué)基礎(chǔ)背包的重量上限θ，使θ分別以0,1,…,7的順序計(jì)算．物品的種類集合N={極小，小，中，大}物品種類i的重量

si，其價(jià)值vi重量上限為θ時(shí)的最優(yōu)値

（現(xiàn)時(shí)點(diǎn)背包內(nèi)價(jià)值的合計(jì)）f

(θ)對于函數(shù)f(θ)，以下的等式成立（Bellman方程式）重量上限θ的最優(yōu)値上限為θーsi時(shí)的最優(yōu)値物品i的價(jià)值編輯ppt動態(tài)規(guī)劃法：現(xiàn)實(shí)中的問題運(yùn)籌學(xué)基礎(chǔ)整數(shù)背包問題的動態(tài)規(guī)劃法編輯ppt動態(tài)規(guī)劃法：現(xiàn)實(shí)中的問題運(yùn)籌學(xué)基礎(chǔ)最優(yōu)解的最短路圖各點(diǎn)表示可能的θ值的狀態(tài)．

某一狀態(tài)（點(diǎn)）和別的狀態(tài)（點(diǎn)）之間的連線為枝枝上的數(shù)字表示狀態(tài)之間變化所增加的背包內(nèi)物品的價(jià)值．下圖為狀態(tài)從0至7的最短路圖解．編輯ppt動態(tài)規(guī)劃法：現(xiàn)實(shí)中的問題運(yùn)籌學(xué)基礎(chǔ)僅以背包的重量θ來表現(xiàn)狀態(tài)有缺陷:內(nèi)裝的物品種類及數(shù)量無法表現(xiàn)！內(nèi)裝的物品1..k種時(shí)的最優(yōu)値f(k,θ)

Bellman方程式內(nèi)裝物品為k個(gè),

且

重量上限θ時(shí)的最優(yōu)値