【正文】 , 1 1 1 2 2( ) ( ) , ( ) , , ( )n n np S u s u s u s?4．策略 策略是一個(gè)按順序排列的決策組成的集合。 常用 Dk(sk)表示第 k階段從狀態(tài) sk出發(fā)的允許決策集合，顯然有 uk（ sk） ∈ Dk(sk)。它是狀態(tài)變量的函數(shù)。它可用一個(gè)數(shù)、一組數(shù)或一向量來(lái)描述。在最優(yōu)控制中也稱(chēng)為控制。這個(gè)性質(zhì)稱(chēng)為無(wú)后效性 (即馬爾科夫性 )。 馬爾科夫性 這里所說(shuō)的狀態(tài)應(yīng)具有下面的性質(zhì)：如果某階段狀態(tài)給定后，則在這階段以后過(guò)程的發(fā)展不受這階段以前各段狀態(tài)的影響。有時(shí)為了方便起見(jiàn)，將該階段的狀態(tài)編上號(hào)碼 1， 2… 這時(shí)也可記S3＝｛ 1， 2， 3， 4｝。點(diǎn)集合｛ C1，C2， C3， C4｝就稱(chēng)為第三階段的可達(dá)狀態(tài)集合。 常用 Sk表示第 k階段的狀態(tài)變量 。 動(dòng)態(tài)規(guī)劃的基本概念 描述過(guò)程狀態(tài)的變量稱(chēng)為 狀態(tài)變量 。它既是該階段某支路的起點(diǎn)，又是前一階段某支路的終點(diǎn)。 動(dòng)態(tài)規(guī)劃的基本概念 ? 2．狀態(tài) ? 狀態(tài)表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件，它描述了研究問(wèn)題過(guò)程的狀況，又稱(chēng)不可控因素。階段的劃分，一般是根據(jù)時(shí)間和空間的自然特征來(lái)劃分，但要便于把問(wèn)題的過(guò)程能轉(zhuǎn)化為多階段決策的過(guò)程。 動(dòng)態(tài)規(guī)劃的基本概念 ? 1．階段 ? 把所給問(wèn)題的過(guò)程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段，以便能按一定的次序去求解。顯然，當(dāng)某階段的始點(diǎn)給定后，會(huì)影響后面各階段的行進(jìn)路線(xiàn)和整個(gè)路線(xiàn)的長(zhǎng)短，而后面各階段路線(xiàn)的發(fā)展不受這點(diǎn)以前各階段決策的影響。在第二階段，再?gòu)腂2點(diǎn)出發(fā)，有一個(gè)可供選擇的終點(diǎn)集合｛ C2， C3， C4｝；若選擇由 B2走至C2，則 C2就是第二階段的終點(diǎn)，同時(shí)又是第三階段的始點(diǎn)。在第一階段， A為起點(diǎn)，終點(diǎn)有 B B2兩個(gè)，因而這時(shí)走的路線(xiàn)有兩個(gè)選擇，一是走到 B1；一是走到 B2，若選擇走到 B2的決策，則 B2就是第一階段決策的結(jié)果?，F(xiàn)通過(guò)討論它的解法，說(shuō)明動(dòng)態(tài)規(guī)劃方法的基本思想，并闡述有關(guān)基本概念。要求制定一個(gè)五年計(jì)劃，在每年開(kāi)始時(shí)，決定如何重新分配完好的機(jī)器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量 g和投入生產(chǎn)的機(jī)器數(shù)量 u1的關(guān)系為 g=g(u1) 這時(shí)，機(jī)器的年完好率為 a，即如果年初完好機(jī)器的數(shù)量為 u，到年終時(shí)完好的機(jī)器就為 au， 0＜ a＜ 1，在低負(fù)荷下生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量 h和投入生產(chǎn)的機(jī)器數(shù)量 u2的關(guān)系為 h=h(u2) 相應(yīng)的機(jī)器年完好率為 b,0＜ b＜ 1。 這種把一個(gè)問(wèn)題可看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程就稱(chēng)為 多階段決策過(guò)程 ， 也稱(chēng)序貫決策過(guò)程 。 因此 ， 各個(gè)階段決策的選取不是任意確定的 ， 它 依賴(lài)于當(dāng)前面臨的狀態(tài) ， 又影響以后的發(fā)展 。 第 8章 動(dòng)態(tài)規(guī)劃的基本方法 ?第 1節(jié) 多階段決策過(guò)程及實(shí)例 ?第 2節(jié) 動(dòng)態(tài)規(guī)劃的基本概念和基本方程 ?第 3節(jié) 動(dòng)態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理 ?第 4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 第 1節(jié) 多階段決策過(guò)程及實(shí)例 ? 例 1 最短路線(xiàn)問(wèn)題 給定一個(gè)線(xiàn)路網(wǎng)絡(luò)，兩點(diǎn)之間連線(xiàn)上的數(shù)字表示兩點(diǎn)間的距離 (或費(fèi)用 )，試求一條由 A到 G的鋪管線(xiàn)路，使總距離為最短 (或總費(fèi)用最小 )。 ? 根據(jù)決策過(guò)程的演變是確定性的還是隨機(jī)性的，又可分為確定性決策過(guò)程和隨機(jī)性決策過(guò)程。 因而，它不像線(xiàn)性規(guī)劃那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，而 必須對(duì)具體問(wèn)題進(jìn)行具體分析處理。 ? 動(dòng)態(tài)規(guī)劃的應(yīng)用 ? 在工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)及軍事等部門(mén)中都有廣泛的應(yīng)用，并且獲得了顯著的效果。 1951年美國(guó)數(shù)學(xué)家貝爾曼 ()等人，根據(jù)一類(lèi)多階段決策問(wèn)題的特點(diǎn)，把多階段決策問(wèn)題變換為一系列 互相聯(lián)系的單階段 問(wèn)題，然后逐個(gè)加以解決。第七章 動(dòng)態(tài)規(guī)劃 ?動(dòng)態(tài)規(guī)劃的基本方法 ?動(dòng)態(tài)規(guī)劃應(yīng)用舉例 動(dòng)態(tài)規(guī)劃 ? 什么是動(dòng)態(tài)規(guī)劃 ? 解決 多階段決策過(guò)程最優(yōu)化 的一種數(shù)學(xué)方法。 ? 動(dòng)態(tài)規(guī)劃的形成 ? 產(chǎn)生于 20世紀(jì) 50年代。與此同時(shí)，他提出了解決這類(lèi)問(wèn)題的“最優(yōu)性原理”，研究了許多實(shí)際問(wèn)題，從而創(chuàng)建了解決最優(yōu)化問(wèn)題的一種新的方法 ——?jiǎng)討B(tài)規(guī)劃。 動(dòng)態(tài)規(guī)劃 ? 動(dòng)態(tài)規(guī)劃在企業(yè)管理中的主要應(yīng)用領(lǐng)域 ? 最優(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)題 ? 等等 動(dòng)態(tài)規(guī)劃是求解某類(lèi)問(wèn)題的一種方法，是考查問(wèn)題的一種途徑，而不是一種特殊算法 (如線(xiàn)性規(guī)劃是一種算法 )。 動(dòng)態(tài)規(guī)劃 ? 動(dòng)態(tài)規(guī)劃模型的分類(lèi) ? 根據(jù)多階段決策過(guò)程的時(shí)間參量是離散的還是連續(xù)變量，分為離散決策過(guò)程和連續(xù)決策過(guò)程。 ? 組合起來(lái)可分為 ? 離散確定性 ? 離散隨機(jī)性 ? 連續(xù)確定性 ? 連續(xù)隨機(jī)性 本書(shū)主要研究離散 確定性 決策過(guò)程。 第 1節(jié) 多階段決策過(guò)程及實(shí)例 ? 多階段決策過(guò)程 ? 在生產(chǎn)和科學(xué)實(shí)驗(yàn)中 ， 有一類(lèi)活動(dòng)的過(guò)程 ， 由于它的特殊性 ， 可將過(guò)程分為若干個(gè)互相聯(lián)系的階段 ， 在它的每一個(gè)階段都需要作出決策 ， 從而使整個(gè)過(guò)程達(dá)到最好的活動(dòng)效果 。 當(dāng)各個(gè)階段決策確定后 ， 就組成了一個(gè)決策序列 ，因而也就決定了整個(gè)過(guò)程的一條活動(dòng)路線(xiàn) 。 第 1節(jié) 多階段決策過(guò)程及實(shí)例 例 2 機(jī)器負(fù)荷分配問(wèn)題 某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。 假定開(kāi)始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為 s1。 第 2節(jié) 動(dòng)態(tài)規(guī)劃的基本概念和基本方程 例 1中求 A到 G的最短路線(xiàn)問(wèn)題是動(dòng)態(tài)規(guī)劃中一個(gè)典型例子。 由圖 82可知，從 A點(diǎn)到 G點(diǎn)可以分為 6個(gè)階段。它既是第一階段路線(xiàn)的終點(diǎn)，又是第二階段路線(xiàn)的始點(diǎn)。遞推下去可看到： 各個(gè)階段的決策不同，路線(xiàn)就不同 。故此問(wèn)題的要求是：在各個(gè)階段上選則一個(gè)恰當(dāng)?shù)臎Q策，使得由這些決策組成的一個(gè) 決策序列 所決定的一條路線(xiàn)是總路程最短的一條。描述階段的變量稱(chēng)為 階段變量 ，常用 k表示。如例 1可分為 6個(gè)階段來(lái)求解， k分別等于 6。在例 1中， 狀態(tài)就是某階段的出發(fā)位置 。通常一個(gè)階段有若干個(gè)狀態(tài)，第一階段有一個(gè)狀態(tài)就是點(diǎn) A，第二階段有兩個(gè)狀態(tài)，即點(diǎn)集合｛ B1， B2｝，一般第 k階段的狀態(tài)就是第 k階段所有始點(diǎn)的集合。它可用一個(gè)數(shù)、一組數(shù)或一向量 (多維情形 )來(lái)描述。如在例 1中第三階段有四個(gè)狀態(tài)，則狀態(tài)變量 Sk可取四個(gè)值，即