動態(tài)規(guī)劃講解+例子-課件

動態(tài)規(guī)劃講解+例子

動態(tài)規(guī)劃的基本概念和思想最短路徑問題投資分配問題背包問題排序問題1動態(tài)規(guī)劃講解+例子動態(tài)規(guī)劃的基本概念和思想1動態(tài)規(guī)劃是運籌學的一個分支，是求解多階段決策過程最優(yōu)化問題的數(shù)學方法。

動態(tài)規(guī)劃在經(jīng)濟管理、工程技術、工農(nóng)業(yè)生產(chǎn)及軍事部門中都有著廣泛的應用，并且獲得了顯著的效果。

學習動態(tài)規(guī)劃，我們首先要了解多階段決策問題。2動態(tài)規(guī)劃是運籌學的一個分支，是求解多階段決策過程最優(yōu)化問題的精品資料3精品資料3你怎么稱呼老師？如果老師最后沒有總結(jié)一節(jié)課的重點的難點，你是否會認為老師的教學方法需要改進？你所經(jīng)歷的課堂，是講座式還是討論式？教師的教鞭“不怕太陽曬，也不怕那風雨狂，只怕先生罵我笨，沒有學問無顏見爹娘……”“太陽當空照，花兒對我笑，小鳥說早早早……”44最短路徑問題：給定一個交通網(wǎng)絡圖如下，其中兩點之間的數(shù)字表示距離（或運費），試求從A點到G點的最短距離（總運輸費用最?。?23456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687636853384222133352566435最短路徑問題：給定一個交通網(wǎng)絡圖如下，其中兩點之間的數(shù)字表示背包問題

有一個徒步旅行者，其可攜帶物品重量的限度為a公斤，設有n

種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應如何選擇攜帶的物品（各幾件），使所起作用（使用價值）最大？物品12…j…n重量（公斤/件）a1

a2

…

aj…

an每件使用價值c1

c2

…cj…

cn

類似的還有工廠里的下料問題、運輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。6背包問題有一個徒步旅行者，其可攜帶物品重量的限度為a公

生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計劃。機器負荷分配問題：某種機器可以在高低兩種不同的負荷下進行生產(chǎn)。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同的負荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達到最高。航天飛機飛行控制問題：由于航天飛機的運動的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機飛行在不同環(huán)境中的情況，不斷地決定航天飛機的飛行方向和速度（狀態(tài)），使之能最省燃料和完成飛行任務（如軟著陸）。7生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因根據(jù)過程的特性可以將過程按空間、時間等標志分為若干個互相聯(lián)系又互相區(qū)別的階段。在每一個階段都需要做出決策，從而使整個過程達到最好的效果。各個階段決策的選取不是任意確定的，它依賴于當前面臨的狀態(tài)，又影響以后的發(fā)展。當各個階段的決策確定后，就組成了一個決策序列，因而也就決定了整個過程的一條活動路線，這樣的一個前后關聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策問題。多階段決策過程的特點：8根據(jù)過程的特性可以將過程按空間、時間等標志分為若干個互相聯(lián)系針對多階段決策過程的最優(yōu)化問題，美國數(shù)學家Bellman等人在20世紀50年代初提出了著名的最優(yōu)化原理，把多階段決策問題轉(zhuǎn)化為一系列單階段最優(yōu)化問題，從而逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法：動態(tài)規(guī)劃。對最佳路徑（最佳決策過程）所經(jīng)過的各個階段，其中每個階段始點到全過程終點的路徑，必定是該階段始點到全過程終點的一切可能路徑中的最佳路徑（最優(yōu)決策），這就是Bellman提出的著名的最優(yōu)化原理。簡言之，一個最優(yōu)策略的子策略必然也是最優(yōu)的。Bellman在1957年出版的《DynamicProgramming》是動態(tài)規(guī)劃領域的第一本著作。9針對多階段決策過程的最優(yōu)化問題，美國數(shù)學家Bellman等人例1、從A

地到E

地要鋪設一條煤氣管道,其中需經(jīng)過三級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應該選擇什么路線，使總距離最短？

動態(tài)規(guī)劃講解+例子AB2B1B3C1C3D1D2E52141126101043121113965810521C210例1、從A地到E地要鋪設一條煤氣管道,其中需經(jīng)過三級中間

解：整個計算過程分四個階段，從最后一個階段開始。

第四階段（D→E）：D有兩條路線到終點E

