動(dòng)態(tài)規(guī)劃運(yùn)籌學(xué)基礎(chǔ)及其應(yīng)用胡運(yùn)權(quán)第五版(編輯修改稿)
2025-01-19 03:38 本頁面
【文章內(nèi)容簡介】 0 1 3 0 0+ f 3 (3 )= 0 + 9 0 = 9 0 * 80+ f 3 (0 )= 8 0 + 0 = 8 0 90 0 5 0 1 5 2 0+ f 3 (5 )= 0 + 1 5 0 = 1 5 0 * 80+ f 3 (2 )= 8 0 + 6 0 = 1 4 0 150 0 對于 k=2 )}3(80{max)}({max)(22323/03322/02222222dxfdxfdcxfxdwxd?????????列出 f2(x2)的數(shù)值表 35 x 1 D 1 ( x 1 ) x 2 65 d 1 + f 2 ( x 2 ) f 1 ( x 1 ) d 1 * 5 0 1 2 5 3 1 0+ f 2 (5 )= 0 + 1 5 0 = 1 5 0 65+ f 2 (3 )= 6 5 + 9 0 = 1 5 5 130+ f 2 (1 )= 1 3 0 + 3 0 = 1 6 0 * 160 2 對于 k=1 )}2(65{max)}({max)(11212/02211/01111111dxfdxfdcxfxdwxd?????????列出 f1(x1)的數(shù)值表 36 由題意知， x1=5 ，由表 f1( x1) 、 f2( x2) 、f3( x3) ，經(jīng)回朔可得： d1* = 2 ， x2= x1 2 d1=1 ， d2* = 0 ， x3= x2 3 d2=1 ，d3*=1 ， x4= x3 d3=0 即應(yīng)取第一種物品 2 件 , 第三種物品 1 件 , 最高價(jià)值為 1 6 0 元 , 背包沒有余量。由 f1( x1)得列表可以看出，如果背包得容量為 W =4 ，W =3 ， W =2 和 W =1 時(shí)，相應(yīng)的最優(yōu)解立即可以得到。 37 機(jī)器負(fù)荷分配問題 38 最短路徑問題和背包問題的狀態(tài)變量和決策 變量都只能取離散的整數(shù)值。當(dāng)狀態(tài)變量和決策變量的取值范圍很大，或者這些變量是連續(xù)的，用列舉的方法就比較困難或者根本不可能了。這就需要用連續(xù)變量的處理方法。 例 5. 8 : 某種機(jī)器可以在高、低兩種負(fù)荷下生產(chǎn)。高負(fù)荷生產(chǎn)條件下機(jī)器完好率為 ，即如果年初有u 臺完好機(jī)器投入生產(chǎn)， 則年末完好的機(jī)器數(shù)量為 u 臺。系數(shù) 稱為完好率。年初投入高負(fù)荷運(yùn)行的 u 臺機(jī)器的年產(chǎn)量為 8 u 噸。系數(shù) 8 稱為單臺產(chǎn)量。低負(fù)荷運(yùn)行時(shí)，機(jī)器完好率為 ，單臺產(chǎn)量為5 噸。設(shè)開始時(shí)有 1000 臺完好機(jī)器 ，要制訂五年計(jì)劃，每年年初將完好的機(jī) 器一部分分配到高負(fù)荷生產(chǎn)，剩下的機(jī)器分配到低負(fù)荷生產(chǎn)，使五年的總產(chǎn)量為最高。 39 構(gòu)造動(dòng)態(tài)規(guī)劃模型如下： 階段 k： 運(yùn)行年份（ k=1,2,3,4,5,6），其中 k=1表示第一年初， … ，依次類推；k=6表示第五年末（即第六年初）。 狀態(tài)變量 xk： 第 k年初完好的機(jī)器數(shù)（ k=1,2,3,4,5,6），其中 x6表示第五年末（即第六年初）的完好機(jī)器數(shù)。 決策變量 dk： 第 k年投入高負(fù)荷運(yùn)行的機(jī)器數(shù)； 狀態(tài)轉(zhuǎn)移方程 ： xk+1=+(xkdk) 決策允許集合 ： Dk(xk)={dk|0?dk?xk} 階段指標(biāo) ： vk(xk ,dk)=8dk+5(xkdk) 終端條件 ： f6(x6)=0 機(jī)器負(fù)荷分配問題 40 遞推方程：fk(xk)=max{vk(xk,dk)+fk+1(xk+1)} dk?Dk(xk) = max{8dk+5(xk dk)+fk+1[+(xkdk)]} 0?dk?xk 根據(jù)題意，本題的決策允許集合應(yīng)該是一個(gè)整數(shù)集合，但由于決策允許集合中 可取的決策數(shù)量很大，一一列舉計(jì)算量很大 ，不妨認(rèn)為狀態(tài)變量和決策變量都是連續(xù)的 ，得到最優(yōu)解后，再作取整處理。 機(jī)器負(fù)荷分配問題 41 f5(x5)=max{8d5+5(x5d5)+f6(x6)} 0?d5?x5 =max{3d5+5x5}=8x5, d5*=x5 0?d5?x5 f4(x4)=max{8d4+5(x4d4)+f5(x5)} 0?d4?x4 =max{8d4+5(x4d4)+8x5} 0?d4?x4 =max{8d4+5(x4d4)+8[+(x4d4)]} 0?d4?x4 =max{+}=, d4*=x4 0?d4?x4 機(jī)器負(fù)荷分配問題 42 f3(x3)=max{8d3+5(x3d3)+f4(x4)} 0?d3?x3 =max{8d3+5(x3d3)+} 0?d3?x3 =max{8d3+5(x3d3)+[+(x3d3)]} 0?d3?x3 =max{+}=, d3*=x3 0?d3?x3 機(jī)器負(fù)荷分配問題 43 f2(x2)=max{8d2+5(x2d2)+f3(x3)} 0?d2?x2 =max{8d2+5(x2d2)+} 0?d2?x2 =max{8d2+5(x2d2)+[+(x2d2)]} 0?d2?x2 =max{+}=,d2*=0 0?d2?x2 機(jī)器負(fù)荷分配問題 44 f1(x1)=max{8d1+5(x1d1)+f2(x2)} 0?d1?x1 =max{8d1+5(x1d1)+} 0?d1?x1 =max{8d1+5(x1d1)+[+(x1d1)]} 0?d1?x1 =max{+}=,d1*=0 0?d1?x1 機(jī)器負(fù)荷分配問題 45 由此可以得到： ? f1(x1)=, d1*=0 ? f2(x2)=, d2*=0 ? f3(x3)=, d3*=x3 ? f4(x4)=, d4*=x4 ? f5(x5)=8x5 d5*=x5 用 x1=1000代入 ， 得到五年最大產(chǎn)量為 ? f1(x1)=f1(1000)=23690 機(jī)器負(fù)荷分配問題 46 每年投入高負(fù)荷運(yùn)行的機(jī)器數(shù)以每年初完好的機(jī)器數(shù)為： ? x1=1000 ? d1*=0, x2=+(x1d1)=900 ? d2*=0, x3=+(x2d2)=810 ? d3*=x3=810, x4=+(x3d3)=567 ? d4*=x4=567, x5=+(x4d4)=397 ? d5*=x5=397, x6=+(x5d5)=278 機(jī)器負(fù)荷分配問題 47 在這個(gè)例子中，狀態(tài)變量的終端值 x6是未加約束的，如果要求在第五年末（即第六年初）完好的機(jī)器數(shù)不少于 500臺，這時(shí)決策變量 d5的決策允許集合將成為： D5(x5)={d5|+(x5d5)?500, d5?0} 即 ?500 d5?0 或 0?d5? 容易想象 ， 這時(shí)的最大產(chǎn)量將比 x6是自由的情況下小 。 ? 這個(gè)例子可以推廣到一般情況 。 設(shè)高負(fù)荷生產(chǎn)時(shí)機(jī)器的完好率為 k1， 單臺產(chǎn)量為 p1；低負(fù)荷完好率為 k2， 單臺產(chǎn)量為 p2。 若有 t滿足 : 機(jī)器負(fù)荷分配問題 48 則從 1— t1年，年初將全部完好機(jī)器投入低負(fù)荷運(yùn)行，從 t— n年，年初將全部完好機(jī)器投入高負(fù)荷運(yùn)行，這樣的決策，將使總產(chǎn)量達(dá)到最大。 ???????????tniitnii kkkpppk0112121)1(01 )( 機(jī)器負(fù)荷分配問題 49 生 產(chǎn) 庫 存 問 題 50 例 ： 一個(gè)工廠生產(chǎn)某種產(chǎn)品 ,1 7月份生產(chǎn)成本和產(chǎn)品需求量的變化情 況如下表： 月份 ( k ) 1 2 3 4 5 6 7 生產(chǎn)成本 ( c k ) 11 18 13 17 20 10 15 需求量 ( r k ) 0 8 5 3 2 7 4 為了調(diào)節(jié)生產(chǎn)生產(chǎn)和需求，工廠設(shè)有一個(gè)產(chǎn)品倉庫，庫容量 H =9 。 已知期初庫存量為 2 ，要求期末（七月低）庫存量為 0 。 每個(gè)月生產(chǎn)的產(chǎn)品在月末入庫，月初根據(jù)當(dāng)月需求 發(fā)貨。 求七個(gè)月的生產(chǎn)量，能滿足各 月的需求，并使生產(chǎn)成本最低。 生 產(chǎn) 庫 存 問 題 51 ? 階段 k： 月份 ， k=1,2,… ,7,8； ? 狀態(tài)變量 xk： 第 k個(gè)月初 （ 發(fā)貨以前 ） 的庫存量； ? 決策變量 dk： 第 k個(gè)月的生產(chǎn)量； ? 狀態(tài)轉(zhuǎn)移方程： xk+1=xkrk+dk； ? 決策允許集合： ? Dk(xk)={dk | dk?0, rk+1?xk+1?H } ={dk | dk?0, rk+1?xkrk+dk?H }； ? 階段指標(biāo)： vk(xk ,dk)=ckdk； ? 終端條件： f8(x8)=0, x8=0； 生 產(chǎn) 庫 存 問 題 52 遞推方程：f
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1