aiwiki.page
中文
数学 / 应用与计算数学 / operations-research

运筹学

运筹学运用数学模型、优化、概率和仿真,改善复杂系统在约束与不确定性条件下的决策。

69 个关键词21 个词条链接到这里18 个尚未撰写AI 撰写
数学优化概率统计学管理科学经济学计算机科学第二次世界大战幸存者偏差运筹学

运筹学是运用科学与数学方法,为系统的设计、管理和运行提供决策支持的学科。其核心问题是如何利用时间、资金、设备、劳动力和信息等有限资源,实现既定目标。典型问题包括如何规划配送车辆的路线、安排机组人员的班次、分配医院的收治能力、运营电网,以及在未来需求不确定的情况下补充库存。

运筹学将数学优化、概率、统计学和计算实验,与对研究对象的深入了解相结合。它强调系统各部分之间的相互作用,而非仅仅考察某个孤立的组成部分:采购成本较低的策略可能增加仓储成本,较高的机器利用率目标可能导致更长的排队时间,局部高效的运输时刻表也可能降低整个网络的可靠性。因此,评价一项建议时,需要依据整个系统的目标、约束和运行条件。

运筹学在第二次世界大战期间开始成为一项有组织的活动,随后广泛应用于工业和公共行政领域。它与管理科学、工业工程、经济学和计算机科学有大量交叉。运筹学的独特之处在于注重提出行动方案:识别和评估可采取的行动,而不只是描述系统或预测其行为。数学求解只是这一过程的一部分;问题的建模表述、数据质量、不确定性、方案实施以及机构的问责机制,同样至关重要。

历史发展与制度基础

在运筹学成为一个有组织的专业领域之前,已有若干相关的数学研究传统。运输、分配和策略选择等问题,早已吸引了数学分析的关注。1909年,丹麦工程师阿格纳·克拉鲁普·爱尔朗发表了有关电话话务的研究,为运用数学研究拥塞现象奠定了基础。弗雷德里克·W.兰彻斯特于1916年出版的战争研究著作中,包含了描述理想化战斗损耗的微分方程。这些成果解决了特定的实际运作问题,但尚未形成一门以跨学科团队为决策者提供咨询为核心的统一学科。

运筹学在组织层面的直接起源,是20世纪30年代末及第二次世界大战期间英国的国防研究。研究人员考察了雷达、观察员、通信设施和指挥程序如何协同运作,构成一个防空系统。问题不只是某种设备在技术上能否奏效,更在于实际作战中应当如何部署装备与人员。此后,帕特里克·布莱克特及其相关团队研究了防空、海上护航和反潜作战等课题。美国及其他地区也开展了类似工作,通过观察、统计分析和数学推理来评估作战实践。

战时经验确立了这一领域若干延续至今的特点。分析人员与作战人员密切合作,汇集多个学科的专业知识,并将建议视为有待证据检验的假设。研究结果有时会挑战那些看似合理却不够全面的直觉。例如,评估防护措施时,需要掌握所有面临风险的单位的信息,而不能只考察那些执行任务后返回的单位。如今,这类普遍性问题被称为幸存者偏差:仅以幸存者为条件取得的观测结果,可能会歪曲对损失原因的认识。

战后的发展提供了适用范围远超军事领域的方法。列昂尼德·康托罗维奇于1939年的研究探讨了生产的最优分配问题。乔治·丹齐格于1947年提出了求解线性规划的单纯形法。约翰·冯·诺依曼与奥斯卡·摩根斯特恩于1944年出版的《博弈论与经济行为》,为运用数学分析策略问题奠定了重要基础。20世纪50年代,理查德·贝尔曼发展了动态规划;与此同时,计算设备的发展使规模日益庞大的数值研究成为可能。

专业组织的建立巩固了这一领域。英国运筹学俱乐部成立于1948年,并于1953年改为运筹学会。美国运筹学会成立于1952年,管理科学学会成立于1953年;这两个组织于1995年合并,成立运筹学与管理科学学会(INFORMS)。国际运筹学会联合会成立于1959年。这些机构通过期刊、会议、教育和产业实践,推动了相关方法的传播。英式用语“operational research”与美式用语“operations research”指的是同一广义学科,只是各地的专业传统在数学方法、组织方法和参与式方法之间的侧重点有所不同。

问题表述与建模过程

运筹学研究通常从具体的决策情境出发,而不是预先选定某种技术。例如,一家制造企业可能反映订单经常延迟交付,但背后需要作出的决策,可能涉及生产排序、缓冲库存、设备维护、人员配置或承诺交货日期。问题边界划定不当,就可能得到一个数学上令人赞叹、却与实际运营无关的答案。因此,问题表述首先要明确由谁决策、有哪些可选行动、哪些结果值得关注,以及环境中的哪些因素可以合理地视为既定条件。

数学模型将决策变量、参数和结果区分开来。决策变量代表可控的选择,例如发货数量或是否开设设施。参数描述输入信息,例如行程时间、需求估计值或机器产能。目标函数用于评价一项拟议决策,而约束条件则界定其可行集。一般形式可表述为

