動態(tài)規(guī)劃方法

動態(tài)規(guī)劃方法2023/4/31第1頁，共39頁，2023年，2月20日，星期三

動態(tài)規(guī)劃（DynamicProgramming）同前面介紹過的線性規(guī)劃方法不同，它不是一種算法，而是考察問題的一種途徑。動態(tài)規(guī)劃是一種求解多階段決策問題的系統(tǒng)技術(shù)。由于動態(tài)規(guī)劃不是一種特定的算法，因而它不像線性規(guī)劃那樣有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，動態(tài)規(guī)劃必須對具體問題進(jìn)行具體的分析處理。動態(tài)規(guī)劃在自然科學(xué)和社會科學(xué)等各個領(lǐng)域都有著廣泛的應(yīng)用，并且獲得了顯著的效果。2023/4/32第2頁，共39頁，2023年，2月20日，星期三1最短路徑問題

2貝爾曼最優(yōu)化原理

3WinQSB軟件應(yīng)用動態(tài)規(guī)劃2023/4/33第3頁，共39頁，2023年，2月20日，星期三動態(tài)規(guī)劃是解決多階段決策問題的一種方法.1951年，美國數(shù)學(xué)家貝爾曼（R.Bellman，1920～1984）研究了一類多階段決策問題的特征，提出了解決這類問題的基本原理。在研究、解決了某些實(shí)際問題的基礎(chǔ)上，他于1957年出版了《動態(tài)規(guī)劃》這一名著。本章將簡要介紹動態(tài)規(guī)劃的思想方法及其應(yīng)用。2023/4/34第4頁，共39頁，2023年，2月20日，星期三——動態(tài)規(guī)劃解決問題的基本思路是：把整體比較復(fù)雜的大問題劃分成一系列較易于解決的小問題，通過逐個求解，最終取得整體最優(yōu)解。這種“分而治之，逐步調(diào)整”的方法，在一些比較難以解決的復(fù)雜問題中已經(jīng)顯示出優(yōu)越性。2023/4/35第5頁，共39頁，2023年，2月20日，星期三——所謂多階段決策過程是指這樣一類活動過程：一個決策過程可以分為若干個相互聯(lián)系的階段，每個階段都需要作一定的決策，但是每個階段最優(yōu)決策的選擇不能只是孤立地考慮本階段所取得的效果如何，必須把整個過程中的各個階段聯(lián)系起來考慮，要求所選擇的各個階段決策的集合——策略，能使整個過程的總效果達(dá)到最優(yōu)。2023/4/36第6頁，共39頁，2023年，2月20日，星期三1最短路徑問題

2023/4/37第7頁，共39頁，2023年，2月20日，星期三1最短路徑問題

【例1】設(shè)在E城的某公司要從S城運(yùn)送一批貨物，兩城之間有公路相連（見圖1(a)），其中是可以供選擇的途經(jīng)站點(diǎn)，各點(diǎn)連線上的數(shù)字表示相鄰站點(diǎn)間的距離?，F(xiàn)在的問題是選擇一條由S到E的路徑，使得所經(jīng)過的路徑最短。2023/4/38第8頁，共39頁，2023年，2月20日，星期三1最短路徑問題(a)(b)2023/4/39第9頁，共39頁，2023年，2月20日，星期三1最短路徑問題分析：如果用枚舉法，將有12條不同的路徑，每條路徑對應(yīng)一個由S到E的路徑距離，其中最小值所對應(yīng)的路徑即為最短路徑。本問題的最短路徑有3條，路程均為21個單位：第1條：第2條：第3條：2023/4/310第10頁，共39頁，2023年，2月20日，星期三1最短路徑問題當(dāng)段數(shù)很多時，枚舉法的計(jì)算量將極其龐大。現(xiàn)在換個思路，尋找由S到E的最短路徑。先把最短路徑問題所考慮的過程分為4個階段：由S到為第1階段；由

到為第2階段；由

到E為第4階段。由

