運(yùn)籌學(xué)第八章動(dòng)態(tài)規(guī)劃

運(yùn)籌學(xué)第八章動(dòng)態(tài)規(guī)劃2023/6/71第一頁，共九十頁，編輯于2023年，星期二8.1 動(dòng)態(tài)規(guī)劃的研究對(duì)象和特點(diǎn)

動(dòng)態(tài)規(guī)劃(DynamicProgramming)是一項(xiàng)重要的數(shù)量規(guī)劃方法，由美國數(shù)學(xué)家貝爾曼(R..Bellman)和徳賴費(fèi)斯（Dreyfus）等人在二十世紀(jì)中葉提出的。1957年，貝爾曼發(fā)表了動(dòng)態(tài)規(guī)劃方面的第一本著作〈〈DynamicProgramming〉〉,標(biāo)志著運(yùn)籌學(xué)的又一個(gè)分支動(dòng)態(tài)規(guī)劃的建立。動(dòng)態(tài)規(guī)劃被廣泛應(yīng)用于企業(yè)經(jīng)營、工業(yè)工程、資源理論、最佳控制理論和商業(yè)決策理論中，并且取得了一定的經(jīng)濟(jì)效果。2第二頁，共九十頁，編輯于2023年，星期二

一、動(dòng)態(tài)規(guī)劃的研究對(duì)象

動(dòng)態(tài)規(guī)劃最初是根據(jù)多階段決策問題的特點(diǎn)，由貝爾曼等人提出了解決此類問題的“最優(yōu)化原理”，并且進(jìn)一步成功地解決了許多實(shí)際問題，才得到大家的充分重視。

1.多階段決策又稱序貫決策問題，通常它可以按時(shí)間順序分成若干個(gè)相互聯(lián)系的階段，在每一個(gè)階段都需要作出一個(gè)決策，每一個(gè)階段作出的決策又稱為子策略，每個(gè)階段作出的子策略就組成此多階段決策問題的策略集。實(shí)際工作中我們很難遇到不影響未來決策的當(dāng)前決策，決策者經(jīng)常面臨的問題通常是要他們作出一系列決策，而這些決策中的每一個(gè)均依賴于先前決策的結(jié)果，動(dòng)態(tài)規(guī)劃就可被用來解決很多此類問題。

2.動(dòng)態(tài)規(guī)劃也可以應(yīng)用于解決某些與時(shí)間無關(guān)的問題。例如：把固定數(shù)量的幾種資源在若干用途上進(jìn)行配置，這個(gè)問題被劃分成幾個(gè)步驟來求解，用這種方法求最后的決策就好象它和時(shí)間有關(guān)似的，這就進(jìn)一步擴(kuò)大了動(dòng)態(tài)規(guī)劃解決問題的范圍。

3第三頁，共九十頁，編輯于2023年，星期二二、動(dòng)態(tài)規(guī)劃的特點(diǎn)

1.動(dòng)態(tài)規(guī)劃根據(jù)問題的具體情況，把整個(gè)問題劃分成數(shù)個(gè)階段，而變成數(shù)個(gè)部分問題。當(dāng)這些部分問題由階段的順序而貫通，則形成一項(xiàng)多重階段的程序（過程）。2.動(dòng)態(tài)規(guī)劃對(duì)整個(gè)問題的求解，通常是從一個(gè)階段的部分問題開始，逐個(gè)逆序向前推求解。對(duì)某些問題也可以反過來從最前一個(gè)階段順序向后推求解。但逆序求解是動(dòng)態(tài)規(guī)劃的一個(gè)顯著特點(diǎn)。3.動(dòng)態(tài)規(guī)劃在每一個(gè)階段求得自以往各階段至本階段的最佳解，并將此項(xiàng)最佳解帶入次階段。4.動(dòng)態(tài)規(guī)劃的目標(biāo)是全局（系統(tǒng)）的最優(yōu)化，而不僅是局部（本階段）的優(yōu)化。5.動(dòng)態(tài)規(guī)劃與運(yùn)籌學(xué)的其它分支不同，它沒有標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和解題規(guī)則，但卻是更一般性的解題方法。一個(gè)動(dòng)態(tài)規(guī)劃問題公式的格式在性質(zhì)上和復(fù)雜程度上會(huì)與其它動(dòng)態(tài)規(guī)劃問題大不一樣，其差異取決于問題的結(jié)構(gòu)。解題時(shí)要有豐富的想象力和創(chuàng)造性技巧?？傊?，應(yīng)用動(dòng)態(tài)規(guī)劃可把一個(gè)復(fù)雜的難以下手的大問題變成一系列較易于各個(gè)解決的小問題，然后可以一個(gè)一個(gè)求解。所以許多問題用動(dòng)態(tài)規(guī)劃求解，常較運(yùn)籌學(xué)的其它方法更有效果。4第四頁，共九十頁，編輯于2023年，星期二三、動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的類型

動(dòng)態(tài)規(guī)劃分為離散確定性、離散隨機(jī)性，連續(xù)確定性、連續(xù)隨機(jī)性四種決策類型。本章主要研究離散型動(dòng)態(tài)規(guī)劃，這也正是動(dòng)態(tài)規(guī)劃的核心內(nèi)容和特色所在

5第五頁，共九十頁，編輯于2023年，星期二

8.2動(dòng)態(tài)規(guī)劃的基本概念與

最優(yōu)化原理

第六頁，共九十頁，編輯于2023年，星期二一、多階段決策問題（漫游數(shù)學(xué)家問題）

這是一個(gè)典型的多階段決策問題，通過這個(gè)例子，有助于我們更好的理解動(dòng)態(tài)規(guī)劃的基本概念和基本思路。例8—1有一個(gè)智慧比金錢多的應(yīng)用數(shù)學(xué)家渴望進(jìn)行一次旅行。假設(shè)他住在城市1，而渴望到城市10（見圖8-1表示可能的路線和花費(fèi)）。這是一個(gè)長(zhǎng)途的旅行，要求必須進(jìn)行3次中間停留，中間站可以選擇。他希望為這次旅行付出的花費(fèi)最小，那么他將選擇那些城市作為自己的中間站？

7第七頁，共九十頁，編輯于2023年，星期二

0站1站2站3站4站.

圖8-1

