Skip to content
返回搜索结果

随机目标规划——在不确定性下优化多个目标

提出者
Contini, B. (building on Charnes & Cooper's chance-constrained programming)
年份
1968
类型
Stochastic multi-goal optimization
类别
Simulation / optimization

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

随机目标规划(SGP)扩展了经典目标规划,以处理目标值、约束系数或右侧参数中的不确定性。通过纳入概率约束和随机目标分量,它能在可接受的概率水平下找到满足多个目标的解决方案,适用于数据固有不确定或可变的决策问题。

方法背后的直觉

经典目标规划问道:我们能否同时接近每个目标?随机目标规划也问同样的问题,但承认世界是不确定的——目标可能转移,资源可能变化,数据可能存在噪声。SGP不为单一固定情景进行优化,而是寻求在期望中表现良好或以指定概率满足每个目标的解决方案。可以将其视为在诚实考虑你不知道的情况下制定最佳可能计划。

历史学

目标规划由Charnes和Cooper在20世纪50年代末提出。Contini(1968)利用机会约束规划的思想将其正式扩展到随机环境。随后的几十年里,其在金融、农业和公共政策领域的应用不断增长。该方法通过与20世纪90年代和2000年代发展的鲁棒优化相关的联系,获得了进一步的理论基础。

何时使用

当决策问题具有多个冲突目标时,至少一些参数(需求、成本、产量)是不确定的并且可以由概率分布表征,并且决策者需要以置信水平而非最坏情况界限表示的保证时,使用随机目标规划。它非常适合供应链规划、医疗资源分配、具有多个目标的金融投资组合管理以及天气不确定性下的农业规划。当目标真正不可衡量且无法加权时,当没有可用的分布信息时(使用鲁棒优化代替),当问题只有一个目标时(使用随机规划),或者当情景数量如此之大以至于确定性等价重构变得难以处理时,请勿使用它。

局限与注意事项

  • 需要了解分布参数(均值、方差),这些参数可能难以准确估计。
  • 非正态分布或联合机会约束可能导致确定性重构难以处理,需要基于情景或模拟的方法。
  • 置信水平alpha_i和目标权重w_i的选择本质上是主观的,并且可能强烈影响结果。
  • 与确定性目标规划相比,计算成本更高,特别是对于大规模或非线性问题。
  • 对非技术利益相关者来说,理解概率目标之间的权衡可能很困难。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 在单一优化框架内同时处理多个冲突目标。
  • 允许明确指定每个目标或约束的可接受风险水平(置信度)。
  • 在正态分布假设下,机会约束可以简化为可处理的二阶锥约束,并可用标准求解器求解。
  • 为决策者提供目标实现概率,提供比单一情景解决方案更丰富的信息。
  • 包含确定性目标规划作为特例(置信水平=1,参数固定)。
  • 理论基础扎实,与机会约束规划和鲁棒优化文献相关。

应用

  • 农业规划:在降雨和价格不确定的条件下,在作物之间分配土地和资源。
  • 医疗资源分配:在患者需求不确定的情况下,在满足服务水平目标的同时安排人员和床位。
  • 供应链管理:在产量、交货时间和需求不确定的情况下进行生产和库存规划。
  • 具有多个目标(回报、风险、流动性)的金融投资组合优化,应对市场不确定性。
  • 能源系统规划:在可再生能源发电不确定的情况下,平衡成本、可靠性和排放目标。
  • 市政预算:在收入和支出不确定的情况下,在各部门之间分配公共资金。

使用方式

使用方式

1

定义决策变量、多个期望目标(目标值)以及任何硬约束。每个目标i表示为:f_i(x) + d_i^- - d_i^+ = g_i,其中d_i^-和d_i^+是从目标g_i产生的负偏差变量和正偏差变量。分配反映实现每个目标相对重要性的优先级权重。

2

确定哪些参数是不确定的:目标值g_i、约束系数或目标函数系数可以建模为具有已知或估计分布(例如,正态分布、均匀分布、经验分布)的随机变量。根据历史数据或专家判断指定分布假设。

3

将不确定约束转换为机会(概率)约束。对于涉及随机参数b_i且具有分布F的随机约束,要求P(g_i(x) <= b_i) >= alpha_i,其中alpha_i是用户指定的置信水平(例如,0.90或0.95)。在正态分布假设下,这些可以重新表述为确定性的二阶锥约束。

公式
P(g_i(x) \leq b_i) \geq \alpha_i
4

求解由此产生的(可能已重新表述的)优化问题:最小化偏差的加权和 min sum_i (w_i^+ d_i^+ + w_i^- d_i^-),约束条件为机会约束的确定性等价形式以及任何剩余的硬约束。根据问题结构使用LP、MILP或非线性求解器。

公式
\min \sum_{i} (w_i^+ d_i^+ + w_i^- d_i^-)
5

通过检查目标实现水平、约束满足概率以及对分布假设的敏感性来评估解决方案。通过抽样参数实现进行事后蒙特卡洛验证,以在模拟情景中验证解决方案是否在规定的置信水平下满足目标。

常见陷阱

  • 在没有经验验证的情况下假设不确定参数的正态性可能产生误导性的置信度保证。
  • 设置过高的置信水平(例如,0.999)会有效地将模型简化为保守的确定性公式,从而违背了随机建模的目的。
  • 将机会约束目标规划与鲁棒目标规划混淆——两者处理不确定性的方式不同,不能互换。
  • 未能通过蒙特卡洛模拟验证随机解决方案,会使目标违背的实际风险未知。
  • 忽略不确定参数之间的相关性可能导致不可行或过于乐观的解决方案。

常见问题

随机目标规划与经典目标规划有何不同?

经典目标规划假设所有参数(目标、约束、成本)都确定已知。随机目标规划允许某些参数为随机变量,并包含概率约束,要求目标以指定的置信水平而非精确满足。

最常用的分布假设是什么?

正态分布是最常见的假设,因为它允许机会约束精确地重新表述为确定性的二阶锥约束。当数据表明非正态分布时,则使用基于情景或模拟的方法。

如何为每个机会约束选择置信水平alpha_i?

置信水平反映了决策者对每个目标的风险承受能力。实践中常用0.90-0.95的值。更高的值会使问题更保守,并可能需要放松其他目标;较低的值允许更多风险,但可能导致不可接受的结果。

随机目标规划能否处理整数决策变量?

可以。当与整数变量结合时,问题就变成了随机整数目标规划,其求解难度更大,但对于中等规模的实例,使用带有机会约束重构的分支定界法仍然是可行的。

当存在不确定参数时,我应该使用随机目标规划还是鲁棒优化?

如果您拥有可靠的分布信息并想要概率保证,SGP是合适的。如果您只知道不确定性集(边界)并想要在没有分布假设的情况下获得最坏情况保证,鲁棒优化更好。当两者都可行时,比较两种方法的解决方案是良好的实践。

相关方法

参考文献

  1. Contini, B. (1968). A stochastic approach to goal programming. Operations Research, 16(3), 576–586.

    打开 DOI 文献
    已复制。
  2. Charnes, A., Cooper, W. W. (1959). Chance-constrained programming. Management Science, 6(1), 73–79.

    打开 DOI 文献
    已复制。