到為第3階段；2023/4/311第11頁，共39頁，2023年，2月20日，星期三1最短路徑問題我們稱由某點(diǎn)到終點(diǎn)的階段數(shù)k為階段變量，如由到E的階段數(shù)為1（這時記由C到E的階段數(shù)為1，它與第1階段是不同的概念），由到E的階段數(shù)為2（這時記由B到E的階段數(shù)為2），等等?？梢婋A段變量的取值正好與實(shí)際進(jìn)行的階段相反（圖（b））。(b)2023/4/312第12頁，共39頁，2023年，2月20日，星期三1最短路徑問題在任一階段開始時所處的位置稱為狀態(tài)變量，在階段k的狀態(tài)變量記為，例如為階段3的狀態(tài)變量，可以取為中任意一個。當(dāng)某一個狀態(tài)給定后，需要做出決策以確定下一步的狀態(tài)，描述決策的變量稱為決策變量，在階段k的決策變量記為。例如在階段2的狀態(tài)取時的決策變量記為，可取為。若，則表示由到，從而決定了下一步的狀態(tài)是。2023/4/313第13頁，共39頁，2023年，2月20日，星期三1最短路徑問題為了尋找由起點(diǎn)S到E終點(diǎn)的最短路徑，我們考察前面用枚舉法找到的第1條最短路徑：容易看出：子路徑“”也應(yīng)是從出發(fā)到終點(diǎn)E的所有路徑中最短的一條。這個現(xiàn)象啟發(fā)我們從階段1開始，逐段逆向地求出各點(diǎn)到終點(diǎn)E的最短路徑，最后求得由起點(diǎn)S到終點(diǎn)E的最短路徑，這就是動態(tài)規(guī)劃的基本思想。2023/4/314第14頁，共39頁，2023年，2月20日，星期三1最短路徑問題

以表示在階段k的狀態(tài)變量為、決策變量為時點(diǎn)與間的距離；記為在階段k由點(diǎn)到終點(diǎn)E的最短路徑的長度。本例中要求的是。在階段1：可以取中任意一個，對應(yīng)的有在階段2：可以取中任意一個，對應(yīng)的有2023/4/315第15頁，共39頁，2023年，2月20日，星期三1最短路徑問題從出發(fā)到終點(diǎn)E最短路徑為“”，決策變量；在階段3：可以取中任意一個，對應(yīng)的有從出發(fā)到終點(diǎn)E最短路徑為“”，決策變量；2023/4/316第16頁，共39頁，2023年，2月20日，星期三1最短路徑問題從出發(fā)到終點(diǎn)E最短路徑為“”，決策變量；從出發(fā)到終點(diǎn)E最短路徑為“”，決策變量；從出發(fā)到終點(diǎn)E最短路徑為“”，決策變量或；最后，在階段4：只可以取S，于是2023/4/317第17頁，共39頁，2023年，2月20日，星期三1最短路徑問題因此，由起點(diǎn)S到終點(diǎn)E的最短路徑為最短路徑長度為21單位長度。2023/4/318第18頁，共39頁，2023年，2月20日，星期三1最短路徑問題由上述計(jì)算過程可知，對有n個階段的最短路徑問題，可以逐段逆向地求出各點(diǎn)到終點(diǎn)的最短路徑，且在求解的每一步都利用階段k和階段k-1間的遞推關(guān)系：此關(guān)系被稱為求最短路徑的動態(tài)規(guī)劃基本方程。求解最短路徑問題的過程，本質(zhì)上是解上述基本方程的過程。2023/4/319第19頁，共39頁，2023年，2月20日，星期三2貝爾曼最優(yōu)化原理

2023/4/320第20頁，共39頁，2023年，2月20日，星期三2貝爾曼最優(yōu)化原理

