高等運籌第六講劉巍大連海事大學

1、高等運籌學高等運籌學大連海事大學大連海事大學劉巍劉巍第二篇 運籌學中的數(shù)學規(guī)劃 第四章第四章 線性規(guī)劃線性規(guī)劃 第五章第五章 非線性規(guī)劃非線性規(guī)劃 第六章第六章 錐規(guī)劃、矩陣規(guī)劃及變分不等式錐規(guī)劃、矩陣規(guī)劃及變分不等式 第七章第七章 整數(shù)規(guī)劃整數(shù)規(guī)劃 第八章第八章 動態(tài)規(guī)劃動態(tài)規(guī)劃 第九章第九章 向量優(yōu)化（多目標優(yōu)化）向量優(yōu)化（多目標優(yōu)化）第八章 動態(tài)規(guī)劃 當系統(tǒng)模型具備馬爾科夫性，同時目標函數(shù)當系統(tǒng)模型具備馬爾科夫性，同時目標函數(shù)可分且嵌套單調時，基于貝爾曼提出的最優(yōu)可分且嵌套單調時，基于貝爾曼提出的最優(yōu)性原理，運用動態(tài)規(guī)劃可將求解多階段全局性原理，運用動態(tài)規(guī)劃可將求解多階段全局最優(yōu)決策問題

2、分解為一系列在各個時間段上最優(yōu)決策問題分解為一系列在各個時間段上的局部優(yōu)化問題。相比其它解法，特別是在的局部優(yōu)化問題。相比其它解法，特別是在有擾動或在隨機情況下，動態(tài)規(guī)劃總是能有有擾動或在隨機情況下，動態(tài)規(guī)劃總是能有效地提供一個在當前信息集下的最優(yōu)反饋控效地提供一個在當前信息集下的最優(yōu)反饋控制策略。制策略。馬爾科夫性 在某些隨機系統(tǒng)中，有一類具有在某些隨機系統(tǒng)中，有一類具有“無后效性性質無后效性性質”，即當隨機過程在某一時刻，即當隨機過程在某一時刻to所處的狀態(tài)已知所處的狀態(tài)已知的條件下，過程在時刻的條件下，過程在時刻tto時所處的狀態(tài)只和時所處的狀態(tài)只和to時刻有關，而與時刻有關，而與to以

3、前的狀態(tài)無關。這種在已知以前的狀態(tài)無關。這種在已知“現(xiàn)在現(xiàn)在”的條件下，的條件下，“未來未來”與與“過去過去”彼此獨彼此獨立的特性就被稱為馬爾科夫性，具有這種性質的立的特性就被稱為馬爾科夫性，具有這種性質的隨機過程就叫做馬爾科夫過程，其最原始的模型隨機過程就叫做馬爾科夫過程，其最原始的模型就是馬爾科夫鏈。就是馬爾科夫鏈。貝爾曼“最優(yōu)性原理” 這個原理歸結為用一組基本的遞推關系這個原理歸結為用一組基本的遞推關系式使過程連續(xù)的最優(yōu)轉移，它可以求這式使過程連續(xù)的最優(yōu)轉移，它可以求這樣的最優(yōu)解，這些最優(yōu)解是以計算每個樣的最優(yōu)解，這些最優(yōu)解是以計算每個決策的后果并對今后的決策制定最優(yōu)決決策的后果并對今后

4、的決策制定最優(yōu)決策為基礎的，但在求最優(yōu)解時要按倒過策為基礎的，但在求最優(yōu)解時要按倒過來的順序進行，即從最終狀態(tài)開始到初來的順序進行，即從最終狀態(tài)開始到初始狀態(tài)為止。始狀態(tài)為止。最優(yōu)化原理： 作為整個過程的最優(yōu)策略具有這樣的性作為整個過程的最優(yōu)策略具有這樣的性質：無論過去的狀態(tài)和決策如何，相對質：無論過去的狀態(tài)和決策如何，相對于前面的決策所形成的狀態(tài)而言，余下于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構成最優(yōu)子策略。也就的決策序列必然構成最優(yōu)子策略。也就是說，一個最優(yōu)策略的子策略也是最優(yōu)是說，一個最優(yōu)策略的子策略也是最優(yōu)的。的。 7 動態(tài)規(guī)劃動態(tài)規(guī)劃(dynamic programming

5、) 動態(tài)規(guī)劃的基本概念和思想動態(tài)規(guī)劃的基本概念和思想 最短路徑問題最短路徑問題 投資分配問題投資分配問題 背包問題背包問題 排序問題排序問題8動態(tài)規(guī)劃是運籌學的一個分支，是求解多階段決策過動態(tài)規(guī)劃是運籌學的一個分支，是求解多階段決策過程最優(yōu)化問題的數(shù)學方法。程最優(yōu)化問題的數(shù)學方法。動態(tài)規(guī)劃在經(jīng)濟管理、工程技術、工農(nóng)業(yè)生產(chǎn)及軍事動態(tài)規(guī)劃在經(jīng)濟管理、工程技術、工農(nóng)業(yè)生產(chǎn)及軍事部門中都有著廣泛的應用，并且獲得了顯著的效果。部門中都有著廣泛的應用，并且獲得了顯著的效果。學習動態(tài)規(guī)劃，我們首先要了解多階段決策問題。學習動態(tài)規(guī)劃，我們首先要了解多階段決策問題。9最短路徑問題最短路徑問題：給定一個交通網(wǎng)絡圖

