《運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃》 (2)ppt課件

1、.1.1動(dòng)態(tài)規(guī)劃問(wèn)題和根本概念動(dòng)態(tài)規(guī)劃問(wèn)題和根本概念.2 .2 動(dòng)態(tài)規(guī)劃的根本原理動(dòng)態(tài)規(guī)劃的根本原理.3 .3 動(dòng)態(tài)規(guī)劃的運(yùn)用動(dòng)態(tài)規(guī)劃的運(yùn)用 多階段決策是指這樣一類特殊的活動(dòng)過(guò)程, 它們可以按時(shí)間順序分解成假設(shè)干相互聯(lián)絡(luò)的階段, 每個(gè)階段都要作出決策, 全部過(guò)程的決策是一個(gè)決策序列, 所以多階段決策問(wèn)題又稱為序貫決策問(wèn)題。多階段決策的目的多階段決策的目的是要到達(dá)整個(gè)活動(dòng)過(guò)程的總體效果最優(yōu), 所以多階段決策又叫做過(guò)程最優(yōu)化。所謂動(dòng)態(tài)規(guī)劃，動(dòng)態(tài)規(guī)劃， 就是處理多階段決策和過(guò)程最優(yōu)化問(wèn)題的一就是處理多階段決策和過(guò)程最優(yōu)化問(wèn)題的一種規(guī)劃方法。種規(guī)劃方法。 例.1 最短路問(wèn)題 設(shè)A地的某一企業(yè)要把一批貨

2、物由A地運(yùn)到E城銷售, 其間要經(jīng)過(guò)八個(gè)城市,各城市間的交通道路及間隔如以下圖所示, 問(wèn)應(yīng)選擇什么道路才干使總的間隔最短? .1 .1 動(dòng)態(tài)規(guī)劃問(wèn)題和根本概念動(dòng)態(tài)規(guī)劃問(wèn)題和根本概念例中，道路圖(共18條道路,3321=18)枚舉法：例中，道路圖(共18條道路,3321=18)為處理這個(gè)最短途徑問(wèn)題，首先給出幾個(gè)定義。1 1、階段、階段(stage) 將所給問(wèn)題的過(guò)程，按時(shí)間或空間特征分解成假設(shè)干相互聯(lián)絡(luò)的段落，以便按次序求解就構(gòu)成了階段 ,階段變量常用字母 K 來(lái)表示。如例 .1有四個(gè)階段，K 就等于 1,2,3,4。第一階段共有 3 條道路即(A,B1), (A,B2)和(A,B3),第二階段

3、有 9 條道路，第 3 階段有 6 條道路,第 4 階段有 2 條道路。12342 2、 形狀形狀 ( state)各階段開(kāi)場(chǎng)時(shí)的出發(fā)點(diǎn)稱作形狀。 描畫(huà)各階段形狀的變量，稱作形狀變量，用sk 表示。 在例.1 中，第一階段的形狀為 A，第二階段的形狀為城市 B1，B2和B3。 所以形狀變量 S1 的集合 S1=A,S2 的集合是 S2=B1,B2,B3,依次有 S3=C1,C2,C3, S4=D1,D2。1234 3 3、 決策決策Decision ) Decision ) 當(dāng)各階段的形狀確定以后，就可以做出不同的決議或選擇，從而確定下一階段的形狀，這種決議就是決策，表示決策的變量稱為決策變量

4、。常用kXks表示第 K 階段當(dāng)形狀為ks時(shí)的決策變量， 在例.1中第二階段如決議從B1出發(fā)，即S2=B1，可選擇走C1或C2，C3 ，假設(shè)我們選擇，從C2走，那么此時(shí)的決策變量可表示x2(B1)=C2。12344 4、戰(zhàn)略、戰(zhàn)略 PolicyPolicy 在各階段決策確定以后，整個(gè)問(wèn)題的決策序列就構(gòu)成了一個(gè)戰(zhàn)略在各階段決策確定以后，整個(gè)問(wèn)題的決策序列就構(gòu)成了一個(gè)戰(zhàn)略, ,用用P1n(s1)P1n(s1)表示。表示。 如對(duì)于例.1總共可有18個(gè)戰(zhàn)略，但最優(yōu)戰(zhàn)略只需一個(gè)。12345 5、目的函數(shù)、目的函數(shù) 用于衡量所選定戰(zhàn)略優(yōu)劣的數(shù)量目的稱作目的函數(shù)。一個(gè)用于衡量所選定戰(zhàn)略優(yōu)劣的數(shù)量目的稱作目的