。顯然有AB2B1B3C1C3D1D2E52141126101043121113965810521C211解：整個計算過程分四個階段，從最后一個階段開始。第四階首先考慮經(jīng)過的兩條路線第三階段（C→D）：C到D有6條路線。(最短路線為)AB2B1B3C1C3D1D2E5214126101043121113965810521C212首先考慮經(jīng)過的兩條路線第三階段（C→D）：CAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)考慮經(jīng)過的兩條路線13AB2B1B3C1C3D1D2E52141261010431AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)考慮經(jīng)過的兩條路線14AB2B1B3C1C3D1D2E52141261010431AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)第二階段（B→C）：B到C有9條路線。首先考慮經(jīng)過的3條路線15AB2B1B3C1C3D1D2E52141261010431AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)考慮經(jīng)過的3條路線16AB2B1B3C1C3D1D2E52141261010431AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)考慮經(jīng)過的3條路線17AB2B1B3C1C3D1D2E52141261010431AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)第一階段（A→B）：A到B有3條路線。

（最短距離為19）18AB2B1B3C1C3D1D2E52141261010431

動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點在于，它可以把一個n

維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。必須對具體問題進行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應的模型，然后再用動態(tài)規(guī)劃方法去求解。即在系統(tǒng)發(fā)展的不同時刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，不斷地做出決策；動態(tài)決策問題的特點：系統(tǒng)所處的狀態(tài)和時刻是進行決策的重要因素；找到不同時刻的最優(yōu)決策以及整個過程的最優(yōu)策略。19動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種

動態(tài)規(guī)劃方法的關鍵：在于正確地寫出基本的遞推關系式和恰當?shù)倪吔鐥l件（簡稱基本方程）。要做到這一點，就必須將問題的過程分成幾個相互聯(lián)系的階段，恰當?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個大問題轉(zhuǎn)化成一組同類型的子問題，然后逐個求解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。20動態(tài)規(guī)劃方法的關鍵：在于正確地寫出基本的遞推

2、在多階段決策過程中，動態(tài)規(guī)劃方法是既把當前一段和未來一段分開，又把當前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的.

最優(yōu)化原理：作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略。也就是說，一個最優(yōu)策略的子策略也是最優(yōu)的。3、在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐段變換得到，從而確定了最優(yōu)路線。212、在多階段決策過程中，動態(tài)規(guī)劃方法是既把當前一段動態(tài)規(guī)劃求解的多階段問題的特點：每個階段的最優(yōu)決策過程只與本階段的初始狀態(tài)有關，而與以前各階段的決策（即為了到達本階段的初始狀態(tài)而采用哪組決策路線無關）。換言之，本階段之前的狀態(tài)與決策，只是通過系統(tǒng)在本階段所處的初始狀態(tài)來影響本階段及以后各個階段的決策?；蛘哒f，系統(tǒng)過程的歷史只能通過系統(tǒng)現(xiàn)階段的狀態(tài)去影響系統(tǒng)的未來。具有這種性質(zhì)的狀態(tài)稱為無后效性（即馬爾科夫性）狀態(tài)。動態(tài)規(guī)劃方法只適用于求解具有無后效性狀態(tài)的多階段決策問題。22動態(tài)規(guī)劃求解的多階段問題的特點：22

現(xiàn)有數(shù)量為a（萬元）的資金，計劃分配給n個工廠,用于擴大再生產(chǎn)。假設：xi為分配給第i個工廠的資金數(shù)量（萬元）；gi(xi)為第i個工廠得到資金后提供的利潤值（萬元）。問題：如何確定各工廠的資金數(shù)，使得總的利潤為最大。據(jù)此，有下式：動態(tài)規(guī)劃講解+例子23現(xiàn)有數(shù)量為a（萬元）的資金，計劃分配給n個工廠,

令：fk(x)表示以數(shù)量為x的資金分配給前k個工廠，所得到的最大利潤值。用動態(tài)規(guī)劃求解，就是求

fn(a)的問題。

當k=1時，f1(x)=g1(x)（因為只給一個工廠）

當1＜k≤n時，其遞推關系如下：設：y為分給第k個工廠的資金（其中0≤y≤x），此時還剩x

－y（萬元）的資金需要分配給前k－1個工廠,如果采取最優(yōu)策略，則得到的最大利潤為fk－1(x－y),因此總的利潤為：

gk(y)＋fk－1(x－y)24令：fk(x)表示以數(shù)量為x的資金分配給前k

如果a是以萬元為資金分配單位，則式中的y只取非負整數(shù)0，1，2，…，x。上式可變?yōu)椋核?，根?jù)動態(tài)規(guī)劃的最優(yōu)化原理，有下式：25如果a是以萬元為資金分配單位，則式中的y

例2：設國家撥給60萬元投資，供四個工廠擴建使用，每個工廠擴建后的利潤與投資額的大小有關，投資后的利潤函數(shù)如下表所示。