6、如下，其中兩點之：給定一個交通網(wǎng)絡圖如下，其中兩點之間的數(shù)字表示距離（或運費），試求從間的數(shù)字表示距離（或運費），試求從a a點到點到g g點的最短距點的最短距離（總運輸費用最?。?。離（總運輸費用最?。?。1 12 23 34 45 56 6ab1b2c1c2c3c4d1d2d3e1e2e3f1f2g53136876368533842221333525664310背包問題背包問題 有一個徒步旅行者，其可攜帶物品重量的限度有一個徒步旅行者，其可攜帶物品重量的限度為為a a 公斤，設有公斤，設有n n 種物品可供他選擇裝入包中。已知每種種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），

7、問此人應如何選擇攜帶物品的重量及使用價值（作用），問此人應如何選擇攜帶的物品（各幾件），使所起作用（使用價值）最大？的物品（各幾件），使所起作用（使用價值）最大？物品物品 1 2 j n重量（重量（公斤公斤/ /件件） a1 a2 aj an每件使用價值每件使用價值 c1 c2 cj cn 類似的還有工廠里的下料問題、運輸中的貨物裝載問題、人造衛(wèi)星內的物品裝載問題等。11 生產(chǎn)決策問題生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季

8、度地生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計劃。根據(jù)庫存和需求決定生產(chǎn)計劃。機器負荷分配問題機器負荷分配問題：某種機器可以在高低兩種不同的負荷：某種機器可以在高低兩種不同的負荷下進行生產(chǎn)。要求制定一個五年計劃，在下進行生產(chǎn)。要求制定一個五年計劃，在每年開始時，決每年開始時，決定如何重新分配定如何重新分配完好的完好的機器在兩種不同的負荷下生產(chǎn)的數(shù)機器在兩種不同的負荷下生產(chǎn)的數(shù)量量，使在五年內產(chǎn)品的總產(chǎn)量達到最高。，使在五年內產(chǎn)品的總產(chǎn)量達到最高。航天飛機飛行控制問題航天飛機飛行控制問題：由于航天飛機的運動的環(huán)境是不：由于航天飛機的運動的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機飛行在不同環(huán)境

9、中的情斷變化的，因此就要根據(jù)航天飛機飛行在不同環(huán)境中的情況，不斷地決定航天飛機的飛行方向和速度（狀態(tài)），使況，不斷地決定航天飛機的飛行方向和速度（狀態(tài)），使之能最省燃料和完成飛行任務（如軟著陸）。之能最省燃料和完成飛行任務（如軟著陸）。12根據(jù)過程的特性可以將過程按空間、時間等標志分為根據(jù)過程的特性可以將過程按空間、時間等標志分為若干個互相聯(lián)系又互相區(qū)別的階段。若干個互相聯(lián)系又互相區(qū)別的階段。在每一個階段都需要做出決策，從而使整個過程達到在每一個階段都需要做出決策，從而使整個過程達到最好的效果。最好的效果。各個階段決策的選取不是任意確定的，它依賴于當前各個階段決策的選取不是任意確定的，它依賴于

10、當前面臨的狀態(tài)，又影響以后的發(fā)展。面臨的狀態(tài)，又影響以后的發(fā)展。當各個階段的決策確定后，就組成了一個決策序列，當各個階段的決策確定后，就組成了一個決策序列，因而也就決定了整個過程的一條活動路線，這樣的一因而也就決定了整個過程的一條活動路線，這樣的一個前后關聯(lián)具有鏈狀結構的多階段過程就稱為多階段個前后關聯(lián)具有鏈狀結構的多階段過程就稱為多階段決策問題。決策問題。多階段決策過程的特點：多階段決策過程的特點：13針對多階段決策過程的最優(yōu)化問題，美國數(shù)學家針對多階段決策過程的最優(yōu)化問題，美國數(shù)學家bellmanbellman等人在等人在2020世紀世紀5050年代初提出了著名的最優(yōu)化原理，年代初提出了著

11、名的最優(yōu)化原理，把多階把多階段決策問題轉化為一系列單階段最優(yōu)化問題段決策問題轉化為一系列單階段最優(yōu)化問題，從而逐個求解，從而逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法：動態(tài)規(guī)劃。創(chuàng)立了解決這類過程優(yōu)化問題的新方法：動態(tài)規(guī)劃。對最佳路徑（最佳決策過程）所經(jīng)過的各個階段，其中每個階段始點到全過程終點的路徑，必定是該階段始點到全過程終點的一切可能路徑中的最佳路徑（最優(yōu)決策），這就是bellman提出的著名的最優(yōu)化原理。簡言之， 一個最優(yōu)策略的子策略必然也是最優(yōu)的。bellmanbellman在在19571957年出版的年出版的dynamic programmingdynamic programmi

12、ng是動是動態(tài)規(guī)劃領域的第一本著作。態(tài)規(guī)劃領域的第一本著作。14例1、從從a a 地到地到e e 地要鋪設一條煤氣管道地要鋪設一條煤氣管道, ,其中需經(jīng)過三其中需經(jīng)過三級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應該選擇什么路線，使總距離最短？問應該選擇什么路線，使總距離最短？ 二. 最短路徑問題a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1 1d d2 2e e52141126101043121113965810521c c2 215 解：解：整個計算過程分四個整個計算過程分四個階段階段，從最后一個階段

