运筹学建模入门：线性规划、整数规划与对偶问题解析

简介：「运筹学期末练习试卷(1).doc」面向运筹学课程学习者与期末备考学生，以一份完整练习卷串联线性规划、整数规划、网络分析与决策分析等核心考点。试卷含建模题、名词解释、作图填空与计算题四类题型：建模部分给出A、B产品两道工序排产、汽车厂钢材与人工约束下的整数规划、织布机自制或购买等原始题干与设元过程；名词解释涉及定性与定量分析、线性规划对偶问题；作图填空要求绘制活动网络图并计算关键路线与完工时间；计算题包含资源分配最优解、决策树试销决策及表上作业法求解运输问题，并附对偶规划与互补松弛性求解示例。包内共1个doc文档，约1.09MB，可直接打印或对照练习。已有571人学习下载，适合用于梳理建模思路、核对答案与考前查漏补缺。

1. 运筹学是什么：先把它当成“给选择题算账的学问”

周末去吃自助餐，盘子大小有限，胃的容量也有限，你想让这一顿吃得最满足——先夹什么、每样夹多少、要不要留肚子给甜品，你脑子里其实飞快跑过了一遍取舍。运筹学干的就是这件事：把“做多少、怎么排、先做哪个”这类现实取舍，翻译成一组带约束的数学式子，再找出最划算的那个方案。它不研究菜好不好吃，只研究在资源有限的前提下，怎么让目标值做到最好。搞懂它，你就拥有了一套看穿“资源怎么分才不亏”的通用视角，小到排班、大到生产计划，背后都是同一套逻辑。

2. 为什么要把现实问题翻译成模型：三道建模题的共同骨架

很多人第一次接触运筹学，卡住的地方是：题目明明读懂了，却不知道第一行该写什么。真正的问题在于，现实语言和数学语言之间缺一道翻译工序。这一章就沿着这份练习卷里的三道建模题，把这道工序拆开给你看——它们长得完全不一样，一个是化工产品，一个是汽车厂，一个是织布机，但建模的动作几乎一模一样。

2.1 建模先做三件事：定变量、写目标、列约束

第一道题讲的是 A、B 两种产品都要过两道化学反应过程。A 每单位占前道 2 小时、后道 3 小时，B 每单位占前道 3 小时、后道 4 小时；前道一共只有 200 小时，后道 240 小时。A 每单位赚 5 元，B 每单位赚 10 元，而每生产 1 个 B 会顺带产出 2 个副产品 C，C 每单位卖 3 元，卖不掉就得花钱销毁，销毁一个亏 1 元，市场最多消化 10 个 C。

建模的第一步不是列式子，而是问自己一句：我到底要决定什么？答案是要决定 A 产多少、B 产多少，所以设 A 为 x1、B 为 x2。第二步才是目标——总利润最大。第三步是约束，也就是“时间不够用”和“副产品不是你想产多少就产多少”。

翻译过来就是三行：

• 前道工时：2x1 + 3x2 ≤ 200
• 后道工时：3x1 + 4x2 ≤ 240
• 副产品的去向：2x2 = 卖掉的 C + 销毁的 C，且卖掉的 C ≤ 10

目标函数则写成 5x1 + 10x2 + 3×（卖掉的 C）− 1×（销毁的 C）。到这里，一道看起来很生活化的题就变成了一组不等式。

通俗地说，建模就是逼你把“差不多”“看情况”这类模糊词全部换成带名字的变量。凡是没被设成变量的东西，后面一定会漏。

2.2 副产品那道题，90% 的错都错在“把产量当销量”

第一道题最容易出错的地方，是把“最多能售出 10 个单位 C”直接写成 2x2 ≤ 10。这么写等于假设“产多少就能卖多少，只是产量不能超过 10”。但副产品的特点是：你生产 B 的时候，C 是被动跟着出来的。“产多少”和“卖多少”根本就是两件不同的事。

正确的处理是给 C 拆成两个变量：一个表示卖出去的，受市场 10 个单位封顶；一个表示没卖出去要销毁的。两者相加，必须正好等于 2x2。这样模型才允许“生产了很多 B，副产品 C 卖不掉，只能倒贴钱销毁”这种情况发生。

