《双层规划》PPT课件

《《双层规划》PPT课件》由会员分享，可在线阅读，更多相关《《双层规划》PPT课件（32页珍藏版）》请在装配图网上搜索。

1、 Bi-Level Programming 最 为 常 见 且 得 到 广 泛 研 究 与 应 用 的 多 层 规 划 是双 层 规 划 问 题 ， 即 考 虑 只 有 两 层 决 策 者 的 情 形 。 这 是 因 为 现 实 的 决 策 系 统 大 都 可 以 看 成 双 层 决 策 。 例 如 ： 中 央 和 地 方 ， 公 司 和 子 公 司 ， 工 厂 的 厂部 和 车 间 ， 高 校 的 校 部 和 院 所 等 。 实 际 上 任 何 多层 决 策 系 统 都 是 一 系 列 双 层 决 策 系 统 的 复 合 。 双 层 规 划 ：双 层 规 划 是 双 层 决 策 问 题 的

2、数 学 模 型 ， 它 是 一种 具 有 双 层 递 阶 结 构 的 系 统 优 化 问 题 ， 上 下 层问 题 都 有 各 自 的 目 标 函 数 和 约 束 条 件 。 上 层 问题 的 目 标 函 数 和 约 束 条 件 不 仅 与 上 层 决 策 变 量有 关 ， 而 且 还 依 赖 于 下 层 问 题 的 最 优 解 ， 而 下层 问 题 的 最 优 解 又 受 上 层 决 策 变 量 的 影 响 。 二 、 双 层 规 划 的 特 点双 层 规 划 问 题 一 般 具 有 如 下 几 大 特 点 ：层 次 性 系 统 分 层 管 理 ， 下 层 服 从 上 层 ， 但下 层 有

3、相 对 的 自 主 权 （ 举 例 说 明 ） 。独 立 性 各 层 决 策 者 各 自 控 制 一 部 分 决 策 变量 ， 以 优 化 各 自 的 目 标 （ 举 例 说 明 ） 。冲 突 性 各 层 决 策 者 有 各 自 不 同 的 目 标 ， 且这 些 目 标 往 往 是 相 互 矛 盾 的 （ 举 例 说 明 ） 。 优 先 性 上 层 决 策 者 优 先 做 出 决 策 ， 下 层决 策 者 在 优 化 自 己 的 目 标 而 选 择 策 略 时 ， 不能 改 变 上 层 的 决 策 （ 举 例 说 明 ） 。自 主 性 上 层 的 决 策 可 能 影 响 下 层 的 行 为 ，

4、因 而 部 分 地 影 响 下 层 目 标 的 实 现 ， 但 上 层 不能 完 全 控 制 下 层 的 选 择 行 为 ， 在 上 层 决 策 允许 范 围 内 ， 下 层 有 自 主 决 策 权 （ 举 例 说 明 ） 。 制 约 性 下 层 的 决 策 不 但 决 定 着 自 身 目 标的 实 现 ， 而 且 也 影 响 上 层 目 标 的 实 现 ， 因 此上 层 在 选 择 策 略 优 化 自 己 的 目 标 时 ， 必 须 考虑 到 下 层 可 能 采 取 的 策 略 对 自 己 的 不 利 影 响（ 举 例 说 明 ） 。依 赖 性 各 层 决 策 者 的 容 许 策 略 集 通

