第十章-動態(tài)規(guī)劃-《管理運籌學》課件

多階段決策過程最優(yōu)化問題舉例例1最短路徑問題下圖表示從起點A到終點E之間各點的距離。求A到E的最短路徑。1BACBDBCDEC412312312322164724838675611063751§1§1多階段決策過程最優(yōu)化問題舉例窮舉法:如果從A到E的站點有k個，除A、E之外每站有3個位置，則總共有3k-1×2條路徑；計算各路徑長度總共要進行(k+1)3k-1×2次加法以及3k-1×2-1次比較。例如：當k=20時，加法進行4.26×1015

次，比較1.37×1014次。若用1億次/秒的計算機計算需要約508天。2§1§1多階段決策過程最優(yōu)化問題舉例討論：以上求從A到E的最短路徑問題，可以轉(zhuǎn)化為四個性質(zhì)完全相同，但規(guī)模較小的子問題，即分別從Di

、Ci、Bi、A到E的最短路徑問題。3§1§1多階段決策過程最優(yōu)化問題舉例第四階段：兩個始點D1和D2，終點只有一個；

分析得知：從D1和D2到E的最短路徑唯一。4本階段始點（狀態(tài)）本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)ED1D210*6106EE§15第三階段：有三個始點C1，C2，C3，終點有D1，D2，分別求C1，C2，C3到D1，D2

的最短路徑問題：

分析得知：如果經(jīng)過C1，則最短路為C1-D2-E；如果經(jīng)過C2，則最短路為C2-D2-E；如果經(jīng)過C3，則最短路為C3-D1-E。

多階段決策過程最優(yōu)化問題舉例本階段始點（狀態(tài)）本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111D2D2D1§16第二階段：始點B1,B2,B3,B4，終點C1,C2,C3，分別求B1,B2,B3,B4到C1,C2,C3的最短路徑問題：

分析得知：如果經(jīng)過B1，則走B1-C2-D2-E；如果經(jīng)過B2，則走B2-C3-D1-E；如果經(jīng)過B3，則走B3-C3-D1-E；如果經(jīng)過B4，則走B4-C3-D1-E。

本階段始點（狀態(tài)）

本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C3§1多階段決策過程最優(yōu)化問題舉例7第一階段：只有1個始點A，終點有B1,B2,B3,B4

，分別求A到B1,B2,B3,B4的最短路徑問題：可以得到：從A到E的最短路徑為AB4C3D1E本階段始點(狀態(tài))

本階段各終點（決策）到E的最短距離本階段最優(yōu)終點(最優(yōu)決策)B1B2B3B4A4+12=163+13=163+14=172+12=14

14B4§1多階段決策過程最優(yōu)化問題舉例8

以上計算過程及結(jié)果，可用下圖表示，不僅得到了從A到D的最短路徑，同時也得到了從圖中任一點到E的最短路徑。

以上過程，僅用了22次加法，計算效率遠高于窮舉法。BACBDBCDEC41231231233216472483867516106010612111112131414127512§1多階段決策過程最優(yōu)化問題舉例9一、基本概念：

1、階段k：表示決策順序的離散的量，可以按時間或空間劃分。

2、狀態(tài)sk：能確定地表示決策過程當前特征的量?？梢允菙?shù)量、字符，數(shù)量狀態(tài)可以連續(xù)、離散。

3、決策xk：從某一狀態(tài)向下一狀態(tài)過渡時所做的選擇。是所在狀態(tài)的函數(shù)，記為xk(sk)。

4、決策允許集合Dk(sk)：在狀態(tài)sk下，允許采取決策的全體。

5、策略Pk,n(sk)：從第k階段開始到最后第n階段的決策序列，稱k子策略。P1,n(s1)即為全過程策略?！?基本概念、基本方程與最優(yōu)化原理106、狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk,xk)：某一狀態(tài)及該狀態(tài)下的決策，與下一狀態(tài)之間的函數(shù)關(guān)系。7、階段指標函數(shù)vk(sk,xk)：從狀態(tài)sk出發(fā)，選擇決策xk所產(chǎn)生的第k階段指標。8、過程指標函數(shù)Vk,n(sk,xk,xk+1,…,xn)：從狀態(tài)sk出發(fā)，選擇決策xk,xk+1,…,xn所產(chǎn)生的過程指標。過程指標具有可分離性：若Vk,n(sk,xk,xk+1,…,xn)=vk(sk,xk)+Vk+1(sk+1,xk+1,…,xn),稱指標具有可加性；若Vk,n(sk,xk,xk+1,…,xn)=vk(sk,xk)×Vk+1(sk+1,xk+1,…,xn)，稱指標具有可乘性?！?基本概念、基本方程與最優(yōu)化原理11二、基本方程：最優(yōu)指標函數(shù)fk(sk)：從狀態(tài)sk出發(fā)，對所有的策略Pk,n，過程指標Vk,n的最優(yōu)值，即對于可加性指標函數(shù)，上式可以寫為

