☰
运筹学期末复习必备:线性规划、对偶理论与运输问题考题精讲
2026/10/7 15:24:04 网站建设 项目流程

每到期末,办公室里被问得最多的就是“运筹学怎么复习”。这门课有个特点:教材厚、算法多、概念杂,但真正会考的无非那几种题型。很多同学看书觉得全会,一上考场填空填不出、计算算不完,问题就出在复习时只动眼不动手。这份运筹学考题汇总,我按填空题和计算题两大题型整理,全部配了解析和答案,覆盖线性规划、对偶理论、运输问题、动态规划、图论与网络优化这些高频考点。不管你是期末冲刺、准备考研复试,还是工作中想把决策模型重新捡起来,这套题都可以直接上手。

1. 内容整体设计与思路拆解

1.1 运筹学考试到底在考什么:核心考点扫描

先说结论:运筹学考试虽然各个学校教材版本不同,但出题范围高度集中。我把主要章节的考查情况整理成一张表,复习之前先对着这张表检查自己的知识框架。

章节核心考点常见题型重要程度
线性规划建模、标准形式、图解法、单纯形法填空+计算★★★★★
对偶理论对偶问题写法、影子价格、互补松弛性填空+计算★★★★
灵敏度分析目标系数、资源量的变化范围分析填空★★★
运输问题表上作业法、最小元素法、位势法计算★★★★
整数规划0-1规划、分支定界法计算★★★
动态规划最优性原理、逆推法、背包问题填空+计算★★★★
图论最短路、最大流、最小生成树填空+计算★★★★
排队论M/M/1指标、Little公式填空★★★

线性规划和运输问题永远是出题大头,因为这两个模块一个是“建模能力”的典型代表,一个是“算法流程”的典型代表。整数规划和动态规划各有侧重,整数规划考分支定界或割平面法,动态规划则几乎必考背包问题。图论模块最稳定,最短路的Dijkstra算法和最大流的标号法属于“背下流程就会做”的题目,性价比很高。排队论在大多数院校以填空或简答形式出现,重点记公式,不太会上复杂计算。

1.2 为什么按“填空+计算”的题型组合来复习

这个问题我每届都跟学生讲。填空考的是一句话的精确性,计算考的是整个流程的完整性,两种题型正好互补。

填空题要求你把概念记到一字不差。比如“产销平衡运输问题中基变量的个数为m+n-1”,这里的“m+n-1”就是标准答案,写“m×n-1”或者“n+m-2”都不给分。考试时填空往往是整张试卷里最容易丢分的地方,因为你觉得你懂了,但落到笔头才发现表述不严谨。

计算题则考你算法执行的颗粒度。单纯形法迭代一步都不能跳,运输问题里的位势法每一步都得有据可循,这类题不看结果只靠蒙是拿不到分的。所以用“填空+计算”的组合来复习,本质上是“知识框架+算法技能”双通道同时过,比单纯刷综合题要高效得多。

1.3 这套考题汇总怎么用:三遍刷题法

第一遍:限时做。填空部分控制在20分钟内,计算题每题15分钟。做完不要急着对答案,先标记出不确定的题目。限时的目的是逼出真实水平,很多错误只有在这种状态下才会暴露。

第二遍:精做和分析。每一道错题都要回归课本找出对应知识点,把解题步骤完整写一遍。尤其是计算题,哪怕结果对了,也要检查中间过程是否规范。我见过太多学生答案正确但步骤跳步,被扣分后还不服气,其实考试看的就是步骤。

第三遍:考前两三天,只看题目列表,自己复述解题过程和答案。能说出来,才算真正掌握。

2. 填空题考点精讲与答案详解

2.1 线性规划核心概念:标准形式与解的性质

填空题1:线性规划问题中,可行域是____集,若最优解存在,则一定可在可行域的____处达到。

答案:凸;顶点(极点)。

