现代化方法讲座第2讲

第二部分双层规划 BiLevelProgramming 现代优化方法讲座 教学内容 双层规划的基本概念 基本模型 求解的复杂性双层规划的求解方法双层规划的应用 网络设计 旅客票价 选址问题等 教学重点 双层规划的基本特点和基本模型双层规划的应用 现代优化方法讲座 层次性是系统的六大特征之一 社会 不断发展 实际问题 规模越来越大 结构越来越复杂 进行决策的人也越来越多 而且这些决策者各自处于不同的层次上 一般 高一级决策机构 者 对下一级决策机构 者 行使某种控制 引导权 而下一级决策机构 者 在这一前提下 亦可以在其管理职责范围内行使一定的决策权 但这种决策权处于从属地位 2 1双层规划简介 现代优化方法讲座 另外 在这种多层次决策系统中 每一级都有自身的目标函数 高层机构的决策目标 重要 权威 具有全局性 最终的决策结果往往是寻求使各层决策机构之间达到某种协调的具体方案 2 1双层规划简介 既可使最高层决策机构的目标达到 最优 也可使作为上级决策 约束 的较低层决策机构的目标在从属位置上相应达到 最优 一般称具有以上基本特征的决策问题为主从递阶 或多层 决策问题 主从递阶决策问题最初是由VonStackelberg于1952年在研究市场经济问题时提出的 因此此问题有时候也称为Stackelberg问题 是一对策论问题 决策者有上下层关系和不同目标 但策略集通常是彼此分离 现代优化方法讲座 20世纪60年代 Dantzig和Wolfe提出了大规模线性规划的分解算法 相当于承认有一个核心决策者 他的目标高于一切 其他各层次的决策者实现自己的目标只不过是为实现核心决策者的目标的一种分工 现在的多层规划承认有最高决策者 但允许下层决策者有各自不同的利益 现代优化方法讲座 20世纪70年代发展起来的多目标规划通常是寻求一个决策者的互相矛盾的多个目标的折衷解 有些技术 如分层优化 也可用来求层次问题 但下层决策不影响上层 可以逐层独立求解 而当前的多层规划正是要强调下层决策对上层目标的影响 因此多层规划问题通常不能逐层独立求解 现代优化方法讲座 20世纪70年代以来 人们在各种现实的层次分散系统优化决策问题的研究中 遇到了用上述方法不能解决的实际问题 开始寻找各种特定的方法解决这些问题 逐渐形成了多层规划的概念和方法 如 Cassidy 1971 的政府政策效力分析 Kyland 1975 的经济层次分析 Bracken 1973 1977 等人的战备武器配置研究 Candler和Norton 1977 的奶制品工业模型和墨西哥农业模型等 现代优化方法讲座 多层规划 MultilevelProgramming 一词就是Candler和Norton在其论文中提出的 它的原意是一组嵌套着的数学规划问题 即在约束条件中含有优化问题的数学规划 20世纪80年代至今 多层规划的数学模型更加明确和形式化了 国内外学者也发表了许多有意义的成果 现代优化方法讲座 总之 在过去20年中 多层规划的理论 方法及应用都有很大发展 正在逐渐形成一个新的运筹学分支 目前 很多国家对多层规划的研究都非常重视 把它列为科学基金资助项目 并取得了巨大成功 现代优化方法讲座 最为常见且得到广泛研究与应用的多层规划是双层规划问题 即考虑只有两层决策者的情形 这是因为现实的决策系统大都可以看成双层决策 例如 中央和地方 公司和子公司 工厂的厂部和车间 高校的校部和院所等 实际上任何多层决策系统都是一系列双层决策系统的复合 现代优化方法讲座 双层规划是具有两个层次系统的规划与管理 控制 问题 很多决策问题由多个具有层次性的决策者组成 这些决策者具有相对的独立性 即是说上层决策只是通过自己的决策去指导 或引导 下层决策者 不直接干涉下层的决策 而下层决策者只需把上层的决策作为参数或约束 它可以在自己的可能范围内自由决策 现代优化方法讲座 如果组成这种上 下层关系不止一个时 这样的系统为多层决策系统 如果只有一个上 下层关系时 这样的系统通常称为双层规划问题 由此可见 双层规划问题虽然是多层决策系统的特殊形式 但它是最基本的形式 现代优化方法讲座 双层规划 双层规划是双层决策问题的数学模型 它是一种具有双层递阶结构的系统优化问题 上下层问题都有各自的目标函数和约束条件 上层问题的目标函数和约束条件不仅与上层决策变量有关 而且还依赖于下层问题的最优解 而下层问题的最优解又受上层决策变量的影响 现代优化方法讲座 双层规划的意义在于 可以同时考虑全局和个体双方的利益 并保证首先从全局出发 体现了顾全大局 先集体后个人的思想 目标是做到既不舍小家 又能顾大家 可以很好地解决许多实际问题 现代优化方法讲座 现代优化方法讲座 上层决策部门 决策变量 下层决策部门 决策变量 相互作用 上层给下层一定的信息 下层在这些信息下 按自己的利益或偏好做出反应 决策 上层再根据这些反应 做出符合全局利益的决策 双层规划决策过程 现代优化方法讲座 如果每个决策者都按规定的指标函数在其可能范围内做出决策 那么 双层决策系统可能描述为双层规划问题 如果每个决策者的指标函数由单个函数组成 这样的双层规划为双层单目标规划问题 如果有的决策者的指标函数是一组函数 这样的双层规划问题为双层多目标规划问题 2 2双层规划特点 现代优化方法讲座 双层规划问题一般具有如下几大特点 层次性 系统分层管理 下层服从上层 但下层有相对的自主权 举例说明 独立性 各层决策者各自控制一部分决策变量 以优化各自的目标 举例说明 冲突性 各层决策者有各自不同的目标 且这些目标往往是相互矛盾的 举例说明 2 2双层规划特点 现代优化方法讲座 优先性 上层决策者优先做出决策 下层决策者在优化自己的目标而选择策略时 不能改变上层的决策 举例说明 自主性 上层的决策可能影响下层的行为 因而部分地影响下层目标的实现 但上层不能完全控制下层的选择行为 在上层决策允许范围内 下层有自主决策权 举例说明 2 2双层规划特点 续 现代优化方法讲座 制约性 下层的决策不但决定着自身目标的实现 而且也影响上层目标的实现 因此上层在选择策略优化自己的目标时 必须考虑到下层可能采取的策略对自己的不利影响 举例说明 依赖性 各层决策者的容许策略集通常是不可分离的 形成一个相关联的整体 举例说明 2 3双层规划模型的基本形式 现代优化方法讲座 其中由下述规划求得 U L 上层决策者通过设置的值影响下层决策者 下层决策变量是上层决策变量的函数 即 这个函数一般被称为反应函数 一般来说 双层规划模型具有如下形式 2 3双层规划模型的基本形式 与一般的数学规划不同 即使当 和都是连续函数 并且上下层的约束集合有界闭的 也可能没有最优解 假设上层选择了点 那么下层面临的是以为参数的简单最小值最优化问题 在有些情况下 对固定的 下层对应的最优问题可能包含不止一个最优解 什么情况下会有这种问题 现代优化方法讲座 如 如果所有的函数都是线性的 很可能当 固定的下层问题的所有最优解组成一个集合 这意味着中的任何一点对下层是无差别的 但对上层的目标函数可能会有差别 上层最优解可能只在中某个特定点上达到 但是没有办法使下层更愿意选择该点 现代优化方法讲座 双层规划分类 线性双层规划 所有目标函数和约束全为线性函数非线性双层规划 上下层目标函数和约束中少有一个非线性函数相应的有整数线性双层规划 整数非线性双层规划等 关于双层规划的一些定义 现代优化方法讲座 记 BP 的约束域为 定义2 1对每个固定的 称为下层问题的可行解集合 为下层问题的合理反应集 在上层决策空间上的投影为 关于双层规划的一些定义 现代优化方法讲座 定义2 3如果存在 对任意的满足称是 BP 的全局最优解或最优解 定义2 2称为 BP 的可行解集合或诱导域 双层规划的一阶必要条件 现代优化方法讲座 设是双层规划的最优解 则其一阶必要条件为 1 都是一阶连续可微函数 2 对 下层问题有唯一解 3 存在 使得是下列问题的可行解 2 3双层规划的基本形式 现代优化方法讲座 例2 1 其中解 2 3双层规划的基本形式 现代优化方法讲座 该例的最优解在点D上达到 即 16 11 在点E 10 14 处 上层目标函数值更优 如果上层选择 下层选择 此时下层目标函数更优但上层则较差 点A 0 5 是问题的一个局部最优解 求解双层规划问题是非常困难的 原因 双层规划问题是一个NP hard问题 双层规划的非凸性 2 4双层规划计算复杂性 现代优化方法讲座 即使能找出双层问题的解 通常也只可能是局部最优解而非全局最优解 由于双层规划问题和博弈论具有一些类似的特性 因此可以利用博弈论中的一些方法来限定双层规划问题解的范围 在博弈论中 同两个选手分别控制各自的决策变量相比 如果一个选手能控制所有的决策变量 那么 这个选手就能更好的优化其自身的目标 现代优化方法讲座 2 4双层规划计算复杂性 现代优化方法讲座 2 4双层规划计算复杂性 其中由下述规划求得 U L 第一种情况 如果下列双层规划的最优解为 现代优化方法讲座 2 4双层规划计算复杂性 第二种情况 如果上层决策者控制所有变量 双层规划变为 设其最优解为 现代优化方法讲座 2 4双层规划计算复杂性 其中 第三种情况 如果上下层决策者分别独立控制各自的决策变量 双层规划变为 设其最优解为 现代优化方法讲座 2 4双层规划计算复杂性 那么有下式存在 除双层规划外 后两种情况都是求单层规划 较容易 因此可不直接求双层规划 而直接求后两类单层规划 然后尽量减小与 与之间的差异 当上层给定一个允许决策后 如果下层问题的最优解不唯一 将导致整个求解的复杂性 甚至无法保证能求得问题的最优解 2 5双层规划求解算法 现代优化方法讲座 对于双层规划是上层先进行决策 为了说明这种顺序的重要性 考虑下面的例子 其中求解 2 5双层规划求解算法 现代优化方法讲座 例2 3 2 5双层规划求解算法 现代优化方法讲座 值 值 同时决策 由表可以看出决策顺序很重要 如果控制变量的选手先决策 它的最小费用要比后选择策略或两选手同时决策要优 现代优化方法讲座 注意与多目标规划的区别 到目前为止 对于双层规划的求解算法归纳起来 可以分为五大类 2 5双层规划求解算法 现代优化方法讲座 1 极点搜索法 ExtremePointSearchMethod 这种方法主要用于求解双层线性规划 其基本观点就是 双层线性规划问题的任何解都出现在下层问题的约束集合的极点位置 因此 首先可以利用各种方法来寻找约束空间的极点 不要求寻找全部极点 然后从中再找出双层问题的局部最优解或全局最优解 2 5双层规划求解算法 现代优化方法讲座 2 K T法 Karush Kuhn TuckerMethod 简称K T法 这种方法将双层问题中的下层问题用它的Karush Kuhn Tucker条件代替 主要用于求解双层线性规划问题 最初用于求解双层线性资源控制问题 3 下降法 DescentMethod 这种方法是基于用各种可能的方法得到的下层问题对上层决策变量的梯度信息 主要用于求解非线性连续变量的双层规划问题 从本质上讲 这是一种迭代求解方法 利用得到的下层问题对上层决策变量的梯度信息来产生一系列使上层目标函数减小的点 最具代表性的下降算法是基于灵敏度分析的求解算法 现代优化方法讲座 2 5双层规划求解算法 4 直接搜索法 DirectSearchMethod 直接使目标函数最小的方法 如Abdulaal和LeBlanc 1979 使用的Hooke Jeeves搜索法就属于此类 在搜索解的过程中 这种方法取决于上层目标函数值的变化 现代优化方法讲座 2 5双层规划求解算法 5 非数值优化方法 这类方法主要包括模拟退火 遗传算法和蚁群算法等 这种非数值优化方法目前主要用来求解城市