上式中“opt”表示“max”或“min”。對于可乘性指標函數(shù)，上式可以寫為

稱為動態(tài)規(guī)劃最優(yōu)指標的遞推方程。終端條件：為了使以上的遞推方程有遞推的起點，必須要設(shè)定最優(yōu)指標的終端條件，一般（對加指標）最后一個狀態(tài)n+1下最優(yōu)指標fn+1(sn+1)=0?！?基本概念、基本方程與最優(yōu)化原理12三、最優(yōu)化原理作為整個過程的最優(yōu)策略具有如下性質(zhì)：不管在此最優(yōu)策略上的某個狀態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)來說，以后的所有決策必定構(gòu)成最優(yōu)子策略。就是說，最優(yōu)策略的任意子策略都是最優(yōu)的。§2基本概念、基本方程與最優(yōu)化原理13一、資源分配問題

例2.某公司擬將某種設(shè)備5臺，分配給所屬的甲、乙、丙三個工廠。各工廠獲得此設(shè)備后，預(yù)測可創(chuàng)造的利潤如表所示，問這5臺設(shè)備應(yīng)如何分配給這3個工廠，使得所創(chuàng)造的總利潤為最大？

工廠盈利設(shè)備臺數(shù)

甲廠

乙廠

丙廠000013542710639111141211125131112§3動態(tài)規(guī)劃的應(yīng)用(1)14解：按甲、乙、丙工廠分為三個階段，編號1、2、3。設(shè)=分配給第k個廠至第3個廠的設(shè)備臺數(shù)。

=分配給第k個廠的設(shè)備臺數(shù)。已知,并有

從與的定義和本題目已知數(shù)據(jù)的特點，可知

§3動態(tài)規(guī)劃的應(yīng)用(1)15第三階段:

將臺設(shè)備都分配給第3工廠時，第3階段的指標值（盈利）為最大，即

由于第3階段是最后的階段，故有其中可取值為0,1,2,3,4,5。其數(shù)值計算見表。

§3動態(tài)規(guī)劃的應(yīng)用(1)16

§3動態(tài)規(guī)劃的應(yīng)用(1)01234500-------------------------001-----4--------------------412----------6---------------623---------------11----------1134--------------------121245-------------------------12125表示取3子過程上最優(yōu)指標值時的的決策。17例：在表中可知當

時，有此時，即當時，此時?。ò?臺設(shè)備分配給第3廠）是最優(yōu)決策，此時階段指標值（盈利）為12，最優(yōu)3子過程最優(yōu)指標值也為12。

§3動態(tài)規(guī)劃的應(yīng)用(1)18

第二階段：當把臺設(shè)備分配給第2工廠和第3工廠時，則對每個值，有一種最優(yōu)分配方案，使最大盈利，即最優(yōu)2子過程最優(yōu)指標函數(shù)值為因為上式也可寫成§3動態(tài)規(guī)劃的應(yīng)用(1)19數(shù)值計算如表。

§3動態(tài)規(guī)劃的應(yīng)用(1)0123450------------------------------001------------------------512------------------1023------------1424------161,2521220例如在的這一行里，當時，查前兩表可知，當時，同樣可知

當時，；當時，當時，

§3動態(tài)規(guī)劃的應(yīng)用(1)21由于，不可能分2廠5臺設(shè)備，故當時，欄不填。從這些數(shù)值中取最大，即得。在取最大值的上加一橫，可知的最優(yōu)決策為1或2?！?動態(tài)規(guī)劃的應(yīng)用(1)22

第一階段：把臺設(shè)備分配給第1，第2，第3廠時，最大盈利為其中

然后按計算表格的順序推算，可知最優(yōu)分配方案有兩個：

0

1

2

3

4

5

5

§3動態(tài)規(guī)劃的應(yīng)用(1)23§3動態(tài)規(guī)劃的應(yīng)用(1)1.由于，根據(jù)，查表10－7可

