第七章

動態規劃教學要求：了解動態規劃的基本思想掌握一維離散動態規劃的建模和求解方法應用會運用動態規劃方法解決一些基本應用問題。目錄動態規劃原理和模型一維動態規劃求解方法動態規劃在經濟和管理中的應用目錄動態規劃原理和模型一維動態規劃求解方法動態規劃在經濟和管理中的應用動態規劃的基本概念最短路問題：某運輸公司擬將一批貨物從A地運往E地，其間的交通系統網絡如下圖所示。圖上節點表示地點，邊表示兩地之間的道路，邊上的數字表示兩地間的運輸費用，求運輸費用最低的運輸路線。AB1B2B3C1C2C3D1D2E第2階段第3階段第4階段第1階段的狀態決策：某階段狀態給定之后，從該狀態演變到下一階段某一狀態的選擇。比如從第一階段到第二階段選擇什么路線。

策略：各階段決策確定后，組成的一個有序的決策序列。第2階段的狀態第1階段動態規劃模型建立實例

增加研制費（萬元）新產品成功的概率甲乙丙0120.600.800.850.400.700.900.300.600.70有一工廠研制甲、乙、丙三種新產品，估計這三種新研制成功的概率分別為：0.6、0.4、0.3。由于工廠急于推出新產品，決定再加撥2萬元研制費，以提高新產品研制成功的概率。據估計，把增加的研制費用于各種新產品研制時，研制成功的概率見下表7-2。現把這批研制費分配給各新產品（不分配、分配給1萬元或分配給2萬元），使這三種新產品都研制成功的概率最大。應怎樣分配。動態規劃模型的建立步驟

劃分階段

把對某一種新產品的研制提供研制費用作為一個階段，這樣可將整個過程分為三個階段，依此為第1階段、第2階段、第3階段，k=1,2,3

狀態變量

把有可能提供的研制費用作為狀態變量，記為sk，它的取值范圍是：0、1、2

決策變量

把給第k種新產品的研制提供研制費用的數量作為決策變量uk

建立狀態轉移方程

sk+1=sk-uk

確定指標函數

確定邊界條件

由于開始時可用的金額為2萬元，而最后將全部用完，所以s1=2，s4=0最優化原理一個過程的最優決策具有這樣的性質：無論初始狀態及初始決策如何，對于先前決策所形成的狀態而言，其以后的所有決策應構成最優策略。動態規劃方法是既把當前的一段和未來的各段分開，又把當前效益和未來效益結合起來考慮的一種最優化方法。因此，每階段決策的選取都是從全局來考慮的。另外，許多問題用動態規劃研究求解比線性規劃、非線性規劃更有效，特別是離散性問題，很難用解析數學的方法，而用動態規劃就迎刃而解了；某些情況下，用動態規劃處理不僅能作定性描述分析，且可利用計算機給出求其數值解的方法。但動態規劃也存在如下不足：

1．沒有統一的處理方法，求解時要根據問題的性質，結合多種數學技巧。因此，實踐經驗及創造性思維將起重要的引導作用。

2．當變量個數太多時，由于計算機內存和速度的限制導致問題無法解決。有些問題由于涉及的函數沒有理想的性質使問題只能用動態規劃描述，而不能用動態規劃方法求解。動態規劃模型的建立1.劃分階段

根據問題的性質，按照時間、空間、變量劃分為若干階段，這是用多階段決策過程描述一個實際問題的第一步。一個階段表示需要做出一次決策的子問題，建立動態規劃模型要求每個階段問題具有同一模式。描述階段的變量稱為階段變量，常用自然數k表示。如例7.1可劃分為4個階段求解，k=1，2，3，4。2.確定狀態變量和決策變量以及相應的取值范圍

多階段決策過程的進展，可用各階段的狀態演變來描述。狀態必須包含表示系統情況和確定決策所需要的全部信息，使其能反映過程的演變特征。同時還要狀態滿足無后效性，即若已知過程現在處于某一階段的某一狀態，則該階段以后過程的演變，不再受以前各階段狀態的影響。確定狀態變量之后，根據具體問題的性質，找出狀態變量在各階段的取值范圍。決策變量一般由系統最優化的目的所決定。3.建立狀態轉移方程

根據狀態變量和決策變量的含義，寫出狀態轉移方程。4.確定指標函數，建立動態規劃的基本方程

選取指標函數，根據指標函數建立最優指標函數遞推關系,即基本方程5.確定邊界條件目錄動態規劃原理和模型一維動態規劃求解方法動態規劃在經濟和管理中的應用一維動態規劃求解方法——逆推法第三階段

s3=0

s3=1

s3=2第二階段

s2=0

s2=1

s2=2第一階段只有S1=2s2=s1-0=2s3=s2-1=1最優解0-1-1從最后一個階段開始，逐階段向前，直至第一階段，即可求出全過程最優策略和指標函數的最優值。一維動態規劃求解方法——順推法s3=s4+1=1s2=s3+1=2最優解0-1-1由第一階段開始，逐階段向后，直至最后一個階段，同樣可求出最優策略和指標函數的最優值。第一階段

s2=0

s2=1

s2=2第二階段

s3=0s3=1

s3=2第三階段目錄動態規劃原理和模型一維動態規劃求解方法動態規劃在經濟和管理中的應用背包問題一位旅行者攜帶背包旅游，已知他的背包所能承受的重量為w千克，現有n種物品可供他選擇裝入包中，第i種物品的單件重量為wi

千克，其價值是攜帶數量的函數。問旅行者應如何選擇攜帶物品的件數，使總價值最大？

