運(yùn)籌學(xué)chap.6 動(dòng)態(tài)規(guī)劃 Dynamic Programming

1、1第六章第六章 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃(Dynamic Programming)教學(xué)要求：教學(xué)要求：了解了解動(dòng)態(tài)規(guī)劃的基本思想掌握掌握一維離散動(dòng)態(tài)規(guī)劃的建模和求解方法應(yīng)用會(huì)運(yùn)用動(dòng)態(tài)規(guī)劃方法解決一些基本應(yīng)用問題。2 動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，是求解多階段決動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，是求解多階段決策過程最優(yōu)化問題的數(shù)學(xué)方法。策過程最優(yōu)化問題的數(shù)學(xué)方法。 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理、工程技術(shù)、工農(nóng)業(yè)生產(chǎn)及動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理、工程技術(shù)、工農(nóng)業(yè)生產(chǎn)及軍事部門中都有著廣泛的應(yīng)用，并且獲得了顯著的效軍事部門中都有著廣泛的應(yīng)用，并且獲得了顯著的效果。果。 學(xué)習(xí)動(dòng)態(tài)規(guī)劃，首先要了解多階段決策問題。學(xué)習(xí)動(dòng)態(tài)規(guī)劃，首先要了解

2、多階段決策問題。3例例1 1：最短路徑問題：最短路徑問題：給定一個(gè)交通網(wǎng)絡(luò)圖如下，：給定一個(gè)交通網(wǎng)絡(luò)圖如下，其中兩點(diǎn)之間的數(shù)字表示距離（或運(yùn)費(fèi)），試求其中兩點(diǎn)之間的數(shù)字表示距離（或運(yùn)費(fèi)），試求從從A A點(diǎn)到點(diǎn)到G G點(diǎn)的最短距離（總運(yùn)輸費(fèi)用最小）。點(diǎn)的最短距離（總運(yùn)輸費(fèi)用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687636853384222133352566434用窮舉法的計(jì)算量用窮舉法的計(jì)算量:從A到G的6個(gè)階段，一共有48條路線，比較47次。481222325例例2 2：背包問題：背包問題 有一個(gè)徒步旅行者，其可攜帶物品重量的有一個(gè)徒步旅行者

3、，其可攜帶物品重量的限度為限度為a a 公斤，設(shè)有公斤，設(shè)有n n 種物品可供他選擇裝入包中。已知每種物品可供他選擇裝入包中。已知每種物品的重量及使用價(jià)值（作用），問此人應(yīng)如何選擇攜帶種物品的重量及使用價(jià)值（作用），問此人應(yīng)如何選擇攜帶的物品（各幾件），使其背包所起作用（使用價(jià)值）最大？的物品（各幾件），使其背包所起作用（使用價(jià)值）最大？物品物品 1 2 j n重量（重量（公斤公斤/ /件件） a1 a2 aj an每件使用價(jià)值每件使用價(jià)值 c1 c2 cj cn類似的還有工廠里的下料問題、運(yùn)輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。6 生產(chǎn)決策問題生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需

4、求是隨時(shí)間變：企業(yè)在生產(chǎn)過程中，由于需求是隨時(shí)間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個(gè)化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個(gè)生產(chǎn)過程中逐月或逐季度地生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計(jì)劃。根據(jù)庫存和需求決定生產(chǎn)計(jì)劃。機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題：某種機(jī)器可以在高低兩種不同的負(fù)荷：某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。要求制定一個(gè)五年計(jì)劃，在下進(jìn)行生產(chǎn)。要求制定一個(gè)五年計(jì)劃，在每年開始時(shí)，決每年開始時(shí)，決定如何重新分配定如何重新分配完好的完好的機(jī)器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)機(jī)器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。，使

5、在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。航天飛機(jī)飛行控制問題航天飛機(jī)飛行控制問題：由于航天飛機(jī)的運(yùn)動(dòng)的環(huán)境是不：由于航天飛機(jī)的運(yùn)動(dòng)的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機(jī)飛行在不同環(huán)境中的情斷變化的，因此就要根據(jù)航天飛機(jī)飛行在不同環(huán)境中的情況，不斷地決定航天飛機(jī)的飛行方向和速度（狀態(tài)），使況，不斷地決定航天飛機(jī)的飛行方向和速度（狀態(tài)），使之能最省燃料和完成飛行任務(wù)（如軟著陸）。之能最省燃料和完成飛行任務(wù)（如軟著陸）。7根據(jù)過程的特性可以將過程按空間、時(shí)間等標(biāo)志分為根據(jù)過程的特性可以將過程按空間、時(shí)間等標(biāo)志分為若干個(gè)互相聯(lián)系又互相區(qū)別的階段。若干個(gè)互相聯(lián)系又互相區(qū)別的階段。在每一個(gè)階段都需要做出決策，從而

6、使整個(gè)過程達(dá)到在每一個(gè)階段都需要做出決策，從而使整個(gè)過程達(dá)到最好的效果。最好的效果。各個(gè)階段決策的選取不是任意確定的，它依賴于當(dāng)前各個(gè)階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個(gè)階段的決策確定后，就組成了一個(gè)決策序列，當(dāng)各個(gè)階段的決策確定后，就組成了一個(gè)決策序列，因而也就決定了整個(gè)過程的一條活動(dòng)路線，這樣的一因而也就決定了整個(gè)過程的一條活動(dòng)路線，這樣的一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策問題。決策問題。多階段決策過程：多階段決策過程：8針對(duì)多階段決策過程的最優(yōu)化問題，美

