運(yùn)籌學(xué)動態(tài)規(guī)劃(1)-文庫吧資料
2025-05-22 22:11本頁面
【正文】 30,20,10,02?????yfygfy最優(yōu)策略為（ 20， 10），此時最大利潤為 70萬元。 ? ?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萬元。 ? ?)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萬元。顯然有 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ì)算。上式可變?yōu)椋? ? ?)()(max)( 1,2,1,0 yxfygxf kkxyk ??? ?? ?所以，根據(jù)動態(tài)規(guī)劃的最優(yōu)化原理，有下式： 例題： 設(shè)國家撥給 60萬元投資，供四個工廠擴(kuò)建使用，每個工廠擴(kuò)建后的利潤與投資額的大小有關(guān)，投資后的利潤函數(shù)如下表所示。 用動態(tài)規(guī)劃求解，就是求 fn(a) 的問題。 問題是如何確定各工廠的資金數(shù)，使得總的利潤為最大。 f3(A)1 = d(A, B1 )＋ f2 ( B1 ) ＝ 2＋ 4＝ 6 f3 (A)2 = d(A, B2 )＋ f2 ( B2 ) ＝ 4＋ 3＝ 7 ∴ f3 (A) = min = min｛ 6,7｝ =6 d(A, B1 )＋ f2 ( B1 ) d(A, B2 )＋ f2 ( B2 ) (最短路線為 A→B 1→ C1 → D) A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 最短路線為 A→B 1→ C1 → D 路長為 6 練習(xí) 1： 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 最優(yōu)路線為： A → B1 → C2 → D1 → E2 → F2 → G 路長 ＝ 18 求從 A到 G的最短路徑 3 k=5， 出發(fā)點(diǎn) E E E3 ? ? ? ?? ? ? ? 7}3543m i n{,m i n2621516115 ?????????????FfFEdFfFEdu5(E1)=F1 E1 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（萬元）的資金，計(jì)劃分配給 n 個工廠 ,用
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1