【文章內(nèi)容簡(jiǎn)介】 gk(y) ＋ fk－ 1(x－ y) 40 ? ?nkyxfygxf kkxyk..)()(m a x)( 10????? ???其中 如果 a 是以萬(wàn)元為資金分配單位，則式中的 y 只取非負(fù)整數(shù) 0， 1， 2， … ， x。上式可變?yōu)椋? ? ?)()(max)( 1,2,1,0 yxfygxf kkxyk ??? ?? ?所以，根據(jù)動(dòng)態(tài)規(guī)劃的最優(yōu)化原理，有下式： 41 例題： 設(shè)國(guó)家撥給 60萬(wàn)元投資，供四個(gè)工廠擴(kuò)建使用，每個(gè)工廠擴(kuò)建后的利潤(rùn)與投資額的大小有關(guān)，投資后的利潤(rùn)函數(shù)如下表所示。 投資 利潤(rùn) 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) 。 42 按順序解法計(jì)算。 第一階段：求 f1(x)。顯然有 f1(x) ＝ g1(x)，得到下表 投資 利潤(rùn) 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)。此時(shí)需考慮第一、第二個(gè)工廠如何進(jìn)行投資分配，以取得最大的總利潤(rùn)。 ? ?)60()(max)60( 1260,10,02 yfygf y ??? ? ?43 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），此時(shí)最大利潤(rùn)為 120萬(wàn)元。 同理可求得其它 f2(x) 的值。 44 ? ?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），此時(shí)最大利潤(rùn)為 105萬(wàn)元。 45 ? ?90 )40()(m a x)40( 1240,10,02?????yfygfy ?最優(yōu)策略為（ 20， 20），此時(shí)最大利潤(rùn)為 90萬(wàn)元。 ? ?70 )30()(m a x)30( 1230,20,10,02?????yfygfy最優(yōu)策略為（ 20， 10），此時(shí)最大利潤(rùn)為 70萬(wàn)元。 46 ? ?50 )20()(m a x)20( 1220,10,02?????yfygfy? ?20 )10()(m a x)10( 12,10,02?????yfygfy最優(yōu)策略為（ 10， 0）或（ 0 ， 10 ） ，此時(shí)最大利潤(rùn)為 20萬(wàn)元。 f2(0) ＝ 0。 最優(yōu)策略為（ 0， 0），最大利潤(rùn)為 0萬(wàn)元。 得到下表 最優(yōu)策略為（ 20， 0），此時(shí)最大利潤(rùn)為 50萬(wàn)元。 47 投資 利潤(rùn) 0 10 20 30 40 50 60 f2(x) 0 20 50 70 90 105 120 最優(yōu)策略 (0,0) (10,0) (0,10) (20,0) (20,10) (20,20) (30,20) (40,20) 第三階段：求 f3(x)。此時(shí)需考慮第一、第二及第三個(gè)工廠如何進(jìn)行投資分配，以取得最大的總利潤(rùn)。 ? ?)60()(max)60( 2360,10,03 yfygf y ??? ? ?48 1550115202205010070859060105251200m a x)0()60()10()50()20()40()30()30()40()20()50()10()60()0(m a x23232323232323?????????????????????????????????????????????????????????????fgfgfgfgfgfgfg最優(yōu)策略為（ 20， 10， 30），最大利潤(rùn)為 155萬(wàn)元。 同理可求得其它 f3(x) 的值。得到下表 49 投資 利潤(rùn) 0 10 20 30 40 50 60 f3(x) 0 25 60 85 110 135 155 最優(yōu) 策略 (0,0,0) (0,0,10) (0,0,20) (0,0,30) (20,0,20) (20,0,30) (20,10,30) 第四階段：求 f4(60)。即問(wèn)題的最優(yōu)策略。 ? ?)60()(max)60( 3460,10,04 yfygf y ??? ? ?50 16007025656060855011040135251550m a x)0()60()10()50()20()40()30()30()40()20()50()10()60()0(m a x34343434343434?????????????????????????????????????????????????????????????fgfgfgfgfgfgfg最優(yōu)策略為（ 20， 0， 30， 10），最大利潤(rùn)為 160萬(wàn)元。 51 習(xí)題 ： 某公司打算在 3個(gè)不同的地區(qū)設(shè)置 4個(gè)銷(xiāo)售點(diǎn)，根據(jù)市場(chǎng)部門(mén)估計(jì)，在不同地區(qū)設(shè)置不同數(shù)量的銷(xiāo)售點(diǎn)每月可得到的利潤(rùn)如表所示。試問(wèn)在各地區(qū)如何設(shè)置銷(xiāo)售點(diǎn)可使每月總利潤(rùn)最大。 地區(qū) 銷(xiāo)售點(diǎn) 0 1 2 3 4 1 2 3 0 0 0 16 12 10 25 17 14 30 21 16 32 22 17 x1=2， x2=1， x3=1， f3(4)=47 52 2022/2/9 第 6章 動(dòng)態(tài)規(guī)劃法 Page 52 ?什么是背包問(wèn)題 ？ 給定 n種物品和一個(gè)背包 ， 物品 i的重量是 wi， 其價(jià)值為 vi， 背包容量為 C。 背包問(wèn)題是如何選擇裝入背包的物品 ， 使得裝入背包中物品的總價(jià)值最大 ？ ?何為 0/1？ 如果在選擇裝入背包的物品時(shí) ， 對(duì)每種物品 i只有兩種選擇：裝入背包或不裝入背包 ， 即不能將物品 i裝入背包多次 ， 也不能只裝入物品 i的一部分 ， 則稱(chēng)為0/1背包問(wèn)題 。 0/1背包問(wèn)題 53 2022/2/9 第 6章 動(dòng)態(tài)規(guī)劃法 Page 53 在 0/1背包問(wèn)題中 ， 物品 i或者被裝入背包 ， 或者不被裝入背包 ， 設(shè) xi表示物品 i裝入背包的情況 ， 則當(dāng) xi=0時(shí) ，表示物品 i沒(méi)有被裝入背包 ， xi=1時(shí) ， 表示物品 i被裝入背包 。 根據(jù)問(wèn)題的要求 ， 有如下 約束條件 和 目標(biāo)函數(shù) ： ???????????)1(}1,0{1nixCxwiniii（ 約束條件 ） ??niii xv1m a x（ 目標(biāo)函數(shù) ） 于是，問(wèn)題歸結(jié)為尋找一個(gè)滿足約束條件，并使目標(biāo)函數(shù)達(dá)到最大的解向量 X=(x1, x2, …, xn)。 0/1背包問(wèn)題 54 2022/2/9 第 6章 動(dòng)態(tài)規(guī)劃法 Page 54 0/1背包問(wèn)題 ?思考： 1. 0/1背包問(wèn)題能用什么方法解決 ？ 這些方法怎么樣 ？ 2. 0/1背包問(wèn)題能否用動(dòng)態(tài)規(guī)劃法解決 ？ 3. 0/1背包問(wèn)題如何用動(dòng)態(tài)規(guī)劃法解決 ？ 4. 0/1背包問(wèn)題用動(dòng)態(tài)規(guī)劃法 ， 與其他方法相比 ， 效率如何 ， 效果如何 ？ 55 2022/2/9 第 6章 動(dòng)態(tài)規(guī)劃法 Page 55 關(guān)鍵問(wèn)題：找出動(dòng)態(tài)規(guī)劃函數(shù) ?0/1背包問(wèn)題可以看作是決策一個(gè)序列 (x1, x2, …, xn)，對(duì)任一變量 xi的決策是決定 xi=1還是 xi=0。在對(duì) xi1決策后，已確定了 (x1, …, xi1)，在決策 xi時(shí)，問(wèn)題處于下列兩種狀態(tài)之一： （ 1） 背包容量不足以裝入物品 i， 則 xi=0， 背包不增加價(jià)值； （ 2） 背包容量可以裝入物品 i。 在 （ 2） 的狀態(tài)下 ， 物品 i有兩種情況 ， 裝入 （ 則 xi=1） 或不裝入 （ 則 xi=0） 。 在這兩種情況下背包價(jià)值的最大者應(yīng)該是對(duì) xi決策后的背包價(jià)值 。 0/1背包問(wèn)題如何用動(dòng)態(tài)規(guī)劃法解決 ？ 56 2022/2/9 第 6章 動(dòng)態(tài)規(guī)劃法 Page 56 令 V(i, j)表示在前 i(1≤i≤n)個(gè)物品中能夠裝入容量為 j（ 1≤j≤C）的背包中的物品的最大值 ，則可以得到如下動(dòng)態(tài)規(guī)劃函數(shù)： V(i, 0)= V(0, j)=0 (式 1) (式 2) 式 1表明：把前面 i個(gè)物品裝入容量為 0的背包和把 0個(gè)物品裝入容量為 j的背包，得到的價(jià)值均為 0。 ( 1 , )( , )m a x { ( 1 , ) , ( 1 , ) }ii i iV i j j wV i jV i j V i j w v j w???? ?? ? ? ? ??57 2022/2/9 第 6章 動(dòng)態(tài)規(guī)劃法 Page 57 （ 1）式 2的第一個(gè)式子表明：如果第 i個(gè)物品的重量大于背包的容量，則物品 i不能裝入背包，則裝入前 i個(gè)物品得到的最大價(jià)值和裝入前 i1個(gè)物品得到的最大價(jià)值是相同的。 (式 2) ( 1 , )( , )m a x { ( 1 , ) , ( 1 , ) }ii i iV i j j wV i jV i j V i j w v j w???? ?? ? ? ? ??58 2022/2/9 第 6章 動(dòng)態(tài)規(guī)劃法 Page 58 （ 2）第二個(gè)式子表明：如果第 i個(gè)物品的重量小于背包的容量，則會(huì)有以下兩種情況： ① 如果第 i個(gè)物品沒(méi)有裝入背包，則背包中物品的價(jià)值就等于把前 i1個(gè)物品裝入容量為 j的背包中所取得的價(jià)值。 ② 如果把第 i個(gè)物品裝入背包，則背包中物品的價(jià)值等于把前 i1個(gè)物品裝入容量為 jwi的背包中的價(jià)值加上第 i個(gè)物品的價(jià)值 vi； 顯然， 取二者中價(jià)