【正文】 組成的集合。Tk稱為狀態(tài)轉(zhuǎn)移函數(shù)。它表示從第 k階段的狀態(tài) sk開始到第 n階段 的終止?fàn)顟B(tài)的過(guò)程，采取最優(yōu)策略所得到的指標(biāo)函數(shù)值。所以，動(dòng)態(tài)規(guī)劃的方法是從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易疃搪肪€的一種方法。 動(dòng)態(tài)規(guī)劃的基本思想和基本方程 動(dòng)態(tài)規(guī)劃方法基本思想歸納： 1. 動(dòng)態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件 (簡(jiǎn)言之為基本方程 )。計(jì)算例 1若用窮舉法，就要對(duì) 48條路線進(jìn)行比較，運(yùn)算在計(jì)算機(jī)上進(jìn)行時(shí)，比較運(yùn)算要進(jìn)行 47次；求各條路線的距離，即使用逐段累加方法，也要進(jìn)行 6+12+24+48+48＝ 138次加法運(yùn)算。 動(dòng)態(tài)規(guī)劃的基本思想和基本方程 建立動(dòng)態(tài)規(guī)劃模型的五個(gè)要點(diǎn)： (1) 將問(wèn)題的過(guò)程劃分成恰當(dāng)?shù)碾A段； (2) 正確選擇狀態(tài)變量 sk，使它既能描述過(guò)程的演變，又要滿足無(wú)后效性； (3) 確定決策變量 uk及每階段的允許決策集合 Dk(sk)； (4) 正確寫出狀態(tài)轉(zhuǎn)移方程； (5) 正確寫出指標(biāo)函數(shù)的關(guān)系，它應(yīng)滿足下面性質(zhì)： ① 是定義在全過(guò)程和所有后部子過(guò)程上的數(shù)量函數(shù)； ② 要具有可分離性，并滿足遞推關(guān)系。 ?動(dòng)態(tài)規(guī)劃研究的問(wèn)題與時(shí)間有關(guān) ，研究具有多階段決策過(guò)程的一類問(wèn)題，將問(wèn)題的整體按時(shí)間或空間的特征分成若干個(gè)前后銜接的時(shí)空階段，把多階段決策問(wèn)題表示為前后有關(guān)聯(lián)的一系列單階段決策問(wèn)題，然后逐個(gè)加以解決，從而求出整個(gè)問(wèn)題的最優(yōu)決策序列。 令最優(yōu)值函數(shù) fk(sk)表示為第 k階段的初始狀態(tài)為 sk，從 k階段到 3階段所得到的最大值。 第 4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 1()kkfs?2 1 2 2 3 3 3 4,s x s x s s x s c? ? ? ? ? ?1 2 2 3 3 4, 0 , 0x s x s x s? ? ? ? ?例 4 將例 3用順推解法解之。而 故 的最大值點(diǎn)在 處，所以得 及相應(yīng)的最優(yōu)解 第 4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 3323 3 30 9 0 9m a x ( ) m a x 2 1 2ssf s s? ? ? ? ??????3 9s ? 33()fs21 ( 9 ) 2 9 1 2 1 7 4f ? ? ? ?**1 2 30 , 0 , 9x x x? ? ?1m a x ( 9) 174Ff??由于 s3不知道，故須再對(duì) s3求一次極值，即 顯然，當(dāng) 時(shí) 才能達(dá)到最大值。因而 的最大值必在兩個(gè)端點(diǎn)上選取。但應(yīng)注意，這里是在上述狀態(tài)變量和決策變量的記法不變的情況下考慮的。 第 4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 ????????????,1i,0x0)(ccxxxxxxzm a xi3213221例 3 用逆推解法求解下面問(wèn)題 解 : 按問(wèn)題的變量個(gè)數(shù)劃分階段，把它看作為一個(gè)三階段決策問(wèn)題 。 ?不同點(diǎn) ?線性規(guī)劃和非線性規(guī)劃研究的問(wèn)題通常與時(shí)間無(wú)關(guān)，故又稱為靜態(tài)規(guī)劃。在逆序 (或順序 )解法中，我們得到的不僅僅是由 A點(diǎn) (或 G點(diǎn) )出發(fā)到 G點(diǎn) (或 A點(diǎn) )的最短路線及相應(yīng)的最短距離，而且得到了從所有各中間點(diǎn)出發(fā)到 G點(diǎn) (或 A點(diǎn) )的最短路線及相應(yīng)的距離。 如例 1最短路線問(wèn)題，初始狀態(tài) A已知，則按下面箭頭所指的方向逐次變換有 從而可得最優(yōu)策略為｛ u1(A),u2(B1),…, u0’(F2)｝，相應(yīng)的最短路線為 已知）()()()(21239。 動(dòng)態(tài)規(guī)劃的基本思想和基本方程 ? ?ku1 1 2 1 2 3 2 1 4 1 2 5 2 2 6 2( ) , ( ) , ( ) , ( ) , ( ) , ( )u A B u B C u C D u D E u E F u F G? ? ? ? ? ?1 2 1 2 2A B C D E F G? ? ? ? ? ?為了找出最短路線，再按計(jì)算的順序反推之 ，可求出最優(yōu)決策函數(shù)序列 ，即由 組成一個(gè)最優(yōu)策略。這與假設(shè)矛盾，是不可能的。即 其中 表示第 j階段的階段指標(biāo)，這時(shí)上式可寫成 (2) 過(guò)程和它的任一子過(guò)程的指標(biāo)是它所包含的 各階段的指標(biāo)的乘積 。即 sk+1的值隨 sk和 uk的值變化而變化。 常用 Dk(sk)表示第 k階段從狀態(tài) sk出發(fā)的允許決策集合，顯然有 uk（ sk） ∈ Dk(sk)。這個(gè)性質(zhì)稱為無(wú)后效性 (即馬爾科夫性 )。 常用 Sk表示第 k階段的狀態(tài)變量 。階段的劃分，一般是根據(jù)時(shí)間和空間的自然特征來(lái)劃分，但要便于把問(wèn)題的過(guò)程能轉(zhuǎn)化為多階段決策的過(guò)程。在第一階段， A為起點(diǎn)，終點(diǎn)有 B B2兩個(gè)，因而這時(shí)走的路線有兩個(gè)選擇，一是走到 B1；一是走到 B2，若選擇走到 B2的決策，則 B2就是第一階段決策的結(jié)果。 這種把一個(gè)問(wèn)題可看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程就稱為 多階段決策過(guò)程 ， 也稱序貫決策過(guò)程 。 因而，它不像線性規(guī)劃那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，而 必須對(duì)具體問(wèn)題進(jìn)行具體分析處理。 ? 動(dòng)態(tài)規(guī)劃的形成 ? 產(chǎn)生于 20世紀(jì) 50年代。 ? 組合起來(lái)可分為 ? 離散確定性 ? 離散隨機(jī)性 ? 連續(xù)確定性 ? 連續(xù)隨機(jī)性 本書主要研究離散 確定性 決策過(guò)程。 假定開始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為 s1。遞推下去可看到： 各個(gè)階段的決策不同，路線就不同 。在例 1中， 狀態(tài)就是某階段的出發(fā)位置 。記為 S3＝｛ C1， C2， C3，C4｝。描述決策的變量，稱為決策變量。由過(guò)程的第 k階段開始到終止?fàn)顟B(tài)為止的過(guò)程，稱為 問(wèn)題的后部子過(guò)程 。如例 1中，狀態(tài)轉(zhuǎn)移方程為 動(dòng)態(tài)規(guī)劃的基本概念 , , 1 1( , , , , ) , 1 , 2 , ,k n k n k k k nV V s u s s k n????6．指標(biāo)函數(shù)和最優(yōu)值函數(shù) 用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的一種數(shù)量指標(biāo)，稱為指標(biāo)函數(shù)。即 “opt”是最優(yōu)化 (optimization)的縮寫，可根據(jù)題意而取 min或 max。 下面按照動(dòng)態(tài)規(guī)劃的方法，將例 1從最后一段開始計(jì)算，由后向前逐步推移至 A點(diǎn)。要做到這一點(diǎn)，必須先將問(wèn)題的過(guò)程分成幾個(gè)相互聯(lián)系的階段，恰當(dāng)?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個(gè)大問(wèn)題化成 一族同類型的子問(wèn)題 ，然后逐個(gè)求解。用動(dòng)態(tài)規(guī)劃方法來(lái)計(jì)算，比較運(yùn)算 (從 k=5段開始向前算 )共進(jìn)行 3+3+4+4+1＝ 15次。即 動(dòng)態(tài)規(guī)劃的基本思想和基本方程 1,1 1 1 , 1 1 ,( ) o p t ( , )knk k k n k k npf s V s p?? ? ? ? ??