6847124415263810974134113695538第八頁，共九十頁，編輯于2023年，星期二分析：他可以采用枚舉法，列出所有18種可能的路線來解決這個(gè)問題。是否有更好的方法？例如：假設(shè)我們?cè)诔鞘?，可通過城市8，也可通過城市9到達(dá)城市10，很明顯我們會(huì)選城市9而不會(huì)選城市8。因?yàn)椋?+3）＜（9+5）,

即（5—9—10）這條路花費(fèi)較少,由于可按三種不同的路線到達(dá)城市5，可以看出枚舉法將做不少不必要的工作。這個(gè)相當(dāng)簡(jiǎn)單的觀察為我們提供了一種解題的思路。若我們處在第3站，可通過城市8或9到達(dá)城市10可用表8—1說明表8—1

第3站城市Min（f）最佳路徑

8

5

8-------10

9

3

9-------109第九頁，共九十頁，編輯于2023年，星期二

現(xiàn)在假定在第2站，并問哪一條路到城市10最近，花費(fèi)最小。若在城市5，最小花費(fèi)是11，即Min{9+5,8+3}=11，將選擇路徑（5—9—10）。同理若在城市6最小花費(fèi)是12，Min{7+5,12+3}=12，將選擇（6—8—10）。城市7最小費(fèi)用8，Min{----,5+3}=8，將選擇路徑為（7—9—10），結(jié)果列于表8—2

表8—2第2站城市Min（f）最佳路徑

5

11

5---9----106

126---8----10

7

87---9----1010第十頁，共九十頁，編輯于2023年，星期二

現(xiàn)在假定在第1站，用類似方法可知：由城市2到城市10的最小費(fèi)用為Min{3+11,---,4+8}=12，路徑為（2—5—9—10）。第一站計(jì)算結(jié)果為表8—3

表8—3

第1站城市Min（f）最佳路徑

2

12

2----7---9----103

143-----7---9----10

4

124----5---9----1011第十一頁，共九十頁，編輯于2023年，星期二最后假定在第0站即城市1也就是起點(diǎn)，那么由城市1到城市10最小花費(fèi)的路線，應(yīng)由城市1到第一站的哪個(gè)城市呢？由Min{4+12,3+14,11+12}=16可知花費(fèi)最小的路線為（1—2—7—9—10），第0站計(jì)算結(jié)果見表8—4表8—4第0站城市Min（f）最佳路徑

1

161—2—7—9—1012第十二頁，共九十頁，編輯于2023年，星期二5263810974134113469712553446181234053111281214121613第十三頁，共九十頁，編輯于2023年，星期二二、動(dòng)態(tài)規(guī)劃的基本概念

階段和階段變量.狀態(tài)和狀態(tài)變量.決策和決策變量.策略和最優(yōu)策略.

指標(biāo)函數(shù).狀態(tài)轉(zhuǎn)移方程.

第十四頁，共九十頁，編輯于2023年，星期二

1.階段（Stage）和階段變量

把所給問題的過程，按照時(shí)間或空間恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系的階段，以便于求解。描述階段的變量稱為階段變量，通常用K表示階段變量。如例8-1可分為4個(gè)階段，當(dāng)K=2時(shí)，表示對(duì)第2階段求解。15第十五頁，共九十頁，編輯于2023年，星期二2.狀態(tài)（State）和狀態(tài)變量

狀態(tài)表示某階段的初始位置，它既是該段某支路的始點(diǎn)，同時(shí)也是前一階段某支路的終點(diǎn)。通常一個(gè)階段，包含若干個(gè)狀態(tài)。描述過程狀態(tài)的變量，稱為狀態(tài)變量，可用一個(gè)數(shù)、一組數(shù)或一個(gè)向量表示。用SK表示，如例8—1中，階段2有三個(gè)狀態(tài)。則狀態(tài)變量S2可取{２，３，４}，S2=3表示第二階段在狀態(tài)3{城市3}處考慮問題．

16第十六頁，共九十頁，編輯于2023年，星期二3.決策{Deciding}和決策變量

決策就是某階段狀態(tài)給定以后，從該狀態(tài)演變到下一階段某狀態(tài)的選擇。描述決策的變量，稱為決策變量（它是改變狀態(tài)變量的機(jī)會(huì)，可能以概率方式出現(xiàn)），常用XK(SK)表示第K階段當(dāng)狀態(tài)為SK時(shí)的決策變量，它是狀態(tài)SK的函數(shù)。在實(shí)際問題中，決策變量的取值往往限制在某一范圍之內(nèi)，此范圍稱為允許決策集合，通常用DK(SK)表示第K階段的關(guān)于SK狀態(tài)的允許決策集合。顯然有XK(SK)∈DK(SK)17第十七頁，共九十頁，編輯于2023年，星期二4．策略（Strategies）和最優(yōu)策略

由過程的第K階段開始到終點(diǎn)為止的過程稱為問題的后部子過程。由后部子過程的每個(gè)階段的決策組成的決策函數(shù)序列{XK(SK)，XK+1(SK+1)―――――Xn(Sn)}就稱為子過程的策略，簡(jiǎn)稱子策略。并記為：PK..n(SK)={XK(SK)，XK+1(SK+1)..

..

..

Xn(Sn)}

當(dāng)K=1時(shí)，則此決策函數(shù)序列就是全過程的一個(gè)策略，簡(jiǎn)稱策略，記為P1..n(S1)?？晒┻x擇的策略范圍，稱為允許策略集合用P表示。使問題達(dá)到最優(yōu)效果的策略，稱為最優(yōu)策略。例8—1中：{X1(1)=2,X2(2)=7,X3(7)=9,X4(9)=10}就是一個(gè)策略，且為最優(yōu)策略。18第十八頁，共九十頁，編輯于2023年，星期二5．指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)值階段指標(biāo)函數(shù)是用來表示某階段給定狀態(tài)和決策取得效應(yīng)的一種數(shù)量指標(biāo)。它是定義在第K階段上的一個(gè)數(shù)量函數(shù)。用vK..N表示：

vK..N=vK..N(SK,XK)

過程指標(biāo)函數(shù)（簡(jiǎn)稱指標(biāo)函數(shù)；又稱目標(biāo)函數(shù)）是用來衡量所考查過程效應(yīng)的一種數(shù)量指標(biāo)。它是定義在從第K階段到終點(diǎn)過程上的一個(gè)數(shù)量函數(shù)。用VK..N表示：

VK..N=VK..N(SK,XK.SK+1,XK+1――――SN+1)