13、開始。，從最后一個階段開始。 第四階段（第四階段（d d e e）：）： d d 有兩條路線到終點有兩條路線到終點e e 。 顯然有顯然有a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1 1d d2 2e e52141126101043121113965810521c c2 22)(; 5)(2414 dfdf16首先考慮經(jīng)過首先考慮經(jīng)過 的兩條路線的兩條路線第三階段（第三階段（c c d d）：）： c c 到到d d 有有 6 6 條路線。條路線。( (最短路線為最短路線為 ) )a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1 1d d

14、2 2e e5 52 2141412126 6101010104 43 31212111113139 96 65 58 810105 52 21 1c c2 282953min)(),()(),(min)(2421141113 dfdcddfdcdcfedc111c17a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1 1d d2 2e e5 52 2141412126 6101010104 43 31212111113139 96 65 58 810105 52 21 1c c2 272556min)(),()(),(min)(2422141223 dfdcddfdc

15、dcf( (最短路線為最短路線為 ) )edc22考慮經(jīng)過考慮經(jīng)過 的兩條路線的兩條路線2c18a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1 1d d2 2e e5 52 2141412126 6101010104 43 31212111113139 96 65 58 810105 52 21 1c c2 21221058min)(),()(),(min)(2423141333 dfdcddfdcdcf( (最短路線為最短路線為 ) )edc23考慮經(jīng)過考慮經(jīng)過 的兩條路線的兩條路線3c19a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1

16、 1d d2 2e e5 52 2141412126 6101010104 43 31212111113139 96 65 58 810105 52 21 1c c2 2201210714812min)(),()(),()(),(min)(33312321131112 cfcbdcfcbdcfcbdbf( (最短路線最短路線為為 ) )edcb111第二階段（第二階段（b b c c）：）： b b 到到c c 有有 9 9 條路線。條路線。首先考慮經(jīng)過首先考慮經(jīng)過 的的3 3條路線條路線1b20a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1 1d d2 2e e5

17、 52 2141412126 6101010104 43 31212111113139 96 65 58 810105 52 21 1c c2 21412471086min)(),()(),()(),(min)(34322422141222 cfcbdcfcbdcfcbdbf( (最短路線為最短路線為 ) )edcb112考慮經(jīng)過考慮經(jīng)過 的的3 3條路線條路線2b21a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1 1d d2 2e e5 52 2141412126 6101010104 43 31212111113139 96 65 58 810105 52 21

18、 1c c2 2191211712813min)(),()(),()(),(min)(33332323131332 cfcbdcfcbdcfcbdbf( (最短路線為最短路線為 ) )edcb223考慮經(jīng)過考慮經(jīng)過 的的3 3條路線條路線3b22a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1 1d d2 2e e5 52 2141412126 6101010104 43 31212111113139 96 65 58 810105 52 21 1c c2 219191145202min)(),()(),()(),(min)(3232221211 bfbadbfbad

19、bfbadaf( (最短路線為最短路線為 ) )edcba112第一階段（第一階段（a a b b）：）： a a 到到b b 有有 3 3 條路線。條路線。 （最短距離為（最短距離為1919）23 動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點在于，數(shù)量方法。其特點在于，它可以把一個它可以把一個n n 維決策問題變換為維決策問題變換為幾個一維最優(yōu)化問題幾個一維最優(yōu)化問題，從而一個一個地去解決。，從而一個一個地去解決。 需指出：需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種

20、算法考察問題的一種途徑，而不是一種算法。必須對具體問題進。必須對具體問題進行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應的模型，行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應的模型，然后再用動態(tài)規(guī)劃方法去求解。然后再用動態(tài)規(guī)劃方法去求解。即在系統(tǒng)發(fā)展的不同時刻（或階段）根據(jù)系統(tǒng)所處的即在系統(tǒng)發(fā)展的不同時刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，狀態(tài)，不斷地做出決策不斷地做出決策；動態(tài)決策問題的特點：動態(tài)決策問題的特點：系統(tǒng)所處的系統(tǒng)所處的狀態(tài)和時刻狀態(tài)和時刻是進行決策的重要因素；是進行決策的重要因素；找到找到不同時刻不同時刻的最優(yōu)決策以及的最優(yōu)決策以及整個過程的最優(yōu)策略整個過程的最優(yōu)策略。24 動態(tài)規(guī)劃

21、方法的關鍵：在于正確地寫出動態(tài)規(guī)劃方法的關鍵：在于正確地寫出基本的遞基本的遞推關系式推關系式和和恰當?shù)倪吔鐥l件恰當?shù)倪吔鐥l件（簡稱（簡稱基本方程基本方程）。）。 要做到這一點，就必須將問題的過程分成幾個相要做到這一點，就必須將問題的過程分成幾個相互聯(lián)系的互聯(lián)系的階段階段，恰當?shù)倪x取，恰當?shù)倪x取狀態(tài)變量狀態(tài)變量和和決策變量決策變量及定義及定義最最優(yōu)值函數(shù)優(yōu)值函數(shù)，從而把一個大問題轉化成一組同類型的子問題，從而把一個大問題轉化成一組同類型的子問題，然后逐個求解。然后逐個求解。 即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的

22、最優(yōu)化結果，問題的求解中，均利用了它前面的子問題的最優(yōu)化結果，依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。的最優(yōu)解。25 2 2、在多階段決策過程中，動態(tài)規(guī)劃方法是既把當前、在多階段決策過程中，動態(tài)規(guī)劃方法是既把當前一段和未來一段一段和未來一段分開分開，又把當前效益和未來效益，又把當前效益和未來效益結合結合起來起來考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的來考慮的，與該段的最優(yōu)選擇答案一般是不同的. . 最優(yōu)化原理：作為整個過程的

23、最優(yōu)策略具有這樣的性質：無論過去的狀態(tài)和決策如何，相對于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構成最優(yōu)子策略。也就是說，一個最優(yōu)策略的子策略也是最優(yōu)的。 3、在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐段變換得到，從而確定了最優(yōu)路線。26動態(tài)規(guī)劃求解的多階段問題的特點：動態(tài)規(guī)劃求解的多階段問題的特點： 每個階段的最優(yōu)決策過程只與本階段的初始狀態(tài)有關每個階段的最優(yōu)決策過程只與本階段的初始狀態(tài)有關，而與以前各階段的決策（即為了到達本階段的初始，而與以前各階段的決策（即為了到達本階段的初始狀態(tài)而采用哪組決策路線無關）。換言之

