數(shù)模(動(dòng)態(tài)規(guī)劃).ppt

1 數(shù)學(xué)模型電子教案 重慶郵電大學(xué)數(shù)理學(xué)院沈世云 2 第7章動(dòng)態(tài)規(guī)劃 Dynamicprogramming 動(dòng)態(tài)規(guī)劃的基本思想 最短路徑問(wèn)題 投資分配問(wèn)題 背包問(wèn)題 3 動(dòng)態(tài)規(guī)劃是用來(lái)解決多階段決策過(guò)程最優(yōu)化的一種數(shù)量方法 其特點(diǎn)在于 它可以把一個(gè)n維決策問(wèn)題變換為幾個(gè)一維最優(yōu)化問(wèn)題 從而一個(gè)一個(gè)地去解決 需指出 動(dòng)態(tài)規(guī)劃是求解某類問(wèn)題的一種方法 是考察問(wèn)題的一種途徑 而不是一種算法 必須對(duì)具體問(wèn)題進(jìn)行具體分析 運(yùn)用動(dòng)態(tài)規(guī)劃的原理和方法 建立相應(yīng)的模型 然后再用動(dòng)態(tài)規(guī)劃方法去求解 4 即在系統(tǒng)發(fā)展的不同時(shí)刻 或階段 根據(jù)系統(tǒng)所處的狀態(tài) 不斷地做出決策 每個(gè)階段都要進(jìn)行決策 目的是使整個(gè)過(guò)程的決策達(dá)到最優(yōu)效果 動(dòng)態(tài)決策問(wèn)題的特點(diǎn) 系統(tǒng)所處的狀態(tài)和時(shí)刻是進(jìn)行決策的重要因素 找到不同時(shí)刻的最優(yōu)決策以及整個(gè)過(guò)程的最優(yōu)策略 多階段決策問(wèn)題 是動(dòng)態(tài)決策問(wèn)題的一種特殊形式 在多階段決策過(guò)程中 系統(tǒng)的動(dòng)態(tài)過(guò)程可以按照時(shí)間進(jìn)程分為狀態(tài)相互聯(lián)系而又相互區(qū)別的各個(gè)階段 5 多階段決策問(wèn)題的典型例子 1 生產(chǎn)決策問(wèn)題 企業(yè)在生產(chǎn)過(guò)程中 由于需求是隨時(shí)間變化的 因此企業(yè)為了獲得全年的最佳生產(chǎn)效益 就要在整個(gè)生產(chǎn)過(guò)程中逐月或逐季度地根據(jù)庫(kù)存和需求決定生產(chǎn)計(jì)劃 2 機(jī)器負(fù)荷分配問(wèn)題 某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn) 在高負(fù)荷下進(jìn)行生產(chǎn)時(shí) 產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)量u1的關(guān)系為g g u1 1 2 n 狀態(tài) 決策 狀態(tài) 決策 狀態(tài) 狀態(tài) 決策 6 這時(shí) 機(jī)器的年完好率為a 即如果年初完好機(jī)器的數(shù)量為u 到年終完好的機(jī)器就為au 0 a 1 在低負(fù)荷下生產(chǎn)時(shí) 產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機(jī)器數(shù)量u2的關(guān)系為h h u2 假定開(kāi)始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為s1 要求制定一個(gè)五年計(jì)劃 在每年開(kāi)始時(shí) 決定如何重新分配完好的機(jī)器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量 使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高 相應(yīng)的機(jī)器年完好率b 0 b 1 7 3 航天飛機(jī)飛行控制問(wèn)題 由于航天飛機(jī)的運(yùn)動(dòng)的環(huán)境是不斷變化的 因此就要根據(jù)航天飛機(jī)飛行在不同環(huán)境中的情況 不斷地決定航天飛機(jī)的飛行方向和速度 狀態(tài) 使之能最省燃料和實(shí)現(xiàn)目的 如軟著落問(wèn)題 不包含時(shí)間因素的靜態(tài)決策問(wèn)題 本質(zhì)上是一次決策問(wèn)題 也可以適當(dāng)?shù)匾腚A段的概念 作為多階段的決策問(wèn)題用動(dòng)態(tài)規(guī)劃方法來(lái)解決 4 線性規(guī)劃 非線性規(guī)劃等靜態(tài)的規(guī)劃問(wèn)題也可以通過(guò)適當(dāng)?shù)匾腚A段的概念 應(yīng)用動(dòng)態(tài)規(guī)劃方法加以解決 8 5 最短路問(wèn)題 給定一個(gè)交通網(wǎng)絡(luò)圖如下 其中兩點(diǎn)之間的數(shù)字表示距離 或花費(fèi) 試求從A點(diǎn)到G點(diǎn)的最短距離 總費(fèi)用最小 1 2 3 4 5 6 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 3 9 一 基本概念1 階段 把一個(gè)問(wèn)題的過(guò)程 恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段 以便于按一定的次序去求解 描述階段的變量稱為階段變量 階段的劃分 一般是根據(jù)時(shí)間和空間的自然特征來(lái)進(jìn)行的 但要便于問(wèn)題轉(zhuǎn)化為多階段決策 2 狀態(tài) 表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件 通常一個(gè)階段有若干個(gè)狀態(tài) 描述過(guò)程狀態(tài)的變量稱為狀態(tài)變量 一個(gè)數(shù) 一組數(shù) 一個(gè)向量 狀態(tài)變量的取值有一定的允許集合或范圍 此集合稱為狀態(tài)允許集合 一 動(dòng)態(tài)規(guī)劃的基本思想 10 3 決策 表示當(dāng)過(guò)程處于某一階段的某個(gè)狀態(tài)時(shí) 可以作出不同的決定 從而確定下一階段的狀態(tài) 這種決定稱為決策 描述決策的變量 稱為決策變量 決策變量是狀態(tài)變量的函數(shù) 可用一個(gè)數(shù) 一組數(shù)或一向量 多維情形 來(lái)描述 在實(shí)際問(wèn)題中決策變量的取值往往在某一范圍之內(nèi) 此范圍稱為允許決策集合 系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)的當(dāng)前的狀態(tài)和決策有關(guān) 而且還與系統(tǒng)過(guò)去的歷史狀態(tài)和決策有關(guān) 4 多階段決策過(guò)程 可以在各個(gè)階段進(jìn)行決策 去控制過(guò)程發(fā)展的多段過(guò)程 其發(fā)展是通過(guò)一系列的狀態(tài)轉(zhuǎn)移來(lái)實(shí)現(xiàn)的 11 圖示如下 狀態(tài)轉(zhuǎn)移方程是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程 如果第k階段狀態(tài)變量sk的值 該階段的決策變量一經(jīng)確定 第k 1階段狀態(tài)變量sk 1的值也就確定 其狀態(tài)轉(zhuǎn)移方程如下 一般形式 能用動(dòng)態(tài)規(guī)劃方法求解的多階段決策過(guò)程是一類特殊的多階段決策過(guò)程 即具有無(wú)后效性的多階段決策過(guò)程 12 如果狀態(tài)變量不能滿足無(wú)后效性的要求 應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法 動(dòng)態(tài)規(guī)劃中能處理的狀態(tài)轉(zhuǎn)移方程的形式 狀態(tài)具有無(wú)后效性的多階段決策過(guò)程的狀態(tài)轉(zhuǎn)移方程如下 無(wú)后效性 馬爾可夫性 如果某階段狀態(tài)給定后 則在這個(gè)階段以后過(guò)程的發(fā)展不受這個(gè)階段以前各段狀態(tài)的影響 過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它未來(lái)的發(fā)展 構(gòu)造動(dòng)態(tài)規(guī)劃模型時(shí) 要充分注意是否滿足無(wú)后效性的要求 狀態(tài)變量要滿足無(wú)后效性的要求 13 5 策略 是一個(gè)按順序排列的決策組成的集合 在實(shí)際問(wèn)題中 可供選擇的策略有一定的范圍 稱為允許策略集合 從允許策略集合中找出達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略 6 狀態(tài)轉(zhuǎn)移方程 是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程 描述了狀態(tài)轉(zhuǎn)移規(guī)律 7 指標(biāo)函數(shù)和最優(yōu)值函數(shù) 用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的一種數(shù)量指標(biāo) 為指標(biāo)函數(shù) 指標(biāo)函數(shù)的最優(yōu)值 稱為最優(yōu)值函數(shù) 在不同的問(wèn)題中 指標(biāo)函數(shù)的含義是不同的 它可能是距離 利潤(rùn) 成本 產(chǎn)量或資源消耗等 動(dòng)態(tài)規(guī)劃模型的指標(biāo)函數(shù) 應(yīng)具有可分離性 并滿足遞推關(guān)系 14 小結(jié) 指標(biāo)函數(shù)形式 和 積 無(wú)后效性 可遞推 15 解多階段決策過(guò)程問(wèn)題 求出 f1 s1 從k到終點(diǎn)最優(yōu)策略子策略的最優(yōu)目標(biāo)函數(shù)值 16 1 動(dòng)態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件 簡(jiǎn)稱基本方程 要做到這一點(diǎn) 就必須將問(wèn)題的過(guò)程分成幾個(gè)相互聯(lián)系的階段 恰當(dāng)?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù) 從而把一個(gè)大問(wèn)題轉(zhuǎn)化成一組同類型的子問(wèn)題 然后逐個(gè)求解 即從邊界條件開(kāi)始 逐段遞推尋優(yōu) 在每一個(gè)子問(wèn)題的求解中 均利用了它前面的子問(wèn)題的最優(yōu)化結(jié)果 依次進(jìn)行 最后一個(gè)子問(wèn)題所得的最優(yōu)解 就是整個(gè)問(wèn)題的最優(yōu)解 二 動(dòng)態(tài)規(guī)劃的基本思想 17 2 在多階段決策過(guò)程中 動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段和未來(lái)一段分開(kāi) 又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法 因此 每段決策的選取是從全局來(lái)考慮的 與該段的最優(yōu)選擇答案一般是不同的 最優(yōu)化原理 作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì) 無(wú)論過(guò)去的狀態(tài)和決策如何 相對(duì)于前面的決策所形成的狀態(tài)而言 余下的決策序列必然構(gòu)成最優(yōu)子策略 也就是說(shuō) 一個(gè)最優(yōu)策略的子策略也是最優(yōu)的 3 在求整個(gè)問(wèn)題的最優(yōu)策略時(shí) 由于初始狀態(tài)是已知的 而每段的決策都是該段狀態(tài)的函數(shù) 故最優(yōu)策略所經(jīng)過(guò)的各段狀態(tài)便可逐段變換得到 從而確定了最優(yōu)路線 18 三 建立動(dòng)態(tài)規(guī)劃模型的步驟1 劃分階段劃分階段是運(yùn)用動(dòng)態(tài)規(guī)劃求解多階段決策問(wèn)題的第一步 在確定多階段特性后 按時(shí)間或空間先后順序 將過(guò)程劃分為若干相互聯(lián)系的階段 對(duì)于靜態(tài)問(wèn)題要人為地賦予 時(shí)間 概念 以便劃分階段 2 正確選擇狀態(tài)變量選擇變量既要能確切描述過(guò)程演變又要滿足無(wú)后效性 而且各階段狀態(tài)變量的取值能夠確定 一般地 狀態(tài)變量的選擇是從過(guò)程演變的特點(diǎn)中尋找 3 確定決策變量及允許決策集合通常選擇所求解問(wèn)題的關(guān)鍵變量作為決策變量 同時(shí)要給出決策變量的取值范圍 即確定允許決策集合 19 4 確定狀態(tài)轉(zhuǎn)移方程根據(jù)k階段狀態(tài)變量和決策變量 寫出k 1階段狀態(tài)變量 狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系 5 確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù) 建立動(dòng)態(tài)規(guī)劃基本方程階段指標(biāo)函數(shù)是指第k階段的收益 最優(yōu)指標(biāo)函數(shù)是指從第k階段狀態(tài)出發(fā)到第n階段末所獲得收益的最優(yōu)值 最后寫出動(dòng)態(tài)規(guī)劃基本方程 以上五步是建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟 由于動(dòng)態(tài)規(guī)劃模型與線性規(guī)劃模型不同 動(dòng)態(tài)規(guī)劃模型沒(méi)有統(tǒng)一的模式 建模時(shí)必須根據(jù)具體問(wèn)題具體分析 只有通過(guò)不斷實(shí)踐總結(jié) 才能較好掌握建模方法與技巧 20 例一 從A地到D地要鋪設(shè)一條煤氣管道 其中需經(jīng)過(guò)兩級(jí)中間站 兩點(diǎn)之間的連線上的數(shù)字表示距離 如圖所示 問(wèn)應(yīng)該選擇什么路線 使總距離最短 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 二 最短路徑問(wèn)題 21 解 整個(gè)計(jì)算過(guò)程分三個(gè)階段 從最后一個(gè)階段開(kāi)始 第一階段 C D C有三條路線到終點(diǎn)D A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 顯然有f1 C1 1 f1 C2 3 f1 C3 4 22 d B1 C1 f1 C1 3 1f2 B1 mind B1 C2 f1 C2 min3 3d B1 C3 f1 C3 1 44 min6 45 第二階段 B C B到C有六條路線 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 B1 B2 最短路線為B1 C1 D 23 d B2 C1 f1 C1 2 1f2 B2 mind B2 C2 f1 C2 min3 3d B2 C3 f1 C3 1 43 min6 35 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 B1 B2 最短路線為B2 C1 D 24 第三階段 A B A到B有二條路線 f3 A 1 d A B1 f2 B1 2 4 6f3 A 2 d A B2 f2 B2 4 3 7 f3 A min min 6 7 6 d A B1 f2 B1 d A B2 f2 B2 最短路線為A B1 C1 D A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 B1 B2 A 25 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 B1 B2 A 最短路線為A B1 C1 D路長(zhǎng)為6 26 練習(xí)1 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 最優(yōu)路線為 A B1 C2 D1 E2 F2 G路長(zhǎng) 18 求從A到G的最短路徑 3 27 k 5 出發(fā)點(diǎn)E1 E2 E3 28 k 2 f2 B1 13u2 B1 C2f2 B2 16u2 B2 C3 29 759 u5 E2 F2 u6 F2 G 最優(yōu)策略 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 3 30 求從A到E的最短路徑 路線為A B2 C1 D1 E 最短路徑為19 A B2 B1 B3 C1 C3 D1 D2 E C2 5 2 14 1 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 練習(xí)2 1 31 現(xiàn)有數(shù)量為a 萬(wàn)元 的資金 計(jì)劃分配給n個(gè)工廠 用于擴(kuò)大再生產(chǎn) 假設(shè) xi為分配給第i個(gè)工廠的資金數(shù)量 萬(wàn)元 gi xi 為第i個(gè)工廠得到資金后提供的利潤(rùn)值 萬(wàn)元 問(wèn)題是如何確定各工廠的資金數(shù) 使得總的利潤(rùn)為最大 據(jù)此 有下式 三 投資分配問(wèn)題 32 令 fk x 以數(shù)量為x的資金分配給前k個(gè)工廠 所得到的最大利潤(rùn)值 用動(dòng)態(tài)規(guī)劃求解 就是求fn a 的問(wèn)題 當(dāng)k 1時(shí) f1 x g1 x 因?yàn)橹唤o一個(gè)工廠 當(dāng)1 k n時(shí) 其遞推關(guān)系如下 設(shè) y為分給第k個(gè)工廠的資金 其中0 y x 此時(shí)還剩x y 萬(wàn)元 的資金需要分配給前k 1個(gè)工廠 如果采取最優(yōu)策略 則得到的最大利潤(rùn)為fk 1 x y 因此總的利潤(rùn)為 gk y fk 1 x y 33 如果a是以萬(wàn)元為資金分配單位 則式中的y只取非負(fù)整數(shù)0 1 2 x 上式可變?yōu)?所以 根據(jù)動(dòng)態(tài)規(guī)劃的最優(yōu)化原理 有下式 34 例題 設(shè)國(guó)家撥給60萬(wàn)元投資 供四個(gè)工廠擴(kuò)建使用 每個(gè)工廠擴(kuò)建后的利潤(rùn)與投資額的大小有關(guān) 投資后的利潤(rùn)函數(shù)如下表所示 解 依據(jù)題意 是要求f4 60 35 按順序解法計(jì)算 第一階段 求f1 x 顯然有f1 x g1 x 得到下表 第二階段 求f2 x 此時(shí)需考慮第一 第二個(gè)工廠如何進(jìn)行投資分配 以取得最大的總利潤(rùn) 36 最優(yōu)策略為 40 20 此時(shí)最大利潤(rùn)為120萬(wàn)元 同理可求得其它f2 x 的值 37 最優(yōu)策略為 30 20 此時(shí)最大利潤(rùn)為105萬(wàn)元 38 最優(yōu)策略為 20 20 此時(shí)最大利潤(rùn)為90萬(wàn)元 最優(yōu)策略為 20 10 此時(shí)最大利潤(rùn)為70萬(wàn)元 39 最優(yōu)策略為 10 0 或 0 10 此時(shí)最大利潤(rùn)為20萬(wàn)元 f2 0 0 最優(yōu)策略為 0 0 最大利潤(rùn)為0萬(wàn)元 得到下表 最優(yōu)策略為 20 0 此時(shí)最大利潤(rùn)為50萬(wàn)元 40 第三階段 求f3 x 此時(shí)需考慮第一 第二及第三個(gè)工廠如何進(jìn)行投資分配 以取得最大的總利潤(rùn) 41 最優(yōu)策略為 20 10 30 最大利潤(rùn)為155萬(wàn)元 同理可求得其它f3 x 的值 得到下表 42 第四階段 求f4 60 即問(wèn)題的最優(yōu)策略 43 最優(yōu)策略為 20 0 30 10 最大利潤(rùn)為160萬(wàn)元 44 練習(xí) 求投資分配問(wèn)題得最優(yōu)策略 其中a 50萬(wàn)元 其余資料如表所示 45 例 某公司打算在3個(gè)不同的地區(qū)設(shè)置4個(gè)銷售點(diǎn) 根據(jù)市場(chǎng)部門估計(jì) 在不同地區(qū)設(shè)置不同數(shù)量的銷售點(diǎn)每月可得到的利潤(rùn)如表所示 試問(wèn)在各地區(qū)如何設(shè)置銷售點(diǎn)可使每月總利潤(rùn)最大 x1 2 x2 1 x3 1 f3 4 47 46 有一個(gè)徒步旅行者 其可攜帶物品重量的限度為a公斤 設(shè)有n種物品可供他選擇裝入包中 已知每種物品的重量及使用價(jià)值 作用 問(wèn)此人應(yīng)如何選擇攜帶的物品 各幾件 使所起作用 使用價(jià)值 最大 這就是背包問(wèn)題 類似的還有工廠里的下料問(wèn)題 運(yùn)輸中的貨物裝載問(wèn)題 人造衛(wèi)星內(nèi)的物品裝載問(wèn)題等 四 背包問(wèn)題 47 設(shè)xj為第j種物品的裝件數(shù) 非負(fù)整數(shù) 則問(wèn)題的數(shù)學(xué)模型如下 用動(dòng)態(tài)規(guī)劃方法求解 令fx y 總重量不超過(guò)y公斤 包中只裝有前k種物品時(shí)的最大使用價(jià)值 其中y 0 k 1 2 n 所以問(wèn)題就是求fn a 48 其遞推關(guān)系式為 當(dāng)k 1時(shí) 有 49 例題 求下面背包問(wèn)題的最優(yōu)解 解 a 5 問(wèn)題是求f3 5 50 51 52 53 54 所以 最優(yōu)解為X 1 1 0 最優(yōu)值為Z 13 55 練習(xí)1 某廠生產(chǎn)三種產(chǎn)品 各種產(chǎn)品重量與利潤(rùn)的關(guān)系如表所示 現(xiàn)將此三種產(chǎn)品運(yùn)往市場(chǎng)出售 運(yùn)輸能力總重量不超過(guò)6噸 問(wèn)如何安排運(yùn)輸 使總利潤(rùn)最大 最優(yōu)方案 X1 0 2 0 X2 1 0 1 Z 260 56 練習(xí)2 求下列問(wèn)題的最優(yōu)解 X 2 1 0 最優(yōu)值為Z 13 57 排序問(wèn)題指n種零件經(jīng)過(guò)不同設(shè)備加工是的順序問(wèn)題 其目的是使加工周期為最短 1 n 1排序問(wèn)題即n種零件經(jīng)過(guò)1種設(shè)備進(jìn)行加工 如何安排 例1 五 排序問(wèn)題 58 1 平均通過(guò)設(shè)備的時(shí)間最小 按零件加工時(shí)間非負(fù)次序排列順序 其時(shí)間最小 即將加工時(shí)間由小到大排列即可 零件加工順序 平均通過(guò)時(shí)間 59 延遲時(shí)間 13 6 7 2 按時(shí)交貨排列順序 零件加工順序 平均通過(guò)時(shí)間 延遲時(shí)間 0 60 3 既滿足交貨時(shí)間 又使平均通過(guò)時(shí)間最小 零件加工順序 延遲時(shí)間 0 平均通過(guò)時(shí)間 61 2 n 2排序問(wèn)題即n種零件經(jīng)過(guò)2種設(shè)備進(jìn)行加工 如何安排 例二 62 經(jīng)變換為 加工順序圖如下 A B T 3 7 5 6 8 9 5 4 3 2 2 2 5 加工周期T 3 7 5 6 8 2 31 63 3 n 3排序問(wèn)題即n種零件經(jīng)過(guò)3種設(shè)備進(jìn)行加工 如何安排 例三 64 A B C T 變換 65 排序 復(fù)原 66 計(jì)算 T 6 10 8 7 6 4 3 44 計(jì)算依據(jù) 67 練習(xí) 68 一動(dòng)態(tài)規(guī)劃的基本概念和最優(yōu)化原理 1 引例 最短路問(wèn)題 假如上圖是一個(gè)線路網(wǎng)絡(luò) 兩點(diǎn)之間連線上的數(shù)字表示兩點(diǎn)間的距離 或費(fèi)用 我們的問(wèn)題是要將貨物從A地運(yùn)往E地 中間通過(guò)B C D三個(gè)區(qū)域 在區(qū)域內(nèi)有多條路徑可走 現(xiàn)求一條由A到E的線路 使總距離最短 或總費(fèi)用最小 69 第四階段 由D1到E只有一條路線 其長(zhǎng)度f(wàn)4 D1 3 同理f4 D2 4 第三階段 由Cj到Di分別均有兩種選擇 即 決策點(diǎn)為D1 決策點(diǎn)為D1 決策點(diǎn)為D2 70 第二階段 由Bj到Cj分別均有三種選擇 即 決策點(diǎn)為C2 決策點(diǎn)為C1或C2 決策點(diǎn)為C2 71 第一階段 由A到B 有三種選擇 即 決策點(diǎn)為B3 f1 A 15說(shuō)明從A到E的最短距離為12 最短路線的確定可按計(jì)算順序反推而得 即A B3 C2 D2 E上述最短路線問(wèn)題的計(jì)算過(guò)程 也可借助于圖形直觀的表示出來(lái) 72 圖中各點(diǎn)上方框的數(shù) 表示該點(diǎn)到E的最短距離 圖中紅箭線表示