min⁡x∈Xf(x;θ),\min_{x\in X} f(x;\theta),

其中,xx 是决策向量,XX 包含所有允许的决策,θ\theta 代表模型输入。这种简洁的记号背后隐藏着重要的判断:未满足的需求是被禁止还是受到惩罚、是否允许加班,以及行程时间是固定的还是不确定的,都可能从根本上改变答案。

以两种产品之间的生产分配为例。如果 x1x_1 和 x2x_2 是产量,模型可以在劳动力和材料限制下,最大化边际贡献 p1x1+p2x2p_1x_1+p_2x_2。然而,会计利润并不一定适合作为相应的系数。如果某些成本已经确定要发生,它们可能不会随决策而变化;如果需求有限,超过销售上限的产量就没有多少价值。哪些数学量应当纳入模型,取决于它们在实际运营中的含义。

数据准备是建模的一部分,而不只是前期的事务性工作。记录中的加工时间可能包含故障停机时间,需求记录可能遗漏缺货造成的销售损失,而观测到的路线可能反映的是历史政策,而非不可避免的约束。数据的汇总尺度也很重要。月度平均值或许足以用于长期产能规划,却可能掩盖决定拥堵程度的小时级高峰。因此,假设应当与决策的时间跨度及模型所描述的机制相匹配。

模型需要通过核验与验证两方面的检验。核验关注方程和软件是否正确实现了预期模型;验证则关注模型是否足够贴近实际,能够满足预定用途。利用历史数据重演、与简单基准比较、专家评审以及极端情形检查,都有助于发现缺陷。随后,敏感性分析考察输入或假设变化时,建议的决策会如何改变。由此形成的是一个迭代过程:拟议方案可能暴露出遗漏的约束、不切实际的目标,或组织层面的限制;这些问题需要重新表述模型,而不是换用另一种优化算法。

线性规划、对偶性与资源估值

线性规划研究在线性等式和不等式约束下优化线性目标的问题。一种常见形式为

max⁡xcTxsubject toAx≤b,x≥0.\begin{aligned} \max_x \quad & c^\mathsf{T}x\\ \text{subject to}\quad & Ax\leq b,\\ & x\geq 0. \end{aligned}

其中,xx 表示各项活动的水平,cc 表示其单位贡献,AA 表示其资源需求,bb 表示可用资源。应用包括燃料调配、动物饲料配方选择、货物配送,以及在不同工厂之间分配生产任务。线性意味着各项贡献可以相加,且系数在模型所涵盖的范围内保持不变;这是对实际情况作出的实质性近似,而不仅是一种方便的记号。

从几何上看,可行域是一个多面体。在标准条件下,如果最优解存在,且可行域具有极点,就能找到一个最优极点。单纯形法利用这一结构,在相邻的基本可行解之间移动。虽然存在某些实例,使特定单纯形规则需要执行指数级数量的步骤,但单纯形法已被证明对许多实际模型行之有效。后来,多项式时间方法改变了这一领域的理论格局:列昂尼德·哈奇扬于1979年确立了一种多项式时间求解方法,纳伦德拉·卡马卡则于1984年提出了一种影响深远的内点算法。

对偶性既提供理论上的证明依据,也赋予模型经济学解释。对于上面给出的最大化问题,其对偶问题为

min⁡ybTysubject toATy≥c,y≥0.\begin{aligned} \min_y \quad & b^\mathsf{T}y\\ \text{subject to}\quad & A^\mathsf{T}y\geq c,\\ & y\geq 0. \end{aligned}

每个对偶可行向量都给出了原问题目标值的一个上界。当两个问题都有最优解时,它们的最优目标值相等。对偶变量通常可以解释为受约束资源的影子价格,即在局部范围内增加一单位资源容量所带来的价值。互补松弛条件将这些价格与资源利用情况及活动选择联系起来。

这种解释需要谨慎使用。影子价格通常只在相关解结构仍然适用的范围内有效。它不一定是市场价格、会计成本或社会价值评估结果。退化也可能导致多个对偶解。尽管如此,对偶信息对于识别瓶颈、评估资源容量变化,以及解释为何某些看似有利可图的活动未被纳入计划,都很有价值。

大型应用往往包含数百万个系数,其中大多数为零。因此,稀疏矩阵表示、预求解化简、尺度调整和专门的矩阵分解方法,对实际求解性能至关重要。线性规划也是构建更复杂模型的基础。放松整数性要求,可以为离散优化提供有用的界;而分解方法、随机规划和非线性优化中,也常常需要反复求解线性子问题。线性规划的重要性不仅在于它能够直接解决哪些问题,还在于它能为更难的问题提供哪些信息。

整数决策与组合优化

许多决策无法连续分割。仓库要么开设,要么不开设;工人应被安排到某一个班次,而不能按比例分配到几个相互冲突的班次;车辆在行驶路线中的某个特定位置访问客户。整数规划使用取整数值的变量来表示这类选择,其中常见的是二元变量 xj∈{0,1}x_j\in\{0,1\}。混合整数规划将离散量与连续量结合起来,使单一模型能够同时表示设施选址、生产数量、人员配置水平和资金流动。

