運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming

第六章動態(tài)規(guī)劃

(DynamicProgramming)教學(xué)要求：了解動態(tài)規(guī)劃的基本思想掌握一維離散動態(tài)規(guī)劃的建模和求解方法應(yīng)用會運(yùn)用動態(tài)規(guī)劃方法解決一些基本應(yīng)用問題。1運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第1頁!動態(tài)規(guī)劃是運(yùn)籌學(xué)的一個分支，是求解多階段決策過程最優(yōu)化問題的數(shù)學(xué)方法。動態(tài)規(guī)劃在經(jīng)濟(jì)管理、工程技術(shù)、工農(nóng)業(yè)生產(chǎn)及軍事部門中都有著廣泛的應(yīng)用，并且獲得了顯著的效果。學(xué)習(xí)動態(tài)規(guī)劃，首先要了解多階段決策問題。§6.1動態(tài)規(guī)劃原理和模型2運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第2頁!例1：最短路徑問題：給定一個交通網(wǎng)絡(luò)圖如下，其中兩點之間的數(shù)字表示距離（或運(yùn)費(fèi)），試求從A點到G點的最短距離（總運(yùn)輸費(fèi)用最?。?。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687636853384222133352566433運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第3頁!用窮舉法的計算量:從A到G的6個階段，一共有48條路線，比較47次。4運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第4頁!

生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計劃。機(jī)器負(fù)荷分配問題：某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機(jī)器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。航天飛機(jī)飛行控制問題：由于航天飛機(jī)的運(yùn)動的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機(jī)飛行在不同環(huán)境中的情況，不斷地決定航天飛機(jī)的飛行方向和速度（狀態(tài)），使之能最省燃料和完成飛行任務(wù)（如軟著陸）。5運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第5頁!針對多階段決策過程的最優(yōu)化問題，美國數(shù)學(xué)家Bellman等人在20世紀(jì)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ī)劃領(lǐng)域的本著作。6運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第6頁!

1、階段（k）

將所給問題的過程，按時間或空間特征分解成若干相互聯(lián)系的階段，以便按次序求解。2、狀態(tài)sk

能表示決策順序的離散的量，階段可以確定地表示決策過程當(dāng)前特征的量。狀態(tài)可以是數(shù)量，也可以是字符，數(shù)量狀態(tài)可以是連續(xù)的，也可以是離散的。

7運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第7頁!5、狀態(tài)轉(zhuǎn)移方程是確定過程由階段的一個狀態(tài)到下一階段另一狀態(tài)下的演變過程，用公式sk+1=Tk(sk,uk)表示。該公式描述了由第k階段到第k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律。8運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第8頁!

基本方程最優(yōu)指標(biāo)函數(shù)fk(sk)：從狀態(tài)sk出發(fā)，對所有的策略Pk,n，過程指標(biāo)Vk,n的最優(yōu)值，即

9運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第9頁!例3：某公司打算在三個不同的地區(qū)設(shè)置四個銷售點，據(jù)市場預(yù)測部門估計，在不同的地區(qū)設(shè)置不同數(shù)量的銷售點，每月可獲得的利潤如下表所示。試問在各個地區(qū)應(yīng)該如何設(shè)置銷售點，才能使每月獲得的總利潤最大？其值是多少？請用動態(tài)規(guī)劃方法分析求解。地區(qū)銷售點01234A036810B045811C067912各地區(qū)不同銷售點數(shù)量利潤表（單位：百萬元）10運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第10頁!7.動態(tài)遞推方程：

f（Sk）=MaxV（Sk，Uk）+f（Sk+1）k=2，1

f（S3）=MaxV（S3，U3）11運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第11頁!階段k=2V（S2，U2）+f（S3）f（S2）U2*U2=0U2=1U2=2U2=3U2=4S2=00+000S2=10+64+060S2=20+74+65+0101S2=30+94+75+68+0111，2S2=40+124+95+78+612+0143表212運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第12頁!例2：從A地到E地要鋪設(shè)一條煤氣管道,其中需經(jīng)過三級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？