5、函數(shù)。一個(gè)n n階階段的決策過(guò)程，從段的決策過(guò)程，從1 1到到n n 叫作問(wèn)題的原過(guò)程。叫作問(wèn)題的原過(guò)程。 目的函數(shù)的最優(yōu)值稱為最優(yōu)目的函數(shù)，最優(yōu)目的函數(shù)記為目的函數(shù)的最優(yōu)值稱為最優(yōu)目的函數(shù)，最優(yōu)目的函數(shù)記為fk(sk)fk(sk)，它表示從第，它表示從第K K階段的形狀階段的形狀SkSk出發(fā)采用的最優(yōu)戰(zhàn)略。出發(fā)采用的最優(yōu)戰(zhàn)略。 當(dāng)當(dāng)K=1K=1時(shí)時(shí), f1(s1 ), f1(s1 )就是從初始形狀就是從初始形狀S1S1到全過(guò)程終了的整體最到全過(guò)程終了的整體最優(yōu)目的函數(shù)。優(yōu)目的函數(shù)。 , 在例.1中，目的函數(shù)就是間隔。如在第2階段，形狀為B2時(shí)，f2 (B2)那么表示從B2到E的最短間隔。本問(wèn)

6、題的總目的是求f 1(A), 即從A到E的最短間隔。12346 6、 形狀轉(zhuǎn)移方程形狀轉(zhuǎn)移方程在動(dòng)態(tài)規(guī)劃中，本階段的形狀往往是上階段決策的結(jié)果。所以假設(shè)給定了第 K 階段的形狀ks和該階段的決策kx(ks)，那么第 K+1 段的形狀1+ks由于 K 階段決策的完成也就完全確定了 ,它們之間的關(guān)系可用如下公式表示： 1+kskTks，kx其中，kT表示從形狀ks出發(fā)經(jīng)過(guò)kx向下一階段的轉(zhuǎn)移(Transfer)，換言之，即1+ks是從形狀ks出發(fā)經(jīng)過(guò)決策kx轉(zhuǎn)移的結(jié)果。由于上式表示了由 K 段到第 K+1 段的形狀轉(zhuǎn)移規(guī)律，所以就稱為形狀轉(zhuǎn)移方程。在例 .1中,形狀轉(zhuǎn)移方程即1+kskx。 為了求

7、出例.1的最短道路,一個(gè)簡(jiǎn)單的方法是,可以求出一切從A到E的能夠走法的路長(zhǎng)并加以比較。不難知道,從A到E共有18條不同的道路,每條道路有四個(gè)階段,要做3次加法,要求出最短道路需做54次加法運(yùn)算和17次比較運(yùn)算,這叫做窮舉法。 當(dāng)問(wèn)題的段數(shù)很多,各段的形狀也很多時(shí),這種方法的計(jì)算量會(huì)大大添加,甚至使得尋優(yōu)成為不能夠。 下面運(yùn)用動(dòng)態(tài)規(guī)劃方法求解例.1。運(yùn)用逆序遞推方法求解,即由最后一段到第一段逐漸求出各點(diǎn)到終點(diǎn)的最短道路,最后求出A點(diǎn)到E點(diǎn)的最短道路。 運(yùn)用逆序遞推方法的益處是可以一直盯住目的,不致脫離最終目的。 例.1是一個(gè)四階段決策問(wèn)題,普通可分為四步：1234第一步第一步,從從K=4開(kāi)場(chǎng)開(kāi)場(chǎng)

