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

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

(DynamicProgramming)教學(xué)要求：

了解動(dòng)態(tài)規(guī)劃的基本思想

掌握一維離散動(dòng)態(tài)規(guī)劃的建模和求解方法應(yīng)用

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

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

a2

…

aj…

an每件使用價(jià)值c1

c2

…cj…

cn類似的還有工廠里的下料問題、運(yùn)輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。5可編輯ppt

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

策略：各階段決策確定后，組成的一個(gè)有序的決策序列。第2階段的狀態(tài)第1階段一、動(dòng)態(tài)規(guī)劃的基本概念9可編輯ppt

1、階段（k）

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

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

10可編輯ppt

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

4、策略Pk,n(sk)從第k階段開始到最后第n階段的決策序列，稱k子策略。PA,E(s1)即為全過程策略。11可編輯ppt5、狀態(tài)轉(zhuǎn)移方程是確定過程由階段的一個(gè)狀態(tài)到下一階段另一狀態(tài)下的演變過程，用公式sk+1=Tk(sk,uk)表示。該公式描述了由第k階段到第k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律。12可編輯ppt

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)。動(dòng)態(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)具有可乘性。13可編輯ppt

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

14可編輯ppt

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

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

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

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

fn+1(sn+1)=0。15可編輯ppt例3：某公司打算在三個(gè)不同的地區(qū)設(shè)置四個(gè)銷售點(diǎn)，據(jù)市場預(yù)測部門估計(jì)，在不同的地區(qū)設(shè)置不同數(shù)量的銷售點(diǎn)，每月可獲得的利潤如下表所示。試問在各個(gè)地區(qū)應(yīng)該如何設(shè)置銷售點(diǎn)，才能使每月獲得的總利潤最大？其值是多少？請(qǐng)用動(dòng)態(tài)規(guī)劃方法分析求解。地區(qū)銷售點(diǎn)01234A036810B045811C067912各地區(qū)不同銷售點(diǎn)數(shù)量利潤表（單位：百萬元）16可編輯ppt解：根據(jù)多階段決策問題的特征，將此問題轉(zhuǎn)化為三個(gè)階段的決策問題。1.階段k=1，2，3，分別代表A，B，C三地區(qū)。2.狀態(tài)變量Sk：表示第k個(gè)地區(qū)設(shè)置銷售點(diǎn)時(shí)還可設(shè)置的銷售點(diǎn)數(shù)量。3.決策變量Uk：表示第k個(gè)地區(qū)的銷售點(diǎn)數(shù)量。6.最優(yōu)指標(biāo)函數(shù)f（Sk）。4.狀態(tài)轉(zhuǎn)移方程：Sk+1=Sk-Uk。5.階段指標(biāo)值：利潤如表V（Sk，Uk）。17可編輯ppt7.動(dòng)態(tài)遞推方程：

f（Sk）=Max

V（Sk，Uk）+f（Sk+1）

k=2，1

f（S3）=Max

V（S3，U3）

18可編輯ppt階段k=3V（S3，U3）f（S3）U3*U3=0U3=1U3=2U3=3U3=4S3=0000S3=10661S3=206772S3=3067993S3=40679121248.逆序遞推求解動(dòng)態(tài)方程：表119可編輯ppt階段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表220可編輯ppt階段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個(gè)銷售點(diǎn)；地區(qū)B——設(shè)置1個(gè)銷售點(diǎn)；地區(qū)C——設(shè)置1個(gè)銷售點(diǎn)。此時(shí)公司可以獲得最大總利潤16（百萬元）。表321可編輯ppt例2：從A地到E地要鋪設(shè)一條煤氣管道,其中需經(jīng)過三級(jí)中間站，兩點(diǎn)之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？

AB2B1B3C1C3D1D2E52141126101043121113965810521C222可編輯ppt

解：整個(gè)計(jì)算過程分四個(gè)階段，從最后一個(gè)階段開始。

