KNOWECON WIKI

ARTICLE

Operations Research

运筹学 (Operations Research) 运筹学 (Operations Research，简称 OR) 是一门运用数学模型、统计分析和优化算法对复杂系统进行决策支持的科学。其名称源于第二次世界大战期间盟军运用科学方法优化军事行动（military operations）的实践。经过八十余年的发展，运筹学已广泛渗透至物流与供应链管理、生产调度、金融

浏览 0 更新 2025-10-31

运筹学 (Operations Research)

运筹学 (Operations Research，简称 OR) 是一门运用数学模型、统计分析和优化算法对复杂系统进行决策支持的科学。其名称源于第二次世界大战期间盟军运用科学方法优化军事行动（military operations）的实践。经过八十余年的发展，运筹学已广泛渗透至物流与供应链管理、生产调度、金融工程、交通规划、能源系统及公共卫生等社会经济各核心领域，成为现代管理科学和工业工程的数学支柱。

线性规划：运筹学的起点

运筹学现代化的重要里程碑是单纯形法 (Simplex Method) 的诞生。1947年，乔治·丹齐格 (George Dantzig) 在美军担任数学顾问期间提出线性规划 (Linear Programming) 的通用求解算法，使得如下标准形式的最优化问题首次获得了可实际操作的解法：

min⁡c⊤xs.t.Ax=b,x≥0\begin{aligned} \min \quad & \mathbf{c}^\top \mathbf{x} \\ \text{s.t.} \quad & \mathbf{A}\mathbf{x} = \mathbf{b}, \quad \mathbf{x} \geq 0 \end{aligned}

单纯形法的几何直观简明而深刻：可行域是由线性约束围成的凸多面体，最优解必出现在其某个顶点上。算法从当前顶点出发，沿边移动到使目标函数值改善的相邻顶点，反复迭代直至到达最优。尽管理论上存在 Klee-Minty 反例使单纯形法在最坏情形下需遍历指数级顶点，实践中算法表现出优异的平均效率。

苏联数学家列昂尼德·坎托罗维奇 (Leonid Kantorovich) 在1939年独立提出线性规划的雏形并阐释了影子价格的经济含义，因此与荷兰经济学家佳林·库普曼斯 (Tjalling Koopmans) 共同获得1975年诺贝尔经济学奖。这标志着运筹学与经济学的初次深度交汇。

1984年，纳伦德拉·卡玛卡 (Narendra Karmarkar) 提出内点法 (Interior Point Method)，由可行域内部趋近最优解，在理论上保证了多项式时间复杂度，对大规模稀疏问题在计算效率上优于单纯形法。现代商业求解器（CPLEX、Gurobi、MOSEK）通常同时实现两种范式，由预处理阶段自动选择或切换。

整数规划与组合优化

线性规划的决策变量若是连续量，可描述"生产多少吨钢材"一类问题；但大量现实决策是离散的——建不建仓、派不派车、选不选某条路径。此时需引入整数规划 (Integer Programming)，即要求部分或全部变量取整数值：

x∈Zn或xj∈{0,1}\mathbf{x} \in \mathbb{Z}^n \quad \text{或} \quad x_j \in \{0, 1\}

整数约束使可行域退化为高维空间中的离散格点集，问题复杂度从 P 类跃升至 NP-hard。代表性的求解方法包括分支定界法 (Branch and Bound)、割平面法 (Cutting Plane) 及其融合——分支切割法 (Branch and Cut)。典型的组合优化问题如旅行商问题 (TSP)、背包问题 (Knapsack)、车辆路径问题 (VRP)、设施选址问题等，尽管最坏情形下精确求解需指数时间，当代求解器结合有效不等式、启发式和预处理技术后，对实际规模的问题常能在合理时间内获得高质量解。

动态规划与序贯决策

对于具有阶段结构的多期决策问题，理查德·贝尔曼 (Richard Bellman) 在1950年代提出的动态规划 (Dynamic Programming) 提供了统一的求解框架。其核心是最优性原则 (Principle of Optimality)：一个最优策略从任意中间状态开始的剩余部分自身也是最优的。