知，再由，求得。即分配給甲廠0臺，乙廠2臺，丙廠3臺。2.由于，根據(jù)，查表10－7可知，再由,求得，即分配給甲廠2臺，乙廠2臺，丙廠1臺。這兩種分配方案都能得到最高的總盈利21萬元。24二、背包問題設(shè)有

種物品，每種物品數(shù)量無限。第

種物品每件重量為

公斤，每件價值

元。現(xiàn)有一只可裝載重量為

公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價值最高。用整數(shù)規(guī)劃模型來描述。設(shè)

為第

種物品裝入背包的件數(shù)，背包中物品的總價值為

，則且為整數(shù)

§3動態(tài)規(guī)劃的應(yīng)用(1)25用動態(tài)規(guī)劃方法解：設(shè)階段變量

：第k次裝載第k種物品狀態(tài)變量

：第k次裝載時背包還可以裝載的重量；決策變量

：第k次裝載第k種物品的件數(shù)；決策允許集合：；狀態(tài)轉(zhuǎn)移方程：

；階段指標：；最優(yōu)過程指標函數(shù)

：第k到n階段容許裝入物品的最大價值；遞推方程： 終端條件：§3動態(tài)規(guī)劃的應(yīng)用(1)26

例3.某咨詢公司有10個工作日可以去處理四種類型的咨詢項目，每種類型的咨詢項目中待處理的客戶數(shù)量、處理每個客戶所需工作日數(shù)以及所獲得的利潤如表所示。顯然該公司在10天內(nèi)不能處理完所有的客戶，它可以自己挑選一些客戶，其余的請其他咨詢公司去做，應(yīng)如何選擇客戶使得在這10個工作日中獲利最大？

咨詢項目類型待處理客戶數(shù)處理每個客戶所需工作日數(shù)處理每個客戶所獲利潤

1

2

3

4

4

3

2

2

1

3

4

7

2

8

11

20§3動態(tài)規(guī)劃的應(yīng)用(1)27

解：我們把此問題分成四個階段。第一階段我們決策將處理多少個第一種咨詢項目類型中的客戶，第二階段決策將處理多少個第二種咨詢項目類型中的客戶，第三階段、第四階段我們也將作出類似的決策。設(shè)＝分配給第k種咨詢項目到第四種咨詢項目的客戶的總工作日（第k階段的狀態(tài)變量）。

=在第k種咨詢項目中處理客戶的數(shù)量（第k階段的決策變量）。已知＝10，并有

§3動態(tài)規(guī)劃的應(yīng)用(1)28第四階段：將個工作日盡可能分配給第四類咨詢項目，即時，第四階段的指標值為最大，表示取不大于的最大整數(shù)，符號為取整符號，故有由于第四階段是最后的階段，故有§3動態(tài)規(guī)劃的應(yīng)用(1)因為至多為10，數(shù)值計算見表。

29

0

1

0

－

0

0

1－

0

0

2－

0

0

3－

0

0

4－

0

0

5

－

0

0

6－

0

0

7

0

20

1

8

0

20

1

9

0

20

1

10

0

20

1§3動態(tài)規(guī)劃的應(yīng)用(1)30第三階段：當把個工作日分配給第四類和第三類咨詢項目時，則對每個值，都有一種最優(yōu)分配方案，使其最大盈利即最優(yōu)3子過程最優(yōu)指標函數(shù)值為因為，故

因為至多為10，所以的取值可為0,1,2。數(shù)值計算見表。

§3動態(tài)規(guī)劃的應(yīng)用(1)31§3動態(tài)規(guī)劃的應(yīng)用(1)0120--------001--------002--------003--------004----1115----1116----1117----200822292221022232

第二階段：同樣以每個值都有一種最優(yōu)分配方案，使其最大盈利即最優(yōu)2子過程最優(yōu)指標函數(shù)值為：因為，故

因為至多為10，所以的取值為0,1,2,3。其數(shù)值計算見表?！?動態(tài)規(guī)劃的應(yīng)用(1)33§3動態(tài)規(guī)劃的應(yīng)用(1)01230------------001------------002------------003--------814--------1105--------1106----1627----2008----22092431028134第一階段：已知，又因為，同樣有

因為,故可取值為0,1,2,…,10。其數(shù)值計算見表?！?動態(tài)規(guī)劃的應(yīng)用(1)35由上表知，，從而，由表的的這一行可知由由表的的這一行可知由，查表的這一行得綜上所述得最優(yōu)解為：最大盈利為28。

