運籌學(xué)第五章動態(tài)規(guī)劃(1)(存儲版)
【正文】 盈 利 數(shù) 商 店 （ 求解見板書 ） 在實際中 ， 如銷售后分配問題 、 機器設(shè)備分配問題 、貨物分配問題 、 投資分配問題等等 ， 均屬于這類資源分配問題 。 動態(tài) 規(guī) 劃 可 以 看 作 是 求 使 得 指 標 函 數(shù) 達到最優(yōu)的極值問題 ， 狀態(tài)轉(zhuǎn)移方程 ， 起始條件以及允許狀態(tài)集 ， 允許決策集等是約束條件 ， 原則上它可以用線性規(guī)劃或非線性規(guī)劃方法求解 。 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ī)劃的順序解法 【 例 】 圖 ， 為水庫 ， 分別為不同的供水目的地 ， 試找出給各供水目的地供水的最短路線 。 (4) 寫出狀態(tài)轉(zhuǎn)移方程； (5) 指出階段指標及指標函數(shù)； 動態(tài)規(guī)劃的原理與求解 動態(tài)規(guī)劃的最優(yōu)化原理 下面我們先研究一下例 。 應(yīng)用 :工程、軍事和商業(yè)等領(lǐng)域 優(yōu)缺點 :適用范圍廣，模型算法一體化，方便編程。 核心 : 在于將問題公式化，也可以說，動態(tài)規(guī)劃是將多階段決策問題進行公式化的一種技術(shù)。 很顯然 ， 要建立動態(tài)規(guī)劃問題的模型 ， 一般可按以下 步驟 來進行： (1) 把問題的過程劃分為恰當?shù)膫€ 階段 ， 引入階段變量 ； nk(2) 正確選擇狀態(tài)變量 ，使它既能描述過程的演變，又能滿足無后效性，同時給出狀態(tài)可能集 ； kskS(3) 確定決策變量 及每個階段的允許決策集 ； ()kkds ()kkDs(6) 寫出最優(yōu)函數(shù) 。 解 由 ， 例 ： ks表示第 個月月初的庫存量； k 表示第 個月已有庫存 的情況下，要定購的商品量， 表示第 個月已有庫存 的情況下，要銷售的商品量 (為方便，后面將分別依次用 ， 來代替 和 )； 1()kkds kkksks2()kkdskx ky1()kkds2()kkds(2) 狀態(tài)變量： (1) 按月份分段： 4 , 3, 2 ,1k ? ； (3) 決策變量： 狀態(tài)轉(zhuǎn)移方程： (4) 允許決策集： (5) 階段指標： 其中 表示第四階段末的狀態(tài)； 5s? ?( ) ( , ) 0 。 動態(tài)規(guī)劃和靜態(tài)規(guī)劃 線性規(guī)劃和非線性規(guī)劃所研究的問題 ， 通常都是與時間無關(guān)的 ， 故又可以稱為 靜態(tài)規(guī)劃 ； 兩類規(guī)劃在很多情況下原則上是可以相互轉(zhuǎn)換的 。 (6) 動態(tài)規(guī)劃基本方程： (5) 階段指標： ( , ( ) ) ( , ) ( )k k k k k k k k kv s d s v s x g x??； 1k k ks s x? ??； 【 例 】 某公司擁有三家連鎖商店 ， 擬將新招聘的 5名員工分配給甲 、 乙 、 丙三個商店 ， 各商店得到新員工后 ， 每年盈利情況如 表 52所示 。 假設(shè)開始生產(chǎn)時完好的機器數(shù)量臺 ， 試問每年應(yīng)如何安排機器在高 、 低兩種負荷下的生產(chǎn) ， 使得五年內(nèi)的產(chǎn)品總產(chǎn)量最高 ？ y18gx? 1x ??5hy???1 1000s ?此問題的 靜態(tài)規(guī)劃模型 ： ? ?511m a x 8 5 ( )0 .7 0 .9 ( )0 , 1 , 2 , , 5i i iik k k kkkz x s xs x s xx s k??? ? ?? ? ??????≤ ≤表示在第 年初擁有的完好的機器數(shù)量； k此問題的 動態(tài)規(guī)劃模型 ： 5, ,1k ?ks()k k kd s x?? ?( ) 0 ,k k k k k kD s x x s x Z??≤ ≤1 ( )k k k ks x s x? ? ? ?( , ) 8 5 ( )k k k i i iv s x x s x? ? ?? ?11()66( ) m a x 8 5 ( ) ( )( ) 0k k kk k k k k k kx D sf s x s x f sfs???? ? ? ? ??????表示第 年度分配給高負荷下生產(chǎn) k(6) 動態(tài)規(guī)劃基本方程： (5) 階段指標： (4) 狀態(tài)轉(zhuǎn)移方程： 允許決策集為 的機器數(shù)量 , (3) 決策變量： (2) 狀態(tài)變量： ，按年份將整個過程分為 5個階段； (1) 階段變量： 設(shè)有 個城市 ， 分別用 來表示 ， 城市 之間的
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1