7、國數(shù)學(xué)家針對(duì)多階段決策過程的最優(yōu)化問題，美國數(shù)學(xué)家BellmanBellman等等人在人在2020世紀(jì)世紀(jì)5050年代初提出了著名的最優(yōu)化原理，年代初提出了著名的最優(yōu)化原理，把多階段把多階段決策問題轉(zhuǎn)化為一系列單階段最優(yōu)化問題決策問題轉(zhuǎn)化為一系列單階段最優(yōu)化問題，從而逐個(gè)求解，從而逐個(gè)求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法：動(dòng)態(tài)規(guī)劃。創(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)策略的

8、子策略必然也是最優(yōu)的。Bellman在在1957年出版的年出版的Dynamic Programming是動(dòng)是動(dòng)態(tài)規(guī)劃領(lǐng)域的第一本著作。態(tài)規(guī)劃領(lǐng)域的第一本著作。9動(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è)有序的決

9、策序列。第2階段的狀態(tài)第1階段一、動(dòng)態(tài)規(guī)劃的基本概念一、動(dòng)態(tài)規(guī)劃的基本概念10 1、階段（、階段（k） 將所給問題的過程，按時(shí)間或空間特征分解成若干相互聯(lián)系的階段，以便按次序求解。 2、狀態(tài)、狀態(tài)sk 能表示決策順序的離散的量，階段可以確定地表示決策過程當(dāng)前特征的量。狀態(tài)可以是數(shù)量，也可以是字符，數(shù)量狀態(tài)可以是連續(xù)的，也可以是離散的。 11 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

