運籌學(xué)動態(tài)規(guī)劃(1)(編輯修改稿)
2025-06-19 22:11 本頁面
【文章內(nèi)容簡介】 F1 G ? ? ? ? ? ?? ? ? ? 5}3245m i n {,m i n262251612525 ?????????????FfFEdFfFEdf EA B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 6 8 3 5 3 3 8 4 2 2 1 2 3 3 3 5 5 2 6 6 4 3 )( 15 Efu5(E2)=F2 E2 F2 G ? ? ? ? ? ?? ? ? ? 9}36 46m i n {,m i n262351613535 ?????????????FfFEdFfFEdf Eu5(E3)=F2 E3 F2 G k=6, F1 G f6(F1)=4 F2 G ,f6(F2)=3 k=4， f4(D1)=7 u4(D1)=E2 f4(D2)=6 u4(D2)=E2 f4(D3)=8 u4(D3)=E2 k=2, f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3 f3(C1)=13 u3(C1)=D1 f3(C2)=10 u3(C2)=D1 f3(C3)=9 u3(C3)=D1 f3(C4)=12 u3(C4)=D3 k=3, = min f1(A)= min d1(A,B1)+ f2(B1) d1(A,B2)+ f2(B2) 5+13 3+16 =18 k=1, u1(A)=B1 u2(B1)=C2 u3(C2)=D1 u4(D1)=E2 u1(A)=B1 u2(B1)=C2 u3(C2)=D1 u4(D1)=E2 u5(E1)=F1 E1 F1 G u5(E2)=F2 E2 F2 G u5(E3)=F2 E3 F2 G 7 5 9 u5(E2)=F2 u6(F2)=G 最優(yōu)策略 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 3 求從 A到 E的最短路徑 路線為 A→B 2→C 1 →D 1 →E ， 最短路徑為 19 A B2 B1 B3 C1 C3 D1 D2 E C2 5 2 14 1 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 練習(xí) 2： 1 現(xiàn)有數(shù)量為 a（萬元）的資金，計劃分配給 n 個工廠 ,用于擴(kuò)大再生產(chǎn)。 假設(shè)： xi 為分配給第 i 個工廠的資金數(shù)量（萬元） ；gi(xi)為第 i 個工廠得到資金后提供的利潤值（萬元）。 問題是如何確定各工廠的資金數(shù)，使得總的利潤為最大。 ?????????????nixaxxgZiniiniii.. 0)(m a x11?據(jù)此，有下式： 三、投資分配問題 令： fk(x) = 以數(shù)量為 x 的資金分配給前 k 個工廠，所得到的最大利潤值。 用動態(tài)規(guī)劃求解，就是求 fn(a) 的問題。 當(dāng) k=1 時， f1(x) = g1(x) （因為只給一個工廠） 當(dāng) 1＜ k≤n 時，其遞推關(guān)系如下： 設(shè)： y 為分給第 k 個工廠的資金（其中 0≤y ≤ x ），此時還剩 x － y（萬元）的資金需要分配給前 k1 個工廠 ,如果采取最優(yōu)策略，則得到的最大利潤為 fk－ 1(x－ y) ,因此總的利潤為： gk(y) ＋ fk－ 1(x－ y) ? ?nkyxfygxf kkxyk..)()(m a x)( 10????? ???其中 如果 a 是以萬元為資金分配單位，則式中的 y 只取非負(fù)整數(shù) 0， 1， 2， … ， x。上式可變?yōu)椋? ? ?)()(max)( 1,2,1,0 yxfygxf kkxyk ??? ?? ?所以，根據(jù)動態(tài)規(guī)劃的最優(yōu)化原理，有下式： 例題： 設(shè)國家撥給 60萬元投資，供四個工廠擴(kuò)建使用，每個工廠擴(kuò)建后的利潤與投資額的大小有關(guān)，投資后的利潤函數(shù)如下表所示。 投資 利潤 0 10 20 30 40 50 60 g1(x) 0 20 50 65 80 85 85 g2(x) 0 20 40 50 55 60 65 g3(x) 0 25 60 85 100 110 115 g4(x) 0 25 40 50 60 65 70 解：依據(jù)題意，是要求 f4(60) 。 按順序解法計算。 第一階段：求 f1(x)。顯然有 f1(x) ＝ g1(x)，得到下表 投資 利潤 0 10 20 30 40 50 60 f1(x) ＝ g1(x) 0 20 50 65 80 85 85 最優(yōu)策略 0 10 20 30 40 50 60 第二階段：求 f2(x)。此時需考慮第一、第二個工廠如何進(jìn)行投資分配，以取得最大的總利潤。 ? ?)60()(max)60( 1260,10,02 yfygf y ??? ? ?12006520605055655080408520850m a x)0()60()10()50()20()40()30()30()40()20()50()10()60()0(m a x12121212121212?????????????????????????????????????????????????????????????fgfgfgfgfgfgfg最優(yōu)策略為（ 40， 20），此時最大利潤為 120萬元。 同理可求得其它 f2(x) 的值。 ? ?105)0()50()10()40()20()30()30()20()40()10()50()0( )50()(m a x)50(1212121212121250,10,02??????????????????????????????????fgfgfgfgfgfgyfygfy ?最優(yōu)策略為（ 30， 20），此時最大利潤為 105萬元。 ? ?90 )40()(m a x)40( 1240,10,02?????yfygfy ?最優(yōu)策略為（ 20， 20），
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1