不确定优化问题的建模和处理方法.ppt

不确定优化问题的建模和处理方法 信息管理与信息系统系刘波 主要内容 不确定优化问题的来源及应用领域灵敏度分析随机规划模糊规划鲁棒优化智能优化算法 1 不确定优化问题的来源及应用领域 在运筹学 管理科学 信息科学 工业工程 航天技术以及军事等众多领域都存在人为的或客观的不确定性 表现形式也多种多样 如随机性 模糊性 粗糙性以及多重不确定性 辩证的看 不确定性是绝对的 确定性是相对的 所以 不确定性是系统的固有属性 对于任何一个组织或系统来说 对不确定性问题都是最为重要的任务之一 在决策制定领域 为了得到科学的决策结果 通常的做法是对决策问题进行抽象建模 然后采用相应优化手段进行求解 1 不确定优化问题的来源及应用领域 在传统的优化问题数学表达式中 优化模型的结构和参数是确定的 但是 在实际当中 不确定性无处不在 其不确定因素主要来源于 1 系统内部潜在的本质决定的不确定性 2 对于系统的实际机理不可能完全了解 3 模型建立前收集数据时 数据采集 包括数据测量和数据统计预处理 过程中不可避免的存在测量工具和测量本身的误差或错误 4 对模型的简化处理 比如用一个简单的模型来近似比较复杂的系统 5 影响所建模型的未来因素不确定 6 在计算过程中 对模型的离散化处理 7 解决方案付诸实际时 由于种种原因还需要不断的修正等 1 不确定优化问题的来源及应用领域 这些不确定因素可能对优化模型的结构和参数产生影响 从而使得优化模型的解不再满足约束条件 同样 优化模型的最优目标值也就不成立 因此 对于这些含有不确定性的决策优化问题 经典的优化理论通常是无能为力的 处理不确定优化问题的方法一般有 概率论与数理统计 可能性理论 模糊理论 灰集理论 粗糙集理论 区间代数 集对理论等 当然这些理论之间存在着互相交叉 选择何种方法取决于所能获得的信息和决策者的态度及目的 下面介绍几种常用的优化理论和方法 1 灵敏度分析 1 灵敏度分析的基本方法 灵敏度分析源于统计 预测 估计或假设等一些不确定的建模中 分析不确定性数据的变化给模型的输出带来的影响 在对线性规划进行灵敏度分析时 是在得到线性规划问题的最优解之后 对要研究这个问题中各个系数的单独变化对目前最优解的影响 1 灵敏度分析 1 灵敏度分析的基本方法 运用灵敏度分析 我们可以得到两方面的结论 一是数据的变化对最优解的影响 二是保持最优解不变时 各参数的变化范围 灵敏度分析主要依赖于线性规划的对偶特性 并且是分析部分参数变化时的情况 灵敏度分析是在优化计算已经完成 得到最优结果之后进行的 因此又被称为优化后分析 1 灵敏度分析 2 灵敏度分析的局限性 1 采用确定性的模型 即便是参数不能完全知道的时候 一般会采用最好的估计值 或者用均值 也就是说 实际上在建模时几乎不考虑不确定性的存在 2 在得到最优结果后进行分析 来确定不确定因素所带来的影响 从某种角度来说 属于一种被动的行为 因为并不在事先主动考虑不确定性 3 一般严格依赖于最优解 或者最优解的求解方法 1 随机规划 概率论和数理统计是处理不确定问题的常用理论工具 在处理优化问题的过程中 往往有一些参数以随机变量的形式出现在模型中 就形成了所谓的随机规划模型 建立模型的目的是要找出满足约束条件的 最好 解作为最终决策 但是 模型中不确定因素的存在 使得模型的数学定义变得不明确 因而对于 最好 解的选择不再是单纯的数学优化问题 还成为一种决策问题 决策者不同决策态度以及周围的一些环境因素将影响对结果的选择 而且一般这种定义不明确的模型需要转换成确定型模型 才能运用各种数学方法进行求解 1 随机规划 随机规划模型主要有以下几种类型 期望值模型 在期望约束下 使目标函数的期望值达到最优的数学规划 称为期望值模型 这种模型是随机规划中最为常见的形式 相对于原始模型 l 5 4 其期望值模型如下式 如果模型中的随机变量和决策变量呈线性关系 且相互独立 则模型可以简化 因此在实际使用中 我们经常直接以决策变量的期望值取代该随机参数直接建模 得到一种期望值意义下的确定性模型 1 随机规划 随机规划模型主要有以下几种类型 机会约束规划模型 机会约束规划又被称为概率规划 形式有很多 比如刘宝旋提出的Maximax机会约束规划 Minimax机会约束规划 及随机相关机会规划等 1 机会约束规划模型 随机规划 对于机会约束来说 计算是非常困难的 这是因为我们需要知道随机变量的概率密度函数以及反函数 而且不同的随机变量 随概率密度函数又是多种多样的 因此其计算的复杂性来自于 当用连续的概率分布函数来描述不确定性时需要复杂的组合技术和方法 这是制约随机模型应用的一个主要原因 当然 在工程上可以采用近似的方法 比如采用随机模拟的方法 但这样也将会增加计算的负担 1 模糊规划 与随机规划类似 模糊规划是另一类重要的解决不确定优化问题的方法 二者的区别在于对不确定因素的描述和建模方面 在随机规划中 不确定参数通过离散或连续的概率密度函数来描述 在模糊规划不确定参数被看作是模糊数 约束被当作模糊集合来处理 其中的一些约束允许被违背 并定义约束的满意度作为约束的隶属函数 1 鲁棒优化 鲁棒优化是不确定优化研究中的一个新的研究主题 它源自鲁棒控制 应用领域非常广泛 鲁棒优化作为一个含有不确定输入的优化问题的建模方法 是随机规划和灵敏度分析的补充替换 其目的是寻求一个对于所有不确定输入都有良好性能的解 该方法不同于随机规划 鲁棒优化对不确定参数没有分布假定 每个可能的值都同等重要 当面向最坏情况时 它代表着一个保守的解 1 鲁棒优化是在不确定环境下研究系统结构内部的参数变化以及外部环境有扰动变量的条件下 如何对系统进行优化的方法 针对系统内部结构的变动 鲁棒优化主要解决约束条件与目标函数的参数的不确定性 对于外部环境的变化 主要处理外界产生的不确定性扰动 鲁棒优化所研究的问题中 不确定性参数的概率分布函数是未知的 用区间 以及相应的集合等来描述不确定参数的变动范围 由于在很多的情况下 参数微小的变化就会严重影响最优解的最优性 甚至使得其最优解不可行 为了使约束条件对所有合理的数据取值都保持可行性 鲁棒优化的目的是找到一个近似最优解 使它对任意的不确定性参数的观测值都不敏感 其最大特点是在考虑了不确定性参数值实现后不同目标函数值之间的差异 而不仅仅是强调数学期望值 因此 鲁棒优化不仅继承了随机规划的优点 而且具有更强的实用性 鲁棒优化 1 鲁棒优化 模糊规划与随机规划是两类重要的处理不确定问题的优化方法 两者的主要区别在于对不确定参数的描述以及建模方法的不同 模糊规划将不确定参数看作是模糊数 将约束当做模糊集来对待 而随机规划 则是把不确定参数描述为离散或者连续的概率密度函数来处理 以上不确定问题优化方法在考虑何时不确定因素对优化产生影响的时机上有所区别 灵敏度分析是在得到最优解之后 属于事后分析 而模糊规划 随机规划以及鲁棒优化则均属于事前分析方法 它们的不同在于 模糊规划需要建立隶属度函数 随机规划需要已知参数的概率分布 鲁棒优化不需要考虑不确定参数的分布 使用更广 更符合实际情况 1 鲁棒优化 通过对不确定优化方法对比 鲁棒优化适合应用于以下情形 1 不确定优化问题的参数需要估计 但是有估计风险 2 优化模型中不确定参数的任何实现都要满足约束函数 3 目标函数或者优化解对于优化模型的参数扰动非常敏感 4 决策者不能承担低概率事件发生后所