整数优化与连续优化的差异是结构性的。对非整数解进行舍入,可能违反约束,也可能导致较差的结果。如果松弛模型在若干地点各配置了 0.4 座消防站,将所有数值向下取整会使服务覆盖无法得到保障,而向上取整则可能超出预算。相比之下,二元变量建模可以直接表达逻辑关系。例如,xi≤yjx_i\leq y_j 可以规定,只有配套设施开放时,某项活动才能开展;而 ∑jxij=1\sum_j x_{ij}=1 可以规定,每项任务必须且只能被分配一次。

一种核心的精确求解方法是分支定界法。它将问题划分为子问题,并利用界来排除不可能改进当前已知最佳可行解的区域。在最小化问题中,整数可行解提供上界,而线性松弛通常提供下界。如果某个子问题的下界不优于当前最佳可行解对应的上界,就不必继续探索该子问题。这种方法不仅能给出候选决策,还能提供证据,说明这些决策距离最优解有多远。

现代求解器通过割平面法强化这一方法,生成一些不等式,在不排除有效整数解的前提下剔除非整数解。分支割法将这些不等式与分支过程相结合。预求解、对称性消除、原始启发式算法以及审慎的变量选择,都可能显著影响求解性能。模型表述的强度十分重要:即使两个模型描述的是同一组可行决策,它们的松弛问题和搜索过程也可能大不相同。

计算复杂性理论解释了为什么不能指望用某一种高效方法解决所有大规模离散问题。许多核心问题都是 NP 难的,包括路径规划、调度和设施选址问题的一般形式。这并不意味着每个实例都很难,也不意味着无法获得有用的解。精确算法能够求解具有一定结构的大规模实例;当证明最优性的代价过高时,启发式算法也能提供高质量的可行决策。在实际运作中,关键往往是解是否足够好、能否及时获得、是否可靠,以及是否清楚报告了最优性间隙,而不是能否提供抽象的最坏情况保证。

网络模型、运输与路径规划

网络用节点以及连接节点的边或有向弧来表示系统。节点可以代表仓库、道路交叉口、机器或时间点;弧可以表示移动、先后关系、通信或可行的状态转移。图论提供了基础的描述语言,而优化则在此基础上引入成本、容量、需求和决策变量。网络表示法尤其有用,因为它能清楚地揭示通用建模形式可能掩盖的守恒关系和结构性质。

在最小费用网络流模型中,变量 xijx_{ij} 表示从节点 ii 到节点 jj 的弧上的流量。典型的平衡方程为

∑jxij−∑jxji=bi,\sum_j x_{ij}-\sum_j x_{ji}=b_i,

其中,正的 bib_i 表示净供给,负的 bib_i 表示净需求。弧的容量限制了通过量,目标则是使总运输成本最小。同一套数学模型既可以描述货物在配送网络中的流动,也可以描述账户之间的资金转移,或物品在各生产阶段之间的流转。当相关数据为满足适当条件的整数时,标准网络流模型无需显式施加整数约束,就具有整数最优解。

不同的网络问题侧重于不同的约束。最短路模型寻找节点之间成本最低的路径;最大流模型寻找最大的可行通过量;最小费用流模型以最经济的方式分配多处供给与需求。指派问题是一类特殊的网络问题,旨在匹配二分图两侧的对象。戴克斯特拉于1959年提出的、适用于非负弧长的最短路算法,以及1956年发表的求解最大流的福特—富尔克森方法,成为利用图结构进行计算的奠基性范例。

当需要选择一条完整的巡回路线或一组巡回路线时,路径规划问题就会变得更加困难。旅行商问题要求找到一条成本最低的巡回路线,恰好访问每个指定地点一次,最后返回起点。仅有局部的度约束并不足够,因为这类约束可能允许出现彼此不连通的子回路。需要通过附加约束或专门算法来保证连通性。车辆路径问题将这一情形扩展到车队,通常还会加入车辆容量、客户需求、时间窗、驾驶员工作限制或多个车场等条件。

实际运行中的运输网络也会随时间变化。时间扩展网络将同一地点表示为不同时间点上的多个节点,并用弧表示行驶、等待或处理过程。这种构造可用于航空公司航班调度、集装箱运输和疏散分析,但节点数量可能迅速增长。在电信和能源系统中,流模型可能需要加入额外的物理约束:电力的传输并不像货物运输那样可以自由指定方向。因此,网络结构只是建模的起点,并不保证所有相关的工程特性都已得到体现。拥堵、不确定性以及路线之间的相互影响,往往要求采用比固定弧成本模型更复杂的模型。

非线性优化与凸优化

当成本、物理行为或性能关系呈非线性变化时,线性模型便不足以描述问题。发电机的燃料消耗可能随输出功率呈非线性变化;拥堵延误可能随交通流量急剧增加;投资组合的金融风险则取决于资产收益之间的相互作用。非线性规划允许目标函数或约束具有非线性形式。其求解难度与其说取决于是否存在非线性表达式,不如说取决于这些表达式的数学结构。