(k=1,2――――N)當(dāng)初始狀態(tài)給定時(shí)過程的策略就確定了，因而指標(biāo)也就確定了，所以指標(biāo)函數(shù)又是初始狀態(tài)和策略的函數(shù)即：

VK..N=VK..N(SK，PK..N(SK))

19第十九頁，共九十頁，編輯于2023年，星期二5．指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)值指標(biāo)函數(shù)VK..N的最優(yōu)值，稱為相應(yīng)的最優(yōu)指標(biāo)函數(shù)值記為：FK(SK)=optVKN(SK，PK..N(SK))式中opt是optimization(最優(yōu)化)的縮寫，根據(jù)問題不同取Max或Min。在不同問題中指標(biāo)的涵義不同，可以是距離、費(fèi)用、收益、產(chǎn)品產(chǎn)量、資源消耗等。從例8—1中：VK..N表示第k階段的點(diǎn)SK到終點(diǎn)城市10的花費(fèi)。FK(SK)=MinVK,N表示SK到城市10的最小花費(fèi)。20第二十頁，共九十頁，編輯于2023年，星期二6.狀態(tài)轉(zhuǎn)移方程

狀態(tài)轉(zhuǎn)移方程表示從階段k到階段k+1的狀態(tài)轉(zhuǎn)移規(guī)律的表達(dá)式。多級(jí)決策過程中，如給定了第K階段的狀態(tài)變量SK和決策變量XK(SK)，則下一階段K+1階段狀態(tài)變量的值也就確定了。即SK+1=TK(SK,XK(SK))上式又稱為狀態(tài)轉(zhuǎn)移函數(shù)。21第二十一頁，共九十頁，編輯于2023年，星期二三、動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的構(gòu)造條件

1.能夠恰當(dāng)?shù)貏澐謫栴}的階段，把問題化為多階段決策過程；2.正確地選擇狀態(tài)變量動(dòng)態(tài)規(guī)劃中的狀態(tài)要能描述受控過程的演變特征：滿足無后效性和可知性。

22第二十二頁，共九十頁，編輯于2023年，星期二

無后效性——如果過程某階段的狀態(tài)給定，則在這個(gè)階段以后過程的發(fā)展不受前面各個(gè)階段的影響，只和當(dāng)前狀態(tài)及今后的決策有關(guān)，過程前面的狀態(tài)和決策只能通過形成的當(dāng)前狀態(tài)去影響過程未來的發(fā)展，即重要的是當(dāng)前的狀態(tài)和今后的決策而于過去的狀態(tài)和決策無關(guān)?？芍浴麟A段狀態(tài)變量的值直接或間接均為已知。23第二十三頁，共九十頁，編輯于2023年，星期二3.能確定決策變量及各階段的允許決策集合；4.能寫出狀態(tài)轉(zhuǎn)移方程；5.根據(jù)實(shí)際問題，列出指標(biāo)函數(shù)VK,N，要滿足遞推關(guān)系。VK,N(SK,XK,SK+1,XK+1,……SN+1)=Ψ[SK,XK,VK+1..N(SK+1,XK+1,……SN+1)]一般是求和或求積的關(guān)系。

24第二十四頁，共九十頁，編輯于2023年，星期二

四、最優(yōu)化原理和基本方程

1.最優(yōu)化原理最優(yōu)策略具有這樣的性質(zhì)：無論過去狀態(tài)和決策如何，對(duì)前面決策所形成的某一狀態(tài)而言，余下的決策序列必須構(gòu)成最優(yōu)策略。25第二十五頁，共九十頁，編輯于2023年，星期二2.動(dòng)態(tài)規(guī)劃的基本方程利用最優(yōu)化原理，把多階段決策問題的求解過程分解為一個(gè)連續(xù)的遞推過程，由后向前逐步推算。求解時(shí)，各階段以前的狀態(tài)和決策，對(duì)后部子過程來說，只充當(dāng)其初始條件，并不影響后面過程的最優(yōu)策略。據(jù)此可得出動(dòng)態(tài)規(guī)劃的遞推關(guān)系：為使關(guān)系式表達(dá)方便,可對(duì)問題增加第N+1階段此時(shí)有：

FN+1(SN+1)=ee為一常數(shù)FN+1(SN+1)=e又稱為動(dòng)態(tài)規(guī)劃的邊界條件。

26第二十六頁，共九十頁，編輯于2023年，星期二2.動(dòng)態(tài)規(guī)劃的基本方程

對(duì)于任何第K階段（1≤K≤N）當(dāng)

VK,N=∑vj(Sj,Xj)時(shí)則有FK(SK)=opt{vK(SK,XK)+Fk+1(SK+1)}

XK(SK)∈DK(SK)sK∈SK

27第二十七頁，共九十頁，編輯于2023年，星期二2.動(dòng)態(tài)規(guī)劃的基本方程又當(dāng)

VK,N=

∏vj(Sj，Xj)時(shí)則有

Fn+1(Sn+1)≠0

Fk

(Sk)=opt{Vk(Sk,Xk)Fk+1(Sk+1)}

Xk

(Sk)∈Dk(Sk)Sk∈Sk再有狀態(tài)轉(zhuǎn)移函數(shù)

Sk+1=Tk

(Sk,Xk(Sk))

問題就可以求解啦

28第二十八頁，共九十頁，編輯于2023年，星期二例8—2：求X1、X2、X3在滿足約束條件：

X1+X2+X3=CXi≧0(i=1,2,3)之下，使函數(shù)F(X1、X2、X3)=X1?X2?X3→MaxK:按變量將問題劃分為3個(gè)階段，每個(gè)階段只決定X1、X2、X3

其中一個(gè)變量的值。SK:表示第K個(gè)階段初尚未分配出的數(shù)值，S1=CXK：表示第K個(gè)階段分配給的數(shù)值,0≤XK≤SK狀態(tài)轉(zhuǎn)移函數(shù)：Sk+1=SK—XK(K=1、2、3)各個(gè)階段效益按乘積組合，所以基本方程為：

FK(SK)=max{XKFk+1(Sk+1)}(K=1,2,3)0≤XK≤SKF4(S4)=129第二十九頁，共九十頁，編輯于2023年，星期二

例8—3某公司有資金1000萬元，擬投資項(xiàng)目有3個(gè)，已知對(duì)第i個(gè)項(xiàng)目投資Xi萬元，凈收益為gi(Xi)，應(yīng)如何分配資金才能使公司總的凈收益最大？

