動態(tài)規(guī)劃方法簡介ppt課件.ppt

《動態(tài)規(guī)劃方法簡介ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、動態(tài)規(guī)劃方法簡介動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種方法。由美國數(shù)學(xué)家貝爾曼（Ballman）等人在20世紀(jì)50年代提出。他們針對多階段決策問題的特點，提出了解決這類問題的“最優(yōu)化原理”，并成功地解決了生產(chǎn)管理、工程技術(shù)等方面的許多實際問題。docin/sundae_meng動態(tài)規(guī)劃是現(xiàn)代企業(yè)管理中的一種重要決策方法，可用于最優(yōu)路徑問題、資源分配問題、生產(chǎn)計劃和庫存問題、投資問題、裝載問題、排序問題及生產(chǎn)過程的最優(yōu)控制等。docin/sundae_meng一.多階段決策過程最優(yōu)化多階段決策過程是指這樣一類特殊的活動過程，他們可以按時間順序分解成若干相互聯(lián)系的階段，在

2、每個階段都要做出決策，全部過程的決策是一個決策序列，所以多階段決策問題也稱為序貫決策問題。動態(tài)規(guī)劃的基本原理docin/sundae_meng12n?狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策圖示多階段決策問題，不論其本身是否與時間有關(guān)，由于分為階段依次解決，這便具有明顯的時序性，而在各階段中所采取的決策是隨階段而變動的，不同階段采取不同決策，這便是動態(tài)的含義.階段往往可以用時段來表示，但動態(tài)規(guī)劃在一定條件下也可以解決一些與時間無關(guān)的靜態(tài)最優(yōu)化問題，只要人為地引入“時段”因素，就可以將其轉(zhuǎn)化為一個多階段決策問題。docin/sundae_meng動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一

3、種數(shù)量方法。其特點在于，它可以把一個n維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。必須對具體問題進(jìn)行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動態(tài)規(guī)劃方法去求解。docin/sundae_meng二、多階段決策問題舉例1)工廠生產(chǎn)過程：由于市場需求是一隨著時間而變化的因素，因此，為了取得全年最佳經(jīng)濟(jì)效益，就要在全年的生產(chǎn)過程中，逐月或者逐季度地根據(jù)庫存和需求情況決定生產(chǎn)計劃安排。docin/sundae_meng2)設(shè)備更新問題：一般企業(yè)用于生產(chǎn)活動的設(shè)備，剛買來

4、時故障少，經(jīng)濟(jì)效益高，即使進(jìn)行轉(zhuǎn)讓，處理價值也高，隨著使用年限的增加，就會逐漸變?yōu)楣收隙?，維修費用增加，可正常使用的工時減少，加工質(zhì)量下降，經(jīng)濟(jì)效益差，并且，使用的年限越長、處理價值也越低，自然，如果賣去舊的買新的，還需要付出更新費．因此就需要綜合權(quán)衡決定設(shè)備的使用年限，使總的經(jīng)濟(jì)效益最好。docin/sundae_meng3)連續(xù)生產(chǎn)過程的控制問題：一般化工生產(chǎn)過程中，常包含一系列完成生產(chǎn)過程的設(shè)備，前一工序設(shè)備的輸出則是后一工序設(shè)備的輸入，因此，應(yīng)該如何根據(jù)各工序的運行工況，控制生產(chǎn)過程中各設(shè)備的輸入和輸出，以使總產(chǎn)量最大。docin/sundae_mengdocin/

5、sundae_meng4)運輸網(wǎng)絡(luò)問題（最短路問題）：如圖1所示的運輸網(wǎng)絡(luò)，點間連線上的數(shù)字表示兩地距離(也可是運費、時間等)，要求從v1至v10的最短路線。這種運輸網(wǎng)絡(luò)問題也是靜態(tài)決策問題。但是，按照網(wǎng)絡(luò)中點的分布，可以把它分為4個階段，而作為多階段決策問題來研究。docin/sundae_meng以上所舉問題的發(fā)展過程都與時間因素有關(guān)，階段的劃分常取時間區(qū)段來表示，并且各個階段上的決策往往也與時間因素有關(guān)，這就使它具有了“動態(tài)”的含義，所以把處理這類動態(tài)問題的方法稱為動態(tài)規(guī)劃方法。不過，實際中尚有許多不包含時間因素的一類“靜態(tài)”決策問題，就其本質(zhì)而言是一次決策問題，是非

6、動態(tài)決策問題，但是也可以人為地引入階段的概念當(dāng)作多階段決策問題，應(yīng)用動態(tài)規(guī)劃方法加以解決。docin/sundae_meng三、動態(tài)規(guī)劃方法導(dǎo)引例1：為了說明動態(tài)規(guī)劃的基本思想方法和特點，下面以圖1所示為例討論的求最短路問題的方法。第一種方法稱做全枚舉法或窮舉法。它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對它們一一進(jìn)行比較，求出最優(yōu)方案。這里從v1到v10的路程可以分為4個階段。第一段的走法有三種，第二三兩段的走法各有兩種，第四段的走法僅一種，因此共有3×2×2×1＝12條可能的路線，分別算出各條路線的距離，最后進(jìn)行比較，可知最優(yōu)路線是v1→v3→v7→v9→v10,

7、最短距離是18．docin/sundae_meng顯然，當(dāng)組成交通網(wǎng)絡(luò)的節(jié)點很多時，用窮舉法求最優(yōu)路線的計算工作量將會十分龐大，而且其中包含著許多重復(fù)計算．第二種方法即所謂“局部最優(yōu)路徑”法，是說某人從k出發(fā)，他并不顧及全線是否最短，只是選擇當(dāng)前最短途徑，“逢近便走”，錯誤地以為局部最優(yōu)會致整體最優(yōu)，在這種想法指導(dǎo)下，所取決策必是v1→v3→v5→v8→v10，全程長度是20；顯然，這種方法的結(jié)果常是錯誤的．docin/sundae_meng第三種方法是動態(tài)規(guī)劃方法。動態(tài)規(guī)劃方法尋求該最短路問題的基本思想是，首先將