多目标线性规划 (MOLP)
- 提出者
- Steuer, R. E.; Charnes, A.; Cooper, W. W.
- 年份
- 1955–1986
- 类型
- Mathematical optimization / vector optimization
- 类别
- Simulation / optimization
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
多目标线性规划 (MOLP) 将经典线性规划扩展到能够同时处理多个相互冲突的线性目标函数,其可行域由线性约束定义。MOLP 不产生单一的最优解,而是生成一个帕累托最优前沿(Pareto-efficient frontier),决策者从中选择一个偏好的权衡方案。它在运筹学和管理科学中是资源分配、规划和具有竞争性目标的工程设计问题的基础。
方法背后的直觉
在普通的线性规划中,您要最小化一个成本或最大化一个利润,但实际决策几乎总是涉及多个相互竞争的目标——例如,在最小化排放的同时最小化成本并最大化服务水平。MOLP 承认没有一个单一的解决方案能在所有目标上同时达到最优。它描绘了非支配(帕累托最优)解的完整前沿,其中改进一个目标必然会恶化另一个目标。然后,决策者使用偏好信息——权重、期望水平或交互式查询——从该前沿中选择最终解决方案,使权衡显性化,而不是隐藏在复合分数中。
历史学
多目标线性规划的理论基础可以追溯到 1950 年代 Charnes 和 Cooper 在目标规划方面的工作以及 Koopmans 在有效生产方面的工作。Steuer 1986 年的教科书整合了该领域,系统化了加权和法、ε-约束法和交互式方法,这些方法至今仍是标准。MOLP 现在是世界范围内运筹学课程的核心主题。
何时使用
当问题具有多个相互竞争的线性目标和线性约束,数据是连续且精确已知的(或可视为确定性的),并且决策者需要明确理解权衡而不是接受预先聚合的分数时,应使用 MOLP。典型场景包括生产规划、投资组合分配、运输路线规划和公共资源预算。当目标或约束是非线性的(应使用多目标非线性规划或元启发式方法代替)、数据是离散或二元的(应使用多目标整数规划)、目标数量超过五六个(有效前沿在计算上变得难以处理)或决策者不愿参与迭代偏好征询时,请勿使用。
局限与注意事项
- 仅限于线性目标函数和线性约束;现实世界的问题通常是非线性的。
- 有效前沿在高维空间中可能包含指数级数量的极端点,使得全面枚举不切实际。
- 需要精确的数值数据;系数中的不确定性或模糊性不能被原生处理。
- 交互式方法在很大程度上依赖于决策者的可用性和一致表达偏好的能力。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 生成完整的帕累托最优前沿,为决策者提供权衡的完整图景。
- 通过基于单纯形求解器,对于中等规模问题在计算上是可行的。
- 保证有效前沿上每个点的数学最优性。
- 得到成熟软件(CPLEX、Gurobi、开源替代品)的良好支持。
- 权衡显性化,而不是折叠成一个不透明的复合指数。
应用
- 生产规划,平衡成本、吞吐量和资源利用率。
- 投资组合优化,权衡回报、风险和流动性。
- 运输和物流网络设计,具有竞争性的成本和服务目标。
- 能源系统规划,在满足排放和可靠性目标的同时最小化成本。
- 医疗资源分配,平衡公平性、效率和预算约束。
- 环境管理,同时优化经济和生态绩效。
使用方式
使用方式
构建 k 个线性目标函数 f1(x) 到 fk(x) 以及由线性不等式和等式约束(Ax <= b, x >= 0)定义的 ज्यात区域 X。确定哪些目标需要最小化,哪些需要最大化。确认所有目标函数和约束在决策变量中都是线性的。
公式
\min_{x \in X} \mathbf{f}(x) = (f_1(x), f_2(x), \ldots, f_k(x))^T \text{ s.t. } Ax \leq b,\; x \geq 0生成帕累托最优(非支配)解集。常用方法包括加权和法(在单纯形上变化权重)、ε-约束法(优化一个目标同时约束其他目标)和切比比雪夫法。每种方法都描绘了有效前沿的一部分或全部。
应用标量化技术将向量问题转化为一系列单目标线性规划问题。在加权和方法中,通过系统地改变权重向量来求解 min sum(wi * fi(x))。记录目标空间中每个有效的极端点。
公式
\min_{x \in X} \sum_{i=1}^{k} w_i f_i(x), \quad w_i \geq 0, \; \sum w_i = 1收集有效的极端点及其连接边以表征帕累托前沿。分析前沿上每个目标的范围,以理解权衡的幅度。通过表格或双目标图将前沿呈现给决策者。
与决策者互动以从有效集中选择一个偏好的解决方案。交互式方法(STEM、NIMBUS)在呈现解决方案和要求决策者表达偏好之间交替进行,最终收敛于一个最能反映其优先级的选择。
常见陷阱
- 在加权和标量化中使用固定权重并仅报告一个解决方案会模糊前沿并破坏 MOLP 的目的。
- 混淆帕累托最优与全局最优:前沿上的每个点都是帕累托最优的,但在没有偏好信息的情况下,没有一个点是全局“最佳”的。
- 忽略检查可行域是否是有界的;无界问题不会产生有限的有效集。
- 将 MOLP 作为黑箱处理而不让决策者参与选择会导致任意的最终选择。
- 将 MOLP 应用于本质上是整数的问题而不切换到多目标整数规划,会产生违反整数约束的解决方案。
常见问题
MOLP 与目标规划有何不同?
目标规划是一种特殊情况或变体:它将每个目标转换为一个期望水平,然后最小化与这些目标的偏差,从而产生一个单一的解决方案。MOLP 的一般形式旨在表征完整的有效前沿,而无需预先指定目标水平,从而为决策者提供更大的灵活性。
MOLP 能处理两个以上的目标吗?
是的,但帕累托前沿在超过两个或三个目标时变得更难可视化,并且有效极端点的数量可能呈指数级增长。对于四个或更多目标,建议使用交互式方法和代表性子集技术。
如果我的数据不确定怎么办?
标准的 MOLP 假定系数是确定性的。可以通过扩展到随机多目标线性规划(机会约束、基于场景的方法)或鲁棒多目标优化来解决不确定性问题,这些是独立的方法。
MOLP 与多目标优化是同一回事吗?
MOLP 是多目标优化的一个特例,其中所有目标和约束都是线性的。多目标优化是更广泛的领域,也包括非线性、整数和组合变体。
我应该使用哪种标量化方法?
加权和法很简单,但会遗漏前沿的非凸部分。ε-约束法即使对于非凸区域也能恢复完整前沿,并且通常更适合进行彻底分析。当可以进行决策者参与时,交互式方法效果最好。
相关方法
参考文献
Steuer, R. E. (1986). Multiple Criteria Optimization: Theory, Computation, and Application. John Wiley & Sons, New York.
ISBN:9780471888468已复制。Chankong, V., Haimes, Y. Y. (1983). Multiobjective Decision Making: Theory and Methodology. North-Holland, New York.
打开出版物文献已复制。