运筹学在工业工程里的落地：线性规划、排队论与仿真

运筹学是工业工程专业最"硬核"也最容易被认为"没用"的一门课。考试时算单纯形表算得头昏，工作后却发现排产、选址、配送路径这些问题，正是运筹学的老本行。这篇把三个最实用的分支——线性规划、排队论、离散事件仿真——从模型讲到落地。

一、运筹学在 IE 中的位置

运筹学（Operations Research, OR）的本质是：用数学模型描述决策问题，用算法求出最优或近优解。

IE 课程里与运筹学直接相关的有：

分支	解决的典型 IE 问题
线性规划（LP）	产品组合优化、配料问题、产能分配、人员排班
整数规划（IP / MIP）	选址、设备选配、切割下料、排程（含 0-1 决策）
网络计划（PERT/CPM）	项目进度管理、关键路径、工期-成本权衡
排队论（Queuing Theory）	服务台数量、缓冲区大小、AGV 数量、检验站配置
库存论	EOQ、安全库存、报童模型（见供应链篇）
动态规划	多阶段决策（如设备更新、生产批量）
决策论 / 博弈论	风险决策、供应商谈判策略
仿真（Simulation）	复杂系统无法解析求解时的验证手段
启发式/元启发式	遗传算法、模拟退火、禁忌搜索（大规模 NP 难问题）

二、线性规划：从建模到求解

1. 三要素

一个线性规划模型由三部分组成：

决策变量：我们要决定的量（x₁, x₂, ...）
目标函数：最大化或最小化的线性函数
约束条件：变量的线性等式或不等式限制

2. 经典例题：产品组合优化

某工厂生产 A、B 两种产品，需要经过机加、装配、检验三道工序。数据如下：

产品	机加（h）	装配（h）	检验（h）	单位利润（元）
A	2	1	1	3,000
B	1	3	1	4,000
可用工时	100	120	60	—

建模：

决策变量：x₁ = 产品 A 的产量，x₂ = 产品 B 的产量

目标函数：max Z = 3000x₁ + 4000x₂

约束条件：
  2x₁ + 1x₂ ≤ 100   （机加工时）
  1x₁ + 3x₂ ≤ 120   （装配工时）
  1x₁ + 1x₂ ≤ 60    （检验工时）
  x₁, x₂ ≥ 0        （非负约束）

求解（图解法/代数法）：

三个约束与两轴围成可行域，最优解一定在顶点上。求交点：

约束①③联立：2x₁ + x₂ = 100，x₁ + x₂ = 60 → 相减得 x₁ = 40，x₂ = 20
- 检验约束②：40 + 3×20 = 100 ≤ 120 ✓
- Z = 3000×40 + 4000×20 = 120,000 + 80,000 = 200,000
约束②③联立：x₁ + 3x₂ = 120，x₁ + x₂ = 60 → 相减得 2x₂ = 60，x₂ = 30，x₁ = 30
- 检验约束①：2×30 + 30 = 90 ≤ 100 ✓
- Z = 3000×30 + 4000×30 = 90,000 + 120,000 = 210,000
约束①②联立：2x₁ + x₂ = 100，x₁ + 3x₂ = 120 → 解得 x₁ = 36，x₂ = 28
- 检验约束③：36 + 28 = 64 > 60 ✗ 不可行
轴上顶点：(0, 40) → Z = 160,000；(50, 0) → Z = 150,000

最优解：x₁ = 30，x₂ = 30，最大利润 210,000 元。

3. 敏感性分析（比最优解更重要）

算出最优解只是开始，管理者真正关心的是"如果条件变了，结论还成立吗"。

影子价格（Shadow Price / 对偶价格）

影子价格 = 约束右端项增加 1 个单位时，目标函数增加的量。

上例中，若检验工时从 60 增加到 61（其他不变）：

新解：x₁ + x₂ = 61，x₁ + 3x₂ = 120 → x₂ = 29.5，x₁ = 31.5
检验约束①：2×31.5 + 29.5 = 92.5 ≤ 100 ✓
Z = 3000×31.5 + 4000×29.5 = 94,500 + 118,000 = 212,500
影子价格 = 212,500 - 210,000 = 2,500 元/小时

这意味着：多一小时检验工时能多赚 2,500 元。如果加班费低于 2,500 元/小时，加班就是划算的。

同理可算：装配工时的影子价格 = 500 元/小时（装配工时不是紧约束的可能性需验证），机加工时的影子价格 = 0（因为约束①有松弛：2×30+30=90 < 100，还有 10 小时没用完）。

关键洞察：