AB2B1B3C1C3D1D2E52141126101043121113965810521C213運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第13頁!首先考慮經(jīng)過的兩條路線第三階段（C→D）：C到D有6條路線。(最短路線為)AB2B1B3C1C3D1D2E5214126101043121113965810521C214運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第14頁!AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)考慮經(jīng)過的兩條路線15運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第15頁!AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)考慮經(jīng)過的3條路線16運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第16頁!AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)階段（A→B）：A到B有3條路線。（最短距離為19）17運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第17頁!

動態(tài)規(guī)劃方法的關(guān)鍵：在于正確地寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件（簡稱基本方程）。要做到這一點，就必須將問題的過程分成幾個相互聯(lián)系的階段，恰當(dāng)?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個大問題轉(zhuǎn)化成一組同類型的子問題，然后逐個求解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。18運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第18頁!練習(xí)1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最優(yōu)路線為：A→B1→C2→D1→E2→F2→G

路長＝18求從A到G的最短路徑319運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第19頁!k=4，f4(D1)=7

u4(D1)=E2f4(D2)=6

u4(D2)=E2f4(D3)=8

u4(D3)=E2k=2,f2(B1)=13

u2(B1)=C2f2(B2)=16u2(B2)=C3f3(C1)=13

u3(C1)=D1f3(C2)=10

u3(C2)=D1f3(C3)=9

u3(C3)=D1f3(C4)=12

u3(C4)=D3k=3,=minf1(A)=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)5+133+16=18k=1,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E220運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第20頁!解：1.劃分階段根據(jù)問題的性質(zhì)，按照時間、空間、變量劃分為若干階段，這是用多階段決策過程描述一個實際問題的步。一個階段表示需要做出一次決策的子問題，建立動態(tài)規(guī)劃模型要求每個階段問題具有同一模式。描述階段的變量稱為階段變量，常用自然數(shù)k表示。

可劃分為3個階段求解，對甲產(chǎn)品增加研制費(fèi)記為第1階段，對乙產(chǎn)品增加研制費(fèi)記為第2階段，對丙產(chǎn)品增加研制費(fèi)記為第3階段，k=1，2，3。21運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第21頁!3.確定決策變量決策變量一般由系統(tǒng)最優(yōu)化的目的所決定。把給第K種新產(chǎn)品的研制費(fèi)用的數(shù)量作為決策變量uk,顯然，uk不能超過當(dāng)時擁有的金額sk

即：uk≤sk22運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第22頁!5.確定邊界條件過程開始和結(jié)束的狀態(tài)。由于開始時可用的金額為2萬元，而最后將全部用完，有S1=2,S4=023運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第23頁!第三階段

s3=0

s3=1

s3=2第二階段

s2=0

s2=1

s2=2第一階段只有S1=2s2=s1-u1*=2-0=2s3=s2-u2*=2-1=1最優(yōu)解0-1-1從最后一個階段開始，逐階段向前，直至階段，即可求出全過程最優(yōu)策略和指標(biāo)函數(shù)的最優(yōu)值?！?.2一維動態(tài)規(guī)劃求解方法

1、逆推法24運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第24頁!有一個徒步旅行者，其可攜帶物品重量的限度為a公斤，設(shè)有n種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應(yīng)如何選擇攜帶的物品（各幾件），使背包其所起作用（使用價值）最大？物品12…j…n重量（公斤/件）a1

a2

…

aj…

an每件使用價值c1

c2

…cj…

cn一、背包問題§6.3動態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用25運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第25頁!其遞推關(guān)系式為：當(dāng)k=1時，有：26運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第26頁!物品(xi)

x1

x2

x3重量（ai）325使用價值851227運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第27頁!物品(xi)

x1

x2

