運籌學動態(tài)規(guī)劃

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

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

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

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

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

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