影子价格 > 0：该资源是紧约束（瓶颈），增加它有收益
影子价格 = 0：该资源有松弛（Slack），增加它没用

这个结论直接指向改善方向：别去改善非瓶颈资源。 这正是约束理论（TOC）的核心思想，也是运筹学与精益/TPS 的交汇点。

目标函数系数的可变范围

产品 A 的利润在什么范围内变化时，最优解 (30, 30) 保持不变？

在最优解处，紧约束是②③。设 A 的利润为 c₁：最优解保持的条件是目标函数斜率介于两条紧约束的斜率之间。

约束②的斜率：-1/3；约束③的斜率：-1 目标函数等值线斜率：-c₁/4000

要求：-1 ≤ -c₁/4000 ≤ -1/3 → 1333 ≤ c₁ ≤ 4000

即 A 的利润在 1333~4000 元之间变化时，生产 30 件 A、30 件 B 仍是最优方案。这给了决策者一个"不需要重新计算"的安全区间。

4. 整数规划：什么时候变量必须取整

很多实际问题的变量不能是小数：买几台设备（不能买 2.7 台）、选不选这个仓库（0-1 决策）。

典型问题 1：选址问题（0-1 规划）

决策变量：y_j = 1（在 j 地建仓）/ 0（不建），x_ij = 从仓库 j 配送给客户 i 的量

目标：min 总成本 = Σ f_j·y_j + ΣΣ c_ij·x_ij
      （固定建设成本 + 运输成本）

约束：
  Σ_j x_ij = d_i        （每个客户需求被满足）
  Σ_i x_ij ≤ Cap_j·y_j  （仓库容量约束，且不建仓则不能配送）
  y_j ∈ {0, 1}

这就是经典的"设施选址问题（Facility Location Problem）"，与 IE 的设施规划课直接对应。

典型问题 2：切割下料（Cutting Stock）

原材料长 6 米，需切割成 2.2 米（80 根）、1.8 米（120 根）、1.2 米（150 根）的料段。如何下料用料最省？

可行切割模式举例：

模式	2.2m	1.8m	1.2m	余料
P1	2	0	1	0.4
P2	1	2	0	0.2
P3	0	3	0	0.6
P4	0	1	3	0.6
P5	1	0	3	0.2

建立整数规划：决策变量为各模式的使用根数，约束为各规格的需求量，目标为余料最小。这类问题的变量数可能很大（模式组合爆炸），工业上常用"列生成（Column Generation）"算法求解。

5. 求解工具

工具	特点
Excel 规划求解（Solver）	上手最快，小规模问题（< 200 变量）够用。用单纯形法/GRG 非线性/演化算法
Python + PuLP / Pyomo	免费、可编程、可复用，建模语法清晰，调用 CBC/GLPK 求解器
Python + OR-Tools（Google）	功能强大，支持 CP、MIP、VRP（车辆路径）、排程专用模块
Lingo / LINDO	学术常用，语法贴近数学表达式
Gurobi / CPLEX	商业求解器，性能最强，学术免费授权，工业授权昂贵
SCIP / HiGHS	开源高性能求解器

给学生的建议：先用 Excel Solver 建立直觉（能看到影子价格和敏感性报告），再用 Python + PuLP/OR-Tools 解决真实规模的问题。

一个 PuLP 的最小示例：

import pulp

prob = pulp.LpProblem("产品组合", pulp.LpMaximize)
x1 = pulp.LpVariable("A", lowBound=0, cat="Continuous")
x2 = pulp.LpVariable("B", lowBound=0, cat="Continuous")

prob += 3000*x1 + 4000*x2, "总利润"
prob += 2*x1 + x2 <= 100, "机加工时"
prob += x1 + 3*x2 <= 120, "装配工时"
prob += x1 + x2 <= 60, "检验工时"

prob.solve()
print(f"A={x1.value()}, B={x2.value()}, 利润={pulp.value(prob.objective)}")
# 影子价格
for name, c in prob.constraints.items():
    print(name, "影子价格 =", c.pi)

三、排队论：缓冲区、服务台与等待时间

1. 为什么 IE 要学排队论

车间里到处是排队：工件在设备前排队、AGV 在充电位排队、检验员在待检品前排队、维修工在报修单前排队。

排队论回答三个问题：

平均等待时间是多少？
队列有多长？需要多大的缓冲区？
需要几个服务台（设备/人员/AGV）才能平衡服务水平和成本？

2. Kendall 记号

标准格式：A / B / c / K / N / D