提示：凡是题目里出现“副产品”“边角料”“残次品”“退货”这类词，几乎都要多设一个变量去接住它，别让它凭空消失。

这个细节也说明了一件事：模型不是越简洁越好，而是越贴近真实的因果链越好。你少设一个变量，模型就会给你一个看似最优、实则没法执行的方案，这种计算结果很漂亮，但执行不了。

2.3 “要么不生产，要么至少生产一批”：0-1 变量与经济规模

第二道题换了个场景。某汽车厂生产微型、中级、高级三种轿车，每辆消耗的钢材是 1.5 / 2 / 2.5 吨，占用人工 30 / 40 / 50 小时，利润是 2 / 3 / 4 万元。每月钢材 6000 吨、人工 55000 小时。关键的一句是：每种车必须达到经济规模才能开工，微型 1500 辆、中级 1200 辆、高级 1000 辆。

这句话翻译成数学，就是“少于这个数，只能是 0；一旦开工，至少是这个数”。这种“要么全不、要么起码一批”的关系，靠普通的不等式写不出来，得引入 0-1 变量——它只取 0 或 1 两个值，相当于一个开关。

设三种车的产量为 x1、x2、x3，开关为 y1、y2、y3（0 表示不开工，1 表示开工），约束就写成：

• x1 ≥ 1500y1，x2 ≥ 1200y2，x3 ≥ 1000y3
• x1 ≤ M1y1，x2 ≤ M2y2，x3 ≤ M3y3

前一组是“开工就至少这么多”，后一组是“不开工就一定是 0”。这里的 M 不是随便写个很大的数，而是这条产线在资源和时间上能产出的上限，需要一辆一辆算出来——微型车受人工约束，55000÷30≈1833 辆；中级车 55000÷40=1375 辆；高级车 55000÷50=1100 辆。

这个 M 取大了会出问题：模型里会出现“开关关着但产量却很大”的空子被绕过的空间，求解器给你一个数学上成立、业务上荒唐的答案。所以 M 一定要取“这条产线物理上可能的极限”，这叫大 M 法的取值纪律，参数不是凑数的。

3. 线性规划与整数规划：只差“整数”两个字，差的是解法

如果只看定义，整数规划就是“线性规划加上变量必须是整数”，一句话就讲完了。但这两个字带来的麻烦，远比想象中大。这一章把两者的边界、以及线性规划背后那个经常被忽略的“对偶”讲清楚。

3.1 线性规划的四个零件

线性规划的结构非常固定，固定到你可以把它当成一个模板来背：决策变量、目标函数、约束条件、非负限制。

拿练习卷里的资源分配题来说，某工厂生产 A、B 两种产品，A 每公斤耗煤 6 吨、电 4 度、劳动力 3 个，B 每公斤耗煤 4 吨、电 5 度、劳动力 10 个；每公斤利润分别是 7 万元和 12 万元；现有煤 360 吨、电 200 度、劳动力 300 个。写成模型就是：

• 目标：最大化 7x1 + 12x2
• 煤：6x1 + 4x2 ≤ 360
• 电：4x1 + 5x2 ≤ 200
• 劳动力：3x1 + 10x2 ≤ 300
• x1 ≥ 0，x2 ≥ 0

“线性”这两个字指的是所有关系都是一次方——没有平方、没有乘积、没有开根号。这个限制听起来很强，但现实里大量问题在局部范围内确实近似线性，所以它够用。“规划”在这里不是“计划”的意思，而是“求最优”的意思。

用代码写出来，模型的结构一目了然：

import pulp # 决策变量：A、B 的产量，下界为 0 即非负限制 x1 = pulp.LpVariable("A", lowBound=0) x2 = pulp.LpVariable("B", lowBound=0) prob = pulp.LpProblem("resource_alloc", pulp.LpMaximize) # 目标函数：每公斤利润之和 prob += 7 * x1 + 12 * x2 # 三类资源各自的约束 prob += 6 * x1 + 4 * x2 <= 360 # 煤 prob += 4 * x1 + 5 * x2 <= 200 # 电 prob += 3 * x1 + 10 * x2 <= 300 # 劳动力 prob.solve()

