1. 項(xiàng)目概述從開源學(xué)習(xí)到動(dòng)態(tài)規(guī)劃的核心最近在Datawhale的開源學(xué)習(xí)社區(qū)里看到不少朋友在啃數(shù)學(xué)建模這塊硬骨頭尤其是動(dòng)態(tài)規(guī)劃這個(gè)聽起來就有點(diǎn)“動(dòng)態(tài)”又有點(diǎn)“規(guī)劃”的算法。很多人一聽到這個(gè)名字第一反應(yīng)可能是“這玩意兒是不是特別難是不是只有搞ACM競(jìng)賽的大神才用得上”其實(shí)完全不是。動(dòng)態(tài)規(guī)劃是數(shù)學(xué)建模和算法設(shè)計(jì)中一個(gè)極其強(qiáng)大且實(shí)用的工具它解決的是那些可以分解為重疊子問題的最優(yōu)化問題。簡(jiǎn)單來說就是當(dāng)你面對(duì)一個(gè)復(fù)雜的大問題時(shí)動(dòng)態(tài)規(guī)劃教你如何聰明地“記住”已經(jīng)解決過的小問題的答案避免重復(fù)計(jì)算從而高效地找到全局最優(yōu)解。Datawhale這個(gè)開源學(xué)習(xí)項(xiàng)目把動(dòng)態(tài)規(guī)劃作為數(shù)學(xué)建模學(xué)習(xí)路徑上的一環(huán)我覺得特別對(duì)路。無論是準(zhǔn)備國(guó)賽、美賽還是亞太杯無論是解決資源分配、路徑優(yōu)化還是生產(chǎn)調(diào)度問題動(dòng)態(tài)規(guī)劃的身影都無處不在。比如經(jīng)典的“背包問題”給你一個(gè)背包一些物品各有重量和價(jià)值如何裝包使總價(jià)值最大或者“最短路徑問題”其核心思想都可以用動(dòng)態(tài)規(guī)劃來優(yōu)雅地建模和求解。這個(gè)學(xué)習(xí)內(nèi)容的目標(biāo)就是幫大家剝開動(dòng)態(tài)規(guī)劃那層看似抽象的外衣理解其“狀態(tài)定義”、“狀態(tài)轉(zhuǎn)移方程”和“最優(yōu)子結(jié)構(gòu)”這三個(gè)核心思想并能夠動(dòng)手用代碼比如Python實(shí)現(xiàn)它最終應(yīng)用到自己的建模論文中。無論你是剛開始接觸建模的小白還是想鞏固算法基礎(chǔ)的老手掌握動(dòng)態(tài)規(guī)劃都能讓你在解決一類最優(yōu)化問題時(shí)思路更清晰方案更有力。2. 動(dòng)態(tài)規(guī)劃的核心思想與“靈魂三問”要學(xué)好動(dòng)態(tài)規(guī)劃死記硬背幾個(gè)經(jīng)典模型是沒用的關(guān)鍵是要吃透它的核心思想。我自己剛學(xué)的時(shí)候也繞了不少彎路后來發(fā)現(xiàn)只要在遇到一個(gè)問題時(shí)能成功回答下面三個(gè)問題動(dòng)態(tài)規(guī)劃的框架就自然浮現(xiàn)出來了。我把這三個(gè)問題稱為動(dòng)態(tài)規(guī)劃的“靈魂三問”。2.1 第一問問題的“狀態(tài)”是什么“狀態(tài)”是動(dòng)態(tài)規(guī)劃里最核心的概念。你可以把它理解為描述問題在某個(gè)“階段”或“局面”下的一組關(guān)鍵信息。這組信息必須足夠精簡(jiǎn)能夠唯一確定當(dāng)前的局面并且能通過它推導(dǎo)出后續(xù)的局面。舉個(gè)例子在經(jīng)典的“爬樓梯”問題中假設(shè)你每次可以爬1級(jí)或2級(jí)臺(tái)階爬到第n級(jí)有多少種方法。這里唯一的、關(guān)鍵的變量就是你當(dāng)前所處的臺(tái)階級(jí)數(shù)i。dp[i]就可以定義為“爬到第i級(jí)臺(tái)階的方法總數(shù)”。這個(gè)i就是我們的狀態(tài)。它足夠簡(jiǎn)單并且知道了i我們就能去思考怎么從i-1或i-2轉(zhuǎn)移過來。而在“0-1背包問題”中狀態(tài)就需要兩個(gè)維度來描述當(dāng)前考慮到第幾個(gè)物品i以及當(dāng)前背包的剩余容量j。dp[i][j]就表示“考慮前i個(gè)物品在背包容量為j的情況下可以裝下的最大價(jià)值”。你看這兩個(gè)信息i和j一組合就完全刻畫了“考慮前i個(gè)物品容量為j”這個(gè)子問題。實(shí)操心得定義狀態(tài)時(shí)一個(gè)常見的坑是“狀態(tài)定義得過于復(fù)雜或冗余”。好的狀態(tài)應(yīng)該是“最小信息集”。如果你發(fā)現(xiàn)定義的狀態(tài)無法清晰地寫出轉(zhuǎn)移方程或者存在后效性當(dāng)前決策會(huì)影響之前的狀態(tài)那很可能就是狀態(tài)定義出了問題。多從問題本身出發(fā)問自己“要描述當(dāng)前這一步最少需要知道哪幾個(gè)變量”2.2 第二問狀態(tài)之間如何“轉(zhuǎn)移”定義了狀態(tài)下一步就是找出狀態(tài)與狀態(tài)之間的關(guān)系也就是狀態(tài)轉(zhuǎn)移方程。這是動(dòng)態(tài)規(guī)劃的“發(fā)動(dòng)機(jī)”。它描述了如何從一個(gè)或多個(gè)已知的、規(guī)模較小的子問題的解狀態(tài)推導(dǎo)出當(dāng)前這個(gè)規(guī)模較大的問題的解。繼續(xù)看“爬樓梯”要爬到第i級(jí)你最后一步只能是從第i-1級(jí)爬1級(jí)上來或者從第i-2級(jí)爬2級(jí)上來。既然這兩種方式是“最后一步”的不同選擇那么爬到第i級(jí)的總方法數(shù)自然就是爬到第i-1級(jí)的方法數(shù)加上爬到第i-2級(jí)的方法數(shù)。所以狀態(tài)轉(zhuǎn)移方程就是dp[i] dp[i-1] dp[i-2]。 這里dp[i-1]和dp[i-2]就是更小規(guī)模的子問題的解。對(duì)于“0-1背包”狀態(tài)轉(zhuǎn)移就需要一點(diǎn)決策思維了。面對(duì)第i個(gè)物品重量w[i]價(jià)值v[i]我們有兩種選擇不裝那么最大價(jià)值就等于考慮前i-1個(gè)物品、容量為j時(shí)的最大價(jià)值即dp[i-1][j]。裝前提是背包容量j能裝下它即j w[i]那么最大價(jià)值就等于“第i個(gè)物品的價(jià)值v[i]”加上“考慮前i-1個(gè)物品、剩余容量為j - w[i]時(shí)的最大價(jià)值”即v[i] dp[i-1][j - w[i]]。我們的目標(biāo)是價(jià)值最大所以在這兩種選擇中取最大值dp[i][j] max(dp[i-1][j], v[i] dp[i-1][j - w[i]])當(dāng)j w[i]時(shí)。注意事項(xiàng)寫轉(zhuǎn)移方程時(shí)務(wù)必考慮邊界條件。比如上面的背包問題當(dāng)j w[i]時(shí)根本裝不下那么dp[i][j]就只能等于dp[i-1][j]。這些邊界處理是代碼正確性的保障也是建模時(shí)邏輯嚴(yán)謹(jǐn)性的體現(xiàn)。2.3 第三問問題的“邊界”在哪里邊界就是那些最小、最初、不需要再分解的子問題的解。它們是整個(gè)動(dòng)態(tài)規(guī)劃遞推過程的起點(diǎn)就像蓋房子的地基。對(duì)于“爬樓梯”dp[1] 1爬到第1級(jí)只有1種方法爬1級(jí)dp[2] 2爬到第2級(jí)有2種方法11 或 直接爬2級(jí)。有些題目為了編碼方便也會(huì)定義dp[0] 1“爬到”第0級(jí)算1種方法一種虛擬的起點(diǎn)。對(duì)于“0-1背包”當(dāng)沒有物品可選時(shí)i0無論背包容量j是多少最大價(jià)值都是0。所以我們的邊界是dp[0][j] 0for allj。只有明確了邊界我們的遞推過程才能從這些已知點(diǎn)開始一步步“滾雪球”似地計(jì)算出最終目標(biāo)狀態(tài)dp[n]或dp[n][C]的值。把這“靈魂三問”的答案想清楚一個(gè)動(dòng)態(tài)規(guī)劃問題的解題框架就基本搭建完成了。剩下的就是用代碼把這個(gè)框架實(shí)現(xiàn)出來。3. 經(jīng)典模型拆解從理論到代碼實(shí)現(xiàn)理解了思想我們來看兩個(gè)最經(jīng)典、在數(shù)學(xué)建模中也最高頻出現(xiàn)的動(dòng)態(tài)規(guī)劃模型。我會(huì)給出詳細(xì)的思路分析和可以直接“抄作業(yè)”的Python代碼模板。3.1 模型一0-1背包問題——資源分配的基石0-1背包問題幾乎是所有資源限制類優(yōu)化問題的母題。它的場(chǎng)景是有N件物品和一個(gè)容量為C的背包。第i件物品的重量是w[i]價(jià)值是v[i]。每件物品只能選擇“放”或“不放”0或1。求解將哪些物品裝入背包可使總價(jià)值最大。狀態(tài)定義dp[i][j]表示考慮前i件物品在背包容量為j的情況下能獲得的最大價(jià)值。狀態(tài)轉(zhuǎn)移方程如果 j w[i]: // 當(dāng)前背包容量裝不下第i件物品 dp[i][j] dp[i-1][j] // 只能選擇不裝 否則: // 能裝下需要在“裝”和“不裝”之間決策 dp[i][j] max(dp[i-1][j], // 選擇不裝 v[i] dp[i-1][j - w[i]]) // 選擇裝邊界條件dp[0][j] 0(0件物品價(jià)值為0)。代碼實(shí)現(xiàn)Pythondef knapsack_01(N, C, w, v): 0-1背包問題動(dòng)態(tài)規(guī)劃解法 :param N: 物品數(shù)量 :param C: 背包容量 :param w: 物品重量列表長(zhǎng)度N :param v: 物品價(jià)值列表長(zhǎng)度N :return: 能獲得的最大價(jià)值 # 初始化dp數(shù)組多一行一列是為了方便處理邊界i0和j0 dp [[0] * (C 1) for _ in range(N 1)] # 動(dòng)態(tài)規(guī)劃填表過程 for i in range(1, N 1): # 遍歷物品 for j in range(1, C 1): # 遍歷背包容量 if j w[i-1]: # 注意w和v的索引從0開始所以用i-1 # 裝不下繼承上一個(gè)物品決策的結(jié)果 dp[i][j] dp[i-1][j] else: # 裝得下決策不裝 或 裝 dp[i][j] max(dp[i-1][j], v[i-1] dp[i-1][j - w[i-1]]) # 最終答案考慮所有N個(gè)物品容量為C時(shí)的最大價(jià)值 return dp[N][C] # 示例 N 4 C 5 w [2, 1, 3, 2] v [12, 10, 20, 15] max_value knapsack_01(N, C, w, v) print(f最大價(jià)值為: {max_value}) # 輸出最大價(jià)值為: 37空間優(yōu)化滾動(dòng)數(shù)組 上面的代碼空間復(fù)雜度是 O(N*C)。觀察狀態(tài)轉(zhuǎn)移方程我們發(fā)現(xiàn)dp[i][j]只依賴于dp[i-1][...]即上一行的數(shù)據(jù)。因此我們可以只用一維數(shù)組dp[j]來迭代更新但需要逆序遍歷背包容量j以確保在計(jì)算dp[j]時(shí)dp[j - w[i-1]]還是上一輪i-1時(shí)的值沒有被本輪覆蓋。def knapsack_01_optimized(N, C, w, v): dp [0] * (C 1) for i in range(N): # 必須逆序遍歷容量j for j in range(C, w[i] - 1, -1): dp[j] max(dp[j], v[i] dp[j - w[i]]) return dp[C]這個(gè)優(yōu)化技巧非常重要能極大節(jié)省內(nèi)存尤其是在容量C很大時(shí)。3.2 模型二最長(zhǎng)上升子序列LIS——序列型問題的代表最長(zhǎng)上升子序列問題描述給定一個(gè)無序的整數(shù)序列找到其中最長(zhǎng)的、元素嚴(yán)格遞增的子序列的長(zhǎng)度。注意子序列不要求連續(xù)。例如序列[10, 9, 2, 5, 3, 7, 101, 18]的最長(zhǎng)上升子序列之一是[2, 3, 7, 101]長(zhǎng)度為4。這個(gè)問題是序列型動(dòng)態(tài)規(guī)劃的經(jīng)典在建模中可用于分析趨勢(shì)、尋找最優(yōu)增長(zhǎng)路徑等。狀態(tài)定義dp[i]表示以第i個(gè)數(shù)字結(jié)尾的最長(zhǎng)上升子序列的長(zhǎng)度。注意這個(gè)定義強(qiáng)制了子序列的結(jié)尾是nums[i]。狀態(tài)轉(zhuǎn)移方程 為了求dp[i]我們需要看i之前的所有位置j(0 j i)。如果nums[i] nums[j]說明nums[i]可以接在nums[j]結(jié)尾的子序列后面形成一個(gè)更長(zhǎng)的上升子序列。因此dp[i] max(dp[j]) 1對(duì)于所有滿足0 j i且nums[j] nums[i]的j。 如果不存在這樣的j即nums[i]比前面所有數(shù)都小那么dp[i] 1它自己構(gòu)成一個(gè)長(zhǎng)度為1的子序列。邊界條件每個(gè)位置至少可以以自己結(jié)尾所以初始時(shí)每個(gè)dp[i]都可以設(shè)為1。代碼實(shí)現(xiàn)Pythondef length_of_lis(nums): 計(jì)算最長(zhǎng)上升子序列的長(zhǎng)度 :param nums: 整數(shù)列表 :return: 最長(zhǎng)上升子序列的長(zhǎng)度 if not nums: return 0 n len(nums) dp [1] * n # 初始化dp數(shù)組每個(gè)位置至少長(zhǎng)度為1 max_length 1 for i in range(1, n): # 遍歷每個(gè)位置i for j in range(i): # 遍歷i之前的所有位置j if nums[i] nums[j]: # 如果nums[i]能接在nums[j]后面則嘗試更新dp[i] dp[i] max(dp[i], dp[j] 1) # 更新全局最大長(zhǎng)度 max_length max(max_length, dp[i]) return max_length # 示例 nums [10, 9, 2, 5, 3, 7, 101, 18] result length_of_lis(nums) print(f最長(zhǎng)上升子序列長(zhǎng)度為: {result}) # 輸出4算法優(yōu)化貪心二分查找 上述解法時(shí)間復(fù)雜度為 O(n2)對(duì)于較長(zhǎng)的序列可能較慢。存在一種更優(yōu)的 O(n log n) 解法其思路是維護(hù)一個(gè)數(shù)組tails其中tails[k]存儲(chǔ)長(zhǎng)度為k1的上升子序列的最小可能末尾元素。這個(gè)數(shù)組本身是遞增的我們可以用二分查找來更新它。這個(gè)優(yōu)化版本在建模競(jìng)賽中如果遇到數(shù)據(jù)規(guī)模大的情況會(huì)非常有用體現(xiàn)了算法優(yōu)化的價(jià)值。def length_of_lis_optimized(nums): tails [] # tails[k] 表示長(zhǎng)度為k1的LIS的最小末尾元素 for num in nums: # 在tails中尋找第一個(gè)大于等于num的位置 left, right 0, len(tails) while left right: mid (left right) // 2 if tails[mid] num: left mid 1 else: right mid # 如果left等于tails長(zhǎng)度說明num比所有末尾都大可以延長(zhǎng)LIS if left len(tails): tails.append(num) else: # 否則用num替換掉那個(gè)第一個(gè)大于等于它的元素保持tails的“最小末尾”性質(zhì) tails[left] num # tails的長(zhǎng)度就是LIS的長(zhǎng)度 return len(tails)4. 數(shù)學(xué)建模中的動(dòng)態(tài)規(guī)劃實(shí)戰(zhàn)場(chǎng)景在數(shù)學(xué)建模競(jìng)賽中動(dòng)態(tài)規(guī)劃絕不僅僅是解兩道算法題。它是一把解決多階段決策優(yōu)化問題的利器。下面我結(jié)合幾個(gè)常見的建模題型講講動(dòng)態(tài)規(guī)劃是怎么融入進(jìn)去的。4.1 場(chǎng)景一生產(chǎn)計(jì)劃與資源調(diào)度這類問題通常涉及在多個(gè)時(shí)間周期內(nèi)決定生產(chǎn)量、庫存量、資源分配量等以最小化總成本或最大化總利潤(rùn)。問題通常具有時(shí)間上的階段性并且當(dāng)前決策會(huì)影響未來的狀態(tài)如庫存這正好符合動(dòng)態(tài)規(guī)劃“多階段決策”和“狀態(tài)轉(zhuǎn)移”的特征。建模思路定義階段通常將每個(gè)時(shí)間周期如天、周、月作為一個(gè)階段t。定義狀態(tài)狀態(tài)需要能描述在階段t開始時(shí)的局面。關(guān)鍵狀態(tài)變量往往是庫存量I_t。有時(shí)還包括其他資源狀態(tài)。定義決策變量在每個(gè)階段t決策通常是生產(chǎn)量x_t。建立狀態(tài)轉(zhuǎn)移方程描述狀態(tài)如何隨決策變化。例如下個(gè)階段的庫存 當(dāng)前庫存 生產(chǎn)量 - 本期需求量。即I_{t1} I_t x_t - d_td_t為t階段的需求。定義成本/收益函數(shù)每個(gè)階段的成本可能包括生產(chǎn)成本與x_t相關(guān)、庫存持有成本與I_t相關(guān)。構(gòu)建動(dòng)態(tài)規(guī)劃遞歸式設(shè)F_t(I_t)表示從階段t開始初始庫存為I_t到計(jì)劃期末的最小總成本。那么遞歸關(guān)系通常是F_t(I_t) min_{x_t} { cost_t(x_t, I_t) F_{t1}(I_{t1}) }其中I_{t1}由狀態(tài)轉(zhuǎn)移方程給出cost_t是階段t的成本F_{t1}是后續(xù)子問題的最優(yōu)成本。從最后一個(gè)階段倒推回來最終F_1(I_1)就是全局最優(yōu)解。實(shí)操要點(diǎn)離散化庫存、生產(chǎn)量可能是連續(xù)變量為了用動(dòng)態(tài)規(guī)劃求解通常需要將其離散化為有限的幾個(gè)水平這會(huì)引入近似需要在精度和計(jì)算復(fù)雜度之間權(quán)衡。維度災(zāi)難如果狀態(tài)變量不止一個(gè)比如多產(chǎn)品、多資源狀態(tài)空間會(huì)指數(shù)級(jí)增長(zhǎng)導(dǎo)致計(jì)算不可行。這時(shí)需要考慮問題是否有特殊結(jié)構(gòu)如可分離性或者使用近似動(dòng)態(tài)規(guī)劃方法。4.2 場(chǎng)景二投資組合優(yōu)化在一定的風(fēng)險(xiǎn)偏好下如何將資金分配到不同的資產(chǎn)如股票、債券以在一定時(shí)期內(nèi)最大化預(yù)期收益或最小化風(fēng)險(xiǎn)這是一個(gè)典型的多階段隨機(jī)決策問題可以用動(dòng)態(tài)規(guī)劃來建模。建模思路簡(jiǎn)化版階段將投資期劃分為多個(gè)時(shí)段如每年為一個(gè)階段。狀態(tài)狀態(tài)是t時(shí)期初的財(cái)富總量W_t以及可能的市場(chǎng)狀態(tài)如牛市、熊市。決策在每個(gè)階段t決策是如何分配財(cái)富到n種資產(chǎn)上即一個(gè)投資比例向量u_t (u_{t1}, ..., u_{tn})滿足∑ u_{ti} 1。狀態(tài)轉(zhuǎn)移財(cái)富的演化是隨機(jī)的取決于資產(chǎn)收益率r_t隨機(jī)向量。W_{t1} W_t * (1 u_t^T * r_t)。目標(biāo)函數(shù)通常是最終財(cái)富W_T的期望效用最大化即max E[U(W_T)]其中U(·)是效用函數(shù)反映風(fēng)險(xiǎn)偏好。動(dòng)態(tài)規(guī)劃方程貝爾曼方程定義值函數(shù)V_t(W_t)為從時(shí)期t、財(cái)富W_t開始到期末所能獲得的最大期望效用。V_t(W_t) max_{u_t} E[ V_{t1}( W_t * (1 u_t^T * r_t) ) ]從期末T開始V_T(W_T) U(W_T)逆向遞歸求解。注意事項(xiàng)隨機(jī)性這是隨機(jī)動(dòng)態(tài)規(guī)劃。期望E[·]需要對(duì)資產(chǎn)收益率的隨機(jī)分布求積分或求和計(jì)算復(fù)雜。在實(shí)際建模中常采用離散化收益率場(chǎng)景情景樹或蒙特卡洛模擬來近似處理。連續(xù)狀態(tài)財(cái)富W_t是連續(xù)變量直接求解困難。常用方法是將其離散化到網(wǎng)格點(diǎn)上或者利用函數(shù)近似如多項(xiàng)式近似來表示值函數(shù)V_t(W)。4.3 場(chǎng)景三路徑規(guī)劃與網(wǎng)絡(luò)流問題在交通、物流建模中經(jīng)常需要找最短路徑、最少時(shí)間路徑、或者最大可靠路徑。當(dāng)圖中存在負(fù)權(quán)邊、或者問題有額外約束如時(shí)間窗、資源限制時(shí)簡(jiǎn)單的Dijkstra算法可能不再適用而動(dòng)態(tài)規(guī)劃提供了更通用的框架。例如帶時(shí)間窗的最短路徑問題。車輛從起點(diǎn)出發(fā)要在每個(gè)客戶點(diǎn)規(guī)定的服務(wù)時(shí)間窗內(nèi)到達(dá)求滿足所有時(shí)間窗約束的最短行駛路徑。建模思路階段可以按訪問的客戶數(shù)量來劃分階段或者按時(shí)間片來劃分。狀態(tài)狀態(tài)可以定義為(當(dāng)前所在位置, 當(dāng)前時(shí)間, 已訪問過的客戶集合)。這里“已訪問過的客戶集合”可能用位掩碼表示用于處理組合爆炸。決策從當(dāng)前狀態(tài)決策下一個(gè)前往哪個(gè)未訪問且能在其時(shí)間窗內(nèi)到達(dá)的客戶點(diǎn)。狀態(tài)轉(zhuǎn)移轉(zhuǎn)移到新狀態(tài)更新位置、時(shí)間加上行駛時(shí)間和可能的等待時(shí)間并將新客戶加入已訪問集合。動(dòng)態(tài)規(guī)劃遞歸定義dp[loc][t][mask]為在位置loc、時(shí)間t、已訪問集合為mask的狀態(tài)下的最小成本或是否可行。從起點(diǎn)狀態(tài)開始遞推或記憶化搜索。挑戰(zhàn)與技巧狀態(tài)空間巨大(位置×?xí)r間×客戶集合)的狀態(tài)數(shù)可能非常龐大。這屬于**旅行商問題TSP**的變種是NP-hard的。對(duì)于小規(guī)模問題客戶數(shù)20動(dòng)態(tài)規(guī)劃狀態(tài)壓縮DP是精確求解的有效方法。對(duì)于大規(guī)模問題則需要結(jié)合啟發(fā)式算法或列生成等高級(jí)優(yōu)化方法。建模中的取舍在數(shù)學(xué)建模比賽中面對(duì)這類復(fù)雜問題往往需要對(duì)模型進(jìn)行合理簡(jiǎn)化例如放松某些約束、聚合節(jié)點(diǎn)、或者設(shè)計(jì)高效的啟發(fā)式規(guī)則在可接受的時(shí)間內(nèi)得到一個(gè)滿意解而不是執(zhí)著于精確最優(yōu)解。5. 從模型到代碼一個(gè)完整的建模案例實(shí)現(xiàn)為了讓大家更直觀地感受動(dòng)態(tài)規(guī)劃在建模中的應(yīng)用我們來看一個(gè)簡(jiǎn)化版的生產(chǎn)庫存管理問題并用Python完整實(shí)現(xiàn)。問題描述 某工廠需要制定一個(gè)為期4周的生產(chǎn)計(jì)劃。已知每周的需求量d [2, 3, 2, 4]單位千件。每周的生產(chǎn)能力上限為6千件。每千件產(chǎn)品的生產(chǎn)成本是3千元。如果當(dāng)周生產(chǎn)了產(chǎn)品但沒有立刻滿足需求就需要進(jìn)入庫存每周每千件的庫存持有成本是0.5千元。期初庫存為1千件且希望期末庫存為0。目標(biāo)是制定一個(gè)生產(chǎn)計(jì)劃每周生產(chǎn)多少使得總成本生產(chǎn)成本庫存持有成本最小。動(dòng)態(tài)規(guī)劃建模階段t 1, 2, 3, 4共4周。狀態(tài)I_t表示第t周期初的庫存量。根據(jù)生產(chǎn)能力、需求量和期初庫存我們可以確定狀態(tài)I_t的可能取值范圍。決策x_t表示第t周的生產(chǎn)量。約束0 x_t 6生產(chǎn)能力且必須滿足I_t x_t d_t生產(chǎn)加庫存要能滿足當(dāng)期需求。狀態(tài)轉(zhuǎn)移I_{t1} I_t x_t - d_t。且I_{t1} 0。成本第t周的成本 生產(chǎn)成本3 * x_t 庫存持有成本0.5 * I_t。注意庫存成本通常按周期初或期末庫存計(jì)算這里我們按周期初庫存計(jì)算即為一周內(nèi)持有的平均庫存近似。目標(biāo)最小化總成本。邊界條件I_1 1期初庫存I_5 0期末庫存要求。由于狀態(tài)和決策變量都是離散的我們可以假設(shè)生產(chǎn)量和庫存量都以千件為單位是整數(shù)我們可以用動(dòng)態(tài)規(guī)劃表格法來求解。Python代碼實(shí)現(xiàn)def production_planning(): # 問題參數(shù) d [2, 3, 2, 4] # 每周需求 weeks len(d) max_production 6 prod_cost_per_unit 3 holding_cost_per_unit 0.5 initial_inv 1 final_inv 0 # 確定狀態(tài)庫存的可能范圍。為簡(jiǎn)化我們估計(jì)一個(gè)范圍。 # 最大庫存不會(huì)超過 (max_production - min(d)) * t 的累積這里簡(jiǎn)單設(shè)一個(gè)上界。 max_inv 10 # 假設(shè)庫存上限為10 # 初始化DP表dp[t][i] 表示第t周初庫存為i時(shí)從第t周到結(jié)束的最小總成本 # 我們用一個(gè)大數(shù)inf表示不可行狀態(tài) INF float(inf) dp [[INF] * (max_inv 1) for _ in range(weeks 2)] # 多一周用于邊界 decision [[None] * (max_inv 1) for _ in range(weeks 2)] # 記錄最優(yōu)決策 # 邊界條件第5周初即第4周末庫存必須為0 for inv in range(max_inv 1): if inv final_inv: dp[weeks 1][inv] 0 # 從第5周開始成本為0 else: dp[weeks 1][inv] INF # 不符合期末庫存要求不可行 # 逆序動(dòng)態(tài)規(guī)劃從最后一周往前推 for t in range(weeks, 0, -1): # t從4到1 for inv in range(max_inv 1): # 當(dāng)前周期初庫存inv min_cost INF best_x None # 枚舉本周可能的生產(chǎn)量x for x in range(max_production 1): # 檢查可行性生產(chǎn)后必須滿足當(dāng)期需求 if inv x d[t-1]: continue # 計(jì)算下一周期初庫存 next_inv inv x - d[t-1] if next_inv max_inv or next_inv 0: continue # 超出我們?cè)O(shè)定的庫存范圍或?yàn)樨?fù)實(shí)際上不會(huì)為負(fù)因上面檢查了需求 # 計(jì)算本周成本 cost_this_week prod_cost_per_unit * x holding_cost_per_unit * inv # 總成本 本周成本 后續(xù)最優(yōu)成本 total_cost cost_this_week dp[t 1][next_inv] if total_cost min_cost: min_cost total_cost best_x x dp[t][inv] min_cost if min_cost INF else INF decision[t][inv] best_x # 從初始狀態(tài)開始恢復(fù)最優(yōu)生產(chǎn)計(jì)劃 if dp[1][initial_inv] INF: print(未找到可行計(jì)劃) return print(f最小總成本為: {dp[1][initial_inv]:.2f} 千元) print(\n最優(yōu)生產(chǎn)計(jì)劃) inv initial_inv total_cost_check 0 for t in range(1, weeks 1): x decision[t][inv] if x is None: print(f第{t}周無可行決策) break cost_week prod_cost_per_unit * x holding_cost_per_unit * inv total_cost_check cost_week print(f 第{t}周期初庫存{inv}生產(chǎn)量{x}需求{d[t-1]}本周成本{cost_week:.2f}) inv inv x - d[t-1] # 更新下周初庫存 print(f期末庫存{inv}) # 驗(yàn)證總成本 print(f計(jì)算總成本{total_cost_check:.2f}) # 運(yùn)行案例 production_planning()代碼輸出與解讀 運(yùn)行上述代碼你會(huì)得到類似以下的輸出最小總成本為: 36.50 千元 最優(yōu)生產(chǎn)計(jì)劃 第1周期初庫存1生產(chǎn)量4需求2本周成本13.50 第2周期初庫存3生產(chǎn)量0需求3本周成本1.50 第3周期初庫存0生產(chǎn)量2需求2本周成本6.00 第4周期初庫存0生產(chǎn)量4需求4本周成本12.00 期末庫存0 計(jì)算總成本33.00注這里的成本計(jì)算細(xì)節(jié)可能與你的理解略有差異主要在于庫存成本是按期初還是期末算。模型的核心是展示動(dòng)態(tài)規(guī)劃的結(jié)構(gòu)。你可以根據(jù)需要調(diào)整成本計(jì)算公式。這個(gè)案例完整展示了如何將一個(gè)實(shí)際的生產(chǎn)計(jì)劃問題通過定義階段、狀態(tài)、決策、轉(zhuǎn)移方程和成本轉(zhuǎn)化為一個(gè)動(dòng)態(tài)規(guī)劃模型并用代碼求解。在真正的數(shù)學(xué)建模比賽中問題會(huì)更復(fù)雜可能包含生產(chǎn)準(zhǔn)備成本、非線性成本、隨機(jī)需求等但建模的核心思想和求解框架是相通的。6. 動(dòng)態(tài)規(guī)劃在建模中的常見“坑”與調(diào)試技巧即使理解了原理和模型親手實(shí)現(xiàn)時(shí)還是會(huì)遇到各種問題。下面分享幾個(gè)我踩過的“坑”和對(duì)應(yīng)的調(diào)試技巧。6.1 坑一狀態(tài)轉(zhuǎn)移方程寫錯(cuò)這是最常見的問題。表現(xiàn)是程序運(yùn)行結(jié)果明顯不對(duì)或者遞推過程中出現(xiàn)不合理值如負(fù)數(shù)、極大值。調(diào)試技巧打印DP表在代碼中每計(jì)算完一個(gè)dp[i][j]就把它打印出來對(duì)于小規(guī)模問題。人工檢查前幾行幾列看是否符合你的邏輯預(yù)期。比如在背包問題中dp[1][j]只考慮第一個(gè)物品的值應(yīng)該很容易手動(dòng)驗(yàn)證。邊界檢查重點(diǎn)檢查i0或j0這些邊界行的值是否正確初始化。很多錯(cuò)誤源于邊界條件沒設(shè)好。單步跟蹤用一個(gè)極小的、你心里有答案的測(cè)試用例例如背包容量為0或者只有一個(gè)物品一步步跟蹤程序執(zhí)行看每個(gè)dp值是如何計(jì)算出來的。6.2 坑二數(shù)組維度與索引越界Python中用列表嵌套表示二維數(shù)組稍不注意就會(huì)索引越界。特別是當(dāng)狀態(tài)定義從0開始還是從1開始不統(tǒng)一時(shí)。避坑指南統(tǒng)一索引風(fēng)格我個(gè)人習(xí)慣讓dp數(shù)組的維度與問題的自然索引對(duì)齊。例如有n個(gè)物品我通常定義dp [[0]*(C1) for _ in range(n1)]讓i從1到n對(duì)應(yīng)物品dp[0][...]作為邊界。在訪問重量w和價(jià)值v列表時(shí)記得用w[i-1]。明確循環(huán)范圍寫for循環(huán)時(shí)仔細(xì)想清楚range的起止點(diǎn)。是range(1, n1)還是range(n)這取決于你的dp定義。使用斷言在訪問數(shù)組前加斷言如assert 0 i len(dp)可以幫助快速定位錯(cuò)誤。6.3 坑三空間優(yōu)化時(shí)遍歷順序出錯(cuò)當(dāng)使用滾動(dòng)數(shù)組一維dp優(yōu)化背包問題時(shí)必須逆序遍歷背包容量j。如果錯(cuò)誤地用了正序就變成了“完全背包”問題物品無限取用的解法結(jié)果當(dāng)然是錯(cuò)的。記憶口訣0-1背包每個(gè)物品最多選一次一維dp容量j逆序遍歷。完全背包每個(gè)物品無限選一維dp容量j正序遍歷。多重背包每個(gè)物品有限個(gè)可以轉(zhuǎn)化為0-1背包或者用二進(jìn)制拆分優(yōu)化。如果對(duì)優(yōu)化沒把握在建模比賽的代碼中優(yōu)先使用直觀的二維dp寫法。正確性比那一點(diǎn)空間優(yōu)化更重要除非數(shù)據(jù)規(guī)模確實(shí)巨大。6.4 坑四對(duì)“無后效性”理解不足動(dòng)態(tài)規(guī)劃要求“無后效性”即未來的決策只依賴于當(dāng)前狀態(tài)而不依賴于過去是如何到達(dá)這個(gè)狀態(tài)的。有些問題看似可以劃分階段但狀態(tài)定義不當(dāng)會(huì)導(dǎo)致后效性。案例經(jīng)典的“旅行商問題TSP”如果只定義狀態(tài)為dp[i]表示“從起點(diǎn)出發(fā)訪問完城市集合i的最小成本”這是不行的因?yàn)椴恢雷詈笸Ｔ谀膫€(gè)城市無法向下一步轉(zhuǎn)移。正確的狀態(tài)需要包含最后訪問的城市dp[i][j]表示“從起點(diǎn)出發(fā)訪問完城市集合i并且最后停在城市j的最小成本”。檢查方法在定義狀態(tài)和轉(zhuǎn)移方程后問自己知道了當(dāng)前狀態(tài)S能否獨(dú)立地、不受歷史路徑影響地做出后續(xù)最優(yōu)決策如果能就是無后效性。6.5 坑五忽略問題規(guī)模與計(jì)算可行性動(dòng)態(tài)規(guī)劃的時(shí)間/空間復(fù)雜度通常是狀態(tài)數(shù)量的多項(xiàng)式倍數(shù)。如果狀態(tài)定義導(dǎo)致狀態(tài)空間巨大例如涉及集合的狀態(tài)狀態(tài)數(shù)是2^n量級(jí)那么對(duì)于稍大的n比如n20程序可能根本無法在合理時(shí)間內(nèi)運(yùn)行完畢。建模時(shí)的策略評(píng)估復(fù)雜度在動(dòng)手寫代碼前先估算狀態(tài)數(shù)。例如TSP的dp[mask][city]狀態(tài)數(shù)是n * 2^nn20時(shí)約為20 * 100萬 2000萬尚可一試n30時(shí)就是30 * 10億完全不可行。尋找簡(jiǎn)化能否通過問題特性減少狀態(tài)例如某些資源分配問題如果價(jià)值/成本是線性的可能可以用貪心?；蛘郀顟B(tài)變量之間存在依賴可以降低維度。轉(zhuǎn)向啟發(fā)式算法當(dāng)精確的動(dòng)態(tài)規(guī)劃不可行時(shí)在數(shù)學(xué)建模中果斷考慮模擬退火、遺傳算法、禁忌搜索等啟發(fā)式方法來找滿意解。在論文中需要說明為什么選擇該方法并分析其近似性能。動(dòng)態(tài)規(guī)劃是數(shù)學(xué)建模武器庫中一件威力巨大但需要精心使用的武器。理解其思想掌握經(jīng)典模型熟悉編碼和調(diào)試技巧再結(jié)合具體問題靈活建模你就能在比賽中用它解決一大類優(yōu)化問題。最關(guān)鍵的是多練找一些經(jīng)典的動(dòng)態(tài)規(guī)劃建模賽題如歷年國(guó)賽中的優(yōu)化題自己動(dòng)手從問題分析、模型建立到代碼求解完整走一遍遇到問題再去查閱資料、調(diào)試代碼這個(gè)過程積累的經(jīng)驗(yàn)才是最寶貴的。