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