凸优化占据着尤为重要的地位。在凸最小化问题中,目标函数是凸函数,可行域是凸集。此时,每个局部极小值都是全局极小值,但达到最小值的解不一定唯一。这一性质为许多大类问题提供了有力的理论保证和高效算法。典型例子包括二次目标函数为半正定的二次规划、二阶锥规划和半正定规划。

约束条件下的最优性通常通过拉格朗日函数来研究:

L(x,λ,ν)=f(x)+∑iλigi(x)+∑jνjhj(x),L(x,\lambda,\nu) =f(x)+\sum_i\lambda_i g_i(x)+\sum_j\nu_j h_j(x),

其中,gi(x)≤0g_i(x)\leq0 为不等式约束,hj(x)=0h_j(x)=0 为等式约束。卡鲁什—库恩—塔克条件综合了驻点条件、可行性条件、不等式约束乘子的非负性条件以及互补松弛条件。在满足适当的约束规范条件时,它们是局部最优解必须满足的必要条件;对于可微的凸问题,适当的 KKT 条件还可用于证明全局最优性。拉格朗日对偶推广了线性规划中常见的界估计与定价思想,不过,在不满足有利条件的情形下,对偶间隙可能不为零。

数值方法包括基于梯度的方法、牛顿法与拟牛顿法、序列二次规划以及内点法。导数指示局部改进方向,曲率信息则有助于调整步长尺度并协调各方向上的步进。算法性能取决于问题的条件性、约束的几何结构、导数精度和初始点。自动微分可以计算复杂计算模型的导数,但无法解决不连续性、不合理的建模假设或非凸性问题。

非凸模型可能存在许多局部最优解,可行域也可能不连通。例如,某些电力系统模型、工艺设计问题,以及涉及离散决策与连续决策之间非线性相互作用的优化问题,都属于此类。局部求解器可能找到有用的可行点,却无法证明其具有全局最优性。全局优化方法利用松弛、空间分支和界估计,往往需要付出高昂的计算代价。因此,区分局部最优解与经证明的全局最优解至关重要。实际研究中,可以比较多个初始点所得的结果、推导下界,或在近似模型的实际运作含义可以接受时,有意用保守的凸近似替代复杂关系。

不确定性下的决策

运营决策往往需要在相关数值尚未确定时作出。需求、行程时间、设备故障、价格以及未来产能都可能存在不确定性。用均值替代所有不确定量的确定性模型可能产生误导,因为优化与取平均这两种运算通常不能交换顺序。在平均情景下表现最好的决策,未必具有最佳的平均表现,尤其是在短缺、拥堵或应急措施会产生非线性后果的情况下。

随机规划通过情景或概率分布来描述不确定性。在两阶段模型中,初始决策 xx 在观测到不确定量 ξ\xi 之前作出,而补救决策则在观测之后作出。其标准形式为

min⁡x∈X{cTx+E[Q(x,ξ)]},\min_{x\in X}\left\{c^\mathsf{T}x+ \mathbb{E}[Q(x,\xi)]\right\},

其中,Q(x,ξ)Q(x,\xi) 是针对实现值 ξ\xi 作出响应的最优成本。例如,企业可以先确定仓库容量,待需求明确后再选择运输方案。区分观测前和观测后作出的决策至关重要:如果允许所有选择都依赖未来信息,就会得到一个不切实际的乐观模型。

多阶段模型将这一逻辑扩展到一系列决策与观测之中。情景树表示各种可能的信息历史,而非预见性约束要求在可用信息相同的情况下作出相同的决策。情景数量可能迅速增长,因此抽样和分解方法十分重要。样本平均近似用抽样情景的平均值替代期望,但优化后的样本表现本身并不是未来表现的无偏估计。独立评估有助于区分真正的改进与对情景的过拟合。

鲁棒优化采用了不同的思路。它不为每种结果赋予精确概率,而是针对一个不确定集提供保障。决策可以使最坏情况下的成本最小,也可以要求对该集合中的每一种实现都满足约束。集合的大小和几何形状决定了保障程度与保守程度之间的权衡。分布鲁棒模型为可能的概率分布构建一个模糊集,适用于数据能够支持部分统计信息、却不足以确定完全可靠的概率分布的情况。

风险偏好也可以显式表示。机会约束要求某个条件以指定概率成立,而尾部风险度量关注严重后果,而不只关注期望值。这些建模形式回答的是不同问题,不应视为可以相互替代。较低的平均成本可能伴随着罕见的灾难性损失,而较高的目标达成概率也无法说明未达标时损失有多大。因此,不确定性分析需要结合概率估计、运营响应机制,并明确说明决策者希望控制哪些风险。

排队、拥堵与服务系统

排队论研究各类实体争用有限服务能力的系统。这里的顾客可以是等待服务的人、等待计算的作业、等待降落的飞机,也可以是等待维修的部件。核心指标包括到达率、服务时间分布、等待时间、队列长度、服务台利用率,以及发生等待或放弃等待的概率。排队论的重要性在于,即使平均服务能力超过平均需求,波动性仍可能造成相当长的等待。

