運籌學課件(動態(tài)規(guī)劃)

動態(tài)規(guī)劃(Dynamicprogramming)動態(tài)規(guī)劃的基本思想最短路徑問題投資分配問題背包問題

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

需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。必須對具體問題進行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應的模型，然后再用動態(tài)規(guī)劃方法去求解。一、動態(tài)規(guī)劃的基本思想（一）、基本概念1、階段：描述階段的變量成為階段變量。把一個問題的過程，恰當?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便于按一定的次序去求解。階段的劃分，一般是根據(jù)時間和空間的自然特征來進行的，但要便于問題轉(zhuǎn)化為多階段決策。2、狀態(tài)：表示每個階段開始所處的自然狀況或客觀條件。通常一個階段有若干個狀態(tài)，描述過程狀態(tài)的變量稱為狀態(tài)變量，可用一個數(shù)、一組數(shù)或一向量（多維情形）來描述。3、決策：表示當過程處于某一階段的某個狀態(tài)時，可以作出不同的決定，從而確定下一階段的狀態(tài)?？捎靡粋€數(shù)、一組數(shù)或一向量（多維情形）來描述。4、策略：是一個按順序排列的決策組成的集合。在實際問題中，可供選擇的策略有一定的范圍，成為允許策略集合。從允許策略集合中找出達到最優(yōu)效果的策略稱為最優(yōu)策略。

5、狀態(tài)轉(zhuǎn)移方程：是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程，描述了狀態(tài)轉(zhuǎn)移規(guī)律。

6、指標函數(shù)和最優(yōu)值函數(shù)：用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標，為指標函數(shù)。指標函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)。在不同的問題中，指標函數(shù)的含義是不同的，它可能是距離、利潤、成本、產(chǎn)量或資源消耗等。（二）、動態(tài)規(guī)劃的基本思想1、動態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當?shù)倪吔鐥l件（簡稱基本方程）。要做到這一點，就必須將問題的過程分成幾個相互聯(lián)系的階段，恰當?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個大問題轉(zhuǎn)化成一組同類型的子問題，然后逐個求解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。2、在多階段決策過程中，動態(tài)規(guī)劃方法是既把當前一段和未來一段分開，又把當前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的.3、在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐段變換得到，從而確定了最優(yōu)路線。

最優(yōu)化原理：作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略?！币簿褪钦f，一個最優(yōu)策略的子策略也是最優(yōu)的。（三）、建立動態(tài)規(guī)劃模型的步驟1、劃分階段劃分階段是運用動態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時間或空間先后順序，將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)問題要人為地賦予“時間”概念，以便劃分階段。2、正確選擇狀態(tài)變量選擇變量既要能確切描述過程演變又要滿足無后效性，而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從過程演變的特點中尋找。3、確定決策變量及允許決策集合通常選擇所求解問題的關(guān)鍵變量作為決策變量，同時要給出決策變量的取值范圍，即確定允許決策集合。4、確定狀態(tài)轉(zhuǎn)移方程根據(jù)k階段狀態(tài)變量和決策變量，寫出k+1階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應當具有遞推關(guān)系。5、確定階段指標函數(shù)和最優(yōu)指標函數(shù)，建立動態(tài)規(guī)劃基本方程階段指標函數(shù)是指第k

階段的收益，最優(yōu)指標函數(shù)是指從第k階段狀態(tài)出發(fā)到第n階段末所獲得收益的最優(yōu)值，最后寫出動態(tài)規(guī)劃基本方程。以上五步是建立動態(tài)規(guī)劃數(shù)學模型的一般步驟。由于動態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動態(tài)規(guī)劃模型沒有統(tǒng)一的模式，建模時必須根據(jù)具體問題具體分析，只有通過不斷實踐總結(jié)，才能較好掌握建模方法與技巧。二、最短路徑問題例一、從A

地到D

地要鋪設(shè)一條煤氣管道,其中需經(jīng)過兩級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應該選擇什么路線，使總距離最短？AB1B2C1C2C3D24333321114解：整個計算過程分三個階段，從最后一個階段開始。第一階段（C→D）：C

