基于Matlab的動(dòng)態(tài)規(guī)劃算法的實(shí)現(xiàn)及應(yīng)用

陳甜甜

【摘要】介紹了動(dòng)態(tài)規(guī)劃的基本理論，包括動(dòng)態(tài)規(guī)劃的基本概念和基本原理，并針對(duì)生產(chǎn)與存儲(chǔ)問題進(jìn)行了分析，然后結(jié)合Matlab做了編程處理，使復(fù)雜問題簡單化，從而使問題能更方便地得到解決。

【關(guān)鍵詞】動(dòng)態(tài)規(guī)劃生產(chǎn)與存儲(chǔ)問題Matlab語言一、引言

動(dòng)態(tài)規(guī)劃是用于解決運(yùn)籌學(xué)中多階段決策過程最優(yōu)化問題的一種方法。其廣泛應(yīng)用于工程技術(shù)、科學(xué)管理、工農(nóng)業(yè)生產(chǎn)及軍事等領(lǐng)域。在理論上，動(dòng)態(tài)規(guī)劃是求解這類問題全局最優(yōu)解的一種有效方法，特別是對(duì)于實(shí)際中的某些非線性規(guī)劃問題可能是最優(yōu)解的唯一方法。然而，動(dòng)態(tài)規(guī)劃僅僅是解決多階段決策問題的一種方法，或者說是考查問題的一種途徑，而不是一種具體的算法。就目前而言，動(dòng)態(tài)規(guī)劃沒有統(tǒng)一的標(biāo)準(zhǔn)模型，其解法也沒有標(biāo)準(zhǔn)算法。在實(shí)際應(yīng)用中，需要具體問題具體分析。動(dòng)態(tài)規(guī)劃模型的求解問題是影響動(dòng)態(tài)規(guī)劃理論和方法應(yīng)用的關(guān)鍵所在，而子問題的求解和大量結(jié)果的存儲(chǔ)、調(diào)用更是一個(gè)難點(diǎn)所在。然而，隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，特別是內(nèi)存容量和計(jì)算速度的增加，使求解較小規(guī)模的動(dòng)態(tài)規(guī)劃問題成為可能，從而使得動(dòng)態(tài)規(guī)劃的理論和方法在實(shí)際中的應(yīng)用范圍迅速增加。

目前，在計(jì)算機(jī)上實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃的一般求解方法并不多見，尤其是用來解決較復(fù)雜的具體問題數(shù)學(xué)成果甚少。本文從實(shí)際出發(fā)，利用Matlab軟件的強(qiáng)大功能，對(duì)動(dòng)態(tài)規(guī)劃中的生產(chǎn)與存儲(chǔ)問題編制程序，并且進(jìn)行了應(yīng)用檢驗(yàn)來說明方法的可行性。

二、動(dòng)態(tài)規(guī)劃的基本理論

實(shí)際中，要構(gòu)造一個(gè)標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃模型，通常需要采用以下幾個(gè)步驟：

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

（2）選擇狀態(tài)。將問題發(fā)展到各個(gè)階段時(shí)所處的各種客觀條件用不同的狀態(tài)表示，即稱為狀態(tài)。狀態(tài)的選擇要滿足無后效性和可知性，即狀態(tài)不僅依賴于狀態(tài)的轉(zhuǎn)移規(guī)律，還依賴于允許決策集合和指標(biāo)函數(shù)結(jié)構(gòu)。

（3）確定決策變量與狀態(tài)轉(zhuǎn)移方程。當(dāng)各段的狀態(tài)取定后，可以做出不同的決策，從而確定下一階段的狀態(tài)，這種決定稱為決策。描述決策的變量稱為決策變量。在決策過程中，由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過程稱為狀態(tài)轉(zhuǎn)移。狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。

（4）寫出動(dòng)態(tài)規(guī)劃的基本方程動(dòng)態(tài)規(guī)劃的基本方程一般根據(jù)實(shí)際問題可分為兩種形式，逆序形式和順序形式。動(dòng)態(tài)規(guī)劃基本方程的逆序形式為： 三、Matlab程序設(shè)計(jì)

為了編制動(dòng)態(tài)規(guī)劃的Matlab程序，我們需要?jiǎng)?chuàng)建M文件。M文件有兩種：命令文件和函數(shù)文件。兩者的區(qū)別在于：命令文件沒有輸入?yún)?shù)，也不返回輸出參數(shù)；而函數(shù)文件可以輸入?yún)?shù)，也可以輸出參數(shù)。命令文件對(duì)Matlab工作空間中的變量進(jìn)行操作，而函數(shù)文件中定義的變量為局部變量，當(dāng)函數(shù)文件執(zhí)行完畢后，這些變量被清除。

由于動(dòng)態(tài)規(guī)劃問題的特殊性，其涉及的實(shí)際問題均需要進(jìn)行反復(fù)計(jì)算求解，所以在使用Matlab語言對(duì)其進(jìn)行程序設(shè)計(jì)的過程中用的最多的是循環(huán)結(jié)構(gòu)。本文中的編程主要用到了循環(huán)結(jié)構(gòu)中的if語句和for語句。