解析:这道题考线性规划几何意义中的两个基本结论。可行域由若干半平面的交集构成,半平面是凸集,凸集的交集仍然是凸集;线性目标函数在凸多面体上的最值一定在某个顶点取得。这里容易混淆的是第二个空,填“边界”不准确,虽然最优解可能出现在一条边界线段上,但题目问“一定可以”,只有顶点是必然保证的。复习时可以顺手把线性规划解的情况和几何特征对应起来:唯一最优解对应顶点,多重最优解对应等值线与边界平行,无界解对应可行域开放方向。

填空题2:将线性规划问题化为标准形式时,若目标函数为求最小值,需要将目标函数系数取____;若约束条件为“≥”型不等式,需要引入____变量;所有决策变量要求____。

答案:相反数;剩余;非负。

解析:标准形式的规定各教材略有差异,但核心三条不变:目标统一、约束统一、变量非负。最小值问题有两种处理方式,一是把目标函数变成求负值最大值,二是直接规定标准形式为min z = cx,但大多数教材习惯统一为max;约束条件“≥”引入的是剩余变量,系数为-1,这一点和“≤”约束引入松弛变量的处理方式不同,很容易写混。

填空题3:若线性规划问题存在多重最优解,则在单纯形法最终表中,存在某个非基变量的检验数为____。

答案:0。

解析:单纯形法判断最优解时,所有检验数σj≤0(最大化问题)。如果某个非基变量检验数正好等于0,说明这个变量入基不会改变目标函数值,意味着存在另一组最优基本可行解。这个结论也解释了为什么检验数出现0就是多重最优解的信号。

填空题4:用单纯形法求解最大化线性规划问题时,当全部检验数满足____条件,且基变量中不存在人工变量,当前解即为最优解。

答案:σj≤0(非正)。

解析:这里最容易被大意的点在于符号方向。最大化问题最优性条件是检验数≤0,最小化问题反而是检验数≥0。每次考完试总有人把这俩弄反,建议自己总结一句口诀:求最大,检验数非正停;求最小,检验数非负停。

2.2 对偶理论与灵敏度分析:方向关系最易出错

填空题5:弱对偶定理指出,若原问题为最大化问题,则对偶问题的任意可行解对应的目标函数值____原问题任意可行解对应的目标函数值。

答案:不小于(≥)。

解析:这是对偶理论里错误率最高的一空。很多同学记住了“对偶值不小于原值”这句话,但考试换了一种问法就蒙了。弱对偶定理实际上说的是:最大化问题的目标函数值永远不会超过最小化问题的目标函数值。所以对偶问题(最小化)的目标函数值在原问题(最大化)目标函数值之上。

填空题6:在原问题和对偶问题都有可行解的情况下,二者最优目标函数值____。

答案:相等。

解析:这是强对偶定理的直接结论。如果看到这个结论,可以顺便回忆一下互补松弛定理,它们经常在同一次考试中出现。互补松弛定理强调原问题和对偶问题最优解之间的对应关系,即如果一个变量取正值,则对应对偶约束取等号。

填空题7:对偶问题最优解中某个变量的值,称为对应原问题某种____的影子价格。

答案:资源。

解析:影子价格的经济含义是:政府或企业每增加一单位这种资源,目标函数最优值会增加多少。它的数学定义就是对偶问题的最优解分量,考试中常与灵敏度分析结合出题,比如问“某种资源影子价格为2,则该资源增加1单位后目标函数最优值增加多少”,答案就是2。

填空题8:在某线性规划问题中,若第i种资源增加一个单位后目标函数值从70变为72,则该资源的影子价格为____。

答案:2。

解析:影子价格不是资源的市场价格,而是资源在现有生产结构中的边际价值。注意这个结论只在资源增量不超过灵敏度分析给出的允许变化范围时才有效,一旦超出范围,原本的基可能发生变化,影子价格也会跟着变。

2.3 运输问题、动态规划与图论:专题概念容易混

填空题9:产销平衡运输问题中,基变量的个数为____;用表上作业法判断最优性时,需要保证所有非基变量的检验数____。

