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

1、動(dòng) 態(tài) 規(guī) 劃 (Dynamic programming),,背包問(wèn)題,資源分配問(wèn)題,生產(chǎn)計(jì)劃問(wèn)題,復(fù)合系統(tǒng)工作可靠性問(wèn)題,有一個(gè)徒步旅行者，其可攜帶物品重量的限度為a 公斤，設(shè)有n 種物品可供他選擇裝入包中。已知每種物品的重量及使用價(jià)值（作用），問(wèn)此人應(yīng)如何選擇攜帶的物品（各幾件），使所起作用（使用價(jià)值）最大？,這就是背包問(wèn)題。類似的還有工廠里的下料問(wèn)題、運(yùn)輸中的貨物裝載問(wèn)題、人造衛(wèi)星內(nèi)的物品裝載問(wèn)題等。,背包問(wèn)題,設(shè)

2、xj 為第j 種物品的裝件數(shù)（非負(fù)整數(shù)）則問(wèn)題的數(shù)學(xué)模型如下：,用動(dòng)態(tài)規(guī)劃方法求解，令 fk(y) = 總重量不超過(guò) y 公斤，包中只裝有前k 種物品時(shí)的最大使用價(jià)值。 其中y ≥0， k ＝1,2, …, n 。所以問(wèn)題就是求 fn(a),其遞推關(guān)系式為：,當(dāng) k=1 時(shí)，有：,例題：求下面背包問(wèn)題的最優(yōu)解,解：a＝5 ，問(wèn)題是求 f3(5),所以，最優(yōu)解為 X＝（1 . 1 . 0），最優(yōu)值為 Z = 13。,練習(xí)2：

3、求下列問(wèn)題的最優(yōu)解,機(jī)器負(fù)荷問(wèn)題　　　某工廠有100臺(tái)機(jī)器，擬分四期使用，每一期都可在高、低兩種不同負(fù)荷下進(jìn)行生產(chǎn)。若把x臺(tái)機(jī)器投入高負(fù)荷下進(jìn)行生產(chǎn)，則在本期結(jié)束時(shí)將有(1/3)*x臺(tái)機(jī)器損壞報(bào)廢；余下的機(jī)器全部投入低負(fù)荷下進(jìn)行生產(chǎn)，則在期末有1/10的機(jī)器報(bào)廢。如果高負(fù)荷下生產(chǎn)時(shí)每臺(tái)機(jī)器可獲利潤(rùn)為10，低負(fù)荷下生產(chǎn)時(shí)每臺(tái)機(jī)器可獲利潤(rùn)為7，問(wèn)怎樣分配機(jī)器使四期的總利潤(rùn)最大？解 將問(wèn)題按周期分為4個(gè)階段，k=1，2，3，4；狀態(tài)變量

4、sk表示第k階段初完好的機(jī)器數(shù)，s1=100，0≤sk≤100；決策變量xk表示第k階段投入高負(fù)荷下生產(chǎn)的機(jī)器數(shù)，則sk－xk表示第k階段投入低負(fù)荷下生產(chǎn)的機(jī)器數(shù)；允許決策集合：Dk（sk）=｛xk|0≤xk≤sk｝狀態(tài)轉(zhuǎn)移方程：sk+1=Tk（sk，xk），即第k+1階段初擁有的完好機(jī)器數(shù)sk+1為：,,階段指標(biāo)函數(shù)：vk（sk，xk）=10xk+7（sk－xk）表示第k階段所獲得的利潤(rùn)；　　　最優(yōu)指標(biāo)函數(shù)fk（sk）表示從

5、第k階段初完好機(jī)器數(shù)為sk至第四階段的最大利潤(rùn)，動(dòng)態(tài)規(guī)劃基本方程為： 　k=4時(shí)， 　　　　　　　　　x4*=s4 　k=3時(shí)， 　　　　　　　 ∴ x3*=s3,,,,k=2時(shí)， 　　　　　　　　　　　　　 ∴ x2*=0 k=1時(shí)， 　　　　　　　　　 ∴ x1*=0,,,因?yàn)閟

6、1=100，所以f1（100）=2680，逆向追蹤得：　s1=100，x1*=0 　　　　　　　　　　　　　　　　x2*=0 　　　　　　　　　　　　　　　　x3*=s3=81 　　　　　　　　　　　　　　　　x4*=s4=54　　　　　即，第1，2期把全部完好機(jī)器投入低負(fù)荷下生產(chǎn)，第3，4期把全部完好機(jī)器投入高負(fù)荷下生產(chǎn)所得利潤(rùn)最大。,,,,三、非線性規(guī)劃問(wèn)題,【例7-4】 用動(dòng)態(tài)規(guī)劃方法解下列非線性規(guī)劃