10、階段的決策序列，稱k子策略。PA,E(s1)即為全過程策略。 125、狀態(tài)轉(zhuǎn)移方程、狀態(tài)轉(zhuǎn)移方程 是確定過程由階段的一個(gè)狀態(tài)到下一階段另一狀態(tài)下的演變過程，用公式 sk+1=Tk(sk, uk)表示。該公式描述了由第k階段到第k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律狀態(tài)轉(zhuǎn)移規(guī)律。13 6、階段指標(biāo)函數(shù)、階段指標(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)具有可分離性動(dòng)態(tài)規(guī)劃要求過程指標(biāo)具有可分離性，即 Vk,n(sk, uk, u

11、k+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)具有可乘性。 14 基本方程基本方程 最優(yōu)指標(biāo)函數(shù)fk(sk)：從狀態(tài)sk出發(fā)，對(duì)所有的策略Pk,n，過程指標(biāo)Vk,n的最優(yōu)值，即 ),()(,)(nkknksDxkkPsVsfoptkkk15 對(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ī)

12、劃的基本方程。 終端條件終端條件：為了使以上的遞推方程有遞推的起點(diǎn)，必須要設(shè)定最優(yōu)指標(biāo)的終端條件，一般最后一個(gè)狀態(tài)n+1下最優(yōu)指標(biāo)， fn+1(sn+1) = 0。nksfusvsfkkkkksDxkkoptkkk, 2 , 1)(),()(11)(nksfusvsfkkkkksDxkkoptkkk, 2 , 1)(),()(11)(16例例3 3：某公司打算在三個(gè)不同的地區(qū)設(shè)置四個(gè)銷售點(diǎn)，據(jù)市場：某公司打算在三個(gè)不同的地區(qū)設(shè)置四個(gè)銷售點(diǎn)，據(jù)市場預(yù)測部門估計(jì)，在不同的地區(qū)設(shè)置不同數(shù)量的銷售點(diǎn)，每月預(yù)測部門估計(jì)，在不同的地區(qū)設(shè)置不同數(shù)量的銷售點(diǎn)，每月可獲得的利潤如下表所示。試問在各個(gè)地區(qū)應(yīng)該如何

13、設(shè)置銷可獲得的利潤如下表所示。試問在各個(gè)地區(qū)應(yīng)該如何設(shè)置銷售點(diǎn)，才能使每月獲得的總利潤最大？其值是多少？請(qǐng)用動(dòng)售點(diǎn)，才能使每月獲得的總利潤最大？其值是多少？請(qǐng)用動(dòng)態(tài)規(guī)劃方法分析求解。態(tài)規(guī)劃方法分析求解。地區(qū) 銷售點(diǎn) 0 1 2 3 4 A 0 3 6 8 10 B 0 4 5 8 11 C 0 6 7 9 1217解：根據(jù)多階段決策問題的特征，將此問題轉(zhuǎn)化為三個(gè)階段的決策問題。187. 動(dòng)態(tài)遞推方程：f（Sk）= Max V（Sk ，Uk）+ f（Sk+1） k = 2，1 f（S3）= Max V（S3 ，U3）19階段階段k =3V（S3 ，U3）f（S3）U3 *U3 = 0U3 = 1

14、U3 = 2U3 = 3U3=4S3 = 0000S3 = 10661S3 = 206772S3 = 3067993S3= 406791212420階段階段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 + 014321階段階段k =1V（S1 ，U1）+ f（S2）f（S1）U1 *U1 = 0U1 =

15、 1U1 = 2U1 = 3U1=4S1 = 40 + 143 + 116 + 108 + 610+016222例2：從從A A 地到地到E E 地要鋪設(shè)一條煤氣管道地要鋪設(shè)一條煤氣管道, ,其中需經(jīng)過三級(jí)其中需經(jīng)過三級(jí)中間站，兩點(diǎn)之間的連線上的數(shù)字表示距離，如圖所示。中間站，兩點(diǎn)之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？問應(yīng)該選擇什么路線，使總距離最短？ AB2B1B3C1C3D1D2E52141126101043121113965810521C223 解：解：整個(gè)計(jì)算過程分四個(gè)整個(gè)計(jì)算過程分四個(gè)階段階段，從最后一個(gè)階段開始。，從最后一個(gè)階段開始。 第四階段（第

16、四階段（D E）：）： D 有兩條路線到終點(diǎn)有兩條路線到終點(diǎn)E 。 顯然有顯然有AB2B1B3C1C3D1D2E52141126101043121113965810521C22)(; 5)(2414 DfDf24首先考慮經(jīng)過首先考慮經(jīng)過 的兩條路線的兩條路線第三階段（第三階段（C D）：）： C 到到D 有有 6 條路線。條路線。(最短路線為最短路線為 )AB2B1B3C1C3D1D2E5214126101043121113965810521C282953min)(),()(),(min)(2421141113 DfDCdDfDCdCfEDC111C25AB2B1B3C1C3D1D2E5214

17、126101043121113965810521C272556min)(),()(),(min)(2422141223 DfDCdDfDCdCf(最短路線為最短路線為 )EDC22考慮經(jīng)過考慮經(jīng)過 的兩條路線的兩條路線2C26AB2B1B3C1C3D1D2E5214126101043121113965810521C21221058min)(),()(),(min)(2423141333 DfDCdDfDCdCf(最短路線為最短路線為 )EDC23考慮經(jīng)過考慮經(jīng)過 的兩條路線的兩條路線3C27AB2B1B3C1C3D1D2E5214126101043121113965810521C2201210

18、714812min)(),()(),()(),(min)(33312321131112 CfCBdCfCBdCfCBdBf(最短路線為最短路線為 )EDCB111第二階段（第二階段（B C）：）： B 到到C 有有 9 條路線。條路線。首先考慮經(jīng)過首先考慮經(jīng)過 的的3條路線條路線1B28AB2B1B3C1C3D1D2E5214126101043121113965810521C21412471086min)(),()(),()(),(min)(33322322131222CfCBdCfCBdCfCBdBf(最短路線為最短路線為 )EDCB112考慮經(jīng)過考慮經(jīng)過 的的3條路線條路線2B29AB2B

19、1B3C1C3D1D2E5214126101043121113965810521C2191211712813min)(),()(),()(),(min)(33332323131332 CfCBdCfCBdCfCBdBf(最短路線為最短路線為 )EDCB223考慮經(jīng)過考慮經(jīng)過 的的3條路線條路線3B30AB2B1B3C1C3D1D2E5214126101043121113965810521C219191145202min)(),()(),()(),(min)(3232221211 BfBAdBfBAdBfBAdAf(最短路線為最短路線為 )EDCBA112第一階段（第一階段（A B）：）： A

20、到到B 有有 3 條路線。條路線。 （最短距離為（最短距離為19）31 動(dòng)態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量動(dòng)態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點(diǎn)在于，方法。其特點(diǎn)在于，它可以把一個(gè)它可以把一個(gè)n 維決策問題變換為幾個(gè)維決策問題變換為幾個(gè)一維最優(yōu)化問題一維最優(yōu)化問題，從而一個(gè)一個(gè)地去解決。，從而一個(gè)一個(gè)地去解決。 需指出：需指出：動(dòng)態(tài)規(guī)劃是求解某類問題的一種方法，是考察動(dòng)態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法問題的一種途徑，而不是一種算法。必須對(duì)具體問題進(jìn)行具。必須對(duì)具體問題進(jìn)行具體分析，運(yùn)用動(dòng)態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，

21、然體分析，運(yùn)用動(dòng)態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動(dòng)態(tài)規(guī)劃方法去求解。后再用動(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)的。 32 動(dòng)態(tài)規(guī)劃方法的關(guān)鍵：在于正確地寫出動(dòng)態(tài)規(guī)劃方法的關(guān)鍵：在于正確地寫出基本的遞推關(guān)基本的遞推關(guān)系式系式和和恰當(dāng)?shù)倪吔鐥l件恰當(dāng)?shù)倪吔鐥l件（簡稱（簡稱基本方程基本方程）。）。 要做到這一點(diǎn)，就必須將問題的過程分成幾個(gè)相互聯(lián)要做到這一點(diǎn)，就必須將問題的過程分成幾個(gè)相互聯(lián)系的系的階段階段，

22、恰當(dāng)?shù)倪x取，恰當(dāng)?shù)倪x取狀態(tài)變量狀態(tài)變量和和決策變量決策變量及定義及定義最優(yōu)值最優(yōu)值函數(shù)函數(shù)，從而把一個(gè)大問題轉(zhuǎn)化成一組同類型的子問題，然，從而把一個(gè)大問題轉(zhuǎn)化成一組同類型的子問題，然后逐個(gè)求解。后逐個(gè)求解。 即從邊界條件開始，逐段遞推尋優(yōu)，在每一個(gè)子問題即從邊界條件開始，逐段遞推尋優(yōu)，在每一個(gè)子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個(gè)子問題所得的最優(yōu)解，就是整個(gè)問題的最進(jìn)行，最后一個(gè)子問題所得的最優(yōu)解，就是整個(gè)問題的最優(yōu)解。優(yōu)解。33動(dòng)態(tài)規(guī)劃適用于求解哪一類問題？動(dòng)態(tài)規(guī)劃適用于求解哪一類問題？ 每個(gè)階段的最優(yōu)決策過程

