每年到这个时间点后台就会收到一波运筹学备考的消息。不是问“线性规划单纯形法最后一行怎么判最优”就是问“运输问题用最小元素法求完初始解位势法到底怎么算检验数”。我这份汇总就是把期末试卷和考研真题里反复出现的填空题、计算题按题型剥开把答案和踩坑点一起放出来题目不多但每一道都值得动手做一遍。这份整理适合三类人一是考前突击、需要快速过一遍考点的同学二是想检验自己复习质量、专门找题练手的人三是已经工作但准备考非全、需要拾起运筹学基础的朋友。填空题部分覆盖了概念、图像性质、对偶理论、灵敏度分析、排队论这些“背了就有分”的点计算题部分则集中在单纯形法、对偶问题、运输问题、指派问题和动态规划这几个必考大类。每道题我都尽量给出“解题过程答案为什么这么做”不是单纯把答案堆在最后让你自己对。先提醒一句运筹学这门课最忌讳的就是只看不练。你觉得自己看懂了单纯形法闭上书试试从建模写到最优解表格大概率在某一列上卡住。下面这些题建议先拿纸笔做一遍再对照答案看差异这样收获完全不一样。1. 试卷结构心里有数各知识板块的出题权重与考察逻辑运筹学考卷虽然学校不同但出题套路相当稳定。一般来说填空、选择这类小题占总分30%左右计算题占60%以上剩下是建模题或简答题。计算题里线性规划纯属必考要么直接考单纯形法计算要么考对偶理论加灵敏度分析这块在多数试卷里占20到25分。运输问题紧跟其后大概率考一个产销平衡的求初始调运方案加位势法检验15分左右。整数规划、图论、动态规划、排队论、存储论等板块中学校会根据课时多少选两到三个来考。不同知识板块的考察逻辑也很清晰。填空题侧重概念辨析与公式记忆比如“满足约束条件和非负条件的解叫什么”“产销不平衡时要引进什么变量”考的是你对定义是否精准计算题则看你能不能把流程走完比如单纯形法从初始可行解开始迭代中间任何一步算错后面最优解必然不对但多数老师会按步骤给分算出基变量、检验数这些中间结果也有分所以过程一定不能省。理解出题逻辑对复习方向很有帮助。我的建议是先把线性规划和运输问题这两块练到“闭着眼都能算”的程度再花时间背填空考点最后处理其他计算题板块。因为线性规划和运输问题分值最重、题型最程序化性价比最高。2. 填空小题别忽略背下这些高频考点就能稳拿基础分填空题分值看似不大但胜在数量多、覆盖面广。很多同学把精力全放在计算题上结果填空题失分严重非常可惜。下面这些是我从多套真题里筛选出的高频考点每题都附答案和一句解析。2.1 基础概念与模型辨析题目1在线性规划问题中由所有约束条件和非负条件共同确定的变量取值范围称为____。答案可行域或称可行解集。解析这里注意和“可行解”区分可行域是集合可行解只是其中的一个点。题目2若线性规划问题存在可行解但其目标函数值无界则称该问题____。答案有无界解或无最优解。解析考试经常会写成“无最优解”阅卷时也算对。但严格说教材先用“无界解”描述原因再得出结论“无最优解”答题时写后者更稳妥。题目3线性规划问题的标准形式中目标函数一律转化为____形式约束条件一律转化为____且所有决策变量____。答案求最大值等式约束加松弛变量/减剩余变量后非负。解析标准形式的三要素max、等式约束、变量非负这是单纯形法计算的前提。如果题目给的是min要转换成max再计算转换方式是令z -z。题目4若线性规划问题存在最优解则最优解必定能在可行域的某个____上达到。答案顶点极点。解析这是线性规划基本定理的结论。图解法中最优解一定在交点处就是顶点。这一条是填空题的钉子户。题目5线性规划问题中若某一基变量取值为零则称该基本可行解为____。答案退化的基本可行解退化解。解析退化问题在单纯形法迭代时可能导致循环但考试一般只考概念。注意“退化解”是“基本可行解退化”不是“可行解退化”。2.2 对偶理论与影子价格题目6线性规划原问题有最优解则对偶问题____有最优解且两者最优目标函数值____。答案也一定相等。解析这是对偶理论中的强对偶定理。考试填空题经常反过来考如果原问题目标函数无界对偶问题一定不可行。题目7影子价格的经济含义是指在其它条件不变的情况下某种资源每增加一个单位目标函数最优值所____的数量。答案增加严格说是相应增加的量可正可负。解析影子价格等于对偶问题的最优解对偶变量对应的是资源的边际价值。注意如果约束是“≥”类型影子价格的含义有所不同但基础题一般考察的是“≤”资源约束。题目8若原问题中某个约束条件为“≤”形式则其对偶变量满足____约束。答案非负≥0。解析对偶变量符号与原问题约束方向有关。约束为“≤”且目标求max时对偶变量≥0约束为“”时对偶变量无符号限制。2.3 运输问题与指派问题题目9在运输问题中当总产量大于总销量时可以通过增加一个____使其转化为产销平衡问题。答案虚拟销地。解析虚拟销地对应的运价通常设为0其销量等于总产量与总销量之差。虚销地运量在实际方案中代表某产地没有运出去的货物量。题目10运输问题中用位势法计算检验数的原理是若所有非基变量的检验数____则当前调运方案为最优方案。答案都大于等于零≥0对于求最小费用问题。解析这是运输问题最优性检验的核心结论。理解成“当前方案没有改进空间”即可检验数小于0说明还有更省钱的调整方案。题目11指派问题的标准数学模型要求每项任务只能由一人完成每人只能承担____项任务目标为总效率____。答案一最大或最小看题目设定。解析指派问题的系数矩阵是方阵如果人数与任务数不等需要添加虚拟的人或任务对应效率设为0。2.4 图论、排队论与动态规划题目12在M/M/1排队模型中第一个M表示到达过程服从____第二个M表示服务时间服从____数字1表示____。答案泊松流到达间隔为负指数分布负指数分布只有一个服务台。解析这个题每年都有学校考。需要记住为什么叫“M”是马尔可夫性的意思说明过程无记忆性。题目13在动态规划中某阶段的状态变量应具有____性质即当前状态已能完全决定未来决策与该阶段之前的历史无关。答案无后效性马尔可夫性。解析这是动态规划建模最核心的假设条件也是判断一个问题能否用动态规划求解的重要依据。题目14网络图中关键线路是总时差为____的工作线路它决定整个工程的工期。答案零。解析关键线路上的工作一点都不能拖延否则总工期延误。计算题中求关键线路和总工期是重点。这十几道填空题基本覆盖了期末考试的高频概念。你如果能把每道题涉及的章节都展开复习一遍填空题的得分就有保障了。3. 线性规划建模与单纯形法从设变量到最优表一步步走计算题的大头在线性规划。它有两种考法一种是给你实际情景让你建模另一种是直接给数学模型让你用单纯形法迭代求最优解。这两类我都给出一道典型题目并把中间的迭代过程写清楚。3.1 生产计划建模题与标准形式转换题目某工厂计划生产甲、乙两种产品。生产1件甲产品需消耗A原料3kg、B原料2kg利润为50元生产1件乙产品需消耗A原料2kg、B原料4kg利润为60元。该工厂现有A原料120kg、B原料160kg。问应如何安排生产使总利润最大请建立线性规划模型。这个题非常简单但能完整体现建模的四个要素决策变量、目标函数、约束条件、非负约束。设生产甲产品x₁件、乙产品x₂件则模型为max z 50x₁ 60x₂s.t. 3x₁ 2x₂ ≤ 1202x₁ 4x₂ ≤ 160x₁, x₂ ≥ 0建模题的关键在于判断“约束条件”与“目标函数”哪个该放一边。很多同学容易把原料约束写反其实记住一句话受限制的写在约束条件里要优化的写在目标函数里。资源消耗不能超过资源总量这就是约束利润要尽可能大这就是目标。进一步把它转换成标准形式以备单纯形法使用。由于两个约束都是“≤”类型引入松弛变量x₃、x₄得到max z 50x₁ 60x₂s.t. 3x₁ 2x₂ x₃ 1202x₁ 4x₂ x₄ 160x₁, x₂, x₃, x₄ ≥ 0松弛变量x₃、x₄实际上表示被闲置的原料量它的系数是1目标函数系数为0不影响利润。3.2 单纯形法完整迭代以两变量模型为例很多人对单纯形法的印象是“表格特别多、符号容易搞混”其实只要抓牢三个要素就行基变量、进基出基规则、检验数。下面用一个更小巧的模型完整走一遍过程。题目求解线性规划问题max z 3x₁ 2x₂s.t. x₁ x₂ ≤ 4x₁ ≤ 2x₂ ≤ 3x₁, x₂ ≥ 0先引入松弛变量x₃、x₄、x₅标准形式为max z 3x₁ 2x₂s.t. x₁ x₂ x₃ 4x₁ x₄ 2x₂ x₅ 3各变量 ≥ 0初始基可行解令x₁和x₂为非基变量取0则x₃4x₄2x₅3初始目标值z0。初始单纯形表为基变量x₁x₂x₃x₄x₅右端项x₃111004x₄100102x₅010013检验数-3-20000检验数中最小的是-3对应x₁所以x₁进基。接着确定出基变量用右端项除以x₁列正系数4/142/12x₅这一行x₁系数为0不参与比值最小比值是2对应x₄出基。主元是x₄行的x₁系数1。进行一次高斯消去让x₁列变成单位向量保持x₁行不变将x₃行减去x₁行检验数行加上3倍x₁行。得到第二张表基变量x₁x₂x₃x₄x₅右端项x₃011-102x₁100102x₅010013检验数0-20306第二张表里检验数最小-2对应x₂进基。比值检验x₃行2/12x₅行3/13最小比值2所以x₃出基。主元是x₃行x₂列的1。再次消去x₂列变成单位向量x₃行不变x₁行减去x₃行x₁行x₂系数为0不用动x₅行减去x₃行检验数行加上2倍x₃行。结果基变量x₁x₂x₃x₄x₅右端项x₂011-102x₁100102x₅00-1111检验数0021010所有检验数都≥0迭代停止。最优解为x₁2、x₂2、x₅1松弛变量最优目标值z10。虚线上方的x₃0、x₄0说明两个资源约束都用满了而x₅1说明第三个资源x₂≤3还有1单位剩余。考场建议单纯形法的计算量不算大但一定要规范列表格、标出主元。我见过太多同学代数不列检验数靠心算是基变量的系数列还是非基变量的系数列最后一步错得离谱。宁可多写一行也不要跳步。3.3 对偶问题与灵敏度分析常考形式对偶问题是线性规划的一个独立考点常与灵敏度分析一起出现。它的核心是对称关系max问题对应对偶的min问题约束方向和变量符号也有对应规则。题目写出下面线性规划问题的对偶问题。max z 4x₁ 3x₂s.t. x₁ 2x₂ ≤ 103x₁ x₂ ≤ 15x₁, x₂ ≥ 0设对偶变量为y₁、y₂分别对应原问题的两个约束原问题目标为max、约束为“≤”则对偶问题的目标为min约束为“≥”目标系数和约束系数矩阵互为转置。对偶模型为min w 10y₁ 15y₂s.t. y₁ 3y₂ ≥ 42y₁ y₂ ≥ 3y₁, y₂ ≥ 0灵敏度分析的考点则是某资源增加一个单位最优目标值变化多少。答案就是该约束对应的影子价格也就是对偶最优解。比如上面问题中如果对偶最优解是y₁1、y₂1说明第一资源量从10增加到11时最优利润会增加1第二资源同理。这类题不需要重新求解单纯形表直接用互补松弛定理或读影子价格即可。4. 运输问题与整数规划方案寻找、最优性检验与指派问题运输问题是每年计算题的重头戏本质是一个特殊结构的线性规划。由于约束矩阵的特殊性考试不让你用单纯形法而是要求掌握表上作业法先求初始调运方案再用位势法检验最后用闭回路调整。4.1 最小元素法求初始方案位势法验最优题目某产品有三个产地A₁、A₂、A₃产量分别为120、180销往三个销地B₁、B₂、B₃销量分别为100、150、50。单位运价如下表求使总运费最小的调运方案。产地\销地B₁B₂B₃产量A₁865120A₂576180销量10015050300先检查产销平衡总产量120180300总销量10015050300产销平衡可以直接用表上作业法。最小元素法的思路是“哪个格子运价最低就先尽量往哪个格子运”。运价表中最低运价有两个A₁到B₃是5A₂到B₁也是5任意选一个先运。这里选A₁→B₃运量为min(120,50)50于是B₃需求完成A₁剩余70。此时把B₃列划去。剩余运价中最低为A₂→B₁的5运量为min(180,100)100B₁需求完成A₂剩余80。划去B₁列。剩余运价中A₁→B₂为6A₂→B₂为7选择A₁→B₂运量为min(70,150)70A₁用完B₂剩余80。最后A₂→B₂运80A₂用完。初始调运方案为A₁→B₂运70A₁→B₃运50A₂→B₁运100A₂→B₂运80。总运费 70×6 50×5 100×5 80×7 420 250 500 560 1730。接下来用位势法检验。基变量个数为4个应该等于mn-123-14恰好非退化设行位势为u₁、u₂列位势为v₁、v₂、v₃。对每个基变量有uᵢvⱼcᵢⱼ。令u₁0可解得A₁→B₂0v₂6得v₂6A₁→B₃0v₃5得v₃5A₂→B₂u₂67得u₂1A₂→B₁1v₁5得v₁4。然后计算非基变量的检验数σcᵢⱼ-(uᵢvⱼ)A₁→B₁8-(04)4A₂→B₃6-(15)0。由于所有检验数≥0当前方案即为最优方案最低运费1730。这里有个细节A₂→B₃的检验数为0说明存在另一个最优方案但目标值相同。考试阅卷时只要运费正确、方案合理一般都给满分。4.2 当检验数出现负数闭回路调整怎么做如果检验数出现负数说明当前方案不是最优。调整的方法是选检验数最小的非基变量进基从该格子出发找闭回路闭回路的偶数顶点上减去进基变量最小运量奇数顶点加上同样运量得到新方案。举例来说承接上题如果某一非基变量检验数为-2比如假设A₁→B₁检验数为-2注意上题实际是4那么从A₁→B₁出发沿水平或垂直方向找基变量顶点形成回路。假定回路顶点为A₁→B₁进基→A₁→B₂基→A₂→B₂基→A₂→B₁基→回到起点。奇数顶点运量分别为A₁→B₂的70、A₂→B₁的100取最小70于是进基变量A₁→B₁运量为70回路奇数顶点减去70偶数顶点加上70。这个调整过程虽然说起来简单但考场上看错行列坐标的人非常多我建议找回路时用笔把格子的行列号标出来每走一步都确认是不是基变量格子。4.3 指派问题匈牙利法的步骤与计算实例指派问题属于整数规划中的0-1规划特例。3个人完成3项任务的效率矩阵如下求使总效率最大的最优指派方案。题目某班组有3名工人甲、乙、丙需完成3项任务A、B、C。每个人完成不同任务的效率见下表求总效率最大的指派方案。工人\任务ABC甲483乙768丙574匈牙利法一般处理最小化问题最大化要先把矩阵转换为最小化。转换方式是取每行最大值或矩阵最大值减去该行元素把它变成“损失矩阵”。这里每行最大值分别为8、8、7转换后矩阵为甲4 0 5乙1 2 0丙2 0 3接着逐行找最小值并减去第一行减去0第二行减去0第三行减去0矩阵不变。然后逐列找最小值并减去第一列min(4,1,2)1减去后第一列为3,0,1第二列min(0,2,0)0第三列min(5,0,3)0。得到甲3 0 5乙0 2 0丙1 0 3用最少的直线覆盖所有0元素最少画线数为33行或3列时已覆盖等于矩阵阶数可以进行试指派。从只有唯一0的行开始乙行只有一个0在A所以乙→A丙行有两个0在B和C甲行只有一个0在B。先指派甲→B丙→C检查安排为甲→B、乙→A、丙→C对应原效率87419。还有另一种丙→B、甲行就没有0可选甲只有B被丙占用则甲无法指派所以不是最优。因此最优指派是甲→B、乙→A、丙→C最大总效率19。这个例子虽然简单但能完整展示“移减去零→试指派”的逻辑。真正的考试题往往是4×4或5×5试指派时可能遇到覆盖线数小于阶数的情况那时需要继续做“无零元素的调整”步骤本质上是在未覆盖元素中找最小值重复减加操作。碰到这类题时记住不要着急试指派先确认画线数与阶数相等否则一定漏了步骤。5. 图、动态规划与排队论三类常见计算题的代表性解法这些板块在不同学校考频差别很大但一旦考到题型通常非常固定。这里各给出一道具有代表性的题目。5.1 最短路问题Dijkstra标号法题目求下图中从v₁到v₆的最短路图中各边权值已标出v₁→v₂权2v₁→v₃权5v₂→v₃权1v₂→v₄权6v₃→v₄权4v₃→v₅权3v₄→v₅权1v₄→v₆权5v₅→v₆权2。Dijkstra标号法的做法是给每个顶点维护一个当前最短距离标号每次从未标号的顶点中选距离最小的那个更新它邻接顶点的距离。迭代过程如下初始d(v₁)0其余顶点标为∞。第一轮选v₁更新v₂为2v₃为5。第二轮未标号中最小是v₂距离2选择v₂更新v₃为min(5, 21)3更新v₄为268。第三轮未标号最小是v₃距离3更新v₄为min(8, 34)7更新v₅为336。第四轮未标号最小是v₅距离6更新v₄为min(7, 61)7更新v₆为628。第五轮最小是v₄距离7更新v₆为min(8, 75)8。最终v₆最短距离为8。对应的最短路有多条比如v₁→v₂→v₃→v₅→v₆距离21328。Dijkstra的适用条件是边权非负考试图题基本都满足。考场容易错在“更新顺序”上一定要先选当前最小标号点再用它去更新而不是按顶点序号顺序更新。5.2 动态规划资源分配/背包问题题目用动态规划求解下列背包问题背包容量为10有3件物品重量分别为3、4、5价值分别为4、5、6每件物品最多取1件求最大总价值。动态规划的核心是定义状态、状态转移方程和边界条件。设f(k, c)表示“考虑前k件物品、容量为c时的最大价值”。状态转移方程为f(k, c) max{ f(k-1, c), f(k-1, c-w_k) v_k }前提是c≥w_k填表过程第一件物品w3, v4容量0~2取0容量3~10取4。第二件物品w4, v5容量0~2取0容量3取4容量4~6可以取max(4, 05)5其中容量4、5取5容量6取5容量7~10可以取max(4, 45)97时取前一件加第二件459。第三件物品w5, v6容量0~2取0容量3取4容量4取5容量5~6取max(5,06)6容量7~8取max(9, 46)10容量9~10取max(9, 56)11。所以最优总价值为11对应选择第二件和第三件价值5611总重量459不超过容量10。这类题的得分点在于写出阶段、状态、决策、状态转移方程和最终表。就算填表数字算错方程写对也能拿到大半过程分所以千万别只写答案不写方程。5.3 排队论M/M/1模型的基本指标题目某售票窗口顾客到达服从泊松流平均每小时到达12人服务时间服从负指数分布平均每小时服务20人。求系统空闲的概率、平均队长、平均等待时间。M/M/1模型的关键参数是服务强度ρλ/μ。λ12人/小时μ20人/小时ρ12/200.6。系统空闲概率P₀1-ρ0.4。平均队长Lₛρ/(1-ρ)0.6/0.41.5人。平均等待时间W_q L_q/λ而平均等待队长L_q ρ²/(1-ρ)0.36/0.40.9人所以W_q0.9/120.075小时4.5分钟。如果需要平均逗留时间Wₛ 1/(μ-λ)1/(20-12)0.125小时7.5分钟。这个题的易错点是把队长和等待队长搞混。平均队长Lₛ包含正在接受服务的那个顾客而平均等待队长L_q只包含排队的人。考试时先写公式再代数字避免最后答案对不上公式时丢分。6. 考场实战策略计算题的表格规范与时间分配计算题能不能拿高分很大程度取决于考场上的书写规范。单纯形法、运输问题、指派问题、动态规划填表这几类都有标准步骤评卷时按步骤给分。我整理了几条实操建议都是自己在考试和辅导中总结出来的。第一每次迭代都完整列出单纯形表并在表中标出主元行、主元列和主元。这样即使最后最优解算错阅卷老师也能看到你迭代逻辑正确过程分不会少。不要跳步去合并表格那种写法风险很大一步手滑整表作废。第二运输问题的初始调运方案画表时注意标记哪行哪列已被划去基变量数量要等于mn-1。如果没有达到这个数量说明出现了退化需要把运量为0的格子当成基变量格子补足否则位势法会出现解不出位势的情况。很多同学就是在这里卡壳的。第三动态规划题中状态转移方程一定要放在显著位置。阅卷人往往先扫方程再看表格方程对了表格个别数值有误也能拿到大部分分。计算最短路时建议在每个顶点旁标一个“当前最短距离前驱”最后回溯路径时可以直接看清楚。第四关于时间分配。我建议根据分值倒推时间假设卷面满分100、考试时间120分钟大概1分对应1.2分钟。线性规划大题给20分就留20到25分钟不要因为它出现在第一题就恋战。填空、选择最多半小时内做完不会的先跳过计算题优先做最熟练的题型。先把能拿的分稳稳拿到再回头抠难题。第五考试时准备一张草稿纸专门做“计算复核”。比如单纯形表的行变换每次消元后用“原行加主元的倍数”重新算一遍检验数或者运输问题算完总费用再按原始运价表手算一遍这能筛掉至少一半的算术错误。运筹学的计算本身不难丢分基本都是粗心造成的。这类考试里还有一个常见的隐性陷阱题目给的是“利润最大化”但表格里却是“费用”或者给的是“最大运输量”却要求“最小运费”。读题时花十秒钟确认目标方向比做完一堆计算才发现方向反了要划算得多。做题时把“max”或“min”圈出来就等于给全卷加了一层保险。运筹学复习到最后拼的不只是谁公式背得熟而是谁能把流程完整、规范地写出来。把上面这些题从“看懂”变成“会算”再变成“算得又对又快”考试基本就稳了。如果你手里有哪道题反复做不对多半是中间某步流程有遗漏回头对照标准步骤比盲目刷十道新题更管用。