網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃

網(wǎng)

絡(luò)

優(yōu)

化

NetworkOptimization/netopt清華大學(xué)數(shù)學(xué)科學(xué)系謝金星辦公室：理科樓2266#（電話：62787812）Email:jxie@/~jxie/courses/netopt清華大學(xué)課號(hào)：70420133第4章動(dòng)態(tài)規(guī)劃(DynamicProgramming)倍便謙朱歡圖掌醇擒肉蘿葛備儀桂梁凍蘋嬸廢漣氈慘庶淋吊滾云輩柿涸剖網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃1動(dòng)態(tài)規(guī)劃問(wèn)題的例子例（續(xù)例1.2）最短路問(wèn)題

(ShortestPathProblem)許多網(wǎng)絡(luò)優(yōu)化問(wèn)題要用到動(dòng)態(tài)規(guī)劃技術(shù)ST特點(diǎn)：多階段決策-子決策仍然最優(yōu)-動(dòng)態(tài)規(guī)劃(DP)技術(shù)動(dòng)態(tài)規(guī)劃–R.E.Bellman(1950’s)恿瞬拾脆蚊群出輕練抱丑捷烯芬率辮誅箍砸蕉波卻教費(fèi)婚估肚擰唉樂(lè)自縛網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃2所謂決策(DecisionMaking)，就是人們?yōu)榱诉_(dá)到一定的目的，從若干個(gè)可能的策略(Policy)（如行動(dòng)、方案）中選取最好的策略的過(guò)程.一般來(lái)說(shuō)，一個(gè)決策模型包含三個(gè)最基本的因素：（1）自然狀態(tài)（或簡(jiǎn)稱狀態(tài),State）：這是指決策活動(dòng)中決策者無(wú)法控制的一些因素，即決策時(shí)客觀對(duì)象所具備的基本條件.狀態(tài)的集合稱為狀態(tài)集合或狀態(tài)空間.（2）策略：這是指決策活動(dòng)中決策者可以采取的行動(dòng)方案.策略的集合稱為策略集合或策略空間.（3）益損值：這是指決策活動(dòng)中決策者可以采取不同的策略，在不同的自然狀態(tài)下所獲得的收益或損失值.它是策略和狀態(tài)的函數(shù)，也是決策活動(dòng)的目標(biāo)和基礎(chǔ).

4.1.1多階段決策模型

戰(zhàn)略決策(高層決策)、戰(zhàn)術(shù)決策(中層決策)、操作決策(基本決策)單目標(biāo)決策、多目標(biāo)決策單階段決策（一次決策）、多階段決策確定型決策、非確定型決策或風(fēng)險(xiǎn)型決策（隨機(jī)決策、模糊決策）今幾使削禹剝含瘓余貫封日環(huán)揀撮和一游兒絢拙諒坑腕惟式揭弟虹丈猙鞋網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃3多階段決策過(guò)程多階段決策（Multi-StageDecisionMaking），是將決策問(wèn)題的全過(guò)程恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系的子過(guò)程（每個(gè)子過(guò)程為一個(gè)階段），以便按照一定的次序去求解.階段一般是根據(jù)時(shí)間和空間的自然特征來(lái)劃分，以便于問(wèn)題的求解為目的.描述階段的變量稱為階段變量，一般用k表示.從第k個(gè)階段開始點(diǎn)到全過(guò)程終點(diǎn)的過(guò)程稱為后部子過(guò)程，或k子過(guò)程.在多階段決策問(wèn)題中，狀態(tài)表示每個(gè)階段開始時(shí)所處的自然狀況或客觀條件.描述過(guò)程狀態(tài)的變量稱為狀態(tài)變量，一般用xk表示第k個(gè)階段的狀態(tài)變量.當(dāng)過(guò)程處于某個(gè)階段的某個(gè)狀態(tài)時(shí)，從該狀態(tài)演變?yōu)橄乱粋€(gè)階段某狀態(tài)的選擇，稱為決策（抉擇，Decision）.描述決策的變量稱為決策變量，一般用uk表示第k個(gè)階段的決策變量，而用Uk(xk)表示第k個(gè)階段xk狀態(tài)下的所有允許決策的集合.樸疊詭耳殉舔焊惰納嘗代道蹈蓋著腸木像厘聲珍廬瀉勁遣孕殃擺漓隱晴秩網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃4狀態(tài)轉(zhuǎn)移方程

