動(dòng)態(tài)規(guī)劃投資分配問(wèn)題.ppt

1、第21講 動(dòng)態(tài)規(guī)劃,投資分配問(wèn)題,ACM算法設(shè)計(jì)與分析王建芳,投資分配問(wèn)題,現(xiàn)有數(shù)量為a（萬(wàn)元）的資金，計(jì)劃分配給n 個(gè)工廠,用于擴(kuò)大再生產(chǎn)。 假設(shè)：xi 為分配給第i 個(gè)工廠的資金數(shù)量（萬(wàn)元）；gi(xi)為第i 個(gè)工廠得到資金后提供的利潤(rùn)值（萬(wàn)元）。 問(wèn)題：如何確定各工廠的資金數(shù)，使得總的利潤(rùn)為最大。,據(jù)此，有下式：,令：fk(x) 表示以數(shù)量為x 的資金分配給前k 個(gè)工廠，所得到的最大利潤(rùn)值。 用動(dòng)態(tài)規(guī)劃求解，就是求 fn(a) 的問(wèn)題。,當(dāng) k=1 時(shí)， f1(x) = g1(x) （因?yàn)橹唤o一個(gè)工廠）,當(dāng)1kn 時(shí)，其遞推關(guān)系如下： 設(shè)：y 為分給第k 個(gè)工廠的資金（其中 0y x

2、），此時(shí)還剩 x y（萬(wàn)元）的資金需要分配給前 k1 個(gè)工廠,如果采取最優(yōu)策略，則得到的最大利潤(rùn)為fk1(xy) ,因此總的利潤(rùn)為： gk(y) fk1(xy),投資分配問(wèn)題,如果a 是以萬(wàn)元為資金分配單位，則式中的y 只取非負(fù)整數(shù)0，1，2，x。上式可變?yōu)椋?所以，根據(jù)動(dòng)態(tài)規(guī)劃的最優(yōu)化原理，有下式：,投資分配問(wèn)題,設(shè)國(guó)家撥給60萬(wàn)元投資，供四個(gè)工廠擴(kuò)建使用，每個(gè)工廠擴(kuò)建后的利潤(rùn)與投資額的大小有關(guān)，投資后的利潤(rùn)函數(shù)如下表所示。,依據(jù)題意，是要求 f4(60) 。,投資分配問(wèn)題,按順序解法計(jì)算。 第一階段：求 f1(x)。顯然有 f1(x) g1(x)，得到下表,第二階段：求 f2(x)。此時(shí)需

3、考慮第一、第二個(gè)工廠如何進(jìn)行投資分配，以取得最大的總利潤(rùn)。,投資分配問(wèn)題,最優(yōu)策略為（40，20），此時(shí)最大利潤(rùn)為120萬(wàn)元。,同理可求得其它 f2(x) 的值。,投資分配問(wèn)題,最優(yōu)策略為（30，20），此時(shí)最大利潤(rùn)為105萬(wàn)元。,投資分配問(wèn)題,最優(yōu)策略為（20，20），此時(shí)最大利潤(rùn)為90萬(wàn)元。,最優(yōu)策略為（20，10），此時(shí)最大利潤(rùn)為70萬(wàn)元。,投資分配問(wèn)題,最優(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)元。,投資分配問(wèn)題,第三階段：求 f3(x)。此時(shí)需考慮第一、第二及第三個(gè)工廠如何進(jìn)行投資分配，以取得最大的總利潤(rùn)。,投資分配問(wèn)題,最優(yōu)策略為（20，10，30），最大利潤(rùn)為155萬(wàn)元。,同理可求得其它 f3(x) 的值。得到下表,投資分配問(wèn)題,第四階段：求 f4(60)。即問(wèn)題的最優(yōu)策略。,投資分配問(wèn)題,最優(yōu)策略為（20，0，30，