【正文】 2022/2/16 1 第五章 動(dòng) 態(tài) 規(guī) 劃 2022/2/16 2 ? 一、綜 述 ? 動(dòng)態(tài)規(guī)劃解決多階段決策過程最優(yōu)化的一種數(shù)學(xué)方法，大約產(chǎn)生于 50年代。 ? 1951年美國數(shù)學(xué)家貝爾曼 (R. Bellman)等人根據(jù)一類多階段決策問題的特點(diǎn)，把多階段決策問題變換為一系列互相聯(lián)系的單階段問題，然后逐個(gè)加以解決。與此同時(shí)，他提出了解決這類問題的 “最優(yōu)性原理”，研究了許多實(shí)際問題，從而創(chuàng)建了解決最優(yōu)化問題的一種新的方法 ——?jiǎng)討B(tài)規(guī)劃。他的名著 《 動(dòng)態(tài)規(guī)劃 》 于 1957年出版，該書是動(dòng)態(tài)規(guī)劃的第一本著作。 2022/2/16 3 ? 動(dòng)態(tài)規(guī)劃的方法在工程技術(shù) 、企業(yè)管理 、工農(nóng)業(yè)生產(chǎn)及軍事部門中都有廣泛的應(yīng)用 ，并且獲得了顯著的效果。 ? 在企業(yè)管理方面，動(dòng)態(tài)規(guī)劃可以用來解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)調(diào)度問題、庫存問題、裝載問題、排序問題、設(shè)備更新問題、生產(chǎn)過程最優(yōu)控制問題等等，所以它是現(xiàn)代企業(yè)管理中的一種重要的決策方法。 ? 許多問題用動(dòng)態(tài)規(guī)劃的方法處理，常常比線性規(guī)劃或非線性規(guī)劃更有效，特別是對(duì)于離散性的問題。應(yīng)當(dāng)指出，動(dòng)態(tài)規(guī)劃是求解問題的一種方法，是考察問題的一種途徑，而不是一種特殊的算法 (如線性規(guī)劃是一種算法 )。 2022/2/16 4 ? 動(dòng)態(tài)規(guī)劃它不像線性規(guī)劃那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確的一組規(guī)則，而必須對(duì)具體的問題進(jìn)行具體的分析和處理。因此，在學(xué)習(xí)動(dòng)態(tài)規(guī)劃時(shí)，除了要對(duì)動(dòng)態(tài)規(guī)劃的基本概念和方法正確理解外，還應(yīng)該以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。 ? 動(dòng)態(tài)規(guī)劃所研究的對(duì)象是多階段決策問題。 ? 多階段決策問題是指一類活動(dòng)過程，它可以分為若干個(gè)相互聯(lián)系的階段，在每個(gè)階段都需要作出決策。這個(gè)決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)。 2022/2/16 5 ? 每個(gè)階段的決策確定以后，就得到一個(gè)決策序列，稱為策略。多階段決策問題就是求一個(gè)策略，使各階段的效益的總和達(dá)到最優(yōu)。 ? 二、 多階段決策問題 ? 多階段決策問題的描述 ? 一個(gè)決策問題常與時(shí)間聯(lián)系，將時(shí)間作為變量的決策問題稱為動(dòng)態(tài)決策問題。在動(dòng)態(tài)決策問題中，研究對(duì)象 —— 系統(tǒng)所處的狀態(tài)和時(shí)點(diǎn)都是進(jìn)行決策的重要因素。決策者要在系統(tǒng)發(fā)展的不同時(shí)點(diǎn)，根據(jù)系統(tǒng)的當(dāng)前狀態(tài)，不斷地作出決策。因此，多次決策是動(dòng)態(tài)決策的一個(gè)基本特點(diǎn)。 2022/2/16 6 ? 在多階段決策過程中，系統(tǒng)的動(dòng)態(tài)過程可以按照時(shí)間的進(jìn)程分為若干個(gè)相互聯(lián)系的階段，而在每一個(gè)階段中，具有一個(gè)或多個(gè)狀態(tài)，在每一個(gè)階段中都要針對(duì)每一個(gè)狀態(tài)作出決策。 ? 在各個(gè)階段的決策確定以后，就順序構(gòu)成了一個(gè)決策序列，稱為一個(gè)策略。 ? 由于每個(gè)階段有多種決策，因此，形成有多種策略可供選擇，策略不同經(jīng)濟(jì)效果也不一定相同。 ? 多階段決策問題，就是在允許選擇的策略集內(nèi)選擇一個(gè)最優(yōu)策略，使在預(yù)定的標(biāo)準(zhǔn)下，達(dá)到最好的經(jīng)濟(jì)效果。 2022/2/16 7 ? 多階段決策案例 ? 介紹一個(gè)經(jīng)典的多階段決策問題 — 最短路線問題的求解。 ? 例 1 如下圖所示，要從 A地出發(fā)到達(dá) B地，如何走，使總路程最短，最短路是多少 ? 2022/2/16 8 2022/2/16 9 ? 生活中的常識(shí)告訴我們 ，最短路有一個(gè)重要的特性：如果由起點(diǎn) A經(jīng)過 P點(diǎn)和 H點(diǎn)而到達(dá)終點(diǎn) G是一條最短路線，則由點(diǎn) P出發(fā)經(jīng)過 H點(diǎn)到達(dá)終點(diǎn) G的這條子路線，對(duì)于從點(diǎn) P出發(fā)到達(dá)終點(diǎn)的所有可能選擇的不同路線來說，必定也是最短路。此特性用反證法易證 。 ? 因?yàn)槿绻皇沁@樣 ，則從點(diǎn) P到 G點(diǎn)有另外一條距離更短的路線存在，把它和原來最短路線由 A點(diǎn)到達(dá) P點(diǎn)的那部分連接起來，就會(huì)得到一條由 A點(diǎn)到 G點(diǎn)的新路線，它比原來那條最短路線的距離還要短些。這與假設(shè)相矛盾，是不可能的。 2022/2/16 10 ? 根據(jù)最短路線這一特性，尋找最短路線的方法，就是從最后一段開始，用由后向前逐步遞推的方法，求出各點(diǎn)到終點(diǎn)的最短路線，最終求得由起點(diǎn)至終點(diǎn)的最短路線。所以，可以利用動(dòng)態(tài)規(guī)劃的方法從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易疃痰穆肪€。 ? 首先，將這一問題看成是四個(gè)階段的問題，由①到 (② ，③，④ )中的點(diǎn)是第一階段 。由 (② 、③、④ )中的點(diǎn)到 (⑤ 、⑥、⑦ )中的一點(diǎn)是第二階段 。由 (⑤ 、⑥ 、⑦ )中的點(diǎn)到 (⑧ 、⑨ )中的一點(diǎn)是第三階段 。由 (⑧ 、⑨ )中的一點(diǎn)到⑩是第四階段。 2022/2/16 11 具體計(jì)算前，先引進(jìn)幾個(gè)符號(hào) : ? K— 階段變量 ? sk— 狀態(tài)變量，表示第 k階段所處的位置。 ? Xk— 決策變量，表示當(dāng)狀態(tài)為 sk時(shí)，可選擇的下一狀態(tài) ? (這里有 Xk =sk十 1) ? d (sk, Xk)— 從 sk到 sk+1= Xk的距離。 ? fk(sk)— 由 sk到終點(diǎn)的最短距離。 ? 求解此問題的過程，是從最后一個(gè)階段開始計(jì)算，逐步倒退直到第一階段為止，稱為 “逆推”，該問題就是求 f1(1)。 2022/2/16 12 ? (1)在第四階段 ? 此時(shí)只要再走一步即到終點(diǎn)⑩ (B地 )。 ? 目前狀態(tài) s4可以是⑧或⑨，可選擇的下一狀態(tài) X4 是⑩ 所以 f4 (8) =d4 (8, 10) =3, ? f4 (9)=d4 (9, 10)=4 ? (2)在第三階段 ? 在第三階段，還需兩步才能到達(dá)終點(diǎn)，此時(shí) f3 ( s3)=min{d3 ( s3， X3)+f4 (s4)} 目前狀態(tài) s3可以是⑤、⑥、⑦，可選擇的下一狀態(tài) X3有兩個(gè)點(diǎn)⑧或⑨ 2022/2/16 13 ? 于是 2022/2/16 14 ? ? (3)在第二階段 ? 在第二階段，還有三步才能到達(dá)終點(diǎn) ? 同理 f2 (s2)=min { d2 (s2, X2) +f3 (s3)} 2022/2/16 15 2022/2/16 16 ? (4)在第一階段 ? 在第一階段 f1(s1)=min {d1(s1, x1)+f2 (s2)} ? 目前狀態(tài) s1是①，即為出發(fā)點(diǎn)，可選擇的下一狀態(tài) x1有三個(gè)點(diǎn)，即②、③、④。 通過計(jì)算，可知從 A地到 B地總路程最小值為 11。 2022/2/16 17 ? 三、動(dòng)態(tài)規(guī)劃的基本概念 ? 階段： 把所給問題的過程恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段，以便能按一定的次序去求解。描述階段的變量稱為階段變量，常用 k表示。 ? 階段的劃分，一般是根據(jù)時(shí)間和空間的自然特征來劃分，但要便于把問題的過程能轉(zhuǎn)化為多階段的決策過程，如例 1中可分為 4個(gè)階段來求解， k=1, 2, 3, 4。 2022/2/16 18 ? 2 、狀態(tài) 狀態(tài)表示每個(gè)階段開始時(shí)所處的自然狀況或客觀條件，它描述了研究問題過程的狀況，又稱為不可控因素。 ? 在例 1中，狀態(tài)就是某階段的出發(fā)位置，它既是該階段某支路的起點(diǎn)，又是前一階段某支路的終點(diǎn)。通常一個(gè)階段有若干個(gè)狀態(tài)，第一階段有一個(gè)狀態(tài)就是點(diǎn)①，第二階段有三個(gè)狀態(tài)，即點(diǎn)集合 {② ，③，④ }，一般第 k階段的狀態(tài)就是第 k階段所有始點(diǎn)的集合。 ? 描述過程狀態(tài)的變量稱為狀態(tài)變量 ,它可用一個(gè)數(shù) 、一組數(shù)或一向量 (多維的情形 )來描述。 2022/2/16 19 ? 常用 Sk表示第 k階段的狀態(tài)變量，例如例 1中第三階段有三個(gè)狀態(tài)，則狀態(tài)變量 S3可以取三個(gè)值，即⑤、⑥、⑦，點(diǎn)集合 {⑤