§3動態(tài)規(guī)劃的應(yīng)用(1)0123456789101028036§3動態(tài)規(guī)劃的應(yīng)用(1)現(xiàn)在我們假設(shè)該咨詢公司的工作計劃有所改變，只有8個工作日來處理這四類咨詢項目，那么該咨詢公司如何選擇客戶使得獲利最大？我們只要在第一階段上把改成8，重新計算即可，如下表所示，這是動態(tài)規(guī)劃的一個好處。0123456788220.137從而得到兩組最優(yōu)解如下：

最優(yōu)解（即最大盈利）都為22。一旦咨詢的工作日不是減少而是增加，那么我們不僅要重新計算第一階段，而且要在第二、第三、第四階段的計算表上補上增加的工作日的新的信息，也可得到新的結(jié)果?！?動態(tài)規(guī)劃的應(yīng)用(1)38三、生產(chǎn)與存貯問題例4.某公司為主要電力公司生產(chǎn)大型變壓器，由于電力采取預(yù)訂方式購買，所以該公司可以預(yù)測未來幾個月的需求量。為確保需求，該公司為新的一年前四個月制定一項生產(chǎn)計劃，這四個月的需求如表所示。生產(chǎn)成本隨著生產(chǎn)數(shù)量而變化。調(diào)試費為4，除了調(diào)試費用外，每月生產(chǎn)的頭兩臺各花費為2，后兩臺花費為1。最大生產(chǎn)能力每月為4臺，生產(chǎn)成本如表所示。

§3動態(tài)規(guī)劃的應(yīng)用(1)39§3動態(tài)規(guī)劃的應(yīng)用(1)每臺變壓器在倉庫中由這個月存到下個月的儲存費為1，倉庫的最大儲存能力為3臺，另外，1月1日時倉庫里存有一臺變壓器，要求在4月30日倉庫的庫存量為零。生產(chǎn)件數(shù)總成本00162839410月份n需求量（臺）12243143試問：該公司應(yīng)如何制定生產(chǎn)計劃，使得四個月的生產(chǎn)成本和儲存總費用最少？40解：第k個月為第i階段設(shè)為第k階段期初庫存量；為第k階段生產(chǎn)量；

為第k階段需求量；

因為下個月的庫存量等于上個月的庫存量加上上個月的產(chǎn)量減去上個月的需求量，得到狀態(tài)轉(zhuǎn)移方程：因為，故有因為，故有

§3動態(tài)規(guī)劃的應(yīng)用(1)41

由于必須要滿足需求，則有

通過移項得到

另一方面，第k階段的生產(chǎn)量必不大于同期的生產(chǎn)能力（4臺），也不大于第k階段至第四階段的需求之和與第k階段期初庫存量之差，否則第k階段的生產(chǎn)量就要超過從第k階段至第四階段的總需求，故有

§3動態(tài)規(guī)劃的應(yīng)用(1)42第四階段：從狀態(tài)轉(zhuǎn)移方程可知這樣就有階段指標可以分成生產(chǎn)成本與儲存費，即由于第四階段末要求庫存為零，即有，可得§3動態(tài)規(guī)劃的應(yīng)用(1)43對于每個的可行值，的值列于表。

當時，可知第四階段要生產(chǎn)臺，總成本為9。同理算出當為1,2,3時的情況?！?動態(tài)規(guī)劃的應(yīng)用(1)01230---------------9931----------8-----822-----6----------6130---------------0044

第三階段：此時有：因為

以及

所以有結(jié)果所示：

§3動態(tài)規(guī)劃的應(yīng)用(1)012340-----1341-----902----------903---------------8045

計算結(jié)果如表所示?！?動態(tài)規(guī)劃的應(yīng)用(1)第二階段：因為所以有012340--------------------2341---------------2042----------1933-----18246第一階段：因為故有

計算結(jié)果見表。§3動態(tài)規(guī)劃的應(yīng)用(1)012341-----291,247

利用遞推關(guān)系得到兩組最優(yōu)解：這時有最低總成本29?！?動態(tài)規(guī)劃的應(yīng)用(1)四、系統(tǒng)可靠性問題例5.某科研項目組由三個小組用不同的手段分別研究，它們失敗的概率各為0.40，0.60，0.80。為了減少三個小組都失敗的可能性，現(xiàn)決定給三個小組中增派兩名高級科學家到各小組，各小組科研項目失敗概率如下表，問如何分派科學家才能使三個小組都失敗的概率（即科研項目最終失敗的概率）最??？高級科學家小組12300.400.600.8010.200.400.5020.150.200.3048§3動態(tài)規(guī)劃的應(yīng)用(1)解：用逆序算法。設(shè)階段：每個研究小組為一個階段