23、只與本階段的初始狀態(tài)有關(guān)，而每個(gè)階段的最優(yōu)決策過程只與本階段的初始狀態(tài)有關(guān)，而與以前各階段的決策（即為了到達(dá)本階段的初始狀態(tài)而采與以前各階段的決策（即為了到達(dá)本階段的初始狀態(tài)而采用哪組決策路線無關(guān)）。換言之，本階段之前的狀態(tài)與決用哪組決策路線無關(guān)）。換言之，本階段之前的狀態(tài)與決策，只是通過系統(tǒng)在本階段所處的初始狀態(tài)來影響本階段策，只是通過系統(tǒng)在本階段所處的初始狀態(tài)來影響本階段及以后各個(gè)階段的決策?；蛘哒f，系統(tǒng)過程的歷史只能通及以后各個(gè)階段的決策?；蛘哒f，系統(tǒng)過程的歷史只能通過系統(tǒng)現(xiàn)階段的狀態(tài)去影響系統(tǒng)的未來。過系統(tǒng)現(xiàn)階段的狀態(tài)去影響系統(tǒng)的未來。 具有這種性質(zhì)的狀態(tài)稱為無后效性（即馬爾科夫性）狀

24、態(tài)。具有這種性質(zhì)的狀態(tài)稱為無后效性（即馬爾科夫性）狀態(tài)。 動(dòng)態(tài)規(guī)劃方法只適用于求解具有無后效性狀態(tài)的多階段決動(dòng)態(tài)規(guī)劃方法只適用于求解具有無后效性狀態(tài)的多階段決策問題。策問題。34練習(xí)練習(xí)1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最優(yōu)路線為：最優(yōu)路線為：A B1 C2 D1 E2 F2 G 路長路長18求從求從A到到G的最短路徑的最短路徑335 53245min,min262251612525 FfFEdFfFEdEfk=5k=5，出發(fā)點(diǎn)，出發(fā)點(diǎn)E E1 1、E E2 2、E E3 3 73543min,min262

25、1161155 FfFEdFfFEdu5(E1 1)= F1 1E1 1 F1 1 GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643)(15Efu5(E2 2)= F2 2E2 2 F2 2 G 93646min,min262351613535 FfFEdFfFEdEfu5(E3 3)= F2 2E3 3 F2 2 Gk=6k=6,F1 G, f f6 6(F(F1 1)=4)=4F F2 2 G,f,f6 6(F(F2 2)=3)=336k=4，f4(D1)=7 u4(D1)=E2f4(D2)=6 u4(D2)=E2f

26、4(D3)=8 u4(D3)=E2k=2, f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(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)=E237增加研制費(fèi)增加研制費(fèi)（萬元萬元）新產(chǎn)品成功的概率新產(chǎn)品成功的概率甲甲乙乙丙丙0120.600.800.850.400.7

27、00.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)怎樣分配。38 解：解：1. 1. 劃分階段劃分階段 根據(jù)問題的性質(zhì)，按照時(shí)間、空間、變量劃分根據(jù)問題的性質(zhì)，按照時(shí)間、空間、變量劃分為若干階段，這是用多階段決策過程描述一個(gè)實(shí)際為若干階段，這是用多階段決策過程描述一個(gè)實(shí)

28、際問題的第一步。一個(gè)階段表示需要做出一次決策的問題的第一步。一個(gè)階段表示需要做出一次決策的子問題，建立動(dòng)態(tài)規(guī)劃模型要求每個(gè)階段問題具有子問題，建立動(dòng)態(tài)規(guī)劃模型要求每個(gè)階段問題具有同一模式。描述階段的變量稱為階段變量，常用自同一模式。描述階段的變量稱為階段變量，常用自然數(shù)然數(shù)k k表示。表示。 可劃分為可劃分為3 3個(gè)階段求解，對(duì)甲產(chǎn)品增加研制費(fèi)記為第個(gè)階段求解，對(duì)甲產(chǎn)品增加研制費(fèi)記為第1 1階段，對(duì)乙產(chǎn)品增加研制費(fèi)記為第階段，對(duì)乙產(chǎn)品增加研制費(fèi)記為第2 2階段，對(duì)丙產(chǎn)階段，對(duì)丙產(chǎn)品增加研制費(fèi)記為第品增加研制費(fèi)記為第3 3階段，階段，k k=1=1，2 2，3 3。39 2. 2. 確定狀態(tài)變量

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

30、態(tài)變量在各階段的取根據(jù)具體問題的性質(zhì)，找出狀態(tài)變量在各階段的取值范圍。值范圍。 把有可能提供的研制費(fèi)用作狀態(tài)變量，記為把有可能提供的研制費(fèi)用作狀態(tài)變量，記為s sk k，取，取值為值為0 0，1 1，2 2（萬元）（萬元）40 3. 3. 確定決策變量確定決策變量 決策變量一般由系統(tǒng)最優(yōu)化的目的所決定。決策變量一般由系統(tǒng)最優(yōu)化的目的所決定。把給第把給第K K種新產(chǎn)品的研制費(fèi)用的數(shù)量作為決策變量種新產(chǎn)品的研制費(fèi)用的數(shù)量作為決策變量u uk k, , 顯然，顯然，u uk k不能超過當(dāng)時(shí)擁有的金額不能超過當(dāng)時(shí)擁有的金額sk 即：即： u uk ksk41 4. 4. 建立狀態(tài)轉(zhuǎn)移方程建立狀態(tài)轉(zhuǎn)移方

