運籌學第五章動態(tài)規(guī)劃(1)-免費閱讀
【正文】 在實際生活中 ， 很多問題 都可以歸納為旅行售貨商這類問題 。 設年回收率分別為 和 則在第一年生產后 ， 回收的資源量合計為 。 種產品的原料數量； 允許決策集： ? ?( ) 0k k k k kD s x x s? ≤ ≤； (4) 狀態(tài)轉移方程： 11()11( ) m a x { ( ) ( ) }( ) 0 , 1 , ,1k k kk k k k k kx D Snnf s g x f sf s k n n?????????? ? ? ???注：利用動態(tài)規(guī)劃基本方程進行逐段計算 ， 最后求得即為所求問題的最大總收入 。 一般的 ， 當初始狀態(tài)給定時 ， 用逆推法比較方便；當終止狀態(tài)給定時 ， 用順推法比較方便 。 E 動態(tài)規(guī)劃最優(yōu)性原理 ： “ 作為整個過程的最優(yōu)策略具有這樣的性質 ， 即無論過去的狀態(tài)和決策如何 ， 對前面的決策所形成的狀態(tài)而言 ， 余下的諸決策必然構成最優(yōu)策略 。 據估計：今后四個月這種商品的購價和售價 ， 如 表 51所 示 。 動態(tài)規(guī)劃的應用。 圖 例 動態(tài)規(guī)劃的基本概念和模型 動態(tài)規(guī)劃的基本概念 下面結合實例來介紹動態(tài)規(guī)劃的基本概念： 【 例 】 如圖 ， 在處有一水庫 ， 現需從點鋪設一條管道到點 ， 弧上的數字表示與其相連的兩個地點之間所需修建的渠道長度 ， 請找出一條由到的修建線路 ， 使得所需修建的渠道長度最短 。 1 ( ) 12fA? ， 13()d A AB? 。 , , 。 12, , , ,nd d d 1 1 2( , , , )nnv d d d【 例 】 用順序法和逆序法求解下面靜態(tài)規(guī)劃 21 2 31 2 3m a x 4 8 2 12100 , 1 , 2 , 3if x x xx x xxi? ? ? ?????? ?? ≥（ 順序法和逆序法 模型及其求解見板書 ） 動態(tài)規(guī)劃應用舉例 資源分配問題 所謂 資源分配問題 ， 就是將數量一定的 一種或若干種資源 (如資金 、 原材料 、 機器設備 、 勞動力 )恰當的分配給 若干個使用者 ， 從而使得 總的經濟效益最大 。 在資源分配問題中，還有一種要考慮資源回收利用的問題，這里決策變量為連續(xù)值，故又可以稱之為 資源連續(xù)分配問題 ，這類分配問題的 一般敘述 如下 : 第二年再將資源數量 中的 和 分別投入到 、 兩種生產 ， 則第二年又可以得到收入為 ， 如此繼續(xù)進行 年 ， 試問：應該如何決定每年投入生產 的資源量 ， 才能使得總的收入最大 ？ 2s 2x 22sx? A B2 2 2( ) ( )g x h s x??n A12 nx x x、 、 、 設有數量為 的某種資源 ， 可投入 和 兩種生產 。kk k k k jijsi k if i s f j s j df i d k n i n s N???? ????? ? ? ? ???(7) 動態(tài)規(guī)劃基本方程： 的最短路線的距離； (6) 最優(yōu)函數： (5) 階段指標： (4) 狀態(tài)轉移方程： 允許決策集為 : (3) 決策變量： j市 ； 1 ( , 。 小 結 動態(tài)規(guī)劃所解決的問題； 動態(tài)規(guī)劃是一種技術，是一種思想 ； 動態(tài)規(guī)劃模型及求解； 動態(tài)規(guī)劃的優(yōu)缺點； 用動態(tài)規(guī)劃可以求解靜態(tài)規(guī)劃； 。 一個推銷商從城市 1 出發(fā)到其他每個城市去一次且只去一次 ， 最后回到城市 1， 問怎樣選擇行走路線 ， 才能使得行走總路程最短 ？ ,ijn 1, 2, ,nijd其 動態(tài)規(guī)劃模型 如下： 1, ,1kn??ks將從城市 1到 城市的中間城市集合用 i表示第 階段到達 城市之 k i 旅行推銷商問題 { 2 , 3 , , 1 , 1 , , }iN i i n? ? ?表示， i 城 ， 規(guī)定推銷員是從城市 1開始的 ， 設推銷員走到 (2)狀態(tài)變量： 按經過城市的個數來分段 ， (1) 階段變量： 1n? 個階段 ， 將整個過程分為 問題 一般描述 如下： ； 前中途所經過的城市的集 ， 則有 ， 其中 ， 因此 ， kisN? ksk?可選取 作為描述過程的狀態(tài)變量； ( , )kisku表示推銷商在狀態(tài) 下前往的下一個城 ( , )kisijd表示從城市 到城市 的距離； i j( , )kkf i s 表示從城市 1經過 個城市 到達城市 kksi? ?101( , ) m i n ( , \ { } )( , ) , 1 , 2 , , 1 。 問分配給各商店各多少員工 ， 才能使得公司的總盈利最大 ？ (單位：千元 ) 表 52 分配新員工后，甲、乙、丙三個商店每年盈利情況 (單位：千元 ) 0 1 2 3 4 5 甲 0 3 7 9 12 13 乙 0 5 10 11 11 11 丙 0 4 6 11 12 12 工 人 數
環(huán)評公示相關推薦
鄂ICP備17016276號-1