5、 常 是不 可 分 离 的 ， 形 成 一 个 相 关 联 的 整 体 （ 举 例说 明 ） 。 三 、 双 层 规 划 模 型 的 基 本 形 式其 中 由 下 述 规 划 求 得)(xyy ),(min yxx F 0yxG ),(.ts（ U） ),(min yx y f 0yxg ),(.ts（ L） 上 层 决 策 者 通 过 设 置 的 值 影 响 下 层 决策 者 。 下 层 决 策 变 量 是 上 层 决 策 变 量 的 函数 ， 即 ,这 个 函 数 一 般 被 称为 反 应 函 数 。x y)(xyy o 一 般 来 说 ， 双 层 规 划 模 型 具 有 如 下 形 式

6、与 一 般 的 数 学 规 划 不 同 ， 即 使 当 和 都 是 连 续 函 数 ， 并 且 上 下 层 的 约 束 集 合 是 有界 闭 的 ， 双 层 规 划 也 可 能 没 有 最 优 解 。GfF ,假 设 上 层 选 择 了 点 ， 那 么 下 层 面 临 的 是 以 为 参 数 的 简 单 最 小 值 最 优 化 问 题 。 在 有 些 情况 下 ， 对 固 定 的 ， 下 层 对 应 的 最 优 问 题 可 能包 含 不 止 一 个 最 优 解 。xx x g 什 么 情 况 下 会 有这 种 问 题 ？ ？ 如 ： 如 果 所 有 的 函 数 都 是 线 性 的 ， 很 可

7、能 当 固 定 的 下 层 问 题 的 所 有 最 优 解 组 成 一 个集 ， 这 意 味 着 中 的 任 何 一 点 对 下 层 是无 差 别 的 ， 但 对 上 层 的 目 标 函 数 可 能 会 有 差 别 。上 层 最 优 解 可 能 只 在 中 某 个 特 定 点 上 达 到 ，但 是 没 有 办 法 使 下 层 更 愿 意 选 择 该 点 。 XX )(xy )(xy )(xy 线 性 ， 就 是 指 y=ax+b这 种 形 式 ， 往 往 指 的 就是 一 次 。线 性 问 题 ， 往 往 是 比 较 “ 良 好 ” 的 问 题 ， 因为 它 们 形 式 简 单 ， 易 求 解

8、 。 如 果 有 误 差 ， 因为 是 线 性 的 缘 故 也 比 较 容 易 估 计 。 常 见 的 线性 问 题 有 匀 速 直 线 运 动 、 商 品 折 扣 等 。非 线 性 ， 就 是 指 并 非 一 次 的 其 他 情 况 。 o 双 层 规 划 分 类 线 性 双 层 规 划 ： 所 有 目 标 函 数 和 约 束 全 为 线 性 函 数非 线 性 双 层 规 划 ： 上 下 层 目 标 函 数 和 约 束 中 至 少 有 一 个 非 线 性 函 数相 应 的 有 整 数 线 性 双 层 规 划 、 整 数 非 线 性 双 层规 划 等 求 解 双 层 规 划 问 题 是 非 常

9、 困 难 的 。 原 因 : 双 层 规 划 问 题 是 一 个 NP-hard （ non-deterministic polynomial， 缩 写 NP） 问 题 。 双 层 规 划 的 非 凸 性 。四 、 双 层 规 划 计 算 的 复 杂 性即 使 能 找 出 双 层 问题 的 解 ， 通 常 也 只可 能 是 局 部 最 优 解而 非 全 局 最 优 解 。？ NP-hard，其中的NP是指非确定性多项式（non-deterministic polynomial，缩写NP）。所谓的非确定性是指，可用一定数量的运算去解决多项式时间内可解决的问题。 NP 问题通俗来说是其解的正确性能

10、够被“很容易检查”的问题，这里“很容易检查”指的是存在一个多项式检查算法。例如，著名的推销员旅行问题（Travel Saleman Problem or TSP）：假设一个推销员需要从香港出发，经过广州，北京，上海，等 n 个城市， 最后返回香港。 任意两个城市之间都有飞机直达，但票价不等。假设公司只给报销 C 元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 C？ 推销员旅行问题显然是 NP 的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于 C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排！ 这将是个天文数字。旅行推销

11、员问题是数学图论中最著名的问题之一，即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds，Cook和Karp等人发现，这批难题有一个值得注意的性质，对其中一个问题存在有效算法时，每个问题都会有有效算法。 迄今为止，这类问题中没有一个找到有效算法。倾向于接受NP完全问题（NP-Complet或NPC）和NP难题（NP-Hard或NPH）不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法。此类问题中，经典的还有 子集和问题； Hamilton回路问题 问 题 的 复 杂 性 ： 是 指 这 个

12、 问 题 本 身 的 复 杂 程 度 ，是 问 题 的 性 质 。 算 法 的 复 杂 性 ： 是 指 解 决 问 题 的 一 个 具 体 的 算法 的 执 行 时 间 ， 是 算 法 的 性 质 。问 题 抽 象 简 化 判 定 性 问 题四 、 双 层 规 划 计 算 的 复 杂 性只需回答yes or no 例 如 ： 求 从 A到 B的 最 短 路 径 ， 可 转 化 成 ：从 A到 B是 否 有 长 度 为 1的 路 径 ？ 从 A到 B是 否 有长 度 为 2的 路 径 ？ ，从 A到 B是 否 有 长 度 为 k的路 径 ？ 如 果 问 到 了 k的 时 候 回 答 了 yes，

13、 则 停 止发 问 ， 我 们 可 以 说 从 A到 B的 最 短 路 径 就 是 k。四 、 双 层 规 划 计 算 的 复 杂 性 四 、 双 层 规 划 计 算 的 复 杂 性 (a) (b) (c) (d) (e) 定 义 : 若 函 数 图 形 上 任 意 两 点 的 连 线 段 必 在 函数 图 形 的 上 方 (下 方 )， 则 称 该 函 数 为 凸 函 数 (凹函 数 )。数 学 表 达 式 定 义 为 ： 函 数 f(X)， 对 任 意 不 相 等的 X1， X2 (a,b), 以 及 (0, 1)， 有 f X 1+(1- )X2 f(X1)+(1- )f(X2) , 则

14、 f(x)称 作 凸 函 数 。 四 、 双 层 规 划 计 算 的 复 杂 性 其 中 由 下 述 规 划 求 得)(xyy ),(min yxx F 0yxG ),(.ts（ U） ),(min yx y f 0yxg ),(.ts（ L） 第 一 种 情 况 ：如 果 下 列 双 层 规 划 的 最 优 解 为 ),( *1*1 yx 第 二 种 情 况 ：如 果 上 层 决 策 者 控 制 所 有 变 量 ， 双 层 规 划 变 为),(min, yxyx F 0yxG ),( 0yxg ),(.ts 2* 2*( , )x y设 其 最 优 解 为 其 中),(min yx x F

15、0yxG ),(.ts ),(min yxy f 0yxg ),(.ts第 三 种 情 况 ：如 果 上 下 层 决 策 者 分 别 独 立 控 制 各 自 的 决 策 变量 ， 双 层 规 划 变 为 3* 3*( , )x y设 其 最 优 解 为那 么 有 下 式 存 在 ： 有 下 式 存 在 ： ),( *2*2 yxF ),( *1*1 yxF ),( *3*3 yxF除 双 层 规 划 外 ， 后 两 种 情 况 都 是 求 单 层 规 划 ， 较容 易 ， 因 此 可 不 直 接 求 双 层 规 划 ， 而 直 接 求 后 两类 单 层 规 划 ， 然 后 尽 量 减 小 与

16、， 与 之 间 的 差 异 。 ),( *1*1 yxF),( *2*2 yxF),( *1*1 yxF),( *3*3 yxF 其中 解对 上 述 问 题 ， 当 时 ， 由 ， 得 。 当 取 时 ， 下 层 问 题 的 最 优 目 标 函 数 值 ， 但 下 层 问 题 的 最 优 解 不 唯 一 ， 满 足 ， 显然 这 对 上 层 目 标 函 数 产 生 影 响 。 当 时 ， ； 当 时 ， 。 21min yyxF .ts 10 x 21,yy21min yyf 121 yyx 0, 21 yy.ts 10 x 1yx 12 y 1 xf5.0 x 5.01min xf 21 y

17、y 5.01 xF )0,5.0(),( 21 yy 0F)5.0,0(),( 21 yy 1F 上 述 例 子 说 明 ：当 上 层 给 定 一 个 允 许 决 策 后 ， 如 果 下 层 问 题 的最 优 解 不 唯 一 ， 将 导 致 整 个 求 解 的 复 杂 性 ， 甚至 无 法 保 证 能 求 得 问 题 的 最 优 解 。 在 交 通 领 域 中 的 应 用 在 管 理 中 的 应 用 资 源 分 配 价 格 问 题 供 应 链 管 理 生 产 计 划 其 它 方 面五 、 双 层 规 划 的 应 用 六 、 双 层 规 划 求 解 算 法一 、 极 点 搜 索 法 （ Extr

18、eme Point Search Method） ：n 用 于 求 解 双 层 线 性 规 划 。n 基 本 观 点 ： 双 层 线 性 规 划 问 题 的 任 何 解 都 出 现在 下 层 问 题 的 约 束 集 合 的 极 点 位 置 。 因 此 ， 首 先可 以 利 用 各 种 方 法 来 寻 找 约 束 空 间 的 极 点 （ 不 要求 寻 找 全 部 极 点 ） ， 然 后 从 中 再 找 出 双 层 问 题 的局 部 最 优 解 或 全 局 最 优 解 。 二 、 下 降 法 （ Descent Method） ：n 主 要 用 于 求 解 非 线 性 连 续 变 量 的 双 层

19、规 划 问 题n 最 具 代 表 性 的 下 降 算 法 ： 基 于 灵 敏 度 分 析 的 求解 算 法 。 三 、 K-T法 （ Karush-Kuhn-Tucker Method） ：这 种 方 法 将 双 层 问 题 中 的 下 层 问 题 用 它 的 Karush-Kuhn-Tucker条 件 代 替 ， 主 要 用 于 求 解 双 层 线 性 规 划问 题 ， 最 初 用 于 求 解 双 层 线 性 资 源 控 制 问 题 。四 、 直 接 搜 索 法 （ Direct Search Method） ：直 接 使 目 标 函 数 最 小 的 方 法 ， 如 Abdulaal和 Le

20、Blanc（ 1979） 使 用 的 Hooke-Jeeves搜 索 法 就 属 于 此 类 ， 在搜 索 解 的 过 程 中 ， 这 种 方 法 取 决 于 上 层 目 标 函 数 值 的变 化 。 五 、 非 数 值 优 化 方 法 （ Non-numerical optimization） 这 类 方 法 主 要 包 括 模 拟 退 火 、 遗 传 算 法 和 蚁 群 算 法 等 。这 种 非 数 值 优 化 方 法 目 前 主 要 用 来 求 解 城 市 交 通 连 续 平 衡网 络 设 计 问 题 （ Cree和 Masher， 1998） 及 其 它 相 关 优 化 问题 例 1

21、, 其 中 解 yxF 5min .ts 0 x yyf min.ts 102 yx 62 yx 212 yx 382 yx 182 yx 0y B(8,1) C(12,3) D(16,11)E(10,14)F(0,9)A(0,5) x y S 该 例 的 最 优 解 在 点 D上 达 到 ，即 =(16,11)， 在 点 E(10,14)处 ， 上 层 目 标函 数 值 更 优 ， 如 果 上 层 选择 ， 下 层 选择 ， 此 时 下 层 目 标函 数 更 优 但 上 层 则 较 差 。 点A(0,5)是 问 题 的 一 个 局 部 最优 解 。 ),( * yx 11,39 * fF 10 x 2y