網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃(已修改)
2025-05-29 04:41 本頁(yè)面
【正文】 1 網(wǎng) 絡(luò) 優(yōu) 化 Network Optimization 清華大學(xué)數(shù)學(xué)科學(xué)系 謝金星 辦公室：理科樓 2266 （電話： 62787812） Email: 清華大學(xué)課號(hào)： 70420213 第 4章 動(dòng)態(tài)規(guī)劃 (Dynamic Programming) 2 動(dòng)態(tài)規(guī)劃問(wèn)題 的例子 例 （ 續(xù)例 ） 最短路問(wèn)題 (Shortest Path Problem) 許多網(wǎng)絡(luò)優(yōu)化問(wèn)題要用到動(dòng)態(tài)規(guī)劃技術(shù) S T 特點(diǎn)：多階段決策 子決策仍然最優(yōu) 動(dòng)態(tài)規(guī)劃 (DP)技術(shù) 動(dòng)態(tài)規(guī)劃 – . Bellman (1950’s) 3 所謂決策 (Decision Making)， 就是人們?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ǔ) . 多階段 決策 模型 ?戰(zhàn)略決策 (高層決策 )、 戰(zhàn)術(shù)決策 (中層決策 )、 操作決策 (基本決策 ) ?單目標(biāo)決策 、 多目標(biāo)決策 ?單階段決策 （ 一次決策 ） 、 多階段決策 ?確定型決策 、 非確定型決策或風(fēng)險(xiǎn)型決策 （ 隨機(jī)決策 、 模糊決策 ） 4 多階段決策過(guò)程 多階段決策（ MultiStage Decision Making），是將決策問(wèn)題的 全過(guò)程 恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系的子過(guò)程（每個(gè)子過(guò)程為一個(gè) 階段 ），以便按照一定的次序去求解 . 階段一般是根據(jù)時(shí)間和空間的自然特征來(lái)劃分，以便于問(wèn)題的求解為目的 . 描述階段的變量稱為 階段變量 ，一般用 k表示 . 從第 k個(gè)階段開(kāi)始點(diǎn)到全過(guò)程終點(diǎn)的過(guò)程稱為 后部子過(guò)程 ，或 k子過(guò)程 . 在多階段決策問(wèn)題中 ， 狀態(tài) 表示每個(gè)階段開(kāi)始時(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)下的所有允許決策的集合 . 5 狀態(tài)轉(zhuǎn)移方程 ),(1 kkkk uxTx ??無(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)策略 ，一般記為 ),( **2*1* ,1 nn uuup ??6 一般記為 nkkkknjjjjnk VuxvuxvV ,11, ),(),( ????? ?無(wú)后效性的多階段決策過(guò)程 準(zhǔn)則函數(shù)及可分性 準(zhǔn)則函數(shù) /指標(biāo)函數(shù)（ Criterion Function）是衡量策略好壞的尺度 (益損值 ). ? 定義在全過(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ù)具有 （ 階段 ） 可分性 ， 即 算，如
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1