投資利潤0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依據(jù)題意，是要求f4(60)。26例2：設國家撥給60萬元投資，供四個工廠擴建使用，每個按順序解法計算。第一階段：求f1(x)。顯然有f1(x)＝g1(x)，得到下表

投資利潤0102030405060f1(x)＝

g1(x)0205065808585最優(yōu)策略0102030405060第二階段：求f2(x)。此時需考慮第一、第二個工廠如何進行投資分配，以取得最大的總利潤。27按順序解法計算。投資01最優(yōu)策略為（40，20），此時最大利潤為120萬元。同理可求得其它f2(x)的值。28最優(yōu)策略為（40，20），此時最大利潤為120萬元。同理可求最優(yōu)策略為（30，20），此時最大利潤為105萬元。29最優(yōu)策略為（30，20），此時最大利潤為105萬元。29最優(yōu)策略為（20，20），此時最大利潤為90萬元。最優(yōu)策略為（20，10），此時最大利潤為70萬元。30最優(yōu)策略為（20，20），此時最大利潤為90萬元。最優(yōu)策略為最優(yōu)策略為（10，0）或（0，10），此時最大利潤為20萬元。

f2(0)＝0。最優(yōu)策略為（0，0），最大利潤為0萬元。得到下表最優(yōu)策略為（20，0），此時最大利潤為50萬元。31最優(yōu)策略為（10，0）或（0，10），此時最大利潤

投資利潤0102030405060f2(x)020507090105120最優(yōu)策略(0,0)(10,0)(0,10)(20,0)(20,10)(20,20)(30,20)(40,20)第三階段：求f3(x)。此時需考慮第一、第二及第三個工廠如何進行投資分配，以取得最大的總利潤。32投資010203040最優(yōu)策略為（20，10，30），最大利潤為155萬元。同理可求得其它f3(x)的值。得到下表33最優(yōu)策略為（20，10，30），最大利潤為155萬元。同理可

投資利潤0102030405060f3(x)0256085110135155最優(yōu)策略(0,0,0)(0,0,10)(0,0,20)(0,0,30)(20,0,20)(20,0,30)(20,10,30)第四階段：求f4(60)。即問題的最優(yōu)策略。34投資0102030405060f3(x)02560最優(yōu)策略為（20，0，30，10），最大利潤為160萬元。35最優(yōu)策略為（20，0，30，10），最大利潤為160萬元。3

有一個徒步旅行者，其可攜帶物品重量的限度為a公斤，設有n

種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應如何選擇攜帶的物品（各幾件），使所起作用（使用價值）最大？物品12…j…n重量（公斤/件）a1

a2

…

aj…

an每件使用價值c1

c2

…cj…

cn

這就是背包問題。類似的還有工廠里的下料問題、運輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。動態(tài)規(guī)劃講解+例子36有一個徒步旅行者，其可攜帶物品重量的限度為a公斤，設設xj為第j種物品的裝件數(shù)（非負整數(shù)）則問題的數(shù)學模型如下：用動態(tài)規(guī)劃方法求解，令

fk(y)=總重量不超過

y公斤，包中只裝有前k種物品時的最大使用價值。其中y≥0，k

＝1,2,…,n。所以問題就是求fn(a)37設xj為第j種物品的裝件數(shù)（非負整數(shù)）則問題的數(shù)學模其遞推關系式為：當k=1時，有：38其遞推關系式為：當k=1時，有：38例3：求下面背包問題的最優(yōu)解物品(xi)

x1

x2

x3重量（ai）325使用價值8512解：a＝5，問題是求f3(5)39例3：求下面背包問題的最優(yōu)解物品(xi)x1物品(xi)

x1

x2

x3重量（ai）325使用價值851240物品(xi)x1x2x3重物品(xi)

x1

x2

x3重量（ai）325使用價值851241物品(xi)x1x2x3重物品(xi)

x1

x2

x3重量（ai）325使用價值851242物品(xi)x1x2x3重4343所以，最優(yōu)解為X＝（1.1.0），最優(yōu)值為Z=13?？偨Y(jié)：解動態(tài)規(guī)劃的一般方法:從終點逐段向始點方向?qū)ふ易钚?大)的方法。44所以，最優(yōu)解為X＝（1.1.0），最優(yōu)值為Z

排序問題指n種零件經(jīng)過不同設備加工是的順序問題。其目的是使加工周期為最短。1、n×1排序問題

即n種零件經(jīng)過1種設備進行加工，如何安排？14682023交貨日期（d）45173加工時間（t）零件代號例5.1動態(tài)規(guī)劃講解+例子45排序問題指n種零件經(jīng)過不同設備加工是的順序問題。

（1）平均通過設備的時間最小

按零件加工時間非負次序排列順序，其時間最小。（即將加工時間由小到大排列即可）零件加工順序

工序時間13457