由此导出贝尔曼方程：

V(s)=max⁡a∈A(s){r(s,a)+β∑s′P(s′∣s,a)⋅V(s′)}V(s) = \max_{a \in A(s)} \left\{ r(s, a) + \beta \sum_{s'} P(s' \mid s, a) \cdot V(s') \right\}

其中 V(s)V(s) 为状态 ss 下的值函数，r(s,a)r(s, a) 为即时收益，β∈(0,1)\beta \in (0, 1) 为折现因子，P(s′∣s,a)P(s' \mid s, a) 为状态转移概率。该方程将复杂的多期优化拆解为逐期递归的一阶条件，避免了穷举所有路径的指数级计算。

动态规划的应用远超运筹学边界：在宏观经济学中，生命周期消费-储蓄决策和 Ramsey 增长模型均可嵌入这一框架；在强化学习中，Q-learning 和策略梯度等方法可视为在转移概率未知时对贝尔曼方程的近似求解。在纯粹运筹学范畴内，动态规划广泛用于库存管理、设备更换、生产排程和资源分配等具有自然阶段划分的决策问题。

随机模型：排队论与库存理论

运筹学不仅处理确定性优化，也深刻研究随机系统。排队论 (Queueing Theory) 由厄朗 (A. K. Erlang) 于1909年开创，用于分析电话交换网中呼叫等待现象。经典模型为 M/M/1M/M/1 队列——到达间隔和服务时间均服从指数分布、单一服务台——其稳态队长分布为几何分布，平均排队人数为 ρ/(1−ρ)\rho/(1-\rho)（其中 ρ=λ/μ\rho = \lambda / \mu 为利用因子）。当 ρ→1−\rho \to 1^- 时系统平均等待时间趋于无穷，揭示了高负载下的严重拥堵特征。

现代排队论拓展至 M/G/kM/G/k（一般服务时间、多服务台）、优先权队列、排队网络（如 Jackson 网络）以及近似方法（如流体逼近和扩散逼近）。应用场景涵盖呼叫中心人员配置、云端服务器负载均衡、医院急诊分诊及机场安检通道设计。

报童模型 (Newsvendor Model) 则为随机库存理论的核心范式：决策者在随机需求实现前一次性订货，面临"订多则积压报废、订少则错失利润"的权衡。最优订货量由临界分位数 (Critical Fractile) 决定：

F(Q∗)=p−cp−s,F(Q^*) = \frac{p - c}{p - s},

其中 pp 为售价，cc 为成本，ss 为残值。当需求分布已知时，上式直接给出解析最优解。报童模型虽形式极简，其逻辑内核——在过度供给成本和短缺成本之间寻求边际均衡——贯穿于收益管理、供应链协调和产能规划等更为复杂的随机模型中。

方法论特征与经济学意义

运筹学与经济学共享对"稀缺资源有效配置"的关注，但方法论取向有所不同。经济学侧重均衡——多个独立决策者交互后形成的市场结果；运筹学偏重优化——在既定约束下为单一决策者（企业、政府、军事指挥部）寻找最佳行动方案。两者在博弈论处交汇：运筹学为博弈提供单方优化的计算工具，博弈论为多主体交互提供均衡概念。

运筹学一个重要的哲学特征是强调"模型化即决策"——将现实管理问题抽象为数学结构的过程本身迫使决策者明确目标、约束和假设，即使最终不使用形式化求解，这一结构化的思考方式也能改善判断质量。正如运筹学先驱斯塔福德·比尔 (Stafford Beer) 所言：模型的价值不全在于给出数字答案，而在于暴露假设、澄清权衡。

进入21世纪，运筹学与机器学习和数据科学发生深度融合。传统运筹学假定模型参数已知或可估计；现代数据环境下，需求函数、转移概率、服务时间分布等可从海量数据中学习，形成"预测后优化" (Predict-then-Optimize) 乃至"端到端决策学习"的新范式。另一方面，随机梯度下降和在线凸优化等机器学习中的计算技术也大量借鉴了运筹学的优化理论根基。运筹学正在从以模型驱动的学科演化为模型与数据双轮驱动的决策科学。