動態(tài)規(guī)劃的基本方法

動態(tài)規(guī)劃的基本思想及應(yīng)用

(Dynamicprogramming)5.1動態(tài)規(guī)劃的實(shí)例5.2動態(tài)規(guī)劃的基本概念5.4資源分配問題5.5背包問題5.3動態(tài)規(guī)劃方法的基本思想*5.6排序問題動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點(diǎn)在于，它可以把一個(gè)n維決策問題變換為幾個(gè)一維最優(yōu)化問題，從而一個(gè)一個(gè)地去解決。需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。必須對具體問題進(jìn)行具體分析，運(yùn)用動態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動態(tài)規(guī)劃方法去求解。5.1動態(tài)規(guī)劃的實(shí)例即在系統(tǒng)發(fā)展的不同時(shí)刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，不斷地做出決策；每個(gè)階段都要進(jìn)行決策,目的是使整個(gè)過程的決策達(dá)到最優(yōu)效果。動態(tài)決策問題的特點(diǎn)：系統(tǒng)所處的狀態(tài)和時(shí)刻是進(jìn)行決策的重要因素；找到不同時(shí)刻的最優(yōu)決策以及整個(gè)過程的最優(yōu)策略。多階段決策問題：是動態(tài)決策問題的一種特殊形式；在多階段決策過程中,系統(tǒng)的動態(tài)過程可以按照時(shí)間進(jìn)程分為狀態(tài)相互聯(lián)系而又相互區(qū)別的各個(gè)階段；多階段決策問題的典型例子：1.生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時(shí)間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個(gè)生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計(jì)劃。2.機(jī)器負(fù)荷分配問題：某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量

g和投入生產(chǎn)的機(jī)器數(shù)量u1的關(guān)系為g=g(u1)12n狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策這時(shí)，機(jī)器的年完好率為a,0<a<1

，即如果年初完好機(jī)器的數(shù)量為u1，到年終完好的機(jī)器就為au1,0<a<1。在低負(fù)荷下生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量h

和投入生產(chǎn)的機(jī)器數(shù)量u2的關(guān)系為h=h(u2)假定開始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為s1。要求制定一個(gè)五年計(jì)劃，在每年開始時(shí)，決定如何重新分配完好的機(jī)器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。

相應(yīng)的機(jī)器年完好率b,0<b<1。