動(dòng)態(tài)規(guī)劃法算法的關(guān)鍵為每月產(chǎn)量和庫存量的取值范圍及相互關(guān)系，這也是程序?qū)崿F(xiàn)時(shí)的最主要部分。程序整體上采用逆推法，首先，計(jì)算四月份最優(yōu)指標(biāo)及對(duì)應(yīng)月初庫存量，并將其存入數(shù)組，然后再計(jì)算三月份最優(yōu)指標(biāo)對(duì)應(yīng)月初庫存量。其中，三月份計(jì)算過程需用到存儲(chǔ)的四月份最優(yōu)指標(biāo)及對(duì)應(yīng)月初庫存量數(shù)值。然后再計(jì)算二月份最優(yōu)指標(biāo)，以此類推。其次，在計(jì)算每月最優(yōu)指標(biāo)及對(duì)應(yīng)月初庫存量時(shí)采用遍歷法，取當(dāng)月月初庫存量及當(dāng)月產(chǎn)量所有值（當(dāng)月月初庫存量取值極限為零到前面幾月均最大生產(chǎn)能力減去前面幾月的市場需求數(shù)，當(dāng)月產(chǎn)量取值極限為零到月最大生產(chǎn)能力），但必須在滿足當(dāng)月月初庫存量和當(dāng)月產(chǎn)量大于當(dāng)月市場需求量并且小于當(dāng)月及后續(xù)月市場需求總和才進(jìn)行計(jì)算。

四、實(shí)例分析——生產(chǎn)與存儲(chǔ)問題

某廠某月生產(chǎn)某種產(chǎn)品600件，當(dāng)月生產(chǎn)的產(chǎn)品若未銷出，就需存儲(chǔ)（當(dāng)月入

庫的產(chǎn)品，當(dāng)月不需要支付存儲(chǔ)費(fèi)）。月初入庫的產(chǎn)品需支付該月的存儲(chǔ)費(fèi)，費(fèi)用為每月每100件1千元。如果假設(shè)生產(chǎn)100件產(chǎn)品的費(fèi)用為5千元，并且如果安排了生產(chǎn)該月工廠還要支付經(jīng)營費(fèi)4千元，每月的市場需求我們?cè)谙卤碇薪o出，如果要求第1個(gè)月的月初及第4個(gè)月的月底庫存量為零，問每月應(yīng)如何安排

生產(chǎn)，才能即滿足市場需求，又可以使這4個(gè)月的總生產(chǎn)及存儲(chǔ)費(fèi)用之和最小。

1.應(yīng)用動(dòng)態(tài)規(guī)劃法的方法求解

首先對(duì)于動(dòng)態(tài)規(guī)劃的概念做一下處理。

計(jì)算過程及結(jié)果如表2所示。

計(jì)算過程及結(jié)果如表3所示。

由表4可知，最優(yōu)生產(chǎn)及存儲(chǔ)方案為第一個(gè)月產(chǎn)量為5個(gè)單位，第二個(gè)月產(chǎn)量為6個(gè)，第三個(gè)月第四個(gè)月不生產(chǎn)，總最低費(fèi)用67元。

2.Matlab程序設(shè)計(jì)（略）

根據(jù)前面的分析與實(shí)際應(yīng)用結(jié)果，可以充分證明，我們采用的求解動(dòng)態(tài)規(guī)劃問題的方法和Matlab實(shí)現(xiàn)程序是有效的。該程序不僅可以方便簡潔地得到結(jié)果，避免了繁瑣的計(jì)算，大大降低了工作量，而且可以處理生產(chǎn)函數(shù)和存儲(chǔ)函數(shù)變化時(shí)的其他一系列生產(chǎn)與存儲(chǔ)問題。簡化了動(dòng)態(tài)規(guī)劃問題的計(jì)算。

參考文獻(xiàn)：

[1]鄭怡，趙海良，徐詠.基于Matlab的動(dòng)態(tài)規(guī)劃問題[J].重慶工學(xué)院學(xué)報(bào)，2008，（05）：152.

[2]于斌，劉姝麗，韓中庚.動(dòng)態(tài)規(guī)劃求解方法的Matlab實(shí)現(xiàn)及應(yīng)用[J].信息工程大學(xué)學(xué)報(bào)，2005，（03）：95.

[3]胡運(yùn)權(quán).運(yùn)籌學(xué)教程[M].北京：清華大學(xué)出版社，2007.

[4]祁宗，鄭至勇，鄧偉.運(yùn)籌學(xué)與最優(yōu)化Matlab編程[M].2010.72.

[5]劉衛(wèi)國.科學(xué)計(jì)算與Matlab語言[M].北京：中國鐵道出版社，2000.

[6]樓順天.Matlab程序設(shè)計(jì)語言[M].西安：西安電子科技大學(xué)出版社，1997.

基金項(xiàng)目：湖南省教育廳科研項(xiàng)目（16C1483）。