x3重量（ai）325使用價值851228運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第28頁!所以，最優(yōu)解為X＝（1.1.0），最優(yōu)值為Z=13?？偨Y(jié)：解動態(tài)規(guī)劃的一般方法:從終點逐段向始點方向?qū)ふ易钚?大)的方法。29運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第29頁!

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

fn(a)的問題。

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

當(dāng)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)30運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第30頁!例4：設(shè)國家撥給60萬元投資，供四個工廠擴(kuò)建使用，每個工廠擴(kuò)建后的利潤與投資額的大小有關(guān)，投資后的利潤函數(shù)如下表所示。投資利潤0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依據(jù)題意，是要求f4(60)。31運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第31頁!最優(yōu)策略為（40，20），此時最大利潤為120萬元。同理可求得其它f2(x)的值。32運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第32頁!最優(yōu)策略為（20，20），此時最大利潤為90萬元。最優(yōu)策略為（20，10），此時最大利潤為70萬元。33運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第33頁!

投資利潤0102030405060f2(x)020507090105120最優(yōu)策略(0,0)(10,0)(0,10)(20,0)(20,10)(20,20)(30,20)(40,20)第三階段：求f3(x)。此時需考慮、第二及第三個工廠如何進(jìn)行投資分配，以取得最大的總利潤。34運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第34頁!

投資利潤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)策略。35運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第35頁!排序問題指n種零件經(jīng)過不同設(shè)備加工是的順序問題。其目的是使加工周期為最短。1.n×1排序問題

即n種零件經(jīng)過1種設(shè)備進(jìn)行加工，如何安排？14682023交貨日期（d）45173加工時間（t）零件代號例：三、排序問題36運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第36頁!（2）按時交貨排列順序零件加工順序工序時間13457實際通過時間56101720交貨時間82314620平均通過時間延遲時間=037運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第37頁!

2.n×2排序問題

即n種零件經(jīng)過2種設(shè)備進(jìn)行加工，如何安排？例：49523B53786A零件設(shè)備ABT38運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第38頁!

3.n×3排序問題

即n種零件經(jīng)過3種設(shè)備進(jìn)行加工，如何安排？例：3468564683579310CBAABCT39運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第39頁!排序4+36+45+86+56+48+65+37+53+910+3B+CA+B復(fù)原3468564683579310CBA40運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第40頁!練習(xí)：11851079827746CBAT=4541運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第41頁!例：某公司打算在3個不同的地區(qū)設(shè)置4個銷售點，根據(jù)市場部門估計，在不同地區(qū)設(shè)置不同數(shù)量的銷售點每月可得到的利潤如表所示。試問在各地區(qū)如何設(shè)置銷售點可使每月總利潤最大。地區(qū)銷售點01234123000161210251714302116322217x1=2，x2=1，x3=1，f3(4)=47

42運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第42頁!練習(xí)2：求下列問題的最優(yōu)解

X=(2.1.0)

最優(yōu)值為

Z=1343運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第43頁!生產(chǎn)計劃問題

已知企業(yè)產(chǎn)品的生產(chǎn)費(fèi)用、存儲費(fèi)用和市場的需求量，在其生產(chǎn)能力和存儲能力許可的前提下，怎樣制定各個時期的生產(chǎn)計劃，既能完成交貨任務(wù)，又使總支出最小。某中轉(zhuǎn)倉庫要按月在月初供應(yīng)一定數(shù)量的某種部件給總裝車間，由于生產(chǎn)條件的變化，生產(chǎn)車間在各月份中生產(chǎn)每單位這種部件所需耗費(fèi)的工時不同，各月份的生產(chǎn)量于當(dāng)月的月底前，全部要存入倉庫以備后用。已知總裝車間的各個月份的需求量以及在加工車間生產(chǎn)該部件每單位數(shù)量所需工時，倉庫容量和開始庫存量，要求最終庫存量為0，要制定一個半年的逐月生產(chǎn)計劃，既滿足需要和倉庫容量的限制，又使生產(chǎn)這種部件的總耗費(fèi)工時數(shù)最少。