8、 1234S1S2S3S4逆序法求解最短路問(wèn)題形狀變量S4可取兩種形狀D1, D2,它們到E點(diǎn)的間隔分別為4和3,這也就是由D1和D2到終點(diǎn)E 的最短間隔， 即 f4(D1)=4, f4(D2)=3.第二步第二步 ,K=3形狀變量 S3 可取 3 個(gè)值即 C1,C2 和 C3。為方便運(yùn)用，規(guī)定用d(sk，sk+1)表示由形狀sk出發(fā)，到達(dá)下一階段sk+1時(shí)的兩點(diǎn)間隔。 3f1Cmin+)(),()(),(24211411DfDCdDfDCd=min+3543=7這闡明,由1c到 E 的最短間隔為 7,其途徑為以1C1DE,相應(yīng)的決策為*3x1C=1D1234S1S2S3S4+)(),()(),

9、(24221412DfDCdDfDCd 3f2Cmin=min+3246=5即從 C2 到 E的最短間隔為 5,其途徑為2C2DE,相應(yīng)的決策為*3x2C=2D1234S1S2S3S4即從 C3 到 E的最短間隔為 5,其途徑為 C3D1E,相應(yīng)的決策為*3x3C=1D。 3f3Cmin+)(),()(),(24231413DfDCdDfDCd=min+3341=51234S1S2S3S4第三步第三步, K=2, K=2由于第 3 段各點(diǎn) C1,C2,C3 到終點(diǎn) E 的最短間隔 f3(C1),f3(C2), f3(C3),知,所以要求城市 B1 到 E 的最短間隔,只需以它們?yōu)楦?分別加上

