動(dòng)態(tài)規(guī)劃方法在物流管理中的應(yīng)用研究

1、摘要隨著我國(guó)經(jīng)濟(jì)的不斷發(fā)展，現(xiàn)代物流業(yè)作為第三利潤(rùn)源，已經(jīng)越來(lái)越多受到大中小企業(yè)的重視，盡可能地減少物流總成本也成為企業(yè)關(guān)注的焦點(diǎn)，企業(yè)家們已經(jīng)開(kāi)始從整個(gè)物流系統(tǒng)的角度來(lái)衡量和分析物流活動(dòng)的耗費(fèi)情況，用全局的思想來(lái)優(yōu)化每一項(xiàng)物流活動(dòng)。因此，物流管理作為物流活動(dòng)的的必要環(huán)節(jié)，其耗費(fèi)人力，財(cái)力以及物力的多少，直接關(guān)系著物流活動(dòng)的成本問(wèn)題。但通過(guò)多方資料對(duì)我國(guó)物流管理的研究，發(fā)現(xiàn)不少企業(yè)仍然使用原始的管理方法，借鑒國(guó)外的大型企業(yè)的優(yōu)秀物流管理方法。結(jié)合我國(guó)實(shí)際國(guó)情，提出了在物流管理中使用動(dòng)態(tài)規(guī)劃的方法，動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的分支，是求解決策過(guò)程最優(yōu)化的數(shù)學(xué)方法。使用動(dòng)態(tài)規(guī)劃來(lái)進(jìn)行物流管理，能合理的利用相

2、關(guān)的措施，有效的降低各項(xiàng)管理活動(dòng)的總成本。提過(guò)企業(yè)的經(jīng)濟(jì)效益。本文通過(guò)將詳細(xì)對(duì)動(dòng)態(tài)規(guī)劃方法和物流管理兩個(gè)關(guān)鍵點(diǎn)進(jìn)行分析，并將把使用動(dòng)態(tài)規(guī)劃解決物流管理的問(wèn)題作為該篇的重心來(lái)進(jìn)行論述，分別對(duì)物流管理中的資源分配問(wèn)題，存貯問(wèn)題，最短路問(wèn)題和背包問(wèn)題進(jìn)行實(shí)際的案例分析。來(lái)論證動(dòng)態(tài)規(guī)劃方法對(duì)物流管理起到的重要作用。關(guān)鍵詞：動(dòng)態(tài)規(guī)劃；物流管理； 物流成本；存貯問(wèn)題AbstractWith China's economy continues to develop modern logistics industry as the third profit source, has been more

3、and more medium and small companies to survive, to minimize total logistics costs become the focus of attention of the enterprise, entrepreneurs have begun from the entirelogistics point of view of the system to measure and analyze the cost of logistics activities, the idea of global optimization of

4、 a logistics activities. , Logistics management as a necessary part of logistics activities, the cost of human, financial and material resources, is directly related to the cost of logistics activities. Through the multi-information on China's logistics management, many companies still use the o

5、riginal management, drawing on the large foreign enterprises of the outstanding logistics management methods. China's actual conditions, using dynamic programming methods in logistics management, dynamic programming is a branch of operations research, mathematical methods for solving decision-ma

6、king process optimization. Using dynamic programming to logistics management, rational use of relevant measures to effectively reduce the total cost of the management activities. Mentioned that the economic efficiency of enterprises.This paper analyzed in detail the two key points of the dynamic pro

7、gramming methods and logistics management, and use dynamic programming to solve the problem of logistics management as the center of gravity of the article discusses the resource allocation problem in logistics management, storage problem, the shortest path problem and the knapsack problem for the a

8、ctual case studies. To demonstrate the dynamic programming method of logistics management play an important role.Key words：Dynamic programming; logistics management; logistics cost; Storage problem目錄第一章 緒論 . 11.1 研究背景及意義 . 11.2 研究概況 . 21.2.1 動(dòng)態(tài)規(guī)劃簡(jiǎn)介 . 21.2.2 物流管理簡(jiǎn)介 . 31.2.3 動(dòng)態(tài)規(guī)劃在物流管理上的應(yīng)用 . 51.3 國(guó)內(nèi)外研究

9、現(xiàn)狀 . 5第二章 動(dòng)態(tài)規(guī)劃的應(yīng)用研究 . 102.1 動(dòng)態(tài)規(guī)劃的基本理論 . 102.1.1 動(dòng)態(tài)規(guī)劃的介紹 . 102.1.2 多階段決策過(guò)程的數(shù)學(xué)描述 . 112.1.3 動(dòng)態(tài)規(guī)劃的基本概念 . 122.1.4 動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型 . 142.1.5 動(dòng)態(tài)規(guī)劃的四大要素及分類 . 162.2 動(dòng)態(tài)規(guī)劃模型的建立與求解 . 172.2.1動(dòng)態(tài)規(guī)劃模型的建立 . 172.2.2 動(dòng)態(tài)規(guī)劃求解的基本方法 . 202.2.3基本方程分段求解時(shí)的幾種常用算法 . 20第三章 物流管理概述 . 223.1 物流管理的發(fā)展概況 . 223.2物流管理的介紹 . 233.2.1 物流管理的主要內(nèi)容 .

10、233.2.2 物流管理的分類 . 243.2.3 物流管理的原則 . 263.2.4 物流管理的三個(gè)階段 . 273.2.5 核心. . 283.3 物流管理的目的和作用 . 293.3.1 物流管理的目的 . 293.3.2 物流管理的作用 . 293.4 現(xiàn)代物流管理的特征 . 31第四章 動(dòng)態(tài)規(guī)劃在物流管理中的應(yīng)用 . 324.1 資源分配問(wèn)題 . 324.1.1 決策變量取離散值的分配問(wèn)題 . 324.1.2 決策為連續(xù)變量的資源分配問(wèn)題 . 354.2 存貯控制問(wèn)題 . 394.3最短路線問(wèn)題 . 424.4背包問(wèn)題 . 45結(jié)論. . 48參考文獻(xiàn). . 50致謝. . 52 附

11、錄一 中文譯文. 附錄二 外文資料原文.（論文）動(dòng)態(tài)規(guī)劃在物流管理中的應(yīng)用研究第一章 緒論1.1 研究背景及意義1918年，英國(guó)猶尼利弗的哈姆勛爵成立了“即時(shí)送貨股份有限公司”，目的是在全國(guó)范圍內(nèi)把商品及時(shí)送到批發(fā)商、零售商和用戶手中，這事物流公司最早的雛形。隨著社會(huì)的不斷進(jìn)步和經(jīng)濟(jì)的斷發(fā)展，現(xiàn)代物流成為了集運(yùn)輸、搬運(yùn)、儲(chǔ)存、保管、包裝、裝卸、流通加工和物流信息處理等基本功能為一體，由供應(yīng)地流向接受地以滿足社會(huì)需求的一種經(jīng)濟(jì)活動(dòng)。其核心目標(biāo)是在物流全過(guò)程中以最小的綜合成本來(lái)滿足顧客的需求。國(guó)際上普遍把物流稱為“降低成本的最后邊界”，排在降低原材料消耗、并且提高勞動(dòng)生產(chǎn)率之后的“第三利潤(rùn)源泉”，