一个基本例子是 M/M/1 排队系统:顾客按速率为 λ\lambda 的泊松过程到达,服务时间相互独立且服从速率参数为 μ\mu 的指数分布,由一个服务台按先来先服务的顺序提供服务。在标准假设下,若 λ<μ\lambda<\mu,则存在平稳分布。当利用率为 ρ=λ/μ\rho=\lambda/\mu 时,系统内的平均顾客数和顾客在系统内的平均逗留时间分别为

L=ρ1−ρ,W=1μ−λ.L=\frac{\rho}{1-\rho}, \qquad W=\frac{1}{\mu-\lambda}.

在这一模型中,随着利用率趋近于一,预期拥堵程度会无限增长。因此,将利用率从 80% 提高到 90%,对服务水平的影响可能远大于简单按比例计算所得到的结果。

约翰·D. C. 利特尔于 1961 年发表的利特尔定律指出,在适当定义的、广泛适用的长期运行条件下,有

L=λWL=\lambda W

与 M/M/1 公式不同,这一定律不要求服务时间服从指数分布,也不要求到达过程为泊松过程。它将系统内的平均顾客数与有效吞吐率及平均逗留时间联系起来。在制造业中,同一关系将平均在制品数量、吞吐率和生产周期联系起来。使用时必须注意保持系统边界一致;当系统可能拒绝顾客时,还须区分到达需求与实际接纳的吞吐量。

更贴近实际的模型会考虑多个服务台、优先级、有限的等候空间、顾客放弃等待、故障,以及由相互关联的队列组成的网络。服务需求的波动性具有独立于其均值的影响。耗时较长或服务时间变化较大的作业可能增加其他作业的延误,因此需要采用不同的调度与资源池化策略。将多个队列合并为共享服务资源池,可以减少负载不均,但移动距离、专业分工和作业准备要求可能抵消这一收益。

应用领域包括联络中心、急诊科、维修设施、生产线和通信网络。人员配置问题往往将排队模型的估算结果与整数规划排班模型结合起来。然而,当需求快速变化时,例如早间高峰或短时突发急诊需求期间,稳态公式可能并不适用,此时时变分析和仿真就十分重要。排队模型还区分效率与体验:使平均延误最小的策略,可能导致不同顾客群体或作业类别之间的等待时间分配不均,因此优先级和服务标准也是问题建模时需要实质性考虑的内容。

仿真与计算实验

仿真用于描述系统在给定规则和输入下如何演变。当交互作用、随机性或非线性行为使直接分析变得困难时,仿真尤其有用。与优化不同,仿真通常是评估一项拟议策略,而不是自动找出最优策略。分析人员可以对医院收治策略、仓库布局或飞机过站作业流程进行仿真,在改变实际系统之前估计其后果。

在离散事件仿真中,系统状态在到达、服务完成、故障或补货等事件发生时改变。未来事件表决定下一个发生的事件,仿真时钟则直接推进到该事件发生的时刻。这样就不必对其间没有相关事件发生的每一时刻都进行计算。相比之下,连续仿真通常通过微分方程描述连续变化的状态;基于智能体的方法则刻画相互作用的个体,由个体遵循的局部规则产生整体行为。

随机抽样将仿真与蒙特卡洛方法联系起来。通过生成随机变量来表示不确定的输入,再通过重复运行来估计性能指标。单次长时间运行并不一定等同于多次独立重复运行。初始化效应、序列相关性和稀有事件都可能使估计失真。对于旨在表示稳态运行的系统,可能需要剔除初始预热期;而对于有明确终止时点的系统,例如以一个营业日为限的系统,初始状态可能本身就是研究问题的一部分,而非人为设置造成的干扰。

比较备选方案时,统计试验设计十分重要。如果不同策略的结果对共同的随机因素有相似反应,那么在各策略中使用共同随机数,就能降低策略间差异估计值的变异性。置信区间应反映实际的依赖结构和重复试验设计。从许多含有随机误差的估计结果中选出表面上最优的策略,也会引入选择效应:胜出策略的排名可能部分归因于对其有利的随机波动。追加独立试验,可以更可信地估计其性能。

仿真优化将仿真嵌入搜索过程。候选决策通过仿真得到的性能进行评估,搜索过程则在各备选方案之间分配计算资源。所用方法涵盖响应面模型、随机逼近、专门的排序与选择程序,以及无导数优化等。仿真的计算成本较高时,就需要在探索更多策略与更精确地估计每项策略的性能之间进行权衡。

模型的可信度与统计精度仍是两个不同的问题。如果仿真不符合实际,即使估计值的区间很窄,也仍会产生误导。模型验证可以比较事件序列、队列分布、资源利用率,以及系统对已知历史扰动的响应。当运行规则或人的行为发生变化时,仿真模型也可能过时。模型的实验结果以所建模的机制、输入分布和适应规则为前提,并非对组织必然如何运作的普遍预测。

动态规划与序贯控制

