【正文】 最優(yōu)解 :S2=4 S2 u2 本期成本 C2 S3 f3(S3) f2(S2) 生產(chǎn) 存儲(chǔ) 4 0 1 2 3 4 5 0 4 5 6 7 8 2 2 2 2 2 2 2 6 7 8 9 10 1 2 3 4 5 6 14 15 16 17 15 2022/2/16 76 第一階段最優(yōu)解 ? 當(dāng) k=1時(shí)， d1=2， S1=0 S1 u1 本期成本 C1 S2 f2(S2) f1(S1) 生產(chǎn) 存儲(chǔ) 0 2 3 4 5 6 5 6 7 8 9 0 0 0 0 0 5 6 7 8 9 0 1 2 3 4 21 22 2022/2/16 77 最優(yōu)解 ? 從第一階段向后反推最優(yōu)路線(xiàn)，總結(jié)可得 時(shí)期 K 期初存貨 期末存貨 最優(yōu)生產(chǎn)量 該期成本 總成本 Sk Sk+1 1 2 3 4 0 3 0 4 3 0 4 0 5 0 6 0 8 9 2 11 2 2022/2/16 78 ? 例、 某企業(yè)集團(tuán)擬將某種高效率的設(shè)備五臺(tái)，分配給所屬的甲、乙、丙三個(gè)工廠(chǎng)，各工廠(chǎng)若獲得這種設(shè)備之后，可以為該集團(tuán)提供的盈利如下圖所示。 時(shí)期（月） 需求量（ dk） 1 2 3 4 2 3 2 4 2022/2/16 62 已知的其它條件 ? 已知生產(chǎn)一件產(chǎn)品的成本是 1千元，每批產(chǎn)品的生產(chǎn)準(zhǔn)備成本是 3千元，每月僅能生產(chǎn)一批，每批 6件。 ? 得第二年定價(jià) 8元，第三年定價(jià) 7元，第四年定價(jià) 6元，第五年定價(jià) 5元。2022/2/16 43 定價(jià)問(wèn)題 ? 某公司考慮為某新產(chǎn)品定價(jià)，該產(chǎn)品的單價(jià)擬從每件 5元、 6元、 7元和 8元這四個(gè)中選取一個(gè)，每年允許價(jià)格有 1元幅度的變動(dòng)，該產(chǎn)品預(yù)計(jì)暢銷(xiāo)五年，據(jù)預(yù)測(cè)不同價(jià)格下各年的利潤(rùn)如表所示。 )(:)()( .)(.1 )}(, ) . ..( ),({)( :)(1*,11,11,11,111,spsPspspksusususpnks pnnnnnnkkkkknkknk最優(yōu)策略使目標(biāo)達(dá)最優(yōu)的策略為為全過(guò)程策略時(shí)當(dāng)階段止的策略階段起至第第?????2022/2/16 22 . 1 , 2 , . . , ), . . . . . ,( .: 1)( .6: },{S . .51,1k系滿(mǎn)足可分離性及遞推關(guān)要求表示描述問(wèn)題的數(shù)量函數(shù)用指標(biāo)函數(shù)指標(biāo)函數(shù)指標(biāo)函數(shù)和最優(yōu)值函數(shù)變換算子另一個(gè)狀態(tài)的變換方程確定過(guò)程由一個(gè)狀態(tài)到狀態(tài)轉(zhuǎn)移方程k , nnnnkkk , nnknkkkkkVnksususVVVTuST?????2022/2/16 23 nkkkkjjnkjjkkkjjnkjjk , njjjk , nnkkkkjjnkjjkkkjjnkjjk , njjjk , nVusvusvusvusvVusvVVusvusvusvusvVusvV,110,110),( ),(),(),( ),( 2),( ),(),(),( ),( 1??????????????????????之積為階段指標(biāo)指標(biāo)積之和為階段指標(biāo)指標(biāo)和2022/2/16 24 ? ?m i nm a x,: ), . . . ,()( :)( )2(1.或取最優(yōu)化指標(biāo)函數(shù)的最優(yōu)值最優(yōu)值函數(shù)最優(yōu)值函數(shù)optsususVoptsf sfnnnkknkuukkkknk????????2022/2/16 25 動(dòng)態(tài)規(guī)劃的最優(yōu)性原理 最優(yōu)決策。它是狀態(tài)變量的函數(shù)。有時(shí)為了方便起見(jiàn)，將第 k階段的可達(dá)狀態(tài)集合記為 Sk 。通常一個(gè)階段有若干個(gè)狀態(tài)，第一階段有一個(gè)狀態(tài)就是點(diǎn)①，第二階段有三個(gè)狀態(tài)，即點(diǎn)集合 {② ，③，④ }，一般第 k階段的狀態(tài)就是第 k階段所有始點(diǎn)的集合。描述階段的變量稱(chēng)為階段變量，常用 k表示。 2022/2/16 12 ? (1)在第四階段 ? 此時(shí)只要再走一步即到終點(diǎn)⑩ (B地 )。 2022/2/16 11 具體計(jì)算前，先引進(jìn)幾個(gè)符號(hào) : ? K— 階段變量 ? sk— 狀態(tài)變量，表示第 k階段所處的位置。 ? 首先，將這一問(wèn)題看成是四個(gè)階段的問(wèn)題，由①到 (② ，③，④ )中的點(diǎn)是第一階段 。 ? 因?yàn)槿绻皇沁@樣 ，則從點(diǎn) P到 G點(diǎn)有另外一條距離更短的路線(xiàn)存在，把它和原來(lái)最短路線(xiàn)由 A點(diǎn)到達(dá) P點(diǎn)的那部分連接起來(lái)，就會(huì)得到一條由 A點(diǎn)到 G點(diǎn)的新路線(xiàn)，它比原來(lái)那條最短路線(xiàn)的距離還要短些。 ? 多階段決策問(wèn)題，就是在允許選擇的策略集內(nèi)選擇一個(gè)最優(yōu)策略，使在預(yù)定的標(biāo)準(zhǔn)下，達(dá)到最好的經(jīng)濟(jì)效果。因此，多次決策是動(dòng)態(tài)決策的一個(gè)基本特點(diǎn)。多階段決策問(wèn)題就是求一個(gè)策略，使各階段的效益的總和達(dá)到最優(yōu)。 ? 動(dòng)態(tài)規(guī)劃所研究的對(duì)象是多階段決策問(wèn)題。 ? 許多問(wèn)題用動(dòng)態(tài)規(guī)劃的方法處理，常常比線(xiàn)性規(guī)劃或非線(xiàn)性規(guī)劃更有效，特別是對(duì)于離散性的問(wèn)題。與此同時(shí)，他提出了解決這類(lèi)問(wèn)題的 “最優(yōu)性原理”，研究了許多實(shí)際問(wèn)題，從而創(chuàng)建了解決最優(yōu)化問(wèn)題的一種新的方法 ——?jiǎng)討B(tài)規(guī)劃。 ? 1951年美國(guó)數(shù)學(xué)家貝爾曼 (R. Bellman)等人根據(jù)一類(lèi)多階段決策問(wèn)題的特點(diǎn)，把多階段決策問(wèn)題變換為一系列互相聯(lián)系的單階段問(wèn)題，然后逐個(gè)加以解決。 ? 在企業(yè)管理方面，動(dòng)態(tài)規(guī)劃可以用來(lái)解決最優(yōu)路徑問(wèn)題、資源分配問(wèn)題、生產(chǎn)調(diào)度問(wèn)題、庫(kù)存問(wèn)題、裝載問(wèn)題、排序問(wèn)題、設(shè)備更新問(wèn)題、生產(chǎn)過(guò)程最優(yōu)控制問(wèn)題等等，所以它是現(xiàn)代企業(yè)管理中的一種重要的決策方法。因此，在學(xué)習(xí)動(dòng)態(tài)規(guī)劃時(shí)，除了要對(duì)動(dòng)態(tài)規(guī)劃的基本概念和方法正確理解外，還應(yīng)該以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。 2022/2/16 5 ? 每個(gè)階段的決策確定以后，就得到一個(gè)決策序列，稱(chēng)為策略。決策者要在系統(tǒng)發(fā)展的不同時(shí)點(diǎn)，根據(jù)系統(tǒng)的當(dāng)前狀態(tài)，不斷地作出決策。 ? 由于每個(gè)階段有多種決策，因此，形成有多種策略可供選擇，策略不同經(jīng)濟(jì)效果也不一定相同。此特性用反證法易證 。所以，可以利用動(dòng)態(tài)規(guī)劃的方法從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易疃痰穆肪€(xiàn)。由 (⑧ 、⑨ )中的一點(diǎn)到⑩是第四階段。 ? 求解此問(wèn)題的過(guò)程，是從最后一個(gè)階段開(kāi)始計(jì)算，逐步倒退直到第一階段為止，稱(chēng)為 “逆推”，該問(wèn)題就是求 f1(1)。 2022/2/16 17 ? 三、動(dòng)態(tài)規(guī)劃的基本概念 ? 階段： 把所給問(wèn)題的過(guò)程恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段，以便能按一定的次序去求解。 ? 在例 1中，狀態(tài)就是某階段的出發(fā)位置，它既是該階段某支路的起點(diǎn)，又是前一階段某支路的終點(diǎn)。記為 S3= {⑤ 、⑥、⑦ }。常用 uk (sk)表示第 k階段當(dāng)狀態(tài)處于 sk時(shí)的決策變量。 2022/2/16 21 策略：決策按順序構(gòu)成的序列，用 p表示。 1 2 k n 五、 動(dòng)態(tài)規(guī)劃處理問(wèn)題的基本步驟 2022/2/16 32 ??最小百元使總運(yùn)費(fèi) 的運(yùn)輸路線(xiàn)，選擇例：如圖所示 )( , EA2022/2/16 33 ???