劃分階段

將可裝入物品按排序，每段裝一種物品，共劃分為n個階段，k=1,2,……,n.

狀態變量

表示在第k階段開始時，背包中允許裝入前k種物品的總重量，記為sk

決策變量

裝入第k種物品的件數xk

建立狀態轉移方程

sk+1=sk-wkxk

允許決策集合

確定指標函數

確定邊界條件

背包所能承受的重量為w千克生產計劃問題已知企業產品的生產費用、存儲費用和市場的需求量，在其生產能力和存儲能力許可的前提下，怎樣制定各個時期的生產計劃，既能完成交貨任務，又使總支出最小。某中轉倉庫要按月在月初供應一定數量的某種部件給總裝車間，由于生產條件的變化，生產車間在各月份中生產每單位這種部件所需耗費的工時不同，各月份的生產量于當月的月底前，全部要存入倉庫以備后用。已知總裝車間的各個月份的需求量以及在加工車間生產該部件每單位數量所需工時，倉庫容量和開始庫存量，要求最終庫存量為0，要制定一個半年的逐月生產計劃，既滿足需要和倉庫容量的限制，又使生產這種部件的總耗費工時數最少。生產計劃問題劃分階段

按月份劃分階段，每個月為一個階段，k=1,2,……,n.

狀態變量

第k階段開始時（即本階段需求送出之前，上階段產品送入之后）部件庫存量，記為sk

決策變量

第k階段內的部件生產量，記為uk

建立狀態轉移方程

sk+1=sk+uk-dk

最優指標函數

fk(sk)表示在第k階段開始的庫存量為sk時，從第k階段到最后一階段生產部件的最小累計工時數。

基本方程

確定邊界條件

so=開始庫存量，sn=0貨物存儲問題考慮下面三個月的庫存問題，在每月初，公司必須決定在本月內，應生產多少產品。在一個月內生產x單位的產品，所需成本為c(x)，其中c(0)=0，當x>0時，c(x)=3+2x。每月最多生產4個單位，每月的需求是隨機的，或為1或為2單位。如果生產的數量大于需求，就出現庫存。每個月末檢查庫存，1個單位的庫存費用是1元。因為庫存能力有限，每月末的庫存量不能超過3單位。但同時要求必須及時滿足需求。在第3個月末要把現有的庫存以每單位2元的價格售出。在第1月的月初，公司有1單位的庫存。如何制定生產策略使三個月內的期望費用最小。

劃分階段

將三個月分為三個階段，每個月為一個階段

狀態變量

sk表示第k個月初的庫存數

決策變量

xk表示第k月生產的單位數

建立狀態轉移方程

，其中為一隨機需求量或為1或為2

最優指標函數

fk(sk)表示第k個月初的庫存是時，第k個月至第3個月內的最小期望費用。設備更新問題在企業中，經常遇到設備陳舊或部分損壞需要更新的問題。從經濟上分析，一種設備應該使用多少年后進行更新最合算。這就是要研究的問題。一般來說，一臺新設備出故障少，維護費用低，帶來的經濟效益就高；隨著使用年限的增加，新設備逐漸變舊，維護費用增加，效用降低。在適當的時候，就要賣掉舊設備，購買新設備。當然，設備越舊越不值錢，購買新設備又需要一定數額的購買費，這就是設備的更新決策問題。

rk(t)：在第k年設備已使用過t年，再使用1年的效益

uk(t)：在第k年設備已使用過t年，再使用1年的維修費用

ck(t)：在第k年賣掉一臺已使用過t年的設備，買進一臺新設備的更新費用

a：折扣因子，表示一年以后的單位收入價值相當于現在的a單位

fk(t)：已使用了t年的舊設備，從第k年開始在以后繼續使用到規定的第n年未知幾年內的總回收額設備更新問題

劃分階段

k表示計劃使用該設備的年限數

狀態變量

sk表示第k年初，設備已使用過的年數

決策變量

xk表示第k年初更新，還是繼續使用舊設備，分別用R和K表示。

建立狀態轉移方程

動態規劃的基本方程資源分配問題將一種或多種有限的資源，分配給若干個使用者，而使目標達到最優設有一原料，總量為a，用于生產n種產品。若分配數量xi用于生產第i種產品，其產生的效益為ri(xi)。問如何分配，才能使生產n種產品的總收入最大？。劃分階段將n種產品按1,2,……,n的序號排列,每種產品為一個階段,分為n個階段,k=1,2,……,n.

狀態變量sk表示分配給第k個產品至第n種產品的資源數。

決策變量xk表示分配給第k個產品的資源數。

建立狀態轉移方程sk+1=sk-xk

最優指標函數fk(sk)表示在擁有資源sk，分配給第k種產品至第n種產品所得到的最大總收入。

基本方程

確定邊界條件因為在第1階段時的資源為總資源，到第n+1階段時資源已分配完畢，所以so=a，sn+1=0,fn+1(sn+1)=0.復合系統可靠性問題若某種機器的工作系統有N個部件組成，只要有一個部件失靈，整個系統就不能正常工作。這些部件的正常工作關系為串接關系，為提高系統工作的可靠性，在每一個部件上均裝有主要元件的備用件，并且設計了備用件自動投入裝置。顯然，備用元件越多，整個系統正常工作的可靠性越大。但備用元件多了，整個系統的成本、重量、體積均相應加大，工作精度也降低。因此，最優化問題是在考慮上述限制條件下，應如何選擇各部件的備用元件數，使整個系統的工作可靠性最大？設部件i上裝有z