有些决策的影响主要体现在它们如何改变未来的选择空间。更换机器会改变未来的故障风险;接受预订会占用容量,而这些容量日后可能以更高的价格售出;今天蓄水则会影响未来的发电量。动态规划将这类序贯问题分解为多个阶段,并根据未来的后果来表述当前决策,从而求解问题。

状态概括了后续决策所需的信息。在时刻 tt,行动 ata_t 按照某种转移规则改变状态,该规则可能涉及随机扰动。有限时域最小化问题可以用贝尔曼方程表示:

Vt(s)=min⁡a∈At(s){ct(s,a)+E ⁣[Vt+1(St+1)∣s,a]}.V_t(s)= \min_{a\in A_t(s)} \left\{ c_t(s,a)+ \mathbb{E}\!\left[V_{t+1}(S_{t+1})\mid s,a\right] \right\}.

终端价值 VTV_T 规定了规划期结束时剩余的成本或价值。随后,通过逆向递推计算更早各期的价值函数。关键在于恰当地表示系统,使过去的历史仅通过当前状态影响未来的可能性。

马尔可夫决策过程用状态、行动、转移概率以及收益或成本,将这一框架形式化。无限时域问题可以以最大化折扣收益或最小化长期平均成本为目标。价值迭代反复应用贝尔曼算子,而策略迭代则交替进行策略评估和策略改进。收敛条件取决于折扣机制、状态与行动空间以及常返性质等因素。

这种方法在计算上的主要障碍是维数灾难。如果一个状态要记录多种产品的库存、机器状况、尚未完成的订单以及天气信息,可能的状态组合数量就会极其庞大,此时精确枚举便不切实际。近似动态规划采用表达能力受限的价值函数表示、状态聚合、转移采样或策略近似。这些方法以牺牲精确性来换取计算上的可处理性,评估时必须考虑近似误差对实际运营造成的影响。

动态规划与强化学习关系密切。经典动态规划通常假定转移模型已知,而强化学习则侧重于在模型未知或仅部分已知时,通过交互或数据学习有效的行为方式。这一区别并非绝对:基于模型的学习与基于仿真的动态规划存在广泛交集。实际运营应用还会引入一般性的收益最大化目标可能忽略的约束,包括服务保障、物理限制,以及成本高昂或不安全的试验。当观测无法揭示真实状态时,可能需要采用部分可观测马尔可夫决策过程,以状态上的信念分布作为决策依据,而非仅依赖直接观测到的状态。

库存、补货与收益管理

库存理论研究应持有多少库存以及何时补货。库存可以缓冲供需不匹配,但也会占用资金,并可能产生仓储、变质或过时成本。库存过少则会导致缺货、销售损失、停产或服务延误。适用何种模型,取决于需求是否已知、缺货需求是延期交付还是直接流失、补货提前期具有怎样的特性,以及多种物品是否共用容量。

一个基础性的确定性模型是经济订货批量,其源头可追溯至福特·惠特曼·哈里斯于1913年的研究。若需求以恒定速率 DD 发生,每次订货产生固定成本 KK,每单位的年库存持有成本为 hh,则相关的年度成本为

C(Q)=KDQ+hQ2.C(Q)=\frac{KD}{Q}+\frac{hQ}{2}.

使成本最小的订货批量为

Q∗=2KDh.Q^*=\sqrt{\frac{2KD}{h}}.

这一公式在频繁小批量订货与低频大批量订货之间取得平衡。它是否有用,取决于其假设是否成立,包括需求恒定、补货方式符合模型设定,以及不存在与订货数量有关的复杂因素。它并不能确定需求不确定时所需的安全库存。

对于单一销售期,报童模型在超储成本与缺货成本之间进行权衡。若需求的累积分布函数为 FF,缺货成本为 CuC_u,超储成本为 CoC_o,则在标准假设下,最优订货量满足

F(Q∗)=CuCu+Co.F(Q^*)=\frac{C_u}{C_u+C_o}.

因此,适宜的需求分位数由库存过剩与短缺的经济后果决定,而不能仅根据平均需求确定。同一模型结构也可用于描述季节性商品、易腐商品,或在需求明朗之前就必须预先投入的容量。

反复补货需要考虑提前期,以及随系统状态变化的订货决策。补足水平策略将库存位置提高到目标水平,而 (s,S)(s,S) 策略则在库存位置降至或低于 ss 时订货,将其恢复至 SS。库存位置通常等于现有库存加上在途订货量,再减去欠交订单量。在多级库存系统中,各节点的库存决策通过上游供应和下游服务相互影响,因此,对各节点分别进行独立优化,可能导致缓冲库存配置不当。

收益管理研究一类相关问题,其中的容量通常固定,且具有时效性。飞机座位或酒店客房在航班起飞或服务日期过后,就会失去销售机会。相关策略可以调整价格、限制可售数量,或为后续需求预留容量。接受一项需求的机会成本,取决于它所占用容量的未来价值。超额预订还需权衡容量闲置的损失与到场顾客超过接待能力所带来的后果。需求估计之所以困难,是因为销售记录受可售容量限制而存在截尾,同时又受到以往价格的影响,因此,统计估计与运营控制之间的相互作用尤为重要。

调度、指派与项目协调