3.航天飛機(jī)飛行控制問題：由于航天飛機(jī)的運(yùn)動的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機(jī)飛行在不同環(huán)境中的情況，不斷地決定航天飛機(jī)的飛行方向和速度（狀態(tài)），使之能最省燃料和實(shí)現(xiàn)目的（如軟著落問題）。不包含時(shí)間因素的靜態(tài)決策問題（本質(zhì)上是一次決策問題）也可以適當(dāng)?shù)匾腚A段的概念，作為多階段的決策問題用動態(tài)規(guī)劃方法來解決。4.線性規(guī)劃、非線性規(guī)劃等靜態(tài)的規(guī)劃問題也可以通過適當(dāng)?shù)匾腚A段的概念，應(yīng)用動態(tài)規(guī)劃方法加以解決。5.最短路問題：給定一個(gè)交通網(wǎng)絡(luò)圖如下，其中兩點(diǎn)之間的數(shù)字表示距離（或花費(fèi)），試求從A點(diǎn)到G點(diǎn)的最短距離（總費(fèi)用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687636853384222133352566431、階段：把一個(gè)問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段，以便于按一定的次序去求解。描述階段的變量稱為階段變量。階段的劃分，一般是根據(jù)時(shí)間和空間的自然特征來進(jìn)行的，但要便于問題轉(zhuǎn)化為多階段決策。2、狀態(tài)：表示每個(gè)階段開始所處的自然狀況或客觀條件。通常一個(gè)階段有若干個(gè)狀態(tài)，描述過程狀態(tài)的變量稱為狀態(tài)變量。年、月、路段一個(gè)數(shù)、一組數(shù)、一個(gè)向量狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)允許集合。5.2動態(tài)規(guī)劃的基本概念3、決策：表示當(dāng)過程處于某一階段的某個(gè)狀態(tài)時(shí)，可以作出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。描述決策的變量，稱為決策變量。決策變量是狀態(tài)變量的函數(shù)?？捎靡粋€(gè)數(shù)、一組數(shù)或一向量（多維情形）來描述。在實(shí)際問題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合。系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)的當(dāng)前的狀態(tài)和決策有關(guān)，而且還與系統(tǒng)過去的歷史狀態(tài)和決策有關(guān)。4、多階段決策過程可以在各個(gè)階段進(jìn)行決策，去控制過程發(fā)展的多段過程；其發(fā)展是通過一系列的狀態(tài)轉(zhuǎn)移來實(shí)現(xiàn)的；圖示如下：狀態(tài)轉(zhuǎn)移方程是確定過程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過程。如果第k階段狀態(tài)變量sk的值、該階段的決策變量一經(jīng)確定，第k+1階段狀態(tài)變量sk+1的值也就確定。其狀態(tài)轉(zhuǎn)移方程如下（一般形式）12ks1u1s2u2s3skuksk+1能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段決策過程。動態(tài)規(guī)劃中能處理的狀態(tài)轉(zhuǎn)移方程的形式。狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下無后效性(馬爾可夫性)如果某階段狀態(tài)給定后，則在這個(gè)階段以后過程的發(fā)展不受這個(gè)階段以前各段狀態(tài)的影響；過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展；構(gòu)造動態(tài)規(guī)劃模型時(shí)，要充分注意是否滿足無后效性的要求；狀態(tài)變量要滿足無后效性的要求；如果狀態(tài)變量不能滿足無后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。

5、策略：是一個(gè)按順序排列的決策組成的集合。在實(shí)際問題中，可供選擇的策略有一定的范圍，稱為允許策略集合。從允許策略集合中找出達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。

6、狀態(tài)轉(zhuǎn)移方程：是確定過程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過程，描述了狀態(tài)轉(zhuǎn)移規(guī)律。

7、指標(biāo)函數(shù)和最優(yōu)值函數(shù)：用來衡量所實(shí)現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)，為指標(biāo)函數(shù)。指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)。在不同的問題中，指標(biāo)函數(shù)的含義是不同的，它可能是距離、利潤、成本、產(chǎn)量或資源消耗等。動態(tài)規(guī)劃模型的指標(biāo)函數(shù)應(yīng)具有可分離性，并滿足遞推關(guān)系。指標(biāo)函數(shù):

指標(biāo)函數(shù)形式:

和、積可遞推

效益最優(yōu)函數(shù):

解多階段決策過程問題，求出

最優(yōu)策略，即最優(yōu)決策序列f1(s1)

最優(yōu)軌線，即執(zhí)行最優(yōu)策略時(shí)的狀態(tài)序列

最優(yōu)目標(biāo)函數(shù)值從k到終點(diǎn)最優(yōu)策略子策略的最優(yōu)目標(biāo)函數(shù)值1、動態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件（簡稱基本方程）。要做到這一點(diǎn)，就必須將問題的過程分成幾個(gè)相互聯(lián)系的階段，恰當(dāng)?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個(gè)大問題轉(zhuǎn)化成一組同類型的子問題，然后逐個(gè)求解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個(gè)子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個(gè)子問題所得的最優(yōu)解，就是整個(gè)問題的最優(yōu)解。5.3動態(tài)規(guī)劃的基本思想2、在多階段決策過程中，動態(tài)規(guī)劃方法是既把當(dāng)前一段和未來一段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的.