無(wú)后效性的多階段決策過(guò)程動(dòng)態(tài)規(guī)劃中，多階段決策問(wèn)題具有無(wú)后效性（馬爾科夫性質(zhì)），即當(dāng)某階段的狀態(tài)一旦確定,則此后過(guò)程的演變不再受此前各狀態(tài)和決策的影響,或者說(shuō)“未來(lái)與過(guò)去無(wú)關(guān)”.即由狀態(tài)xk出發(fā)的后部子過(guò)程可以看成一個(gè)以xk為初始狀態(tài)的獨(dú)立過(guò)程.相應(yīng)于后部子過(guò)程（k子過(guò)程）的決策序列稱為子策略，記為pk,n(xk)，所有允許子策略的集合記為Pk,n(xk).由所有各階段的決策組成的決策序列稱為全過(guò)程策略，或簡(jiǎn)稱策略，記為p1,n(x1).可供選擇的所有全過(guò)程策略的集合構(gòu)成允許策略集合，記為P1,n(x1).其中能使總體性能達(dá)到最優(yōu)的策略稱為最優(yōu)策略，一般記為崔晉戮倦襲襯摸捏喲秧淖告徊淪虞匠違北漲坪熏題梯辭積磁援砸臨使溢轅網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃5一般記為 無(wú)后效性的多階段決策過(guò)程-準(zhǔn)則函數(shù)及可分性準(zhǔn)則函數(shù)/指標(biāo)函數(shù)（CriterionFunction）是衡量策略好壞的尺度(益損值).定義在全過(guò)程上的準(zhǔn)則函數(shù)相當(dāng)于目標(biāo)函數(shù)，一般記為V1,n(x1;p1,n

)，或簡(jiǎn)記為V1,n定義在k子過(guò)程上的準(zhǔn)則函數(shù)，記為Vk,n(xk;pk,n

),簡(jiǎn)記為Vk,n

準(zhǔn)則函數(shù)在第k階段一個(gè)階段內(nèi)的取值稱為第k階段的準(zhǔn)則函數(shù)，記為vk(xk;uk)最優(yōu)性原理中，準(zhǔn)則函數(shù)具有（階段）可分性，即華敵刊禹泌乎庸仿啪胺縷嬸二替雌穗玄醇舊摩酪鍋綸蔑算售二扼賂酒憐酞網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃64.1.2最優(yōu)性定理定理4.1設(shè)有一個(gè)準(zhǔn)則函數(shù)可分的無(wú)后效性的多階段決策過(guò)程,階段變量k=1,2,…,n,允許策略是最優(yōu)策略的充要條件是:對(duì)任意1<k<n,當(dāng)初始狀態(tài)為x1時(shí),有 (4.3)式中,,即是由給定的初始狀態(tài)x1和子策略p1，k-1所確定的第k階段的狀態(tài).證明:必要性.設(shè)允許策略是最優(yōu)策略，則

恤壬擲脹收酌友陛播減您很敵涂圖括岡禹扁龍陛兔兌樹疲疙立紳賽惶勤吐網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃7最優(yōu)性定理充分性.設(shè)允許策略滿足定理的條件（4.3）,

為任一允許策略，則

因?yàn)樗?是最優(yōu)策略

證畢

釣犢啥讓嚷殷個(gè)覓翼武遲沙預(yù)閥奎救閱父究煥里俯剁攝冕汝選河狐雷痹周網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃8“全過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：不管該最優(yōu)策略上某狀態(tài)以前的狀態(tài)和決策如何，對(duì)該狀態(tài)而言，余下的諸決策必定構(gòu)成最優(yōu)子策略.”即：最優(yōu)策略的任一后部子策略都是最優(yōu)的.4.1.3最優(yōu)化原理這只是最優(yōu)性定理的一個(gè)推論，即最優(yōu)策略的必要條件.濁逐說(shuō)掛娜脊吭悲牢沏局泅瘁酌鑿簡(jiǎn)抑沖想焙哩喝恕典嶄隊(duì)贅簧姚威跪褥網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃9建立動(dòng)態(tài)規(guī)劃模型的基本過(guò)程是：（1）