將求解最短路徑問題的思路推廣到一般多階段決策問題時，可以表述成：貝爾曼最優(yōu)化原理：一個過程的最優(yōu)策略具有這樣的性質(zhì)，即無論其初始狀態(tài)和初始決策如何，今后的諸決策，對以第一個決策所形成的狀態(tài)作為初始狀態(tài)的過程而言，必須構(gòu)成最優(yōu)策略。這個原理是動態(tài)規(guī)劃的理論基礎(chǔ)。2023/4/321第21頁，共39頁，2023年，2月20日，星期三2貝爾曼最優(yōu)化原理應(yīng)用動態(tài)規(guī)劃方法解決一般多階段決策問題時，其求解過程如下：（1）把實(shí)際問題適當(dāng)?shù)貏澐殖蒶個階段，階段變量為；（2）在每個階段k，確定狀態(tài)變量為及此階段可能的狀態(tài)集合；（3）確定決策變量及每個階段k的允許決策集合；（4）列出遞推關(guān)系即動態(tài)規(guī)劃基本方程并計(jì)算：2023/4/322第22頁，共39頁，2023年，2月20日，星期三2貝爾曼最優(yōu)化原理【例2】（石油輸送管道鋪設(shè)優(yōu)選問題）某石油公司計(jì)劃從A地到E地鋪設(shè)一條石油輸送管道，為此在A地與E地之間必須建立三個油泵加壓站，如圖2所示，其中分別為必須建站的地區(qū)，而分別為可供選擇的各站點(diǎn)，各點(diǎn)連線上的數(shù)字表示相鄰站點(diǎn)間鋪設(shè)輸送管道所需費(fèi)用.問：如何鋪設(shè)石油輸送管道，能使總費(fèi)用最少？2023/4/323第23頁，共39頁，2023年，2月20日，星期三2貝爾曼最優(yōu)化原理(a)(b)2023/4/324第24頁，共39頁，2023年，2月20日，星期三2貝爾曼最優(yōu)化原理解劃分成4個階段：階段變量依次為4，3，2，1，如圖2所示.設(shè)階段k的狀態(tài)變量為。在階段1：在階段2：可以取中任意一個，對應(yīng)的有2023/4/325第25頁，共39頁，2023年，2月20日，星期三2貝爾曼最優(yōu)化原理從出發(fā)到終點(diǎn)E最短路徑為“”，決策變量；從出發(fā)到終點(diǎn)E最短路徑為“”，決策變量；從出發(fā)到終點(diǎn)E最短路徑為“”，決策變量；2023/4/326第26頁，共39頁，2023年，2月20日，星期三2貝爾曼最優(yōu)化原理在階段3：可以取中任意一個，于是2023/4/327第27頁，共39頁，2023年，2月20日，星期三2貝爾曼最優(yōu)化原理從出發(fā)到終點(diǎn)E最短路徑為“”或決策變量或；從出發(fā)到終點(diǎn)E最短路徑為“”，決策變量；從出發(fā)到終點(diǎn)E最短路徑為“”或決策變量或；在階段4：2023/4/328第28頁，共39頁，2023年，2月20日，星期三2貝爾曼最優(yōu)化原理因此，由起點(diǎn)A到終點(diǎn)E的費(fèi)用最少路徑有3條：此3條路徑對應(yīng)的總費(fèi)用均為11單位金額。2023/4/329第29頁，共39頁，2023年，2月20日，星期三2貝爾曼最優(yōu)化原理動態(tài)規(guī)劃為我們提供了一種優(yōu)秀的決策思想：戰(zhàn)略上追求全局優(yōu)化，戰(zhàn)術(shù)上穩(wěn)扎穩(wěn)打、步步為營。這深刻地揭示了局部與全局的統(tǒng)一關(guān)系。動態(tài)規(guī)劃在實(shí)際中得到廣泛應(yīng)用，如可應(yīng)用于背包問題、資源分配問題、生產(chǎn)與存儲問題、設(shè)備更新問題等。需要指出的是：動態(tài)規(guī)劃是一種求解思路，注重決策過程，而不是一種算法，不同的問題模型各異。2023/4/330第30頁，共39頁，2023年，2月20日，星期三3WinQSB軟件應(yīng)用2023/4/331第31頁，共39頁，2023年，2月20日，星期三本節(jié)結(jié)合最短路徑問題、背包問題介紹WinQSB軟件的應(yīng)用，其他問題的求解可參考本章參考文獻(xiàn).求解動態(tài)規(guī)劃問題，需要調(diào)用WinQSB軟件中的子程序“DynamicProgramming”.方法：點(diǎn)擊“開始”“程序”“WinQSB”“DynamicProgramming”,屏幕顯示如圖3.3所示.該程序有3個子模塊：最短路問題（StagecoachProblem）,背包問題（KnapsackProblem）,生產(chǎn)與存儲問題（ProductionandInventoryScheduling）.

3WinQSB軟件應(yīng)用2023/4/332第32頁，共39頁，2023年，2月20日，星期三

3WinQSB軟件應(yīng)用2023/4/333第33頁，共39頁，2023年，2月20日，星期三1.最短路問題【例3】用WinQSB軟件求解例1.解（1）調(diào)用WinQSB軟件中的子程序“DynamicProgramming”，建立新問題.在圖3.3中選擇第一項(xiàng)，輸入標(biāo)題和站點(diǎn)數(shù).（2）輸入數(shù)據(jù).按照圖3.1從左到右將相鄰站點(diǎn)間的距離輸入表3.1中，其中表示圖3.1中從左到右的第k

個站點(diǎn)，k=1,2,…,9表3.1

3WinQSB軟件應(yīng)用2023/4/334第34頁，共39頁，2023年，2月20日，星期三（3）求解.點(diǎn)擊菜單欄“SolveandAnalyze”“SolvetheProblem”,得到圖3.4.再點(diǎn)擊“Solve”鍵，得到計(jì)算結(jié)果，見表3.2.可見由起點(diǎn)到終點(diǎn)的最短路徑為

3WinQSB軟件應(yīng)用2023/4/335第35頁，共39頁，2023年，2月20日，星期三表2

3WinQSB軟件應(yīng)用2023/4/336第36頁，共39頁，2023年，2月20日，星期三2.背包問題背包問題的一般提法是：設(shè)有一位旅行者攜帶背包去登山，