31、程 根據(jù)狀態(tài)變量和決策變量的含義，寫出狀態(tài)根據(jù)狀態(tài)變量和決策變量的含義，寫出狀態(tài)轉(zhuǎn)移方程。轉(zhuǎn)移方程。 根據(jù)以上對(duì)狀態(tài)變量和決策變量的規(guī)定，有：根據(jù)以上對(duì)狀態(tài)變量和決策變量的規(guī)定，有：),(1kkkusTskkkuss142 5. 5. 確定邊界條件確定邊界條件 過程開始和結(jié)束的狀態(tài)。過程開始和結(jié)束的狀態(tài)。 由于開始時(shí)可用的金額為由于開始時(shí)可用的金額為2 2萬元，而最后將全部用萬元，而最后將全部用完，有完，有S1=2,S4=043 6.6.確定指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃的基本方程確定指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃的基本方程 選取指標(biāo)函數(shù)，根據(jù)指標(biāo)函數(shù)建立最優(yōu)指標(biāo)函選取指標(biāo)函數(shù)，根據(jù)指標(biāo)函數(shù)建立最優(yōu)指標(biāo)函數(shù)遞

32、推關(guān)系數(shù)遞推關(guān)系, ,即基本方程。即基本方程。 定義各階段研制成功概率定義各階段研制成功概率p pk k(s(sk k,u,uk k) )的乘積為指標(biāo)函的乘積為指標(biāo)函數(shù)，并求指標(biāo)函數(shù)最大化。數(shù)，并求指標(biāo)函數(shù)最大化。 基本方程為基本方程為)( 1)(1 , 2 , 3,)(),(max)(4411必然事件sfksfuspsfkkkkkkk44第三階段)(),(max)(4433333sfuspsf04s33us s3=0 s3=1 s3=230. 0130. 0max)0()0 , 0(max)0(433fpf0*3u60. 0160. 0max)0() 1 , 1 (max) 1 (433fp

33、f1*3u70. 0170. 0max)0()2 , 2(max)2(433fpf2*3u第二階段)(),(max)(22322222usfuspsf12. 030. 040. 0max)0()0 , 0(max)0(322fpf0*2u s2=0 s2=1 s2=224. 03 . 07 . 06 . 04 . 0max) 11 () 1 , 1 ()01 ()0 , 1 (max) 1 (32322fpfpf0*2u42. 03 . 09 . 06 . 07 . 07 . 04 . 0max)22()2 , 2() 12() 1 , 2()02()0 , 2(max)2(3232322fp

34、fpfpf1*2u第一階段)(),(max)(11111111usfuspsf252. 012. 085. 024. 08 . 042. 06 . 0max)22()2 , 2() 12() 1 , 2()02()0 , 2(max)2(2121211fpfpfpf0*1u只有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)值。 6.26.2一維動(dòng)態(tài)規(guī)劃求解方法一維動(dòng)態(tài)規(guī)劃求解方法1、逆推法、逆推法452、順推法、順推法 s3=s4+1=1s2=s3+1=2最優(yōu)解0-1-1由