第四階段（D→E）：D有兩條路線到終點(diǎn)E。顯然有AB2B1B3C1C3D1D2E52141126101043121113965810521C223可編輯ppt首先考慮經(jīng)過的兩條路線第三階段（C→D）：C到D有6條路線。(最短路線為)AB2B1B3C1C3D1D2E5214126101043121113965810521C224可編輯pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)考慮經(jīng)過的兩條路線25可編輯pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)考慮經(jīng)過的兩條路線26可編輯pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)第二階段（B→C）：B到C有9條路線。首先考慮經(jīng)過的3條路線27可編輯pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)考慮經(jīng)過的3條路線28可編輯pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)考慮經(jīng)過的3條路線29可編輯pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)第一階段（A→B）：A到B有3條路線。（最短距離為19）30可編輯ppt

動(dòng)態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點(diǎn)在于，它可以把一個(gè)n維決策問題變換為幾個(gè)一維最優(yōu)化問題，從而一個(gè)一個(gè)地去解決。需指出：動(dòng)態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。必須對(duì)具體問題進(jìn)行具體分析，運(yùn)用動(dòng)態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動(dòng)態(tài)規(guī)劃方法去求解。二.動(dòng)態(tài)規(guī)劃的原理最優(yōu)化原理：作為整個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對(duì)于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略。也就是說，一個(gè)最優(yōu)策略的子策略也是最優(yōu)的。31可編輯ppt

動(dòng)態(tài)規(guī)劃方法的關(guān)鍵：在于正確地寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件（簡稱基本方程）。要做到這一點(diǎn)，就必須將問題的過程分成幾個(gè)相互聯(lián)系的階段，恰當(dāng)?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個(gè)大問題轉(zhuǎn)化成一組同類型的子問題，然后逐個(gè)求解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個(gè)子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個(gè)子問題所得的最優(yōu)解，就是整個(gè)問題的最優(yōu)解。32可編輯ppt動(dòng)態(tài)規(guī)劃適用于求解哪一類問題？每個(gè)階段的最優(yōu)決策過程只與本階段的初始狀態(tài)有關(guān)，而與以前各階段的決策（即為了到達(dá)本階段的初始狀態(tài)而采用哪組決策路線無關(guān)）。換言之，本階段之前的狀態(tài)與決策，只是通過系統(tǒng)在本階段所處的初始狀態(tài)來影響本階段及以后各個(gè)階段的決策?；蛘哒f，系統(tǒng)過程的歷史只能通過系統(tǒng)現(xiàn)階段的狀態(tài)去影響系統(tǒng)的未來。具有這種性質(zhì)的狀態(tài)稱為無后效性（即馬爾科夫性）狀態(tài)。動(dòng)態(tài)規(guī)劃方法只適用于求解具有無后效性狀態(tài)的多階段決策問題。33可編輯ppt練習(xí)1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最優(yōu)路線為：A→B1→C2→D1→E2→F2→G

路長＝18求從A到G的最短路徑334可編輯pptk=5，出發(fā)點(diǎn)E1、E2、E3u5(E1)=F1E1F1GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u5(E2)=F2E2F2Gu5(E3)=F2E3F2Gk=6,F1G,f6(F1)=4F2G,f6(F2)=335可編輯pptk=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)=E236可編輯ppt增加研制費(fèi)（萬元）新產(chǎn)品成功的概率甲乙丙0120.600.800.850.400.700.900.300.600.70例3：有一工廠研制甲、乙、丙三種新產(chǎn)品，估計(jì)這三種新研制成功的概率分別為：0.6、0.4、0.3。由于工廠急于推出新產(chǎn)品，決定再加撥2萬元研制費(fèi)，以提高新產(chǎn)品研制成功的概率。據(jù)估計(jì)，把增加的研制費(fèi)用于各種新產(chǎn)品研制時(shí)，研制成功的概率見下表?，F(xiàn)把這批研制費(fèi)分配給各新產(chǎn)品（不分配、分配給1萬元或分配給2萬元），使這三種新產(chǎn)品都研制成功的概率最大。應(yīng)怎樣分配。37可編輯ppt解：1.劃分階段根據(jù)問題的性質(zhì)，按照時(shí)間、空間、變量劃分為若干階段，這是用多階段決策過程描述一個(gè)實(shí)際問題的第一步。一個(gè)階段表示需要做出一次決策的子問題，建立動(dòng)態(tài)規(guī)劃模型要求每個(gè)階段問題具有同一模式。描述階段的變量稱為階段變量，常用自然數(shù)k表示。

