動態(tài)規(guī)劃模型舉例ppt課件(編輯修改稿)
2025-06-02 12:08 本頁面
【文章內(nèi)容簡介】 是第 k周的生產(chǎn)量，記作 uk（ k=1， 2， … ， n）。已知下列數(shù)據(jù)及函數(shù)關(guān)系：第 k周的需求量 dk：第 k周產(chǎn)量為 uk時(shí)的生產(chǎn)費(fèi) ck（ uk）；第 k周初貯存量為xk時(shí)這一周的貯存費(fèi) hk（ xk）；第 k周的生產(chǎn)能力限制 Uk；初始（ k=0）及終結(jié)（ k=n）時(shí)貯存量均為零。按照最短路問題的思路，設(shè)從第 k周初貯存量為 x 到（ n周末）過程結(jié) k6/3/2022 16 束的最小費(fèi)用函數(shù)為 f（ x ），則下列逆向遞推公式成立。 （ 1） 而 xk與 xk+1滿足 (2) 這里貯存量 x是狀態(tài)變量，（ 2）式給出了相鄰階段的狀態(tài)在決策變量作用下的轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移規(guī)律。在用（ 1）式計(jì)算時(shí)， xk的取值范圍 —— 允許狀態(tài)集合 Xk由（ 2）式及允許決策集合（ 0≤uk≤Uk）決定。 ??????????????????0)(1,2,)]()()([mi n)(11110nnkkkkkkkkUukkxfnkXxxfxhucxfkk，????????????012,x 111knkkkxxnkdux ，k k6/3/2022 17 在實(shí)際問題中，為簡單起見，生產(chǎn)費(fèi)用常 ck（ uk） =0 (uk=0)； ck(uk)=a+c uk(uk＞ 0)，其中 c是單位產(chǎn)品生產(chǎn)費(fèi) , 而a是生產(chǎn)準(zhǔn)備費(fèi)。貯存費(fèi)用常取 hk（ xk） = h xk， h是單位產(chǎn)品（一周的）貯存費(fèi)。 最優(yōu)方程（ 1）和狀態(tài)轉(zhuǎn)移方程（ 2）構(gòu)成了這個(gè)多階段決策問題的動態(tài)規(guī)劃模型。實(shí)際上，多階段決策問題有時(shí)也可用靜態(tài)規(guī)劃方法求解，如例 2的生產(chǎn)計(jì)劃問題。 例 15 資源分配問題?？偭繛?m1的資源 A和總量為 m2的資源 B同時(shí)分配給 n個(gè)用戶，已知第 k用戶利用數(shù)量 uk的資源 A和數(shù)量 v 的資源 B時(shí)，產(chǎn)生的效益為 gk（ uk, vk ），問 k6/3/2022 18 如何分配現(xiàn)有資源使總效益最大。 解 ：這本來是個(gè)典型的靜態(tài)規(guī)劃問題： Max Z = (1) (2) (3) 但是當(dāng) gk比較復(fù)雜及 n較大時(shí)，用非線性規(guī)劃求解是困難的，特別是，若 gk是用表格或圖形給出而無解析表達(dá)式時(shí)，則難以求解。而這種情況下，將其轉(zhuǎn)化為 ??nkkkk vug1),(????nkkk umu11 0,????nkkk vmv12 0,6/3/2022 19 動態(tài)規(guī)劃，是一種可行的方法。 資源 A， B每分配給一個(gè)用戶劃分為一個(gè)階段，分配給第 k用戶的數(shù)量是二維決策變量（ uk, vk），而把向第 k用戶分配之前，分配者手中掌握的資源數(shù)量作為二維狀態(tài)變量，記作（ xk， yk），這樣，狀態(tài)轉(zhuǎn)移方程應(yīng)為 (4) ?????????kkkkkkvyyuxx116/3/2022 20 最優(yōu)值函數(shù) fk（ xk， yk）定義為將數(shù)量 xk， ky的資源分配給第 k至第 n用戶時(shí)能獲得的最大效益，它滿足最優(yōu)方程 (5) 對于由（ 4），（ 5）式構(gòu)成的動態(tài)規(guī)劃模型，不需要 gk， fk的解析表達(dá)式，完全可以求數(shù)值解。 ??????????????????????0)0,0(1,2,0,0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1