運(yùn)籌學(xué)第五章動態(tài)規(guī)劃(1)-wenkub
2023-05-21 15:19:43 本頁面
【正文】 動態(tài)規(guī)劃所解決的問題 ： 多階段問題 動態(tài)規(guī)劃的核心 。 應(yīng)用 :工程、軍事和商業(yè)等領(lǐng)域 優(yōu)缺點(diǎn) :適用范圍廣，模型算法一體化，方便編程。 該倉庫的最大容量為 1000件 ， 每月中旬定購商品 ， 并于下月初取到訂貨 。 (4) 寫出狀態(tài)轉(zhuǎn)移方程； (5) 指出階段指標(biāo)及指標(biāo)函數(shù)； 動態(tài)規(guī)劃的原理與求解 動態(tài)規(guī)劃的最優(yōu)化原理 下面我們先研究一下例 。 注 ：而事實(shí)上 ， 從各點(diǎn)到 的最短路線和最短路線距離都求出來了 。 0 1 0 0 0 ( )k k k k k k k k kD s x y y s x s y? ? ?≤ ≤ ≤ ≤4, 3, 2,1k ?11 , 500k k k ks s x y s? ? ? ? ?(6) 動態(tài)規(guī)劃基本方程： ? ?11( , ) ( )55( ) m a x ( , , ) ( )( ) 0 4 , 3 , 2 ,1k k k kk k k k k k k kx y D sf s v s x y f sf s k???? ????????求解 （ 要求板書 ） ( , , )k k k k k k k kv s x y q y p x?? 4, 3, 2,1k ?， ； 輔圖 1 輔圖 2 輔圖 3 動態(tài)規(guī)劃的順序解法 【 例 】 圖 ， 為水庫 ， 分別為不同的供水目的地 ， 試找出給各供水目的地供水的最短路線 。 但是 ， 兩種方法各有優(yōu)勢 ， 如前向法求解例 ， 有明顯的優(yōu)勢 。 動態(tài) 規(guī) 劃 可 以 看 作 是 求 使 得 指 標(biāo) 函 數(shù) 達(dá)到最優(yōu)的極值問題 ， 狀態(tài)轉(zhuǎn)移方程 ， 起始條件以及允許狀態(tài)集 ， 允許決策集等是約束條件 ， 原則上它可以用線性規(guī)劃或非線性規(guī)劃方法求解 。 一種資源分配問題可敘述如下 ：設(shè)有數(shù)量為 的某種資源 ， 用于生產(chǎn) 種產(chǎn)品 ， 若以數(shù)量為 的資源投入第 種產(chǎn)品的生產(chǎn) ， 其收益相應(yīng)的為 ， 問如何分配這種資源 ， 才能使得生產(chǎn) 種產(chǎn)品的總收入最大 ？ anix i()iigxn(3) 決策變量： (2) 狀態(tài)變量： , 1, ,1k n n?? 其靜態(tài)規(guī)劃的數(shù)學(xué)模型的形式一般為： 1m a x n iiif g x?? ?10 1 2niiixax i n?? ???? ???， ， ， ，≥ 轉(zhuǎn)化成動態(tài)規(guī)劃模型為： (1) 階段變量： ks 表示分配用于生產(chǎn)第 種產(chǎn)品至第 k nkx 表示分配給生產(chǎn)第 種產(chǎn)品的原料數(shù)， k,這里把資源分配給一個(gè) 或者幾個(gè)使用者的過程作為一個(gè)階段。 問分配給各商店各多少員工 ， 才能使得公司的總盈利最大 ？ (單位：千元 ) 表 52 分配新員工后，甲、乙、丙三個(gè)商店每年盈利情況 (單位：千元 ) 0 1 2 3 4 5 甲 0 3 7 9 12 13 乙 0 5 10 11 11 11 丙 0 4 6 11 12 12 工 人 數(shù) 盈 利 數(shù) 商 店 （ 求解見板書 ） 在實(shí)際中 ， 如銷售后分配問題 、 機(jī)器設(shè)備分配問題 、貨物分配問題 、 投資分配問題等等 ， 均屬于這類資源分配問題 。 這種資源在投入到 、 生產(chǎn)后 ， 年終還可以回收再投入生產(chǎn) 。 一個(gè)推銷商從城市 1 出發(fā)到其他每個(gè)城市去一次且只去一次 ， 最后回到城市 1， 問怎樣選擇行走路線 ， 才能使得行走總路程最短 ？ ,ijn 1, 2, ,nijd其 動態(tài)規(guī)劃模型 如下： 1, ,1kn??ks將從城市 1到 城市的中間城市集合用 i表示第 階段到達(dá) 城市之 k i 旅行推銷商問題 { 2 , 3 , , 1 , 1 , , }iN i i n? ? ?表示， i 城 ， 規(guī)定推銷員是從城市 1開始的 ， 設(shè)推銷員走到 (2)狀態(tài)變量： 按經(jīng)過城市的個(gè)數(shù)來分段 ， (1) 階段變量： 1n? 個(gè)階段 ， 將整個(gè)過程分為 問題 一般描述 如下： ； 前中途所經(jīng)過的城市的集 ， 則有 ， 其中 ， 因此 ， kisN? ksk?可選取 作為描述過程的狀態(tài)變量； ( , )kisku表示推銷商在狀態(tài) 下前往的下一個(gè)城 ( , )kisijd表示從城市 到城市 的距離； i j( , )kkf i s 表示從城市 1經(jīng)過 個(gè)城市 到達(dá)城市 kksi? ?101( , ) m i n ( , \ { } )( , ) , 1 , 2 , , 1 。 邊界條件為 0 12 0 13 0 14( 2 , ) 8 , ( 3 , ) 5 , ( 4 , ) 6f d f d f d? ? ? ? ? ? ? ? ?1 0 321 0 421( 2 , { 3 }) ( 3 , ) 5 9 14( 2 , { 4 }) ( 4 , ) 6 7 131k if f df f d?? ? ? ? ? ?? ? ? ? ? ?， ：當(dāng) 時(shí) 即 從 城 開 始 ， 中 間 經(jīng) 過 一 個(gè) 城 到 城 的 最 短 距 離 是1
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1