调度理论研究如何在时间维度上将活动分配给资源。调度问题需要明确作业或任务、加工要求、资源可用情况,以及优先关系、释放时间或截止期限等约束。目标可以包括最小化总完成时间、最大延误、加权拖期、准备成本,或最后一个作业的完成时间,即最大完工时间。即使作业和机器完全相同,不同的目标也可能使最优调度方案截然不同。

一些简单情形揭示了有用的原则。在单机环境中,如果所有作业在初始时刻均已就绪,且不允许抢占,那么按加工时间从短到长排序,可以使完成时间之和最小。在作业权重均为正且满足相应假设的情况下,按加工时间与权重之比从小到大排序,可以使加权完成时间之和最小。在基本的单机环境中,按交期从早到晚排序,可以使最大延误最小。这些结果并非普适的派工规则:释放时间、与加工顺序有关的准备作业、多台机器或其他约束,都可能使这些规则不再具有最优性。

制造业中的调度结构更为复杂。在流水车间中,各作业按相同的机器顺序加工;在作业车间中,不同作业则可能遵循不同的加工路线。资源约束与优先关系相互影响,一台机器上的决策也会影响其他环节何时有作业可供加工。医疗和交通运输领域还涉及技能要求、法律规定的工作时段、作业时长的不确定性,以及连续性要求。例如,护士排班必须体现各时段的人员覆盖、资质、休息时间和合同规定,而不能只是为每天分配一个人数。

项目调度侧重于由相互依赖的活动构成的网络。关键路径法出现于20世纪50年代末,而计划评审技术则是为美国海军的“北极星”项目开发的。在活动持续时间固定、资源不受约束的基本优先关系网络中,最长路径决定了项目最早能够完成的时间。相对于这一完工目标,关键路径上的活动没有调度余量。然而,一旦引入数量有限的作业班组或设备,资源受限项目调度问题所需的决策就不再只是计算最长路径。

求解方法可以采用混合整数规划、专门的调度算法或约束规划。约束规划尤其擅长表达逻辑关系与时间关系,包括共用同一资源的活动不得在时间上重叠等约束。大型实际调度方案通常将精确方法与启发式方法、滚动修订相结合。鲁棒性十分重要,因为安排过于紧凑的调度方案可能很脆弱:微小的延误就可能沿着衔接关系和共享资源传播。因此,缓冲时间的设置、恢复方案以及重新调度的成本,可能与名义上的效率同样重要。调度方案不仅是一张静态时间表,也是应对各种扰动的管理框架。

策略互动与多重目标

并非每个运筹学问题都由单一决策者掌控所有相关行动。竞争对手会调整价格,供应商会对合同作出反应,出行者会选择路线,员工也会对激励作出回应。博弈论对这类策略互动进行建模。此时,决策的结果不仅取决于不确定的外部条件,还取决于追求各自目标的其他参与者。若将他们的行为视为固定参数,提出的建议可能一经实施就不再奏效。

在零和博弈中,一方的收益就是另一方的损失。有限双人零和博弈与线性规划密切相关:混合策略和博弈值可以通过原问题与对偶问题的形式计算得出。更一般的情形则使用纳什均衡等概念;在纳什均衡下,给定其他参与者的策略,任何参与者都无法通过单方面改变策略来提高自身收益。均衡未必具有社会效率,也未必唯一或容易达成。它描述的是个体激励之间的一种相容条件,而非由中央决策者选定的最优解。

交通拥堵就是一个具体例子。出行者各自选择最快的路线,所形成的路网流量分布,可能不同于使总出行时间最短的分布。增加通行能力也可能以出人意料的方式改变路线选择。企业共用物流基础设施、医院争夺专业人员,或发电企业在市场中竞价时,也会出现类似问题。优化方法仍然适用,但模型必须区分集中控制与分散响应。激励设计和合同设计可以力求使个体选择与更广泛的系统目标保持一致。

即使只有一个决策主体,通常也会同时存在多个目标。交通管理机构可能既关注成本和出行时间,也关注排放、可靠性以及不同地区的交通可达性。多目标优化用于识别这些评价标准之间的权衡。如果不存在任何可行的替代方案,能够在不使至少一个其他目标变差的前提下改善某个目标,那么该解就具有帕累托效率。这些解构成一条前沿,而不是一个天然应当优先选择的唯一答案。

加权和将多个目标合并为一个数值指标,但其含义取决于计量单位、尺度处理以及权重是否有合理依据。在非凸问题中,加权和法还可能无法求得某些具有帕累托效率的解。其他方法包括:对除一个目标之外的所有目标设定界限,按字典序确定优先级,或采用基于目标值的建模形式。但无论采用哪种方法,都无法免去对优先事项作出实质性取舍的必要。

决策理论有助于形式化描述对不确定结果的偏好,而决策分析则可以系统梳理备选方案、后果和信息需求。这些方法能够澄清假设,却不能把存在争议的社会价值观转化为纯粹的技术事实。在集体决策情境中,由谁设定权重、衡量哪些结果,以及受影响群体是否有代表参与,本身就是决策问题的组成部分。