最優(yōu)化原理：作為整個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略?！币簿褪钦f，一個(gè)最優(yōu)策略的子策略也是最優(yōu)的。3、在求整個(gè)問題的最優(yōu)策略時(shí)，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐段變換得到，從而確定了最優(yōu)路線。建立動態(tài)規(guī)劃模型的步驟

1、劃分階段劃分階段是運(yùn)用動態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時(shí)間或空間先后順序，將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)問題要人為地賦予“時(shí)間”概念，以便劃分階段。2、正確選擇狀態(tài)變量選擇變量既要能確切描述過程演變又要滿足無后效性，而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從過程演變的特點(diǎn)中尋找。3、確定決策變量及允許決策集合通常選擇所求解問題的關(guān)鍵變量作為決策變量，同時(shí)要給出決策變量的取值范圍，即確定允許決策集合。4、確定狀態(tài)轉(zhuǎn)移方程根據(jù)k階段狀態(tài)變量和決策變量，寫出k+1階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。5、確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動態(tài)規(guī)劃基本方程階段指標(biāo)函數(shù)是指第k階段的收益，最優(yōu)指標(biāo)函數(shù)是指從第k階段狀態(tài)出發(fā)到第n階段末所獲得收益的最優(yōu)值，最后寫出動態(tài)規(guī)劃基本方程。以上五步是建立動態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。由于動態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動態(tài)規(guī)劃模型沒有統(tǒng)一的模式，建模時(shí)必須根據(jù)具體問題具體分析，只有通過不斷實(shí)踐總結(jié)，才能較好掌握建模方法與技巧。例從A

地到D

地要鋪設(shè)一條煤氣管道,其中需經(jīng)過兩級中間站，兩點(diǎn)之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？AB1B2C1C2C3D24333321114最短路徑問題解：整個(gè)計(jì)算過程分三個(gè)階段，從最后一個(gè)階段開始。第一階段（C→D）：C

有三條路線到終點(diǎn)D

。

AB1B2C1C2C3D24333321114DC1C2C3顯然有f1(C1)

=1；

f1(C2)

=3；

f1(C3)

=4

d(B1,C1)+f1(C1)

3+1f2(B1)=mind(B1,C2

)+f1(C2)

=min3+3

d(B1,C3)+f1(C3)1+44=min6=45第二階段（B→C）：B到C有六條路線。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為B1→C1→D)

d(B2,C1)+f1(C1)

2+1f2(B2)=mind(B2,C2

)+f1(C2)

=min3+3

d(B2,C3)+f1(C3)1+43=min6=35AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為B2→C1→D)第三階段（

A→B

）：A到B有二條路線。

f3(A)1=d(A,B1)＋f2(B1)＝2＋4＝6

f3(A)2=d(A,B2)＋f2(B2)＝4＋3＝7∴f3(A)

=min=min｛6,7｝=6d(A,B1)＋f2(B1)d(A,B2)＋f2(B2)(最短路線為A→B1→C1→D)AB1B2C1C2C3D24333321114DC1C2C3B1B2AAB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路線為A→B1→C1→D

路長為6例5.1AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最優(yōu)路線為：A→B1→C2→D1→E2→F2→G

路長＝18求從A到G的最短路徑3k=5，出發(fā)點(diǎn)E1、E2、E3u5(E1)=F1E1F1GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u5(E2)=F2E2F2Gu5(E3)=F2E3F2Gk=6,F1Gf6(F1)=4F2G

,f6(F2)=3k=4，f4(D1)=7

u4(D1)=E2f4(D2)=6

u4(D2)=E2f4(D3)=8

u4(D3)=E2k=2,f2(B1)=13

u2(B1)=C2f2(B2)=16u2(B2)=C3f3(C1)=13

u3(C1)=D1f3(C2)=10

u3(C2)=D1f3(C3)=9

u3(C3)=D1f3(C4)=12

u3(C4)=D3k=3,=minf1(A)=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)5+133+16=18k=1,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u5(E1)=F1E1F1Gu5(E2)=F2E2F2Gu5(E3)=F2E3F2G759