這個(gè)問題與時(shí)間無明顯關(guān)系，我們可按項(xiàng)目將問題分為三個(gè)階段，每個(gè)階段只考慮對(duì)一個(gè)項(xiàng)目的投資額。K=3狀態(tài)變量SK表示第K個(gè)階段初未分配資金額。決策變量XK表示第K個(gè)階段分配給第K個(gè)項(xiàng)目的投資額。狀態(tài)轉(zhuǎn)移函數(shù)為：SK+1=SK-XK

（K=1、2、3）指標(biāo)函數(shù)基本方程為：

FK(SK)=max{gK(XK)+FK+1(SK+1)}(K=1,2,3)0≤XK≤SK

F4(S4)=030第三十頁，共九十頁，編輯于2023年，星期二

8.2動(dòng)態(tài)規(guī)劃的基本概念與最優(yōu)化原理

根據(jù)動(dòng)態(tài)規(guī)劃的基本思路和最優(yōu)化原理，一般列出其基本方程即可對(duì)實(shí)際問題進(jìn)行求解，但有些問題由于結(jié)構(gòu)的不同，其基本方程可能有特殊性，關(guān)鍵是要靈活地創(chuàng)造性地應(yīng)用動(dòng)態(tài)規(guī)劃的最優(yōu)化原理和思想。31第三十一頁，共九十頁，編輯于2023年，星期二8.3動(dòng)態(tài)規(guī)劃的求解與應(yīng)用一、動(dòng)態(tài)規(guī)劃的解法動(dòng)態(tài)規(guī)劃的求解有兩種基本方法：逆序解法（后向動(dòng)態(tài)規(guī)劃）、順序解法（前向動(dòng)態(tài)規(guī)劃）（一）逆序解法逆序解法的尋優(yōu)方向與實(shí)際決策過程的行進(jìn)方向相反，它是從最后一個(gè)階段開始逐段向前推進(jìn)，從而求得全過程的最優(yōu)策略，這種方法更體現(xiàn)動(dòng)態(tài)規(guī)劃的本質(zhì)和最優(yōu)化原理：不管過去如何，只求未來更優(yōu)。前面我們建立的動(dòng)態(tài)規(guī)劃模型均是按逆序方法建立的，它也是求解動(dòng)態(tài)規(guī)劃問題的主要方法。例8—4用動(dòng)態(tài)規(guī)劃逆序法求解例例8—2解：基本方程為：

FK(SK)=Max{XKFk+1(Sk+1)}(K=1,2,3)0≤XK≤SKF4(S4)=1狀態(tài)轉(zhuǎn)移函數(shù)為：Sk+1=SK—XK(K=1、2、3)32第三十二頁，共九十頁，編輯于2023年，星期二8.3動(dòng)態(tài)規(guī)劃的求解與應(yīng)用第Ⅲ階段，K=3F3(S3)=Max{X3·F4(S4)}0≤X3≤S3

=Max{X3?1}0≤X3≤S3

=S3

X3=S3

第Ⅱ階段，K=2F2(S2)=Max{X2?F3(S3)}0≤X2≤S2=Max{X2?S3}0≤X2≤S2=Max{X2?(X2-S2)}=Max{(S2/2)2-(X2-S2/2)2}=(S2/2)2X2=S2/233第三十三頁，共九十頁，編輯于2023年，星期二8.3動(dòng)態(tài)規(guī)劃的求解與應(yīng)用第Ⅰ階段，K=1F1(S1)=Max{X1?F2(S2)}0≤X1≤S1

=Max{X1?(S2/2)2}=Max{X1?(S1-X1/2)2}=(S1/3)3X1=S1/3由于初始狀態(tài)S1=C所以：

S1=CX1*=C/3F1(C)=(C/3)3S2=C-X1*=2C/3X2*=C/3F2(S2)=(C/3)2S3=S2-X2*=C/3X3*=S3=C/3F3(S3)=(C/3)所以最優(yōu)策略為：X1*=X2*=X3*=C/3最優(yōu)指標(biāo)函數(shù)的值為：F1(S1)=F1(C)=(C/3)334第三十四頁，共九十頁，編輯于2023年，星期二8.3動(dòng)態(tài)規(guī)劃的求解與應(yīng)用（二）順序解法順序解法的尋優(yōu)方向與實(shí)際決策過程的行進(jìn)方向相同，它是從第一個(gè)階段（始點(diǎn)）開始，逐段向后推進(jìn)，從而求得全過程的最優(yōu)策略。順序解法的階段變量、狀態(tài)變量設(shè)置同逆序解法相同，而最優(yōu)指標(biāo)函數(shù)FK(SK+1)表示第K階段末的結(jié)束狀態(tài)為SK+1時(shí)，從第一階段到第K階段所得到的最大收益。一般選擇第K階段末（即第K+1階段）的狀態(tài)作為第K階段的狀態(tài)變量狀態(tài)轉(zhuǎn)移方程為：

SK=TK(SK+1,XK)

基本方程為：

FK(SK+1)=opt{VK(SK+1,XK)+FK--1(SK)}

XK(SK+1)∈DK(SK+1)

F0(S1)=0式中FK(SK+1)指第K階段狀態(tài)為SK+1時(shí)從始點(diǎn)到第K階段的最優(yōu)指標(biāo)函數(shù)值；VK(SK+1,XK)表示第Ｋ階段末狀態(tài)為SK+1時(shí)，決策變量為XK時(shí)本階段的效益值．35第三十五頁，共九十頁，編輯于2023年，星期二8.3動(dòng)態(tài)規(guī)劃的求解與應(yīng)用

逆序解法和順序解法兩者的解題方向不同，但結(jié)果是一致的。在解動(dòng)態(tài)規(guī)劃問題時(shí)，順序解法有時(shí)比較困難，甚至有些問題根本無法采用順序解法，而逆序解法在大多數(shù)情況下都比較方便。一般來講，當(dāng)過程的終點(diǎn)狀態(tài)給定時(shí)，可采用順序解法，當(dāng)過程的起點(diǎn)狀態(tài)和終點(diǎn)狀態(tài)都給定時(shí)，則逆序解法和順序解法都會(huì)得到最優(yōu)結(jié)果，只給定初始狀態(tài)時(shí)則無法采用順序解法，因大多數(shù)問題均只有初始狀態(tài)，所以常用逆序解法。求解動(dòng)態(tài)規(guī)劃問題時(shí)，除了我們介紹的數(shù)學(xué)解析方法，對(duì)離散型問題可能用表格法更合適，下面我們將結(jié)合具體應(yīng)用問題進(jìn)行介紹。36第三十六頁，共九十頁，編輯于2023年，星期二二、動(dòng)態(tài)規(guī)劃的應(yīng)用