答案:m+n-1;非负(≥0)。

解析:运输问题基变量个数的公式是m+n-1,这个结论由约束方程组秩为m+n-1导出。注意题目问的是产销平衡的情况,如果不平衡要先化为平衡再用公式。检验数符号规则再次出现,运输问题是求最小运费,所以非基变量检验数全部≥0为最优,与单纯形法最大化问题的判断方向正好相反。

填空题10:动态规划依据的最优性原理指出,无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的决策必然构成____。

答案:最优策略。

解析:这是贝尔曼最优性原理的经典表述。很多同学背了动态规划“从后往前推”“状态转移”这些操作,却说不清原理本身。如果填空题出到这句话,必须一字不差地写清楚。

填空题11:Dijkstra算法适用于所有边权____的网络最短路问题;若图中存在负权边,应采用____算法。

答案:非负;Bellman-Ford。

解析:Dijkstra算法每次从未标记节点中选出距离最小的节点进行扩展,由于假设边权非负,才能保证当前标记的距离已经是最终最短路。如果存在负权边,这个前提被打破,Dijkstra会失效,必须改用Bellman-Ford算法。

填空题12:在最大流问题中,最大流的值等于最小____的容量。

答案:割。

解析:最大流最小割定理是网络流的理论基石。割的定义是:将顶点集合分成包含源点和汇点的两个集合S和T,从S到T的所有有向弧的容量之和。考试中如果让手工求最大流,一旦当前流值等于某个割的容量,就可以立刻确认已经是最大流了,不需要再继续找增广链。

填空题13:在M/M/1排队模型中,若顾客到达率为λ,服务率为μ,则服务强度ρ=,系统空闲的概率P0=。

答案:λ/μ;1-ρ。

解析:排队论的填空通常就是套公式。服务强度ρ=λ/μ,当且仅当ρ<1时系统才稳定。空闲概率P0=1-ρ,服务台繁忙的概率就是ρ。这几个公式连在一起考,看你能不能分清条件的适用前提,即λ<μ。

3. 计算题真题实战:题型拆解与完整求解

3.1 线性规划双解法:图解法直观定位,单纯形法规范求解

计算题1:求解以下线性规划问题。

max z = 3x1 + 2x2 s.t. 2x1 + x2 ≤ 8 x1 + 2x2 ≤ 7 x1, x2 ≥ 0

这道题我特意选了两个变量的经典形态,因为两个变量的线性规划既能用图解法展示几何意义,又能用单纯形法展示代数迭代,一举两得。考场上碰到两个变量的题,优先考虑图解法,快且不容易算错。

先用图解法。画出约束线2x1+x2=8和x1+2x2=7,加上坐标轴围出可行域。这个可行域是一个四边形,四个顶点分别是O(0,0)、A(4,0)、B(3,2)、C(0,3.5)。将四个点代入目标函数:z(0,0)=0,z(4,0)=12,z(3,2)=13,z(0,3.5)=7。所以最优解为x1=3、x2=2,最优值z*=13。

图解法的本质是拿目标函数等值线在可行域上平移,最后一根碰到可行域的等值线对应的目标函数值就是最大值。碰到顶点时是唯一最优解,碰到边界线时是多重最优解,如果可行域无界还可能无界解,这三种情况考试都出现过。

再用单纯形法验证一遍。将问题化为标准形,引入松弛变量x3、x4:

max z = 3x1 + 2x2 + 0x3 + 0x4 s.t. 2x1 + x2 + x3 = 8 x1 + 2x2 + x4 = 7 x1, x2, x3, x4 ≥ 0

初始单纯形表如下:

cj3200θ
CB基变量bx1x2x3
0x38211
0x47120
σj320

选择检验数最大的正数对应的变量x1入基,θ=min{b_i/a_i1 | a_i1>0}=min{8/2, 7/1}=4,所以x3出基。以2为主元做一次行变换,得到:

cj3200θ
CB基变量bx1x2x3
3x1410.50.5
0x4301.5-0.5
σj00.5-1.5