u5(E2)=F2u6(F2)=G最優(yōu)策略AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643求從A到E的最短路徑路線為A→B2→C1→D1→E

，最短路徑為19AB2B1B3C1C3D1D2EC25214112610104312111396581052課堂練習(xí)1*例5.2

利用動態(tài)規(guī)劃的順推解法求解下列問題。解：按問題中變量的個(gè)數(shù)分為三個(gè)階段。設(shè)狀態(tài)變量為s0,s1,s2,s3，并記s3≤9；取x1,x2,x3為各階段的決策變量；各階段指標(biāo)函數(shù)按加法方式結(jié)合。令最優(yōu)值函數(shù)fk(sk)表示第k

階段的結(jié)束狀態(tài)為sk，從第1階段到第k

階段的最大值。設(shè)3x1=s1,s1+2x2=s2,s2+x3=s3，則有x1=s1/3,0≤x2≤s2/2,0≤x3≤s3用順推法，從前向后依次有，當(dāng)k=1

時(shí)當(dāng)k=2時(shí)，有令，由得由于該點(diǎn)不在允許決策集合內(nèi)，所以最大值點(diǎn)不可能在該點(diǎn)取得，所以無需驗(yàn)證。因此，h2(x2)的最大值必在兩個(gè)端點(diǎn)上選取。計(jì)算得到所以h2(x2)的最大值在x2=0處取得，且有當(dāng)k=3時(shí)，有令，由又，所以x3=2s3/11為極小值點(diǎn)，由此可得，函數(shù)h3(x3)的最大值點(diǎn)必在兩個(gè)端點(diǎn)上選取。計(jì)算兩個(gè)端點(diǎn)的函數(shù)值，有所以h3(x3)的最大值點(diǎn)在x3=s3

處。由此可知由于s3

未知，故須再對s3求一次極值，即顯然，當(dāng)s3=9時(shí)，f3(s3)達(dá)到最大值，即再按計(jì)算的順序反推算，可以求得最優(yōu)解和最優(yōu)值現(xiàn)有數(shù)量為a（萬元）的資金，計(jì)劃分配給n個(gè)工廠,用于擴(kuò)大再生產(chǎn)。假設(shè)：xi為分配給第i個(gè)工廠的資金數(shù)量（萬元）；gi(xi)為第i個(gè)工廠得到資金后提供的利潤值（萬元）。問題是如何確定各工廠的資金數(shù)，使得總的利潤為最大。據(jù)此，有：5.4資源分配問題令：fk(x)=以數(shù)量為x的資金分配給前k個(gè)工廠所得到的最大利潤值。用動態(tài)規(guī)劃求解，就是求fn(a)的問題。當(dāng)k=1時(shí)，f1(x)=g1(x)（因?yàn)橹唤o一個(gè)工廠）當(dāng)1＜k≤n時(shí)，其遞推關(guān)系如下：設(shè)：y為分給第k個(gè)工廠的資金（其中0≤y≤x），此時(shí)還剩x–y(萬元)的資金需要分配給前k-1個(gè)工廠,如果采取最優(yōu)策略，則得到的最大利潤為fk-1(x-y),因此總的利潤為：

gk(y)+fk-1(x-y)如果a

是以萬元為資金分配單位，則式中的y只取非負(fù)整數(shù)0,1,2,…,x。上式可變?yōu)椋核?，根?jù)動態(tài)規(guī)劃的最優(yōu)化原理，有下式：例5.3設(shè)國家撥給60萬元投資，供四個(gè)工廠擴(kuò)建使用，每個(gè)工廠擴(kuò)建后的利潤與投資額的大小有關(guān)，投資后的利潤函數(shù)如下表所示。投資利潤0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依據(jù)題意，是要求f4(60)

。按順序解法計(jì)算。第一階段：求f1(x)。顯然有f1(x)＝g1(x)，得到下表