44運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第44頁!貨物存儲問題考慮下面三個月的庫存問題，在每月初，公司必須決定在本月內(nèi)，應(yīng)生產(chǎn)多少產(chǎn)品。在一個月內(nèi)生產(chǎn)x單位的產(chǎn)品，所需成本為c(x)，其中c(0)=0，當(dāng)x>0時，c(x)=3+2x。每月最多生產(chǎn)4個單位，每月的需求是隨機(jī)的，或為1或為2單位。如果生產(chǎn)的數(shù)量大于需求，就出現(xiàn)庫存。每個月末檢查庫存，1個單位的庫存費(fèi)用是1元。因為庫存能力有限，每月末的庫存量不能超過3單位。但同時要求必須及時滿足需求。在第3個月末要把現(xiàn)有的庫存以每單位2元的價格售出。在第1月的月初，公司有1單位的庫存。如何制定生產(chǎn)策略使三個月內(nèi)的期望費(fèi)用最小。

劃分階段

將三個月分為三個階段，每個月為一個階段狀態(tài)變量

sk表示第k個月初的庫存數(shù)

決策變量

xk表示第k月生產(chǎn)的單位數(shù)

建立狀態(tài)轉(zhuǎn)移方程

，其中為一隨機(jī)需求量或為1或為2

最優(yōu)指標(biāo)函數(shù)

fk(sk)表示第k個月初的庫存是時，第k個月至第3個月內(nèi)的最小期望費(fèi)用。45運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第45頁!設(shè)備更新問題

劃分階段

k表示計劃使用該設(shè)備的年限數(shù)

狀態(tài)變量

sk表示第k年初，設(shè)備已使用過的年數(shù)

決策變量

xk表示第k年初更新，還是繼續(xù)使用舊設(shè)備，分別用R和K表示。

建立狀態(tài)轉(zhuǎn)移方程

動態(tài)規(guī)劃的基本方程46運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第46頁!復(fù)合系統(tǒng)可靠性問題若某種機(jī)器的工作系統(tǒng)有N個部件組成，只要有一個部件失靈，整個系統(tǒng)就不能正常工作。這些部件的正常工作關(guān)系為串接關(guān)系，為提高系統(tǒng)工作的可靠性，在每一個部件上均裝有主要元件的備用件，并且設(shè)計了備用件自動投入裝置。顯然，備用元件越多，整個系統(tǒng)正常工作的可靠性越大。但備用元件多了，整個系統(tǒng)的成本、重量、體積均相應(yīng)加大，工作精度也降低。因此，最優(yōu)化問題是在考慮上述限制條件下，應(yīng)如何選擇各部件的備用元件數(shù)，使整個系統(tǒng)的工作可靠性最大？設(shè)部件i上裝有zi個備用遠(yuǎn)見時，它正常工作的概率是pi(zi)。因此，整個系統(tǒng)正常工作的可靠性，可以用它的正常工作的概率來衡量。即

設(shè)部件i的一個備用元件的費(fèi)用為ci，重量為wi，要求整個系統(tǒng)所裝備用元件的總費(fèi)用不超過C，總重量不超過W47運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第47頁!例2：背包問題

有一個徒步旅行者，其可攜帶物品重量的限度為a公斤，設(shè)有n種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應(yīng)如何選擇攜帶的物品（各幾件），使其背包所起作用（使用價值）最大？物品12…j…n重量（公斤/件）a1

a2

…

aj…

an每件使用價值c1

c2

…cj…

