基于Matlab的動態規劃算法的實現及應用

◆陳甜甜

(湘南學院數學與金融學院)

一、引言

動態規劃是用于解決運籌學中多階段決策過程最優化問題的一種方法。其廣泛應用于工程技術、科學管理、工農業生產及軍事等領域。在理論上，動態規劃是求解這類問題全局最優解的一種有效方法，特別是對于實際中的某些非線性規劃問題可能是最優解的唯一方法。然而，動態規劃僅僅是解決多階段決策問題的一種方法，或者說是考查問題的一種途徑，而不是一種具體的算法。就目前而言，動態規劃沒有統一的標準模型，其解法也沒有標準算法。在實際應用中，需要具體問題具體分析。動態規劃模型的求解問題是影響動態規劃理論和方法應用的關鍵所在，而子問題的求解和大量結果的存儲、調用更是一個難點所在。然而，隨著計算機技術的快速發展，特別是內存容量和計算速度的增加，使求解較小規模的動態規劃問題成為可能，從而使得動態規劃的理論和方法在實際中的應用范圍迅速增加。

目前，在計算機上實現動態規劃的一般求解方法并不多見，尤其是用來解決較復雜的具體問題數學成果甚少。本文從實際出發，利用Matlab軟件的強大功能，對動態規劃中的生產與存儲問題編制程序，并且進行了應用檢驗來說明方法的可行性。

二、動態規劃的基本理論

實際中，要構造一個標準的動態規劃模型，通常需要采用以下幾個步驟：

(1)劃分階段。將所給問題的過程，按照問題的時間或空間特征分解成若干互相聯系的階段，以便按次序求每階段的解。

(2)選擇狀態。將問題發展到各個階段時所處的各種客觀條件用不同的狀態表示，即稱為狀態。狀態的選擇要滿足無后效性和可知性，即狀態不僅依賴于狀態的轉移規律，還依賴于允許決策集合和指標函數結構。

(3)確定決策變量與狀態轉移方程。當各段的狀態取定后，可以做出不同的決策，從而確定下一階段的狀態，這種決定稱為決策。描述決策的變量稱為決策變量。在決策過程中，由一個狀態到另一個狀態的演變過程稱為狀態轉移。狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。

(4)寫出動態規劃的基本方程動態規劃的基本方程一般根據實際問題可分為兩種形式，逆序形式和順序形式。動態規劃基本方程的逆序形式為：

三、Matlab程序設計

為了編制動態規劃的Matlab程序，我們需要創建M文件。M文件有兩種：命令文件和函數文件。兩者的區別在于：命令文件沒有輸入參數，也不返回輸出參數；而函數文件可以輸入參數，也可以輸出參數。命令文件對Matlab工作空間中的變量進行操作，而函數文件中定義的變量為局部變量，當函數文件執行完畢后，這些變量被清除。

由于動態規劃問題的特殊性，其涉及的實際問題均需要進行反復計算求解，所以在使用Matlab語言對其進行程序設計的過程中用的最多的是循環結構。本文中的編程主要用到了循環結構中的if語句和for語句。

動態規劃法算法的關鍵為每月產量和庫存量的取值范圍及相互關系，這也是程序實現時的最主要部分。程序整體上采用逆推法，首先，計算四月份最優指標及對應月初庫存量，并將其存入數組，然后再計算三月份最優指標對應月初庫存量。其中，三月份計算過程需用到存儲的四月份最優指標及對應月初庫存量數值。然后再計算二月份最優指標，以此類推。其次，在計算每月最優指標及對應月初庫存量時采用遍歷法，取當月月初庫存量及當月產量所有值(當月月初庫存量取值極限為零到前面幾月均最大生產能力減去前面幾月的市場需求數，當月產量取值極限為零到月最大生產能力)，但必須在滿足當月月初庫存量和當月產量大于當月市場需求量并且小于當月及后續月市場需求總和才進行計算。

四、實例分析——生產與存儲問題

某廠某月生產某種產品600件，當月生產的產品若未銷出，就需存儲(當月入庫的產品，當月不需要支付存儲費)。月初入庫的產品需支付該月的存儲費，費用為每月每100件1千元。如果假設生產100件產品的費用為5千元，并且如果安排了生產該月工廠還要支付經營費4千元，每月的市場需求我們在下表中給出，如果要求第1個月的月初及第4個月的月底庫存量為零，問每月應如何安排生產，才能即滿足市場需求，又可以使這4個月的總生產及存儲費用之和最小。

1.應用動態規劃法的方法求解

首先對于動態規劃的概念做一下處理。

計算過程及結果如表2所示。

計算過程及結果如表3所示。

由表4可知，最優生產及存儲方案為第一個月產量為5個單位，第二個月產量為6個，第三個月第四個月不生產，總最低費用67元。

2.Matlab程序設計(略)

根據前面的分析與實際應用結果，可以充分證明，我們采用的求解動態規劃問題的方法和Matlab實現程序是有效的。該程序不僅可以方便簡潔地得到結果，避免了繁瑣的計算，大大降低了工作量，而且可以處理生產函數和存儲函數變化時的其他一系列生產與存儲問題。簡化了動態規劃問題的計算。