投資利潤0102030405060f1(x)＝

g1(x)0205065808585最優(yōu)策略0102030405060第二階段：求f2(x)。此時(shí)需考慮第一、第二個(gè)工廠如何進(jìn)行投資分配，以取得最大的總利潤。最優(yōu)策略為（40，20），此時(shí)最大利潤為120萬元。同理可求得其它f2(x)

的值。最優(yōu)策略為（30，20），此時(shí)最大利潤為105萬元。最優(yōu)策略為（20，20），此時(shí)最大利潤為90萬元。最優(yōu)策略為（20，10），此時(shí)最大利潤為70萬元。最優(yōu)策略為（10，0）或（0，10），此時(shí)最大利潤為20萬元。f2(0)＝0最優(yōu)策略為（0，0），最大利潤為0萬元。得到下表最優(yōu)策略為（20，0），此時(shí)最大利潤為50萬元。

投資利潤0102030405060f2(x)020507090105120最優(yōu)策略(0,0)(10,0)(0,10)(20,0)(20,10)(20,20)(30,20)(40,20)第三階段：求f3(x)。此時(shí)需考慮第一、第二及第三個(gè)工廠如何進(jìn)行投資分配，以取得最大的總利潤。最優(yōu)策略為（20，10，30），最大利潤為155萬元。同理可求得其它f3(x)的值。得到下表投資利潤0102030405060f3(x)0256085110135155最優(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)。即問題的最優(yōu)策略。最優(yōu)策略為（20，0，30，10），最大利潤為160萬元。練習(xí)：求投資分配問題得最優(yōu)策略，其中a＝50萬元，其余資料如表所示。投資利潤01020304050g1(x)02140528085g2(x)015365073100g3(x)02560656870例：某公司打算在3個(gè)不同的地區(qū)設(shè)置4個(gè)銷售點(diǎn)，根據(jù)市場部門估計(jì)，在不同地區(qū)設(shè)置不同數(shù)量的銷售點(diǎn)每月可得到的利潤如表所示。試問在各地區(qū)如何設(shè)置銷售點(diǎn)可使每月總利潤最大。地區(qū)銷售點(diǎn)01234123000161210251714302116322217x1=2，x2=1，x3=1，f3(4)=47

*資源連續(xù)分配問題這類問題需要考慮資源的回收利用，其中的決策變量為連續(xù)值。此類分配問題一般敘述如下：設(shè)有數(shù)量為s1

的某種資源，可投入生產(chǎn)A和B兩種產(chǎn)品。第一年若以數(shù)量u1

投入生產(chǎn)A，剩下s1-u1

的就投入生產(chǎn)B，可得收入為這種資源投入A、B生產(chǎn)后，年終還可回收再投入生產(chǎn)。設(shè)年回收率分別為0<a<1和0<b<1，則在第一年生產(chǎn)后，回收的資源數(shù)量合計(jì)為第二年再將資源數(shù)量s2中的u2和s2-u2分別再投入生產(chǎn)A和B，則第二年又可得到的收入為如此繼續(xù)進(jìn)行n年，試問：應(yīng)當(dāng)如何決定每年投入A生產(chǎn)的資源量u1,u2,…,un，才能使總的收入最大？此問題寫成靜態(tài)規(guī)劃問題為用動態(tài)規(guī)劃方法求解的思路如下：設(shè)sk為狀態(tài)變量，表示在第k階段（第k年）可投入生產(chǎn)A和B兩種產(chǎn)品的資源量。uk為決策變量，表示在第k階段（第k年）用于生產(chǎn)A的資源量，則sk-uk為用于生產(chǎn)B的資源量。狀態(tài)轉(zhuǎn)移方程為最優(yōu)值函數(shù)fk(sk)表示有資源sk，從第k階段至第n階段采取最優(yōu)分配方案進(jìn)行生產(chǎn)后所得到的最大總收入。因此可以寫出動態(tài)規(guī)劃的逆推關(guān)系式為最后求出的f1(s1)即為所求問題的最大收入。例5.4(機(jī)器負(fù)荷分配問題)。某種機(jī)器可在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。設(shè)機(jī)器在高負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為g=8u1，其中u1為投入生產(chǎn)的機(jī)器數(shù)量，年完好率a=0.7；在低負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為h=5y，其中y為投入生產(chǎn)的機(jī)器數(shù)量，年完好率為b=0.9。假定開始生產(chǎn)時(shí)完好機(jī)器的數(shù)量s1=1000。試問每年如何安排機(jī)器在高、低負(fù)荷下的生產(chǎn)，使在5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。解：設(shè)階段序數(shù)k表示年度；狀態(tài)變量sk

