線性規(guī)劃教學(xué)PPT動態(tài)規(guī)劃(上)

1、第六講第六講 動態(tài)規(guī)劃動態(tài)規(guī)劃 n多階段決策過程的最優(yōu)化多階段決策過程的最優(yōu)化n動態(tài)規(guī)劃的基本概念和基本原理動態(tài)規(guī)劃的基本概念和基本原理 n動態(tài)規(guī)劃模型的建立與求解動態(tài)規(guī)劃模型的建立與求解n動態(tài)規(guī)劃在經(jīng)濟管理中的應(yīng)用動態(tài)規(guī)劃在經(jīng)濟管理中的應(yīng)用 第一節(jié)第一節(jié) 多階段決策過程的最優(yōu)化多階段決策過程的最優(yōu)化 美國數(shù)學(xué)家貝爾曼美國數(shù)學(xué)家貝爾曼( ( r. bellman )50r. bellman )50年年代執(zhí)教于普林斯頓和斯坦福大學(xué)，后進入蘭代執(zhí)教于普林斯頓和斯坦福大學(xué)，后進入蘭德（德（randrand）研究所。研究所。19571957年發(fā)表年發(fā)表“dynamic dynamic programm

2、ingprogramming”一書，標(biāo)識動態(tài)規(guī)劃的正式一書，標(biāo)識動態(tài)規(guī)劃的正式誕生。誕生。 最短路問題最短路問題給定一個交通網(wǎng)絡(luò)圖如下，其中兩點之間的數(shù)字表示距離（或給定一個交通網(wǎng)絡(luò)圖如下，其中兩點之間的數(shù)字表示距離（或花費），試求從花費），試求從a a點到點到g g點的最短距離（總費用最?。c的最短距離（總費用最小）ab1b2c1c2c3c4d1d2d3e1e2e3f1f2g5313687668353384221233355266431234562 2、每個階段都要進行、每個階段都要進行決策決策, ,目的是使整個過程的決目的是使整個過程的決策達到最優(yōu)效果。策達到最優(yōu)效果。多階段決策問題：多階

3、段決策問題：1 1、在多階段決策過程中、在多階段決策過程中, ,系統(tǒng)的動態(tài)過程可以按照時系統(tǒng)的動態(tài)過程可以按照時間進程分為間進程分為狀態(tài)狀態(tài)相互相互聯(lián)系聯(lián)系而又相互而又相互區(qū)別區(qū)別的各個的各個階段階段；12n狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)狀態(tài)狀態(tài)決策決策多階段決策問題的典型例子多階段決策問題的典型例子 給定一個線路網(wǎng)絡(luò)圖，要從給定一個線路網(wǎng)絡(luò)圖，要從a a地向地向f f地鋪設(shè)一條輸油管道，地鋪設(shè)一條輸油管道，各點間連線上的數(shù)字表示距離，問應(yīng)選擇什么路線，可使總距各點間連線上的數(shù)字表示距離，問應(yīng)選擇什么路線，可使總距離最短離最短? ? 5 6 2 1 3 3 4 3 4 8 4 3 5

4、 4 8 5 3 6 8 7 7 2 5 4 a b2 b1 c2 c1 c4 c3 d2 d3 d1 e1 e2 f 2 3 4 5 1 圖 7-1 資源分配問題資源分配問題 例例. . 某公司擬將某種設(shè)備某公司擬將某種設(shè)備5 5臺，分配給所屬的甲、乙、丙三臺，分配給所屬的甲、乙、丙三個工廠。各工廠獲得此設(shè)備后，預(yù)測可創(chuàng)造的利潤如下表所示，個工廠。各工廠獲得此設(shè)備后，預(yù)測可創(chuàng)造的利潤如下表所示，問這問這5 5臺設(shè)備應(yīng)如何分配給這臺設(shè)備應(yīng)如何分配給這3 3個工廠，使得所創(chuàng)造的總利潤為個工廠，使得所創(chuàng)造的總利潤為最大？最大？ 工廠 盈利設(shè)備臺數(shù) 甲 廠 乙 廠 丙 廠 0 0 0 0 1 3 5

5、 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 12機器負荷分配問題機器負荷分配問題 某種機器可以在高低兩種不同的負荷下進行生產(chǎn)。在高負荷下進某種機器可以在高低兩種不同的負荷下進行生產(chǎn)。在高負荷下進行生產(chǎn)時，產(chǎn)品的年產(chǎn)量行生產(chǎn)時，產(chǎn)品的年產(chǎn)量g g和投入生產(chǎn)的機器數(shù)量和投入生產(chǎn)的機器數(shù)量u u1 1的關(guān)系為的關(guān)系為g g= =g g( (u u1 1) ) 這時，機器的年完好率為這時，機器的年完好率為a a，即如果年初完好機器的數(shù)量為即如果年初完好機器的數(shù)量為u u，到年到年終完好的機器就為終完好的機器就為auau, 0, 0a a11。 在低負荷下生產(chǎn)時，產(chǎn)

6、品的年產(chǎn)量在低負荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h h和投入生產(chǎn)的機器數(shù)量和投入生產(chǎn)的機器數(shù)量u u2 2的關(guān)系為的關(guān)系為 h h= =h h( (u u2 2) ) 假定開始生產(chǎn)時完好的機器數(shù)量為假定開始生產(chǎn)時完好的機器數(shù)量為s s1 1。要求制定一個五年計劃，在每要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同的負荷下生產(chǎn)的數(shù)量，年開始時，決定如何重新分配完好的機器在兩種不同的負荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達到最高。使在五年內(nèi)產(chǎn)品的總產(chǎn)量達到最高。 相應(yīng)的機器年完好率相應(yīng)的機器年完好率b b, 0, 0b b19/2)s(fxmax)s(fsx221011411 2910, 0959max994max)10(112*1111100111100111xssxsxsxsxfxx2229s)s(f 當(dāng)當(dāng)時時矛盾，舍去矛盾，舍去。是凹函數(shù)，故比較是凹函