这段代码里，每一行都对应模型的一个零件：LpVariable是变量声明，lowBound=0就是非负限制；prob +=出现两次，第一次加的是目标函数，后面加的是约束。新手最容易犯的错是把目标函数写在约束后面，顺序其实无所谓，但自己读起来会乱。参数的含义也很直白：系数就是每单位消耗，右边的常数就是资源总量。

线性规划之所以被广泛使用，是因为它有一个很好的几何性质：所有约束围出来的可行域是一个多边形（高维叫多面体），而目标函数是平的，最优解一定出现在某个顶点上。于是求解不需要“试遍所有点”，只要沿着顶点走就行，规模再大也算得动。

3.2 整数规划：可行域从一整块变成了一堆散点

现在把“产量必须是整数”加进去，情况立刻变了。原本那个多边形内部的每一个点都是合法方案，现在只留下格子点。最优的那个格子点，往往不在多边形的顶点上。

打个比方：线性规划像是在一整块草地上找最高点，你可以站在任何位置；整数规划则要求你只能站在草地上的树桩上，而最高的树桩可能离最高点有一段距离。这段距离叫“整数间隙”，它是整数规划难算的根源。

更麻烦的是“0-1 变量”这类开关型决策。汽车厂那道题里，三个开关每个只有开和关两种状态，看起来简单，但组合起来就是 2³=8 种，如果换成 100 条产线就是 2¹⁰⁰ 种，穷举根本不可能。这就是为什么教材要专门讲分支定界法、割平面法——它们本质上是“聪明地剪枝”，把明显不可能更优的分支提前砍掉。

注意：整数规划算出来的最优值，一定不会优于把整数限制去掉后的线性规划最优值。所以做题时可以先松绑算一遍，得到的那个数是一个上界（求最大时），用来检查后面结果有没有算错。

实际业务里还有一个折中做法：如果变量数值很大，比如产量动辄上万，那么“取整”造成的误差可以忽略，直接按线性规划算完四舍五入就行；但如果变量本身很小，比如“开几条产线”“买几台设备”，就必须老老实实做整数规划。

3.3 对偶问题：同一个问题的另一张面孔

练习卷里有一道名词解释，问“线性规划的对偶问题”。这个概念是很多人学运筹学时的一道坎，因为它听起来像是“把原题反过来再解一遍”，其实不是。

通俗地说，原问题是站在“生产者”角度问：我该怎么安排产量，让利润最大？对偶问题是站在“资源定价”角度问：如果这些煤、电、劳动力可以按市场价转让，我最低该开什么价才不亏？

这两个问题的最优值是相等的。也就是说，你辛苦生产能赚到的最大利润，等于你手上这些资源在最优配置下的“影子价格”总和。这个结论叫对偶定理。

对偶问题本身也是一个线性规划，只是变量和约束的角色发生了对调：原问题的每个约束，对应对偶问题的一个变量；原问题的每个变量，对应对偶问题的一个约束。最大值问题对最小值问题，≤ 对 ≥。

它的实用价值在于“影子价格”这个概念。假设煤的约束在最优解处是紧的（也就是煤刚好用完），那么对偶解里对应煤的那个数值，就告诉你“再多给一吨煤，利润能增加多少”。这个数可以直接拿去做采购决策：如果一吨煤的市场价低于影子价格，买进来就是赚的。

3.4 互补松弛性：为什么能“反推”对偶最优解

练习卷最后的综合题，给了一个线性规划，要求先写出对偶问题，再用互补松弛性求对偶最优解。这个方法值得单独说一下，因为它体现了一种很实用的思路：不用重新解一遍对偶问题，而是从原问题的最优解里“读”出对偶解。

互补松弛性说的是两句话：第一，如果原问题里某个约束没有被用满（有剩余），那么对偶问题里对应的那个变量一定等于 0；第二，如果原问题里某个变量大于 0，那么对偶问题里对应的那个约束一定取等号。

