专业学习|随机规划概观(内涵、分类以及例题分析)

时间:2024-09-30 16:05:10

一、随机规划概览

(一)随机规划的定义

        随机规划是通过考虑随机变量的不确定性来制定优化决策的一种方法。其基本思想是在决策过程中,目标函数和约束条件可以包含随机因素。

(1)重点

        随机规划的中心问题是选择参数,使收益的数学期望达到最大。随机规划实际上是给出了你考虑所有情形下的解。这些解的平均目标函数是达到了最大。

(2)随机规划的随机性

其中随机规划的随机性主要体现在:

  • 输入参数的不确定性:例如,需求量、生产成本、收益等都可能是随机变量。
  • 决策结果的随机性:由于外部环境的变化,决策结果可能受到多种随机因素的影响。

(3)随机规划案例

来源:初识随机规划:用一个小例子理解随机规划 - 知乎 (zhihu.com)

(二)随机规划的分类

(1)随机规划分类

  1. 阶段性随机规划

    • 适用于具有多个决策阶段的问题(例如,动态规划)。
  2. 单阶段随机规划

    • 所有决策在同一阶段进行,通常在决策时对未来的随机性进行汇总。
  3. 混合随机规划

    • 结合了上述两种形式,适用于复杂的问题。

(2)与鲁棒优化的联系和区别

   随机规划鲁棒优化都是运筹优化中比较高阶的内容。二者都是考虑不确定情形下的数学规划,但是两者又有不同。随机规划旨在优化不确定情形下的目标函数的期望,比如总收益的期望值等。但是鲁棒优化致力于使得最坏的情况最好。所以相比而言,基本的鲁棒优化获得的结果会比较保守。

(3)随机规划的分类

来源:[1]戎晓霞.不确定优化问题的若干模型与算法研究[D].山东大学,2005.

1)随机规划方法归类

2)方法解释和介绍

        灵敏度分析是在优化计算完成得到最优结果之后进行的因此又被称为优化后分析。

        期望值模型——在 期 望 约 束 下 使 目 标 函 数 的 期 望 值 达 到 最 优 的 数 学 规 划 称 为 期 望 值模 型 。这 种 模 型 是 随 机 规 划 中 最 为 常 见 的 形 式 。

        随机变量的概率 密度函数概率密度的组合以及反函数而且不同的随机变量随概率密度 函 数 又 是 多 种 多 样 的 因 此 其 计 算 的 复 杂 性 来 自 于 当 用 连 续 的 概 率 分 布 函 数 来描述不确定性时需要复杂的组合技术和方法。

        与随机规划类似 模糊规划是另一类重要的解决不确定优化问题的方 法。二者的区别在于对不确定因素的描述和建模方法。在随机规划中不确定参数通过离散或连续的概率密度函数来描述在模糊规划不确定参数被看 作是模糊数约束被当作模糊集合来处理。其中的一些约束允许被违背并 定义约束的满意度作为约束的隶属函数。

        近 年 来 所 提 出 的 鲁 棒 优 化 方 法 主 要 针 对 最 坏 情 形 利 用 一 目标 进 行 优 化 但 是 结 果 过 于 保 守 。后 来 研 究 的 重 点 在 于 如 何 降 低 解 的 保 守 性 。此 时 “ 鲁 棒 ” 的 含 义 是 模型对数据的不确定具有 免疫性。

        上述鲁棒优化的方法都存在共同的局限性 第一所考虑的不确定性只 考虑约束左端参数的变化 第二随机参数的分布是对称的而且没有利用 概率分布的信息 第三鲁棒性的提高是以标称问题的性能指标为代价的。

        多 目标 优 化。对存在不确定性的决策问题建立多目标模型的思想方法是 如果能在 给出决策解的最优程度的同时能给出不确定性因素的影响程度并能让决策 人在两者之间权衡那将为决策人对其决策优劣的可靠性和决策解的鲁棒性的了解及事先评价决策质量提供有效的支持。 郑 泳 凌 等 ’ 对 一 类 区 间 数 规 划 问 题 在 双 目标 规 划 的 基 础 上 提 出 了 三 目 标 规 划 的 解 决 方 法 三 个 目标 分 别 表 示 均 值 、 不 确 定 度 和 后 悔 度 。

        基于全局搜索的智能优化算法种类很多包括模拟退火 ‘一’ 、粒子群 算 法 ‘ 一‘ 、 蚁 群 算 法 【” ” 一‘川 、 遗 传 算 法 ’ 等 。 这 类 算 法 大 都 模 拟 生 物 的 进 化现象并采用 自然进化的机制来表现复杂现象的一种概率搜索方法。

        基于全局搜索的智能优化算法种类很多包括模拟退火 ‘一’ 、粒子群 算 法 ‘ 一‘ 、 蚁 群 算 法 【” ” 一‘川 、 遗 传 算 法 ’ 等 。 这 类 算 法 大 都 模 拟 生 物 的 进 化现象并采用 自然进化的机制来表现复杂现象的一种概率搜索方法