此时x2的检验数0.5为正,继续入基。θ=min{8, 3/1.5}=2,x4出基。以1.5为主元再进行一次行变换,得到最终表:

cj3200
CB基变量bx1x2
3x1310
2x2201
σj00

检验数全部≤0,迭代结束,结果和图解法一致:x1=3,x2=2,z*=3×3+2×2=13。

提示:单纯形法出基变量选择时,θ=min{基变量值/入基列正系数}。这里最容易犯错——有人会把分母为0或负数的行也拿来做比值,一定要排除掉。

3.2 对偶问题与影子价格:互补松弛性的标准用法

计算题2:写出计算题1中线性规划问题的对偶问题,并求两种资源的影子价格。

原问题是:

max z = 3x1 + 2x2 s.t. 2x1 + x2 ≤ 8 x1 + 2x2 ≤ 7 x1, x2 ≥ 0

第一个约束对应资源1(总量8),第二个约束对应资源2(总量7)。设对偶变量为y1、y2,对偶问题为:

min w = 8y1 + 7y2 s.t. 2y1 + y2 ≥ 3 y1 + 2y2 ≥ 2 y1, y2 ≥ 0

对偶问题的规则是:原问题max,对偶问题就min;原问题约束“≤”,对偶问题约束“≥”;原问题变量非负,对偶问题变量非负。如果原问题约束是“≥”或变量无符号限制,对偶形式会变形,那是另一套规则,建议把四种对应关系写在一张卡片上反复背。

利用互补松弛定理求影子价格。原问题最优解x1=3>0,x2=2>0,两个变量都大于0,所以对偶问题的两个约束在最优解处必须取等式:

2y1 + y2 = 3 y1 + 2y2 = 2

解这个方程组:第一个式子减去两倍的第二个式子(或者用消元法),从2y1+y2=3可得y2=3-2y1,代入y1+2y2=2得到y1+2(3-2y1)=2,即y1+6-4y1=2,所以-3y1=-4,y1=4/3;代回去y2=3-8/3=1/3。

因此影子价格y1=4/3≈1.33,y2=1/3≈0.33。验证对偶目标值:w*=8×(4/3)+7×(1/3)=32/3+7/3=39/3=13,与原问题最优值相等,符合强对偶定理。

影子价格的意义是:资源1总量每增加1个单位,最大利润约增加1.33单位;资源2全长量每增加1个单位,最大利润约增加0.33单位。企业在决策时可以拿影子价格和资源市场价比较——如果市场价低于影子价格,应当增加购买这种资源;反之则不应扩展。

提示:互补松弛定理使用前提是拿到原问题最优解。如果原问题有的变量为0,对应那一行对偶约束就不要写成等式,而写成不等式,然后结合对偶可行性和目标值相等的条件去解。

3.3 运输问题全流程:最小元素法搭初始方案,位势法验最优

计算题3:有三个产地A1、A2、A3,产量分别为10、15、20;四个销地B1、B2、B3、B4,销量分别为8、12、10、15。单位运价表如下:

产地\销地B1B2B3B4产量
A1534610
A2423515
A3365420
销量812101545

先检查产销平衡:总产量=10+15+20=45,总销量=8+12+10+15=45,恰好平衡,可以应用表上作业法。

第一步,最小元素法求初始方案。从运价表里找最小运价:B2列A2行运价为2,优先安排A2给B2供货,分配min(15,12)=12,A2剩余3,B2需求归零。接着找剩余未分配中的最小运价:A2-B3运价3,分配min(3,10)=3,A2用完,B3剩7。继续:A3-B1运价3,分配min(20,8)=8,A3剩12,B1需求归零。然后A1-B3运价4,分配min(10,7)=7,A1剩3,B3需求归零。再然后A3-B4运价4,分配min(12,15)=12,A3用完,B4剩3。最后A1-B4运价6,分配min(3,3)=3,A1用完,B4需求归零。初始运输方案如下表:

产地\销地B1B2B3B4
A173
A2123
A3812

初始运费=7×4+3×6+12×2+3×3+8×3+12×4=28+18+24+9+24+48=151。

基变量数量是6个,恰好等于m+n-1=3+4-1,说明没有出现退化的情况,可以直接进入下一步。

第二步,位势法检验最优性。设u1=0,对每个基变量计算vj=cij-ui或ui=cij-vj。由(A1,B3)得v3=4;由(A1,B4)得v4=6;由(A2,B3)得u2=3-4=-1;由(A2,B2)得v2=2-(-1)=3;由(A3,B4)得u3=4-6=-2;由(A3,B1)得v1=3-(-2)=5。

对每个非基变量计算检验数σij=cij-ui-vj:

非基变量检验数
(A1,B1)5-0-5=0
(A1,B2)3-0-3=0
(A2,B1)4-(-1)-5=0
(A2,B4)5-(-1)-6=0
(A3,B2)6-(-2)-3=5
(A3,B3)5-(-2)-4=3

所有检验数≥0,当前方案已是最优方案。最小总运费151。

这里有一个考试中常考的知识点:非基变量检验数出现了0,说明运输问题存在多重最优解。比如(A1,B1)检验数为0,玩家可以沿闭回路调整得到另一组最优解,总运费不变。如果考题问“是否有多个最优方案”,答案就是有。

提示:位势法检验完成后,顺手检查一下基变量对应的检验数是否全部为0。如果不为0,说明位势计算过程中某一环错了,需要回溯检查。

3.4 0-1背包问题:动态规划递推表与方案回溯

计算题4:有4件物品,重量分别为2、3、4、5,价值分别为3、4、5、6,背包容量为9。在不超过背包容量的前提下,如何选择物品使总价值最大?

设f_i(w)表示只考虑前i件物品、背包容量为w时的最大总价值。状态转移方程为:

f_i(w) = max{ f_{i-1}(w), f_{i-1}(w - wi) + vi } 当 w ≥ wi f_i(w) = f_{i-1}(w) 当 w < wi

第一项对应不装第i件物品,第二项对应装入第i件物品。初始f_0(w)=0对所有w成立。

逐个物品填表。第1件物品(w=2, v=3):容量1及以下装不了,容量2开始价值为3。第2件物品(w=3, v=4):容量3时max(3,4)=4,容量5时max(3,3+4)=7,也就是同时装第1件和第2件。第3件物品(w=4, v=5)加入后,容量6时3+5=8,容量7时4+5=9,容量9时7+5=12。第4件物品(w=5, v=6)加入后,容量8时9的旧方案和3+6=9打平,容量9时旧方案12仍优于6+6=11。

完整递推表如下:

i\容量0123456789
00000000000
10033333333
20034477777
300345789912
4003457891012

f_4(9)=12,即最大总价值为12。但考试通常还会追问“装哪几件”,这时候不能只看最后的值,要做回溯。从f_4(9)开始:f_4(9)=f_3(9),说明第4件物品没装;f_3(9)=12=f_2(5)+5,说明第3件物品装了,剩余容量为9-4=5;f_2(5)=7=f_1(2)+4,说明第2件物品装了,剩余容量为5-3=2;f_1(2)=3=f_0(0)+3,说明第1件物品装了。最终选择物品1、2、3,总重量2+3+4=9,总价值3+4+5=12。

动态规划这块,很多人觉得填表难,其实填表是机械劳动,真正理解后最有趣的是回溯。回溯的过程相当于回答“最优方案是什么”,而不是停留在“最优值是多少”。建议平时练习时每次填完表都倒着走一遍,养成习惯,考试时就不慌。

提示:如果遇到“物品可以分割”的背包变形,那是分数背包问题,直接按单位价值排序用贪心,不能用这个动态规划表;动态规划适合的是0-1整数选择场景。

3.5 最短路问题:Dijkstra算法手算全程

计算题5:求下图网络中从v1到v6的最短路径,边上数字为距离权重。