用大白话讲：一样资源如果还有富余，它的影子价格就是 0——多给你一点也没用，因为本来就用不完。反过来，一个真的在量产的产品，它消耗的资源一定是被用光的，否则你还能多产一点多赚一点，那就不叫最优了。

具体操作就是：先看原问题最优解里哪些变量非零，把对应的对偶约束改成等式；再看哪些约束是松的，把对应的对偶变量置为 0。这样一般能剩下两三个方程，解出来就完事。这条路比重新建模求解省事得多，但前提是你得先把原问题的最优解拿在手上。

4. 四个最容易搞混的概念：定性定量、对偶、关键路径与最优解

学到这儿，概念开始扎堆，很多词长得很像，用起来却完全不同。这一章挑四个最常被混为一谈的点，按“容易混在哪、为什么会混、怎么区分”说清楚。

4.1 定性分析与定量分析：不是谁替代谁

易混点：很多人以为定量分析更“高级”，定性分析就是拍脑袋，能不用就不用。

为什么混：因为教材里对定性分析的描述常常是“依据经验和判断”，听起来就不够严谨；而定量分析有公式有数据，自然显得可靠。

怎么区分：定性分析解决的是“这个问题值不值得算、该把哪些因素放进模型”，定量分析解决的是“在既定框架下，最优的那个数是多少”。前者决定边界，后者决定数值。

练习卷的名词解释里写得很明白：定性分析带有主观性，依赖决策者的经历和判断；定量分析依赖数据和模型，具有客观性。但客观性不等于正确性——模型里的假设是你定的，参数是你估的，如果一开始就把关键因素漏在模型外，算得再准也是白算。

举一个具体场景：某公司要不要进入一个新市场。这件事首先得靠定性判断——政策环境、消费习惯、竞争对手的反应，这些很难量化；等方向定了，再用定量分析算“投多少、分几年、产能铺多大”。顺序反了，就容易出现“用精确的方法算了一个不该算的问题”。

4.2 对偶问题不是“把原问题反着再算一遍”

易混点：以为对偶问题就是求最小值版本的原问题，或者以为它是原问题的一个“校验答案”。

为什么混：因为对偶问题确实是把 max 换成 min、把 ≤ 换成 ≥，形式上像照镜子。

怎么区分：原问题的变量是“产量”，对偶问题的变量是“资源价格”，两者描述的是完全不同的对象，只是最优值恰好相等。一个回答“做什么”，一个回答“值多少”。

这个区别在实际使用中很关键。如果你想知道“要不要多买一台设备”，看的是对偶解；如果你想知道“这条产线该排多少产量”，看的是原问题的解。把两者混着用，就会出现拿着影子价格去安排生产的荒唐操作。

4.3 关键路径不是“耗时最长的那条线”这么简单

易混点：以为关键路径就是把所有线路的长度算一遍，取最长的那条。

为什么混：在简单网络里这么算确实能对上答案，于是很多人就把它当成了定义。

怎么区分：关键路径的严格定义是“总时差为 0 的活动连成的路径”，也就是这条链上任何一个活动延迟一天，整个工程就延迟一天。它恰好也是最长路径，但“最长”是结果，不是判据。

练习卷里那道网络图题就是典型：A 工期 5 天无紧前，B 工期 1 天无紧前，C 工期 2 天紧前是 B，D 工期 4 天紧前是 A 和 C，E 工期 6 天紧前是 A，F 工期 3 天紧前是 D 和 E。算下来关键路径是 A-E-F，总工期 14 天。而活动 B 的总时差是 4 天——它可以晚开工 4 天而不影响总工期，因为它后面那条链路本身就有富余。

这个“总时差”才是网络分析真正的产出：它告诉你哪些活动可以缓一缓，哪些一天都不能拖。只会找最长路径，等于只用了这个方法一半的价值。

4.4 最优解、可行解、满意解：三个不同层次的答案

易混点：以为只要模型建出来，就一定能得到一个最优解。

为什么混：教材例题都很规整，算出来必有一个漂亮的最优解，容易让人以为这是常态。

怎么区分：可行解是满足所有约束的解，可能有很多个，也可能一个都没有；最优解是在可行解里目标值最好的那个，可能唯一，也可能有无数个（目标函数和某个约束平行时）；满意解则是现实里常用的退让——当模型太复杂、数据太贵、或者决策需要快速响应时，找一个“够好”的方案就收手。