有三條路線到終點D。

AB1B2C1C2C3D24333321114DC1C2C3顯然有f1(C1)

=1；

f1(C2)

=3；

f1(C3)

=4

d(B1,C1)+f1(C1)

3+1f2(B1)=mind(B1,C2

)+f1(C2)

=min3+3

d(B1,C3)+f1(C3)1+44=min6=45第二階段（B→C）：B到C

有六條路線。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為B1→C1→D)

d(B2,C1)+f1(C1)

2+1f2(B2)=mind(B2,C2

)+f1(C2)

=min3+3

d(B2,C3)+f1(C3)1+43=min6=35AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為B2→C1→D)第三階段（

A→B）：A到B有二條路線。

f3(A)1=d(A,B1)＋f2(B1)＝2＋4＝6

f3(A)2=d(A,B2)＋f2(B2)＝4＋3＝7∴f3(A)

=min=min｛6,7｝=6d(A,B1)＋f2(B1)d(A,B2)＋f2(B2)(最短路線為A→B1→C1→D)AB1B2C1C2C3D24333321114DC1C2C3B1B2AAB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路線為A→B1→C1→D練習：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最優(yōu)路線為：A→B1→C2→D1→E2→F2→G

路長＝18三、投資分配問題現(xiàn)有數(shù)量為a（萬元）的資金，計劃分配給n個工廠,用于擴大再生產(chǎn)。假設(shè)：xi為分配給第i個工廠的資金數(shù)量（萬元）；gi(xi)為第i個工廠得到資金后提供的利潤值（萬元）。問題是如何確定各工廠的資金數(shù)，使得總的利潤為最大。據(jù)此，有下式：令：fk(x)=以數(shù)量為x的資金分配給前k

個工廠，所得到的最大利潤值。用動態(tài)規(guī)劃求解，就是求fn(a)的問題。當k=1

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

時，其遞推關(guān)系如下：設(shè)：y

為分給第k個工廠的資金（其中0≤y≤x

），此時還剩x－y（萬元）的資金需要分配給前k-1

個工廠,如果采取最優(yōu)策略，則得到的最大利潤為fk－1(x－y),因此總的利潤為：

gk(y)＋

fk－1(x－y)

如果a

是以萬元為資金分配單位，則式中的y只取非負整數(shù)0，1，2，…，x。上式可變?yōu)椋核?，根?jù)動態(tài)規(guī)劃的最優(yōu)化原理，有下式：例題：設(shè)國家撥給60萬元投資，供四個工廠擴建使用，每個工廠擴建后的利潤與投資額的大小有關(guān)，投資后的利潤函數(shù)如下表所示。投資利潤0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依據(jù)題意，是要求f4(60)。按順序解法計算。第一階段：求f1(x)。顯然有f1(x)＝g1(x)，得到下表

投資利潤0102030405060f1(x)＝

g1(x)0205065808585最優(yōu)策略0102030405060第二階段：求f2(x)。此時需考慮第一、第二個工廠如何進行投資分配，以取得最大的總利潤。最優(yōu)策略為（40，20），此時最大利潤為120萬元。同理可求得其它f2(x)

的值。最優(yōu)策略為（30，20），此時最大利潤為105萬元。最優(yōu)策略為（20，20），此時最大利潤為90萬元。最優(yōu)策略為（20，10），此時最大利潤為70萬元。最優(yōu)策略為（10，0）或（0，10），此時最大利潤為20萬元。

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

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

的值。得到下表

投資利潤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)策略。最優(yōu)策略為（20，0，30，10），最大利潤為160萬元。練習：求投資分配問題得最優(yōu)策略，其中a＝50萬元，其余資料如表所示。投資利潤01020304050g1(x)02140528085g2(x)015365073100g3(x)02560656870有一個徒步旅行者，其可攜帶物品重量的限度為a公斤，設(shè)有n

種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應如何選擇攜帶的物品（各幾件），使所起作用（使用價值）最大？四、背包問題物品

12…j