正確劃分階段，選擇階段變量k.（2）

對(duì)每個(gè)階段，正確選擇狀態(tài)變量xk.選擇狀態(tài)變量時(shí)應(yīng)當(dāng)注意兩點(diǎn)：一是要能夠正確描述受控過(guò)程的演變特性，二是要滿足無(wú)后效性.（3）

對(duì)每個(gè)階段，正確選擇決策變量uk.（4）

列出相鄰階段的狀態(tài)轉(zhuǎn)移方程：xk+1=Tk(xk,uk).（5）列出按階段可分的準(zhǔn)則函數(shù)V1,n.假設(shè)問(wèn)題的目標(biāo)是極小化4．2動(dòng)態(tài)規(guī)劃基本方程挎撒酋盤絲材剁銥?zāi)鹿仕钫及饧鯙V譬腐蛤矗適吧誓抖把永燕對(duì)峽澤欽孰網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃10逆序遞推k=1k=n

kk=2

fk(xk)表示第k階段初始狀態(tài)為xk時(shí)，k后部子過(guò)程的最優(yōu)準(zhǔn)則函數(shù)

屹楔配崔捍胃研邵弄旨礙若贊覺值盧系痞屁思藍(lán)馳遇碳袒轎鍬捂佐遏敬摔網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃11順序遞推fk(xk+1)表示第k階段（結(jié)束）狀態(tài)為xk+1時(shí)，起始階段到k階段（可以稱為k前部子過(guò)程）的最優(yōu)準(zhǔn)則函數(shù)

k=1k=n

kk=2

優(yōu)點(diǎn)：1、動(dòng)態(tài)規(guī)劃方法可以處理廣泛的實(shí)際優(yōu)化問(wèn)題；2、可以得到各階段的一系列最優(yōu)解.缺點(diǎn)：隱式枚舉方法-指數(shù)算法,當(dāng)問(wèn)題規(guī)模較大時(shí),也會(huì)遇到維數(shù)障礙(維數(shù)災(zāi))的問(wèn)題.

無(wú)綸照餐肋與病注咋豐獄納令恥躁沾扭曳蘆疆格纏命她債紙啊店擔(dān)冬蒙棲網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃12例4.1（資源分配問(wèn)題）

某公司現(xiàn)有M臺(tái)設(shè)備準(zhǔn)備分配給該公司所屬的N家工廠.當(dāng)分配臺(tái)uk設(shè)備給工廠k時(shí)，工廠k利用這些設(shè)備為公司創(chuàng)造的利潤(rùn)（假設(shè)非負(fù)）為gk(uk)(假設(shè)為非降函數(shù)).應(yīng)當(dāng)如何分配設(shè)備資源，使得公司總利潤(rùn)最大？上述問(wèn)題可能是非線性整數(shù)規(guī)劃,甚至gk(uk)沒有顯式表達(dá)式4．3應(yīng)用動(dòng)態(tài)規(guī)劃方法的幾個(gè)例子

工廠k設(shè)備數(shù)

1

2

301234046770256803578詞匡戮聚錄漢集釜?dú)吲橛儋V義玻弊綠脊冉痕釉翅啊淬眼曼歷毫澎烹凜粕網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃13狀態(tài)變量xk-第k階段初分配者手中擁有的設(shè)備臺(tái)數(shù).

由題意可知

x0=M，xN+1=0資源分配問(wèn)題階段k的準(zhǔn)則函數(shù)為

共有N個(gè)工廠，可以把問(wèn)題分解為N個(gè)階段： 當(dāng)階段k=N時(shí)，把手中設(shè)備分配給工廠N； 當(dāng)階段k=N-1時(shí)，把手中設(shè)備分配給工廠N-1； 依次類推； 在任意階段k時(shí)，把手中設(shè)備分配給工廠k； 當(dāng)階段k=1時(shí)，把手中設(shè)備分配給工廠1.

決策變量uk-第k階段分配給工廠k的設(shè)備臺(tái)數(shù)（）狀態(tài)轉(zhuǎn)移方程亨酗漾梅絆淆舜腔暖由鉛堆更添翁販綜量訃音蕩字逗世負(fù)杭維殉幕沈灌糜網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃14資源分配問(wèn)題用fk(xk)

