運(yùn)籌學(xué)第五章動(dòng)態(tài)規(guī)劃(1)-閱讀頁
2025-05-30 15:19本頁面
【正文】 kkds kkksks2()kkdskx ky1()kkds2()kkds(2) 狀態(tài)變量： (1) 按月份分段： 4 , 3, 2 ,1k ? ； (3) 決策變量： 狀態(tài)轉(zhuǎn)移方程： (4) 允許決策集： (5) 階段指標(biāo)： 其中 表示第四階段末的狀態(tài)； 5s? ?( ) ( , ) 0 。 A1 2 3 1 2 3 1 2, , 。 ,B B B C C C D DA231132142321B2B3B1C2C3C2D1D241圖 例 （ 模型及其求解見板書 ） 逆序解法與順序解法的關(guān)系 從本質(zhì)上講 ， 兩種方法原理 (除去其方向因素外 )是相同的 ， 在具體的求解過程中 ， 也都是將原問題轉(zhuǎn)化為一系列單個(gè)問題的求解 。 一般的 ， 當(dāng)初始狀態(tài)給定時(shí) ， 用逆推法比較方便；當(dāng)終止?fàn)顟B(tài)給定時(shí) ， 用順推法比較方便 。 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃 線性規(guī)劃和非線性規(guī)劃所研究的問題 ， 通常都是與時(shí)間無關(guān)的 ， 故又可以稱為 靜態(tài)規(guī)劃 ； 兩類規(guī)劃在很多情況下原則上是可以相互轉(zhuǎn)換的 。 反過來 ， 一些靜態(tài)規(guī)劃只要適當(dāng)引入階段變量 、 狀態(tài) 、 決策變量等要素就可以用動(dòng)態(tài)規(guī)劃方法來求解 。 資源分配問題一般 包括 一種資源 和 多種資源 的分配問題 。 種產(chǎn)品的原料數(shù)量； 允許決策集： ? ?( ) 0k k k k kD s x x s? ≤ ≤； (4) 狀態(tài)轉(zhuǎn)移方程： 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?????????? ? ? ???注：利用動(dòng)態(tài)規(guī)劃基本方程進(jìn)行逐段計(jì)算 ， 最后求得即為所求問題的最大總收入 。 (6) 動(dòng)態(tài)規(guī)劃基本方程： (5) 階段指標(biāo)： ( , ( ) ) ( , ) ( )k k k k k k k k kv s d s v s x g x??； 1k k ks s x? ??； 【 例 】 某公司擁有三家連鎖商店 ， 擬將新招聘的 5名員工分配給甲 、 乙 、 丙三個(gè)商店 ， 各商店得到新員工后 ， 每年盈利情況如 表 52所示 。 這種只將資源合理分配而不考慮回收的問題 ，又稱之為 資源平行分配問題 。 第一年若以數(shù)量 投入生產(chǎn) 后 ,剩下的量 就投入生產(chǎn) ,則可以得到收入 ， 其中 和 為已知函數(shù) ， 且 。 設(shè)年回收率分別為 和 則在第一年生產(chǎn)后 ， 回收的資源量合計(jì)為 。 假設(shè)開始生產(chǎn)時(shí)完好的機(jī)器數(shù)量臺(tái) ， 試問每年應(yīng)如何安排機(jī)器在高 、 低兩種負(fù)荷下的生產(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??? ? ?? ? ??????≤ ≤表示在第 年初擁有的完好的機(jī)器數(shù)量； k此問題的 動(dòng)態(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???? ? ? ? ??????表示第 年度分配給高負(fù)荷下生產(chǎn) k(6) 動(dòng)態(tài)規(guī)劃基本方程： (5) 階段指標(biāo)： (4) 狀態(tài)轉(zhuǎn)移方程： 允許決策集為 的機(jī)器數(shù)量 , (3) 決策變量： (2) 狀態(tài)變量： ，按年份將整個(gè)過程分為 5個(gè)階段； (1) 階段變量： 設(shè)有 個(gè)城市 ， 分別用 來表示 ， 城市 之間的距離為 。 2 , 3 , 。 )k k k ks T i s u? ? ； { 2 , 3 , , 1 , 1 , , }iN i i n? ? ?； 【 例 】 求解四個(gè)城市面上旅行推銷員問題 ， 其距離矩陣如表 53所示 ， 當(dāng)推銷員從城市 1出發(fā) ， 經(jīng)過每個(gè)城市一次且僅一次 ， 最后回到 1城市 ， 問應(yīng)該按照怎樣的路線走 ，才能使得總的行程最短 ？ 表 53 例 1 2 3 4 1 0 8 5 6 2 6 0 8 5 3 8 9 0 5 4 7 7 8 0 城市 城市 距離 解 利用上面的分析很容易寫出其模型，下面直接對(duì)其求解。 在實(shí)際生活中 ， 很多問題 都可以歸納為旅行售貨商這類問題 。 注 ：動(dòng)態(tài)規(guī)劃所涉及的典型問題含有 背包問題 ， 設(shè)備更新問題等 ， 有興趣的同學(xué)可以參考其他相關(guān)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1