A：到达过程分布（M = 泊松/指数，D = 确定，G = 一般分布）
B：服务时间分布（M / D / G）
c：服务台数量
K：系统容量（默认 ∞）
N：顾客源总数（默认 ∞）
D：排队规则（FCFS / LCFS / SIRO / 优先级，默认 FCFS）

最常用的是 M/M/1 和 M/M/c。

3. M/M/1 模型的核心公式

条件：到达为泊松过程（速率 λ），服务时间服从指数分布（服务率 μ），单服务台，FCFS，无限队长。

系统利用率（交通强度）ρ = λ / μ        （要求 ρ < 1，否则队列无限增长）

系统中的平均顾客数 Ls   = λ / (μ - λ) = ρ / (1 - ρ)
队列中的平均顾客数 Lq   = λ² / (μ(μ - λ)) = ρ² / (1 - ρ)
系统中平均逗留时间 Ws   = 1 / (μ - λ)
队列中平均等待时间 Wq   = λ / (μ(μ - λ)) = ρ / (μ - λ)

Little 法则（通用，不限于 M/M/1）：

L = λ × W
（系统中的平均数量 = 到达率 × 平均逗留时间）

这个法则极其有用，适用于任何稳定系统。比如：某车间在制品平均 240 件，日均产出 60 件，则平均生产周期 = 240 / 60 = 4 天。

4. 算例：检验站要配几个人

工件以泊松过程到达检验站，平均 每小时 12 件。一名检验员平均检验速度为 每小时 15 件（指数分布）。

方案 A：配 1 人（M/M/1）

λ = 12，μ = 15，ρ = 12/15 = 0.8

Ls = 0.8 / (1 - 0.8) = 4 件
Lq = 0.64 / 0.2 = 3.2 件
Ws = 1 / (15 - 12) = 0.333 小时 = 20 分钟
Wq = 12 / (15 × 3) = 0.267 小时 = 16 分钟

方案 B：配 2 人（M/M/2）

M/M/c 需先算 P₀（系统空闲概率）：

c = 2，λ = 12，μ = 15，ρ = λ/(cμ) = 12/30 = 0.4

P₀ = [ Σ(n=0 到 c-1) ( (λ/μ)^n / n! ) + ( (λ/μ)^c / c! ) × ( 1 / (1-ρ) ) ]^(-1)
   = [ (0.8^0/0!) + (0.8^1/1!) + (0.8^2/2!) × (1/(1-0.4)) ]^(-1)
   = [ 1 + 0.8 + (0.64/2) × 1.667 ]^(-1)
   = [ 1 + 0.8 + 0.533 ]^(-1)
   = (2.333)^(-1) = 0.4286

Lq = [ (λ/μ)^c × ρ / (c! × (1-ρ)²) ] × P₀
   = [ 0.64 × 0.4 / (2 × 0.36) ] × 0.4286
   = [ 0.256 / 0.72 ] × 0.4286
   = 0.3556 × 0.4286 = 0.1524 件

Wq = Lq / λ = 0.1524 / 12 = 0.0127 小时 ≈ 0.76 分钟
Ws = Wq + 1/μ = 0.0127 + 0.0667 = 0.0794 小时 ≈ 4.76 分钟
Ls = λ × Ws = 12 × 0.0794 = 0.952 件

结果对比：

指标	1 人	2 人
平均等待时间 Wq	16 分钟	0.76 分钟
平均逗留时间 Ws	20 分钟	4.76 分钟
系统中平均工件数	4.0 件	0.95 件
检验员利用率	80%	40%

决策分析：加一个人，等待时间从 16 分钟降到 0.76 分钟。值不值？要看等待的代价（在制品占用、交付周期、下游停工风险）与人力成本的对比。

这里有一个重要的非线性规律：当单服务台利用率 ρ 接近 1 时，等待时间会爆炸性增长。

ρ	Wq（以 1/μ 为单位）
0.5	1.0
0.7	2.33
0.8	4.0
0.9	9.0
0.95	19.0
0.99	99.0

实践启示：

设备利用率追求 100% 是灾难——排队会无限增长
瓶颈设备的利用率一般控制在 85% 左右，留出缓冲
非瓶颈设备的利用率低是正常的，不是浪费

5. 降低等待的四个杠杆

增加服务台数（c）：最直接，但有成本
提高服务率（μ）：改善工装、标准化作业、减少换型
降低到达波动：平准化（Heijunka）、批量均衡化——波动比均值更致命
改变排队规则：优先级调度（紧急件优先）

特别强调第 3 点：M/M/1 的等待时间远大于 M/D/1（到达/服务确定的情形）。降低变异性，往往比增加产能更划算且更便宜。 这是精益强调"平准化"和六西格玛强调"降低变异"的数学依据。

