動(dòng)態(tài)規(guī)劃(完整).ppt

主要內(nèi)容 7 1多階段決策問題 7 2動(dòng)態(tài)規(guī)劃的基本概念和基本原理 7 3動(dòng)態(tài)規(guī)劃應(yīng)用舉例 例求解最短路問題 分階段的最短路徑 C1 T3 B1 C1 T4 A2 B1 C1 T7 Q A2 B1 C1 T11Q A3 B1 C1 T11Q A3 B2 C2 T11 最短路徑 3 4 4 7 6 11 7 8 11 最短路徑解的特點(diǎn) 1 可以將全過程求解分為若干階段求解 多階段決策問題2 在全過程最短路徑中 將會(huì)出現(xiàn)階段的最優(yōu)路徑 遞推性3 前面的終點(diǎn)確定 后面的路徑也就確定了 且與前面的路徑 如何找到的這個(gè)終點(diǎn) 無關(guān) 無后效性3 逐段地求解最優(yōu)路徑 勢必會(huì)找到一個(gè)全過程最優(yōu)路徑 動(dòng)態(tài)規(guī)劃 7 1多階段決策問題 動(dòng)態(tài)規(guī)劃是解決多階段最優(yōu)決策的方法 由美國數(shù)學(xué)家貝爾曼 R Bellman 于1951年首先提出 1957年貝爾曼發(fā)表動(dòng)態(tài)規(guī)劃方面的第一部專著 動(dòng)態(tài)規(guī)劃 標(biāo)志著運(yùn)籌學(xué)的一個(gè)新分支的創(chuàng)立 動(dòng)態(tài)規(guī)劃將復(fù)雜的多階段決策問題分解為一系列簡單的 離散的單階段決策問題 采用順序求解方法 通過解一系列小問題達(dá)到求解整個(gè)問題目的 動(dòng)態(tài)規(guī)劃的各個(gè)決策階段不但要考慮本階段的決策目標(biāo) 還要兼顧整個(gè)決策過程的整體目標(biāo) 從而實(shí)現(xiàn)整體最優(yōu)決策 動(dòng)態(tài)規(guī)劃的分類 離散確定型離散隨機(jī)型連續(xù)確定型連續(xù)隨機(jī)型 動(dòng)態(tài)規(guī)劃的特點(diǎn) 動(dòng)態(tài)規(guī)劃沒有準(zhǔn)確的數(shù)學(xué)表達(dá)式和定義精確的算法 它強(qiáng)調(diào)具體問題具體分析 依賴分析者的經(jīng)驗(yàn)和技巧 與運(yùn)籌學(xué)其他方法有很好的互補(bǔ)關(guān)系 尤其在處理非線性 離散性問題時(shí)有其獨(dú)到的特點(diǎn) 通常多階段決策過程的發(fā)展是通過狀態(tài)的一系列變換來實(shí)現(xiàn)的 一般情況下 系統(tǒng)在某個(gè)階段的狀態(tài)轉(zhuǎn)移除與本階段的狀態(tài)和決策有關(guān)外 還可能與系統(tǒng)過去經(jīng)歷的狀態(tài)和決策有關(guān) 因此 問題的求解就比較困難復(fù)雜 而適合于用動(dòng)態(tài)規(guī)劃方法求解的只是一類特殊的多階段決策問題 即具有 無后效性 的多階段決策過程 所謂無后效性 又稱馬爾柯夫性 是指系統(tǒng)從某個(gè)階段往后的發(fā)展 僅由本階段所處的狀態(tài)及其往后的決策所決定 與系統(tǒng)以前經(jīng)歷的狀態(tài)和決策 歷史 無關(guān) 具有無后效性的多階段決策過程的特點(diǎn)是系統(tǒng)過去的歷史 只能通過現(xiàn)階段的狀態(tài)去影響系統(tǒng)的未來 當(dāng)前的狀態(tài)就是后過程發(fā)展的初始條件 動(dòng)態(tài)規(guī)劃的應(yīng)用 動(dòng)態(tài)規(guī)劃在工程技術(shù) 企業(yè)管理 軍事部門有廣泛的應(yīng)用 可解決資源分配 生產(chǎn)調(diào)度 庫存管理 路徑優(yōu)化 設(shè)備更新 投資規(guī)劃 排序問題和生產(chǎn)過程的最優(yōu)控制等問題 使用動(dòng)態(tài)規(guī)劃方法求解決策問題首先要將問題改造成符合動(dòng)態(tài)規(guī)劃求解要求的形式 要涉及以下概念 1 階段 2 狀態(tài) 3 決策與策略 4 狀態(tài)轉(zhuǎn)移方程 5 指標(biāo)函數(shù) 6 基本方程 7 2動(dòng)態(tài)規(guī)劃的基本概念和基本思想 一 基本概念 1 劃分階段把一個(gè)復(fù)雜決策問題按時(shí)間或空間特征分解為若干 n 個(gè)相互聯(lián)系的階段 stage 以便按順序求解 階段變量描述當(dāng)前所處的階段位置 一般用下標(biāo)k表示 每階段有若干狀態(tài) state 表示某一階段決策面臨的條件或所處位置及運(yùn)動(dòng)特征的量 稱為狀態(tài) 反映狀態(tài)變化的量叫作狀態(tài)變量 k階段的狀態(tài)特征可用狀態(tài)變量sk描述 每一階段的全部狀態(tài)構(gòu)成該階段的狀態(tài)集合Sk 并有sk Sk 每個(gè)階段的狀態(tài)可分為初始狀態(tài)和終止?fàn)顟B(tài) 或稱輸入狀態(tài)和輸出狀態(tài) 階段的初始狀態(tài)記作sk 終止?fàn)顟B(tài)記為sk 1 也是下個(gè)階段的初始狀態(tài) 2 確定狀態(tài) 3 決策 決策變量 所謂決策就是確定系統(tǒng)過程發(fā)展的方案 決策的實(shí)質(zhì)是關(guān)于狀態(tài)的選擇 是決策者從給定階段狀態(tài)出發(fā)對(duì)下一階段狀態(tài)作出的選擇 用以描述決策變化的量稱之決策變量 和狀態(tài)變量一樣 決策變量可以用一個(gè)數(shù) 一組數(shù)或一向量來描述 也可以是狀態(tài)變量的函數(shù) 記以 表示于k階段狀態(tài)sk時(shí)的決策變量 決策變量的取值往往也有一定的容許范圍 稱之允許決策集合 決策變量xk sk 的允許決策集用XK SK 表示 xk sk XK SK 允許決策集合實(shí)際是決策的約束條件 4 策略和允許策略集合 策略 Policy 也叫決策序列 策略有全過程策略和k部子策略之分 全過程策略是指具有n個(gè)階段的全部過程 由依次進(jìn)行的n個(gè)階段決策構(gòu)成的決策序列 簡稱策略 表示為 從k階段到第n階段 依次進(jìn)行的階段決策構(gòu)成的決策序列稱為k部子策略 表示為 顯然當(dāng)k 1時(shí)的k部子策略就是全過程策略 5 狀態(tài)轉(zhuǎn)移方程 狀態(tài)轉(zhuǎn)移確定從一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)移過程 由狀態(tài)轉(zhuǎn)移方程描述 sk 1 T sk xk 狀態(tài)轉(zhuǎn)移方程在大多數(shù)情況下可以由數(shù)學(xué)公式表達(dá) 如 sk 1 sk xk 6 指標(biāo)函數(shù) 用來衡量策略或子策略或決策的效果的某種數(shù)量指標(biāo) 就稱為指標(biāo)函數(shù) 它是定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù) 對(duì)不同問題 指標(biāo)函數(shù)可以是諸如費(fèi)用 成本 產(chǎn)值 利潤 產(chǎn)量 耗量 距離 時(shí)間 效用 等等 用vk sk xk 表示第k段處于狀態(tài)sk且所作決策為xk時(shí)的指標(biāo) 則它就是第k段指標(biāo)函數(shù) 簡記為vk 用f sk xk 表示第k子過程的指標(biāo)函數(shù) 表示處于第k段sk狀態(tài)且所作決策為xk時(shí) 從sk點(diǎn)到終點(diǎn)的距離 由此可見 f sk xk 不僅跟當(dāng)前狀態(tài)sk有關(guān) 2 過程指標(biāo)函數(shù) 也稱目標(biāo)函數(shù) 1 階段指標(biāo)函數(shù) 也稱階段效應(yīng) 還跟該子過程策略pk sk 有關(guān) 嚴(yán)格說來 應(yīng)表示為fk sk pk sk 它是由各階段的階段指標(biāo)函數(shù)vk sk xk 累積形成的 對(duì)于k部子過程的指標(biāo)函數(shù)可以表示為 式中 表示某種運(yùn)算 可以是加 減 乘 除 開方等 多階段決策問題中 常見的目標(biāo)函數(shù)形式之一是取各階段效應(yīng)之和的形式 即 有些問題 如系統(tǒng)可靠性問題 其目標(biāo)函數(shù)是取各階段效應(yīng)的連乘積形式 7 最優(yōu)解 用fk sk 表示第k子過程指標(biāo)函數(shù)Fk sk pk sk 在狀態(tài)sk下的最優(yōu)值 即 稱fk sk 為第k子過程上的最優(yōu)指標(biāo)函數(shù) 與它相應(yīng)的子策略pk sk 稱為狀態(tài)sk下的最優(yōu)子策略 記為pk sk 例用動(dòng)態(tài)規(guī)劃求解最短路問題 最短路的求解 階段 可分為4個(gè)階段 k 1 4 狀態(tài) 可用城市編號(hào) S1 Q S2 A1 A2 A3 S3 B1 B2 B3 S4 C1 C2 S5 T 決策 決策變量也可用城市編號(hào) 狀態(tài)轉(zhuǎn)移方程 sk 1 xk 階段指標(biāo)函數(shù) 過程指標(biāo) 階段遞推 函數(shù) k 4f4 C1 3 f4 C2 4k 3f3 B1 min 1 f4 C1 4 4 f4 C2 8 4f3 B2 min 6 f4 C1 9 3 f4 C2 7 7f3 B3 min 3 f4 C1 6 3 f4 C2 7 6k 2f2 A1 min 7 f3 B1 4 f3 B2 6 f3 B3 min 11 11 12 11f2 A2 min 3 f3 B1 2 f3 B2 4 f3 B3 min 7 9 10 7f2 A3 min 4 f3 B1 1 f3 B2 5 f3 B3 min 8 8 11 8k 1f1 Q min 2 f2 A1 4 f2 A2 3 f2 A3 min 13 11 11 11最短路是 Q A2 B1 C1 T p A2 B1 C1 T Q A3 B1 C1 T p A3 B1 C1 T Q A3 B2 C2 T p A3 B2 C2 T 整個(gè)過程的最優(yōu)策略應(yīng)具有這樣的性質(zhì) 無論過去的狀態(tài)和決策如何 對(duì)前面的決策所形成的狀態(tài)而言 后續(xù)的諸決策必須構(gòu)成最優(yōu)策略 上一條成立的條件是階段遞推函數(shù)嚴(yán)格單調(diào) 二 動(dòng)態(tài)規(guī)劃的最優(yōu)性原理 在例題中 求解最短路線的計(jì)算公式可以概括寫成 其中 vk在這里表示從狀態(tài)sk到由決策xk所決定的狀態(tài)sk 1之間的距離 f5 s5 0是邊界條件 表示全過程到第四階段終點(diǎn)結(jié)束 一般地 對(duì)于n個(gè)階段的決策過程 假設(shè)只考慮指標(biāo)函數(shù)是 和 與 積 的形式 第k階段和第k 1階段間的遞推公式可表示如下 當(dāng)過程指標(biāo)函數(shù)為下列 和 的形式時(shí) 相應(yīng)的函數(shù)基本方程為 當(dāng)過程指標(biāo)函數(shù)為下列 積 的形式時(shí) 相應(yīng)的函數(shù)基本方程為 動(dòng)態(tài)規(guī)劃的優(yōu)缺點(diǎn) 動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)可以解決線性 非線性 整數(shù)規(guī)劃無法有效求解的復(fù)雜問題 容易找到全局最優(yōu)解 可以得到一組解 動(dòng)態(tài)規(guī)劃的缺點(diǎn) 沒有標(biāo)準(zhǔn)的模型可供應(yīng)用 構(gòu)模依賴于個(gè)人的經(jīng)驗(yàn)和技巧 狀態(tài)變量需滿足無后效性 有較大的局限性 動(dòng)態(tài)規(guī)劃的維數(shù)災(zāi)難限制了對(duì)規(guī)模較大問題的求解效率 7 3動(dòng)態(tài)規(guī)劃方法應(yīng)用 動(dòng)態(tài)規(guī)劃的步驟 1 將問題按時(shí)間或空間劃分為滿足遞推關(guān)系的若干階段 對(duì)非時(shí)序問題可人為地引入 時(shí)段 概念 2 正確選擇狀態(tài)變量sk 滿足 可知性 正確描述動(dòng)態(tài)過程演變 可直接或間接確定狀態(tài)變量的值 無后效性 后面的決策與前面的決策無關(guān) 3 確定決策變量xk以及允許決策集合Xk 4 寫出狀態(tài)轉(zhuǎn)移方程sk 1 T sk xk 5 決策變量的取值范圍6 寫出過程指標(biāo)函數(shù) 階段函數(shù) 的遞推關(guān)系 應(yīng)滿足 a 是定義在所有階段上的數(shù)量函數(shù) b 具有可分離性 并滿足遞推關(guān)系 c 階段函數(shù)應(yīng)嚴(yán)格單調(diào) 動(dòng)態(tài)規(guī)劃應(yīng)用舉例 1 最優(yōu)路徑問題2 資源配置問題3 生產(chǎn)與庫存問題4 機(jī)器負(fù)荷分配問題5 復(fù)合系統(tǒng)工作可靠性問題6 二維背包問題7 設(shè)備更新問題貨郎擔(dān)問題非線性規(guī)劃的求解 1 最優(yōu)路徑問題 某廠要確定一種新產(chǎn)品在今后五年內(nèi)的價(jià)格 并已擬定只在5 6 7 8元這四種單價(jià)中進(jìn)行選擇 據(jù)預(yù)測 今后五年不同價(jià)格下每年盈利 萬元 見下表 但是各相鄰年度價(jià)格增減不得超過1元 問今后五年內(nèi)每年定價(jià)各為多少 可逾七五年總利潤最大 13 14 11 8 4 3 4 10 18 22 23 17 24 28 28 30 37 35 36 38 解 1 建立動(dòng)態(tài)規(guī)劃模型 階段 以年劃分階段 k 5 4 3 2 1 狀態(tài)變量sk為每個(gè)階段初的價(jià)格 則Sk 5 6 7 8 決策變量xk為每年所確定的價(jià)格 則Xk 5 6 7 8 狀態(tài)轉(zhuǎn)移方程 階段指標(biāo)函數(shù)vk sk xk 為每個(gè)階段選擇xk所取得的盈利 例如v sk 過程指標(biāo)函數(shù)為第k階段狀態(tài)為sk時(shí)到最后一個(gè)階段的總利潤 基本函數(shù)方程為 逆序求解 k 5f5 s5 x5 v5 s5 x5 f6 s6 f5 s5 x5 sx567858 08564 04673 03784 048 k 4f4 s4 x4 v4 s4 x4 f5 s5 f4 s4 x4 sx567855 85 413566 86 46 314577 47 37 4116 886 36 4107 k 3f3 s3 x3 v3 s3 x3 f4 s4 f3 s3 x3 sx567854 134 1418668 138 148 1122779 149 119 1023686 116 10177 k 2f2 s2 x2 v2 s2 x2 f3 s3 f2 s2 x2 sx567852 182 2224665 185 225 2328775 225 235 1728787 237 17307 k 1f1 s1 x1 v1 s1 x1 f2 s2 f1 s1 x1 sx567859 249 2837667 247 287 28356 776 286 286 3036888 288 30388 S1 8X1 8s2 8x2 7s3 7x3 6s4 6x4 5s5 5x5 5 2 資源配置問題 如何將有限的資源分配給若干種生產(chǎn)活動(dòng) 并使資源利用的收益最大是經(jīng)濟(jì)活動(dòng)中常見的問題 動(dòng)態(tài)規(guī)劃可以求解一些線性規(guī)劃無法解決的資源配置問題 一般的資源分配問題可以描述為如下的規(guī)劃問題 max z g1 x1 g2 x2 gn xn x1 x2 xn axi 0i 1 n 例 某廠為擴(kuò)大生產(chǎn)能力 擬訂購某種成套4 6套 以分配給其所轄1 2 3個(gè)分廠使用 預(yù)計(jì)個(gè)分廠分的不同套數(shù)的設(shè)備后 每年創(chuàng)造的利潤 萬元 如下表所示 該廠應(yīng)訂購幾套設(shè)備并如何分配 才能使每年預(yù)計(jì)創(chuàng)利總額最大 建立動(dòng)態(tài)規(guī)劃模型 1 階段與分廠相聯(lián)系 階段k只考慮分配分廠k的設(shè)備套數(shù) 2 狀態(tài)變量sk表示k分廠可分配的設(shè)備套數(shù) 3 決策變量xk表示決定在k分廠使用的設(shè)備套數(shù) 4 狀態(tài)轉(zhuǎn)移方程 sk 1 sk xk 階段函數(shù) vk sk xk 為k分廠使用設(shè)備xk時(shí)的獲利 從第一分廠到第k分廠的總獲利fk sk max vk sk xk fk 1 sk 1 6 基本狀態(tài)方程 k 3 k 2 s3 s2 x2 k 1 s2 s1 x1 因此得到 x1 2 s2 6 2 4 x2 1 s3 4 1 3 x3 3x1 1 s2 6 1 5 x2 2 s3 5 2 3 x3 3即 p 2 1 3 或 1 2 3 獲利18萬元 3 復(fù)合系統(tǒng)的工作可靠性問題例 為保證設(shè)備可靠運(yùn)行 一些關(guān)鍵部件往往由多個(gè)器件并聯(lián)運(yùn)行 如果器件i的失效概率為pi 則xi個(gè)器件并聯(lián)工作的可靠性為 1 pixi 假定每個(gè)器件的采購費(fèi)用為ci 在滿足總采購費(fèi)用不超過預(yù)算限制C的前提下 使設(shè)備可靠性最高的規(guī)劃問題可以描述為 該問題為整數(shù)非線性規(guī)劃 可以用動(dòng)態(tài)規(guī)劃求解 設(shè)關(guān)鍵器件數(shù)n 3 總費(fèi)用為120萬元 器件的單價(jià)與可靠性如下表 建立動(dòng)態(tài)規(guī)劃模型 階段與器件掛鉤 第k階段僅考慮器件k的采購數(shù)量 sk表示k階段可使用的采購費(fèi)用 xk表示k階段決定購買k器件的數(shù)量 狀態(tài)轉(zhuǎn)移方程 sk 1 sk ckxk 遞推階段函數(shù) vk sk xk 1 pkxk總可靠性fk sk max 1 pkxk fk 1 sk 1 基本狀態(tài)方程 k 3 k 2 s3 s2 c2x2 k 1 s2 s1 c1x1 因此得到 x1 1 s2 120 30 90 x2 2 s3 90 2 15 60 x3 3即 p 1 2 3 可靠性為0 756 4 生產(chǎn)調(diào)度 生產(chǎn)與庫存 問題 某廠根據(jù)市場預(yù)測 確認(rèn)今后4個(gè)月該廠的一種主要產(chǎn)品每月的需求的量d為3 2 3 2萬件 已知每月生產(chǎn)固定費(fèi)用b為2千元 但若當(dāng)月不生產(chǎn)則為0 產(chǎn)品成本c為1千元 件 貯存費(fèi)用h為0 2千元 萬件 月 最大存貯能力w為4萬件 若第1月初五庫存產(chǎn)品 第4月末也不留庫存 則該廠怎樣安排生產(chǎn) 才能使今后4個(gè)月的總費(fèi)用最少 建立動(dòng)態(tài)規(guī)劃模型 1 階段與時(shí)間相聯(lián)系 階段k表示月份2 狀態(tài)變量sk表示k月初的庫存量 3 決策變量xk表示k月的產(chǎn)量 4 若dk為需求量 則狀態(tài)轉(zhuǎn)移方程 sk 1 sk xk dk 5 階段函數(shù) vk sk xk 為k月的生產(chǎn)費(fèi)用 過程函數(shù) fk sk 為從第一月到第k月的總生產(chǎn)費(fèi)用fk sk max vk sk xk fk 1 sk 1 6 基本狀態(tài)方程 k 4這是最后一個(gè)月 需求為2 無庫存s5 0 由狀態(tài)方程知 s4 2 x4 x4 0 則s4只能是0 1 2 k 3這是第3個(gè)月 需求為3 由狀態(tài)方程知 s4 s3 x3 3 又由于2 s4 0 即2 s3 x3 3 0 s3 w 4則s3取值是0 1 2 3 4 X3 x3 3 s3 x3 5 s3 0 1 2 3 4 k 2這是第2個(gè)月 需求為2 第一個(gè)月無庫存s1 0 s2 s1 x1 3 x1 3 又因x1 5 則s2取值是0 1 2 由狀態(tài)方程知 s3 s2 x2 2 又由于4 s3 0 即4 s2 x2 2 0 X2 x2 2 s2 x2 6且x2 5 s2 0 1 2 k 1這是第1個(gè)月 需求為3 第一個(gè)月無庫存s1 0 s2 x1 3 x1 3 又因x1 5 s2取值是0 1 2 X1 x1 3 x1 5 5設(shè)備更新問題 設(shè)備在使用全過程中會(huì)遭受磨損 使用一段時(shí)間后就要維修 而且使用的時(shí)間越長 維修費(fèi)用越高 設(shè)備使用多少時(shí)間在經(jīng)濟(jì)上最合算 就是設(shè)備更新問題 分析 階段k 1 2 3 4 5 sk表示k年初設(shè)備已使用的年限 xk為k年初決定設(shè)備是繼續(xù)使用還是更新的決策變量 xk 1表示繼續(xù)使用 xk 0表示更新 狀態(tài)轉(zhuǎn)移方程 sk 1 sk 1 xk 1 sk 1 1 xk 0 k 5狀態(tài)變量s5可取1 2 3 4f5 1 maxx1 0 1 r 0 u 0 c 1 r 1 u 1 max 5 0 5 1 5 4 5 1 3 5 x5 1 f5 2 max 5 0 5 2 2 4 1 5 2 5 x5 1 f5 3 max 5 0 5 2 5 3 75 2 2 x5 0 f5 4 max 5 0 5 3 3 2 5 1 5 x5 0 k 4狀態(tài)變量s4可取1 2 3f4 1 max r 0 u 0 c 1 f5 1 r 1 u 1 f5 2 max 5 0 5 1 5 3 5 4 5 1 2 5 6 5 x4 0 f4 2 max 5 0 5 2 2 3 5 4 1 5 2 5 8 x4 0 f4 3 max 5 0 5 2 5 3 5 3 75 2 1 5 5 5 x4 0 k 3狀態(tài)變量s3可取1 2 f3 1 max r 0 u 0 c 1 f4 1 r 1 u 1 f4 2 max 5 0 5 1 5 6 5 4 5 1 5 8 9 5 x3 0 f3 2 max 5 0 5 2 2 6 5 4 1 5 5 5 8 8 x3 0 k 2狀態(tài)變量s2可取1 f2 1 max r 0 u 0 c 1 f3 1 r 1 u 1 f3 2 max 5 0 5 1 5 9 5 4 5 1 8 8 12 5 x2 0 最優(yōu)策略為 k 12345不更新更新更新更新不更新 k 1時(shí)狀態(tài)變量s1只能取0f1 0 max r 0 u 0 c 0 f2 1 r 0 u 0 f2 1 max 5 0 5 0 5 12 5 5 0 5 12 5 17 x1 1 6 機(jī)器負(fù)荷分配問題有某種機(jī)床 可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn) 在高負(fù)荷下生產(chǎn)時(shí) 產(chǎn)品的年產(chǎn)量為g 與年初投入生產(chǎn)的機(jī)床數(shù)量u1的關(guān)系為g g u1 8u1 這時(shí) 年終機(jī)床完好臺(tái)數(shù)將為 au1 a為機(jī)床完好率 0 a 1 設(shè)a 0 7 在低負(fù)荷下生產(chǎn)時(shí) 產(chǎn)品的年產(chǎn)量為h 和投入生產(chǎn)的機(jī)床數(shù)量的關(guān)系為h h u2 5u2 相應(yīng)的機(jī)床完好率為b 0 b 2 設(shè)b 0 9 一般情況下 a b 假設(shè)某廠開始有x1 1000臺(tái)完好的機(jī)床 現(xiàn)要制定一個(gè)五年生產(chǎn)計(jì)劃 問每年開始時(shí)如何重新分配完好的機(jī)床在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量 以使在5年內(nèi)產(chǎn)品的總產(chǎn)量為最高 解 首先構(gòu)造這個(gè)問題的動(dòng)態(tài)規(guī)劃模型 1 分階段 設(shè)階段變量k表示年度 因此 階段總數(shù)n 5 2 狀態(tài)變量 用sk表示第k年度初擁有的完好機(jī)床臺(tái)數(shù) 同時(shí)也是第k 1年度末時(shí)的完好機(jī)床數(shù)量 3 決策變量 用uk表示第k年度中分配于高負(fù)荷下生產(chǎn)的機(jī)床臺(tái)數(shù) 于是sk uk便為該年度中分配于低負(fù)荷下生產(chǎn)的機(jī)床臺(tái)數(shù) 4 狀態(tài)轉(zhuǎn)移方程為 決策變量的取值 在第k段為 6 階段指標(biāo)函數(shù) 令vk sk uk 表示由第k年的狀態(tài)sk出發(fā) 采取uk分配方案的產(chǎn)品產(chǎn)量 7 條件最優(yōu)目標(biāo)函數(shù)遞推方程 令fk sk 表示由第k年的狀態(tài)sk出發(fā) 采取最優(yōu)分配方案到第5年度結(jié)束這段時(shí)間的產(chǎn)品產(chǎn)量 根據(jù)最優(yōu)化原理有以下遞推關(guān)系 下面采用逆序遞推計(jì)算法 從第5年度開始遞推計(jì)算 K 5時(shí)有 顯然 當(dāng)u5 s5時(shí) f5 s5 有最大值 相應(yīng)的有f5 s5 8s5 K 4時(shí)有 因此 當(dāng)u4 s4時(shí) 有最大值f4 s4 13 6s4 K 3時(shí)有 可見 當(dāng)u3 s3時(shí) 有最大值f3 s3 17 55s3 K 2時(shí)有 此時(shí) 當(dāng)u2 0時(shí)有最大值 即f2 s2 20 8s2 其中s2 0 7u1 0 9 s1 u1 K 1時(shí)有 當(dāng)u1 0時(shí) 有最大值 即f1 s1 23 7s1 因?yàn)閟1 1000 故f1 s1 23700個(gè)產(chǎn)品 按照上述計(jì)算順序?qū)ほ櫟玫较率鲇?jì)算結(jié)果 上面所討論的最優(yōu)決策過程是所謂始端狀態(tài)固定 終端狀態(tài)自由 如果終端也附加上一定的約束條件 那么計(jì)算結(jié)果將會(huì)與之有所差別 例如 若規(guī)定在第五個(gè)年度結(jié)束時(shí) 完好的機(jī)床數(shù)量為500臺(tái) 上面只有278臺(tái) 問應(yīng)該如何安排五年的生產(chǎn) 使之在滿足這一終端要求的情況下產(chǎn)量最高 解 由狀態(tài)轉(zhuǎn)移方程 有 由此式得 當(dāng)k 5時(shí)有 當(dāng)k 4時(shí)有 顯然 只有