举个具体的：某跨平台系统的排产问题，如果约束有上百条、还带整数和随机因素，求解时间可能从几秒涨到几小时。这时候业务部门往往等不起，直接用一个启发式规则排出可行方案就上线了。这不叫偷懒，这叫在“算得更准”和“决策更快”之间做取舍。

判断该用哪种，看两件事：这个决策错一次的代价有多大，以及你手上有多少时间。代价高、时间足，就追求最优；代价低、要快速响应，满意解就够。

5. 不确定性怎么算：决策树、网络图与表上作业法

前面几章处理的都是“数都知道”的问题，但现实里更常见的是“数不知道，只知道概率”。这一章讲三样工具：一个处理不确定性，一个处理时间安排，一个处理运输这类特殊结构的问题。

5.1 决策树：给“要不要先试一下”标价

练习卷里有一道新产品决策题：某工厂准备大批量投产一种新产品，估计销路好的概率 0.7、销路差 0.3；销路好获利 1200 万元，销路差亏损 150 万元。现在多了一个选项——先花 5 万元建一个小型试验工厂试销，试销时销路好的概率是 0.8；如果试销好，之后大批量投产时销路好的概率升到 0.85；如果试销差，之后销路好的概率只有 0.1。

这道题的关键，是把“决策点”和“机会点”分开画。决策点是你主动选的（试销或不试销、投产或不投产），机会点是概率决定的（销路好或差）。画出来之后，从右往左算期望值。

先算不试销的期望：0.7×1200 + 0.3×(−150) = 840 − 45 = 795 万元。

再算试销：如果试销好（概率 0.8），投产的期望是 0.85×1200 + 0.15×(−150) = 1020 − 22.5 = 997.5 万元；如果试销差（概率 0.2），投产的期望是 0.1×1200 + 0.9×(−150) = 120 − 135 = −15 万元。注意这里——试销差的时候，你完全可以不投产，收益是 0，比亏 15 万强。所以这一支取 max(−15, 0) = 0。

于是试销的期望是 0.8×997.5 + 0.2×0 = 798 万元，减去 5 万元试销成本，净得 793 万元。

793 小于 795，结论是不试销。

这个结果挺反直觉：花了钱买信息，反而不划算。但换个角度看就通了——信息本身确实有价值，价值等于 798 − 795 = 3 万元，可获取信息的成本是 5 万元，买卖不成立。这就是“完全信息价值”的概念：信息的价格上限，就是它带来的期望收益增量。

提示：决策树里最容易被漏掉的一环，就是“拿到坏消息之后可以选择不干”。少了这个选项，期望值会被算低，结论就会反过来。

5.2 网络图：关键路径与松弛时间怎么算

网络图的价值在于把一个多环节的项目拆成活动和先后关系，然后回答两个问题：整个项目最短多久能完工，哪些活动一天都不能拖。

手工算的时候用前推后推：前推算每个活动的最早开始和最早完成，后推算最晚开始和最晚完成，两者相减就是总时差。活动一多，手算就容易翻车，写几行代码更稳：

# 活动名: (紧前活动列表, 工期)，列表顺序已经是拓扑序 acts = { "A": ([], 5), "B": ([], 1), "C": (["B"], 2), "D": (["A", "C"], 4), "E": (["A"], 6), "F": (["D", "E"], 3), } order = ["A", "B", "C", "D", "E", "F"] # 保证算某个活动时，它的紧前活动已算完 es, ef = {}, {} for name in order: preds, dur = acts[name] es[name] = max([ef[p] for p in preds], default=0) # 所有紧前都完工才能开始 ef[name] = es[name] + dur project_end = max(ef.values()) # 工程总工期 ls, lf = {}, {} for name in reversed(order): succs = [k for k, (p, _) in acts.items() if name in p] lf[name] = min([ls[s] for s in succs], default=project_end) ls[name] = lf[name] - acts[name][1] slack = {k: ls[k] - es[k] for k in acts} # 总时差为 0 的活动构成关键路径

