简介这份运筹学期末练习试卷面向高校运筹学课程学习者与备考学生用于系统检验建模与求解能力。试卷涵盖线性规划建模、整数规划建模、名词解释、网络分析与计算题等模块具体涉及A、B产品生产计划建模、汽车厂三种车型的整数规划、织布机生产安排、决策树分析及运输问题表上作业法等典型题型并附有详细解答过程便于对照理解建模思路与求解技巧。资源包共1个doc文件约1.09MB内容完整、排版清晰可直接打印练习或作为复习提纲使用。目前已有571人学习下载适合需要巩固运筹学核心知识点、熟悉期末题型与解题方法的学生参考也可为教师命题提供素材。1. 运筹学期末复习从一张知识地图说起运筹学期末复习最怕的不是题难而是知识点散。翻开教材线性规划、对偶理论、整数规划、运输问题、决策树、网络计划每一块都像独立的山头考场上却要求你在两小时内自由切换。这份练习试卷的价值恰恰在于它用五道大题把整学期的核心模块串成了一条线建模题考的是把文字描述翻译成数学语言的能力名词解释考的是概念边界作图填空考的是网络图的时间参数计算题则把单纯形法、决策树和表上作业法一次性拉通。复习时如果只盯着计算步骤很容易在建模假设和变量定义上翻车。下面按知识模块逐层拆解最后落到一份可以照着走的查漏补缺清单。2. 线性规划建模变量定义与约束翻译的四个关键动作2.1 从文字到变量先定决策变量再写目标函数线性规划建模的第一步不是列约束而是把“安排什么”翻译成决策变量。试卷第一题设每月生产 A、B 的数量为 x₁、x₂同时把销毁的产品 C 设为 x₃。这里最容易忽略的是副产品变量B 每生产 1 个单位会同时得到 2 个单位的 CC 最多能售出 10 个单位卖不出去的要销毁且每单位销毁费 1 元。如果只设 x₁、x₂ 而不设 x₃约束里就无法表达“C 的产销存平衡”目标函数里也扣不掉销毁费用。梳理下来这类题的变量定义要覆盖三类量生产量、销售量、处理量。生产量进约束销售量进目标函数处理量用来平衡供需差额。试卷里 C 的平衡关系可以写成# 产品C的产销平衡约束示意 # x1: A的产量, x2: B的产量, x3: 销毁的C数量 # B每单位产出2单位CC最多售出10单位 2 * x2 - x3 10 # 可售出的C不超过市场上限 x3 0 # 销毁量非负这段约束的含义是B 带来的 C 总量减去销毁量就是实际售出的 C它不能超过市场预测的 10 个单位。参数 2 来自“每单位 B 同时得到 2 个单位 C”10 来自“最多能售出 10 个单位 C”。如果题目改成“C 的销毁费用为每单位 1 元”目标函数里就要减去 x₃而不是把销毁量当成常数。2.2 目标函数利润要按“净贡献”写别漏掉联动收益第一题的目标函数容易写成 5x₁ 10x₂ 3×(2x₂) 就收手漏掉了销毁成本。正确的净利润是 A 的利润加 B 的利润加 C 的销售利润减 C 的销毁费用。C 的销售利润取决于实际售出量而实际售出量受上限约束所以目标函数里 C 的贡献要写成 3×min(2x₂, 10) 的分段形式或者引入 x₃ 后写成 3×(2x₂ - x₃) - 1×x₃。后者更线性也更适合放进标准型。第二题的整数规划建模则展示了另一种目标函数写法三种轿车的利润分别是 2、3、4 万元但每种车有经济规模下限只有产量达到下限才允许生产。这时需要引入 0-1 变量 yᵢ 表示“是否生产第 i 种车”约束写成 xᵢ ≤ M·yᵢ 且 xᵢ ≥ 下限·yᵢ。M 取一个足够大的数比如钢材总量对应的最大产量。这里的关键是经济规模不是“产量至少多少”这么简单而是“要么不生产要么至少生产这么多”必须用 0-1 变量把两种状态分开。2.3 资源约束把“可供利用”翻译成不等式方向第一题的前道过程 200 小时、后道过程 240 小时对应两条 ≤ 约束2x₁ 3x₂ ≤ 2003x₁ 4x₂ ≤ 240。方向写反是血泪经验里最常见的翻车点。判断方向的方法很简单资源是“可供利用”的上限消耗量不能超过它所以是 ≤如果题目说“至少需要满足的需求”才是 ≥。第三题的织布机问题更复杂因为它同时有自制和购买两种满足需求的方式。设 D 型机生产四种纺织品的小时数为 d₁ 到 d₄R 型机生产纺织品 3、4 的小时数为 r₃、r₄购买量为 p₁ 到 p₄。约束要分三层写机器时间上限D 型机 20 台×30 天×24 小时R 型机 8 台×30 天×24 小时、需求满足自产量加购买量等于需求量、以及“R 型机不生产纺织品 1、2”的隐含限制。第三层最容易被漏掉因为表格里 R 型机那两格写的是“不生产”不是数字。2.4 建模题的检查清单四个“有没有”做完一道建模题用四个问题自查有没有定义所有出现在约束里的变量有没有漏掉副产品或联产品的平衡关系不等式方向有没有和“上限/下限”对应整数规划里有没有用 0-1 变量处理“要么不生产、要么达到规模”的逻辑这四问能拦住大部分建模失分。3. 对偶理论与互补松弛性从原问题反推对偶最优解3.1 对偶问题的构造规则对称型与非对称型试卷综合题给了一个线性规划要求写出对偶问题并求对偶最优解。对偶构造的规则取决于原问题的形式如果原问题是“max约束全为 ≤变量全非负”对偶就是“min约束全为 ≥变量全非负”如果原问题有等式约束或自由变量对偶的约束方向和变量符号要相应调整。记忆口诀是“max 变 min≤ 变 ≥约束系数转置右端项与目标系数互换”。以试卷中的原问题为例假设原问题是 max z cᵀx约束为 Ax ≤ bx ≥ 0则对偶问题是 min w bᵀy约束为 Aᵀy ≥ cy ≥ 0。写对偶时最容易错的是变量个数原问题有几个约束对偶就有几个变量原问题有几个变量对偶就有几个约束。把这条对应关系先画出来再填系数比直接背公式稳。3.2 互补松弛性用原问题最优解推对偶最优解试卷答案里写“利用互补松弛性将原问题最优解带入”这是对偶理论里最实用的技巧。互补松弛性说的是如果原问题某个约束是严格不等式松弛变量大于零对应的对偶变量必为零如果对偶问题某个约束是严格不等式对应的原问题变量必为零。反过来如果已知原问题最优解中某个变量大于零那么对偶问题中对应的约束必须取等号。具体操作分三步先把原问题最优解代入各约束找出哪些约束取等号、哪些有松弛再根据“松弛对应对偶变量为零”列出对偶变量的取值条件最后解剩下的等式方程组。试卷里 y₃ 0 就是这么来的——原问题第三个约束在最优解处有松弛所以对偶第三个变量为零。这一步如果漏掉对偶最优解会多一个自由度解不唯一。提示互补松弛性只给出“哪些变量为零”的信息剩下的非零变量还要靠对偶约束取等号来解。两步都做完才能写出完整的对偶最优解。3.3 对偶理论的常见考法三个层次期末考对对偶理论的考查通常分三层第一层是写出对偶问题考构造规则第二层是已知原问题最优解求对偶最优解考互补松弛性第三层是解释对偶变量的经济含义比如影子价格。试卷覆盖了前两层第三层常以名词解释或简答出现。复习时把这三层按顺序过一遍比零散背公式有效。4. 运输问题与表上作业法初始解、检验数与闭回路4.1 表上作业法的三步流程试卷计算题第三题给了 3×4 的运输表产量为 16、10、22销量为 8、14、12、14总产量 48 等于总销量 48是产销平衡问题。表上作业法的流程固定为三步求初始基可行解最小元素法或伏格尔法、求检验数判断最优性位势法、用闭回路调整改进解。初始解用最小元素法时从运价最小的格子开始分配能填多少填多少填完划掉对应行或列。这道题运价最小的是 A₂B₁ 的 1先填 min(10, 8) 8A₂ 还剩 2B₁ 满足接着找次小运价依此类推。最小元素法快但初始解质量一般伏格尔法考虑“次小运价与最小运价之差”初始解更接近最优但计算量大。考试时如果题目没指定方法最小元素法够用但要注意基变量个数必须是 m n - 1 3 4 - 1 6 个不够时要补零。4.2 位势法求检验数u 和 v 的方程组位势法的核心是给每个行一个位势 uᵢ、每个列一个位势 vⱼ对基变量格子满足 uᵢ vⱼ cᵢⱼ。基变量有 6 个未知数有 7 个3 个 u 加 4 个 v所以令某个 u 或 v 为零解出其余。然后对非基变量格子算检验数 σᵢⱼ cᵢⱼ - (uᵢ vⱼ)如果所有 σᵢⱼ ≥ 0当前解最优有负检验数就选最小的那个格子进基画闭回路调整。闭回路的画法是从进基格子出发沿行或列走遇到基变量格子就转弯回到起点形成闭合折线顶点除起点外都是基变量。调整量取闭回路上偶数顶点减去方向的最小值然后加减调整。这一步的易错点是闭回路方向搞反导致调整后出现负值。画完回路先标“ - -”再算调整量能减少出错。4.3 产销不平衡的处理虚拟产地或虚拟销地如果总产量大于总销量加一个虚拟销地销量等于差额运价全为零如果总销量大于总产量加一个虚拟产地。试卷这道题产销平衡不需要虚拟但复习时要记住这个处理方式因为考试经常在这里设坑。虚拟格子的运价为零意味着“未被满足的需求”或“未运出的库存”不产生运费但检验数计算时虚拟格子同样参与。5. 网络计划与决策树时间参数与期望值倒推5.1 网络图的时间参数最早开始、最迟开始与总时差试卷作图填空题给了五个活动 A 到 F 及其紧前关系要求画网络图、找关键路线、算完工时间、算活动 B 和 E 的可推迟天数。这类题的核心是四个时间参数最早开始时间 ES、最早完成时间 EF、最迟开始时间 LS、最迟完成时间 LF。正推法算 ES 和 EF从起点开始取所有紧前活动 EF 的最大值逆推法算 LS 和 LF从终点开始取所有紧后活动 LS 的最小值。总时差 TF LS - ES LF - EF总时差为零的活动在关键路线上。试卷里关键路线是 A-E-F完工时间 14 天。活动 B 的紧前活动是“无”紧后活动是 CC 的紧前是 BD 的紧前是 A 和 CE 的紧前是 AF 的紧前是 D 和 E。正推一遍A 的 ES0EF5B 的 ES0EF1C 的 ES1EF3D 的 ESmax(5,3)5EF9E 的 ES5EF11F 的 ESmax(9,11)11EF14。逆推F 的 LF14LS11E 的 LF11LS5D 的 LF11LS7C 的 LFmin(7)7LS5B 的 LF5LS4A 的 LFmin(5,5)5LS0。B 的总时差 4 - 0 4 天E 的总时差 5 - 5 0 天和试卷答案一致。5.2 决策树先画树再倒推期望值试卷计算题第二题是决策树销路好概率 0.7、获利 1200 万销路差概率 0.3、亏损 150 万可以先建小型试验工厂试销试销费 5 万试销销路好概率 0.8试销好之后大批量投产销路好的概率 0.85试销差之后大批量投产销路好的概率 0.1。决策树的画法是从左到右画决策点方框和状态点圆圈从右到左算期望值。不试销的期望值0.7×1200 0.3×(-150) 840 - 45 795 万。试销的期望值要分两支算试销好的分支后续投产期望值 0.85×1200 0.15×(-150) 1020 - 22.5 997.5 万试销差的分支后续投产期望值 0.1×1200 0.9×(-150) 120 - 135 -15 万。试销的总期望值 0.8×997.5 0.2×(-15) - 5 798 - 3 - 5 790 万。790 795所以不试销更优。这里最容易错的是忘了减试销费 5 万或者把试销概率和投产概率混在一起用。5.3 网络计划与决策树的共同点倒推两类题看起来无关但解题逻辑都是“先正推、再倒推”。网络计划正推算最早时间、逆推算最迟时间决策树正推画分支、逆推算期望值。复习时把这两个“倒推”放在一起记能减少混淆。6. 易漏点与易错点五条考场翻车高发区易漏点一建模题漏写变量非负约束。为什么漏注意力全在资源约束和目标函数上觉得“产量当然非负”。怎么补每写完一组约束回头检查所有变量是否都声明了 ≥ 0整数规划还要加整数约束或 0-1 约束。易漏点二对偶问题变量个数与原问题约束个数对不上。为什么漏直接套公式没先数原问题有几个约束。怎么补写对偶前先在草稿上标出原问题的约束数和变量数对偶的变量数等于原约束数对偶的约束数等于原变量数数一遍再动笔。易漏点三表上作业法基变量个数不足 mn-1。为什么漏最小元素法分配时同时划掉行和列导致基变量少一个。怎么补每次只划掉一行或一列如果同时满足只划一个另一个留到后面补零最后检查基变量个数不够就在空格补零。易漏点四网络图总时差算成“最迟开始减最早开始”却用错活动。为什么漏正推逆推的数字抄串行。怎么补把每个活动的 ES、EF、LS、LF 列成表格一行一个活动算完总时差再标关键路线不要跳步。易漏点五决策树期望值忘记减试销成本或调查费用。为什么漏只算投产收益把前期费用当成“已经花掉不用管”。怎么补在决策树的每个分支末端把该分支的所有费用列出来期望值算完后统一扣减或者直接在分支上标净收益。7. 复习清单从知识地图到考场动作的查漏补缺复习到最后阶段不要再从头翻教材按下面这张清单逐项打勾哪一项卡住就回到对应章节补。模块必会动作自查问题对应试卷题线性规划建模设变量、写目标、列约束、补非负副产品平衡写了吗不等式方向对吗建模题 1、3整数规划建模0-1 变量处理规模下限“要么不产、要么达产”用 y 表达了吗建模题 2对偶理论写对偶、互补松弛求最优解对偶变量个数数对了吗松弛对应零用上了吗综合题运输问题最小元素法、位势法、闭回路基变量够 mn-1 吗检验数全非负吗计算题 3网络计划正推 ES/EF、逆推 LS/LF、算总时差关键路线总时差为零吗作图填空决策树画树、算分支期望、倒推决策试销费减了吗概率乘对了吗计算题 2具体操作上建议按“先建模、再计算、后概念”的顺序过一遍第一天把三道建模题重新写一遍变量定义和约束不看答案第二天做运输问题和网络图重点练位势法和总时差表格第三天做对偶和决策树对偶题强制用互补松弛性推一遍第四天只看易漏点清单把五条翻车点各找一道题验证。每道题做完问自己一句如果题目改一个参数我的模型哪里会变能答上来才算真掌握。注意试卷里“只建模、无需求解”的题不要跳过求解练习。建模是翻译能力求解是计算能力期末考通常两者都考分开练才能都稳。从那以后我每次复习运筹学都强制走一遍“变量定义→约束方向→基变量个数→期望值扣费”这四个检查动作哪怕时间再紧也不省。这套动作拦住过好几次本可以避免的失分。希望这份梳理帮到你把散落的知识点串成一张能带进考场的图。本文还有配套的精品资源点击获取
算法详解)