動(dòng)態(tài)規(guī)劃的應(yīng)用范圍很廣，解題的方法也各有不同。下面我們將介紹一些典型應(yīng)用問題，進(jìn)一步加深對(duì)動(dòng)態(tài)規(guī)劃的理解和解題技巧的掌握。

（一）資源分配問題（一維資源分配問題）資源分配問題，是指將供應(yīng)量有限的一種或若干種資源（如原材料、資金、機(jī)器、勞力、食品等）分配給若干用戶，而使目標(biāo)函數(shù)最優(yōu)。設(shè)有某種原料總量為M，擬用來進(jìn)行N種生產(chǎn)活動(dòng)。若分配數(shù)量為Xi的原料用于第i種生產(chǎn)活動(dòng)，其收益為gi(Xi)，問應(yīng)如何分配才能使N種生產(chǎn)活動(dòng)的總收益最大？這類問題可寫成靜態(tài)規(guī)劃問題：

Max[g1(X1)+g2(X2)+…+gn(Xn)]X1+X2+…+Xn=MXi≧0i=1,2,3,…n37第三十七頁，共九十頁，編輯于2023年，星期二（一）資源分配問題（一維資源分配問題）

在用動(dòng)態(tài)規(guī)劃方法求解此類問題時(shí)，一般地將N種活動(dòng)作為一個(gè)互相銜接的整體，由于要確定分給每種活動(dòng)的資源數(shù)，所以通常把資源分配給一個(gè)或幾個(gè)使用者的過程劃分為若干個(gè)階段，每個(gè)階段都要確定分配給某一種活動(dòng)的資源量，并且首先要對(duì)N種活動(dòng)指定分配的階段序號(hào)。由于將階段聯(lián)系在一起的是所有生產(chǎn)活動(dòng)都在爭(zhēng)取的資源，因此狀態(tài)變量就要按照資源分配來確定。把第K個(gè)階段的狀態(tài)變量SK定義為第K階段初所擁有的資源量，即將要在第K種活動(dòng)到第N種活動(dòng)之間分配的資源量。這樣我們?cè)诖_定第K個(gè)階段的資源分配時(shí)就不需要考慮第K個(gè)階段以前的資源分配情況。決策變量XK定義為第K個(gè)階段對(duì)資源的分配量，即對(duì)第K種活動(dòng)的資源分配量。

38第三十八頁，共九十頁，編輯于2023年，星期二（一）資源分配問題（一維資源分配問題）狀態(tài)變量的約束條件是：0≤SK≤M

決策變量的約束條件是：0≤XK≤SK

此時(shí)狀態(tài)轉(zhuǎn)移函數(shù)是：SK+1=SK-XK即第K+1階段初的資源擁有量等于第K階段初的資源擁有量與分配量之差。顯然，它滿足無后效性。階段指標(biāo)函數(shù)為對(duì)第K個(gè)階段分配資源XK時(shí)的收益：

VK(SK,XK)=gK(XK)

目標(biāo)函數(shù)FK(SK)為從第K個(gè)階段到第N個(gè)階段按最優(yōu)分配方案分配資源后的最大總收益，則動(dòng)態(tài)規(guī)劃的基本方程為

FK(SK)=Max{gK(SK)(XK)+FK+1(SK+1)}(K=1,2,3,---,n)0≤XK≤SKFn+1(Sn+1)=039第三十九頁，共九十頁，編輯于2023年，星期二（一）資源分配問題（一維資源分配問題）例8-6某機(jī)械公司購置五臺(tái)先進(jìn)設(shè)備，需分給所屬的甲，乙，丙三個(gè)工廠。各工廠獲得這些設(shè)備后，每年為公司提供的盈利（萬元）見表8—5：表8—5單位：萬元

設(shè)備數(shù)工廠

012345甲

03791213乙

0510111111丙04611121240第四十頁，共九十頁，編輯于2023年，星期二（一）資源分配問題（一維資源分配問題）問如何分配這些設(shè)備才能使公司得到的盈利額最大。此問題當(dāng)設(shè)Xi(i=1,2,3)為分配給第i個(gè)工廠的設(shè)備數(shù)時(shí)，gi(Xi)為第i個(gè)工廠的盈利時(shí)，可以寫成靜態(tài)規(guī)劃問題:

Max[g1(X1)+g2(X2)+g3(X3)]X1+X2+X3=5Xi≧0i=1,2,3

無法用單純形方法求解，枚舉法比較麻煩。故采用動(dòng)態(tài)規(guī)劃的方法，特別當(dāng)工廠和設(shè)備數(shù)量增大時(shí)，采用動(dòng)態(tài)規(guī)劃的方法更方便一些。41第四十一頁，共九十頁，編輯于2023年，星期二（一）資源分配問題（一維資源分配問題）解：將問題按工廠劃分為三個(gè)階段，三個(gè)工廠的編號(hào)分別記為1，2，3。SK表示分配給第K個(gè)工廠到第3個(gè)工廠的設(shè)備臺(tái)數(shù)，XK表示分配給第K個(gè)工廠的設(shè)備臺(tái)數(shù)：

S1=5SK+1=SK-XK

VK(XK)表示XK臺(tái)設(shè)備分配到第K個(gè)工廠得到的盈利值。

FK(SK)表示SK臺(tái)設(shè)備分配到第K個(gè)工廠至第三個(gè)工廠所得的最大盈利。因此有遞推關(guān)系：

FK(SK)=Max{VK(XK)+FK+1(SK-XK)}(K=1,2,3)0≤XK≤SK(K=1,2,3)F4(S4)=042第四十二頁，共九十頁，編輯于2023年，星期二（一）資源分配問題（一維資源分配問題）現(xiàn)從最后一個(gè)階段向前遞推求解：階段ⅢK=3

設(shè)把S3臺(tái)設(shè)備（S3=0，1，2，3，4，5）全部分配給工廠3時(shí)，則最大盈利值為：F3(S3)=Max[V3(X3)]X3=0,1,2,3,4,5因?yàn)橹挥幸粋€(gè)工廠，給不同臺(tái)數(shù)的盈利就是每種情況下的最大盈利。因此最優(yōu)方案是把全部設(shè)備放到工廠3去。數(shù)值計(jì)算及決策見表8—6

