◆陳甜甜

(湘南學(xué)院數(shù)學(xué)與金融學(xué)院)

一、引言

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

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

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

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

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

(2)選擇狀態(tài)。將問題發(fā)展到各個階段時所處的各種客觀條件用不同的狀態(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)，這種決定稱為決策。描述決策的變量稱為決策變量。在決策過程中，由一個狀態(tài)到另一個狀態(tài)的演變過程稱為狀態(tài)轉(zhuǎn)移。狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。

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

三、Matlab程序設(shè)計

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

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

動態(tài)規(guī)劃法算法的關(guān)鍵為每月產(chǎn)量和庫存量的取值范圍及相互關(guān)系，這也是程序?qū)崿F(xiàn)時的最主要部分。程序整體上采用逆推法，首先，計算四月份最優(yōu)指標(biāo)及對應(yīng)月初庫存量，并將其存入數(shù)組，然后再計算三月份最優(yōu)指標(biāo)對應(yīng)月初庫存量。其中，三月份計算過程需用到存儲的四月份最優(yōu)指標(biāo)及對應(yīng)月初庫存量數(shù)值。然后再計算二月份最優(yōu)指標(biāo)，以此類推。其次，在計算每月最優(yōu)指標(biāo)及對應(yīng)月初庫存量時采用遍歷法，取當(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)行計算。

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

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

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

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

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

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

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

2.Matlab程序設(shè)計(略)

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