多目标目标规划
- 提出者
- Charnes, A. and Cooper, W. W.
- 年份
- 1961
- 类型
- Mathematical programming / multi-criteria optimization
- 类别
- Simulation / optimization
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
多目标目标规划(Multi-Objective Goal Programming, MOGP)是一种数学规划技术,它通过最小化各目标加权偏差的总和来同时追求多个期望目标。MOGP 源于 Charnes 和 Cooper(1961)提出的目标规划框架,并将其扩展以处理多个相互竞争的目标,这使其在运筹学、供应链设计、资源分配和政策分析等领域不可或缺,因为在这些领域,决策者必须同时满足——或尽可能接近——多个冲突的要求。
方法背后的直觉
设想一位管理者必须同时实现利润目标、控制碳排放预算并使员工加班时间低于某个阈值。单纯的优化只能一次优化一个目标,而将其他目标视为硬约束可能会导致不可行。目标规划将每个目标重构为一个“期望”,并最小化解决方案在达到(或超出)每个期望方面的偏差。多目标变体对所有目标的偏差进行加权,并找到最佳的可行折衷方案——这很像在景观中寻找一个同时最接近几个山顶的点。
历史学
目标规划由 Charnes 和 Cooper 于 1961 年提出,作为线性规划的扩展,通过期望水平来处理多个目标。Ijiri(1965)形式化了字典序变体,Lee(1972)将其整合为管理科学应用方法。多目标(向量)公式通过 Tamiz、Jones 和 Romero 在 20 世纪 90 年代的工作而兴起,如今 MOGP 已成为运筹学课程和应用优化中的标准工具。
何时使用
当决策问题涉及多个可量化、可能相互冲突的目标,并且决策者能够为每个目标表达期望水平时,应使用 MOGP。它特别适用于资源分配、投资组合选择、生产计划和环境政策等领域,这些领域需要在追求多个目标的同时保持可行性。当利益相关者倾向于“要达到的目标”而非“要最大化的目标”时,应优先考虑 MOGP 而非纯粹的多目标优化。当目标无法量化为定量目标、问题本质上是非线性的且缺乏可用求解器、无法证明基数权重合理性或需要严格的帕累托前沿分析(无目标锚定)时,则不应使用。
局限与注意事项
- 需要从决策者那里获取目标(期望)水平和权重,这可能具有主观性和政治争议性。
- 解决方案对所选权重敏感;不同的权重方案可能产生显著不同的结果。
- 标准的线性 GP 假设凸性;非凸或组合问题需要专门的求解器,并且可能在计算上非常密集。
- 不保证帕累托最优——如果目标和权重指定不当,GP 解决方案可能会被支配。
- 不具有可比性的目标尺度需要归一化,这可能会引入进一步的主观选择。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 在单个可处理的优化模型中自然地处理多个冲突目标。
- 灵活的成就函数——加权、字典序或 min-max 变体——可适应不同的利益相关者偏好结构。
- 产生一个单一的推荐解决方案,而不是一个大的帕累托集,简化了决策者的沟通。
- 可扩展到整数、二进制或非线性公式,涵盖广泛的现实世界问题。
- 对权重和期望水平的敏感性分析很直接,揭示了解决方案对偏好变化的稳健性。
应用
- 供应链网络设计,平衡成本、服务水平和碳足迹目标。
- 医院资源分配,同时满足人员配备、床位占用率和预算目标。
- 农业规划,在固定土地约束下优化作物产量、用水量和经济回报。
- 金融投资组合选择,满足回报、风险和流动性期望水平。
- 能源政策建模,在可再生能源容量、电网可靠性和投资成本之间进行权衡。
- 大学课程调度,尊重教师负荷、教室容量和学生偏好目标。
使用方式
使用方式
确定所有 K 个目标,并为每个目标函数 f_k(x) 设定期望水平 g_k。目标可以反映利润目标、成本上限、环境配额或服务水平要求。决定对于每个目标,是过度达成、未达成还是两者都有偏差是不可取的。
为每个目标 k 引入非负偏差变量 d_k^+(过度达成)和 d_k^-(未达成),使得 f_k(x) + d_k^- - d_k^+ = g_k。这些变量量化了解决方案与每个期望水平的差距。
公式
d_k^+ = \max(f_k(x) - g_k, 0), \quad d_k^- = \max(g_k - f_k(x), 0)
构建成就(目标)函数,作为偏差变量的加权和:min Z = sum_k (w_k^+ * d_k^+ + w_k^- * d_k^-)。权重 w_k 反映了实现每个目标的相对重要性。或者,可以使用字典序优先级排序来代替权重,以实现严格的优先级结构。
公式
\min \; Z = \sum_{k=1}^{K} (w_k^+ d_k^+ + w_k^- d_k^-)使用标准求解器求解由此产生的线性(或非线性)规划。根据敏感性分析或利益相关者反馈调整目标水平和权重,并重新求解以探索决策空间并理解目标之间的权衡。
检查最终的偏差值,以确定哪些目标已完全实现(d_k^+ = d_k^- = 0),哪些目标存在剩余偏差。向决策者展示帕累托最优前沿或成就图,以供最终选择和论证。
常见陷阱
- 设定不切实际的期望水平可能导致所有目标同时无法实现,从而导致每个目标都有很大的偏差和一个无信息量的解决方案。
- 忽略了不期望的过度达成和不期望的未达成之间的区别(例如,将超额利润视为问题)会导致偏差惩罚的错误设定。
- 在没有归一化的情况下合并具有非常不同单位或量级的目标会导致成就函数被数值较大的目标所支配。
- 将 GP 输出视为最终答案而不进行敏感性分析,可能会忽略权重不确定性对所选解决方案的影响。
常见问题
MOGP 与标准多目标优化有何不同?
标准多目标优化在不固定目标的情况下寻求完整的帕累托前沿,而 MOGP 将每个目标锚定在特定的期望水平,并最小化与这些水平的偏差,从而产生一个与既定目标一致的单一折衷解决方案。
加权目标规划与字典序目标规划有何区别?
加权 GP 将所有偏差变量合并为一个加权总和,权衡各个目标。字典序 GP 将目标分层排序,并按顺序优化每个层级,从不牺牲更高优先级的目标来换取较低优先级的目标。
MOGP 能处理非线性目标函数吗?
可以,但计算成本会增加。非线性 MOGP 需要非线性求解器,且不再保证凸性,因此可能无法保证全局最优性。线性化或分段近似是常见的解决方法。
如何确定目标权重?
权重应反映决策者的偏好,可以通过直接评分、成对比较(AHP)或试错敏感性分析来获取。权重选择的透明度对于利益相关者的接受至关重要。
目标规划的解决方案总是帕累托最优的吗?
不一定。加权 GP 的解决方案可能是弱帕累托最优但不是严格最优,特别是当某些权重为零时。建议的做法是为所有偏差使用正权重并检查被支配的解决方案。
相关方法
参考文献
Charnes, A., Cooper, W. W. (1961). Management Models and Industrial Applications of Linear Programming. Wiley, New York.
ISBN:978-0471148258已复制。Jones, D., Tamiz, M. (2010). Practical Goal Programming. Springer, New York.
打开 DOI 文献已复制。