【天津大學】《運籌學》(精品課) P29 - 29. 應用舉例 教學錄像(3)

长安书院_
146粉絲
1 次觀看·2026年10月3日
AI 生成·可能包含錯誤
同學們好
我們已經學了動態規劃的原理和基本的方法
今天我們再做一些個練習題
下面請看我們的課件
第一個練習題是這樣的
我們從課件看一下
某個旅行者準備駕車從A城到E城
他不在意形態的長短
而最關心最小化他在駕駛過程中遇到的最大海拔高度
這個圖給出了從A城到E城可能的路徑
每條路上的數字是這段道路的最大海拔高度
是用動態規劃方法確定這個旅行者應選擇的線路
我們看到這個圖以後很容易想到最短路問題
那麼這個問題和最短路問題在有些方面確實是相同的
但是他問題的提法並不相同
因爲在這裏他不是尋找A到E的最短路
而是要尋找這條線路上最大的海拔高度最小
當然這個問題在其他的方面和最短路問題還是有相似之處
比如說他這個問題劃分的階段那麼和最短路一樣的
我們在這個圖裏頭他已經人爲的把它分爲了四個階段
那麼每一個階段的狀態在這裏依然是選擇初始的位置
那麼每一個狀態下的決策也是在這個位置下可能向前走的路
那麼這裏的狀態轉移關係以及狀態集合決策集合
那麼和最短路問題都是一樣的
那麼這個問題和最短路問題很大的不同在於
它的地推關係是不一樣的
換句話說他是要尋找一條線路上最大的海拔高度最小
因此在這裏頭它這條線路上每一段的它的最大海拔高度
要和下一段比如我們轉移後到前面一段
整個的這一個可以說在動態圖畫中相當於一個後步子過程
要在這個裏頭尋找這個海拔的最大高度
但是作爲一個狀態下我們它的最優質版函數
那又是要尋找不同決策下帶來的相應的後步子過程
或者說後步子策略中對應的指標函數中的最小
因此這個問題它的基本的地推關係
我們大家可以看到應該是這樣的
所以咱們可以看看這個課件上也有
那麼在這個裏頭在我們這個顯示器裏頭也有
大家可以看到它這是
這個是在SK狀態下做某一個決策XK
那麼相應的階段指標
換句話說就是這個從這走的一段路
這樣的最大海拔高度
那當然這個是相應的狀態轉移
就是說你從這裏頭做這個決策
那麼狀態轉移到下一個相應的狀態
那麼這個狀態下相應的最優質版函數
這兩個先取最大值
而在不同的決策中在它的決策集合中
選擇不同的決策的話
那麼我們是要取得這個最大值中的
幾個最大值中的最小
所以它的基本的遞遞關係
是和前面我們講的動態固化
都有一些不太一樣
那是這個問題的出點
其實它做起來的話當然是非常好做的
下面我們可以回到客店來看一看
我們看看這個問題
那麼按照逆序遞遞
首先是第四階段
第四階段可能的狀態那麼很簡單
一個是第一一個是第二一個是第三
那麼在這裏的話
每一個狀態下的最優質版函數
很顯然就是相應的這個階段指標
因爲後邊已經到頭了
所以這樣的話我們很容易得到
第一這個狀態下的最優質版函數
那就是這個階段指標就是13
那麼第二的話呢
最優質版函數當然就是這個8
第三個最優質版函數值是這個9
相應的最優的Hobbs策略
這些都給出來
或者說最優的決策
這裏可以得到的
那是K等於4
那麼我們在下邊看
第三階段
第三階段可能的狀態
也就是狀態集合是C1和C2
那麼我們分別來看
作爲C1來說
它的決策集合
那顯然它是有三個
它可以選擇
它可以選擇C1到D1
也可以選擇C1到D2
也可以選擇C1到D3
那麼我們按照剛纔我們說的
基本的遞退關係
那麼它選擇C1這個決策的時候
這一段的最大海拔高度是8
而到了D1以後
按照動態掛的原理
利用在這個狀態下的
最優質版函數值
當然這個問題非常簡單了
實際上就是後邊這個
實際上還是後邊這個
這段路的一個最大的海拔高度
所以要取得這個值
我們大家可以看到
做這個決策
階段指標是8
然後相應的狀態轉移到D1
利用D1的最優質版函數值
當然這是13
那麼就是做這個決策
如果做C1到D2的決策
當然就是這樣做
如果C1到D3的決策
那就是這樣做
最後這個三個不同的決策
要看看誰的最小
誰的最小
那這個我們當然可以算出來
這樣算出來的結果
是C1到D2
C1到D2
這個最大的海拔高度是最小的
那麼同樣道理
對於C2
我們也可以做同樣的分析和計算
這是對於C2的計算
這也是對於C2的計算
那這樣的話
我們在第三階段
可能的狀態下
最優質版函數也都做完了
那麼下面我們再看第二階段
在第二階段
第二階段的狀態很少
狀態只有兩個
其實狀態
對不起這裏狀態的話有三個
是B1 B2 B3
那我們分別做相應的計算
在B1它的決策只有一個
所以在這裏的話
只是做唯一的一個決策
它的階段值班是9
那麼到了C1
利用C1
這個狀態下
我們已經得到的
最優質版函數值
那就是這個8
因爲大家從這個簡單圖可以看到
實際上我們已經得出了
從這裏
實際上是這個
這是最優的厚布斯策略
所以它相應的
最優質版函數值應該是8
那在這裏的話
我們要做一個比較
這個9和8
去最大的
最大當然是最小
當然就沒什麼比較
因爲它只有一個決策
那麼B2的話呢
也只有一個決策
是這樣
這個做起來比較簡單
作爲B3
B3這個狀態
它的決策是兩個
它只有兩個決策
那麼這時候我們可以看到
這個時候呢
我們在這個課件上
在這個投影機上可以看到
這個時候
我們可以看到
作爲B3
我們給大家看
作爲B3
做這個決策的話
相應的階段指標是11
這是11
那麼到了C1以後
還利用C1已經得到的
前幾段已經得到的
最優質版函數值
利用這個
當然這個我們前面
做出來是18
然後這兩個先取自打值
同樣的話
如果我們做這個決策
到C2
那利用C2情況下的
最優質版函數值
這已經得到也是8
那麼這個階段指標的話
就是這段是7
這段是7
所以這兩個取自打值
這兩個取自打值
然後兩個自打值中
取最小
當然這個我們可以得到
最後的結果的話呢
因爲這個是
自打值是11
這個自打值是8
最後得到是8
那就應該是在B3的
這個狀態下的
最優質版函數值
應該是8
那麼相應的
它的這一步的
最優的決策
是B3到C2
B3到C2
對吧
這是K等於2的情況
下面我們來看看
在K等於1的情況
K等於1的情況
這個更簡單了一些
這個更簡單
因爲在這裏的話
狀態只有一個
就是A
它可能的決策是三個
一個是這樣走
一個這樣走
那麼做這個決策
做這個決策
狀態轉移到B1
利用B1
我們已經得到的
最優質版函數值
也就是這個值
這個F2B1
這個它本身的
階段指標值是10
所以這兩個先取最大值
同樣的話
如果做這個決策
由A到B2
那麼階段指標是7
然後利用這裏
我們已經得到的
B2的最優質版函數值
那麼如果說
做這個決策
它的階段指標是6
然後狀態轉移到B3
利用B3
這個狀態下的
最優質版函數值
這些先求最大
然後這三個最大值
再求最小
那麼最後得到這個結果
那麼從這裏的話
我們可以看到
它這一步的最優決策
是A到B2
或者是A到B3
那麼把前面
我們已經得到的結果
合在一起
它前面我們得到的結果
合在一起的話
那麼整個這個問題的
最優的策略
從一開始的最優策略
那我們很容易得到的話
這個是由A、B2到C1到D2到E
或者是A、B3到C2到D2到E
那麼是這個問題的
一個求解的過程
所以總的來說
這個問題本身
它並沒有其他的特別的地方
只是它的
我們基本的
這個地區關係中
尤其是從指標函數
和階段指標
它的關係中
那我們主要是
先是求最大值
就在幾個最大值
再求最小
那這個和我們以前
學過的有些不一樣
但是這個完全符合
動態規劃的一些基本原理
這是一個練習
下面我們來看第二個練習
第二個練習是
一個很簡單的練習
那麼這個練習的話
本身的話
我們看起來
本身的話
我們看它是一個
本身的話
這是一個非線域規劃的形式
那我們還是回到
這個科技上
可能看得更清楚一些
我們看看
這個非線域整數規劃
是這樣一個情況
大家比較簡單了
它的木辦函數
當然是個非線域函數
然後它的約束條件
如果按我們以前講過的
相當於結構約束條件
只有一個
當然這裏頭還有一個
是非附條件
另外它是個整數的
它是個非線域整數規劃
那麼這裏的話
只有這個
從
作爲動態圖畫
可求解的這樣的問題來講
那麼它的
紙邊函數
應該是可分離的
當然這個問題
一看我們就可以看到
可分離的
實際上在這個問題中
相當於
G1 X1
那就是X1
那G2 X2
就是X2
唯獨G3 X3
是一個
已經知道的一個
特定的函數
這是個特定的函數
對吧
那麼這個問題的要求
就是用
準備用動態圖畫
來求這個問題
但是它並沒有
要求做全過程
只是要求一部分
第一
寫出以下表達式
或者集合的具體內容
這是它的一些要求
然後第二個
只需要計算
某一個階段的
某一個狀態的
自由紙邊函數
對吧
所以這裏頭
介紹的話是
計算第二階段
狀態爲12時的
自由紙邊函數
那依據它的相應的決策
對吧
那下邊我們看看
這個問題的
求解情況
那麼這個問題的
狀態轉移方程
很簡單
是Sk加1
等於Sk減去Xk
因爲這相當於
一個自然分配問題
已經用到了
已經用到了一部分
然後剩下的
是下一階段
總的一個狀態
對吧
那麼它的遞推關係
大家注意
這是相乘的
對吧
因爲這是由它的
這個問題的
由這個問題的
原問題的目標函數
所決定
對吧
因爲這裏頭
本身是一個相
我們可以看到
這是一個
階段紙邊
這是一個階段紙邊
相乘的關係
對吧
那麼第一階段的
狀態集合
這個我們從
這個問題本身
已經聯繫到
我們前面講過的
自然分配問題的
特別是依爲
自然分配問題的例子
那麼第一階段的
狀態集合
這階段是20
那麼第二階段
狀態爲5的時候
允許決策集合
那麼顯然應該是
因爲取整數
取整數
所以顯然是
0、1、2、3、4、5
對吧
也就是說到了
你分配到第二個
相當於我們前面
講過的
自然分配問題
分配到第二個部門
分配到第二個部門的話
那麼一共
你有五單位的資源
這五單位的資源
那麼你對於
第二個部門來講
你可以給它分配的量
可以給它分配的量
顯然是
0、1、2、3、4、5
都可以
對吧
所以這個時候
我們回到課件上
這個時候
它的決策集合
應該是這個樣子
對吧
所以這個事應該說
很好表達的
那麼作爲
下一個
下一問的話呢
我們看一看
計算第二階段
狀態爲12時的
自由值、半數值
對吧
那麼這個時候
我們可以看到
也就是算
F2、12
對吧
狀態是12
第二階段狀態爲12
對吧
那麼我們想到
狀態爲12的時候
這個時候
可能的決策
對吧
到第二階段
這個時候
你分配的總的資源量
是12
而且按照整數分配
那麼這個時候
很顯然
相應的決策
那就是
0、1、2、3、4、5、6、7、8、9
是一直到實際12
對吧
所以是這樣一些決策
那麼由這些決策
帶來的狀態轉移
那也非常簡單
如果你一共是12
你給一個第二階段是0
那麼到了第三階段的話
那麼相應的總量
那就是12
對吧
如果你分配給這個1
那相應的到後面
那就是11
所以這個也是非常簡單的
和我們前面的資源分配問題
完全一樣
對吧
所以這裏頭
這個道理非常簡單
只不過在計算的時候
也就是說
你要用到
第三階段的自由指標函數
而第三階段的自由指標函數
在這個問題中的話
實際上就相當於
它的階段指標
對吧
因爲第三階段是最後一階段
對吧
那麼這樣一來的話
我們可以根據
已知的這個條件
把相應的第三階段
不同的這個
狀態的情況下
它的自由指標函數
把它得到
對吧
所以這個我們看看
這個表達式的話
這裏寫的沒有
沒有完全寫全
但是已經寫的比較清楚了
對吧
那這個0
這個0相當於什麼呢
相當於我們
按動態研究科
按動態化的DP關係來講
相當於是
V2
X2
對吧
就是說
決策是0
決策是0的時候
是階段指標
對吧
那麼這時候剛纔說了
你這個
你這裏分配是0的話
那狀態轉移
到下一個階段的話
當然是12
到下邊來分配的話
那個總量應該是12
對吧
那其他的也一樣
其他的
這是1
那這是11
這是2
這是10
對吧
我這裏寫的
已經把相應的
階段指標都寫了
因爲在
對於第二階段來講
我們從這條件
對於第二階段來講
它的階段指標
它的收益函數
就是X2
對吧
等於X2是0
那這個值就是0
這個階段指標就是0
對吧
那麼
對於
第三階段的話呢
我們剛纔說了
第三階段又是最後一個階段
對吧
而且這個收益本身的話呢
不管怎麼樣
G3
X3
對於X3來講
它是一個不減函數
所以這樣的話
那你
剩下的資源
應該都給它
這是毫無疑問
對吧
剩下的資源應該都給這個
都給這個
對吧
那麼
那麼這樣一來的話
我們可以看到
我們就分別算一下
你看
這個是
因爲這是相乘的關係
如果它是0
那當然不管它等於
這還是0
對吧
如果是1
那這個應該是11
11的話
作爲第三階段
那麼
它的最後值萬數
剛纔說了
它實際上也就是
也就是相應的
階段指標
相應的階段指標
所以我們從這裏可以看到
對吧
如果是
它在11
就在這個範圍裏頭
那應該是
三十分之三
乘上X3
所以應該
是三十分之三
乘上11
所以這裏是
三十分之三
是吧
那麼其他的
我們就不一一的說了
是吧
那麼經過這些數值的比較
我們可以知道
這個是最大的
是吧
也就是說這個時候
是相當於
決策爲9的時候
這個時候是最大值
那麼相應的
這個最後值萬數是27
是吧
這個時候
也是我們要求的
第二階段
狀態是12的時候
相應的最後值萬數
最後值萬數值是27
那麼這個時候
相應的最後決策
是9
也就是說
如果你在
按照動態的話
你分配這些資源
到第二部門
總量12的時候
那麼給第二部門的
分配量
最佳的分配量
應該是9
是吧
應該是9
是吧
所以這個是我們
這個問題
是吧
下面我們再看
這個練習三
是吧
練習三實際上也是
是一個相當於
一個設備更新問題
和我們前面
介紹的設備更新問題的
例子
那基本上是一樣的
但是它有些
微細微的地方
那先我們注意一下
是吧
那麼現在我們看看
這個問題本身
是吧
就是某個企業
一個產品的生產中
用到一種檢測儀器
預測今後五年年初
購買價格
CK如表1
是吧
這是表1
是吧
這是根據預測的
根據測的逐年
有些變化
是吧
當然這前兩年沒什麼變化
後邊也稍微有些漲
是吧
那麼爲了保持
必要的精度
該儀器最多使用三年
就要淘汰更新
是吧
那麼這一點呢
我們要注意
它會隱藏在
我們不同的階段的話
那麼相應的狀態集合
是吧
因爲它換句話說
這個時候
你這設備最多
是用三年
是吧
你不可能有一個
到了比如到第四年
第五年
那麼你的設備
它的已經使用的時候
已經超過三年
那這是不可能的
所以我們要注意
是吧
那麼淘汰的儀器
可以有償轉讓
那麼有償轉讓
給其他的要求
經過交接的企業
那麼預測
使用了T年後的儀器
轉讓收入
轉讓收入是NT
是吧
這是轉讓的收入
是吧
那麼購置新儀器
在使用T年後
再有一年的運用費用
這個也有表
運用表
是吧
這個一般的是
隨着E0的話
應該是相對的低增的
是吧
因爲這個和我們前面
這個設備更新問題的
假定是一樣的
是吧
那麼現在
這個企業的話
需要制定該儀器
五年的更新計劃
使總的成本最小
是吧
這個是五年末的儀器
我們假定是不再用了
是吧
所以這樣的話
它可以把它
它的應用的
因爲到了五年
它已經不再用了
它可以把這個儀器
轉讓給別人
那麼有一定的所得
抵消成本
是吧
那麼這個問題
也可以用動態化來求解
是吧
這是相應的儀式條件
那麼我們看看
第一要求
如果選擇
D開年初
儀器已使用的年數
爲狀態變量SK
是吧
這地方相當於E0
這和我們前面講的
設備更新問題是一樣的
是吧
就是以設備的這個
E0
以設備的E0
作爲這個狀態
是吧
寫出決策變量SK
還有決策集合
狀態軟儀方程
階段指標
以及還有
以及按照秩序
遞推的這個
遞推方程
是吧
還有相當於
相當於這個
這個第五階段
和第四階段的
狀態集合
是吧
第五階段和第四階段的
狀態集合
是吧
這是第一個要求
是吧
那麼第二個要求的話呢
就是要寫出計算
計算的過程
和最終的結果
是吧
那麼這個問題
剛纔我們說過
它和我們前面講過的
設備更新問題
其實本質上是一樣的
是吧
唯一的一點差別的話
一個就是
它有一個三年淘汰
所以這時候
我們考慮
不同的階段
那麼它的狀態集合
會有些影響
是吧
注意這個問題
是吧
再有一個問題呢
這個問題
我們前面講
設備更新問題
我們是用的
收益的一個函數
是吧
用的收益的函數
是吧
那麼在這裏的話呢
是用的成本
用的成本函數
是吧
就是它要追求
總成本最小
那麼作爲成本的話
這裏要注意
就是說
那些淘汰的設備
你轉讓所得
那麼這個的話呢
作爲成本來講
它就是個負成本
是吧
它可以抵消嘛
可以抵消一部分
這個成本
是吧
所以這個我們注意點
另外這個問題
我們要注意到
它的終端條件
是吧
因爲它說了
五年以後
這個設備不用了
不用了以後呢
那你現有的設備呢
你要把它轉讓
轉讓以後
有一定的收入
這個收入
你要記錄
這個終端條件
是吧
這樣可能做起來
這樣做起來
纔是正確的
那下邊我們看看
這個問題呢
相應的糾結
爲了方便
我們把有
某些用得到的
一致條件
我們標在這裏
是吧
這個問題的決策變量
如同我們講過的
設備更新問題一樣
我們是隻有兩個
就是你到了某年初
你的決策
要麼就是接着用
要麼就更新
是吧
我們以零一點兩的表達
是吧
以一表示繼續使用
以零表示更新
是吧
那麼決策集合
這個我們稍微分析的細一點
是吧
嚴格的講
或者籠統的說
我們這個決策集合
你可以都是零和一
但是這裏有些細微的差別
是吧
所以如果我們做的
稍微細一點的話呢
我們可以看到
你看看
當這個SK小於等於二
是吧
也就是說
當你這個設備
你的一零
是小於等於二
是吧
這個時候呢
那當然這個相應的決策
相應的決策是一和零
一和零
但是如果你已經用了三
你已經用了三年
按照我們這個問題的要求
已經用了三年
那你的決策只能是零
那你必須更新
對吧
那麼相應的狀態轉移的關係
我們可以看到這裏頭
一些細微的地方
大家注意點
相應的狀態轉移關係
就是SK加一
等於SK
加上一
就是如果繼續用
你看繼續用
那應該這樣
當然繼續用的條件的話呢
那就還得
它的本身的一零
已經是小於等於二
已經小於等於二
所以這是
企業的關係
是吧
那麼
如果是你決策是更新
或者說你的一零
已經達到了這個三年
但這個條件
如果我們不寫
也問題不大
因爲前面我們有這個要求
對吧
這已經有了要求
是吧
那麼這個時候呢
你顯然你前一年你更新了
那麼再過一年
那一零是一
是吧
這在我們前面講過的
設備更新問題
其實也這樣表達的
是吧
那麼階段指標的話呢
這個問題
因爲這是成本
是吧
所以這裏你看有維修費用
是吧
另外還有更新的這個成本
有更新的成本
是吧
這更新的成本
注意它只花費減去
它相應的一個轉讓費用
是吧
也可以叫一個廣義的殘值
是吧
當然這個的話
只有當什麼呢
只有當你更新的時候有
是吧
所以這個
這個答案是
如果我們按照xk
它本身是一個零一電量
把它分別來表達的話呢
那就應該是這個樣子
應該這個樣子
是吧
那麼地推關係
或者說基本的地推方程
這個我們可以看到
基本的表達是
是這個樣子
是吧
但是這裏頭注意到
這個終端條件
是吧
注意到這個終端條件
是吧
終端條件的話那就看了
你到了第六年初
你這個設備
它已經用了多長時間
是吧
已經用了多長時間
所以我們可以看到
如果說這個x
S6
等於三的話
等於三
那就說已經用了
在我們看這個儀式條件
已經用了三年的設備
你轉讓的話呢
還可以得到四千五萬元
是吧
剛纔我說了
這個轉讓所得
作爲你總的成本計算中
當然它是抵消成本
所以這裏我們寫個負的
寫個負的四千五
那麼當你第六年初
你的設備
應用了兩年
也就是狀態是二
或者是狀態是一的時候
那分別有一定的
這個終端的值
是吧
終端值
那就根據這個
還有根據這個所得到
是吧
所以這個問題
我們要注意的
這些狀態集合的話
就是第五階段的狀態
集合第四階段的狀態
集合我們要注意
在這個問題中
實際上都是可能的狀態
也就是到了第四四年初
到了第五年初和第四年初
那麼這個設備
已經用過的這個年頭
那就是一個狀態
集合是吧
那麼這個問題中呢
我們可以想到
因爲它有一個
三年必須淘汰的現場
對吧
所以這樣的話呢
就是你到了
即便到了第五年初
你不可能有一個
就是說它的1014的情況
對吧
那這樣的話
就是說相應的話
我們說這裏的狀態集合
你看S5
123
但S4本身就是123
對吧
因爲它最多到了第四年初
我們開始是個新設備
不想強定
那麼它最多也就用
這個三年
下面我們比較仔細的計算一下
在計算中
我們就是把有些
爲了方便
還是把這個一致的表
我們放在這裏
對吧
這個我們看着比較方便
你看這個
剛纔我們說了
在第五階段
因爲我們按照逆序
對吧
在第五階段
第五年初
那麼這個設備可能的10
那就是123
對吧
那下面我們分別計算
分別計算它的設備10
是321的情況
對吧
那大家看看
10是3
那這個時候
按照我們前面的
這個問題的要求
它只能是更新
已經到了
到了第五年初
你這個設備已經用了三年了
那你必須更新
對吧
所以這時候呢
相應的成本
我們看到相應的成本
這裏頭
一個是你已經用了三年的設備
你把它更新
轉讓給別人
這個所得4500
那做成本
只是負4500
對吧
那麼你更新預測
第五年初更新的價格是13000
對吧
然後新設備
新設備本身
新的設備本身
那麼這時候的話呢
它的運營的費用
這比較小
只有800
對吧
然後新的設備
再用一年到第六年初
這應該是F61
對吧
F61
也就是說這個
你更新完了
第五年初
你更新完了
然後第六年初
你用了一年
用了一年不用了
那你還要轉讓
轉讓又一部分所得
對吧
又一部分轉讓所得
對吧
這個所以我們很容易
很容易把它算出來
對吧
這個轉讓所得應該是用了
用了一年
用了一年以後的
轉讓的收入
對吧
所以就應該把它
這個
當然這個值
應該在這裏是負的
對吧
這個值應該是負的
對吧
這個值應該在這裏是負的
對吧
這是這個
第五階段狀態爲三的情況
那麼第五階段狀態爲二的時候呢
當然這時候可以有兩個選擇
一個是這裏是更新的情況
這裏是更新的情況
這裏是繼續用
對吧
繼續用
已經用了兩年的設備
然後再用一年
對它的運營的成本
是比較大的
另外這個時候呢
狀態轉移
到了
第六階段初
第六年初
那這個時候應該再增加
一零增加一年
所以F63
F63
對吧
那當然這個時候
這個設備就到了
這個時候
這利用的中端條件可以
對吧
已經必須要轉讓
所以這兩個要做一個比較
那麼狀態爲一的時候也是一樣
對吧
這個第五階段狀態爲一
第五年年初
這個設備
如果說剛剛用了一年
那當然它可以
還可以更新
也可以接着用
對吧
可以更新
也可以接着用
這是相應的計算
對吧
我們把每一個相應的
自由指標函數
也就是說
第五階段
每一個狀態下的
自由指標函數
這我們都可以算出值來
以及相應的自由決策
都可以得到
對吧
那這樣第五階段
做完了
對吧
那下邊第四階段
第四階段剛剛我也分析過
第四階段的狀態
狀態
那麼還是
一二三
對吧
那麼這也一樣
在第四階段
狀態爲三
也就是到了第四年初
如果你的設備
已經用了三年
那麼按照我們這個問題的條件
只能更新
對吧
只能更新
所以這裏頭
就是沒有什麼決策的
決策的選擇
只能是更新
對吧
但更新以後呢
你到第五年初
那你的一零隻有一
對吧
所以這是用這個相應的狀態
第五階段相應的狀態爲一的時候
的自由指標函數
對吧
那麼如果是二的時候呢
那可以更新
也可以接着用
對吧
所以這兩個我們做比較
對吧
如果是一的話
如果到第四年初
第四年初
那麼設備的已經用了四年
只用了一年
對不起啊
只用了一年的話呢
那麼這時候我們可以更新
也可以繼續用
對吧
那這樣一來
我們把第四階段狀態
分別爲三二一
它的自由指標函數值
以及相應的自由決策
都得到
對吧
那麼下邊都是
我們不是說的特別詳細
我們這裏都有
都有這個
都有這個結果
對吧
那麼到了第三階段
第三階段初
它的狀態一和
那隻能是一和二
對吧
因爲第三年初
對吧
第三年初
第三年初的話
我們一開始
第一年初是個新設備
所以到第三年初的話呢
那麼這個設備
最多
也就是前面你都繼續用
那到這兒用了兩年
對吧
當然有可能你第一年末
第二年初
你就更新了
所以到這兒是一年
對吧
所以它的狀態集合呢
只是這個一和二
對吧
一和二
它不會是三
對吧
那就相對的更簡單一點
那麼我們看到
第三階段狀態爲二的時候
它的可能的決策呢
當然
這個表示什麼
表示更新
對吧
這個表示繼續用
對吧
這個是更新
這個是繼續用
對吧
你看
第三階段狀態爲二的時候
更新
在這回收
你這個已經用了兩年的
這是六千
對吧
然後你購值的成本
這個第三年初
第三年初
預計是一萬億
對吧
然後新設備運行成本
這是八百
對吧
狀態轉移
到了第四階段的話呢
那麼你這更新
到了下一年初
它這個值是一
這個狀態是一
利用我們已經
前面一個階段
已經求得的
這個自由值
百分之二
對吧
這是繼續用
繼續用的話
那這個
你這是二
你再接着用一年
這個是三
對吧
那麼狀態爲一的情況下
以此類推
這個以此類推
對吧
這是第二階段
這是第三階段
那麼第二階段
第二階段出
這個設備本身
可能的一零
那隻能是一
因爲很容易想到
第一年初
這個設備
因爲新設備
它肯定是接着用
對吧
它肯定接着用
按我們這個題目的條件
它肯定
你把它再更新的話
你肯定是不合算
對吧
這跟前面我們講過的
設備更新問題是一致的
對吧
所以這個時候呢
它的狀態
只有一個
只有一個可能的狀態
對吧
這個比較簡單
那我們可以把它修改
最後第一階段的話
那這個狀態
也只有一個
對吧
一零是零
對吧
零的話呢
大家知道
這時候你一零的話
那就是新設備吧
新設備的話
那隻能是
就說你這個購值成本
這是它的購值成本
這是它的這個運行的成本
對吧
另外狀態轉移以後
到了第二年
第二年的年初
那它的一零是一
我們利用前面已經算的結果
對吧
所以我們把
每一個階段的
每一個狀態下的
最優的
這個值班函數值
以及相應的
最優決策都得到
但如果更完整的話
可以寫出
像我們
有的教材一樣
寫出
這個時候相應的後部
最優的後步詞策略
那當然更好
當然我們這個裏頭
寫出最優決策
我們通過狀態轉移
也很容易把它得到
把相應的最優決策
最優策略得到
所以這樣的話
我們最後得到這個問題的
最優策略
那就說
第一年那就接着用
對吧
第二年年初更新
第三年年初更新
第四年接着用
第五年也是接着用
對吧
第一年年初
這個接着用
第二第三年初更新
第四年年初繼續使用
這樣的最低成本
最低成本
是15900
15900
最優成本
對吧
最低成本
對吧
這是我們這個
第三個練習
對吧
接着我們看看第四個練習
第四個練習
它的這個問題的表述
比較複雜一點
對吧
因爲它是涉及到一個
證券投資的一個問題
對吧
當然這個問題
我們不做特別詳細的
這個糾結
對吧
把這個問題的基本特點
跟大家說一下
對吧
大家看看這個問題
一個投資者
準備通過信託公司
對項目A和B的基金
進行投資
那麼投資期限是五年
對吧
該投資的收益有兩部分
一是長期的
到第五年末的紅利收入
對吧
也就是這個是既福利的
對吧
所以這個年利率分別是
大寫的A和大寫的IB
對吧
然後既福利
而且五年間利率不變
對吧
爲了把這個問題
說明的更好一些
避免一些誤解的話
我們這裏特別加了一些個
附加的說明
對吧
比如第一年初投了A項目一元
那麼五年後
紅利收入應該是
1加上0.06
這個無私方
按既福利
大家知道應該按值出來
對吧
然後二是短期的利息收入
對吧
也就是說你投了錢以後
一個到最後
有一個總的
另外每年對你的投入
還可以寄點利息
這個利息可以供你到下一年
你再選擇
往哪去投入
對吧
是這樣的情況
所以兩個項目
在不同年份的利率
這個短期的
一個是小寫的IA
IAK和IBK
對吧
那這個我們都有表
這是它的短期的收入
對吧
那這個爲了說明的問題
也是這樣
第一年初投入A項目一元
除了五年後的紅利收入以外
一年後
還有0.02元的利息收入
因爲大家知道
這是0.02
對吧
這是0.02
對吧
下面這個投資者
第一年初投入
這是五萬
以後二至五年初
每年還投入一萬
對吧
這個投入不包括
它的利息收入
不包括你投入的
這個短期的利息收入
對吧
那麼所有投入的基金的資金
在第五年末之前不得支取
對吧
這個剛纔我們說過
就是你這個投入的話
五年末在一塊算賬
對吧
那麼中間雖然有短期的利息收入
但這個短期利息收入
實際上是給你記錄
然後供你進一步選擇
往哪個方面投資的
一個選擇的一個值
但不是馬上也得取出來
對吧
你必須還要拿它去投資
對吧
所以我們注意這個問題
有這樣一個限制
對吧
所以這裏也說明一下
所有投入基金的資金
在第五年末之前不得支取
但是投資者需要決定
每年初的資金
對吧
也就是當年投入的資金
加上你投資金的短期利息
對吧
那麼對於項目A和B的分配額
離時五年末的總收入最大
所以這是這樣一個問題
對吧
那麼現在也準備用
動態觀看法來求解
我們都是按例去遞推
對吧
這裏爲了統一的期間的話
我們狀態變量
狀態變量
我們爲DK年初
可分配的資金總量
對吧
那麼決策變量XK
爲DK年初
分配給A的資金量
當然你要說選擇B的
也完全可以
對吧
那麼要求
第一寫出以下表達式
這是有允許決策集合
狀態轉移方程
然後階段指標
這階段指標有一個特點
特別第五年的
所以對第五年的
加一個提示
第五年的階段指標
因年末短期利息收入
不再投入
需要單獨把它表示出來
對吧
到第五年
第五年的時候
你投了
完了
第五年年初決定完了
到了第五年年末
這個事兒
這個錢就都拿走了
對吧
所以他就不再去選擇
什麼投資再投資
就沒有這個
對吧
所以這個我們注意一下
把基本的地區關係寫出來
這個要求給出
就是第五階段
四的時候
它的相應表達式
但這個我們不去仔細地算
因爲這個相對比較複雜
這個問題
儘管它問題本身是一個
投資的問題
對吧
但是我們大家可以看到
它其實
其實它本身的話
很像我們
我們給大家
很像我們給大家講過的
機器的負荷分配問題
對吧
那是年初有多少臺好的機器
那麼這時候
你如何去分配它
分配到高負荷運行
低負荷運行
我們這裏的
高低負荷的問題的話
就相當於什麼
相當於是
你這投入的A
還是投入的B的問題
對吧
相當於這樣一個情況
那下面我們
特別對前面這些表達式
我們看一看
應該怎麼來考慮
我們允許決策集合
這個大家很容易想到
你年初有SK
這麼多的資金
那麼你投入A
你可以在0到SK
任意的選擇
對吧
所以從這個意義上講
我們這個決策
也可以認爲是個連續量
對吧
沒有必要你把它劃分成
一元一元的
或者是更什麼的情況
對吧
狀態轉移的問題
這個也很好理解
狀態轉移你看SK加1
對吧
下一年年初
一個你本身就要投入這麼多
你本身要投入這麼多
對吧
另外還有一些
和前一年投入到
那個短期利息收入
對吧
因爲因爲長期的
那個他已經
長期的那個
他已經到第五年末計算
對吧
這個是
那就是他
他不能在這個每年
就下一年初
再做一個選擇
那就不算
對吧
只有短期的
短期的這部分
就可以算
對吧
就可以算
對吧
然後階段指標的話呢
階段指標我們可以看到
階段指標因爲作爲
除了第五年以外
我們說過
你投入的錢
其實都算作
五年末的
五年末的一個收入
對吧
都算作五年末的一個收入
對吧
所以在這種情況下呢
我們這個階段指標
這個階段指標的話
那就是說
你看這裏頭
這是
五年的對吧
就按福利計算
按福利計算
你第K年的話
當然你真正的
你存的年頭的話
是六減K
對吧
六減K
對吧
這是投入到A的
這是投入到B的
對吧
當然這個我們可以整理
然後第五年的話呢
特殊
第五年的話
既有這個
就是按
長期的那個紅利收入
對吧
但只有一年了
這個只有一年
對吧
那還有相應的短期收入
加一塊
對吧
然後這是這個問題的
這個地區關係
這個問題地區關係
倒是比較簡單
那當然這個問題
在進一步求解的時候
因爲我們這裏
就不再進一步求解
因爲他計算比較複雜
進一步求解的時候
我們可以知道
這是我們這個問題
我們是把狀態
和決策
都做一個連續的這樣看待
對吧
所以這樣的話
我們每一個
每一個
階段的相應的狀態下
我們得到的
除了第一階段
那我們得到的
都是相當於
一個自由指標函數值
對吧
就是一個自由指標函數值
那誰的函數呢
當然就是這個狀態的函數
對吧
也就是說你
你到了
DK年
你有的
你有的可以投入的錢
是SK
那麼相應的自由指標函數
我只給出的話
就是相當於SK
它的一個函數值
對吧
相當於SK的一個函數值
對吧
這是這個問題的特點
最後一個
我們再看一個
也是一個很簡單的問題
但這個問題
有點小小的綜合性
也就是說
它把一個動態圖畫問題
我們也可以用動態圖畫求解
也可以用一個
這個相當於
靈異圖畫來求解
靈異圖畫模型來求解
對吧
所以這是這樣一個問題
那麼注意到
這個問題
有六萬元的資金
準備向三個項目投資
三個項目的預期收益
分別是
這個REX1
是這樣子
大家注意
這裏有一個
相當於一個固定收益
對吧
這個不是固定成本
但是它的
我們可以類比
是完全和固定成本一樣
對吧
也就是說
你要投入
你投入大於零
對吧
你投入大於零
當然它就按照萬元
按照萬元來
按照萬元的整數倍投資
你只要投
你這個可以進入
七個單位的收益
對吧
那麼這個地方
還有一個
相當於可變成本
可變收益
對吧
如果你乾脆不投入的話
那就是零
對吧
這個就是零
這是R2
這是R3
對吧
有這個特點
那麼市中XI
是對項目愛的投資
都取萬元的整數倍
問如何分配
各項目的投資額
是總的收益最大
對吧
那麼如果用
動態規劃方式
糾結本問題
要求寫出本問題的
狀態變量
決策變量
以及第二階段
狀態V2的允許決策集合
它的定義或者表達式
然後寫出狀態轉移方程
和遞退方程
另外計算一下
第二階段狀態V4的
自由值班上市和自由決策
對吧
那麼第二個問題的話
如果這個問題
用線性整數規劃
用線性整數
也就是說帶有零一變量
其實這應該說
就是零一
對吧
零一混合規劃
來解決問題的話呢
那麼把這個
相應的模型列出來
對吧
把相應的模型列出來
這個和我們
前面的這個
線性固化那章的
那個關於整數固化的結
有一定的聯繫
對吧
我們重點看看
前面這些表達
對吧
這個倒都比較簡單
狀態變量
分配給DK
這是第三個項目的
總資金量
因爲這個也是個
資金分配問題
對吧
一共是六萬元的資金
怎麼分配
所以決策變量的話呢
決策變量
這是分配給DK
項目的資金量
對吧
那麼第二階段
狀態V2的時候
來決策集合
這個非常簡單
顯然是零一二
對吧
你到第二階段的話
那麼你總的資金量
總的資金量是
總的資金量是這個
二兩萬元
對吧
那麼你可能的
選擇的話呢
當然是零也行
一也行
二也行
對吧
那麼狀態轉移方程
這個和資源分配
一樣
那麼DK關係
也沒有什麼
特別的地方
對吧
這裏的計算呢
我們並沒有寫出
詳細的結果
這大家可以
做一個練習
這個注意什麼呢
注意就是
它的收益
收益本身
都有個
這個固定的
是一個
相當於固定成本
一樣那樣的收益
對吧
也就是零的時候
它都是零
但是你一旦大於零
它就有一個
辦了一個固定的收益
這個把它加
然後加以比較
所以這個做起來
也並不難
那這個問題
如果我們
用一個零一規劃
來表達的話呢
那大家知道
因爲它有一個
相當於固定收益嘛
就相當於我們對照
固定成本一樣
那這個時候的話
我們這裏的話
除了設這個變量
XI以外
就是你投入多少
對吧
那麼你還要設一個
零一變量
設個YI
對吧
當XI大於零的時候
這是一
等於零的時候
這是零
對吧
那麼這時候呢
相應的模型
我們可以這樣建
這時候大家可以看到
它只有一個
資金的一個總量的
一個約束
對吧
然後這個收益呢
這部分大家可以看到
這是什麼
相當於就是說
和你投入成
固定比例的部分
對吧
但是同時
還都有一個
相應的一個固定的收益
只要大於零
有個固定的收益
對吧
因爲這個問題
是要求
總的收益最大化
總收益最大化
對吧
所以這時候
我們就可以想到
如果你這個
大於零的時候
那肯定得讓它等於一
對吧
你大於零的時候
你那個固定的收益部分
它就產生了
對吧
但是如果等於零的時候呢
那必須是零
等於零必須是零
對吧
所以在這個問題中呢
我們如同前面講的
這個零一規劃一樣
對吧
那這時候
我們這裏頭
要加這樣一個約束條件
對吧
加這樣一個條件
對吧
這個約束條件
大家注意
因爲這是收益最大化
對吧
那這個條件保證什麼呢
如果它等於零
它一定是零
對吧
如果你不投入
那肯定固定的收益也沒有
對吧
但如果你這個
你這個投入
那這個呢
當然可以是零可以是一
但是大家注意到
這個時候
是一個最大化的
一個目標價值
那最終的話
它當然是會是一
對吧
因爲等於一的話
這個就多出一部分這個值
對吧
所以這個是和我們的固定費用的
一個模型可以類比
但是它有點小小的差別
因爲這裏是收益最大化
而不是成本最低
對吧
那其他的這個問題的話
應該是還是比較簡單的問題
對吧
那麼我們現在
就是做這樣幾個練習
讓大家更好的理解
動態圖畫的這個
基本的原理和基本的方法
對吧
那麼這一節課
我們就講到這裏