35、第一階段開始，逐階段向后，直至最后一個(gè)階段，同樣可求出最優(yōu)策略和指標(biāo)函數(shù)的最優(yōu)值。Sk+1 表示第k階段的狀態(tài)變量。第一階段 s2=0 s2=1 s2=2)(),(max)(1012121sfuspsf21s85. 0185. 0max)2()2 , 0(max)0(011fpf2*1u80. 0180. 0max)2() 1 , 1 (max) 1 (011fpf1*1u60. 0160. 0max)2()0 , 2(max)2(011fpf0*1u1*2u第二階段 s3=0 s3=1 s3=2)(),(max)(2123232sfuspsf56. 06 . 09 . 08 . 07 . 0

36、85. 04 . 0max)2()2 , 0() 1 () 1 , 0()0()0 , 0(max)0(1212122fpfpfpf1*2u42. 06 . 07 . 08 . 04 . 0max)2() 1 , 1 () 1 ()0 , 1 (max) 1 (12122fpfpf24. 06 . 040. 0max)2()0 , 2(max)2(122fpf0*2u232uss第三階段)(),(max)(3234343sfuspsf343uss04s252. 024. 07 . 042. 06 . 056. 03 . 0max)2()2 , 0() 1 () 1 , 0()0()0 , 0(

37、max)0(2323233fpfpfpf1*3u1)(3 , 2 , 1,)(),(max)(10111sfksfuspsfkkkkkkk46有一個(gè)徒步旅行者，其可攜帶物品重量的限度為a 公斤，設(shè)有n 種物品可供他選擇裝入包中。已知每種物品的重量及使用價(jià)值（作用），問此人應(yīng)如何選擇攜帶的物品（各幾件），使背包其所起作用（使用價(jià)值）最大？物品物品 1 2 j n重量（重量（公斤公斤/ /件件） a1 a2 aj an每件使用價(jià)值每件使用價(jià)值 c1 c2 cj cn一、背包問題6.3動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用47設(shè) xj 為第 j 種物品的裝件數(shù)（非負(fù)整數(shù)）則問題的數(shù)

38、學(xué)模型如下： ).(maxnjxaxaxcZjnijjjnjjj21 01且為整數(shù)用動(dòng)態(tài)規(guī)劃方法求解，令 fk(y) 為 總重量不超過 y 公斤，包中只裝有前k 種物品時(shí)的最大使用價(jià)值。 其中y 0， k 1,2, , n 。所以問題就是求 fn(a) 48其遞推關(guān)系式為： nkxayfxcyfkkkkkayxkkk 2 10其中)(max)(當(dāng) k=1 時(shí)，有：的最大整數(shù)表示不超過其中1111111 )(ayayaycxcyf49例3：求下面背包問題的最優(yōu)解 且且為為整整數(shù)數(shù)0,55231258max321321321xxxxxxxxxZ物品物品( (xi ) x1 x2 x3重量（重量（a

39、i） 3 2 5 使用價(jià)值使用價(jià)值 8 5 12解：a5 ，問題是求 f3(5) )55(12max)5(323503333xfxfxax 整整數(shù)數(shù)50 )( max)( 32350355125333xfxfxax 整數(shù) )( max 323550551233xfxxx 整數(shù) )( max 3231055123xfxx ， )( )()( ),(max 10223301250 xxff物品物品( (xi ) x1 x2 x3重量（重量（ai） 3 2 5使用價(jià)值使用價(jià)值 8 5 1251 5 5 )( 2)1()0(1112122, 10212250212502222222222)1(10),

40、3(5),5(0max)25(max)25(max)25(5max)5(xxxxxxxaxfffxfxxfxxfxf，整整數(shù)數(shù)整整數(shù)數(shù)物品物品( (xi ) x1 x2 x3重量（重量（ai） 3 2 5使用價(jià)值使用價(jià)值 8 5 12 )()()()(max)(1022333012505x xf, ff52 )0( )0(0max )20(5 max )20(5 max )20(5 max)0(1 )0( 12120212 200212 0022222222ffxfxxfxxfxfxxxxxax 整數(shù)整數(shù)整數(shù)整數(shù)物品物品( (xi ) x1 x2 x3重量（重量（ai） 3 2 5使用價(jià)值使用

41、價(jià)值 8 5 12 )1()0(22333)0(12)5(0max)5(x xf, ff53)0(0308)0()0(0318)1()1(8338)3()1(8358)5(1111111111111111 xxcfxxcfxxcfxxcf ) 1, 1(1310, 85, 8max) 1 (10),3(5),5(0max)5(212)1()0(1112222 xxffffxxx )( 54 )0, 0(0)0()0(0max)0(211)0(122 xxfffx )0,1,1(13012,130max)0(12),5(0max)5(321)1()0(22333 xxxfffxx所以，最優(yōu)解為所

42、以，最優(yōu)解為 X（1 . 1 . 0），），最優(yōu)值為最優(yōu)值為 Z = 13?？偨Y(jié)：總結(jié)：解動(dòng)態(tài)規(guī)劃的一般方法解動(dòng)態(tài)規(guī)劃的一般方法:從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ覐慕K點(diǎn)逐段向始點(diǎn)方向?qū)ふ易钚∽钚?大大)的方法。的方法。55現(xiàn)有數(shù)量為a（萬元）的資金，計(jì)劃分配給n 個(gè)工廠，用于擴(kuò)大再生產(chǎn)。假設(shè)：xi 為分配給第i 個(gè)工廠的資金數(shù)量（萬元）；gi(xi)為第i 個(gè)工廠得到資金后提供的利潤值（萬元）。問題：如何確定各工廠的資金數(shù)，使得總的利潤為最大。 nixaxxgziniiniii.2.1 0)( max11據(jù)此，有下式：二. 投資分配問題56 令：令：fk(x) 表示表示 以數(shù)量為以數(shù)量為 x 的資金分

43、配給的資金分配給前前k 個(gè)個(gè)工廠，所工廠，所得到的最大利潤值。得到的最大利潤值。 用動(dòng)態(tài)規(guī)劃求解，就是用動(dòng)態(tài)規(guī)劃求解，就是求求 fn(a) 的問題的問題。 當(dāng)當(dāng) k=1 時(shí)，時(shí)， f1(x) = g1(x) （因?yàn)橹唤o一個(gè)工廠）（因?yàn)橹唤o一個(gè)工廠） 當(dāng)當(dāng)1kn 時(shí)，其遞推關(guān)系如下：時(shí)，其遞推關(guān)系如下：設(shè)：設(shè)：y 為分給第為分給第k 個(gè)工廠的資金（其中個(gè)工廠的資金（其中 0y x ），此時(shí)還剩），此時(shí)還剩 x y（萬元）的資金需要分配給前（萬元）的資金需要分配給前 k1 個(gè)工廠，如果采取個(gè)工廠，如果采取最優(yōu)策略，則得到的最大利潤為最優(yōu)策略，則得到的最大利潤為fk1(xy) ，因此總的利潤，因此總

44、的利潤為：為： gk(y) fk1(xy) 57nkyxfygxfkkxyk,3 ,2)()(max)(10其中如果如果a 是以萬元為資金分配單位，則式中的是以萬元為資金分配單位，則式中的y 只取非負(fù)整數(shù)只取非負(fù)整數(shù)0，1，2，x。上式可變?yōu)椋?。上式可變?yōu)椋?)()(max)(,yxfygxfkkxyk 1210所以，根據(jù)動(dòng)態(tài)規(guī)劃的最優(yōu)化原理，有下式：所以，根據(jù)動(dòng)態(tài)規(guī)劃的最優(yōu)化原理，有下式：58例4：設(shè)國家撥給60萬元投資，供四個(gè)工廠擴(kuò)建使用，每個(gè)工廠擴(kuò)建后的利潤與投資額的大小有關(guān)，投資后的利潤函數(shù)如下表所示。 投資利潤0102030405060g1(x)0205065808585g2(x)0

45、204050556065g3(x)0256085100110115g4(x)0254050606570解：依據(jù)題意，是要求 f4(60) 。59按順序解法計(jì)算。按順序解法計(jì)算。第一階段：求第一階段：求 f1(x)。顯然有。顯然有 f1(x) g1(x)，得到下表，得到下表 投資投資利潤利潤0102030405060f1(x) g1(x)0205065808585最優(yōu)策略最優(yōu)策略0102030405060第二階段：求第二階段：求 f2(x)。此時(shí)需考慮第一、第二個(gè)工廠如何進(jìn)行。此時(shí)需考慮第一、第二個(gè)工廠如何進(jìn)行投資分配，以取得最大的總利潤。投資分配，以取得最大的總利潤。 )60()(max)60