计算架构与实际部署

运筹学在实践中能够发挥多大作用,既取决于数学理论,也取决于计算工作的组织方式。用于生产运行的模型通常要经过数据提取、一致性检查、模型构建、求解器执行、解的验证,以及将结果转化为操作指令等环节。任何一个环节出现问题,都可能使原本正确的优化方法失效。例如,求解器可能生成一份数学上可行、却无法导入调度系统的排程;模型也可能使用在解发布时就已过时的库存数据。

大型问题往往具有可利用的结构。雅克·本德斯于1962年提出的本德斯分解,将某些使问题复杂化的决策与子问题分离,再将这些子问题的信息反馈给主问题。列生成则从一个有限的变量集合出发,在新增变量能够改善解时引入这些变量。在乘务排班中,每一种符合规定的潜在工作安排都可以视为一列;这类安排的数量可能极其庞大,无法逐一显式列出。定价子问题负责寻找有价值的新列。

分解方法也能体现组织结构。多区域供应问题可以自然地按情景、地点或时段拆分,并通过协调约束确保各部分遵守共享产能限制。并行计算可以加快其中一些计算,但通信开销、内存限制以及子问题之间的依赖关系会制约加速效果。数值实现需要注意尺度调整和数值稳定性。逻辑建模中使用的极大常数、近乎冗余的约束,以及尺度失衡的系数,都可能削弱界的质量,或使可行性判断变得不可靠。

实际运行系统通常采用滚动时域规划:对未来一段时间建立模型并求解,只执行近期决策;待新信息到来后,再次求解模型。这种方式能够适应需求变化和突发扰动,但如果每次重新优化都大幅修改先前的计划,也可能造成不稳定。设置变更惩罚、冻结某些时段的决策,以及明确必须履行的承诺,有助于在适应性与可预测性之间取得平衡。实时应用还可能需要一套快速的备用策略,以便在主优化流程超时或遇到无效数据时使用。

模型部署时,需要报告的不只是目标函数值。用户需要知道模型是否找到了可行解、是否已证明最优性、哪些约束处于紧约束状态,以及哪些假设决定了推荐方案。即使混合整数求解因时限而终止,只要清楚区分当前最佳可行解与界,结果仍然可能有用。监测应同时跟踪计算指标和实际运行结果。设备、客户行为、合同规则或数据定义的变化,都可能使先前成功的模型失效,因此,维护和定期重新建模始终是分析系统不可缺少的工作。

应用领域、证据与问责

运筹学广泛应用于物流领域,其中设施选址、库存、运输和调度决策构成一个相互关联的系统。设施选址决定应在何处配置产能,以及如何分配需求。长期网络设计与日常调度有所不同,但两者相互影响:仓库位置会影响可实现的配送时效、车队需求,以及应对中断的韧性。综合研究必须选择恰当的细化程度,既能反映这些相互作用,又不至于把日常运营中的每一种突发情况都纳入战略模型。

在能源领域,优化方法为发电调度、检修规划、燃料分配和投资分析提供支持。机组组合模型在考虑启动成本、最短运行时间和容量限制的基础上,决定哪些发电机组应在何时运行。经济调度则在可用机组之间分配出力。可再生能源发电增加了不确定性,也使储能、备用容量和输电变得更加重要。电网模型必须遵循网络的物理规律并满足运行安全要求;对于许多电力决策,简单地类比货物流动并不足够。

在卫生系统中的应用包括人员配置、手术室排程、急救服务布点、诊断能力配置和物资配送。这些场景兼具需求不确定、服务要求各异和资源约束严格等特点。数学模型可以比较不同的容量配置方案或估计拥堵程度,但结论取决于行政管理数据的质量,以及模型涵盖了哪些结果指标。利用率的提高不等于服务各个维度的改善,而从历史数据中观察到的规律,也不能自动揭示拟议干预措施的效果。

运筹学与数据科学和机器学习的关系日益重要。预测模型估计需求、故障风险或出行时间;决策优化模型则利用这些估计来选择行动。预测更准确,并不总能带来更好的决策,因为不同误差会产生不同的运营后果。低估高峰需求所造成的成本,可能远高于在低谷时段出现同等幅度误差所造成的成本。反过来,某些预测误差对决策的影响也可能相对较小。因此,评估应将预测准确性与实际目标及约束联系起来。

运营改善的证据可以来自历史数据回放、受控部署、仿真或精心设计的比较。每种方法都有局限性。历史数据反映的是以往政策的影响,而实施新方案可能改变行为,使原先假定的投入与结果之间的关系不再成立。声称节省了成本,需要有明确的比较基准、统一的核算口径,并关注是否有成本被转移到系统的其他部分。

当模型用于分配负担、准入机会或稀缺服务时,就会产生问责问题。约束条件可以体现法律义务和服务标准,但仅凭优化本身无法推断公平性。审计记录、对假设的书面说明、对数据隐私的适当保护,以及人工复核程序,都能使模型建议接受审查。目标函数只计入明确纳入其中的后果;即使计算所得的解是最优解,建模时遗漏的影响也依然真实存在。