運籌與決策復(fù)習題-資料下載頁
2025-01-07 00:12本頁面
【正文】 3 4 1 6 2 5 1 4 8 6 3 7 2 4 w5=6 w6=5 w7=14 w8=15 w9=10 w10=0 w11=0 w12=0 1 9 8 w1=0 w2=3 w3=7 w4=14 min(14+6,17+2)=19, w11=19, X={1,2,3,4,5,6,7,8,9,10,11,12} 獲得最優(yōu)解。從 1 到 12 的最短路徑長度為 12，路徑為 1234812。從 1 到其他各點的最短路徑如圖所示。 八、動態(tài)規(guī)劃 —— 資源分配問題 有資金 4 萬元，投資 A、 B、 C 三個項目，每個項目的投資效益與投入該項目的資金有關(guān)。三個項目 A、 B、 C 的投資效益（萬噸）和投入資金（萬元）的關(guān)系見下表： 效益（萬噸） 項 目 A B C 投入 資金 （萬元） 1 25 萬噸 18 萬噸 13 萬噸 2 32 萬噸 33 萬噸 32 萬 噸 3 38 萬噸 45 萬噸 48 萬噸 4 43 萬元 54 萬元 62 萬元 求對三個項目的最優(yōu)投資分配，使總投資效益最大。 這是一個資源分配問題。 階段 k：每投資一個項目作為一個階段； 狀態(tài)變量 xk：投資第 k 個項目前的資金數(shù)； 決策變量 dk：第 k 個項目的投資； 決策允許集合： 0≤ dk≤ xk 狀態(tài)轉(zhuǎn)移方程： xk+1=xkdk 階段指標： vk(xk,dk)見表中所示； 遞推方程： fk(xk)=max{vk(xk,dk)+fk+1(xk+1)} 終端條件： f4(x4)=0 k=4， f4(x4)=0 k=3， 0≤ d3≤ x3， x4=x3d3 x3 D3(x3) x4 v3(x3,d3) v3(x3,d3)+f4(x4) f3(x3) d3* 0 0 0 0 0+0=0 0 0 1 0 1 0 0+0=0 13 1 1 0 13 13+0=13* 2 0 2 0 0+0=0 32 2 1 1 13 11+0=11 2 0 32 32+0=32* 3 0 3 0 0+0=0 48 3 6 7 8 5 10 11 12 9 2 3 4 1 3 4 7 6 2 5 1 4 8 6 3 7 2 4 w1=0 w2=3 w3=7 w4=14 w5=6 w6=5 w7=14 w8=15 w9=10 w10=17 w11=19 w12=18 1 9 8 1 2 13 13+0=13 2 1 32 32+0=32 3 0 48 48+0=48* 4 0 4 0 0+0=0 62 4 1 3 13 13+0=13 2 2 32 32+0=32 3 1 48 48+0=48 4 0 62 62+0=62* k=2， 0≤ d2≤ x2， x3=x2d2 x2 D2(x2) x3 v2(x2,d2) v2(x2,d2)+f3(x3) f2(x2) d2* 0 0 0 0 0+0=0 0 0 1 0 1 0 0+13=13 18 1 1 0 18 18+0=18* 2 0 2 0 0+32=32* 32 0或 1 1 1 18 18+13=32* 2 0 33 33+0=29 3 0 3 0 0+48=48 50 1 1 2 18 18+32=50* 2 1 33 33+13=46 3 0 45 45+0=45 4 0 4 0 0+62=62 65 2 1 3 18 18+48=56 2 2 33 33+32=65* 3 1 45 45+13=58 4 0 54 54+0=54 k=1， 0≤ d1≤ x1， x2=x1d1 x1 D1(x1) x2 v1(x1,d1) v1(x1,d1)+f2(x2) f1(x1) d1* 4 0 4 0 0+65=65 75 1 1 3 25 25+50=75* 2 2 32 32+32=64 3 1 38 38+18=56 4 0 43 43+0=43 最優(yōu)解為 x1=4, d1*=1, x2=x1d1=3, d2*=1, x3=x2d2*=2, d3*=2, x4=x3d3*=0，即項目 A 投資 1萬元，項目 B 投資 1 萬元，項目 C 投資 2 萬元，最大效益為 75 萬噸。 九、動態(tài)規(guī)劃 —— 背包問題 有 5 萬元資金 ,用于購買 3 種設(shè)備 ,每種設(shè)備的單臺價格和單臺生產(chǎn)能力見下表： 設(shè) 備 A B C 價格 pk（萬元 /臺） 2 1 3 生產(chǎn)能力 qk（萬噸 /臺） 23 11 31 三種設(shè)備應(yīng)各購買多少臺，使總的生產(chǎn)能力最大？ 這是一個背包問題。 階段 k：每購買一種設(shè)備作為一個階段， k=1,2,3,4； 狀態(tài)變量 xk：購買第 k 種設(shè)備以前的資金（萬元）； 決策變量 dk：購買第 k 種設(shè)備的臺數(shù)（臺）； 決策允許集合 Dk(xk)： 0≤ dk≤ xk/pk， dk為整數(shù) 狀態(tài)轉(zhuǎn)移 方程： xk+1=xkpkdk 階段指標： vk(xk,dk)=qkdk 遞推方程： fk(xk)=max{qkdk+fk+1(xk+1)} 終端條件： f4(x4)=0 k=4， f4(x4)=0 k=3， f3(x3)=max{31d3+f4(x4)}， 0≤ d3≤ x3/3， x4=x33d3 x3 D3(x3) x4 31d3 31d3+f4(x4) f3(x3) d3* 0 0 0 0 0+0=0 0 0 1 0 1 0 0+0=0 0 0 2 0 2 0 0+0=0 0 0 3 0 3 0 0+0=0 31 1 1 0 31 31+0=31 4 0 4 0 0+0=0 31 1 1 1 31 31+0=31 5 0 5 0 0+0=0 31 1 1 2 31 31+0=31 k=2， f2(x2)=max{11d2+f3(x3)}， 0≤ d2≤ x2/1， x3=x21d2 x2 D2(x2) x3 11d2 11d2+f3(x3) f2(x2) d2* 0 0 0 0 0+0=0 0 0 1 0 1 0 0+0=0 11 1 1 0 11 11+0=11* 2 0 2 0 0+0=0 22 2 1 1 11 11+0=11 2 0 22 22+0=22* 3 0 3 0 0+31=31 33 3 1 2 11 11+0=11 2 1 22 22+0=22 3 0 33 33+0=33* 4 0 4 0 0+31=31 44 4 1 3 11 11+31=42 2 2 22 22+0=22 3 1 33 33+0=33 4 0 44 44+0=44* 5 0 5 0 0+31=31 55 5 1 4 11 11+31=42 2 3 22 22+31=53 3 2 33 33+0=33 4 1 44 44+0=44 5 0 55 55+0=55* k=1， f1(x1)=max{23d1+f2(x2)}， 0≤ d1≤ x1/2， x2=x12d1 x1 D1(x1) x2 23d1 23d1+f2(x2) f1(x1) d1* 5 0 5 0 0+55=55 57 2 1 3 23 23+33=56 2 1 46 46+11=57* 最優(yōu) 解為 x1=5, d1*=2, x2=x12d1=1, d2*=1, x3=x2d2=0, d3*=0，最大產(chǎn)量為 57 萬噸。
公司管理相關(guān)推薦
鄂ICP備17016276號-1