这段代码的逻辑是：前推阶段，一个活动的最早开始时间等于它所有紧前活动最早完成时间的最大值，default=0处理的是没有紧前活动的起点。后推阶段反过来，一个活动的最晚完成时间等于它所有紧后活动最晚开始时间的最小值，没有紧后活动的就用总工期收尾。最后slack为 0 的活动，就是关键活动。

参数上唯一需要注意的是order必须满足拓扑序，也就是任何一个活动都排在它的紧前活动之后。如果顺序错了，ef[p]会取到空值，结果就会莫名其妙地偏小，这是这类脚本最常见的出错位置。

5.3 表上作业法：运输问题为什么不用单纯形

练习卷里还有一道运输问题，四个产地、四个销地，给出单位运价、产量和销量，要求用表上作业法求解。这类问题的约束矩阵很特殊——每个变量只出现在两个约束里（一行一列），结构稀疏，用通用单纯形法算属于杀鸡用牛刀。

表上作业法的思路是：先在运价表上按某种规则（比如最小元素法或西北角法）凑出一个初始调运方案，然后用位势法算出每个格子的检验数，看有没有能改进的地方，有就沿着闭合回路调整，直到所有检验数都满足最优性条件。

它的好处是全程在表格上操作，不用写矩阵，适合手算。坏处是一旦规模上去了，闭回路的寻找会变得非常繁琐，实际项目里还是交给求解器。

值得注意的是，运输问题的约束有一个隐含条件：总产量必须等于总销量。如果不等，就要补一个虚拟产地或虚拟销地，运价填 0。这一步漏了，模型会直接无解，而且报错信息通常不会告诉你原因，属于典型的“踩坑点”。

6. 什么时候该请运筹学出场，什么时候别硬套

这套工具好用，但它有明确的适用边界。判断标准其实只有一条：这个问题的核心矛盾，是不是“在有限资源下做取舍”。

如果是，那建模大概率能帮上忙。比如排产、排班、路径规划、库存控制、项目工期压缩，这些问题的共同点是：目标清楚、约束能写出来、数据能拿到。反过来，如果核心矛盾是“目标本身还没想清楚”，比如一个新业务该不该做、团队文化该怎么建，那再精巧的模型也只是把模糊的东西包装得更精确而已。

具体一点，可以按下面这张表做初筛：

还有一个经常被忽略的边界：模型给出的是“在假设成立的前提下最优”，不是“现实中一定最好”。假设一旦松动，结论就可能反转。比如线性规划默认资源可以无限细分，但现实里你不可能买 0.37 台设备；比如决策树里的概率是估出来的，估偏 10 个百分点，最优方案可能就换了一个。所以真正靠谱的用法，是拿模型做“敏感性分析”——看看某个参数在多大范围内变动时，结论依然不变。范围越宽，这个决策越稳。

我自己就犯过一次典型的错误。早些年做一个小项目的排产测算，把设备可用工时按理论值填进去，模型算出来一个很漂亮的方案，我拿着就去汇报了。结果上线第一周就崩了——理论工时没算换型、没算保养、没算交接班，实际可用时间只有七成。模型没错，是我把参数喂错了。从那以后我每次建模都强制走一遍：先把每个参数问一句“这个数是哪来的、最坏能差多少”，再跑一次敏感性分析，确认结论在合理波动范围内还站得住，才敢往下用。

这也是我建议你拿这份练习卷动手过一遍的原因。卷面上的题只要求建模不求求解，看起来是降低了难度，实际上恰恰抓住了最容易出错的地方——变量设错、约束漏项、参数取值没纪律，这些错误在纸面上就能暴露，不用等到算完才发现结果荒唐。三道建模题分别对应副产品处理、整数开关、自制与外购的取舍，再加上对偶、网络图、决策树和运输问题，基本把入门阶段最核心的几类模型都覆盖到了。

如果你正处在“概念都听过、真上手就卡壳”的阶段，把这几道题从头到尾自己写一遍，比看十篇讲解都管用。完整资料已经整理好，按需取用就行，希望帮到你。

本文还有配套的精品资源，点击获取