(三)随机规划的解题步骤

(1)求解步骤

  1. 模型构建

    • 确定决策变量、目标函数和约束条件,明确哪些是随机变量。
  2. 随机性描述

    • 使用概率分布函数描述随机变量的特性。
  3. 求解方法选择

    • 选择适合的求解方法,例如:Monte Carlo 方法、拉格朗日对偶法、随机线性规划等。
  4. 求解优化问题

    • 利用数学编程或其他数值方法求解模型。
  5. 结果分析与验证

    • 分析结果的稳定性和可行性,并进行敏感性分析。

(2)案例及python代码实现

        假设我们要为一个零售商制定库存管理策略,考虑到需求是随机的,可以用随机规划来优化库存水平,以最小化库存成本和缺货成本。

import numpy as np
from scipy.optimize import linprog

# 随机变量的参数
demand_mean = 100  # 需求的均值
demand_std = 20    # 需求的标准差

# 目标函数系数 (库存成本)
c = [2]  # 每单位库存成本

# 约束条件 (库存必须满足需求)
# 例如,设定一个库存水平
x0_bounds = (0, None)

# 随机需求生成 (这里假设需求服从正态分布)
np.random.seed(42)
random_demand = np.random.normal(demand_mean, demand_std, 1000)

# 约束条件,假设需要满足95%的需求
quantile_demand = np.percentile(random_demand, 95)

# 线性规划求解
res = linprog(c, A_ub=[[-1]], b_ub=[-quantile_demand], bounds=[x0_bounds], method='highs')

# 输出结果
if res.success:
    print(f'优化库存水平为: {res.x[0]:.2f},以满足95%的需求')
else:
    print('求解失败')

说明

  • 随机变量:需求量是随机变量,通过正态分布生成。

  • 优化目标:最小化库存成本,同时确保库存足够满足大部分需求。

二、一些常见的随机规划案例

(一)两阶段随机规划

(1)两阶段随机规划模型定义

        两阶段随机规划模型是随机规划的一个重要分支,它涉及在两个不同的决策阶段处理不确定性。这种模型特别适用于那些在项目或决策过程的不同时间点面临未知参数的情况。

1)模型结构
  1. 第一阶段决策:在初始阶段,决策者会根据当前信息做出一系列决策。这些决策是不可逆的,且通常在不确定性完全揭示之前做出。
  2. 随机参数的揭示:在第一阶段决策做出后,一些关键参数(如需求、成本等)的不确定性会逐步揭示。
  3. 第二阶段决策:基于随机参数的实际值,决策者会做出第二组决策,以优化最终结果。这些决策通常被认为是可调整或修正的。
2)特点
  • 顺序决策:决策分为两个阶段进行,每个阶段的决策都是基于当前可用信息的最优选择。
  • 适应性:第二阶段决策可以根据第一阶段之后揭示的不确定性进行调整。
3)相对于传统随机规划的改进

        传统的随机规划通常假设所有随机参数在做出决策之前就已知其概率分布。然而,两阶段随机规划模型提供了更实际的处理方式:

  1. 更贴近实际:许多实际情况下,不确定性是在决策过程中逐步揭示的,两阶段模型更准确地反映了这种现实。
  2. 灵活性:允许在获得更多信息后调整决策,提供了更大的灵活性和适应性。
  3. 风险管理:通过两阶段决策,可以更好地管理风险和不确定性。
4)解决的问题
  1. 逐步决策的需求:在不确定性完全揭示之前,可能需要做出初步决策。两阶段模型允许在信息更充分时做出修正。
  2. 动态规划问题:两阶段模型为动态规划问题提供了一种解决方案,使得决策可以随时间动态调整。
  3. 资源分配的优化:在供应链管理、金融投资等领域,两阶段模型帮助决策者在不确定性下更有效地分配资源。
5)应用示例
  1. 供应链管理:在产品需求不确定的情况下,第一阶段可能涉及购买原材料,第二阶段根据实际需求调整生产计划。
  2. 能源管理:在风力或太阳能发电中,第一阶段可能涉及承诺购买一定量的能源,第二阶段根据实际天气条件调整能源购买。

(2)两阶段随机规划案例

来源:初识随机规划 (2):两阶段随机规划(一个详细的例子)-****博客

(二)鲁棒优化模型

(1)两阶段鲁棒优化问题(Two-stage Robust Optimization)

    鲁棒优化旨在处理优化问题中参数不确定的挑战,致力于优化最坏情况(worst case)下的解,或者最坏参数分布下的解(对应分布式鲁棒优化),从而使最终得到的解具有非常强的抵抗不确定性或者风险的能力