cn類似的還有工廠里的下料問題、運(yùn)輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。48運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第48頁!根據(jù)過程的特性可以將過程按空間、時間等標(biāo)志分為若干個互相聯(lián)系又互相區(qū)別的階段。在每一個階段都需要做出決策，從而使整個過程達(dá)到最好的效果。各個階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個階段的決策確定后，就組成了一個決策序列，因而也就決定了整個過程的一條活動路線，這樣的一個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策問題。多階段決策過程：49運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第49頁!動態(tài)規(guī)劃的基本概念最短路問題：某運(yùn)輸公司擬將一批貨物從A地運(yùn)往E地，其間的交通系統(tǒng)網(wǎng)絡(luò)如下圖所示。圖上節(jié)點表示地點，邊表示兩地之間的道路，邊上的數(shù)字表示兩地間的運(yùn)輸費(fèi)用，求運(yùn)輸費(fèi)用最低的運(yùn)輸路線。AB1B2B3C1C2C3D1D2E第2階段第3階段第4階段第1階段的狀態(tài)決策：某階段狀態(tài)給定之后，從該狀態(tài)演變到下一階段某一狀態(tài)的選擇。比如從階段到第二階段選擇什么路線。

策略：各階段決策確定后，組成的一個有序的決策序列。第2階段的狀態(tài)第1階段一、動態(tài)規(guī)劃的基本概念50運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第50頁!

3、決策uk從某一狀態(tài)向下一狀態(tài)過渡時所做的選擇。表示決策的變量為決策變量，用uk(sk)表示第k階段，狀態(tài)為sk時的決策變量。決策允許集合Dk(sk)：在狀態(tài)sk下，允許采取決策的全體。

4、策略Pk,n(sk)從第k階段開始到最后第n階段的決策序列，稱k子策略。PA,E(s1)即為全過程策略。51運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第51頁!

6、階段指標(biāo)函數(shù)vk(sk,uk)

從狀態(tài)sk出發(fā)，選擇決策uk所產(chǎn)生的第k階段指標(biāo)。過程指標(biāo)函數(shù)Vk,n(sk,uk,uk+1,…,un)：從狀態(tài)sk出發(fā)，選擇決策uk,uk+1,…,un所產(chǎn)生的過程指標(biāo)。動態(tài)規(guī)劃要求過程指標(biāo)具有可分離性，即Vk,n(sk,uk,uk+1,…,un)=Vk(sk,uk)+Vk+1(sk+1,uk+1,…,un)稱指標(biāo)具有可加性。Vk,n(sk,uk,uk+1,…,un)=Vk(sk,uk)×Vk+1(sk+1,uk+1,…,un)稱指標(biāo)具有可乘性。52運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第52頁!

對于可加性指標(biāo)函數(shù)，上式可以寫為

上式中“opt”表示“max”或“min”。對于可乘性指標(biāo)函數(shù)，上式可以寫為

以上式子稱為動態(tài)規(guī)劃最優(yōu)指標(biāo)的遞推方程，是動態(tài)規(guī)劃的基本方程。

終端條件：為了使以上的遞推方程有遞推的起點，必須要設(shè)定最優(yōu)指標(biāo)的終端條件，一般最后一個狀態(tài)n+1下最優(yōu)指標(biāo)，

fn+1(sn+1)=0。53運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第53頁!解：根據(jù)多階段決策問題的特征，將此問題轉(zhuǎn)化為三個階段的決策問題。1.階段k=1，2，3，分別代表A，B，C三地區(qū)。2.狀態(tài)變量Sk：表示第k個地區(qū)設(shè)置銷售點時還可設(shè)置的銷售點數(shù)量。3.決策變量Uk：表示第k個地區(qū)的銷售點數(shù)量。6.最優(yōu)指標(biāo)函數(shù)f（Sk）。4.狀態(tài)轉(zhuǎn)移方程：Sk+1=Sk-Uk。5.階段指標(biāo)值：利潤如表V（Sk，Uk）。54運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第54頁!階段k=3V（S3，U3）f（S3）U3*U3=0U3=1U3=2U3=3U3=4S3=0000S3=10661S3=206772S3=3067993S3=40679121248.逆序遞推求解動態(tài)方程：表155運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第55頁!階段k=1V（S1，U1）+f（S2）f（S1）U1*U1=0U1=1U1=2U1=3U1=4S1=40+143+116+108+610+0162決策方案：地區(qū)A——設(shè)置2個銷售點；地區(qū)B——設(shè)置1個銷售點；地區(qū)C——設(shè)置1個銷售點。此時公司可以獲得最大總利潤16（百萬元）。表356運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第56頁!

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