10、B1 到達(dá) C1,C2,C3 的一段間隔,加以比較取其最短者即可。即 B1 到終點(diǎn) E 的最短間隔為 9,其途徑為 B1C2D2E,本段的相應(yīng)決策為*2x1B=2C )(12Bf=min+)(),()(),()(),(333123211311CfCBdCfCBdCfCBd=min+555476=91234S1S2S3S4同理有: )(22Bf=min+)(),()(),()(),(333223221312CfCBdCfCBdCfCBd=min+565778=11 即*2x2B3CB2C3 D1 E1234S1S2S3S4+ )(32Bf=min+)(),()(),()(),(333323231

11、313CfCBdCfCBdCfCBd=min+595877=13 即*2x3B2C1234S1S2S3S4B3C2 D2 E第四步第四步, K=1, 只需一個(gè)形狀點(diǎn) A,那么 )(1Af=min+)(),()(),()(),(333232121BfBAdBfBAdBfBAd=min+13511998=171234S1S2S3S4從城市 A 到城市 E 的最短間隔為 17。把各段的最優(yōu)決策按計(jì)算順序反推,即得到最優(yōu)決策序列,即*1xA1B,*2 x1B=2C,*3 x2C2D，*4x2DE，所以最短道路為:AB1C2D2E.1234 圖例.1各點(diǎn)到終點(diǎn)的最短途徑根據(jù)例 .1, 動(dòng)態(tài)規(guī)劃的根本思想

12、可總結(jié)如下：一、 將多階段決策過(guò)程劃分階段,恰當(dāng)?shù)剡x取形狀變量,決策變量和定義最優(yōu)目的函數(shù),從而把問(wèn)題化成一族同類型的子問(wèn)題，然后逐個(gè)求解。二、 求解時(shí)從邊境開(kāi)場(chǎng)， 沿過(guò)程行進(jìn)方向，逐段遞推尋優(yōu)。在每一個(gè)子問(wèn)題求解時(shí),都要利用它前邊已求出的子問(wèn)題的最優(yōu)結(jié)果,最后一個(gè)子問(wèn)題的最優(yōu)解,就是整個(gè)問(wèn)題的最優(yōu)解。三、 動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段與未來(lái)各段分開(kāi),又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)思索的一種最優(yōu)化方法,因此,每段的最優(yōu)決策的選取都是從全局思索的,它與該段的最優(yōu)選擇是不同的。在例.1的求解過(guò)程中 , 各段的計(jì)算都利用了第K 段和第 K+1 段的如下關(guān)系：kfksminkdks，sk+1 )(11+

13、kksf (k=4,3,2,1) (1)(55sf 0 (2)這種遞推關(guān)系稱為動(dòng)態(tài)規(guī)劃的根本方程動(dòng)態(tài)規(guī)劃的根本方程,(2)式稱邊境條件,容易算出,運(yùn)用動(dòng)態(tài)規(guī)劃方法解例 .1 只進(jìn)展了 17 次加法運(yùn)算,11 次比較運(yùn)算，就獲得了最優(yōu)解,比窮舉法的計(jì)算量明顯地要少,而且隨著問(wèn)題段數(shù)的添加和變量程度的提高,計(jì)算量將呈指數(shù)規(guī)律減少。其次,動(dòng)態(tài)規(guī)劃的計(jì)算結(jié)果不僅得到了 A 到 E 的最短道路,而且得到了恣意一點(diǎn)到 E 點(diǎn)的最優(yōu)道路。這可由圖 .2 來(lái)描畫(huà)(用彩色線表示最優(yōu)道路,各點(diǎn)上的數(shù)字表最短間隔).2.1 最優(yōu)化原理最優(yōu)化原理 動(dòng)態(tài)規(guī)劃方法是由美國(guó)數(shù)學(xué)家貝爾曼(R.Bellman)等人于本世紀(jì) 5

14、0 年 代提出的。他們針對(duì)多階段決策問(wèn)題的特點(diǎn),提出理處理這類問(wèn)題的 最優(yōu) 化原理 ,并勝利地處理了消費(fèi)管理、工程技術(shù)許多方面的實(shí)踐問(wèn)題。最優(yōu)化 原理可以表述為：“一個(gè)過(guò)程的最優(yōu)戰(zhàn)略具有這樣的性質(zhì) , 即無(wú)論初始形狀 和初始決策如何,對(duì)于先前決策所構(gòu)成的形狀而言,其以后的一切決策必構(gòu)成 最優(yōu)戰(zhàn)略。 簡(jiǎn)言之：最優(yōu)戰(zhàn)略的任一子戰(zhàn)略都是最優(yōu)的。 假設(shè)把最優(yōu)化原理用數(shù)學(xué)言語(yǔ)描畫(huà),就得到了動(dòng)態(tài)規(guī)劃的根本方程： kfks opt)(),(11+kkkkksfxsd (k=n,n-1,1) 1+kf1+ks0 其中,opt 可依題意取max或min7.2.2 動(dòng)態(tài)規(guī)劃求解的根本步驟 求解動(dòng)態(tài)規(guī)劃 , 就是分

15、析問(wèn)題并建立問(wèn)題的動(dòng)態(tài)規(guī)劃根本方程。勝利地運(yùn)用動(dòng)態(tài)規(guī)劃方法的關(guān)鍵 ;在于識(shí)別問(wèn)題的多階段特征 ,將問(wèn)題 分解成可用遞推關(guān)系式聯(lián)絡(luò)起來(lái)的假設(shè)干子問(wèn)題 ,或者說(shuō)是要正確地建立具 體問(wèn)題的根本方程。而正確地建立關(guān)于遞推關(guān)系根本方程的關(guān)鍵，又 在于正確地選擇形狀變量保證各階段的形狀變量具有遞推的形狀轉(zhuǎn)移關(guān)系。 1+ks),(kkkxsT。 這是建立動(dòng)態(tài)規(guī)劃模型的兩個(gè)要點(diǎn)。 1234S1S2S3S4例P184 某公司有資金萬(wàn)元，擬投資于個(gè)工程，其收益分別為2111222333()4, ()9, ()2gxxgxxgxx可建立以下模型：2123123123max z=4x92 x10 x ,0 xxxxx

16、x+7.2.2 動(dòng)態(tài)規(guī)劃求解的根本步驟 2. 形狀變量ks：表示第 K 段可用于剩余的 n-k+1 個(gè)工程的資金數(shù), 顯然有1s=10, 4s=0。 3. 決策變量kx： 即應(yīng)分配第 K 個(gè)工程上的投資額。 1.階段：K=1，2，4. 形狀轉(zhuǎn)移方程：kkkxss-+1 5. 最優(yōu)目的函數(shù)kfks：表示當(dāng)可投資金數(shù)為ks時(shí),投資于剩余的 n-k+1個(gè)工程的最大收益。 6. 根本方程為： +0)()()(max)(1111nnkkkkkksfsfxgsf k=3,2,1 (逆序解法)投資問(wèn)題: 設(shè)總投資額為 A萬(wàn)元, 擬投資于n個(gè)工程上，知對(duì)第i 個(gè)工程投 資ix萬(wàn)元,收益函數(shù)為)(iixg,問(wèn)應(yīng)

17、如何分配資金才可以使總收益最大 ? 這是一個(gè)與時(shí)間無(wú)明顯關(guān)系的靜態(tài)最優(yōu)化問(wèn)題 ,可先列出其靜態(tài)模型為： 為了運(yùn)用動(dòng)態(tài)規(guī)劃方法求解, 我們可以人為地賦予它“時(shí)段的概 念。方法是將投資工程排序, 假想對(duì)各個(gè)投資工程有先后順序。 首先考 慮對(duì)項(xiàng)目 1 的投資, 然后思索對(duì)工程 2 的投資, 依次最后思索第 n 項(xiàng) 投資.這樣就把原問(wèn)題轉(zhuǎn)化為 n 階段的決策過(guò)程。接下來(lái)的問(wèn)題，便是如 何選擇正確的形狀變量,并使各后部子過(guò)程間具有遞推關(guān)系。 Max Vniiixg1)( s.t. Axnii1 0ix (i=1,2,n) 2. 形狀變量ks：表示第 K 段可用于剩余的 n-k+1 個(gè)工程的資金數(shù), 顯然

18、有1s=A, 1+ns=0。 3. 決策變量kx： 即應(yīng)分配第 K 個(gè)工程上的投資額。 1.階段：K=1，2，n4. 形狀轉(zhuǎn)移方程：kkkxss-+1 5. 最優(yōu)目的函數(shù)kfks：表示當(dāng)可投資金數(shù)為ks時(shí),投資于剩余的 n-k+1個(gè)工程的最大收益。 6. 根本方程為： +0)()()(max)(1111nnkkkkkksfsfxgsf k=n,n-1,2,1 假設(shè)運(yùn)用逆序遞推尋優(yōu), 那么)(1s1f就是所求的最大收益。 7.2.3 動(dòng)態(tài)規(guī)劃求解時(shí)的幾種常用算法離散變量的分段窮舉法如最短路問(wèn)題的解法, 離散型資源分配問(wèn)題等延續(xù)變量的解法根據(jù)方程的詳細(xì)情況靈敏選取求解方法a.逆序解法b.順序解法如

19、延續(xù)型資源分配問(wèn)題等例用動(dòng)態(tài)規(guī)劃方法求解以下問(wèn)題2123123123max z=4x92 x10 x ,0 xxxxxx+解：采用逆序解法順序解法的根本方程為： +0)()()(max)(144k+1kkkkksfsfxgsf k=3,2,1當(dāng)3時(shí)，有333333440()m a x ()()xsfsgxfs+33230max 2xsx可以看到,當(dāng) 時(shí), f3(s3)獲得極大值*33xs332233330()max22xsfsxs當(dāng)時(shí)，有222222330()max ()()xsfsgxfs+222223302230m ax 9()m ax 92)xsxsxfsxs+2222220m ax 9

20、2() xsxsx+-2222222 (,)92()h sxxsx+-記 求其極值點(diǎn):22222294 ()(1)09 4d hsxd xxs+-這是一個(gè)極小點(diǎn), 為什么?所以,極大值只能夠在0,s2的端點(diǎn)獲得, 那么有2222222()2 ()9fssfss或當(dāng)1時(shí)，有111111220()max ()()xsfsgxfs+111220max4()xsxfs+分兩種情況: 討論!當(dāng) x1=0時(shí), f1(10)=200, 到達(dá)最大值.再由形狀轉(zhuǎn)移方程順推,可求出: x2=0 x3=10例用動(dòng)態(tài)規(guī)劃方法求解以下問(wèn)題2123123123max z=4x92 x10 x ,0 xxxxxx+解：采用

21、順序解法順序解法的根本方程為： +0)()()(max)(1kkkkkksfsfxgsf k=3,2,1當(dāng)時(shí)，有121211010()max ()()xsfsgxfs+12102m a x 44xsxs12*xs當(dāng)時(shí)，有232322120()max ()()xsfsgxfs+23232120220m a x 9() m a x 94) xsxsxfsxs+23232320230m a x 94 () m a x 54) xsxsxsxxs+-+39 s*23xs當(dāng)3時(shí)，有343433230()max ()()xsfsgxfs+34342323023430m a x 2() m a x 29 (

22、) xsxsxfsxsx+-2343h(s,x)=2x9()sx+-記33490dhxdx-求導(dǎo)，得934x解得223 40d hdx此點(diǎn)僅為極小點(diǎn)極大值應(yīng)在0，s4=0，10的端點(diǎn)獲得當(dāng)x3=0時(shí)，f3 (10)=90當(dāng)x3=10時(shí)，f3 (10)=200*3 10 x再由形狀轉(zhuǎn)移方程逆推： *332*232*1100 x000sxssxx-逆序解法的過(guò)程見(jiàn)書(shū) P.3.1 資源分配問(wèn)題 例 某企業(yè)共有設(shè)備 5 臺(tái),擬分給三個(gè)工廠,各工廠利用這些設(shè)備 為企業(yè)可提供的盈利 kk(x )g各不一樣 ( 見(jiàn)表.4) ,問(wèn)應(yīng)如何分配這四臺(tái) 設(shè)備才干使企業(yè)獲得的盈利最大? 表 .4 有關(guān)資料 單位：萬(wàn)元

