《運(yùn)籌學(xué)》胡運(yùn)權(quán)清華版-7-01動(dòng)態(tài)規(guī)劃

第七章動(dòng)態(tài)規(guī)劃多階段決策問(wèn)題動(dòng)態(tài)規(guī)劃的基本概念和基本原理動(dòng)態(tài)規(guī)劃模型的建立逆推解法與順推解法動(dòng)態(tài)規(guī)劃應(yīng)用舉例

1ppt課件第一節(jié)多階段決策問(wèn)題2ppt課件多階段決策問(wèn)題在實(shí)際生產(chǎn)經(jīng)營(yíng)活動(dòng)中，存在著一類將過(guò)程劃分為若干個(gè)相互聯(lián)系的階段，而每個(gè)階段都需要做出決策，并且一個(gè)階段的決策確定后，常影響下一階段的決策，即多階段決策問(wèn)題。在這類多階段決策問(wèn)題中，整個(gè)問(wèn)題的各個(gè)階段所確定的決策構(gòu)成一個(gè)決策序列，通稱為策略。對(duì)應(yīng)于一個(gè)策略，就有確定活動(dòng)效果，且可用數(shù)量指標(biāo)來(lái)衡量。因此多階段決策問(wèn)題就需要在允許選擇的那些策略中選擇最優(yōu)策略，使在預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好的效果。3ppt課件在多階段決策問(wèn)題中，階段往往可用時(shí)段來(lái)表示，隨著時(shí)間的推移，在每一時(shí)段上選擇最恰當(dāng)?shù)臎Q策，以期在整體上達(dá)到最優(yōu)。動(dòng)態(tài)規(guī)劃是解決多階段決策過(guò)程的方法。

R.Bellman50年代執(zhí)教于普林斯頓和斯坦福大學(xué)，1957年發(fā)表“DynamicProgramming”一書(shū)，標(biāo)識(shí)動(dòng)態(tài)規(guī)劃的正式誕生。

12n

狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策4ppt課件AB1B2C1C2C3C4D1D2D3E1E2F542368778443548531356243123455階段決策問(wèn)題例4.最短路問(wèn)題5ppt課件如何求解最短路問(wèn)題？（1）最短路問(wèn)題的特點(diǎn)：若A－>B1－>C2－>D2－>E2－>F

是從A到F的最短路，則必有B1－>C2－>D2－>E2－>F

是從B1到F的最短路，

C2－>D2－>E2－>F

是從C2到F的最短路，

D2－>E2－>F

是從D2到F的最短路，E2－>F

是從E2到F的最短路即：若某一點(diǎn)在最優(yōu)路線上，那么從那一點(diǎn)到終點(diǎn)的最短路線也在最優(yōu)路線上。6ppt課件（2）解決最短路問(wèn)題的方法：

假設(shè)每一個(gè)點(diǎn)都在最優(yōu)路線上，然后做相關(guān)計(jì)算。具體地：從最后階段的兩個(gè)始點(diǎn)E1和E2開(kāi)始，由后向前，計(jì)算每一個(gè)點(diǎn)到F的最短路線，直到結(jié)點(diǎn)A，這時(shí)找到A到F的最短路。7ppt課件AB1B2C1C2C3C4D1D2D3E1E2F5423687784435485313562433

4

最短路問(wèn)題的求解123458ppt課件AB1B2C1C2C3C4D1D2D3E1E2F5423687784435485313562433

4

5

7

5

123459ppt課件AB1B2C1C2C3C4D1D2D3E1E2F5423687784435485123

4

5

7

512

10

8

91234510ppt課件AB1B2C1C2C3C4D1D2D3E1E2F54236877123

4

5

7

5

12

10

8

913

15

1234511ppt課件AB1B2C1C2C3C4D1D2D3E1E2F54123

4

5

7

5

12

10

8

913

15

17

1234512ppt課件AB1B2C1C2C3C4D1D2D3E1E2F123

4

5

7

5

12

10

8

913

15

17

注：同時(shí)得到所有頂點(diǎn)到終點(diǎn)最短路。1234513ppt課件用動(dòng)態(tài)規(guī)劃求解最短路問(wèn)題的思路將大問(wèn)題分成結(jié)構(gòu)相似的小問(wèn)題，遞推求解。14ppt課件最短路問(wèn)題：AB1B2C1C2C3C4D1D2D3E1E2F54236877844354853135624312345子問(wèn)題1——在第5階段應(yīng)怎樣走，使得第5階段初各起點(diǎn)E1、E2到終點(diǎn)F的路長(zhǎng)最短？15ppt課件AB1B2C1C2C3C4D1D2D3E1E2F54236877844354853135624312345子問(wèn)題2——根據(jù)上一步的結(jié)果，在第4階段應(yīng)怎樣走，使得第4階段初各起點(diǎn)D1、D2、D3到終點(diǎn)F的路長(zhǎng)最短？16ppt課件AB1B2C1C2C3C4D1D2D3E1E2F54236877844354853135624312345子問(wèn)題3——根據(jù)上一步的結(jié)果，在第3階段應(yīng)怎樣走，使得第3階段初各起點(diǎn)C1、C2、C3、C4到終點(diǎn)F的路長(zhǎng)最短？17ppt課件AB1B2C1C2C3C4D1D2D3E1E2F54236877844354853135624312345子問(wèn)題4——根據(jù)上一步的結(jié)果，在第2階段應(yīng)怎樣走，使得第2階段初各起點(diǎn)B1、B2到終點(diǎn)F的路長(zhǎng)最短？18ppt課件AB1B2C1C2C3C4D1D2D3E1E2F54236877844354853135624312345子問(wèn)題5——根據(jù)上一步的結(jié)果，在第1階段應(yīng)怎樣走，使得第1階段初起點(diǎn)A到終點(diǎn)F的路長(zhǎng)最短？即為所求！19ppt課件例:W先生每天駕車去公司上班。如圖，W先生的住所位于A，公司位于F，圖中的直線段代表公路，交叉點(diǎn)代表路口，直線段上的數(shù)字代表兩路口之間的平均行駛時(shí)間?，F(xiàn)在W先生的問(wèn)題是要確定一條最省時(shí)的上班路線。20ppt課件A3B14C13D14532B22C23D24E11234C34D35E2