可劃分為3個(gè)階段求解，對(duì)甲產(chǎn)品增加研制費(fèi)記為第1階段，對(duì)乙產(chǎn)品增加研制費(fèi)記為第2階段，對(duì)丙產(chǎn)品增加研制費(fèi)記為第3階段，k=1，2，3。38可編輯ppt2.確定狀態(tài)變量及相應(yīng)的取值范圍

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

把有可能提供的研制費(fèi)用作狀態(tài)變量，記為sk，取值為0，1，2（萬元）39可編輯ppt3.確定決策變量決策變量一般由系統(tǒng)最優(yōu)化的目的所決定。把給第K種新產(chǎn)品的研制費(fèi)用的數(shù)量作為決策變量uk,顯然，uk不能超過當(dāng)時(shí)擁有的金額sk

即：uk≤sk40可編輯ppt4.建立狀態(tài)轉(zhuǎn)移方程根據(jù)狀態(tài)變量和決策變量的含義，寫出狀態(tài)轉(zhuǎn)移方程。根據(jù)以上對(duì)狀態(tài)變量和決策變量的規(guī)定，有：41可編輯ppt5.確定邊界條件過程開始和結(jié)束的狀態(tài)。由于開始時(shí)可用的金額為2萬元，而最后將全部用完，有S1=2,S4=042可編輯ppt6.確定指標(biāo)函數(shù)，建立動(dòng)態(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ù)最大化。基本方程為43可編輯ppt第三階段

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從最后一個(gè)階段開始，逐階段向前，直至第一階段，即可求出全過程最優(yōu)策略和指標(biāo)函數(shù)的最優(yōu)值?！?.2一維動(dòng)態(tài)規(guī)劃求解方法

1、逆推法44可編輯ppt2、順推法

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

s2=0

s2=1

s2=2第二階段

s3=0s3=1

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

a2

…

aj…

an每件使用價(jià)值c1

c2

…cj…

cn一、背包問題§6.3動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用46可編輯ppt設(shè)xj為第j種物品的裝件數(shù)（非負(fù)整數(shù)）則問題的數(shù)學(xué)模型如下：用動(dòng)態(tài)規(guī)劃方法求解，令fk(y)為總重量不超過y公斤，包中只裝有前k種物品時(shí)的最大使用價(jià)值。其中y≥0，k＝1,2,…,n。所以問題就是求fn(a)47可編輯ppt其遞推關(guān)系式為：當(dāng)k=1時(shí)，有：48可編輯ppt例3：求下面背包問題的最優(yōu)解物品(xi)

x1

x2

x3重量（ai）325使用價(jià)值8512解：a＝5，問題是求f3(5)49可編輯ppt物品(xi)

x1

x2

x3重量（ai）325使用價(jià)值851250可編輯ppt物品(xi)

x1

x2

x3重量（ai）325使用價(jià)值851251可編輯ppt物品(xi)

x1

x2

x3重量（ai）325使用價(jià)值851252可編輯ppt53可編輯ppt所以，最優(yōu)解為X＝（1.1.0），最優(yōu)值為Z=13。總結(jié)：解動(dòng)態(tài)規(guī)劃的一般方法:從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易钚?大)的方法。54可編輯ppt現(xiàn)有數(shù)量為a（萬元）的資金，計(jì)劃分配給n個(gè)工廠，用于擴(kuò)大再生產(chǎn)。假設(shè)：xi為分配給第i個(gè)工廠的資金數(shù)量（萬元）；gi(xi)為第i個(gè)工廠得到資金后提供的利潤值（萬元）。問題：如何確定各工廠的資金數(shù)，使得總的利潤為最大。據(jù)此，有下式：二.投資分配問題55可編輯ppt

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