两阶段鲁棒优化是一种用于解决不确定性问题的优化方法,它通过将决策过程分为两个阶段来处理不确定性。在第一阶段,决策者在面临不确定性的情况下做出初步决策;在第二阶段,基于实际观察到的不确定性结果进行调整。这种方法特别适合于那些不确定性在决策实施后才显现的场景。

1)鲁棒性方面
  1. 应对不确定性:能够有效应对输入参数的不确定性。
  2. 可行性保障:确保在所有可能的情况下解都是可行的,无论真实情况如何变化。
  3. 性能稳定性:在最坏情况下保持相对较好的性能,避免极端情况的影响。
2)分类

        两阶段鲁棒优化可以根据不确定性的信息类型、决策变量的性质等进行分类:

  1. 基于信息的分类

    • 完全信息模型:假设未来信息完全已知。
    • 不完全信息模型:不确定性以某种概率分布呈现。
  2. 基于决策变量的性质

    • 离散决策问题:决策变量为离散值。
    • 连续决策问题:决策变量为连续值。
3)求解步骤
  1. 建立模型:明确目标函数和约束条件,识别不确定性参数。
  2. 分阶段决策
    • 第一阶段:制定初步决策(如选择方案)。
    • 第二阶段:针对第一阶段决策,在不确定性场景下优化调整。
  3. 求解优化问题:使用适当的算法或工具求解得到最优解。
  4. 敏感性分析:分析模型对不确定性变化的敏感性,从而评估鲁棒性。

(2)案例及代码实现

        以供应链管理中的库存决策为例,企业需要在面对需求不确定性的情况下制定采购策略。通过两阶段鲁棒优化,可以实现以下目标:

  • 第一步骤制定一个安全库存水平;
  • 第二步根据实际需求调整订单量,以降低库存成本和缺货风险。
import pulp

# 创建问题
problem = pulp.LpProblem("Two-Stage_Robust_Optimization", pulp.LpMinimize)

# 定义决策变量
x1 = pulp.LpVariable("x1", lowBound=0)  # 第一阶段决策
y1 = pulp.LpVariable("y1", lowBound=0)  # 第二阶段调整决策

# 定义目标函数
problem += 5 * x1 + 2 * y1, "Total Cost"

# 定义约束条件
problem += x1 + y1 >= 10, "Demand Constraint"
problem += x1 <= 20, "Stock Limit"

# 求解问题
problem.solve()

# 输出结果
print(f"Optimal Solution: x1 = {x1.varValue}, y1 = {y1.varValue}")
print(f"Total Cost = {pulp.value(problem.objective)}")
  • 在此示例中,x1代表第一阶段的决策,y1代表在观察到实际需求后所作的调整。
  • 目标函数是要最小化总成本,同时满足需求约束。

三、补充知识

(一)蒙特卡洛

常用 的方法是蒙特卡洛模拟 ( 也称随机模拟法) , 该方法通过对刻画收益情景的生成模型进行蒙特卡洛模拟来产生随机情景。 首先根据历史统计分布、 或某个特定 的概率分布或者随机过程建立随机变量的概率模 型 , 然后利用 计算机的 随机数程序多 次模拟随机变量 出 现的 累计概率, 再根据 已经建立 的概率模型获得随机变量各种可能值的计算机模拟值, 再不断地经过多 次、 反复无重复 的抽样模拟仿真, 以数量或者是精度为 标准, 尽可能的模拟随机变量所有的可能值, 最 后统计分析模拟的结果, 整理分析所确定的随机变量参数值的特征值。 在实际应用 中 , 对所生成的随机数序列进行统计检验可以避免 “ 伪随机数” 的发生, 例如均值检验、 标 准差检验 , 分布检验和相 关性检验等 , 当 所生成 的 随机数通过检验 时 , 就基本可 以 认为 它们具有了统计意义上的随机性, 进而可以作为 “ 真正” 的随机数使用。

(二)情景生成方法

        当 随机情景生成后 , 需要选择有代表的情景进行概率分配构建情景树, 即情景树上少数的节点要代表不确定性在不同阶段的可能值, 通常采用 的方法有:

        (1) 随机抽样法

随机抽样法就是在大量经济元素中 , 按照情景数的要求随机抽取经济元素, 构成情 景树的决策节点, 举例说明 , 如果构造的情景树在第一阶段决策节点有 个, 我们可 以在用蒙特卡罗模拟出 的 “ 真正” 随机数中抽取独立的 个结果向量, 并设定每个情 景发生的概率相同 即可。 情景树的第二阶段的节点仍可使用 随机抽样的方法, 值得注意 的是 , 后阶段的条件分布依赖于前一阶段的情景值。