运筹学期末题型拆解：线性规划建模、对偶与网络图答题模板

简介这份运筹学期末练习试卷面向高校运筹学课程复习与备考人群围绕线性规划、整数规划、网络分析与运输问题等核心考点组织题目适合用于期末自测、建模训练和解题思路梳理。包内共1个doc文件约1.09MB内容以试卷正文与解答为主包含建模题、名词解释、作图填空和计算题等模块。试卷中的建模题涉及两种产品生产计划、汽车厂产量规划与织布机资源分配计算题覆盖运输问题表上作业、决策树和线性规划对偶及互补松弛性可帮助读者从题干与参考答案中体会约束设置、目标函数构建和最优解验证。已有571人学习适合需要系统刷题、查漏补缺或教师组卷参考的读者也能帮助理解运筹学定量分析的基本流程和常用求解技巧。1. 运筹学期末这张卷子建模 30 分丢分往往不在算错整张练习卷的结构很固定建模题 30 分、名词解释 10 分、作图填空 15 分、计算题 30 分、综合题 15 分。很多人复习时把时间全押在单纯形表上翻开卷子第一题却愣住了——A、B 两种产品附带副产品 C卖不掉还要倒贴销毁费目标函数里 B 的系数到底写 10 还是 16这道题不要求求解却最能筛人考的是把「产量、销量、销毁量」拆开写清楚的能力。拿分逻辑也在这里建模题看变量和约束是否闭合网络图看时间参数是否算全计算题看最优解和检验数是否对得上。适合已经学过一遍、看得懂模型但一上考场就漏约束、漏符号的人。下面按题型顺序拆每类题给到能直接背的写法。2. 建模题三道生产计划变量设错后面全白写建模题共 3 小题、每题 10 分阅卷时先看变量定义再看约束是否齐全最后看目标函数系数。变量设错后面写得再漂亮也拿不到分。这一章把三道题拆成「变量表—约束链—目标函数」三步每步都给可套用的写法。2.1 副产品与销毁费用A/B/C 那道题的目标函数怎么写先列变量表这是整道题的地基变量含义关系x1产品 A 的产量独立决策x2产品 B 的产量每单位带出 2 单位 Cx3产品 C 的销毁量销量 2x2 − x3C 的产量是 2x2能卖出去的最多 10 单位卖不掉的必须销毁。目标函数这样推A 贡献 5x1B 贡献 10x2C 卖出去的部分贡献 3(2x2 − x3)销毁部分倒扣 1·x3。合并同类项max z 5x1 10x2 3(2x2 − x3) − x3 5x1 16x2 − 4x3这里有两个容易翻车的系数。B 的系数不是 10而是 16因为每生产 1 单位 B 强制带出 2 单位 C这 2 单位都能卖掉时边际贡献是 10 2×3 16。C 的销毁系数是 −4 而不是 −1因为销毁 1 单位 C既少赚 3 元又付 1 元销毁费机会成本加实际支出共 4 元。阅卷时这两个数字对不上基本判定没有理解副产品联动。约束按「资源—市场—非负」三层写2x1 3x2 ≤ 200 前道工序工时 3x1 4x2 ≤ 240 后道工序工时 2x2 − x3 ≤ 10 C 的销量不超过市场上限 x1, x2, x3 ≥ 0第二层市场约束也可以写成x3 ≥ 2x2 − 10含义是「产量超过 10 的部分必须销毁」两种写法等价。但目标函数里保留 x3 更直观因为销毁费直接挂在 x3 上。提示如果题目改一个字说「C 必须全部售出或销毁」就要把2x2 销售量 x3写成等式再单独设销售量变量 x4模型变成max 5x1 10x2 3x4 − x3约束加x4 x3 2x2、x4 ≤ 10。这样变量定义更干净也不会在目标函数里出现隐式展开。答题模板固定为五步设变量并写清单位—写产量联动关系—写资源约束—写市场约束—写目标函数。每一步单独成行阅卷老师找点快自己也容易查漏。2.2 经济规模与固定费用整数规划里的 0-1 变量怎么用汽车厂这道题的难点不在资源约束而在「产量必须达到经济规模才可生产」。微型车 1500 辆、中级车 1200 辆、高级车 1000 辆低于这个数就不能开工等于 0。这不是普通的 x ≥ 1500必须引入 0-1 变量把「要么不生产要么至少生产这么多」表达出来。先算每个车型的资源上限用来确定大 M车型钢材上限人工上限取小者 M微型6000/1.5 400055000/30 ≈ 18331833中级6000/2 300055000/40 13751375高级6000/2.5 240055000/50 11001100模型写成max z 2x1 3x2 4x3 1.5x1 2x2 2.5x3 ≤ 6000 30x1 40x2 50x3 ≤ 55000 1500y1 ≤ x1 ≤ 1833y1 1200y2 ≤ x2 ≤ 1375y2 1000y3 ≤ x3 ≤ 1100y3 x1, x2, x3 ≥ 0 且为整数 y1, y2, y3 ∈ {0, 1}下界乘 y 保证「开工就至少 1500」上界乘 y 保证「不开工就是 0」。只写下界不行x1 可以无限大只写上界也不行x1 可以取 1 到 1499 之间的数等于绕过了经济规模。两个一起写约束才闭合。大 M 的取法也有讲究。有人图省事写 99999模型能跑但松弛得厉害阅卷时也显得没算过资源上限。取该变量在资源约束下的最大可行值既紧又体现你读懂了数据。这道题只建模不求解但 M 写对10 分里至少保住 3 分。注意如果题目说「超过经济规模的部分才有补贴」那就不是 0-1 变量能解决的属于分段线性本题不涉及。看到「达到一定数量才可生产」「要么不开工要么至少多少」才用 0-1 变量。2.3 自制或购买多设备多产品的工时约束与利润系数织布机这道题信息量最大先算总工时每月 30 天、每天 24 小时单台 720 小时。D 型机 20 台总工时 14400 小时R 型机 8 台总工时 5760 小时。变量设三组D 型机生产各纺织品的小时数 x_D1 到 x_D4R 型机生产纺织品 3、4 的小时数 x_R3、x_R4购买量 p1 到 p4。注意 R 型机不能生产 1、2对应变量直接不设不要设了再补一句等于 0。产量和需求的关系是等式因为题目要求「满足所有需求」4.63x_D1 p1 165000 4.63x_D2 p2 220000 5.23(x_D3 x_R3) p3 62000 5.23(x_D4 x_R4) p4 7500 x_D1 x_D2 x_D3 x_D4 ≤ 14400 x_R3 x_R4 ≤ 5760目标函数用题目已经算好的单位利润乘数量不要重复减成本max z 0.33×4.63x_D1 0.31×4.63x_D2 0.61×5.23(x_D3 x_R3) 0.73×5.23(x_D4 x_R4) 0.19p1 0.16p2 0.50p3 0.54p4题面给的 0.33、0.31、0.61、0.73 是自产单位利润0.19、0.16、0.50、0.54 是外购单位利润都是「售价减成本」之后的结果。每小时产量是「件/小时」乘小时数才是件数这一步是整道题最常翻车的地方。有人直接把小时数当产量写进需求约束量纲对不上后面全错。还有一个隐藏考点D 型机生产纺织品 3 和 R 型机生产纺织品 3 的每小时产量都是 5.23所以目标函数里可以把两者合并成0.61×5.23(x_D3 x_R3)。合并之后变量关系更清楚也不容易漏掉 R 型机的贡献。3. 计算题从最优解到对偶价格四类题型一条线打通计算题 30 分通常是一道线性规划求解、一道决策树、一道运输问题综合题再考对偶。这四类题共用一套底层逻辑先写标准形式再找可行域最后用检验数或期望值定优劣。这一章按「求解—对偶—决策—名词」的顺序拆。3.1 线性规划求解图解法定位单纯形表验证A、B 两种产品煤 6/4 吨、电 4/5 度、劳动力 3/10 个利润 7/12 万元。模型max z 7x1 12x2 6x1 4x2 ≤ 360 4x1 5x2 ≤ 200 3x1 10x2 ≤ 300 x1, x2 ≥ 0三个约束两两求交点。煤与电的交点解出 x1 ≈ 71.4代入电约束已经超了不可行煤与劳动力的交点 (50, 15) 代入电约束 275 200也不可行电与劳动力的交点4x1 5x2 200 3x1 10x2 300第一式乘 2 得 8x1 10x2 400减去第二式得 5x1 100x1 20回代得 x2 24。检查煤约束6×20 4×24 216 ≤ 360可行。目标值 z 7×20 12×24 428 万元。再检查两个轴上的截点x1 轴由电约束卡在 50z 350x2 轴由劳动力约束卡在 30z 360。都低于 428所以最优解就是 (20, 24)。用代码复核一遍顺便看松弛量import numpy as np from scipy.optimize import linprog # linprog 默认求最小值所以目标系数取负 c [-7, -12] A [[6, 4], [4, 5], [3, 10]] b [360, 200, 300] bounds [(0, None), (0, None)] res linprog(c, A_ubA, b_ubb, boundsbounds, methodhighs) print(最优解:, res.x) # [20. 24.] print(最优值:, -res.fun) # 428.0 print(松弛量:, np.array(b) - np.array(A) res.x) # [144. 0. 0.]参数说明c取负是因为linprog只做最小化A_ub和b_ub对应三个 ≤ 约束bounds写非负。输出的松弛量 144、0、0 说明煤没用完电和劳动力刚好用尽。紧约束对应的对偶价格才可能为正松约束的对偶价格一定是 0这条结论下一节直接用到。提示考场上如果没有计算器交点方程用手算就行但一定要回代检查第三个约束。很多人算出交点直接写答案忘了验证可行性结果把不可行的交点当成最优解。3.2 对偶转换与互补松弛从原问题最优解反推 y原问题 max、约束全为 ≤、变量非负对偶就是 min、约束全为 ≥、变量非负系数矩阵转置min w 360y1 200y2 300y3 6y1 4y2 3y3 ≥ 7 4y1 5y2 10y3 ≥ 12 y1, y2, y3 ≥ 0互补松弛性两条规则原问题某个约束是松的对应的对偶变量为 0原问题某个变量为正对应的对偶约束取等号。把上一节的最优解代进去煤约束松弛量 144 0所以 y1 0x1 20 0、x2 24 0所以对偶的两个约束都取等号。方程组变成4y2 3y3 7 5y2 10y3 12第一式乘 10 得 40y2 30y3 70第二式乘 3 得 15y2 30y3 36相减得 25y2 34y2 1.36回代得 y3 0.52。对偶目标值 w 200×1.36 300×0.52 272 156 428和原问题一致验证通过。这套流程就是综合题的標準答法写对偶—找松约束—令对偶变量为 0—非零原变量对应的对偶约束取等—解方程—回代验证。比重新解一遍对偶问题快得多也不容易算错。符号规则单独记原问题约束是等式对偶变量无符号限制原问题变量无符号限制对偶约束取等号原问题求 max、约束 ≤对偶求 min、约束 ≥。这三条在名词解释和综合题里都会考写错一个方向后面全反。3.3 决策树试销的 5 万元到底值不值先算不试销的期望0.7×1200 0.3×(−150) 840 − 45 795 万元。再算试销。试销好的概率 0.8试销差的概率 0.2。试销好之后大批量投产销路好的概率 0.85期望是 0.85×1200 0.15×(−150) 1020 − 22.5 997.5 万元。试销差之后投产销路好的概率只有 0.1期望是 0.1×1200 0.9×(−150) 120 − 135 −15 万元。关键一步试销差的时候可以选择不投产期望记 0而不是硬着头皮投产拿 −15。所以试销的期望收益是 0.8×997.5 0.2×0 798 万元扣掉 5 万元试验费净期望 793 万元。793 795结论是不建试验工厂直接大批量投产。这个结果和直觉相反很多人默认「多了解信息总没坏处」。决策树算的是期望货币值信息有成本。试销带来的信息价值是 798 − 795 3 万元低于 5 万元试验费所以不值。临界点是试验费 3 万元低于这个数才该试销。最容易错的地方是把试销差之后的 −15 直接加权进去0.8×997.5 0.2×(−15) 795正好等于不试销于是得出「试销与否无差别」的错误结论。实际上试销差时及时止损期望是 0这 3 万元的信息价值全部来自「差的时候不投产」这个选择权。3.4 名词解释两句话拿满 10 分的写法定性分析按四段写定义是决策者依据经验、直觉和判断做选择特点是主观、快速、难以复核适用场景是信息不足、时效要求高、变量难以量化局限是不同人结论可能相反。定量分析同样四段定义是依据数据和数学模型计算得出决策特点是客观、可验证、依赖数据质量适用场景是结构化问题、变量可量化、有历史数据局限是模型假设不成立时结论会偏。最后补一句关系定性定方向定量定精度实际决策常先用定性筛方案再用定量比优劣。10 分题写四段每段一两行比只写一句定义稳得多。线性规划的对偶问题也按三段定义是同一组数据从另一个角度描述原问题经济含义是对偶变量是影子价格衡量资源每增加一个单位带来的目标增量转换规则是 max 变 min、约束系数转置、不等号方向翻转。能写出影子价格这层含义这道题就从「背定义」变成「懂经济含义」。4. 网络图与运输表关键路线 14 天和 244 元成本怎么算出来作图填空 15 分、运输问题 10 分这两类题共同点是「步骤固定、一步错步步错」。网络图错一个时间参数后面四个空全错运输表初始解错一个数检验数全废。这一章把两类题的算路完整走一遍。4.1 画网络图先排紧前关系再补虚活动题目给的活动表活动时间紧前活动A5无B1无C2BD4A、CE6AF3D、E画图顺序A、B 无紧前从起点节点引出C 接在 B 后D 要同时等 A 和 C所以 A 的结束节点和 C 的结束节点都指向 D 的开始节点E 只等 A从 A 的结束节点另引一条F 等 D 和 E两条线收在同一个节点再连终点。虚活动只在紧前关系没法用节点直接表达时才加。本题 A 的结束节点分出两条线一条给 D、一条给 E节点本身已经区分了先后不需要虚活动。如果两道活动有完全相同的开始和结束节点才需要加一条虚箭线把其中一道隔开。画完图给节点编号每条弧标上活动名和持续时间后面算时间参数直接对着图看不用反复翻题干。4.2 时间参数表14 天工期是怎么算出来的正向计算最早时间取最大值反向计算最迟时间取最小值。活动时间ESEFLSLF总时差 TF自由时差 FFA5050500B1014540C2135742D45971122E651151100F31114111400正向算A 的 EF 5B 的 EF 1C 的 ES 1、EF 3D 的 ES 取 A 的 5本文还有配套的精品资源点击获取