12、是企業(yè)整體利潤(rùn)的最大源泉。所以，各國(guó)的企業(yè)才越來(lái)越重視物流，逐漸把企業(yè)的物流管理當(dāng)作一個(gè)戰(zhàn)略新視角，變?yōu)楝F(xiàn)代企業(yè)管理戰(zhàn)略中的一個(gè)新的著眼點(diǎn)，通過(guò)制定各種物流戰(zhàn)略，從物流這一巨大的利潤(rùn)空間去尋找出路，以增強(qiáng)企業(yè)的競(jìng)爭(zhēng)力。而好的物流管理方法成為企業(yè)生產(chǎn)研究的重中之重。我國(guó)把物流作為一個(gè)學(xué)科來(lái)研究, 并與國(guó)外物流界發(fā)生是近二十年才開(kāi)始的。與一些發(fā)達(dá)國(guó)家相比，我國(guó)物流業(yè)從各方面都要一些差距的。就目前來(lái)說(shuō)我國(guó)的物流前景大好，據(jù)調(diào)查我國(guó)物流成本占GDP 的比重逐年下降，從這個(gè)角度來(lái)講，當(dāng)下降速度超過(guò)GDP 速度時(shí)，物流行業(yè)應(yīng)該是創(chuàng)造的產(chǎn)值越來(lái)越低的一個(gè)行業(yè)。但這并不意味著物流行業(yè)沒(méi)有前景。物流成本占GDP