為第k年度初擁有的完好機(jī)器數(shù)量，同時(shí)也是第k-1年度末時(shí)的完好機(jī)器數(shù)量。決策變量uk

為第k年度中分配高負(fù)荷下生產(chǎn)的機(jī)器數(shù)量，則該年度中分配在低負(fù)荷下生產(chǎn)的機(jī)器數(shù)量為sk-uk，這里sk

和uk

均取連續(xù)變量。狀態(tài)轉(zhuǎn)移方程為k段允許決策集合為設(shè)vk(sk,uk)為第k

年度的產(chǎn)量，則指標(biāo)函數(shù)為令最優(yōu)值函數(shù)fk(sk)表示由資源量sk

出發(fā)，從第k

年開始到第5年結(jié)束時(shí)所生產(chǎn)的產(chǎn)品的總產(chǎn)量最大值，則有逆推關(guān)系式采用逆推法，從第5年度開始向前逆推計(jì)算。最優(yōu)策略為即前兩年應(yīng)把年初全部完好機(jī)器投入低負(fù)荷生產(chǎn)，后三年應(yīng)把年初全部完好機(jī)器投入高負(fù)荷生產(chǎn)，這樣所得的產(chǎn)量最高，總計(jì)為23691.2。在得到整個(gè)問題的最優(yōu)指標(biāo)函數(shù)值和最優(yōu)策略后，還需反過來確定每年年初的機(jī)器狀態(tài)，即從始端向終端遞推計(jì)算出每年年初完好機(jī)器數(shù)。已知s1=1000臺，則可得采用LINGO程序來進(jìn)行求解。該問題的靜態(tài)規(guī)劃模型為sets:stages/1..6/:s;years/1..5/:u;endsetsdata:a=0.7;b=0.9;enddatamax=@sum(years(i):8*u(i)+5*(s(i)-u(i)));s(1)=1000;@for(stages(j)|j#ge#2:s(j)=0.7*u(j-1)+0.9*(s(j-1)-u(j-1)));@for(years(i):u(i)<=s(i));上面所討論的最優(yōu)策略過程，始端狀態(tài)s1是固定的，終端狀態(tài)s6是自由的。由此所得出的最優(yōu)策略稱為始端固定終端自由的最優(yōu)策略，實(shí)現(xiàn)的是5年里的產(chǎn)品總產(chǎn)量最高。如果在終端也附加一定的約束條件，如規(guī)定在第5年度結(jié)束時(shí)，完好的機(jī)器數(shù)量為500臺（上面只有277.83臺），問如何安排生產(chǎn)才能在滿足這一終端要求的情況下產(chǎn)量最高？如果采用LINGO程序進(jìn)行求解，則只要在以上的程序清單中增加一條約束，即增加語句s(6)=500;運(yùn)算結(jié)果如下：

Globaloptimalsolutionfound.Objectivevalue:21832.85Totalsolveriterations:2VariableValueReducedCostS(1)1000.0000.000000S(2)900.00000.000000S(3)810.00000.000000S(4)729.00000.000000S(5)656.10000.000000S(6)500.00000.000000U(1)0.0000002.407300U(2)0.0000001.897000U(3)0.0000001.330000U(4)0.0000000.7000000U(5)452.45000.000000即在前4年將完好機(jī)器全部在低負(fù)荷狀態(tài)下運(yùn)行，第5年年初將656.1臺完好的機(jī)器中的452.45臺用于高負(fù)荷生產(chǎn)，其他的機(jī)器在低負(fù)荷狀態(tài)下生產(chǎn)，則在第5年末完好的機(jī)器數(shù)為500臺，最優(yōu)的總產(chǎn)量為21832.85。有一個(gè)徒步旅行者，其可攜帶物品重量的限度為a公斤，設(shè)有n

種物品可供他選擇裝入包中。已知每種物品的重量及使用價(jià)值（作用），問此人應(yīng)如何選擇攜帶的物品（各幾件），使所起作用（使用價(jià)值）最大？物品

12…j…n重量（公斤/件）

a1a2…

aj

…

an每件使用價(jià)值

c1c2…cj

…

cn這就是背包問題。類似的還有工廠里的下料問題、運(yùn)輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。5.5背包問題設(shè)xj

為第j種物品的裝件數(shù)（非負(fù)整數(shù)）則問題的數(shù)學(xué)模型如下：用動態(tài)規(guī)劃方法求解，令

fk

(y)=總重量不超過

y公斤，包中只裝有前k種物品時(shí)的最大使用價(jià)值。其中y≥0，k

＝1,2,…,n。所以問題就是求fn(a)

其遞推關(guān)系式為：當(dāng)k=1時(shí)，有：例5.5：求下面背包問題的最優(yōu)解(a=5)物品123重量（公斤）325使用價(jià)值8512解：a＝5，問題是求f3(5)所以，最優(yōu)解為X＝（1,1,0），最優(yōu)值為Z=13。練習(xí)：某廠生產(chǎn)三種產(chǎn)品，各種產(chǎn)品重量與利潤的關(guān)系如表所示?，F(xiàn)將此三種產(chǎn)品運(yùn)往市場出售，運(yùn)輸能力總重量不超過6噸，問如何安排運(yùn)輸，使總利潤最大？種類123重量（噸/公斤）234單件利潤（元）80130180最優(yōu)方案：X1

=（0,2,0）X2=（1,0,1）Z=2605.6.1n×1排序問題即n

種零件經(jīng)過1種設(shè)備進(jìn)行加工，已知每種零件的加工時(shí)間和交貨日期，如何安排加工順序才能使：（1）平均通過設(shè)備的時(shí)間最小？（2）所有零件均能按時(shí)交貨？（3）既能滿足交貨時(shí)間，又使平均通過時(shí)間最??？例5.6

有5種零件需要在同一臺機(jī)器上加工，每種零件的加工時(shí)間和需要交貨的時(shí)間如下表所示。零件代號j1j2j3j4j5加工時(shí)間(t)37154交貨日期(d)23208614*5.6排序問題1、平均通過設(shè)備的時(shí)間最小按零件加工時(shí)間非負(fù)次序排列順序，其時(shí)間最小，即將加工時(shí)間由小到大排列即可。各零件的加工順序如圖5-4所示。其中：某零件實(shí)際通過設(shè)備的時(shí)間=前面加工的零件實(shí)際通過時(shí)間+該零件的加工時(shí)間平均通過時(shí)間=各零件實(shí)際通過時(shí)間之和/零件數(shù)延遲交貨時(shí)間=max{各零件實(shí)際通過時(shí)間–交貨時(shí)間,0}因此，本例中平均通過時(shí)間=(1+4+8+13+20)/5=9.2延遲交貨時(shí)間=max{1-8,4-23,8-14,13-6,20-20}=72、按時(shí)交貨排列順序如果要求按時(shí)交貨，則零件的加工順序可按交貨時(shí)間從小到大的