x3s3

V3(x3)+F4(S4)F3(s3)x3*01234500

00104

4120466230461111340461112124504611121212543第四十三頁，共九十頁，編輯于2023年，星期二（一）資源分配問題（一維資源分配問題）

階段Ⅱ

K=2

設(shè)把S2臺(tái)（S2=0，1，2，3，4，5）設(shè)備全部分給工廠3、工廠2時(shí)，則最大盈利值為：F2(S2)=Max[V2(X2)+F3(S2-X2)]X2=0,1,2,3,4,5

選擇X2數(shù)值使F2(S2)最大決策及計(jì)算結(jié)果如表6—7：

x2s2

V2(X2)+F3(S2-X2)F2(s2)X2*01234500

0010+45+0

5120+65+410+010230+115+610+411+014240+125+1110+611+411+0161&250+125+1210+1111+611+411+021244第四十四頁，共九十頁，編輯于2023年，星期二（一）資源分配問題（一維資源分配問題）

階段ⅠK=1

設(shè)把S1臺(tái)設(shè)備（S1=5）分配給1，2，3三個(gè)工廠，則最大盈利值為：

F1(S1)=Max{V1(X1)+F2(S1-X1)}X1=0,1,2,3,4,5現(xiàn)選取X1的值，使F1(S1)最大，數(shù)值計(jì)算見表6—8由表中可知：最優(yōu)方案有二個(gè)：

(1)X1=0X2=2X3=3F1(S1)=21(2)X1=2X2=2X3=1F1(S1)=21如資源是連續(xù)的，則解題時(shí)首先必須將問題進(jìn)行離散化處理，如本問題不是5臺(tái)設(shè)備而是50萬元人民幣，那么我們可以每10萬元為單位進(jìn)行分割，當(dāng)然也可以1萬元為單位分割，但計(jì)算工作量會(huì)大幅度提高，因此分割單位的選擇十分重要

x1s1V1(X1)+F2(S1-X1)F1(s1)X1*01234550+213+167+149+1012+513+0210&245第四十五頁，共九十頁，編輯于2023年，星期二(二)資源分配問題（考慮資源回收的問題）例8-7．某個(gè)公司新購某種機(jī)床125臺(tái)。這種設(shè)備5年后將被其它新設(shè)備代替，此機(jī)床如在高負(fù)荷狀態(tài)下工作年損壞率為1/2，每臺(tái)年收益為10萬元；如在低負(fù)荷下工作年損壞率為1/5，每臺(tái)年收益為6萬元。問應(yīng)如何安排這些機(jī)床的生產(chǎn)負(fù)荷，才能使5年內(nèi)所獲收益最大？46第四十六頁，共九十頁，編輯于2023年，星期二(二)資源分配問題（考慮資源回收的問題）

解：按年度劃分為5個(gè)階段，用K表示階段序號(hào)。狀態(tài)變量SK

為第K年擁有完好設(shè)備的數(shù)量，決策變量XK

為第K年中處于高負(fù)荷工作的設(shè)備數(shù)量，決策變量(SK—XK)為第K年中處于低負(fù)荷工作的設(shè)備數(shù)量狀態(tài)轉(zhuǎn)移函數(shù)即第K+1年年初完好的設(shè)備臺(tái)數(shù):SK+1=SK—1/2XK—1/5(SK—XK)=4/5SK—3/10XK第K階段允許決策集合為

DK(SK)={XK/0≤XK≤SK}VK(SK,XK)為第K年度的收益則VK=VK(SK,XK)=10XK+6(SK—XK)=6SK+4XK47第四十七頁，共九十頁，編輯于2023年，星期二(二)資源分配問題（考慮資源回收的問題）因此基本方程為:FK(SK)=Max{6SK+4XK+FK+1(SK+1)}0≤XK≤SKK=1,2,3,4,5F6(S6)=0下面求解問題：階段ⅤK=5F6(S6)=0有：F5(S5)=Max{4X5+6S5}0≤X5≤S5

因?yàn)?X5+6S5隨X5單調(diào)遞增，所以取X5=S5

此時(shí)：

X5=S5

F5(S5)=10S5

48第四十八頁，共九十頁，編輯于2023年，星期二(二)資源分配問題（考慮資源回收的問題）階段ⅣK=4F4(S4)=Max{4X4+6S4+F5(S5)}0≤X4≤S4=Max{4X4+6S4+10S5}=Max{4X4+6S4+8S4-3X4}=Max{X4+14S4}0≤X4≤S4因?yàn)閄4+14S4單凋遞增。所以取X4=S4此時(shí)

X4=S4

F4(S4)=15S449第四十九頁，共九十頁，編輯于2023年，星期二(二)資源分配問題（考慮資源回收的問題）階段ⅢK=3F3(S3)=Max{4X3+6S3+F4(S4)}=Max{4X3+6S3+15S4}=Max{4X3+6S3+15(0.8S3-0.3X3}=Max{18S3–(1/2)X3}0≤X3≤S3

由于18S3–(1/2)X3隨X3單調(diào)遞減所以取X3=0此時(shí)：

X3=0F3(S3)=18S3

50第五十頁，共九十頁，編輯于2023年，星期二(二)資源分配問題（考慮資源回收的問題）階段ⅡK=2F2(S2)=Max{4X2+6S2+F3(S3)}=Max{4X2+6S2+18S3}=Max{4X2+6S2+18(0.8S2-0.3X2)}=Max{20.4S2-1.4X2}0≤X2≤S2同理取X2=0此時(shí)

X2=0F2(S2)=20.4S251第五十一頁，共九十頁，編輯于2023年，星期二(二)資源分配問題（考慮資源回收的問題）階段ⅠK=1F1(S1)=Max{4X1+6S1+F2(S2)}=Max{4X1+6S1+20.4S2}=Max{4X1+6S1+20.4(0.8S1-0.3X1)}=Max{22.32S1-2.12X1}0≤X1≤S1同理取X1=0此時(shí)

X1=0F1(S1)=22.32S152第五十二頁，共九十頁，編輯于2023年，星期二(二)資源分配問題（考慮資源回收的問題）將S1=125代入得:F1(S1)=F1(125)=22.32X125=2790(萬元)

即公司五年內(nèi)可獲得最大收益值為2790萬元，最優(yōu)生產(chǎn)計(jì)劃方案為表6—9所示表6—9而且5年結(jié)束后，尚有32-(1/2)x32=16臺(tái)設(shè)備處于完好狀態(tài)。如初始狀態(tài)S1=125加以改變，我們也不需要重新開始計(jì)算，借助狀態(tài)轉(zhuǎn)移函數(shù)，我們可以很快得到最佳策略，這也是動(dòng)態(tài)規(guī)劃問題的一個(gè)顯著特點(diǎn)。年份項(xiàng)目12345狀態(tài)S125100806432高負(fù)荷X1=0X2=0X3=0X4=64X5=32低負(fù)荷125100800053第五十三頁，共九十頁，編輯于2023年，星期二（三）生產(chǎn)與存貯問題例8-8某造船股份有限責(zé)任公司根據(jù)合同，從現(xiàn)在起連續(xù)4年每年年未要向客戶提供型號(hào)相同的大型遠(yuǎn)洋客船，每年的交貨數(shù)及生產(chǎn)每條船的生產(chǎn)費(fèi)用見表8—10所示。該公司的生產(chǎn)能力設(shè)計(jì)為每年6條船。每個(gè)計(jì)劃年度造船公司固定費(fèi)用為60萬元。若造出的船當(dāng)年不交貨，則每條船積壓一年的損失為40萬元。假定開始時(shí)及第四年年未交貨后均無積壓船只，問公司應(yīng)如何安排四年的生產(chǎn)計(jì)劃，使所支付總費(fèi)用最經(jīng)濟(jì)？年度項(xiàng)目一二三四生產(chǎn)費(fèi)用（CK)百萬元/條