24、，本階段之狀態(tài)而采用哪組決策路線無關）。換言之，本階段之前的狀態(tài)與決策，只是通過系統(tǒng)在本階段所處的初始前的狀態(tài)與決策，只是通過系統(tǒng)在本階段所處的初始狀態(tài)來影響本階段及以后各個階段的決策?；蛘哒f，狀態(tài)來影響本階段及以后各個階段的決策。或者說，系統(tǒng)過程的歷史只能通過系統(tǒng)現(xiàn)階段的狀態(tài)去影響系系統(tǒng)過程的歷史只能通過系統(tǒng)現(xiàn)階段的狀態(tài)去影響系統(tǒng)的未來。統(tǒng)的未來。 具有這種性質的狀態(tài)稱為無后效性（即馬爾科夫性）具有這種性質的狀態(tài)稱為無后效性（即馬爾科夫性）狀態(tài)。狀態(tài)。 動態(tài)規(guī)劃方法只適用于求解具有無后效性狀態(tài)的多階動態(tài)規(guī)劃方法只適用于求解具有無后效性狀態(tài)的多階段決策問題。段決策問題。27 現(xiàn)有數(shù)量為a（萬元

25、）的資金，計劃分配給n 個工廠,用于擴大再生產(chǎn)。 假設：xi 為分配給第i 個工廠的資金數(shù)量（萬元）；gi(xi)為第i 個工廠得到資金后提供的利潤值（萬元）。 問題：如何確定各工廠的資金數(shù)，使得總的利潤為最大。 nixaxxgziniiniii.2.1 0)( max11據(jù)此，有下式：三. 投資分配問題28 令：令：f fk k( (x x) ) 表示表示 以數(shù)量為以數(shù)量為 x x 的資金分配給的資金分配給前前k k 個個工工廠，所得到的最大利潤值。廠，所得到的最大利潤值。 用動態(tài)規(guī)劃求解，就是用動態(tài)規(guī)劃求解，就是求求 f fn n( (a a) ) 的問題的問題。 當當 k k=1 =1

26、時，時， f f1 1( (x x) = ) = g g1 1( (x x) ) （因為只給一（因為只給一個工廠）個工廠） 當當1 1k kn n 時，其遞推關系如下：時，其遞推關系如下： 設：設：y y 為分給第為分給第k k 個工廠的資金（其中個工廠的資金（其中 00y y x x ），），此時還剩此時還剩 x x y y（萬元）的資金需要分配給前（萬元）的資金需要分配給前 k k1 1 個工個工廠廠, ,如果采取最優(yōu)策略，則得到的最大利潤為如果采取最優(yōu)策略，則得到的最大利潤為f fk k1 1( (x xy y) ,) ,因此總的利潤為：因此總的利潤為： g gk k( (y y) )

27、f fk k1 1( (x xy y) ) 29 nkyxfygxfkkxyk.)()(max)(3210 其中 如果如果a a 是以萬元為資金分配單位，則式中的是以萬元為資金分配單位，則式中的y y 只取只取非負整數(shù)非負整數(shù)0 0，1 1，2 2，x x。上式可變?yōu)椋?。上式可變?yōu)椋?)()(max)(,yxfygxfkkxyk 1210所以，根據(jù)動態(tài)規(guī)劃的最優(yōu)化原理，有下式：所以，根據(jù)動態(tài)規(guī)劃的最優(yōu)化原理，有下式：30 例2：設國家撥給60萬元投資，供四個工廠擴建使用，每個工廠擴建后的利潤與投資額的大小有關，投資后的利潤函數(shù)如下表所示。 投資利潤0102030405060g1(x)02050

28、65808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依據(jù)題意，是要求 f4(60) 。31按順序解法計算。按順序解法計算。第一階段：求第一階段：求 f f1 1( (x x) )。顯然有。顯然有 f f1 1( (x x) ) g g1 1( (x x) )，得到，得到下表下表 投資投資利潤利潤0102030405060f1(x) g1(x)0205065808585最優(yōu)策略最優(yōu)策略0102030405060第二階段：求第二階段：求 f f2 2( (x x) )。此時需考慮第一、第二個工廠如何進。此時需考慮第一

29、、第二個工廠如何進行投資分配，以取得最大的總利潤。行投資分配，以取得最大的總利潤。 )60()(max)60(1260,10,02yfygfy 3212006520605055655080408520850max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max12121212121212fgfgfgfgfgfgfg最優(yōu)策略為（最優(yōu)策略為（4040，2020），此時最大利潤為），此時最大利潤為120120萬元。萬元。同理可求得其它同理可求得其它 f f2 2( (x x) ) 的值。的值。 )60()(max)60(1260,10

30、,02yfygfy 33 105)0()50()10()40()20()30()30()20()40()10()50()0( )50()(max)50(1212121212121250,10,02 fgfgfgfgfgfgyfygfy最優(yōu)策略為（最優(yōu)策略為（3030，2020），此時最大利潤為），此時最大利潤為105105萬元。萬元。34 90 )40()(max)40(1240,10,02 yfygfy最優(yōu)策略為（最優(yōu)策略為（2020，2020），此時最大利潤為），此時最大利潤為9090萬元。萬元。 70 )30()(max)30(1230,20,10,02 yfygfy最優(yōu)策略為（最優(yōu)策略

31、為（2020，1010），此時最大利潤為），此時最大利潤為7070萬元。萬元。35 50 )20()(max)20(1220,10,02 yfygfy 20 )10()(max)10(12,10,02 yfygfy最優(yōu)策略為（最優(yōu)策略為（1010，0 0）或（）或（ 0 0 ， 10 10 ） ，此時最大利，此時最大利潤為潤為2020萬元。萬元。 f f2 2(0) (0) 0 0。最優(yōu)策略為（最優(yōu)策略為（0 0，0 0），最大利潤為），最大利潤為0 0萬萬元。元。 得到下表得到下表最優(yōu)策略為（最優(yōu)策略為（2020，0 0），此時最大利潤為），此時最大利潤為5050萬元。萬元。36 投資投資利

32、潤利潤0102030405060f2(x)020507090105120最優(yōu)策略最優(yōu)策略(0,0)(10,0)(0,10)(20,0) (20,10) (20,20) (30,20) (40,20)第三階段：求第三階段：求 f f3 3( (x x) )。此時需考慮第一、第二及第三個。此時需考慮第一、第二及第三個工廠如何進行投資分配，以取得最大的總利潤。工廠如何進行投資分配，以取得最大的總利潤。 )60()(max)60(2360,10,03yfygfy 371550115201105010070859060105251200max)0()60()10()50()20()40()30()30(

33、)40()20()50()10()60()0(max23232323232323 fgfgfgfgfgfgfg最優(yōu)策略為（最優(yōu)策略為（2020，1010，3030），最大利潤為），最大利潤為155155萬元。萬元。同理可求得其它同理可求得其它 f f3 3( (x x) ) 的值。得到下表的值。得到下表38 投資投資利潤利潤0102030405060f3(x)0256085110135155最優(yōu)最優(yōu)策略策略(0,0,0) (0,0,10) (0,0,20) (0,0,30) (20,0,20) (20,0,30) (20,10,30)第四階段：求 f4(60)。即問題的最優(yōu)策略。)60()(m

34、ax)60(3460,10,04yfygfy3916007025656060855011040135251550max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max34343434343434fgfgfgfgfgfgfg最優(yōu)策略為（20，0，30，10），最大利潤為160萬元。40 有一個徒步旅行者，其可攜帶物品重量的限度為a 公斤，設有n 種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應如何選擇攜帶的物品（各幾件），使所起作用（使用價值）最大？物品物品 1 2 j n重量（重量（公斤公斤/ /件件）

35、a1 a2 aj an每件使用價值每件使用價值 c1 c2 cj cn 這就是背包問題。類似的還有工廠里的下料問題、運輸中的貨物裝載問題、人造衛(wèi)星內的物品裝載問題等。四、背包問題41設 xj 為第 j 種物品的裝件數(shù)（非負整數(shù)）則問題的數(shù)學模型如下： ).(maxnjxaxaxczjnijjjnjjj21 01且為整數(shù)用動態(tài)規(guī)劃方法求解，令 fk(y) = 總重量不超過 y 公斤，包中只裝有前k 種物品時的最大使用價值。 其中y 0， k 1,2, , n 。所以問題就是求 fn(a) 42其遞推關系式為： nkxayfxcyfkkkkkayxkkk 2 10其中)(max)(當 k=1 時，

36、有：的最大整數(shù)表示不超過其中1111111 ayayayxaycyf ,)(43例3：求下面背包問題的最優(yōu)解 且且為為整整數(shù)數(shù)0,55231258max321321321xxxxxxxxxz物品物品( (xi ) x1 x2 x3重量（重量（ai） 3 2 5使用價值使用價值 8 5 12解：a5 ，問題是求 f3(5) )55(12max)5(323503333xfxfxax 整整數(shù)數(shù)44 )( max)( 32350355125333xfxfxax 整數(shù) )( max 323550551233xfxxx 整數(shù) )( max 3231055123xfxx ， )( )()( ),(max 1

37、0223301250 xxff物品物品( (xi ) x1 x2 x3重量（重量（ai） 3 2 5使用價值使用價值 8 5 1245 5 5 )( 2)1()0(1112122, 10212250212502222222222)1(10),3(5),5(0max)25(max)25(max)25(5max)5(xxxxxxxaxfffxfxxfxxfxf，整數(shù)整數(shù)整數(shù)整數(shù)物品物品( (xi ) x1 x2 x3重量（重量（ai） 3 2 5使用價值使用價值 8 5 12 )()()()(max)(1022333012505x xf, ff46 )0( )0(0max )20(5 max )2

38、0(5 max )20(5 max)0(1 )0( 12120212 200212 0022222222ffxfxxfxxfxfxxxxxax 整數(shù)整數(shù)整數(shù)整數(shù)物品物品( (xi ) x1 x2 x3重量（重量（ai） 3 2 5使用價值使用價值 8 5 12 )1()0(22333)0(12)5(0max)5(x xf, ff47)0(0308)0()0(0318)1()1(8338)3()1(8358)5(1111111111111111 xxcfxxcfxxcfxxcf ) 1, 1(1310, 85, 8max) 1 (10),3(5),5(0max)5(212)1()0(111222

39、2 xxffffxxx )( 48 )0, 0(0)0()0(0max)0(211)0(122 xxfffx )0,1,1(13012,130max)0(12),5(0max)5(321)1()0(22333 xxxfffxx所以，最優(yōu)解為所以，最優(yōu)解為 x x（1 . 1 . 01 . 1 . 0），），最優(yōu)值為最優(yōu)值為 z z = = 1313?？偨Y：總結：解動態(tài)規(guī)劃的一般方法解動態(tài)規(guī)劃的一般方法: :從終點逐段向始點方向尋從終點逐段向始點方向尋找找最小最小( (大大) )的方法。的方法。49 排序問題指n 種零件經(jīng)過不同設備加工是的順序問題。其目的是使加工周期為最短。 1、n 1 排序問

40、題 即n 種零件經(jīng)過1 種設備進行加工，如何安排？14146 68 820202323交貨日期（交貨日期（d d）4 45 51 17 73 3加工時間（加工時間（t t）零件代號零件代號2j1j3j4j5j例5.1 五、排序問題50 （1）平均通過設備的時間最小 按零件加工時間非負次序排列順序，其時間最小。（即將加工時間由小到大排列即可）1j2j3j4j5j零件加工順序零件加工順序 工序工序時間時間1 13 34 45 57 7 實際通過時間實際通過時間1 14 48 813132020 交貨交貨時間時間8 8232314146 62020 平均通過時間2 . 9)1481320(51 x延

41、遲時間 = 13 6 = 751 （2）按時交貨排列順序1j2j3j4j5j零件加工順序零件加工順序 工序工序時間時間1 13 34 45 57 7 實際通過時間實際通過時間5 56 6101017172020 交貨交貨時間時間8 8232314146 62020 平均通過時間6 .11)56101720(51 x延遲時間 = 052 （3）既滿足交貨時間，又使平均通過時間最小1j2j3j4j5j零件加工順序零件加工順序 工序工序時間時間1 13 34 45 57 7 實際通過時間實際通過時間1 16 69 913132020 交貨交貨時間時間8 8232314146 62020延遲時間 =

42、0 平均通過時間8 .9)1691320(51 x53 2 2、n n 2 2 排序問題排序問題 即即n n 種零件經(jīng)過種零件經(jīng)過2 2 種設備進行加工，如何安種設備進行加工，如何安排？排？例5.24 49 95 52 23 3b b5 53 37 78 86 6a a 零件零件2j1j3j4j5j設備設備a ab bt t54經(jīng)變換為4 49 95 52 23 3b b5 53 37 78 86 6a a 零件零件2j1j3j4j5j設備設備加工順序圖如下：加工順序圖如下：a ab bt t3j1j2j4j5j3 37 75 56 68 89 95 54 43 32 2+2+2+2+2-5-

43、5 加工周期加工周期 t = 3+7+5+6+8+2 = 31t = 3+7+5+6+8+2 = 31小小即即batti 55 3 3、n n 3 3 排序問題排序問題 即即n n 種零件經(jīng)過種零件經(jīng)過 3 3 種設備進行加工，如何安種設備進行加工，如何安排？排？例5.33 34 46 68 85 56 64 46 68 83 35 57 79 93 31010c cb ba a1j2j3j4j5ja ab bc ct t56a ab bc ct t變換4+34+36+46+45+85+86+56+56+46+48+68+65+35+37+57+53+93+910+310+3b + b + c

44、 ca+ba+b1j2j3j4j5j57排序4+34+36+46+45+85+86+56+56+46+48+68+65+35+37+57+53+93+910+310+3b + b + c ca+ba+b1j2j3j4j5j復原3 34 46 68 85 56 64 46 68 83 35 57 79 93 31010c cb ba a1j2j3j4j5j58計算t = 6+10+8+7+6+4+3 = 44t = 6+10+8+7+6+4+3 = 44計算依據(jù)：abccbabcbattttttttttiiiiii 或即可按下式計算或maxminmaxmin60 六、系統(tǒng)可靠性問題 例例6.某科

45、研項目組由三個小組用不同的手段分別研究，它們失敗的概率各為0.40，0.60，0.80。為了減少三個小組都失敗的可能性，現(xiàn)決定給三個小組中增派兩名高級科學家，到各小組后，各小組科研項目失敗概率如下表： 問如何分派科學家才能使三個小組都失敗的概率（即科研項目最終失敗的概率）最?。?高級科學家小組12300.400.600.8010.200.400.5020.150.200.3061 解：用逆序算法。設 階段：每個研究小組為一個階段，且階段123小組12362計算 當n=3時，當n=2時， s3 f3*(s3) x3*008001050120302 x2s2f2(s2,x2)=p2(x2) f3*

46、(s2-x2) f2*(s2) x2*01200480480103003203002018020016016263當n=1時， 最優(yōu)解為 x1*=1，x2*=0，x3*=1；科研項目最終失敗的概率為0.060。 x1s1f1(s1,x1)=p1(x1) f2*(s1-x1)f2*(s2)x2*01220064 0060 0072 0060 164連續(xù)連續(xù)確定性動態(tài)規(guī)劃確定性動態(tài)規(guī)劃對于狀態(tài)變量和決策變量只取連續(xù)值，過程的演變方式為確定性時，這種動態(tài)規(guī)劃問題就稱為連續(xù)確定性動態(tài)規(guī)劃問題。65動態(tài)規(guī)劃的應用動態(tài)規(guī)劃的應用機器負荷分配問題機器負荷分配問題 例例1 一種機器能在高低兩種不同的負荷狀態(tài)下

47、工作。設機器在高負荷下生產(chǎn)時，產(chǎn)量函數(shù)為p1=8u1，其中u1為在高負荷狀態(tài)下生產(chǎn)的機器數(shù)目，年完好率為a=0.7，即到年底有70的機器保持完好。在低負荷下生產(chǎn)時，產(chǎn)量函數(shù)為p2=5u2，其中u2為在低負荷狀態(tài)下生產(chǎn)的機器數(shù)目，年完好率為b=0.9。設開始生產(chǎn)時共有1000臺完好的機器，請問每年應該如何把完好機器分配給高、低兩種負荷下生產(chǎn)，才能使得5年內生產(chǎn)的產(chǎn)品總產(chǎn)量最高。66解 建立動態(tài)規(guī)劃模型： 分為5個階段，每個階段為1年。設狀態(tài)變量sk表示在第k階段初擁有的完好機器數(shù)目；k=1,2,3,4,5。 決策變量xk表示第k階段中分配給高負荷狀態(tài)下生產(chǎn)的機器數(shù)目；k=1,2,3,4,5。顯然

48、sk-xk為分配給低負荷狀態(tài)下生產(chǎn)的機器數(shù)目。 狀態(tài)轉移方程為 sk+1=0.7xk+0.9(sk-xk) 階段指標 rk(sk,xk)=8xk+5(sk-xk) 最優(yōu)指標函數(shù) ，其中k=1,2,3,4,5。 f6(s6)=0。)()58max)(11kkkkkkksfxsxsf（kksx 067第5階段： 因為f5(s5)是x5的線性單調增函數(shù)，故有x5* =s5，于是有f5(s5)=8s5。第4階段： )(2 .126 .13max)(9 . 07 . 0 8)(58max8)(58max)()(58max)(44404444440544405544404444444444xsxxsxxs

49、xsxsxsfxsxsfsxsxsxsx 68 同樣的，f4(s4)是x4的線性單調增函數(shù)，有x4*=s4 ，f4(s4)=13.6s4。 對前幾個階段依次類推，可得 f3(s3)=17.5s3， f2(s2)=20.75s2， f1(s1)=23.72s1。 因為期初共有完好機器1000臺，故s1=1000。有f1(s1)=23.72s123720，即5年最大的產(chǎn)量為23720臺。得最優(yōu)解為 ， ， ， 。 這意味著前兩年應把年初完好機器完全投入低負荷生產(chǎn)，后三年應把年初完好機器完全投入高負荷生產(chǎn)。0*1x0*2x3*3sx 4*4sx 5*5sx 69 下一步工作是確定每年初的狀態(tài)，按照從

50、前向后的順序依次計算出每年年初完好的機器數(shù)目。已知s1=1000,根據(jù)狀態(tài)轉移方程，有:9009 . 0)(9 . 07 . 01*11*12sxsxs8109 . 0)(9 . 07 . 02*22*23sxsxs5677 . 0)(9 . 07 . 03*33*34sxsxs3977 . 0)(9 . 07 . 04*44*45sxsxs70 上面所討論的最優(yōu)策略過程，初始端狀態(tài)s1=1000臺是固定的，終點狀態(tài)s6沒有要求。這種情況下得到最優(yōu)決策稱為初始端固定終點自由的最優(yōu)策略。 如果終點附加一定的條件，則問題就稱為“終端固定問題”。例如，規(guī)定在第5年度結束時仍要保持500臺機器完好（而

51、不是278臺），應如何安排生產(chǎn)才能使得總產(chǎn)量最大？ 下面來分析： 根據(jù)終點條件有 可得500)(9 . 07 . 05556xsxs25005 . 455sx71 顯然，由于固定了終點的狀態(tài)，x5的取值受到了約束。因此有 類似的， 容易解得 ，f4(s4)=21.7s4-7500。75005 .18)25005 . 4(5)25005 . 4(8max)(555555sssssf75007 . 07 .21max75005 .18)(58max)()(58max)(4405444055444044444444xssxsxsfxsxsfsxsxsx0*4x72 依次類推，得 f3(s3)=24.

52、5s3-7500 f2(s2)=27.1s2-7500 f1(s1)=29.4s1-7500 再采用順序方法遞推計算各年的狀態(tài)，有 s1=1000， 0*1*2*3xxx9009 . 0)(9 . 07 . 01*11*12sxsxs8109 . 0)(9 . 07 . 02*22*23sxsxs7297 . 0)(9 . 07 . 03*33*34sxsxs6567 . 0)(9 . 07 . 04*44*45sxsxs73 可見，為了使終點完好的機器數(shù)量增加到500臺，需要安排前四年中全部完好機器都要投入低負荷生產(chǎn)，且在第5年，也只能全部投入高負荷。 相應的最優(yōu)指標為 f1(s1)=29.

53、4s1-750021900。 可以看到，因為增加了附加條件，總產(chǎn)量f1(s1)要比終點自由情況下的產(chǎn)量要低。動態(tài)規(guī)劃進展 在過去的若干年里，動態(tài)規(guī)劃取得了不在過去的若干年里，動態(tài)規(guī)劃取得了不少可喜的進展，特別是它被擴展到多目少可喜的進展，特別是它被擴展到多目標動態(tài)規(guī)劃標動態(tài)規(guī)劃;動態(tài)規(guī)劃應用在本世紀前后動態(tài)規(guī)劃應用在本世紀前后的一個重大突破是其在海量數(shù)據(jù)（大數(shù)的一個重大突破是其在海量數(shù)據(jù)（大數(shù)據(jù)）分析中的應用，特別是人類基因組據(jù)）分析中的應用，特別是人類基因組計劃完成以后，它成為生物信息學的一計劃完成以后，它成為生物信息學的一個基本模型和工具。個基本模型和工具。問題與研究方向 應當指出，在克服

54、被貝爾曼稱之為應當指出，在克服被貝爾曼稱之為“維數(shù)災維數(shù)災”的這一動態(tài)規(guī)劃致命弱點的方面，至今尚的這一動態(tài)規(guī)劃致命弱點的方面，至今尚未取得突破性的進展。所以尋求克服維數(shù)災未取得突破性的進展。所以尋求克服維數(shù)災的有效算法對動態(tài)規(guī)劃在高維間題中的應用的有效算法對動態(tài)規(guī)劃在高維間題中的應用具有它的緊迫性。另外，求解不可分優(yōu)化問具有它的緊迫性。另外，求解不可分優(yōu)化問題得到的最優(yōu)策略并不滿足最優(yōu)性原理，或題得到的最優(yōu)策略并不滿足最優(yōu)性原理，或不具備時間一致性。這牽涉到不可分優(yōu)化問不具備時間一致性。這牽涉到不可分優(yōu)化問題模型本身的合理性。因此怎樣找出一組可題模型本身的合理性。因此怎樣找出一組可分優(yōu)化間題來

55、逼近一個給定的不可分優(yōu)化間分優(yōu)化間題來逼近一個給定的不可分優(yōu)化間題也對動態(tài)規(guī)劃發(fā)展具有顯然的重要性。題也對動態(tài)規(guī)劃發(fā)展具有顯然的重要性。 動態(tài)決策問題無處不在。在眾多求解序貫決策問題動態(tài)決策問題無處不在。在眾多求解序貫決策問題方法中，由理查貝爾曼教授率先提出的動態(tài)規(guī)劃方法中，由理查貝爾曼教授率先提出的動態(tài)規(guī)劃方法毫無疑問是最具廣泛適用性的。但是任何方法方法毫無疑問是最具廣泛適用性的。但是任何方法都有其局限性。動態(tài)規(guī)劃以最優(yōu)性原理為基礎。該都有其局限性。動態(tài)規(guī)劃以最優(yōu)性原理為基礎。該原理要求多階段決策的最優(yōu)決策序列必須具備這樣原理要求多階段決策的最優(yōu)決策序列必須具備這樣的性質：不論初始狀態(tài)和初始

56、決策如何，對于前面的性質：不論初始狀態(tài)和初始決策如何，對于前面的一系列決策所造成的某一當前狀態(tài)，其后各階段的一系列決策所造成的某一當前狀態(tài)，其后各階段的決策序列仍需對這一狀態(tài)構成最優(yōu)策略。的決策序列仍需對這一狀態(tài)構成最優(yōu)策略。 此原理本質上是要求決策者的偏好（風此原理本質上是要求決策者的偏好（風險態(tài)度）不隨時間和狀態(tài)發(fā)生變化。但險態(tài)度）不隨時間和狀態(tài)發(fā)生變化。但在現(xiàn)實生活中，人們的偏好常常會隨當在現(xiàn)實生活中，人們的偏好常常會隨當前所處的時間與狀況的改變而不同。前所處的時間與狀況的改變而不同。 因此，決策者常常陷入兩難境地：應考因此，決策者常常陷入兩難境地：應考慮整個時間跨度上的總體目標，還是關

57、慮整個時間跨度上的總體目標，還是關心尾部時間區(qū)間上的局部目標。心尾部時間區(qū)間上的局部目標。 這進一這進一步導致全局最優(yōu)決策步導致全局最優(yōu)決策 遵守承諾的遵守承諾的行為與局部最優(yōu)決策行為與局部最優(yōu)決策 受誘惑的受誘惑的行為之間的沖突，造成決策行為的時行為之間的沖突，造成決策行為的時間不一致。此時貝爾曼的最優(yōu)性原理不間不一致。此時貝爾曼的最優(yōu)性原理不再滿足。再滿足。 目前文獻中處理這一問題的途徑主要有目前文獻中處理這一問題的途徑主要有兩類：完全忽視局部誘惑來求得全局最兩類：完全忽視局部誘惑來求得全局最優(yōu)策略，或完全忽視全局目標從而求得優(yōu)策略，或完全忽視全局目標從而求得滿足時間一致性的策略。其中一個

58、具有滿足時間一致性的策略。其中一個具有挑戰(zhàn)性的研究課題是怎樣平衡（時間不挑戰(zhàn)性的研究課題是怎樣平衡（時間不一致）動態(tài)決策問題中的長期和短期利一致）動態(tài)決策問題中的長期和短期利益沖突。益沖突。 李端教授出生于中國上海。他本科畢業(yè)于上海復旦大學物理系，其后獲上海交通大學自動控制碩士學位與美國凱斯西儲大學系統(tǒng)工程博士學位。李教授于一九八七年至一九九四年在美國弗吉尼亞大學任教，任系統(tǒng)工程學系副教授（研究），并任工程系統(tǒng)風險管理中心副主任。他于一九九四年底加入香港中文大學系統(tǒng)工程與工程管理學系，現(xiàn)任系統(tǒng)工程與工程管理學講座教授，并曾于二零零三年至二零一二年出任該系系主任。 構造了一個帶有自我控制的多階段

59、均值構造了一個帶有自我控制的多階段均值-方差投資博弈模型，其中負責整體投資方差投資博弈模型，其中負責整體投資決策的高層決策者可以通過某種具體的決策的高層決策者可以通過某種具體的懲罰承諾來影響不同時間段上決策執(zhí)行懲罰承諾來影響不同時間段上決策執(zhí)行者的偏好，從而建立長期目標和短期目者的偏好，從而建立長期目標和短期目標之間的理性關聯(lián)。標之間的理性關聯(lián)。 進一步推導出解析形式的納什均衡策略進一步推導出解析形式的納什均衡策略，找到了全局和局部利益之間的最佳平，找到了全局和局部利益之間的最佳平衡點。對于一般的（時間不一致）隨機衡點。對于一般的（時間不一致）隨機決策問題，進一步擴展了帶有自我控制決策問題，進

60、一步擴展了帶有自我控制的博弈模型以得到更具一般性的結論。的博弈模型以得到更具一般性的結論。同時論證了該模型與現(xiàn)有經(jīng)濟文獻中關同時論證了該模型與現(xiàn)有經(jīng)濟文獻中關于自我控制的理論是吻合的。于自我控制的理論是吻合的。動態(tài)規(guī)劃實現(xiàn)中的問題動態(tài)規(guī)劃實現(xiàn)中的問題 應用動態(tài)規(guī)劃解決問題，在有了基本的應用動態(tài)規(guī)劃解決問題，在有了基本的思路之后，一般來說，算法實現(xiàn)是比較思路之后，一般來說，算法實現(xiàn)是比較好考慮的。但有時也會遇到一些問題，好考慮的。但有時也會遇到一些問題，而使算法難以實現(xiàn)。而使算法難以實現(xiàn)。 動態(tài)規(guī)劃思想設計的算法從整體上來看基本都是按照得動態(tài)規(guī)劃思想設計的算法從整體上來看基本都是按照得出的遞推關