开门见山说吧我最近在带几个学弟学妹备赛数学建模发现动态规划是不少人最头疼的一块。上课听例题觉得很简单课后做作业也没问题可一拿到竞赛题就傻眼不知道该选什么做状态不知道为什么要倒着推更不知道MATLAB代码到底怎么写才能不越界、不出错。这篇我就用一道很经典的“生产计划库存控制”例题把从读题、设状态、列转移方程到用MATLAB写代码、回溯方案的全过程走一遍。我不会只给一个代码模板而是把每一步背后的判断理由都讲清楚适合正在备战国赛、美赛或华为杯的同学参考。数学建模里的优化问题很大一部分都是“多阶段决策”事情按照时间或顺序发展成一连串阶段在每个阶段做一次决策而这次决策会影响后面的状态。动态规划就是专门对付这类问题的框架。但框架归框架真正到了比赛现场如何把一个实际问题翻译成DP的“状态”“转移”“边界”才是最要命的。我希望通过这篇文章把这一套翻译流程拆碎给你看让你以后看到类似问题不再是“凭感觉”。1. 动态规划在数学建模里究竟解决什么问题1.1 先来分清线性规划管连续决策动态规划管多阶段决策很多同学第一次接触数学建模时最先学的是线性规划——目标函数、约束条件、交给求解器跑。但线性规划本质上处理的是一个“一次性决策”所有变量在一个模型里同时确定不存在时间先后、阶段推进的结构。动态规划不一样。它解决的是那种“一步一步做决策、每一阶段都会改变未来状态”的问题。最典型的就是生产计划、库存控制、设备更新、投资组合、最短路径、车辆调度这些场景。共同特点是系统有一个随时间演变的状态这个状态被当前决策改变又会继续影响下一阶段的决策空间。我常和学生打一个比方线性规划像是你站在地图外看全貌一次性算出从A到B的全局最优路径动态规划则是你开车上路每过一个路口都要根据当前的位置和油量重新决定下一步怎么走。后者天然适合描述“过程型”的优化问题。1.2 最优子结构与重叠子问题两个性质决定了DP能不能用动态规划能用首先要求问题具备最优子结构全局最优方案拆开看从任何一个中间状态到终点的子方案也一定是对应子问题的最优解。否则局部不是最优、全局却最优那种情况DP根本没法处理。第二个性质是重子问题。如果你把问题写成递归会发现大量相同的子状态被反复计算。动态规划的作用说白了就是用一个表把这些子问题的结果存起来避免重复劳动。这就是为什么DP经常被说成“用空间换时间”。比如斐波那契数列递归版本算n40都很慢用数组从底往上推就是一行循环的事。这两个性质一旦同时成立DP的基本范式就成立了明确阶段、定义状态、写出状态转移方程、确定边界条件、按顺序填表、回溯得到决策序列。1.3 什么情况下别硬上DPDP不是万能钥匙。最典型的反例是状态空间爆炸。比如一个问题需要同时记录库存、资金、设备状态、人员数量每个维度有10个取值四个维度就是一万个状态看起来还行但如果维度一多或者每个维度的取值很大状态表会迅速膨胀到内存都装不下。这时候DP就跑不动了比赛里该换启发式算法或整数规划。另外如果问题不满足无后效性——也就是说未来只取决于当前状态而与过去是通过什么路径到达当前状态无关——DP也需要谨慎使用。比如某些带“必须连续选择某种方式两次”的约束只记录当前库存就不够了需要额外加一维状态去记忆前置信息复杂度会大幅上升。2. 一道生产计划题的完整建模过程从读题到状态转移方程2.1 题目设定需求波动下常规生产、加班生产、库存怎么搭配直接看例题。假设某工厂要为未来4个月安排生产第t个月的市场需求分别是月份需求百件12243143月初没有库存。每个月可以通过两种方式生产常规生产单件成本5元产能上限4百件加班生产单件成本8元产能上限2百件。每百件产品如果月末没有卖出去留到下一月会产生1元的库存成本。仓库最多只能存2百件。为了简化要求第4个月结束后库存必须为0。问这4个月每个月应该常规生产多少、加班生产多少才能让总成本最低这种题在数学建模里非常常见本质是一个带时间维度的资源分配与调度问题。很多人第一反应是用线性规划把所有变量一口气求出来这当然能解但我要用DP来做因为DP的解结构能输出每一个月、每一个阶段的决策逻辑而且代码写起来也比线性规划建模更直观。2.2 状态变量为什么选“月末库存”而不是“累计产量”这里最关键的一步也是大多数新手卡住的地方状态变量选什么我见过不少同学把状态设为“累计产量”或“已生产总量”结果方程越写越乱。其实正确的思路是问自己一句当我站在第i个月的起点时为了决定这个月怎么生产我需要知道哪些信息答案是上个月剩了多少货这就是当前库存。至于前几个月怎么生产的、总共生产了多少对后续决策没有影响——需求是已知的后续能不能卖完只取决于当前库存和后续安排而不取决于库存是怎么积累起来的。这说明“库存”是一个满足无后效性的状态变量。所以我定义阶段月份 i 1, 2, 3, 4状态变量第 i 个月结束后的库存量 I_i取值范围 0 到 2百件且 I_0 0I_4 0决策变量第 i 个月常规生产量 a_i加班生产量 b_i这里我故意把状态设为“月末库存”而不是“月初库存”是为了让递推方向更顺已知上一个月的库存 I_{i-1}本月生产完之后求 I_i再判断是否满足仓库容量约束。2.3 状态转移方程、成本函数与边界条件的推导第 i 个月的生产量与库存变化满足I_i I_{i-1} a_i b_i - d_i其中 d_i 是第 i 个月的需求。这个式子就是动态规划里的状态转移方程它描述的是决策如何把旧状态变为新状态。每个月的直接成本包括常规生产成本、加班生产成本和月末库存持有成本C_i 5a_i 8b_i I_i月度产能约束为0 ≤ a_i ≤ 40 ≤ b_i ≤ 2库存约束为0 ≤ I_i ≤ 2整张表的填法采用“倒推”思想定义 dp(i, I_{i-1} 1) 表示已知第 i 个月初库存为 I_{i-1} 时从第 i 个月开始到第 4 个月结束的最小总成本。那么递推式就是dp(i, I_{i-1} 1) min [5a_i 8b_i I_i dp(i1, I_i)]注意这里的 I_i 由转移方程决定且必须落在0到2之间。边界条件是第4个月结束后库存必须为0即 I_4 0所以 dp(5, 01) 0或者说第5阶段只有库存0这一点是合法的其余状态设为 inf。2.4 一张手工递推表把倒推思想讲清楚空讲不如手算。我们先看第4个月最后一个阶段。假设第4个月初库存分别为 0、1、2由于要求月末库存必须为0所以本月刚好生产到满足需求即可即 a_4 b_4 d_4 - I_3。如果月初库存 I_3 0本月的需求是3常规生产最多4所以直接常规生产3百件即可成本 5×3 15如果月初库存 I_3 1本月只需再生产2百件成本 10如果月初库存 I_3 2本月只需再生产1百件成本 5这些都是可行决策且由于阶段已结束不存在“未来影响”所以这些值就是 dp(4, I_31) 的结果。再往前推一个月。第3个月的需求是1假设第3个月初库存是0。那么生产量必须覆盖本月的需求1同时还要为第4个月留出库存。试几个方案生产1百件月末库存为0后续第4月成本15总成本 5 15 20生产2百件月末库存为1库存成本1后续第4月成本10总成本 10 1 10 21生产3百件月末库存为2库存成本2后续第4月成本5总成本 15 2 5 22所以第3个月初库存为0时最优策略是只生产当月需要的1百件总成本20。这个手工演算过程可能看起来很简单但它就是动态规划递推的核心站在当前阶段枚举本次决策产生的成本再叠加未来阶段的最优成本取最小值。别看第3个月数字很小当阶段多、状态多、决策空间大的时候这种“枚举查表”的思路可以处理几十上百个阶段的问题手工根本算不动但代码可以。3. MATLAB实现动态规划的代码骨架与回溯技巧3.1 用dp矩阵存“从第i阶段到终点的最小成本”代码实现的第一步是先确定数据存储结构。我这里用两个矩阵dp(i, I_prev1)已知第 i 个月初库存为 I_prev 时从本月到结束的最小总成本dec_a(i, I_prev1) 和 dec_b(i, I_prev1)记录达到这个最小成本时本月选择的常规生产量和加班生产量注意MATLAB的数组索引从1开始而库存值可以从0开始所以一律用“库存值1”作为列索引。这是个极其容易踩坑的地方后面第5节我会展开讲。整个实现采用自底向上填表从最后一个阶段开始倒推到第一个阶段。这么做一方面避免递归调用次数过深另一方面矩阵逻辑也更清晰。3.2 核心递推循环自底向上填表别用递归硬刚我把核心实现写成一个独立脚本方便直接复制运行%% 动态规划求解生产计划问题 clear; clc; % 参数设置 T 4; % 总月数 demand [2, 4, 1, 3]; % 每月需求百件 regular_max 4; % 常规产能上限 overtime_max 2; % 加班产能上限 c_regular 5; % 常规生产成本元/件 c_overtime 8; % 加班生产成本元/件 h 1; % 库存持有成本元/百件 inv_max 2; % 最大库存容量百件 % 状态空间月末库存取值 0 ~ inv_max % dp(i, I_prev1): 第 i 月月初库存为 I_prev 时从第 i 月到结束的最小总成本 dp inf(T 1, inv_max 1); dec_a zeros(T, inv_max 1); dec_b zeros(T, inv_max 1); % 边界条件第 T 月结束后库存必须为 0 dp(T 1, 0 1) 0; % 从后往前递推 for i T:-1:1 for I_prev 0:inv_max % 枚举月初库存 best inf; best_a 0; best_b 0; for a 0:regular_max % 枚举常规生产量 for b 0:overtime_max % 枚举加班生产量 I_cur I_prev a b - demand(i); % 合法性检查库存不能为负不能超出仓库容量 if I_cur 0 || I_cur inv_max continue; end % 如果是最后一个月必须保证月末库存为0 if i T I_cur ~ 0 continue; end % 本月成本 常规生产 加班生产 库存持有 cost_cur c_regular * a c_overtime * b h * I_cur; total cost_cur dp(i 1, I_cur 1); if total best best total; best_a a; best_b b; end end end dp(i, I_prev 1) best; dec_a(i, I_prev 1) best_a; dec_b(i, I_prev 1) best_b; end end % 输出最优总成本 fprintf(最优总成本: %.1f 元\n, dp(1, 0 1));这段代码的关键点在于它把上图手工推演的过程完全复制了。最外层的月份循环从4到1状态循环枚举月初库存内层两个循环枚举所有可行的生产组合再使用合法性检查进行剪枝。这里的 inf 初值非常重要如果初始化为0那么最优值永远不会被更新掉。3.3 回溯输出决策序列比赛论文里需要的不是最优值而是方案很多同学算完最优成本就结束了但数学建模论文里评委想看到的是“每月的生产安排是什么”而不仅仅是一个数字。所以必须做决策回溯从第1个月开始根据已经存下来的 dec_a 和 dec_b把每个月的生产量取出来再用状态转移方程更新库存进入下一个月。回溯代码很简单%% 回溯最优方案 fprintf(\n最优生产方案如下\n); I_prev 0; % 第1个月月初库存为0 total_cost 0; for i 1:T a dec_a(i, I_prev 1); b dec_b(i, I_prev 1); I_cur I_prev a b - demand(i); cost_cur c_regular * a c_overtime * b h * I_cur; total_cost total_cost cost_cur; fprintf([第%d个月: 常规生产 %d 百件, 加班生产 %d 百件, , ... 月末库存 %d 百件, 本月成本 %.1f 元\n], ... i, a, b, I_cur, cost_cur); I_prev I_cur; end fprintf(校验总成本: %.1f 元\n, total_cost);跑一下这段程序输出结果大概是最优总成本: 88.0 元 最优生产方案如下 第1个月: 常规生产 4 百件, 加班生产 0 百件, 月末库存 2 百件, 本月成本 22.0 元 第2个月: 常规生产 4 百件, 加班生产 0 百件, 月末库存 2 百件, 本月成本 22.0 元 第3个月: 常规生产 1 百件, 加班生产 0 百件, 月末库存 2 百件, 本月成本 7.0 元 第4个月: 常规生产 1 百件, 加班生产 0 百件, 月末库存 0 百件, 本月成本 37.0 元 校验总成本: 88.0 元如果你自己手推会发现第1、2个月确实应该尽量多生产利用常规生产的低价优势先备货第3个月因为需求小虽然可以少生产但为了满足第4个月需求且避免加班提前备货到库存上限2百件也是划算的。这个趋势和直觉完全吻合。4. 背包、投资与路径规划DP在建模中的常见变形4.1 0-1背包的状态压缩为什么容量循环必须倒序生产库存问题掌握了以后我建议你立刻用它去理解背包问题。背包问题几乎每个建模比赛都有可能出现尤其是资源分配子模型。0-1背包的经典定义是有 n 件物品每件物品有重量 w_i 和价值 v_i背包容量 W问能装入的最大价值。朴素DP状态是 dp(i, c)表示前 i 件物品在容量 c 下的最大价值。状态转移为dp(i, c) max(dp(i-1, c), dp(i-1, c-w_i) v_i)空间优化时很多人会把第一维压缩掉变成一维数组 dp(c)。这时内层循环必须从 W 向下循环到 w_i原因在于如果正序更新新的 dp(c-w_i) 可能是本轮已经更新过的值相当于同一件物品被重复使用多次变成完全背包了。倒序更新保证每个物品最多被考虑一次。这个细节在代码实现里很经典面试和比赛都爱考。4.2 多次决策与状态加维从背包到投资组合再到车辆调度在生产计划问题里我们只有“库存”一个状态维度在背包问题里我们有“容量”一个维度。如果问题变复杂比如投资问题中同时关心资金总额和风险限额那么状态就可以是两个维度例如 dp(i, funds, risk)。状态加维是DP很自然的推广代价是内存和计算量按维度指数级增长所以要非常谨慎。再往上走像车辆调度、旅行商问题这类路径规划问题状态往往需要记录“当前所在城市”和“已经访问过的城市集合”。后者通常用一个二进制掩码表示这就是状态压缩动态规划dp(mask, j) 表示已经访问的城市集合为 mask当前停在城市 j 的最小距离。对于 n个城市的TSP状态数是 2^n × nn20 就已经是千万级了。比赛里碰到更大规模的路径优化DP很快就不适用这时应该转向遗传算法、模拟退火或一些启发式方法。热搜里出现“车辆动态规划问题”很多人以为DP能直接解大规模车辆调度其实DP更适合小规模精确求解或者作为启发式算法中的局部优化算子。4.3 遇到复杂约束DP和整数规划怎么选我个人的习惯是如果问题的决策天然是按时间或顺序展开而且状态变量很清晰就优先用DP比如生产计划、设备更换、库存管理。如果问题约束复杂、变量多、还混着布尔约束比如部分物品必须成套购买、供应商上限等DP的状态设计会变得很难受这时候用整数规划工具箱MATLAB的 intlinprog反而更省事。数学建模比赛中DP和整数规划并不是对立关系。我常常先用DP解一个小规模样例把结果和整数规划的结果对比两者一致才能证明模型的正确性。论文里同时呈现两种方法也能体现你对优化工具的掌握程度。5. MATLAB写DP时那几个最容易翻车的细节5.1 索引偏移MATLAB从1开始状态从0开始这是我最想强调的一个坑。动态规划里状态为0是非常正常的比如库存为0、容量为0。但MATLAB的数组索引必须从1开始所以如果你直接用 dp(i, I_cur) 来访问当 I_cur0 时就会越界而当你用 dp(i, I_cur1) 解决了0的问题后又要非常小心地保持整个代码里所有访存都统一加1否则极容易出现“计算结果错得离谱但程序不报错”的情况。我的经验是给变量命名时就直接用 I_offset I_cur 1这样逻辑上更清晰不容易在第5层循环里把偏移搞混。或者直接统一约定“第 j 列代表库存 j-1”然后在代码注释里明确标注。5.2 inf初始化、不可行状态和NaN陷阱求最小化问题时dp 矩阵一定要初始化为 inf而不是0。0会让所有最小值判断失效。初始化后还要注意inf参与加法仍然等于inf这没问题但一旦 inf inf 在某些MATLAB版本里可能产生 NaN而 NaN 参与比较时结果恒为假这会导致 best 一直不被更新。所以遇到 NaN 要先查是不是有不可达状态混进了递推。更稳妥的做法是在递推之前就把不可行状态单独标记出来或者在循环里用 continue 跳过不合法的库存组合。我们前面的代码已经用了这个策略库存必须非负、不能超出容量最后一个月还必须清库存。这三条过滤条件缺一不可。5.3 三重循环速度优化与记忆化搜索的取舍很多初学者担心MATLAB三层循环太慢。说实话在状态规模几千到几万这个级别MATLAB循环完全够用。如果状态数到了几十万甚至百万级别三层循环可能就要等半天了这时候可以改用向量化计算或者把内层决策枚举变成一个查找表。另一个思路是改成递归记忆化搜索。也就是写一个递归函数只有当某个状态第一次被访问时才计算并存入一个 container.Map 或稀疏矩阵。对于状态空间稀疏、很多状态根本不可达的问题这比强行填满整个 dp 矩阵要快得多。我自己调试DP时有个习惯先写一个递归版本它能让我很清楚地看到“当前状态是怎么依赖后续状态的”验证正确性确认无误后再改成循环版本去跑大数据。两种写法对照排查几乎能解决所有逻辑错误。5.4 用表格整理DP公式和参数提高论文可读性比赛论文里如果把状态转移方程直接丢成一个长公式评委看着累自己也容易写错。我习惯把题目中的参数先整理成表符号含义取值T计划期数4d_t第 t 月需求[2,4,1,3]c_r常规生产成本5c_o加班生产成本8h单位库存成本1I_t第 t 月末库存0~2a_t第 t 月常规生产量0~4b_t第 t 月加班生产量0~2论文里一旦表格化公式推导就会变得清晰很多。这也是我想特别提醒的动态规划的难点不在数学推导本身而在于把题目里的离散参数、状态变量、决策变量之间的关系理清楚这一步用表格辅助非常有帮助。6. 比赛实战中的DP建模心得6.1 先手算小规模样例再做全量计算比赛压力下大家很容易拿到题就开写代码。但DP的 bug 隐蔽性很强错一个状态下标可能结果偏差巨大但程序不报错。所以我强烈建议先手动算一个阶段少、状态少的小例子比如把需求改成 [1, 2]把库存上限改成1手推几个步骤再用代码去算核对一致后再扩展到完整数据。这个验证成本非常低但能帮你排除掉至少一半的建模和编码错误。我见过太多队伍因为“结果跑出来了但方向不对”最后发现是状态定义错了白白浪费半天时间。6.2 不会建模时先把阶段找出来很多同学一看到新题就懵不知道状态该设什么。我的经验是遇到优化问题先问自己有没有“阶段性”。如果有明显的时间顺序按天、按月、按工序或者有逐步推进的过程逐步分配资源、逐步访问城市那就可以优先考虑动态规划。然后再问站在每个阶段的起点我为了做出当前决策需要知道哪些信息这个问题的答案往往就是状态变量。比如生产计划需要知道库存投资问题需要知道剩余资金路径问题需要知道当前位置和已访问集合。顺着这个思路走比盯着题目硬想“这题能不能用DP”要靠谱得多。6.3 用DP求结果后千万别忘了验证和对比数学建模比赛和纯算法题不一样光计算出数字不够还得让人信服。我每次用DP得到方案后只要规模允许一定会再用整数规划或穷举法验证一次小规模结果。如果两种方法得到的目标函数值一致论文里的可信度就上去了如果不一致说明至少有一个模型出了问题这时候沿着状态转移方程和约束条件逐行排查通常能找到原因。6.4 给论文呈现的几点建议论文里写动态规划时我建议采用这样的顺序先写清楚“为什么这个问题是多阶段决策问题”再列出集合、参数、决策变量、状态变量然后给出状态转移方程和边界条件接着用一个小表格展示部分填表过程最后给出MATLAB核心代码和输出结果。表格和公式比大段文字说明要直观得多。评委在一篇十几页的论文里通常没有精力去推演每一处逻辑结构清晰、符号统一、有表格辅助的DP模型往往更容易拿到高分。回头再说一句动态规划这个工具本身并不复杂本质上就是用空间换时间把重复计算的子问题结果缓存起来。真正难的从来不是代码而是把实际问题里的“阶段”和“状态”挖出来。多练几种不同类型的DP题——背包、生产计划、投资组合、路径规划——你会发现它们的建模流程其实是完全一致的。当年我练到后期看到一道优化题脑子里第一反应已经不是“能不能用DP”而是“它的阶段在哪里、状态是什么、转移方程长什么样”希望你也能尽快到这个状态。