fn(a)的問題。

當(dāng)k=1時(shí)，f1(x)=g1(x)（因?yàn)橹唤o一個(gè)工廠）

當(dāng)1＜k≤n時(shí)，其遞推關(guān)系如下：設(shè)：y為分給第k個(gè)工廠的資金（其中0≤y≤x），此時(shí)還剩x－y（萬元）的資金需要分配給前k－1個(gè)工廠，如果采取最優(yōu)策略，則得到的最大利潤為fk－1(x－y)，因此總的利潤為：

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

投資利潤0102030405060f1(x)＝

g1(x)0205065808585最優(yōu)策略0102030405060第二階段：求f2(x)。此時(shí)需考慮第一、第二個(gè)工廠如何進(jìn)行投資分配，以取得最大的總利潤。59可編輯ppt最優(yōu)策略為（40，20），此時(shí)最大利潤為120萬元。同理可求得其它f2(x)的值。60可編輯ppt最優(yōu)策略為（30，20），此時(shí)最大利潤為105萬元。61可編輯ppt最優(yōu)策略為（20，20），此時(shí)最大利潤為90萬元。最優(yōu)策略為（20，10），此時(shí)最大利潤為70萬元。62可編輯ppt最優(yōu)策略為（10，0）或（0，10），此時(shí)最大利潤為20萬元。

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

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

投資利潤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)策略。66可編輯ppt最優(yōu)策略為（20，0，30，10），最大利潤為160萬元。67可編輯ppt排序問題指n種零件經(jīng)過不同設(shè)備加工是的順序問題。其目的是使加工周期為最短。1.n×1排序問題

即n種零件經(jīng)過1種設(shè)備進(jìn)行加工，如何安排？14682023交貨日期（d）45173加工時(shí)間（t）零件代號(hào)例：三、排序問題68可編輯ppt（1）平均通過設(shè)備的時(shí)間最小按零件加工時(shí)間非負(fù)次序排列順序，其時(shí)間最小。（即將加工時(shí)間由小到大排列即可）零件加工順序工序時(shí)間13457實(shí)際通過時(shí)間1481320交貨時(shí)間82314620平均通過時(shí)間延遲時(shí)間=13–6=769可編輯ppt（2）按時(shí)交貨排列順序零件加工順序工序時(shí)間13457實(shí)際通過時(shí)間56101720交貨時(shí)間82314620平均通過時(shí)間延遲時(shí)間=070可編輯ppt（3）既滿足交貨時(shí)間，又使平均通過時(shí)間最小零件加工順序工序時(shí)間13457實(shí)際通過時(shí)間1691320交貨時(shí)間82314620延遲時(shí)間=0平均通過時(shí)間71可編輯ppt

2.n×2排序問題

即n種零件經(jīng)過2種設(shè)備進(jìn)行加工，如何安排？例：49523B53786A零件設(shè)備ABT72可編輯ppt經(jīng)變換為49523B53786A零件設(shè)備加工順序圖如下：ABT3756895432+2+2-5

加工周期T=3+7+5+6+8+2=3173可編輯ppt

3.n×3排序問題