46、(1260,10,02yfygfy 6012006520605055655080408520850max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max12121212121212fgfgfgfgfgfgfg最優(yōu)策略為（最優(yōu)策略為（40，20），此時(shí)最大利潤為），此時(shí)最大利潤為120萬元。萬元。同理可求得其它同理可求得其它 f2(x) 的值。的值。 )60()(max)60(1260,10,02yfygfy 61 105)0()50()10()40()20()30()30()20()40()10()50()0( )50()(ma

47、x)50(1212121212121250,10,02 fgfgfgfgfgfgyfygfy最優(yōu)策略為（最優(yōu)策略為（3030，2020），此時(shí)最大利潤為），此時(shí)最大利潤為105105萬元。萬元。62 90 )40()(max)40(1240,10,02 yfygfy最優(yōu)策略為（最優(yōu)策略為（20，20），此時(shí)最大利潤為），此時(shí)最大利潤為90萬元。萬元。 70 )30()(max)30(1230,20,10,02 yfygfy最優(yōu)策略為（最優(yōu)策略為（20，10），此時(shí)最大利潤為），此時(shí)最大利潤為70萬元。萬元。63 50 )20()(max)20(1220,10,02 yfygfy 20 )10(

48、)(max)10(12,10,02 yfygfy最優(yōu)策略為（最優(yōu)策略為（10，0）或（）或（ 0 ， 10 ） ，此時(shí)最大利潤為，此時(shí)最大利潤為20萬元。萬元。 f2(0) 0。最優(yōu)策略為（最優(yōu)策略為（0，0），最大利潤為），最大利潤為0萬元。萬元。 得到下表得到下表最優(yōu)策略為（最優(yōu)策略為（20，0），此時(shí)最大利潤為），此時(shí)最大利潤為50萬元。萬元。64 投資投資利潤利潤0102030405060f2(x)020507090105120最優(yōu)策略最優(yōu)策略(0,0)(10,0)(0,10)(20,0) (20,10) (20,20) (30,20) (40,20)第三階段：求第三階段：求 f3(x

49、)。此時(shí)需考慮第一、第二及第三個(gè)工。此時(shí)需考慮第一、第二及第三個(gè)工廠如何進(jìn)行投資分配，以取得最大的總利潤。廠如何進(jìn)行投資分配，以取得最大的總利潤。 )60()(max)60(2360,10,03yfygfy 651550115201105010070859060105251200max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max23232323232323 fgfgfgfgfgfgfg最優(yōu)策略為（最優(yōu)策略為（20，10，30），最大利潤為），最大利潤為155萬元。萬元。同理可求得其它同理可求得其它 f3(x) 的值。得到下表

50、的值。得到下表66 投資投資利潤利潤0102030405060f3(x)0256085110135155最優(yōu)最優(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)策略。)60()(max)60(3460,10,04yfygfy6716007025656060855011040135251550max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max34343434343434fgfgfgfgfgfgfg最

51、優(yōu)策略為（20，0，30，10），最大利潤為160萬元。68排序問題指n 種零件經(jīng)過不同設(shè)備加工是的順序問題。其目的是使加工周期為最短。 1. n 1 排序問題 即n 種零件經(jīng)過1 種設(shè)備進(jìn)行加工，如何安排？14682023交貨日期（交貨日期（d）45173加工時(shí)間（加工時(shí)間（t）零件代號(hào)零件代號(hào)2j1j3j4j5j例： 三、排序問題69 （1）平均通過設(shè)備的時(shí)間最小按零件加工時(shí)間非負(fù)次序排列順序，其時(shí)間最小。（即將加工時(shí)間由小到大排列即可）1j2j3j4j5j零件加工順序零件加工順序 工序時(shí)間工序時(shí)間13457 實(shí)際通過時(shí)間實(shí)際通過時(shí)間1481320 交貨時(shí)間交貨時(shí)間82314620 平均通

52、過時(shí)間2 . 9)1481320(51 x延遲時(shí)間 = 13 6 = 770 （2）按時(shí)交貨排列順序1j2j3j4j5j零件加工順序零件加工順序 工序時(shí)間工序時(shí)間13457 實(shí)際通過時(shí)間實(shí)際通過時(shí)間56101720 交貨時(shí)間交貨時(shí)間82314620 平均通過時(shí)間6 .11)56101720(51 x延遲時(shí)間 = 071 （3）既滿足交貨時(shí)間，又使平均通過時(shí)間最小1j2j3j4j5j零件加工順序零件加工順序 工序時(shí)間工序時(shí)間13457 實(shí)際通過時(shí)間實(shí)際通過時(shí)間1691320 交貨時(shí)間交貨時(shí)間82314620延遲時(shí)間 = 0 平均通過時(shí)間8 .9)1691320(51 x72 2. n 2 排序問

53、題排序問題 即即n 種零件經(jīng)過種零件經(jīng)過2 種設(shè)備進(jìn)行加工，如何安排？種設(shè)備進(jìn)行加工，如何安排？例：49523B53786A 零件零件2j1j3j4j5j設(shè)備設(shè)備ABT73經(jīng)變換為49523B53786A 零件零件2j1j3j4j5j設(shè)備設(shè)備加工順序圖如下：加工順序圖如下：ABT3j1j2j4j5j3756895432+2+2-5 加工周期加工周期 T = 3+7+5+6+8+2 = 31小小即即BAtti 74 3. n 3 排序問題排序問題 即即n 種零件經(jīng)過種零件經(jīng)過 3 種設(shè)備進(jìn)行加工，如何安排？種設(shè)備進(jìn)行加工，如何安排？例：3468564683579310CBA1j2j3j4j5jA

54、BCT75ABCT變換4+36+45+86+56+48+65+37+53+910+3B + CA+B1j2j3j4j5j76排序4+36+45+86+56+48+65+37+53+910+3B + CA+B1j2j3j4j5j復(fù)原3468564683579310CBA1j2j3j4j5j77計(jì)算T = 6+10+8+7+6+4+3 = 44計(jì)算依據(jù)：ABcCBABCBAttttttttttiiiiii 或即可按下式計(jì)算或maxminmaxmin78練習(xí)：練習(xí)：11851079827746CBA1j2j3j4jT=451j2j3j4j79 練習(xí)：練習(xí)： 求投資分配問題得最優(yōu)策略，其中求投資分配問

55、題得最優(yōu)策略，其中a50 萬元，其余萬元，其余資料如表所示。資料如表所示。 投資投資利潤利潤01020304050g1(x)02140528085g2(x)015365073100g3(x)0256065687080例：某公司打算在例：某公司打算在3個(gè)不同的地區(qū)設(shè)置個(gè)不同的地區(qū)設(shè)置4個(gè)銷售點(diǎn)，個(gè)銷售點(diǎn)，根據(jù)市場部門估計(jì)，在不同地區(qū)設(shè)置不同數(shù)量的銷根據(jù)市場部門估計(jì)，在不同地區(qū)設(shè)置不同數(shù)量的銷售點(diǎn)每月可得到的利潤如表所示。試問在各地區(qū)如售點(diǎn)每月可得到的利潤如表所示。試問在各地區(qū)如何設(shè)置銷售點(diǎn)可使每月總利潤最大。何設(shè)置銷售點(diǎn)可使每月總利潤最大。 地地區(qū)區(qū)銷售點(diǎn)銷售點(diǎn)01234123000161210

56、251714302116322217 x1=2，x2=1，x3=1，f3(4)=47 81 練習(xí)練習(xí)1：某廠生產(chǎn)三種產(chǎn)品，各種產(chǎn)品重量與利：某廠生產(chǎn)三種產(chǎn)品，各種產(chǎn)品重量與利潤的關(guān)系如表所示。現(xiàn)將此三種產(chǎn)品運(yùn)往市場出售，潤的關(guān)系如表所示?，F(xiàn)將此三種產(chǎn)品運(yùn)往市場出售，運(yùn)輸能力總重量不超過運(yùn)輸能力總重量不超過 6 噸，問如何安排運(yùn)輸，使噸，問如何安排運(yùn)輸，使總利潤最大？總利潤最大？種類種類 1 2 3重量（噸重量（噸/ /公斤）公斤） 2 3 4 單件利潤（元）單件利潤（元） 80 130 180最優(yōu)方案：最優(yōu)方案：X1 = =（0.2.00.2.0）X2 = =（1.0.11.0.1）Z=260

57、=26082 練習(xí)練習(xí)2：求下列問題的最優(yōu)解：求下列問題的最優(yōu)解 且且為為整整數(shù)數(shù)0,10543654max321321321xxxxxxxxxZ X=(2. 1. 0) 最優(yōu)值為最優(yōu)值為 Z = 1383背包問題 一位旅行者攜帶背包旅游，已知他的背包所能承受的重量為w千克，現(xiàn)有n種物品可供他選擇裝入包中，第i種物品的單件重量為wi 千克，其價(jià)值是攜帶數(shù)量 的函數(shù) 。問旅行者應(yīng)如何選擇攜帶物品的件數(shù)，使總價(jià)值最大？ ix)(iixp 劃分階段劃分階段 將可裝入物品按排序，每段裝一種物品，共劃分為n個(gè)階段，k=1,2,n. 狀態(tài)變量狀態(tài)變量 表示在第k階段開始時(shí)，背包中允許裝入前k種物品的總重量

58、，記為sk 決策變量決策變量 裝入第k 種物品的件數(shù) xk 建立狀態(tài)轉(zhuǎn)移方程建立狀態(tài)轉(zhuǎn)移方程 sk+1=sk-wkxk 允許決策集合允許決策集合 確定指標(biāo)函數(shù)確定指標(biāo)函數(shù) 確定邊界條件確定邊界條件 背包所能承受的重量為w千克 ,/0|)(11為整數(shù)kkkkkkkxwsxxsD 0)(, 2 , 1),()( max )(10/1 , 1 , 0111 sfnkxwsfxpsfkwkskxkkkkkkkk84生產(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)一

59、定數(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ù)最少。 85生產(chǎn)計(jì)劃問題 劃分階段劃分階段 按月份劃分階段，每個(gè)月為一個(gè)階段，k=1,2,n. 狀態(tài)變量狀態(tài)變量 第k階段開始時(shí)（即本階段需求送出之前，上階段產(chǎn)品送入之后）部件庫存量，記為sk 決策變量決策變量 第k階段內(nèi)的部件生產(chǎn)量，記為uk 建立狀態(tài)轉(zhuǎn)移方程建立狀態(tài)轉(zhuǎn)移方程 sk+1=sk+uk-dk 最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù) fk(sk)表示在第k階段開始的庫存量為sk時(shí)，從第k階段到最后一階段生產(chǎn)部件的最小 累計(jì)工時(shí)數(shù)。 基本方程基本方程 確定邊界條件確定邊界條件 so=開始庫存量，sn=0)(min)(11kkkkkksfuasf86貨物存儲(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)