高等运筹学期末复习：手写解答20道题，吃透对偶理论KKT与动态规划

期末复习季又是被《高等运筹学》支配的恐惧。这门课我上大学时就被虐过一遍现在回想起来它跟本科的运筹学完全不是一个量级——对偶理论不再只是背个式子而是让你从几何和经济学角度解释影子价格非线性规划的KKT条件不再是套公式而是先判断约束资质再动手动态规划更是彻底甩开看状态转移的直觉要你自己设计状态、证明最优性原理。我花了整整两周把手头20多道复习题逐一手写解答整理出这本复习题手写解答笔记。这篇文章就是把我这两周踩过的坑、悟出的规律、总结的答题模板全部讲清楚。内容是一份完整的期末复习手写解答实录包括题型拆解、每类题的解题套路、典型题目完整演算过程、以及复盘时的易错点清单。适合正在准备《高等运筹学》期末考试的研究生或高年级本科生也适合自学优化理论、想在科研里用数学建模的从业者参考。先说重点运筹学的复习光靠看讲义是绝对不够的必须动手写。手写解答这件事本身就有强制思考的作用——你在纸上把每一步推导展开错误会自己浮现出来你要是只用眼睛感觉会了考场上大概率会卡在第一道大题。下面这篇内容就是我手写解答全部复习题后的完整记录。1. 复习整体思路与命题逻辑拆解1.1 高等运筹学到底考什么高等运筹学跟我本科那会儿学的不太一样它的覆盖面并不广但深度非常挑剔。我们的课程重点集中在四个模块第一是线性规划的局部分支重点不是单纯形法本身而是对偶理论、灵敏度分析、影子价格的经济解释以及偶问题的互补松弛条件。第二是非线性规划核心是凸集凸函数判断、KKT条件求解、拉格朗日对偶。第三是整数规划与组合优化包括分支定界、割平面法、0-1规划建模。第四是动态规划与网络流典型题型是最短路径、资源分配、背包问题以及最大流最小割。期末试卷通常有五六道大题题型固定分布基本是一道纯对偶理论证明题、一道带约束的非线性规划求解题、一道整数规划建模题、一道动态规划建模计算题、一道网络流或灵敏度综合题。人话翻译一下它不是考你会不会算而是考你为什么这么算。比如单纯形法基础运筹学会问迭代到哪一步停止高级运筹学会反过来问如果目标函数系数变了最优解怎么变或者对偶问题的最优解为什么等于影子价格。所以复习的时候光记住算法流程远远不够关键是要理解每一步背后的数学原理。1.2 手写解答的选题策略与三轮复习法我把20多道复习题按照难度和题型做了分类然后设计了三轮复习节奏。第一轮是回顾加归纳。把讲义里的定理、公式、算法步骤用A4纸重新手写一遍不看书全靠记忆往外抽。抽不出来的地方就是薄弱点标红。这轮的重点是建立知识框架不用做题。第二轮是刷题加分析。把复习题按题型分组每组挑两道做精讲其他题做速算。手写解答时强迫自己分步骤写清楚每步都注明用到了哪个定理。这个过程非常痛苦因为很多题表面看是一个样子动手做才发现条件不够或者需要分类讨论。但恰恰是这些卡壳的地方是最有价值的复习内容。第三轮是模拟加查漏。把近两年的真题或者模拟题按考试时间要求三个小时闭卷独立完成。做完之后对着解答逐题核对把出错点整理成一张速查表。这张表是我考试前一晚唯一复习的资料。这三轮下来我的体会是第一轮建立框架第二轮培养手感第三轮发现盲区。手写解答不是抄答案而是把我以为我会了变成我真的会了的唯一途径。2. 五大高频题型的解题套路与答题要点2.1 对偶理论与灵敏度分析别只会背式子对偶理论在高等运筹学里几乎是必考题而且通常不是单纯让你写出对偶问题而是结合互补松弛定理求最优解或者做敏感性分析。先说说对偶问题怎么快速正确地写出来。标准形式是原始问题如果是最大化、约束为小于等于、变量非负那对偶问题就是最小化、约束为大于等于、变量非负。遇到非标准形式优先转为标准形再写对偶这样就避免了对偶变量符号出错。如果是混合约束或者自由变量就按约束方向决定对偶变量符号的规则逐条处理。接下来是互补松弛定理的应用。这个定理说的是如果原始问题某个约束在最优解处是松的即严格不等式那对应的对偶变量必须等于0反过来如果对偶变量大于0对应的原始约束一定取等号。考试里常见的出题方式是已经给出原问题和对偶问题的最优目标值让你利用互补松弛条件反推最优解。这类题卡住的地方往往是要判断哪条约束是被激活的判断完剩下的就是一个低维线性方程组的求解。灵敏度分析的话重点掌握目标函数系数变化范围和约束右端项变化范围两个计算套路。前者影响的是非基变量的检验数后者影响的是基变量的可行性。记住一个口诀系数的变化看检验数资源的变化看可行性。做题时先把标准形的单纯形表列出来不要直接背公式因为不同的教材松弛变量的位置不同公式中的符号也跟着变。2.2 非线性规划KKT条件的完整使用流程非线性规划在复习题里通常占一到大题最常考的就是KKT条件。不过这个题想答好有三件事必须提前做。第一件事是判断约束资质。我们平时用的是KKT条件的必要性但它成立需要满足一定的约束规格比如线性约束独立、Slater条件等。考试中如果你直接对非凸问题用KKT条件而不说明约束资质满足会被扣步骤分。所以我的习惯是先写一句约束函数均为线性/凸函数且满足Slater条件因此KKT条件是必要的再把推导摆上去。这一句话成本很低但能保证思路完整。第二件事是写出完整的KKT系统。拉格朗日函数写出来后要分成四条梯度条件、原始可行性、对偶可行性、互补松弛条件。有些同学只写梯度条件遗漏了对偶变量的非负约束导致求解时引入不满足条件的解。手写时我习惯用大括号把四个条件框在一起视觉上逼迫自己逐条检查。第三件事是求解KKT系统。这个系统本质上是一个带条件的分情况讨论一般需要对互补松弛条件按哪些约束取等号分类。不要怕分类多按每个不等式约束是否松弛来分最多也就三五类。很多题在分类后直接消掉一半因为某些情况会导致矛盾。我在答题时会把每种分类写清楚即使某类无解也写明该类无可行解——这种严谨性在阅卷时很加分。2.3 整数规划分支定界不是玄学整数规划的题目通常有两种形态一是建模题让你把实际问题写成0-1整数规划二是求解题用分支定界法或割平面法求解。建模题的话关键是识别典型约束的转化方式。互斥选择的项目用一组0-1变量和线性约束表示如果两个约束至少有一个成立引入大M法转化如果选择某个项目后必须先完成另一件事用前者必须推出后者的逻辑约束表示。题目千变万化但模型结构就那么几种手写解答时先列一个逻辑条件到线性约束的对照表再动手建模准确率高很多。分支定界法的手算过程很多人觉得繁琐其实是流程没理顺。正确步骤是先求解线性松弛问题如果最优解全是整数那它就是最终答案如果有的变量是小数挑选一个小数变量分支新增一个大于等于或小于等于的整数约束分别求解两个子问题的松弛问题。剪枝条件有三个子问题不可行、目标值小于当前下界求最大时、子问题已是整数解。这三个条件只要满足任意一个就不用再往下分支。手写解答时画分支树也很重要。我通常把每个节点标上松弛解是谁、目标值是多少、是否剪枝。这样即使计算全对但树画得乱阅卷人也没有耐心一个个核对。另外提醒一句分支变量要选离整数最远的也就是小数部分接近0.5的变量这样可以更快剪枝。2.4 动态规划状态设计的套路化方法动态规划在复习题里属于那种看起来简单但极易翻车的题型。最常见的是资源分配问题和最短路径问题。我的经验是动态规划解题关键不在背诵递推方程而在设计状态。状态必须包含所有影响后续决策的信息同时要尽可能精简。比如资源分配问题我惯用的状态定义是剩余资源量当前阶段而背包问题则是考虑前i件物品当前容量。只要状态定义合理递推方程几乎可以机械地写出来。递推方程手写时有两个容易出错的地方。一个是边界条件比如费了很大力气推导却忘了初始化f(0)0或者f(i,0)0导致整个递推失效。另一个是决策变量的取值范围有的题决策不是0到剩余量连续取而是有上限。我在手写解答时会先把边界条件和可选取值范围写在递推方程上方相当于给阅卷人一个这个递推域是完备的的证据。最后动态规划题一定要现场演算一个小规模例子。比如资源分配题只给了三台设备三个项目那完全可以手推算出每步的决策。考试答案是按步骤给分的从状态定义、边界条件、递推方程、小规模计算到最终最优解一步步呈现比直接写得解稳妥得多。2.5 网络流与其他冷门考点网络流虽然不是每年必考但经常作为综合题出现。最大流最小割定理是理论根子考试却很少考纯理论证明更多是给出一个网络让你用标号法求最大流并指出最小割。标号法的实操要点是正向边如果还有剩余容量就可以增广反向边如果流量大于0也可以回退。增广路找法是从源点出发按可标号规则一层层标记找不到新的增广路时已标号集合和未标号集合之间的割就是最小割。我踩过的坑是求完某个增广路后马上更新流量但忘记更新反向边的剩余容量。这个错误会导致后续迭代完全走偏。所以手写解答时我会把正向剩余容量和反向剩余容量两个数组都写在纸上每次增广后同步更新。另一个冷门考点是排队论常以M/M/1模型为主背熟Little公式和稳态概率的表达式就能应付关键是区分到达率、服务率、服务强度这些符号别把参数算反。3. 典型复习题手写解答实录3.1 对偶理论题互补松弛定理求最优解题目大意给出一个两变量三约束的线性规划问题已知原问题的最优目标值要求写出对偶问题并用互补松弛定理求原问题和对偶问题的最优解。我手写解答时是按这四步走的第一步把原问题写成标准形式逐条写出对偶变量。原问题如果是极大化问题对偶变量对应每条约束符号与实际约束方向有关。第二步明确互补松弛条件原问题第i个约束若为松约束则对应对偶变量y_i0若y_i0则原问题第i个约束取等号。第三步把已知最优目标值代入对偶目标函数结合y_i的取值和约束求出全部变量。第四步用原问题约束验证可行性如果有一个约束违反了说明对偶变量假设错了反向重新分类。这一题我在第一次做时错在偷懒默认所有对偶变量都大于0强行解线性方程组结果得到原问题不可行。后来才意识到互补松弛定理的价值就在于把哪些约束是紧的这个判断转化为哪些对偶变量是正的这个代数条件。先分类再求解是这题唯一正确的打开方式。3.2 非线性规划题KKT条件的完整展开题目大意求一个带三个不等式约束的非线性规划问题的最优解目标函数是凸二次函数约束是线性的。我使用的答题框架是六步一写出拉格朗日函数L f(x) - Σμ_i g_i(x)。注意这里的符号约定有的教材用加号有的用减号但KKT条件里的对偶可行性必须和符号约定保持一致。二声明约束资质满足Slater条件KKT必要。这里验证也很简单所有约束线性必满足线性约束规格。三列出梯度条件∇f(x) - Σμ_i ∇g_i(x)0。这条是矢量方程有几维就拆成几个标量方程。四列出原始可行性和对偶可行性g_i(x)≤0μ_i≥0。五列出互补松弛条件g_i(x)·μ_i0。如果g_i(x)0μ_i0如果μ_i0g_i(x)0。六分情况求解。我先把三个μ的是否大于0组合列成表格共4种情况排除全为0或部分为0逐一检查。每一种情况把g_i(x)0的约束当作等式组代入梯度条件解出候选点后验证其他约束是否满足。这道题的分情况讨论让我意识到写步骤时不要怕长最怕的是漏情况。漏一个分类可能刚好漏掉最优解。3.3 动态规划题资源分配的标准递推题目大意三个项目共享一定资源每个项目投资不同金额产生不同收益求总收益最大的分配方案。我的状态设计是f_k(s)表示前k个项目共使用s单位资源时的最大总收益决策d_k是第k个项目分得的资源数取值范围0到s。递推方程写作f_k(s) max { r_k(d) f_{k-1}(s-d) }其中0≤d≤sr_k(d)是第k个项目投资d单位的收益。边界条件写f_0(0)0f_0(s0)-∞。这个边界条件的意思是没有项目时只有资源零才可能其他情况不可行。然后我从k1开始逐层手算收益表。计算时我会把每个s下的最优d用下划线标出来方便最后追踪最优方案。这个小习惯帮我避免了很多因追溯失误而丢分的情况。最后一问通常是给出最优资源分配方案有些人算完最优值就停了没答分配方案白白丢分。我提醒自己在答案最后补一句此时三个项目的分配分别为...作为收尾。3.4 手写解答的排版规范与验算习惯手写解答有没有统一格式我觉得有。我在复习阶段采用的格式是题号、题干摘要、解题思路一句话、详细步骤、答案、验算栏。这样做的目的是考场上如果时间不够阅卷人至少能在前面看到思路后面的步骤即使略写也有个骨架。验算方面我有一套固定动作。首先是数值回代线性规划求出最优解后带回约束条件看是否可行、目标值是否一致非线性规划求出的候选点带回KKT条件逐条核对动态规划算出的收益表用另一个顺序方向重推一次看看结果是否一致。这些验算动作看似浪费时间但实际能挽回的分数非常可观。我复习过程中有超过一半的重大发现都是靠验算找到的比如某道动态规划题我用反向递推重新计算时发现正向递推的某个f值抄错了直接把一道题的分救回来一半。4. 高频易错点与排查实战4.1 易错点速查表我把手写解答过程中遇到的错误整理成一张表贴在了书桌正前方。下面是其中一部分题型 | 常见错误 | 排查方法 线性规划对偶 | 忘了对偶变量的符号规则写错约束方向 | 先转标准形再写对偶逐条对照约束方向决定变量符号 灵敏度分析 | 只改RHS不重算B逆导致最优基判错 | 每次算完变化范围后重新检查对偶可行性和原始可行性 非线性规划KKT | 漏掉对偶变量非负约束解出不可行点 | 每个候选点都返回KKT系统逐条验对偶可行性 动态规划 | 状态定义不完整导致递推时漏信息 | 反问自己当前处于哪一阶段还剩下什么资源/能力 分支定界 | 剪枝时忽略子问题整数解且目标值更优的情况 | 三个剪枝条件逐条口头核对缺一不可 排队论 | 到达率与服务率搞反计算ρ时用错分母 | 先用文字标注单位时间平均到达数/服务数再代入这张表不是理论总结而是我亲手踩过的坑。宁可多花两分钟检查也不要因为粗心丢掉计算题的分。4.2 翻车场景复盘与应急思路我复习时有过一次特别惨烈的模拟考试。三个小时里我卡在第一道非线性规划题上整整四十分钟原因是我一开始假设所有约束都取等号解出来一个候选点却违背了对偶可行性然后我不敢推翻重来硬往下套越套越乱。还有一道动态规划题我状态设计把资源维度写漏了导致递推方程算出来的结果跟题目数据完全对不上最后只能崩溃放弃。复盘之后我给自己定了几条考场应急策略如果KKT分类中初始假设出错立刻放弃这个方向回到分情况表格重新选择未尝试的分类。因为这类题通常有一个显然可以跳过的情况只要分类表是完整的换一个分类最多花五分钟。如果动态规划的状态设计出问题先停下来检查边界条件和状态维度。在草稿纸上用小例子验证递推方程比如只有一项资源时能不能算对。千万别在错误的状态上推下一层那只会让错误不断积累。4.3 考场时间分配与答题顺序建议期末卷子一般五到六道大题三个小时。我建议的时间分配是大致均匀的但有个原则先做自己最有把握的题。具体来说一到考场先快速扫一遍所有题目花半分钟判断每道题属于哪个模块。线性规划对偶、动态规划这类套路清晰的题先写非线性规划KKT这类计算量大、分类多的题放在中间如果遇到冷门题型或者没有见过证明题留到最后。每道题的时间控制在二十五到三十分钟。如果一道题卡了超过十分钟果断跳过优先保障其他题目的完整度。千万别出现一道题做了五十分钟剩下五道题只能瞎写的情况。另外考场上留出最后十五分钟做统一验算。这十五分钟检查的不是答案对不对而是检查符号、单位、是否回答了所有小问。丢分往往不是因为不会做而是因为漏答。5. 最后的经验心得经过这段时间的手写解答我最大的感受是高级运筹学复习的核心其实是把每一步合理性说清楚。计算题大家都算得出来真正区分分数的是过程完整性和逻辑严谨性。我的建议是复习时不要总盯着答案对不对而是每次做完一道题都复盘一遍我为什么在这个地方用了这个定理这个步骤为什么可行。期末前一周我用一种特别笨但有效的办法拿着打印好的复习题清单不看答案在空白纸上把每个题型的完整解答步骤默写一遍。能够默写出来的就是掌握了的默写不出来的就翻到错题本里再写一遍。反复两三轮之后这些套路基本就刻在脑子里了。最后分享一个我反复使用的小技巧手写解答时一定要留白。每道题做完在纸的侧面留出空位等隔天再看一遍的时候把新的理解补上去。这个做法让我的复习资料变成了一个活的笔记而不只是一次性的草稿纸。希望这份手写解答记录对你的复习有帮助。运筹学的魅力就在于它让问题可以被结构化地思考哪怕题目千变万化核心的思路框架永远是那几步。祝期末顺利。