即n種零件經(jīng)過3種設(shè)備進(jìn)行加工，如何安排？例：3468564683579310CBAABCT74可編輯pptABCT變換4+36+45+86+56+48+65+37+53+910+3B+CA+B75可編輯ppt排序4+36+45+86+56+48+65+37+53+910+3B+CA+B復(fù)原3468564683579310CBA76可編輯ppt計(jì)算T=6+10+8+7+6+4+3=44計(jì)算依據(jù)：77可編輯ppt練習(xí)：11851079827746CBAT=4578可編輯ppt練習(xí)：求投資分配問題得最優(yōu)策略，其中a＝50萬元，其余資料如表所示。投資利潤01020304050g1(x)02140528085g2(x)015365073100g3(x)0256065687079可編輯ppt例：某公司打算在3個(gè)不同的地區(qū)設(shè)置4個(gè)銷售點(diǎn)，根據(jù)市場部門估計(jì)，在不同地區(qū)設(shè)置不同數(shù)量的銷售點(diǎn)每月可得到的利潤如表所示。試問在各地區(qū)如何設(shè)置銷售點(diǎn)可使每月總利潤最大。地區(qū)銷售點(diǎn)01234123000161210251714302116322217x1=2，x2=1，x3=1，f3(4)=4780可編輯ppt練習(xí)1：某廠生產(chǎn)三種產(chǎn)品，各種產(chǎn)品重量與利潤的關(guān)系如表所示。現(xiàn)將此三種產(chǎn)品運(yùn)往市場出售，運(yùn)輸能力總重量不超過6噸，問如何安排運(yùn)輸，使總利潤最大？種類123重量（噸/公斤）234單件利潤（元）80130180最優(yōu)方案：X1

=（0.2.0）X2=（1.0.1）Z=26081可編輯ppt練習(xí)2：求下列問題的最優(yōu)解

X=(2.1.0)

最優(yōu)值為

Z=1382可編輯ppt背包問題

一位旅行者攜帶背包旅游，已知他的背包所能承受的重量為w千克，現(xiàn)有n種物品可供他選擇裝入包中，第i種物品的單件重量為wi千克，其價(jià)值是攜帶數(shù)量的函數(shù)。問旅行者應(yīng)如何選擇攜帶物品的件數(shù)，使總價(jià)值最大？

劃分階段

將可裝入物品按排序，每段裝一種物品，共劃分為n個(gè)階段，k=1,2,……,n.

狀態(tài)變量

表示在第k階段開始時(shí)，背包中允許裝入前k種物品的總重量，記為sk

決策變量

裝入第k種物品的件數(shù)xk

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

sk+1=sk-wkxk

允許決策集合

確定指標(biāo)函數(shù)

確定邊界條件

背包所能承受的重量為w千克83可編輯ppt生產(chǎn)計(jì)劃問題

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

84可編輯ppt生產(chǎn)計(jì)劃問題劃分階段

按月份劃分階段，每個(gè)月為一個(gè)階段，k=1,2,……,n.

狀態(tài)變量

第k階段開始時(shí)（即本階段需求送出之前，上階段產(chǎn)品送入之后）部件庫存量，記為sk

決策變量

第k階段內(nèi)的部件生產(chǎn)量，記為uk

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

sk+1=sk+uk-dk

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

fk(sk)表示在第k階段開始的庫存量為sk時(shí)，從第k階段到最后一階段生產(chǎn)部件的最小累計(jì)工時(shí)數(shù)。

基本方程

確定邊界條件

so=開始庫存量，sn=085可編輯ppt貨物存儲(chǔ)問題考慮下面三個(gè)月的庫存問題，在每月初，公司必須決定在本月內(nèi)，應(yīng)生產(chǎn)多少產(chǎn)品。在一個(gè)月內(nèi)生產(chǎn)x單位的產(chǎn)品，所需成本為c(x)，其中c(0)=0，當(dāng)x>0時(shí)，c(x)=3+2x。每月最多生產(chǎn)4個(gè)單位，每月的需求是隨機(jī)的，或?yàn)?或?yàn)?單位。如果生產(chǎn)的數(shù)量大于需求，就出現(xiàn)庫存。每個(gè)月末檢查庫存，1個(gè)單位的庫存費(fèi)用是1元。因?yàn)閹齑婺芰τ邢?，每月末的庫存量不能超過3單位。但同時(shí)要求必須及時(shí)滿足需求。在第3個(gè)月末要把現(xiàn)有的庫存以每單位2元的價(jià)格售出。在第1月的月初，公司有1單位的庫存。如何制定生產(chǎn)策略使三個(gè)月內(nèi)的期望費(fèi)用最小。

劃分階段

將三個(gè)月分為三個(gè)階段，每個(gè)月為一個(gè)階段

狀態(tài)變量

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

決