13、 比重的下降除了產(chǎn)業(yè)結(jié)構(gòu)調(diào)整（第三產(chǎn)業(yè)物流需求較低）因素之外，物流管理水平的提高是一個(gè)主要因素。目前我國(guó)物流成本占GDP 比重為20%左右，美國(guó)為10%左右，拋除產(chǎn)業(yè)結(jié)構(gòu)因素，我國(guó)的比重比美國(guó)的比重應(yīng)該高5%左右。也就是說(shuō)隨著越來(lái)越多的物流企業(yè)掌握先進(jìn)的物流技術(shù)和管理水平之后，我國(guó)物流成本占GDP 的比重將會(huì)持續(xù)下降。那這些掌握先進(jìn)物流管理水平的企業(yè)將是我國(guó)物流行業(yè)的勝利者。本文所要論述的中心就是應(yīng)用最簡(jiǎn)單的方法來(lái)進(jìn)行物流管理活動(dòng)。61.2研究概況1.2.1動(dòng)態(tài)規(guī)劃簡(jiǎn)介動(dòng)態(tài)規(guī)劃(dynamic programming 是運(yùn)籌學(xué)的一個(gè)分支，是求解決多階段決策過(guò)程(decision process

14、最優(yōu)化問(wèn)題的一種數(shù)學(xué)方法。20世紀(jì)50年代初美國(guó)數(shù)學(xué)家R.E.bellman 等人在研究多階段決策過(guò)程(multistep decision process的優(yōu)化問(wèn)題時(shí)，針對(duì)多階段決策問(wèn)題的特點(diǎn)，提出了著名的最優(yōu)化原理(principle of optimality，把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類過(guò)程優(yōu)化問(wèn)題的新方法。動(dòng)態(tài)規(guī)劃的最優(yōu)化原理：作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)，無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)前面所形成的狀態(tài)而言，余下的諸決策必構(gòu)成最優(yōu)策略。利用這個(gè)原理，可以把多階段決策問(wèn)題的求解過(guò)程看成一個(gè)連續(xù)的遞推過(guò)程，由后向前逐步推算。在求

15、解時(shí)，各狀態(tài)前面的狀態(tài)和決策，相對(duì)其后面的子問(wèn)題，相當(dāng)于初始條件，并不影響后面過(guò)程的最優(yōu)策略。所以，動(dòng)態(tài)規(guī)劃方法解題的基本思路，是將一個(gè)多階段決策問(wèn)題轉(zhuǎn)化為依次求解多個(gè)單階段的決策問(wèn)題，從而簡(jiǎn)化計(jì)算過(guò)程。這種轉(zhuǎn)化的實(shí)現(xiàn)是從終點(diǎn)出發(fā)一步步反推，即采用逆序算法。成功的解決了生產(chǎn)管理、工程技術(shù)等方面的許多實(shí)際問(wèn)題。1957年，R Bellman發(fā)表了該分支領(lǐng)域的第一本專著動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃是現(xiàn)代企業(yè)管理中的一種重要決策方法，可用于解決最優(yōu)路徑問(wèn)題、資源分配問(wèn)題、生產(chǎn)計(jì)劃與庫(kù)存、投資、裝載、排序等問(wèn)題及生產(chǎn)過(guò)程的最優(yōu)控制等。由于它獨(dú)特的解題思路，在處理某些優(yōu)化問(wèn)題是，比線性規(guī)劃和非線性規(guī)劃方法更有效。

16、任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動(dòng)態(tài)規(guī)劃也并不是萬(wàn)能的。適用動(dòng)態(tài)規(guī)劃的問(wèn)題必須滿足最優(yōu)化原理和無(wú)后效性。(1 最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過(guò)去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡(jiǎn)而言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。一個(gè)問(wèn)題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。(2 無(wú)后效性我們要求狀態(tài)具有下面的性質(zhì)：如果給定某一階段的狀態(tài)，則在這一階段以后過(guò)程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時(shí)，整個(gè)過(guò)程也就確定了。也就是說(shuō)，過(guò)程的每一次實(shí)現(xiàn)可以用一個(gè)狀態(tài)序列表示，在前面的

17、例子中每階段的狀態(tài)是該線路的始點(diǎn)，確定了這些點(diǎn)的序列，整個(gè)線路也就完全確定。從某一階段以后的線路開(kāi)始，當(dāng)這段始點(diǎn)給定時(shí)，不受以前線路（所通過(guò)的點(diǎn)）的影響。狀態(tài)的這個(gè)性質(zhì)意味著過(guò)程的歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它的未來(lái)的發(fā)展。換句話說(shuō)，每個(gè)狀態(tài)都是過(guò)去歷史的一個(gè)完整總結(jié)。這就是無(wú)后向性，又稱為無(wú)后效性。 圖1-1 無(wú)后效性(3 子問(wèn)題的重疊性動(dòng)態(tài)規(guī)劃將原來(lái)具有指數(shù)級(jí)復(fù)雜度的搜索算法改進(jìn)成了具有多項(xiàng)式時(shí)間的算法。其中的關(guān)鍵在于解決冗余，這是動(dòng)態(tài)規(guī)劃算法的根本目的。動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過(guò)程中，不得不存儲(chǔ)產(chǎn)生過(guò)程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。21.2.

18、2 物流管理簡(jiǎn)介物流管理（Logistics Management）是指在社會(huì)在生產(chǎn)過(guò)程中，根據(jù)物質(zhì)資料實(shí)體流動(dòng)的規(guī)律，應(yīng)用管理的基本原理和科學(xué)方法，對(duì)物流活動(dòng)進(jìn)行計(jì)劃、組織、指揮、協(xié)調(diào)、控制和監(jiān)督，使各項(xiàng)物流活動(dòng)實(shí)現(xiàn)最佳的協(xié)調(diào)與配合，以降低物流成本，提高物流效率和經(jīng)濟(jì)效益。物流體系的四個(gè)核心是：采購(gòu)、倉(cāng)儲(chǔ)、配送、運(yùn)輸?，F(xiàn)代物流管理是建立在系統(tǒng)論、信息論和控制論的基礎(chǔ)上的。(1 物流管理的基本內(nèi)容主要分六個(gè)：物流作業(yè)管理：物流作業(yè)管理強(qiáng)調(diào)低成本、高質(zhì)量和快速響應(yīng)。企業(yè)利用作業(yè)成本法測(cè)算與物流活動(dòng)相關(guān)的費(fèi)用，使得物流成本明晰化。然后，在作業(yè)成本法的基礎(chǔ)上，應(yīng)用作業(yè)管理思想來(lái)進(jìn)行物流管理，深入開(kāi)展

19、企業(yè)作業(yè)的增值性分析和因果關(guān)系分析。物流戰(zhàn)略管理：物流戰(zhàn)略管理是指通過(guò)物流戰(zhàn)略設(shè)計(jì)、戰(zhàn)略實(shí)施、戰(zhàn)略評(píng)價(jià)與控制等環(huán)節(jié)，調(diào)節(jié)物流資源、組織結(jié)構(gòu)等最終實(shí)現(xiàn)物流系統(tǒng)宗旨和戰(zhàn)略目標(biāo)的一系列動(dòng)態(tài)過(guò)程的總和。物流成本管理：物流成本管理（Logisticscostcontrol ）是對(duì)物流相關(guān)費(fèi)用進(jìn)行的計(jì)劃、協(xié)調(diào)與控制。物流成本管理是通過(guò)成本去管理物流，即管理的對(duì)象是物流而不是成本。物流成本管理可以說(shuō)是以成本為手段的物流管理方法。物流服務(wù)管理：物流企業(yè)要取得競(jìng)爭(zhēng)優(yōu)勢(shì)，向集約化發(fā)展是一條必由之路。物流的配送中心不僅只提供倉(cāng)儲(chǔ)和運(yùn)輸服務(wù)，還必須開(kāi)展配貨、配送和各種提高附加值的流通加工服務(wù)項(xiàng)目，也可按客戶的的需要提

20、供其他個(gè)性化服務(wù)。物流企業(yè)一方面要與貨主企業(yè)結(jié)成戰(zhàn)略伙伴關(guān)系，以保證得到長(zhǎng)期的貨源；一方面要與貨主企業(yè)結(jié)成戰(zhàn)略伙伴關(guān)系，以保證得到長(zhǎng)期的貨源；一方面要有助于貨主企業(yè)的產(chǎn)品迅速進(jìn)入市場(chǎng)，提高競(jìng)爭(zhēng)力，從而實(shí)現(xiàn)互利共贏。因此，對(duì)于物流企業(yè)而言，服務(wù)質(zhì)量和服務(wù)水平正逐步成為比價(jià)格更為重要的選擇因素。7物流組織與人力資源管理：對(duì)專門從事物流經(jīng)營(yíng)和管理活動(dòng)的組織和個(gè)人進(jìn)行有效的管理，以提高企業(yè)的工作效率提升企業(yè)的經(jīng)濟(jì)效益。供應(yīng)鏈管理：圍繞核心企業(yè)，通過(guò)對(duì)信息流，物流, 資金流的控制，從采購(gòu)原材料開(kāi)始，制成中間產(chǎn)品及最終產(chǎn)品，最后由銷售網(wǎng)絡(luò)把產(chǎn)品送到消費(fèi)者手中。它是將供應(yīng)商, 制造商，分銷商，零售商, 直到

21、最終用戶連成一個(gè)整體的功能網(wǎng)鏈模式來(lái)進(jìn)行計(jì)劃、協(xié)調(diào)、操作、控制和優(yōu)化的各種活動(dòng)和過(guò)程。(2 物流管理的原則主要有三點(diǎn):物流管理的總原則物流合理化物流管理的具體原則很多，但最根本的指導(dǎo)原則是保證物流合理化的實(shí)現(xiàn)。所謂物流合理化，就是對(duì)物流設(shè)備配置和物流活動(dòng)組織進(jìn)行調(diào)整改進(jìn)，實(shí)現(xiàn)物流系統(tǒng)整體優(yōu)化的過(guò)程。它具體表現(xiàn)在兼顧成本與服務(wù)上，即以盡可能低的物流成本，獲得可以接受的物流服務(wù)，或以可以接受的物流成本達(dá)到盡可能高的服務(wù)水平。物流合理化的基本思想物流活動(dòng)各種成本之間經(jīng)常存在著此消彼長(zhǎng)的關(guān)系，物流合理化的一個(gè)基本的思想就是“均衡”的思想，從物流總成本的角度權(quán)衡得失。不求極限，但求均衡，均衡早就合理。物

22、流管理面臨的新挑戰(zhàn)近年來(lái)，很多先進(jìn)的信息技術(shù)的出現(xiàn)，極大地推動(dòng)了物流行業(yè)的巨變。我們不能再以傳統(tǒng)的觀念來(lái)認(rèn)識(shí)信息時(shí)代的物流，物流也不再是物流功能的簡(jiǎn)單組合運(yùn)作，它現(xiàn)在已是一個(gè)網(wǎng)的概念。加強(qiáng)連通物流結(jié)點(diǎn)的效率，加強(qiáng)系統(tǒng)的管理效率已成為整個(gè)物流產(chǎn)業(yè)面臨的關(guān)鍵問(wèn)題。151.2.3動(dòng)態(tài)規(guī)劃在物流管理上的應(yīng)用動(dòng)態(tài)規(guī)劃說(shuō)到底是一種特殊的決策序列，它使得一個(gè)問(wèn)題可以逐步推導(dǎo)到最優(yōu)解，準(zhǔn)確而又快捷的解決繁雜的物流管理問(wèn)題。因此在物流管理的中能多次的使用它的理論和計(jì)算方法。該篇論文就對(duì)物流管理中常見(jiàn)的資源分配問(wèn)題，存貯控制問(wèn)題，運(yùn)輸最短路問(wèn)題和背包問(wèn)題用動(dòng)態(tài)規(guī)劃方法分別予以詳細(xì)的計(jì)算和分析。1.3 國(guó)內(nèi)外研究現(xiàn)

23、狀物流概念從上個(gè)世紀(jì) 70年代末引入我國(guó)，90年代中期開(kāi)始出現(xiàn)“物流熱”。進(jìn)入新世紀(jì)以來(lái)，也就是“十五”時(shí)期，我國(guó)現(xiàn)代物流跨越“起步期”，進(jìn)入理性、務(wù)實(shí)、持續(xù)、快速發(fā)展的新階段。現(xiàn)代物流的產(chǎn)業(yè)地位得以確立。今年3月，全國(guó)十屆人大四次會(huì)議通過(guò)的國(guó)民經(jīng)濟(jì)和社會(huì)發(fā)展第十一個(gè)五年規(guī)劃綱要，在第四篇“加快發(fā)展服務(wù)業(yè)” ,第十六章“拓展生產(chǎn)性服務(wù)業(yè)”里面，單列一節(jié)“大力發(fā)展現(xiàn)代物流業(yè)”。這在我國(guó)國(guó)民經(jīng)濟(jì)和社會(huì)發(fā)展規(guī)劃的歷史上也是第一次，標(biāo)志著現(xiàn)代物流的產(chǎn)業(yè)地位在國(guó)家規(guī)劃層面得以確立。物流產(chǎn)業(yè)平穩(wěn)快速發(fā)展。據(jù)國(guó)家發(fā)改委、國(guó)家統(tǒng)計(jì)局和中國(guó)物流與采購(gòu)聯(lián)合會(huì)統(tǒng)計(jì)：“十五”時(shí)期，我國(guó)社會(huì)物流總額扣除價(jià)格因素，年均增

24、長(zhǎng) 15%左右，明顯快于“十五”時(shí)期 GDP增長(zhǎng)的水平；我國(guó)社會(huì)物流總費(fèi)用與 GDP的比率由 2000年的 19.4%下降到 2005年的 18.6%，等于節(jié)約社會(huì)物流費(fèi)用合計(jì) 1090億元；物流業(yè)增加值 2005年超過(guò) 1.2萬(wàn)億元，同比增長(zhǎng) 12.7%，占當(dāng)年服務(wù)業(yè)增加值的 16.6%。今年上半年，我國(guó)社會(huì)物流總額繼續(xù)保持快速增長(zhǎng)，達(dá)到 26.8萬(wàn)億元，按可比價(jià)格計(jì)算同比增長(zhǎng) 15.3%；社會(huì)物流總費(fèi)用與 GDP的比率繼續(xù)下降，由去年全年的 18.6%，下降至 18.4 %，下降 0.2個(gè)百分點(diǎn)。物流企業(yè)群體迅速成長(zhǎng)。“十五”時(shí)期，傳統(tǒng)大型國(guó)有物流企業(yè)改制重組，加快向現(xiàn)代物流轉(zhuǎn)型，民營(yíng)物流

25、企業(yè)瞄準(zhǔn)市場(chǎng)需求，發(fā)展勢(shì)頭迅猛，外資物流企業(yè)“搶灘”中國(guó)物流市場(chǎng)，形成了“三足鼎立”的物流企業(yè)群體。制造業(yè)和流通業(yè)物流運(yùn)作模式發(fā)生了轉(zhuǎn)變。許多制造企業(yè)運(yùn)用現(xiàn)代物流理念，實(shí)施流程再造，分離外包物流業(yè)務(wù)，出現(xiàn)了銷售物流向生產(chǎn)物流、供應(yīng)物流延伸的趨勢(shì)，一體化運(yùn)作、供應(yīng)鏈管理初現(xiàn)端倪。流通企業(yè)不斷強(qiáng)化自身物流能力，大力發(fā)展連鎖經(jīng)營(yíng)、物流配送和電子商務(wù)等現(xiàn)代營(yíng)銷方式，促進(jìn)了商流、物流、信息流和資金流的融合，極大地改變了傳統(tǒng)流通模式。物流基礎(chǔ)設(shè)施和信息化建設(shè)進(jìn)度加快?！笆濉逼陂g，我國(guó)物流相關(guān)行業(yè)固定資產(chǎn)投資年均增速達(dá) 19.7%，比“九五”時(shí)期加快 4.2個(gè)百分點(diǎn)。物流園區(qū)（基地、中心）在“十五”期間起

26、步建設(shè)，物流信息化取得突出成就，為物流資源整合和一體化運(yùn)作提供了必不可少的基礎(chǔ)條件。今年上半年，國(guó)內(nèi)物流相關(guān)行業(yè)固定資產(chǎn)投資額為 4322億元，同比增長(zhǎng) 20.7%。物流行業(yè)基礎(chǔ)性工作已有成效。國(guó)家標(biāo)準(zhǔn)化管理委員會(huì)相繼批準(zhǔn)成立了跨部門、跨行業(yè)的全國(guó)物流標(biāo)準(zhǔn)化技術(shù)委員會(huì)和全國(guó)物流信息管理標(biāo)準(zhǔn)化技術(shù)委員會(huì)，全國(guó)物流標(biāo)準(zhǔn) 2005年 -2010年發(fā)展規(guī)劃正在組織實(shí)施，物流企業(yè)分類與評(píng)估指標(biāo)國(guó)家標(biāo)準(zhǔn)正在貫徹。國(guó)家發(fā)改委和國(guó)家統(tǒng)計(jì)局聯(lián)合制定了我國(guó)社會(huì)物流統(tǒng)計(jì)核算制度，監(jiān)測(cè)分析現(xiàn)代物流業(yè)發(fā)展的相關(guān)數(shù)據(jù)開(kāi)始發(fā)布，覆蓋全國(guó)的物流統(tǒng)計(jì)工作體系正在形成。國(guó)家有關(guān)部門和企業(yè)、院校、行業(yè)協(xié)會(huì)為物流人才的培養(yǎng)教育做了大

27、量工作，我國(guó)物流人才嚴(yán)重短缺的局面已經(jīng)有所緩解。區(qū)域物流出現(xiàn)新的局面。我國(guó)的現(xiàn)代物流首先從沿海發(fā)達(dá)地區(qū)起步，現(xiàn)已形成珠三角、長(zhǎng)三角和環(huán)渤海地區(qū)等現(xiàn)代物流快速發(fā)展的區(qū)域。去年以來(lái)，泛珠三角地區(qū)物流合作、東北三省一區(qū)物流規(guī)劃和圍繞中部崛起的物流業(yè)發(fā)展引起關(guān)注。特別是黨中央、國(guó)務(wù)院提出天津?yàn)I海新區(qū)開(kāi)發(fā)開(kāi)放，建設(shè)北方國(guó)際物流中心，將是中國(guó)新時(shí)期、新階段區(qū)域經(jīng)濟(jì)發(fā)展的重大舉措。物流發(fā)展的體制和政策環(huán)境有了較大改善。這兩年，隨著國(guó)家發(fā)改委等九部委文件的印發(fā)，全國(guó)現(xiàn)代物流工作部際聯(lián)席會(huì)議的建立和首次全國(guó)現(xiàn)代物流工作會(huì)議召開(kāi)，聯(lián)席會(huì)議各成員單位做了大量工作，推進(jìn)現(xiàn)代物流業(yè)發(fā)展的合力正在形成。各省市自治區(qū)明確了

28、現(xiàn)代物流工作牽頭部門，不少地方制定規(guī)劃，出臺(tái)政策，物流發(fā)展的體制和政策環(huán)境有了較大改善。從以上情況看，我國(guó)物流發(fā)展很快、很好。但是，與發(fā)達(dá)國(guó)家相比，與我國(guó)經(jīng)濟(jì)發(fā)展需要相比，差距仍然不小。我國(guó)全社會(huì)物流費(fèi)用與 GDP的比率，雖然有所下降，但仍比發(fā)達(dá)國(guó)家高出一倍左右。體制的制約、設(shè)施的落后、企業(yè)集中度不夠、效益和效率不高、服務(wù)較差、地區(qū)和行業(yè)發(fā)展不平衡等問(wèn)題嚴(yán)重存在。我國(guó)現(xiàn)代物流剛剛進(jìn)入發(fā)展期，潛力巨大，任重道遠(yuǎn)。國(guó)民經(jīng)濟(jì)持續(xù)快速健康發(fā)展，對(duì)現(xiàn)代物流業(yè)提出了新的更高要求。我們要建立快捷、高效、安全、方便并具有國(guó)際競(jìng)爭(zhēng)力的現(xiàn)代物流服務(wù)體系，提高物流的社會(huì)化、專業(yè)化和現(xiàn)代化水平，社會(huì)物流費(fèi)用與 GDP

29、的比率應(yīng)該繼續(xù)有所降低?！笆晃濉币?guī)劃綱要提出的重點(diǎn)任務(wù)是：推廣現(xiàn)代物流管理技術(shù)，促進(jìn)企業(yè)內(nèi)部物流社會(huì)化；培育專業(yè)化物流企業(yè)，積極發(fā)展第三方物流；建立物流標(biāo)準(zhǔn)化體系，加強(qiáng)物流新技術(shù)開(kāi)發(fā)利用，推進(jìn)物流信息化；加強(qiáng)物流基礎(chǔ)設(shè)施整合，建設(shè)大型物流樞紐，發(fā)展區(qū)域性物流中心。5隨著中國(guó)社會(huì)主義市場(chǎng)經(jīng)濟(jì)體系建立、世界經(jīng)濟(jì)一體化進(jìn)程的加快和科學(xué)技術(shù)的飛速發(fā)展，物流產(chǎn)業(yè)作為國(guó)民經(jīng)濟(jì)中的一個(gè)新興的產(chǎn)業(yè)部門，將成為本世紀(jì)重要產(chǎn)業(yè)和國(guó)民經(jīng)濟(jì)新的增長(zhǎng)點(diǎn)。目前，從中央到地方以及許多市場(chǎng)意識(shí)敏銳的企業(yè)，已把物流作為提高市場(chǎng)競(jìng)爭(zhēng)力和提升企業(yè)核心競(jìng)爭(zhēng)力的重要手段，把現(xiàn)代物流理念、先進(jìn)的物流技術(shù)和現(xiàn)代物流模式引入國(guó)家、地方經(jīng)濟(jì)

30、建設(shè)和企業(yè)經(jīng)營(yíng)和管理之中。但是我國(guó)的物流管理仍十分滯后，阻礙了經(jīng)濟(jì)的發(fā)展和經(jīng)濟(jì)效益的提高。隨著社會(huì)、經(jīng)濟(jì)、技術(shù)的高速發(fā)展，各種基礎(chǔ)設(shè)施的不斷完善, 全球經(jīng)濟(jì)一體化趨勢(shì)和市場(chǎng)競(jìng)爭(zhēng)程度日益增加，對(duì)物流提出了更高的要求，賦予了新的內(nèi)涵?，F(xiàn)代物流指的是將信息、運(yùn)輸、倉(cāng)儲(chǔ)、庫(kù)存、裝卸搬運(yùn)以及包裝等物流活動(dòng)綜合起來(lái)的一種新型的集成式管理，即在傳統(tǒng)物流的基礎(chǔ)上，引入高科技手段，運(yùn)用計(jì)算機(jī)進(jìn)行信息聯(lián)網(wǎng)，并對(duì)物流信息進(jìn)行科學(xué)管理，從而使物流速度加快，準(zhǔn)確率提高，庫(kù)存減少，成本降低，提高質(zhì)量，為顧客提供最好的服務(wù)?，F(xiàn)在世界做專業(yè)物流比較著名的公司有：美國(guó)聯(lián)合包裹（UPS ）荷蘭郵政（TNT ）德國(guó)郵政（DHL ）

31、美國(guó)聯(lián)邦快遞（FEDEX ）為什么現(xiàn)代物流業(yè)的前景看好呢？據(jù)中國(guó)物流與采購(gòu)聯(lián)合會(huì)統(tǒng)計(jì)，全國(guó)已有30多個(gè)省與城市作出了物流業(yè)發(fā)展規(guī)劃并出臺(tái)了必要的產(chǎn)業(yè)政策，國(guó)家發(fā)改委正在編寫(xiě)中國(guó)物流業(yè)發(fā)展大綱，并提出了物流業(yè)發(fā)展的產(chǎn)業(yè)政策初步意見(jiàn)。由于有政策的扶持，物流企業(yè)與企業(yè)物流開(kāi)始步入快車道。到現(xiàn)在為止，中國(guó)已經(jīng)形成公有制物流企業(yè)、民營(yíng)物流企業(yè)與外資（含中外合資）物流企業(yè)三足鼎立的局面，這種趨勢(shì)從03年開(kāi)始，并在明顯加速。在5至10年內(nèi)，將形成10個(gè)左右全國(guó)公認(rèn)的中國(guó)物流領(lǐng)軍企業(yè)，并走向國(guó)際。80%企業(yè)物流已開(kāi)始部分外包，外包的比例與外包的領(lǐng)域?qū)⒅鸩綌U(kuò)大，涌現(xiàn)出包括海爾物流、寶供物流、招商局物流在內(nèi)的優(yōu)秀

32、物流企業(yè)。物流總值的高速增長(zhǎng)，表明中國(guó)經(jīng)濟(jì)增長(zhǎng)對(duì)物流的需求越來(lái)越大，經(jīng)濟(jì)發(fā)展對(duì)物流的依賴程度也越來(lái)越高。全球最大的貨運(yùn)公司之一美國(guó)萬(wàn)絡(luò)環(huán)球公司副總裁卡扎瑞預(yù)測(cè)，“中國(guó)物流業(yè)預(yù)計(jì)未來(lái)10年內(nèi)相關(guān)服務(wù)收入將保持20%的年增長(zhǎng)速度”。北京科技大學(xué)教授、物流研究所所長(zhǎng)吳清一認(rèn)為，中國(guó)現(xiàn)代物流發(fā)展尚處于起步階段，配送體系不健全，但隨著電子商務(wù)的普及，物流市場(chǎng)潛力和發(fā)展前景十分廣闊，中國(guó)的現(xiàn)代物流業(yè)發(fā)展既有難得機(jī)遇，也有嚴(yán)峻挑戰(zhàn)。機(jī)遇稍縱即逝，挑戰(zhàn)不請(qǐng)自來(lái)。我們要抓住機(jī)遇，乘勢(shì)而上，大力發(fā)展現(xiàn)代物流業(yè)。美國(guó)和日本是物流業(yè)發(fā)展的領(lǐng)頭羊，歐洲的現(xiàn)代物流起步較晚，但是政府和企業(yè)也相當(dāng)重視，所以也得到了較大發(fā)展。

33、美國(guó)的經(jīng)濟(jì)模式把信息通訊領(lǐng)域里的高新技術(shù)有機(jī)地融入到社會(huì)中，所以能率先實(shí)現(xiàn)高度的物流信息化和集成化。美國(guó)企業(yè)的利潤(rùn)和投資收益能夠持續(xù)增加的原因是美國(guó)的生產(chǎn)流通率極高，這就誘發(fā)了新的投資，即物流業(yè)投資，這種投資提高了勞動(dòng)生產(chǎn)率，是一種良性循環(huán)。融合了信息技術(shù)和交通運(yùn)輸?shù)默F(xiàn)代物流對(duì)世界經(jīng)濟(jì)有著積極深遠(yuǎn)的影響。14物流業(yè)在電子商務(wù)的推動(dòng)下也從傳統(tǒng)物流轉(zhuǎn)型為現(xiàn)代物流，這種趨勢(shì)勢(shì)不可擋。在國(guó)際上，網(wǎng)絡(luò)規(guī)劃與優(yōu)化、自動(dòng)、智能化的關(guān)鍵技術(shù)等科技的進(jìn)步明顯推動(dòng)了物流業(yè)發(fā)展，大大降低了物流成本，并且隨著科學(xué)技術(shù)的不斷發(fā)展也在不斷創(chuàng)新。各大物流商激烈競(jìng)爭(zhēng)，導(dǎo)致了物流發(fā)展主要分四個(gè)主要方向：物流運(yùn)作管理信息化，物流

34、運(yùn)作流程智能化，物流技術(shù)裝備自動(dòng)化和多種技術(shù)集成化。從發(fā)達(dá)國(guó)家的物流現(xiàn)狀來(lái)看，國(guó)外物流管理已進(jìn)入較為成熟的階段，發(fā)展主要是物流內(nèi)涵的拓展、過(guò)程的延伸、覆蓋面的擴(kuò)大以及物流管理的日益專業(yè)化、信息化和標(biāo)準(zhǔn)化。1(1 物流服務(wù)的拓展物流服務(wù)已經(jīng)逐步將加工、保稅、倉(cāng)儲(chǔ)、金融、保險(xiǎn)乃至報(bào)關(guān)、通關(guān)、商檢、衛(wèi)檢、動(dòng)植檢、中轉(zhuǎn)等業(yè)務(wù)統(tǒng)進(jìn)來(lái)，把整個(gè)商貿(mào)流通過(guò)程作為個(gè)完整的領(lǐng)域來(lái)進(jìn)行通盤考慮和經(jīng)營(yíng)。近年來(lái)，由于信息技術(shù)的發(fā)展和比較成本優(yōu)勢(shì)的驅(qū)動(dòng)，產(chǎn)品異地加工、裝配、包裝、標(biāo)志、分撥、配送、銷售等增值服務(wù)，也逐漸涵蓋進(jìn)來(lái)。(2 物流服務(wù)過(guò)程的延伸物流服務(wù)的過(guò)程經(jīng)歷了“港口到港口”、“門到門”和“貨架到貨架”等幾個(gè)階

35、段，其過(guò)程在逐步延伸。由于生產(chǎn)企業(yè)需要實(shí)行“即時(shí)供貨”和“零庫(kù)存”，以加速資金和貨物的周轉(zhuǎn)利用，物流業(yè)將生產(chǎn)以前的計(jì)劃、供應(yīng)也逐漸包括在自己的服務(wù)范圍之內(nèi)，使服務(wù)過(guò)程向前延伸。(3 物流服務(wù)的覆蓋面不斷擴(kuò)大科學(xué)技術(shù)的日新月異和交通工具、信息系統(tǒng)的不斷創(chuàng)新，使地球變得越來(lái)越小，也使物流業(yè)相應(yīng)地?cái)U(kuò)大了自己的覆蓋面。近年來(lái)，跨國(guó)家、跨地區(qū)、跨城市的物流服務(wù)都有了較快發(fā)展。(4 第三方物流作用日趨顯著“第三方物流”來(lái)是指為發(fā)貨人(第一方 和收貨人(第二方 提供專業(yè)物流服務(wù)的第三方企業(yè)。物流服務(wù)公司在貨物的實(shí)際移動(dòng)鏈中并不是一個(gè)獨(dú)立的參與者，而是代表發(fā)貨人或收貨人來(lái)執(zhí)行。之所以強(qiáng)調(diào)發(fā)展第三方，主要是實(shí)現(xiàn)

36、物流運(yùn)營(yíng)的專業(yè)化、科學(xué)化，并使物流企業(yè)與物流需求者之間建立更緊密、有效的聯(lián)系。(5 電子物流發(fā)展基于互聯(lián)網(wǎng)的電子商務(wù)迅速發(fā)展，使電子物流快速發(fā)展。企業(yè)或個(gè)人通過(guò)電子網(wǎng)絡(luò)與外界構(gòu)通，實(shí)現(xiàn)網(wǎng)上購(gòu)物，這種網(wǎng)上直通的方式使企業(yè)能迅速、準(zhǔn)確、全面的了解需求信息，進(jìn)步實(shí)現(xiàn)最優(yōu)的生產(chǎn)模式和物流業(yè)務(wù)。這種可在線跟蹤貨物、在線規(guī)劃物流線路、在線實(shí)施物流調(diào)度及貨運(yùn)檢查的電子物流，是21世紀(jì)物流的發(fā)展方向。第二章動(dòng)態(tài)規(guī)劃的應(yīng)用研究2.1 動(dòng)態(tài)規(guī)劃的基本理論2.1.1 動(dòng)態(tài)規(guī)劃的介紹規(guī)劃問(wèn)題的最終目的就是確定各決策變量的取值，以使目標(biāo)函數(shù)達(dá)到極大或極小。在線性規(guī)劃和非線性規(guī)劃中，決策變量都是以集合的形式被一次性處理的

37、；然而，有時(shí)我們也會(huì)面對(duì)決策變量需分期、分批處理的多階段決策問(wèn)題。所謂多階段決策問(wèn)題是指這樣一類活動(dòng)過(guò)程：它可以分解為若干個(gè)互相聯(lián)系的階段，在每一階段分別對(duì)應(yīng)著一組可供選取的決策集合；即構(gòu)成過(guò)程的每個(gè)階段都需要進(jìn)行一次決策的決策問(wèn)題。將各個(gè)階段的決策綜合起來(lái)構(gòu)成一個(gè)決策序列，稱為一個(gè)策略。顯然，由于各個(gè)階段選取的決策不同，對(duì)應(yīng)整個(gè)過(guò)程可以有一系列不同的策略。當(dāng)過(guò)程采取某個(gè)具體策略時(shí)，相應(yīng)可以得到一個(gè)確定的效果，采取不同的策略，就會(huì)得到不同的效果。多階段的決策問(wèn)題，就是要在所有可能采取的策略中選取一個(gè)最優(yōu)的策略，以便得到最佳的效果。動(dòng)態(tài)規(guī)劃（dynamic programming）同前面介紹過(guò)的

38、各種優(yōu)化方法不同，它不是一種算法，而是考察問(wèn)題的一種途徑。動(dòng)態(tài)規(guī)劃是一種求解多階段決策問(wèn)題的系統(tǒng)技術(shù)，可以說(shuō)它橫跨整個(gè)規(guī)劃領(lǐng)域（線性規(guī)劃和非線性規(guī)劃）。當(dāng)然，由于動(dòng)態(tài)規(guī)劃不是一種特定的算法，因而它不象線性規(guī)劃那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，動(dòng)態(tài)規(guī)劃必須對(duì)具體問(wèn)題進(jìn)行具體的分析處理。在多階段決策問(wèn)題中，有些問(wèn)題對(duì)階段的劃分具有明顯的時(shí)序性，動(dòng)態(tài)規(guī)劃的“動(dòng)態(tài)”二字也由此而得名。動(dòng)態(tài)規(guī)劃的主要?jiǎng)?chuàng)始人是美國(guó)數(shù)學(xué)家貝爾曼（Bellman ）。20世紀(jì)40年代末50年代初，當(dāng)時(shí)在蘭德公司（Rand Corporation）從事研究工作的貝爾曼首先提出了動(dòng)態(tài)規(guī)劃的概念。1957年貝爾曼發(fā)表了

39、數(shù)篇研究論文，并出版了他的第一部著作動(dòng)態(tài)規(guī)劃。該著作成為了當(dāng)時(shí)唯一的進(jìn)一步研究和應(yīng)用動(dòng)態(tài)規(guī)劃的理論源泉。1961年貝爾曼出版了他的第二部著作，并于1962年同杜瑞佛思（Dreyfus ）合作出版了第三部著作。在貝爾曼及其助手們致力于發(fā)展和推廣這一技術(shù)的同時(shí)，其他一些學(xué)者也對(duì)動(dòng)態(tài)規(guī)劃的發(fā)展做出了重大的貢獻(xiàn)，其中最值得一提的是愛(ài)爾思（Aris ）和梅特頓（Mitten ）。愛(ài)爾思先后于1961年和1964年出版了兩部關(guān)于動(dòng)態(tài)規(guī)劃的著作，并于1964年同尼母霍思爾（Nemhauser ）、威爾德（Wild ）一道創(chuàng)建了處理分枝、循環(huán)性多階段決策系統(tǒng)的一般性理論。梅特頓提出了許多對(duì)動(dòng)態(tài)規(guī)劃后來(lái)發(fā)展有著

40、重要意義的基礎(chǔ)性觀點(diǎn)，并且對(duì)明晰動(dòng)態(tài)規(guī)劃路徑的數(shù)學(xué)性質(zhì)做出了巨大的貢獻(xiàn)。動(dòng)態(tài)規(guī)劃在工程技術(shù)、經(jīng)濟(jì)管理等社會(huì)各個(gè)領(lǐng)域都有著廣泛的應(yīng)用，并且獲得了顯著的效果。在經(jīng)濟(jì)管理方面，動(dòng)態(tài)規(guī)劃可以用來(lái)解決最優(yōu)路徑問(wèn)題、資源分配問(wèn)題、生產(chǎn)調(diào)度問(wèn)題、庫(kù)存管理問(wèn)題、排序問(wèn)題、設(shè)備更新問(wèn)題以及生產(chǎn)過(guò)程最優(yōu)控制問(wèn)題等，是經(jīng)濟(jì)管理中一種重要的決策技術(shù)。許多規(guī)劃問(wèn)題用動(dòng)態(tài)規(guī)劃的方法來(lái)處理，常比線性規(guī)劃或非線性規(guī)劃更有效。特別是對(duì)于離散的問(wèn)題，由于解析數(shù)學(xué)無(wú)法發(fā)揮作用，動(dòng)態(tài)規(guī)劃便成為了一種非常有用的工具。動(dòng)態(tài)規(guī)劃可以按照決策過(guò)程的演變是否確定分為確定性動(dòng)態(tài)規(guī)劃和隨機(jī)性動(dòng)態(tài)規(guī)劃；也可以按照決策變量的取值是否連續(xù)分為連續(xù)性動(dòng)態(tài)

41、規(guī)劃和離散型動(dòng)態(tài)規(guī)劃。72.1.2 多階段決策過(guò)程的數(shù)學(xué)描述有這樣一類活動(dòng)過(guò)程，其整個(gè)過(guò)程可分為若干相互聯(lián)系的階段，每一階段都要作出相應(yīng)的決策，以使整個(gè)過(guò)程達(dá)到最佳的活動(dòng)效果。任何一個(gè)階段（stage ，即決策點(diǎn)）都是由輸入（input ）、決策（decision ）、狀態(tài)轉(zhuǎn)移律（transformation function）和輸出（output ）構(gòu)成的，如圖2-1（a ）所示。其中輸入和輸出也稱為狀態(tài)（state ），輸入稱為輸入狀態(tài)，輸出稱為輸出狀態(tài)。 圖2-1 多階段決策過(guò)程由于每一階段都有一個(gè)決策，所以每一階段都應(yīng)存在一個(gè)衡量決策效益大小的指標(biāo)函數(shù)，這一指標(biāo)函數(shù)稱為階段指標(biāo)函數(shù)，用

42、g n 表示。顯然g n 是狀態(tài)變量S n 和決策變量d n 的函數(shù)，即g n = r（S n ，d n ），如圖2-1（b ）所示。顯然，輸出是輸入和決策的函數(shù)，即：S n+1=f (S n ,d n 2-1式（2-1）即為狀態(tài)轉(zhuǎn)移律。在由N 個(gè)階段構(gòu)成的過(guò)程里，前一個(gè)階段的輸出即為后一個(gè)階段的輸入。2.1.3 動(dòng)態(tài)規(guī)劃的基本概念動(dòng)態(tài)規(guī)劃的數(shù)學(xué)描述離不開(kāi)它的一些基本概念與符號(hào)，因此有必要在介紹多階段決策過(guò)程的數(shù)學(xué)描述的基礎(chǔ)上，系統(tǒng)地介紹動(dòng)態(tài)規(guī)劃的一些基本概念。(1 階段（stage ）階段是過(guò)程中需要做出決策的決策點(diǎn)。描述階段的變量稱為階段變量，常用k 來(lái)表示。階段的劃分一般是根據(jù)時(shí)間和空間

43、的自然特征來(lái)進(jìn)行的，但要便于將問(wèn)題的過(guò)程轉(zhuǎn)化為多階段決策的過(guò)程。對(duì)于具有N 個(gè)階段的決策過(guò)程，其階段變量k 1，2，N 。(2 狀態(tài)（state ）狀態(tài)表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件，它描述了研究問(wèn)題過(guò)程的狀況。狀態(tài)既反映前面各階段系列決策的結(jié)局，又是本階段決策的一個(gè)出發(fā)點(diǎn)和依據(jù)；它是各階段信息的傳遞點(diǎn)和結(jié)合點(diǎn)。各階段的狀態(tài)通常用狀態(tài)變量S k 來(lái)加以描述。作為狀態(tài)應(yīng)具有這樣的性質(zhì)：如果某階段狀態(tài)給定后，則該階段以后過(guò)程的發(fā)展不受此階段以前各階段狀態(tài)的影響。換句話說(shuō)，過(guò)程的歷史只能通過(guò)當(dāng)前的狀態(tài)來(lái)影響未來(lái)，當(dāng)前的狀態(tài)是以往歷史的一個(gè)總結(jié)。這個(gè)性質(zhì)稱為無(wú)后效性（the future i

44、s independent of the past ）或健忘性（the process is forgetful）。(3 決策（decision ）決策是指決策者在所面臨的若干個(gè)方案中做出的選擇。決策變量d k 表示第k 階段的決策。決策變量d k 的取值會(huì)受到狀態(tài)S k 的某種限制，用D k （S k ）表示第k 階段狀態(tài)為S k 時(shí)決策變量允許的取值范圍，稱為允許決策集合，因而有d k （S k ） D k （S k ）。(4 狀態(tài)轉(zhuǎn)移律（transformation function）狀態(tài)轉(zhuǎn)移律是確定由一個(gè)狀態(tài)到另一狀態(tài)演變過(guò)程的方程，這種演變的對(duì)應(yīng)關(guān)系記為S k+1 = Tk （S k

45、 , dk ）。(5 策略（policy ）與子策略（sub-policy ）由所有階段決策所組成的一個(gè)決策序列稱為一個(gè)策略，具有N 個(gè)階段的動(dòng)態(tài)規(guī)劃問(wèn)題的策略可表示為：d 1(s1 ，d 2(S2,dN (S N 2-2從某一階段開(kāi)始到過(guò)程終點(diǎn)為止的一個(gè)決策子序列，稱為過(guò)程子策略或子策略。從第k 個(gè)階段起的一個(gè)子策略可表示為：d k (S k ,d k+1(S k+1 ,dN (S N 2-3(6 指標(biāo)函數(shù)指標(biāo)函數(shù)有階段指標(biāo)函數(shù)和過(guò)程指標(biāo)函數(shù)之分。階段指標(biāo)函數(shù)是對(duì)應(yīng)某一階段決策的效率度量，用g k = r（S k ，d k ）來(lái)表示；過(guò)程指標(biāo)函數(shù)是用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的數(shù)量指標(biāo)，是定義在全

46、過(guò)程（策略）或后續(xù)子過(guò)程（子策略）上的一個(gè)數(shù)量函數(shù)，從第k 個(gè)階段起的一個(gè)子策略所對(duì)應(yīng)的過(guò)程指標(biāo)函數(shù)常用G k,N 來(lái)表示，即：, , , , , , (11, N N k k k k N k d S d S d S R G += 2-4構(gòu)成動(dòng)態(tài)規(guī)劃的過(guò)程指標(biāo)函數(shù)，應(yīng)具有可分性并滿足遞推關(guān)系；即：N k k N k G g G , 1, += 2-5這里的表示某種運(yùn)算，最常見(jiàn)的運(yùn)算關(guān)系有如下二種：過(guò)程指標(biāo)函數(shù)是其所包含的各階段指標(biāo)函數(shù)的“和”，即：=Nk j j N k g G , 2-6于是N k k N k G g G , 1, += 2-7過(guò)程指標(biāo)函數(shù)是其所包含的各階段指標(biāo)函數(shù)的“積”，

47、即：=Nk j j N k g G , 2-8于是N k k N k G g G , 1, += 2-9(7 最優(yōu)指標(biāo)函數(shù)從第k 個(gè)階段起的最優(yōu)子策略所對(duì)應(yīng)的過(guò)程指標(biāo)函數(shù)稱為最優(yōu)指標(biāo)函數(shù)，可以用式（2-10）加以表示： (1N k k d k k g g g opt S f Nk =+ 2-10其中“opt ”是最優(yōu)化“optimization ”的縮寫(xiě)，可根據(jù)題意取最大“max ”或最小“min ”。在不同的問(wèn)題中，指標(biāo)函數(shù)的含義可能是不同的，它可能是距離、利潤(rùn)、成本、產(chǎn)量或資源量等。2.1.4 動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型除包括式（2-10）外，還包括階段的劃分、各階段的狀態(tài)變量和

48、決策變量的選取、允許決策集合和狀態(tài)轉(zhuǎn)移律的確定等。如何獲得最優(yōu)指標(biāo)函數(shù)呢？一個(gè)N 階段的決策過(guò)程，具有如下一些特性：剛好有N 個(gè)決策點(diǎn)；對(duì)階段k 而言，除了其所處的狀態(tài)k S 和所選擇的決策k d 外，再?zèng)]有任何其它因素影響決策的最優(yōu)性了；階段k 僅影響階段1+k 的決策，這一影響是通過(guò)1+k S 來(lái)實(shí)現(xiàn)的；貝爾曼（Bellman ）最優(yōu)化原理：在最優(yōu)策略的任意一階段上，無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)過(guò)去決策所形成的當(dāng)前狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)子策略。根據(jù)貝爾曼（Bellman ）最優(yōu)化原理，可以將式（2-2）表示為遞推最優(yōu)指標(biāo)函數(shù)關(guān)系式（2-11）或式（2-12）：( (111+=k

49、 k k d N k k d k k S f g opt g g g opt S f kN k 2-11( (111+=k k k d N k k d k k S f g opt g g g opt S f kN k 2-12利用式（2-11）和式（2-12）可表示出最后一個(gè)階段（第N 個(gè)階段，即k = N）的最優(yōu)指標(biāo)函數(shù)：( (11+=N N N d N N S f g opt S f N2-13( (11+=N N N d N N S f g opt S f N2-14其中 (11+N N S f 稱為邊界條件。一般情況下，第N 階段的輸出狀態(tài)1+N S 已經(jīng)不再影響本過(guò)程的策略，即式（2

50、-5）中的邊界條件0 (11=+N N S f ，式（2-6）中的邊界條件1 (11=+N N S f ；但當(dāng)問(wèn)題第N 階段的輸出狀態(tài)1+N S 對(duì)本過(guò)程的策略產(chǎn)生某種影響時(shí)，邊界條件 (11+N N S f 就要根據(jù)問(wèn)題的具體情況取適當(dāng)?shù)闹?，這一情況將在后續(xù)例題中加以反映。已知邊界條件 (11+N N S f ，利用式（2-3）或式（2-4）即可求得最后一個(gè)階段的最優(yōu)指標(biāo)函數(shù) (N N S f ；有了 (N N S f ，繼續(xù)利用式（2-3）或式（2-4）即可求得最后兩個(gè)階段的最優(yōu)指標(biāo)函數(shù) (11-N N S f ；有了 (11-N N S f ，進(jìn)一步又可以求得最后三個(gè)階段的最優(yōu)指標(biāo)函數(shù)

51、(22-N N S f ；反復(fù)遞推下去，最終即可求得全過(guò)程N(yùn) 個(gè)階段的最優(yōu)指標(biāo)函數(shù) (11S f ，從而使問(wèn)題得到解決。由于上述最優(yōu)指標(biāo)函數(shù)的構(gòu)建是按階段的逆序從后向前進(jìn)行的，所以也稱為動(dòng)態(tài)規(guī)劃的逆序算法。通過(guò)上述分析可以看出，任何一個(gè)多階段決策過(guò)程的最優(yōu)化問(wèn)題，都可以用非線性規(guī)劃（特殊的可以用線性規(guī)劃）模型來(lái)描述；因此，從原則上講，一般也可以用非線性規(guī)劃（或線性規(guī)劃）的方法來(lái)求解。那么利用動(dòng)態(tài)規(guī)劃求解多階段決策過(guò)程有什么優(yōu)越性、又有什么局限性。動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)：第一，求解更容易、效率更高。動(dòng)態(tài)規(guī)劃方法是一種逐步改善法，它把原問(wèn)題化成一系列結(jié)構(gòu)相似的最優(yōu)化子問(wèn)題，而每個(gè)子問(wèn)題的變量個(gè)數(shù)比原問(wèn)題少

52、得多，約束集合也簡(jiǎn)單得多，故較易于確定最優(yōu)解。第二，解的信息更豐富。非線性規(guī)劃（或線性規(guī)劃）的方法是對(duì)問(wèn)題的整體進(jìn)行一次性求解的，因此只能得到全過(guò)程的解；而動(dòng)態(tài)規(guī)劃方法是將過(guò)程分解成多個(gè)階段進(jìn)行求解的，因此不僅可以得到全過(guò)程的解，同時(shí)還可以得到所有子過(guò)程的解。動(dòng)態(tài)規(guī)劃的缺點(diǎn)：第一，沒(méi)有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)模型。由于實(shí)際問(wèn)題不同，其動(dòng)態(tài)規(guī)劃模型也就各有差異，模型構(gòu)建存在一定困難。第二，應(yīng)用條件苛刻。由于構(gòu)造動(dòng)態(tài)規(guī)劃模型狀態(tài)變量必須滿足“無(wú)后效性”條件，這一條件不僅依賴于狀態(tài)轉(zhuǎn)移律，還依賴于允許決策集合和指標(biāo)函數(shù)的結(jié)構(gòu)，不少實(shí)際問(wèn)題在取其自然特征作為狀態(tài)變量時(shí)并不滿足這一條件，這就降低了動(dòng)態(tài)規(guī)劃的通用性。第三，狀態(tài)變量存在“維數(shù)障礙”。最優(yōu)指標(biāo)函數(shù) (k k S f 是狀態(tài)變量的函數(shù)，當(dāng)狀態(tài)變量的維數(shù)增加時(shí)，最優(yōu)指標(biāo)函數(shù)的計(jì)算量將成指數(shù)倍增長(zhǎng)；因此，無(wú)論是手工計(jì)算還是電算“維數(shù)障礙”都是無(wú)法完全克服的。2.1.5 動(dòng)態(tài)規(guī)劃的四大要素及分類(1 動(dòng)態(tài)規(guī)劃的四大要素 狀態(tài)變量及其可能集合 s k Sk 決策變量及其允許集合 x k Dk 狀態(tài)轉(zhuǎn)移方程 s k+1= Tk (sk ,xk 階段收益 v k ( sk , xk (2 動(dòng)態(tài)