23、 設(shè)備分配數(shù) )(11xg )(22xg )(33xg 0 1 2 3 45 0 3 7 9 1213 0 5 10 11 1111 0 4 6 11 1212 甲廠乙廠丙廠 Max z3iiixg1)( s.t. 5xnii1 0ix (i=1,2,n) 分析: 可建立如下模型解： 1.將問(wèn)題按工廠分為三個(gè)階段，k=1,2,3 2.設(shè) xk分配給第k個(gè)工廠的設(shè)備臺(tái)數(shù)。S1S2S3S4甲廠x1乙廠x2丙廠x33.形狀轉(zhuǎn)移方程：Sk+1=Sk - xk知 s1=5 s2=s1-x1 s3=s2-x2 4.目的函數(shù)為: fk(sk)=maxgk(xk)+fk+1(sk+1) k=3,2,1 f4(

24、s4)=0 設(shè)備分配數(shù) )(11xg )(22xg )(33xg 0 1 2 3 45 0 3 7 9 1213 0 5 10 11 1111 0 4 6 11 1212 甲廠乙廠丙廠當(dāng) K=3時(shí)形狀變量3s的取值范圍為3s0，1，2，3，4 ,53x的取值范圍也是3D0，1，2，3，4, 5 ,33sx 0)(44sf,K=3時(shí)的結(jié)果如下表: x3s3f3(s3)=g3(x3)+ f4(s4)f3(s3)x30123450123455.列表計(jì)算：046111212012345046111212當(dāng)K=2時(shí)223xss-322ssx- X2s2f2(s2)=g2(x2)+f3(s3)f2(s2)

25、x20123450123450+00+40+60+110+120+125+05+45+65+115+1210+010+410+610+1111+011+411+611+011+411+00051102142 161,2212形狀變量的取值范圍為 s2=0,1,2,3,4,5,x2的取值范圍也是2D0，1，2，3，4, 5 ,當(dāng)k=1時(shí)，s1=5, x1的可取值為0,1,2,3,4,5計(jì)算結(jié)果如下： x1s1f1(s1)=g1(x1)+f2(s2)f1(s1)x10123455最優(yōu)分配方案有兩個(gè)：x1=0, x2=2, x3=30+213+167+14 9+10 12+5 13+0210，2x1

26、=2, x2=2, x3=1例 7.5 一運(yùn)輸商擬用一 10 噸載分量的大卡車裝載 3 種貨物, 資料如下表,問(wèn)應(yīng)如何組織裝載,可使總價(jià)值最大? 解： 設(shè)裝載第三種貨物的件數(shù)為ix，那么有： Max z=41x+52x+63x s.t. 31x+42x+53x10 0 xi 且為整數(shù) 貨物編號(hào)1 2 3單位分量噸單位價(jià)值(百元)3 4 54 5 67.3.2背包問(wèn)題背包問(wèn)題是動(dòng)態(tài)規(guī)劃的典型問(wèn)題。一維背包問(wèn)題的典型提法是：一位游覽者能接受的背包最大分量是 b 千克，現(xiàn)有 n 種物品供他選擇裝入背包，第 i 種物品單件分量為ia千克，其價(jià)值(或重要性參數(shù))為 ci，總價(jià)值是攜帶數(shù)量ix的函數(shù)即ii

27、xc，問(wèn)游覽者應(yīng)如何選擇所攜帶物品的件數(shù)以使總價(jià)值最大? 模型可表述為：niiixcz1max s.t. bxaniii1 0ix 且為整數(shù)i=1,2,n段。用動(dòng)態(tài)規(guī)劃方法來(lái)求解1. 階段 k：即需求裝入的 n 種物品的次序,每段裝入一種,共 n2. 形狀變量ks：即在第 k 段開(kāi)場(chǎng)時(shí),允許裝入前 k 種物品的總重量，顯然有1s=b 3. 決策變量kx：即裝入第 K 種物品的件數(shù)4. 形狀轉(zhuǎn)移方程：kkkkxass-+1允許的決策集合是：kkkkkkasxxsD0|)(且為整數(shù) 5. 目的函數(shù)是:)+nkSn+1fsfxcsfk+1kkkkk,.,2, 10)(max)(n+11當(dāng)K=3時(shí)，S

28、3=0，1，2，10 ， f3(S3)=max6x3+0 x3s36x3+0f3(s3)x301201234567891000000666661200000666661200000111112 x2s25x2+ f3(S3)f2(s2)x2012012345678910當(dāng)K=2時(shí)，S2=0，1，2，10， f2(S2)=max6x2+ f3(S3)000000+60+60+60+60+60+125+05+05+05+05+05+65+610+010+010+00000566610111100001000211當(dāng)K=1時(shí)，S1=10, f1(S1)=max4x1+ f2(S2) x1s14x1+

29、 f2(S2)f1(s1)x1S2012310最優(yōu)解為： X1*=2, X2*=1, X3*=0 Z*=130+114+68+512+013247.3.3 消費(fèi)與存儲(chǔ)問(wèn)題 例 7.6 某廠消費(fèi)的一種產(chǎn)品，以后四個(gè)月的訂單如下表：月份1234訂貨量bk)3324合同規(guī)定在各月底前交貨，消費(fèi)每批產(chǎn)品的固定本錢為3千元，每批消費(fèi)的產(chǎn)品件數(shù)不限。每件產(chǎn)品的可變本錢為1千元，每批產(chǎn)品的最大消費(fèi)才干為5件。產(chǎn)品每件每月的存儲(chǔ)費(fèi)為500元。又知1月初有庫(kù)存產(chǎn)品1件，4月底不再留下產(chǎn)品。試在滿足需求的前提下，如何組織消費(fèi)才干使總的本錢最低。解：1.設(shè)階段變量為K,那么每月為一個(gè)階段,K=1,2,3,40 xk

30、5,4. 形狀轉(zhuǎn)移方程由下式確定： 1+ks kkkbxs-+ 其中 ,kd表示第 K 階段的產(chǎn)品總本錢，即 ),(kkkxsd+)0(0.5sk)50(3kkxxxk+0.5sk2.每月初的產(chǎn)品庫(kù)存量作為形狀變量，由知條件顯然有S1=1，S5=03.決策變量是每月的產(chǎn)品消費(fèi)量，由知條件知： 5. 建立根本方程即本錢最小化)(),(min)(11+kkkkkUkksfxsdsfkk=4,3,2,10)(55sf當(dāng)K=4時(shí)，S4的最小能夠值為0，即4月初沒(méi)有存貨。S4的最大能夠值=5313 3 2，4=4即 S4=0，1，2，3，4。 K=4s4本階段費(fèi)用s5f5(s5)d+ f5(s5)f4(s4)x4消費(fèi)費(fèi)用存儲(chǔ)費(fèi)d(s4,x4)043+4070077133+30.56.5006