第四階段（D→E）：D有兩條路線到終點E。顯然有AB2B1B3C1C3D1D2E52141126101043121113965810521C257運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第57頁!AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)考慮經(jīng)過的兩條路線58運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第58頁!AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)第二階段（B→C）：B到C有9條路線。首先考慮經(jīng)過的3條路線59運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第59頁!AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)考慮經(jīng)過的3條路線60運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第60頁!

動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點在于，它可以把一個n維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。必須對具體問題進(jìn)行具體分析，運(yùn)用動態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動態(tài)規(guī)劃方法去求解。二.動態(tài)規(guī)劃的原理最優(yōu)化原理：作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略。也就是說，一個最優(yōu)策略的子策略也是最優(yōu)的。61運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第61頁!動態(tài)規(guī)劃適用于求解哪一類問題？每個階段的最優(yōu)決策過程只與本階段的初始狀態(tài)有關(guān)，而與以前各階段的決策（即為了到達(dá)本階段的初始狀態(tài)而采用哪組決策路線無關(guān)）。換言之，本階段之前的狀態(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)的多階段決策問題。62運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第62頁!k=5，出發(fā)點E1、E2、E3u5(E1)=F1E1F1GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u5(E2)=F2E2F2Gu5(E3)=F2E3F2Gk=6,F1G,f6(F1)=4F2G,f6(F2)=363運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第63頁!增加研制費(fèi)（萬元）新產(chǎn)品成功的概率甲乙丙0120.600.800.850.400.700.900.300.600.70例3：有一工廠研制甲、乙、丙三種新產(chǎn)品，估計這三種新研制成功的概率分別為：0.6、0.4、0.3。由于工廠急于推出新產(chǎn)品，決定再加撥2萬元研制費(fèi)，以提高新產(chǎn)品研制成功的概率。據(jù)估計，把增加的研制費(fèi)用于各種新產(chǎn)品研制時，研制成功的概率見下表?，F(xiàn)把這批研制費(fèi)分配給各新產(chǎn)品（不分配、分配給1萬元或分配給2萬元），使這三種新產(chǎn)品都研制成功的概率最大。應(yīng)怎樣分配。64運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第64頁!2.確定狀態(tài)變量及相應(yīng)的取值范圍

多階段決策過程的進(jìn)展，可用各階段的狀態(tài)演變來描述。狀態(tài)必須包含表示系統(tǒng)情況和確定決策所需要的全部信息，使其能反映過程的演變特征。同時還要狀態(tài)滿足無后效性，即若已知過程現(xiàn)在處于某一階段的某一狀態(tài)，則該階段以后過程的演變，不再受以前各階段狀態(tài)的影響。確定狀態(tài)變量之后，根據(jù)具體問題的性質(zhì)，找出狀態(tài)變量在各階段的取值范圍。

把有可能提供的研制費(fèi)用作狀態(tài)變量，記為sk，取值為0，1，2（萬元）65運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第65頁!4.建立狀態(tài)轉(zhuǎn)移方程根據(jù)狀態(tài)變量和決策變量的含義，寫出狀態(tài)轉(zhuǎn)移方程。根據(jù)以上對狀態(tài)變量和決策變量的規(guī)定，有：66運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第66頁!6.確定指標(biāo)函數(shù)，建立動態(tài)規(guī)劃的基本方程選取指標(biāo)函數(shù)，根據(jù)指標(biāo)函數(shù)建立最優(yōu)指標(biāo)函數(shù)遞推關(guān)系,即基本方程。

定義各階段研制成功概率pk(sk,uk)的乘積為指標(biāo)函數(shù)，并求指標(biāo)函數(shù)最大化?；痉匠虨?7運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第67頁!2、順推法