网络结构如下(文字描述):

v1 —(2)— v2 v1 —(5)— v3 v2 —(1)— v3 v2 —(6)— v4 v3 —(2)— v4 v3 —(3)— v5 v4 —(4)— v5 v4 —(7)— v6 v5 —(1)— v6

用Dijkstra算法。维护一个已标记节点集合S,以及每个节点到v1的当前最短距离d(v)。初始时d(v1)=0,其余d=∞,S为空。

第一步:选择距离最小的未标记节点v1,标记v1。更新v1邻接点:d(v2)=min(∞,0+2)=2,d(v3)=min(∞,0+5)=5。

第二步:未标记节点中d最小的是v2(d=2),标记v2。更新v2的邻接点:d(v3)=min(5,2+1)=3,d(v4)=min(∞,2+6)=8。

第三步:未标记节点中d最小的是v3(d=3),标记v3。更新v3的邻接点:d(v4)=min(8,3+2)=5,d(v5)=min(∞,3+3)=6。

第四步:未标记节点中d最小的是v4(d=5),标记v4。更新v4的邻接点:d(v5)=min(6,5+4)=6,d(v6)=min(∞,5+7)=12。

第五步:未标记节点中d最小的是v5(d=6),标记v5。更新v5的邻接点:d(v6)=min(12,6+1)=7。

第六步:标记最后一个节点v6。

用表格记录整个迭代过程:

迭代标记节点d(v1)d(v2)d(v3)d(v4)d(v5)d(v6)
0无0∞∞∞∞∞
1v1025∞∞∞
2v20238∞∞
3v302356∞
4v40235612
5v5023567
6v6023567

v1到v6的最短距离为7。路径回溯:d(v6)=7由v5更新(前驱为v5),d(v5)=6由v3更新,d(v3)=3由v2更新,d(v2)=2由v1更新,所以最短路径为v1→v2→v3→v5→v6,总长度2+1+3+1=7。

Dijkstra算法每轮只标记一个节点,更新一次距离表,考试时按轮次画表就不会乱。注意已经标记的节点不要重复更新,这是很多同学手算时出错的原因。

提示:Dijkstra算法无法处理负权边。如果题图中出现负数权重,必须改用Bellman-Ford算法,考试时优先检查边权符号,这往往是出题人埋的坑。

3.6 最大流问题:标号法求增广链与最小割验证

计算题6:求以下网络中从源点s到汇点t的最大流,括号内为容量。

网络如下(文字描述):

s —(4)— v1 s —(3)— v2 v1 —(2)— v2 v1 —(3)— v3 v2 —(2)— v3 v2 —(3)— t v3 —(4)— t

用标号法(Ford-Fulkerson方法)求最大流。从零流开始,每次找一条从s到t的增广链,取该链上各边剩余容量的最小值为增广量。

找第一条增广链:s→v1→v3→t,各边剩余容量分别为4、3、4,瓶颈为3,沿链增广3个单位。此时总流量为3,s-v1剩1,v1-v3已满,v3-t剩1。

找第二条增广链:s→v2→t,剩余容量分别为3、3,瓶颈为3,增广3个单位。此时总流量为6,s-v2已满,v2-t已满。

找第三条增广链:s→v1→v2→v3→t,各边剩余容量为1、2、2、1,瓶颈为1,增广1个单位。此时总流量为7,s-v1已满,v3-t已满。

当前流量为7。尝试继续找增广链:从s出发的正向边s-v1和s-v2都已达到剩余容量0,v1和v2无法得到标记,不存在s到t的增广链。因此当前流就是最大流,最大流值为7。

验证最大流最小割定理:取割(S,T),其中S={s},割的容量为从S指向T的所有边的容量之和,即s-v1的4加上s-v2的3,等于7。最大流等于最小割容量,结论一致。

网络流问题在考场上最怕的是“找不到增广链就宣布结束”,但没有把握时一定要用最小割验证。一旦当前流值等于某个割的容量,就必然是最优流,这是做题最稳的收尾方式。