決策變量

：分配給第n小組的高級科學家數(shù)目，相應(yīng)的失敗概率為；

狀態(tài)變量

：在階段n時可分配于階段

的高級科學家人數(shù)。

遞推關(guān)系：階段123小組12349§3動態(tài)規(guī)劃的應(yīng)用(1)當n=3時，當n=2時，50s3f3*(s3)x3*00.80010.50120.302x2s2f2(s2,x2)=P2(x2)*f3*(s2-x2)f2*(s2)x2*01200.480.48010.300.320.30020.180.200.160.162§3動態(tài)規(guī)劃的應(yīng)用(1)當n=1時，最優(yōu)解為x1*=1，x2*=0，x3*=1；科研項目最終失敗的概率為0.060。51x1s1f1(s1,x1)=P1(x1)·f2*(s1-x1)f2*(s2)x2*01220.0640.0600.0720.0601§3動態(tài)規(guī)劃的應(yīng)用(1)一、連續(xù)確定性動態(tài)規(guī)劃

對于狀態(tài)變量和決策變量只取連續(xù)值，過程的演變方式為確定性時，這種動態(tài)規(guī)劃問題就稱為連續(xù)確定性動態(tài)規(guī)劃問題。52§4動態(tài)規(guī)劃的應(yīng)用(2)機器負荷分配問題例1一種機器能在高低兩種不同的負荷狀態(tài)下工作。設(shè)機器在高負荷下生產(chǎn)時，產(chǎn)量函數(shù)為P1=8u1，其中u1為在高負荷狀態(tài)下生產(chǎn)的機器數(shù)目，年完好率為a=0.7，即到年底有70％的機器保持完好。在低負荷下生產(chǎn)時，產(chǎn)量函數(shù)為P2=5u2，其中u2為在低負荷狀態(tài)下生產(chǎn)的機器數(shù)目，年完好率為b=0.9。設(shè)開始生產(chǎn)時共有1000臺完好的機器，請問每年應(yīng)該如何把完好機器分配給高、低兩種負荷下生產(chǎn)，才能使得5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。53§4動態(tài)規(guī)劃的應(yīng)用(2)解建立動態(tài)規(guī)劃模型：分為5個階段，每個階段為1年。設(shè)狀態(tài)變量sk表示在第k階段初擁有的完好機器數(shù)目；k=1,2,3,4,5。

決策變量xk表示第k階段中分配給高負荷狀態(tài)下生產(chǎn)的機器數(shù)目；sk-xk為分配給低負荷狀態(tài)下生產(chǎn)的機器數(shù)目。狀態(tài)轉(zhuǎn)移方程為sk+1=0.7xk+0.9(sk-xk)

階段指標rk(sk,xk)=8xk+5(sk-xk)

最優(yōu)指標函數(shù)f6(s6)=054§4動態(tài)規(guī)劃的應(yīng)用(2)第5階段：因為f5(s5)是x5的線性單調(diào)增函數(shù)，故有x5*=s5，于是有f5(s5)=8s5。第4階段：同樣，f4(s4)是x4的線性單調(diào)增函數(shù)，有x4*=s4，f4(s4)=13.6s4。

55

§4動態(tài)規(guī)劃的應(yīng)用(2)依次類推，可得f3(s3)=17.52s3，

f2(s2)=20.768s2，

f1(s1)=23.6912s1。因為期初共有完好機器1000臺，故s1=1000。有f1(s1)=23.6912s1＝23691.2，即5年最大的產(chǎn)量為23691臺。最優(yōu)解為即前兩年應(yīng)把年初完好機器完全投入低負荷生產(chǎn)，后三年應(yīng)把年初完好機器完全投入高負荷生產(chǎn)。56§4動態(tài)規(guī)劃的應(yīng)用(2)下一步工作是確定每年初的狀態(tài)，按照從前向后的順序依次計算出每年年初完好的機器數(shù)目。已知,根據(jù)狀態(tài)轉(zhuǎn)移方程，有:57§4動態(tài)規(guī)劃的應(yīng)用(2)