6.0

6.06.36.5需交付船（dK）條/年度

1

3

2

254第五十四頁，共九十頁，編輯于2023年，星期二（三）生產(chǎn)與存貯問題解：按年度劃分階段，四年分為4個(gè)階段，k=1，2，3，4。狀態(tài)變量SK為第K階段初存儲(chǔ)的船只數(shù)量。狀態(tài)變量SK需要滿足以下條件：⑴不能超過本年和以后各年交船數(shù)的總和

0≤SK≤Σdi⑵為保證按時(shí)交船，每年年初的存船數(shù)加上本年度的最大可能生產(chǎn)量不得小于本年度的交船數(shù)SK+6≥dK⑶此外，還有S1=S5=0

決策變量XK為第K階段生產(chǎn)的船只數(shù),且XK必須滿足以下條件：⑴某年末所擁有的存船數(shù)，不應(yīng)超過本年度及以后各年交船數(shù)的總和：

XK+SK≤Σdi⑵某年初所擁有的存船數(shù)加上當(dāng)年生產(chǎn)船只數(shù)量，不應(yīng)少于本年度的交船數(shù)

XK+SK≥dK55第五十五頁，共九十頁，編輯于2023年，星期二（三）生產(chǎn)與存貯問題

狀態(tài)轉(zhuǎn)移函數(shù)

SK=SK+XK–dK=1,2,3,4即第K年初的存船數(shù)加上第K年船只的生產(chǎn)數(shù)，再減去第K年交付的船數(shù)，就等于第K+1年初的存船數(shù)。第K階段的指標(biāo)函數(shù)VK就是第K年度生產(chǎn)費(fèi)用與存貯費(fèi)用兩部分之和。

0.6+CKXK+0.4SK

當(dāng)XK>0VK(SK,XK)K=1,2,3,40.4SK

當(dāng)XK=0動(dòng)態(tài)規(guī)劃的基本方程為：

FK(SK)=Min{VK(SK,XK)+Fk+1(Sk+1)}(K=1,2,3,4)0≤XK≤6F5(S5)=056第五十六頁，共九十頁，編輯于2023年，星期二（三）生產(chǎn)與存貯問題階段Ⅳ，K=4，d4=2S4∈{0,1,2}X4∈{2,1,0}0.6+6.5X4+0.4S4

當(dāng)X4>0V4=0.4S4

當(dāng)X4=0計(jì)算結(jié)果見表6—11所示表6—11階段Ⅳ決策表

階段k

期初存船（S4）可能的生產(chǎn)量（X4）本期費(fèi)用（V4）期末存船（S5

）以后各期費(fèi)用F5(S5)

總費(fèi)用V4+F5

最佳生產(chǎn)量（X4）40213.60013.62117.5007.51200.8000.8057第五十七頁，共九十頁，編輯于2023年，星期二（三）生產(chǎn)與存貯問題階段Ⅲ，K=3，D3=2，故:S3∈{0,1,2,3,4}0.6+6.3X3+0.4S3

當(dāng)X3>0V3=0.4S3

當(dāng)X3=0計(jì)算結(jié)果如下表6—12

表6—12階段Ⅲ決策表階段k

期初存船（S3）可能的生產(chǎn)量（X3）本期費(fèi)用（V3）期末存船（S4）以后各期費(fèi)用F4(S4)

總費(fèi)用V3+F4最佳生產(chǎn)量（X3）30213.2013.626.84319.517.527425.820.826.61

17.3013.620.9

3

213.617.521.1319.920.8

20.758第五十八頁，共九十頁，編輯于2023年，星期二（三）生產(chǎn)與存貯問題

表6—12(續(xù))階段Ⅲ決策表階段k

期初存船（S3）可能的生產(chǎn)量（X3）本期費(fèi)用（V3）期末存船（S4）以后各期費(fèi)用F4(S4)

總費(fèi)用V3+F4最佳生產(chǎn)量（X3）3200.8013.6

14.4017.717.515.221420.8

14.8301.217.58.7018.120.88.9401.620.8

2.4059第五十九頁，共九十頁，編輯于2023年，星期二（三）生產(chǎn)與存貯問題階段Ⅱ，K=2，D2=3，故S2∈{0,1,2,3,4,5}

0.6+6.5X2+0.4S2

當(dāng)X2>0V2=0.4S2

當(dāng)X2=0計(jì)算結(jié)果見表6—13所示表6—13階段Ⅱ決策表

階段k

期初存船（S2）可能的生產(chǎn)量（X2）本期費(fèi)用（V2）期末存船（S3

）以后各期費(fèi)用F3(S3)

總費(fèi)用V2+F3最佳生產(chǎn)量（X2）20

318.6026.645.25424.6120.745.3530.6214.445.0636.638.745.360第六十頁，共九十頁，編輯于2023年，星期二（三）生產(chǎn)與存貯問題