4. 常见易错点与高频丢分细节

4.1 填空题里最容易失分的5个概念细节

第一,松弛变量和剩余变量名称混用。“≤”约束引入的是松弛变量,“≥”约束引入的是剩余变量,虽然都起“把不等式变成等式”的作用,但符号相反、名称不同,填空题里写错直接扣分。

第二,弱对偶定理的不等号方向。记住一个判断技巧:最大化问题求上界,对偶问题的目标函数值是这个上界的一个估计值,所以对偶值≥原值。强对偶定理才让两个值相等。

第三,运输问题基变量个数m+n-1。经常有人写成m×n-1或者m+n,这个空纯粹靠记忆,没有推导过程的投机取巧。考试前默写三遍,比做十道题都管用。

第四,动态规划最优性原理的表述。填“最优策略”而不是“局部最优”,这是概念精确性的体现。

第五,Dijkstra算法适用范围是“非负权”,不是“非零权”,更不是“无环”。这三个概念连在一起考的时候最好辨析清楚,负权边场景要用Bellman-Ford,带负环场景根本没有有限最短路。

4.2 计算题步骤中的高频错误盘点

单纯形法里,出基变量的最小比值选择是个重灾区。正确操作是:用b列除以入基变量列的正系数,取最小值。很多同学把负系数和零也拿来参与比值,这种情况在迭代几次后尤其容易发生,结果选错出基变量,整个迭代崩盘。

对偶问题写法里,原问题是max,约束是≤,对偶约束就是≥;原问题变量≥0,对偶变量≥0。一旦原问题某个约束是等式,对偶变量就没有非负约束了。考试时如果发现题目里出现等式约束,对偶写法要多留个心眼。

运输问题最小元素法分配时,如果某行产量和某列销量同时满足,只能划去一行或一列,同时要在另一个未划掉的位置补一个0运量,保证基变量数量仍然是m+n-1。这一步叫“退化处理”,不会的人往往在这里卡住,导致后续位势法无法执行。

动态规划回溯时只看最优值不回溯方案。很多学生算出f_4(9)=12就觉得完事了,但考试问的是“选择哪些物品”。平时练习就养成“算完值必须走一遍回溯”的习惯,考场上才不会遗漏。

最大流问题里忘记检查反向边。Ford-Fulkerson标号法在找增广链时,如果正向边已饱和,但可以通过某条反向边“退回”之前的流量,也有可能形成增广链。有的题专门靠反向边出陷阱,只看正向边会漏解。

4.3 考前一周到考场的实用冲刺建议

考前一周,不再追求做新题,而是回归基础。填空题部分每天过一遍,把13道填空涉及的结论盖住答案,自己默写。计算题每天完整做两道,挑最典型的线性规划和运输问题,做完后对照规范步骤检查自己有没有跳步。

考前一天晚上,把单纯形法迭代规则、对偶问题写法、最小元素法和位势法步骤、动态规划递推方程、Dijkstra和标号法流程这五块内容再过一遍。不用做全题,但要把步骤“过一遍电影”。

考试做题顺序建议先做计算题再做填空题。计算题分值高,而且一旦状态进入之后思路会越来越顺,填空题概念性判断需要靠记忆和熟练度,放到后面做不会因为紧张而忘了基础结论。时间分配上,填空控制在30分钟以内,计算题平均每题12到15分钟,最后留10分钟检查单纯形表的符号和运输方案的完整性。

我个人带复习的实际体会是,运筹学考高分的人往往不是天赋最好的,而是动手最多的。这套题目里的每一道都是经典套路,如果你能不看答案独立做出每一步,考场上大概率问题不大。还有一个很实用的小技巧:每做完一道计算题,都把自己代入“阅卷老师”的角色,检查一下这一步不看前面过程能不能看懂,这样能逼着你自己把步骤写规范。

需要专业的网站建设服务?

联系我们获取免费的网站建设咨询和方案报价,让我们帮助您实现业务目标

立即咨询