s3=s4+1=1s2=s3+1=2最優(yōu)解0-1-1由階段開始，逐階段向后，直至最后一個階段，同樣可求出最優(yōu)策略和指標(biāo)函數(shù)的最優(yōu)值。Sk+1表示第k階段的狀態(tài)變量。第一階段

s2=0

s2=1

s2=2第二階段

s3=0s3=1

s3=2第三階段68運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第68頁!設(shè)xj為第j種物品的裝件數(shù)（非負(fù)整數(shù)）則問題的數(shù)學(xué)模型如下：用動態(tài)規(guī)劃方法求解，令fk(y)為總重量不超過y公斤，包中只裝有前k種物品時的最大使用價值。其中y≥0，k＝1,2,…,n。所以問題就是求fn(a)69運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第69頁!例3：求下面背包問題的最優(yōu)解物品(xi)

x1

x2

x3重量（ai）325使用價值8512解：a＝5，問題是求f3(5)70運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第70頁!物品(xi)

x1

x2

x3重量（ai）325使用價值851271運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第71頁!72運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第72頁!現(xiàn)有數(shù)量為a（萬元）的資金，計劃分配給n個工廠，用于擴(kuò)大再生產(chǎn)。假設(shè)：xi為分配給第i個工廠的資金數(shù)量（萬元）；gi(xi)為第i個工廠得到資金后提供的利潤值（萬元）。問題：如何確定各工廠的資金數(shù)，使得總的利潤為最大。據(jù)此，有下式：二.投資分配問題73運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第73頁!如果a是以萬元為資金分配單位，則式中的y只取非負(fù)整數(shù)0，1，2，…，x。上式可變?yōu)椋核?，根?jù)動態(tài)規(guī)劃的最優(yōu)化原理，有下式：74運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第74頁!按順序解法計算。階段：求f1(x)。顯然有f1(x)＝g1(x)，得到下表

投資利潤0102030405060f1(x)＝

g1(x)0205065808585最優(yōu)策略0102030405060第二階段：求f2(x)。此時需考慮、第二個工廠如何進(jìn)行投資分配，以取得最大的總利潤。75運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第75頁!最優(yōu)策略為（30，20），此時最大利潤為105萬元。76運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第76頁!最優(yōu)策略為（10，0）或（0，10），此時最大利潤為20萬元。

f2(0)＝0。最優(yōu)策略為（0，0），最大利潤為0萬元。得到下表最優(yōu)策略為（20，0），此時最大利潤為50萬元。77運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第77頁!最優(yōu)策略為（20，10，30），最大利潤為155萬元。同理可求得其它f3(x)的值。得到下表78運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第78頁!最優(yōu)策略為（20，0，30，10），最大利潤為160萬元。79運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第79頁!（1）平均通過設(shè)備的時間最小按零件加工時間非負(fù)次序排列順序，其時間最小。（即將加工時間由小到大排列即可）零件加工順序工序時間13457實際通過時間1481320交貨時間82314620平均通過時間延遲時間=13–6=780運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第80頁!（3）既滿足交貨時間，又使平均通過時間最小零件加工順序工序時間13457實際通過時間1691320交貨時間82314620延遲時間=0平均通過時間81運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第81頁!經(jīng)變換為49523B53786A零件設(shè)備加工順序圖如下：ABT3756895432+2+2-5

加工周期T=3+7+5+6+8+2=3182運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第82頁!ABCT變換4+36+45+86+56+48+65+37+53+910+3B+CA+B83運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第83頁!計算T=6+10+8+7+6+4+3=44計算依據(jù)：84運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的是第84頁!練習(xí)：求投資分配問題得最優(yōu)策略，其中a＝50萬元，其余資料如表所示。投資利潤01020304050g1(x)02140528085g2(x)015365073100g3(x)0256065687085運(yùn)籌學(xué)chap6動態(tài)規(guī)劃DynamicProgramming共91頁，您現(xiàn)在瀏覽的