上面所討論的最優(yōu)策略過程，初始端狀態(tài)s1=1000臺是固定的，終點狀態(tài)s6沒有要求。這種情況下得到最優(yōu)決策稱為初始端固定終點自由的最優(yōu)策略。如果終點附加一定的條件，則問題就稱為“終端固定問題”。例如，規(guī)定在第5年度結(jié)束時仍要保持500臺機器完好（而不是278臺），應(yīng)如何安排生產(chǎn)才能使得總產(chǎn)量最大？

58§4動態(tài)規(guī)劃的應(yīng)用(2)顯然，由于固定了終點的狀態(tài)，x5的取值受到了約束。因此有類似的，容易解得，

。

59§4動態(tài)規(guī)劃的應(yīng)用(2)根據(jù)終點條件有可得依次類推，得再采用順序方法遞推計算各年的狀態(tài)，有

60§4動態(tài)規(guī)劃的應(yīng)用(2)

可見，為了使終點完好的機器數(shù)量增加到500臺，需要安排前四年中全部完好機器都要投入低負荷生產(chǎn)，且在第5年，有臺投入高負荷生產(chǎn)，204臺投入低負荷生產(chǎn)。相應(yīng)的最優(yōu)指標為

可以看到，因為增加了附加條件，總產(chǎn)量要比終點自由情況下的產(chǎn)量要低。61§4動態(tài)規(guī)劃的應(yīng)用(2)二、離散隨機性動態(tài)規(guī)劃隨機型的動態(tài)規(guī)劃是指狀態(tài)的轉(zhuǎn)移律是不確定的，即對給定的狀態(tài)和決策，下一階段的到達狀態(tài)是具有確定概率分布的隨機變量，這個概率分布由本階段的狀態(tài)和決策完全確定。其基本結(jié)構(gòu)如下：

62sk狀態(tài)xk決策概率k階段的收益p1p2pN….k+1階段的狀態(tài)sk+1c1c2cN12N§4動態(tài)規(guī)劃的應(yīng)用(2)

圖中N表示第k+1階段可能的狀態(tài)數(shù)，p1、p2、…pN為給定狀態(tài)sk和決策xk的前提下，可能達到下一個狀態(tài)的概率。ci為從k階段狀態(tài)sk轉(zhuǎn)移到k+1階段狀態(tài)為i時的指標函數(shù)值。在隨機性的動態(tài)規(guī)劃問題中，由于下一階段到達的狀態(tài)和階段的效益值不確定，只能根據(jù)各階段的期望效益值進行優(yōu)化。63§4動態(tài)規(guī)劃的應(yīng)用(2)

例2某公司承擔一種新產(chǎn)品研制任務(wù)，合同要求三個月內(nèi)交出一件合格的樣品，否則將索賠2000元。根據(jù)有經(jīng)驗的技術(shù)人員估計，試制品合格的概率為0.4，每次試制一批的裝配費為200元，每件產(chǎn)品的制造成本為100元。每次試制的周期為1個月。問該如何安排試制，每次生產(chǎn)多少件，才能使得期望費用最??？

64§4動態(tài)規(guī)劃的應(yīng)用(2)解：把三次試制當作三個階段（k=1,2,3）決策變量xk表示第k次生產(chǎn)的產(chǎn)品的件數(shù)；狀態(tài)變量sk表示第k次試制前是否已經(jīng)生產(chǎn)出合格品，如果有合格品，則sk=0；如果沒有合格品，記sk=1。最優(yōu)函數(shù)fk(sk)表示從狀態(tài)sk、決策xk出發(fā)的第k階段以后的最小期望費用。故有fk(0)＝0。生產(chǎn)出一件合格品的概率為0.4，所以生產(chǎn)xk件產(chǎn)品都不合格的概率為，至少有一件合格品的概率為1-，故有狀態(tài)轉(zhuǎn)移方程為

65§4動態(tài)規(guī)劃的應(yīng)用(2)

用

表示第

階段的費用，第階段的費用包括制造成本和裝配費用，故有根據(jù)狀態(tài)轉(zhuǎn)移方程以及

，可得到

如果3個月后沒有試制出一件合格品，則要承擔2000元的罰金，因此有

。66§4動態(tài)規(guī)劃的應(yīng)用(2)當k=3時，計算如下表：

67x3

s3

C(x3)+20×0.6X3f3(s3)x3*012345600——————001201511.29.328.598.568.938.565§4動態(tài)規(guī)劃的應(yīng)用(2)當k=2時，計算如下表：

68x2

s2

C