表6—13(續(xù)1)階段Ⅱ決策表

階段k

期初存船（S2）可能的生產(chǎn)量（X2）本期費(fèi)用（V2）期末存船（S3

）以后各期費(fèi)用F3(S3)

總費(fèi)用V2+F3最佳生產(chǎn)量（X2）21213026.639.64or6

319120.739.7425214.439.453138.739.763742.439.42

17.4026.6343or5

213.4120.734.1319.4214.433.8425.438.734.1531.442.433.861第六十一頁，共九十頁，編輯于2023年，星期二

階段k

期初存船（S2）可能的生產(chǎn)量（X2）本期費(fèi)用（V2）期末存船（S3

）以后各期費(fèi)用F3(S3)

總費(fèi)用V2+F3最佳生產(chǎn)量（X2）2301.2026.627.8017.8120.728.5213.8214.428.2319.838.728.5425.842.428.2401.6120.722.3018.2214.422.6214.238.722.9320.242.422.65

02.0214.416.4018.638.717.3214.642.417.0表6—13(續(xù)2)階段Ⅱ決策62第六十二頁，共九十頁，編輯于2023年，星期二（三）生產(chǎn)與存貯問題階段Ⅰ，K=1，D1=1，故S1=0,X1∈{1,2,3,4,5,6}V1=0.6+6.0X1計(jì)算結(jié)果見表6—14

表6—14階段Ⅰ決策表階段k

期初存船（S1）可能的生產(chǎn)量（X1）本期費(fèi)用（V1）期末存船（S2）以后各期費(fèi)用F2(S2)

總費(fèi)用V1+F2最佳生產(chǎn)量（X1）10

16.60

45.0

51.61212.6139.452.0318.6233.852.4424.6327.852.4530.6422.352.9636.6516.453.063第六十三頁，共九十頁，編輯于2023年，星期二（三）生產(chǎn)與存貯問題

由表6-14知，第1年應(yīng)該生產(chǎn)1艘船，整個(gè)過程的最小費(fèi)用為F1（0）=51.6百萬元。由遞推關(guān)系可得問題的最佳策略，詳見表5—15

公司最佳生產(chǎn)方案

即第1年船廠應(yīng)該安排生產(chǎn)1艘船，第2年安排生產(chǎn)5艘船，第3年不安排生產(chǎn)，第4年安排生產(chǎn)2艘船，船廠按此策略安排生產(chǎn)計(jì)劃才能既滿足客戶要求又能使支出總費(fèi)用最小，總費(fèi)用為5160萬元

年度期初存船(Sk）最佳生產(chǎn)量（Xk）期末存船（Sk+1）本期費(fèi)用VK(SK)

最小總費(fèi)用min(VK+Fk+1)10106.651.6205230.645.032000.814.4402013.613.664第六十四頁，共九十頁，編輯于2023年，星期二（四）背包問題背包問題又稱裝載問題，如汽車，火車，輪船，飛機(jī)，宇宙飛船等工具的裝載問題，還可用于機(jī)械加工中零部件的最優(yōu)加工，下料等問題，具有廣泛的實(shí)用價(jià)值。典型的背包問題是講有一位登山運(yùn)動(dòng)員，它的背包的載重量不能超過a千克，現(xiàn)有n種物品可供選擇裝入背包，第i種物品的單位重量是ai千克，第i種物品的價(jià)值是攜帶數(shù)量Xi的函數(shù)Ci(Xi)(i=1,2,---,n)，那么運(yùn)動(dòng)員應(yīng)如何選擇各種物品的數(shù)量，而使總價(jià)值最大？

65第六十五頁，共九十頁，編輯于2023年，星期二（四）背包問題例8-9，某公司有三種貨物需要裝飛機(jī)運(yùn)輸，各種貨物的重量和可能獲得的收益見表8—16。飛機(jī)允許裝載能力為6噸，問應(yīng)如何裝載才能使公司獲得最大收益？表8—16解：按貨物種類劃分階段：K=1表示裝載第1種貨物；K=2表示裝載第2種貨物；K=3表示裝載第3種貨物。狀態(tài)變量SK表示第K階段可以利用的裝載能力。

S1=6SK={0，1，2，3，4，5，6}K=2，3貨物種類（i）貨物重量（Wi）噸收益（Vi）(千克)1280231303418066第六十六頁，共九十頁，編輯于2023年，星期二（四）背包問題決策變量XK為第K種貨物的裝載數(shù)量。允許決策集合：XK∈DK(SK)={0,1,2,---,[SK/aK]}K=1,2,3

狀態(tài)轉(zhuǎn)移函數(shù)：SK+1=SK—WKXK階段指標(biāo)函數(shù)為：VKXK動(dòng)態(tài)規(guī)劃基本方程：

FK(SK)=Max{VKXK+FK+1(SK+1)}(K=3,2,1)XK∈DK(SK)F4(S4)=067第六十七頁，共九十頁，編輯于2023年，星期二（四）背包問題階段ⅢK=3W3=4,V3=180,S3∈{0,1,2….,6}因?yàn)閄3∈{0,1,…,[S3/4]}={0,1}所以：F3(S3)=Max{180X3+0}X3∈(0,1)S3∈{0,1,2,…,6}計(jì)算結(jié)果如下表8—17階段

X3S3180X3F3(S3)

X3*S401300

00010

00120

00230

00340180+01801050180+01801160180+01801268第六十八頁，共九十頁，編輯于2023年，星期二（四）背包問題

階段Ⅱ

K=2W2=3,V2=130,S2∈{0,1,2,3,4,5,6}

因?yàn)?X2∈{0,1,…,[S2/3]}={0,1,2}S3=S2—3X2

所以:F2(S2)=Max{130X2+F3(S3)}=Max{130X2+F3(S2-3X2)}計(jì)算結(jié)果如下表8—18

階段

X2S2130X2+F3(S3)F2(S2)

X2*S3012200

00010

00120

00230130+01301040+180130+01800450+180130+01800560+180130+0260+02602069第六十九頁，共九十頁，編輯于2023年，星期二（四）背包問題階段Ⅰ

K=1W1=2,V1=80,S1=6因?yàn)?X1∈{0,1,…,[6/2]}={0,1,2,3}S2=S1-2X1所以:F1(S1)=Max{80X1+F2(S2)}=Max{80X1+F2(S1-2X1)}X1∈{0,1,2,3}S1=6計(jì)算結(jié)