四、项目进度：PERT/CPM

关键路径法（CPM）

步骤：

分解活动（WBS），确定各活动工期
确定前后关系（紧前活动）
画网络图（AON 单代号网络图最常用）
正推法算最早开始 ES / 最早完成 EF
逆推法算最迟开始 LS / 最迟完成 LF
计算总时差 TF = LS - ES = LF - EF
总时差为 0 的活动连成的路径 = 关键路径

PERT 的三点估计

活动工期不确定时，用三点估计：

期望工期 TE = (乐观时间 a + 4 × 最可能时间 m + 悲观时间 b) / 6
方差 σ² = ((b - a) / 6)²

项目总工期的方差 = 关键路径上各活动方差之和（假设独立），据此可算完工概率。

时间-成本权衡（赶工 Crashing）

压缩关键路径上的活动可以缩短工期，但要付出额外成本。要选择赶工成本斜率最小的活动优先压缩，且压缩后要重新计算关键路径（可能出现多条关键路径）。

五、仿真：当解析方法失效时

排队论和线性规划都有严格的假设（泊松到达、指数分布、线性关系）。真实系统往往不满足，这时用离散事件仿真。

什么时候用仿真

系统太复杂，无法建立解析模型
存在大量随机性（故障、换型、质量返工）
需要验证"如果……会怎样"（what-if）
需要观察动态行为（拥堵如何形成、瓶颈如何漂移）

仿真的基本要素

要素	说明
实体（Entity）	流动的对象：工件、订单、AGV、人员
属性（Attribute）	实体携带的信息：订单号、优先级、工艺路线
资源（Resource）	提供服务的对象：设备、工位、人员、叉车
队列（Queue）	排队规则：FIFO / 优先级 / 按交期
事件（Event）	触发状态变化：到达、开始加工、完成、故障
随机分布	到达间隔、加工时间、故障间隔（MTBF）、修复时间（MTTR）

仿真的正确流程（很多人搞错）

定义问题与目标：不要"为了仿真而仿真"
收集数据：到达间隔分布、加工时间分布、故障率、换型时间——垃圾进，垃圾出
建立概念模型：画出流程图与逻辑关系
验证模型（Verification）：模型是否按你设想的逻辑运行？（代码/逻辑是否正确）
确认模型（Validation）：模型输出是否与真实系统吻合？（用历史数据对比）
设计实验：要对比哪些方案？样本量多少？
运行与分析：注意**预热期（Warm-up）**的处理——稳态仿真要丢弃初始阶段的数据
多次重复运行：随机系统一次运行的结果没有意义，要多次运行取均值与置信区间
输出结论与建议

最常见的错误：

不分预热期，把初始空系统的数据算进结果（严重低估在制品）
只跑一次就下结论（随机误差巨大）
不做模型确认（模型与真实系统对不上，结论自然不可信）

六、运筹学学习的实用建议

先建立直觉，再啃算法。理解"影子价格 = 资源边际价值"、"ρ 趋近 1 时排队爆炸"这些直觉，比会手算单纯形表重要得多。
用 Excel Solver 练手。它能在建模、求最优解、跑敏感性报告之间快速闭环，非常适合建立手感。
学一门建模语言。Python + PuLP/OR-Tools 是性价比最高的选择，能处理 Solver 搞不定的规模。
重视建模 > 求解。真实工作里，把业务问题抽象成变量、目标、约束的能力，比会调用哪个求解器更稀缺。
结合专业场景练：用排班问题练整数规划、用 AGV 配置问题练排队论、用产线方案比选练仿真。

小结

运筹学在 IE 中的主干：线性规划（组合优化）、排队论（缓冲区与服务台）、PERT/CPM（进度）、仿真（复杂系统）。
线性规划最有价值的产出不是最优解，而是影子价格——它指出哪个资源是真正的瓶颈。改善非瓶颈资源没有收益。
排队论核心公式：ρ = λ/μ，Wq = λ/(μ(μ-λ))，L = λW（Little 法则）。
当 ρ 接近 1 时等待时间爆炸，所以设备利用率不宜追求 100%，瓶颈通常控制在 85% 左右。
降低波动比增加产能更划算，这是平准化与六西格玛的数学依据。
仿真必须做验证（逻辑对不对）+ 确认（与真实对不对），处理预热期，多次重复运行取置信区间。

配套阅读：《供应链与库存管理》《设施规划与车间布局》《用 Python 做 IE 数据分析》。

工业工程