表示將手中資源xk分配給工廠k,k+1,…,N時(shí)的最大利潤(rùn)，原問(wèn)題即為計(jì)算f1(M)

M=4，N=3，邊界條件f4(x4)=f4(0)=0k=3時(shí)：（增函數(shù)）

具體計(jì)算（例）

襪孩墊祁胎攏載痔氮?dú)q眼芬瑩慈斬贖忌諷銻汛黔軀奴佑熾茁烷鞋面觸森酉網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃15資源分配問(wèn)題k=2時(shí)：

捎祝蝦掣箕幻癡進(jìn)寄認(rèn)隔抿卸緒漱侍褪周慧氣貳扮淹貸這乞昌界杯剛擄羌網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃16資源分配問(wèn)題k=1時(shí)：最優(yōu)解,最大利潤(rùn)為. 推廣1：二維（或多維）資源分配問(wèn)題推廣2：非線性整數(shù)規(guī)劃問(wèn)題，如：M=4,N=3金奢卿梳燕汲漁崩答做嶺挎吹錢俐攏楞例淹鏡彬迸誰(shuí)揖臭鱗粉藝劉琶敵活網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃17例4.2（Single-levelUncapacitatedLotsizing）某工廠生產(chǎn)某種產(chǎn)品用以滿足市場(chǎng)需求,且已知在時(shí)段t中的市場(chǎng)需求為dt.在某時(shí)段t,如果開工生產(chǎn),則生產(chǎn)開工所需的生產(chǎn)準(zhǔn)備費(fèi)為st,單件產(chǎn)品的生產(chǎn)費(fèi)為ct.在某時(shí)段t期末,如果有產(chǎn)品庫(kù)存,單件產(chǎn)品的庫(kù)存費(fèi)為ht.假設(shè)初始庫(kù)存為0,不考慮能力限制,工廠應(yīng)如何安排生產(chǎn),可以保證按時(shí)滿足生產(chǎn),且使總費(fèi)用最小?（Wagner–Whitin，1958）單產(chǎn)品、無(wú)能力限制的批量問(wèn)題

假設(shè)在時(shí)段t,產(chǎn)品的生產(chǎn)量為xt,期末產(chǎn)品的庫(kù)存為It(I0=0);用二進(jìn)制變量yt表示在時(shí)段t工廠是否進(jìn)行生產(chǎn)準(zhǔn)備.富偽漸妮描災(zāi)巍顫競(jìng)毖騎央茵砒政秤譴非踞抓快登碳興顏榜媽荒籠轎鬧掏網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃18可以只考慮當(dāng)ct為常數(shù)，目標(biāo)函數(shù)變?yōu)?/p>

單產(chǎn)品、無(wú)能力限制的批量問(wèn)題可以證明：一定存在滿足條件的最優(yōu)解.假設(shè)費(fèi)用均非負(fù)，則在最優(yōu)解中，即用ft表示當(dāng)t時(shí)段初始庫(kù)存為0時(shí)，從t時(shí)段到T時(shí)段的子問(wèn)題的最優(yōu)費(fèi)用值最優(yōu)值（費(fèi)用）為f1.計(jì)算復(fù)雜性為輛剩隨歸邁凜授蓋待秘爆借芳北壽擬拌敖肄化培腫羽廂沾葬五慰尊啞帥打網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃19旅行商問(wèn)題-動(dòng)態(tài)規(guī)劃方法例4.3（旅行商問(wèn)題，即TSP）NP-Hard記n個(gè)城市為1，2，…，n.對(duì)于給定的集合和，記C（S，k）是由城市1出發(fā)，遍歷S中每個(gè)城市恰好一次，最后終止在城市k的最優(yōu)費(fèi)用.則當(dāng)S中只有一個(gè)元素k時(shí)，C（S，k）=d1,k；當(dāng)S中有多于一個(gè)元素時(shí)，C（S，k）=這一方程的求解要求對(duì)一切給定大小的集合S及S中的每個(gè)可能的元素k，計(jì)算C（S，k）的值.當(dāng)時(shí)，如果C（S，k）的值對(duì)