《现代优化技术-靳志宏》第2讲：现代优化技术基础之数学基础.ppt

现代优化技术 第2讲 现代优化技术基础之数学基础 第2讲 主要内容 高等数学基础运筹学基础 高等数学基础集合 排列与组合凸集 凸函数凸组合 凸规划 运筹学基础穷举法 分枝定界法 动态规划法 高等数学基础 基本概念 高等数学基础 基本概念 高等数学基础 基本概念 高等数学基础 基本概念 凸组合 凸组合性质 高等数学基础 基本概念 高等数学基础 基本概念 高等数学基础 基本概念 高等数学基础 基本性质 高等数学基础 基本性质 高等数学基础 基本概念 高等数学基础 基本性质 高等数学基础 基本性质 凸规划例 凸可行域 高等数学基础 基本性质 凸规划例 凸目标函数 高等数学基础 基本性质 高等数学基础 基本概念 非凸规划 高等数学基础 基本性质 非凸规划 高等数学基础 基本性质 非凸规划 高等数学基础 基本性质 非凸规划 运筹学基础 运筹学的方法论基础 穷举法 完全枚举法 列举树法 分枝定界法 分支限定法 B B法 动态规划法 运筹学基础 列举树法 现实中的问题 例 旅行商问题 欧洲7日游 现在的位置 瑞士的苏黎士下一步要观光去的地方 西班牙的马德里 英国的伦敦 意大利的罗马 德国的柏林 目的地 返回苏黎士 问题 以怎样的顺序观光 旅行的总距离最短 运筹学基础 列举树法 现实中的问题 各都市间的距离 miles B 784 852 774 1154 434 894 736 408 569 476 L Z M R 列举树法 现实中的问题 运筹学基础 B R L R B B L R L B R L B L R M B R M R B B M R M B R M B B R L B L M L B B M L M B L M B M L R R L M L R R M L M R L M R M L B Z 3047 3047 3407 3485 3485 3596 3297 3497 3407 3825 4034 3256 3297 3784 4034 3674 3825 3584 3297 3674 3784 3497 3256 3596 旅行商问题的列举树 列举树法 现实中的问题 运筹学基础 Zurich Z Rome R Madrid M London L Berlin B 434 852 784 569 408 巡回路 可行解 3047 目标函数值 总距離最小的旅行路线 最优巡回路 最优解 最优解 之一 列举树法 理论升华 运筹学基础 列举树法 理论升华 运筹学基础 列举树法 理论升华 运筹学基础 资金预算问题的列举树 列举树法 理论升华 运筹学基础 资金预算问题的列举树 分枝定界法 现实中的问题 运筹学基础 例 背包问题制约条件 背包的容量目标函数 背走尽可能高价值的东西 分枝定界法 现实中的问题 运筹学基础 分枝定界法 不是生成所有可能的分枝 仅仅取其中的一部分探索效率高分枝操作 branch 基本上与列举树的生成操作相同 限定操作 bound 对列举树上的某点以后没有必要再进行探索判断依据 探索时点的目标函数的上下界值 分枝定界法 现实中的问题 运筹学基础 分枝操作 黒点表示背包无法容纳 非可行解 每一步都分两种情形考虑 背走极小熊 放弃极小熊 背走小熊 背走中熊 背走大熊 决策点 放弃小熊 放弃中熊 放弃大熊 分枝定界法 现实中的问题 运筹学基础 定界操作 上界与下界值的利用 下界值及其作用 因为背包問題是极大值問題 任一可行解都是其下界值 例如 仅仅背走小熊时背包完全可以容纳 因而是可行解 小熊的价值为19万元 故其现时点的下界为19 上界值及其作用 有必要导入背包问题的松弛问题 分枝定界法 现实中的问题 运筹学基础 背包問題的松弛问题 取而代之为线性制約 线性松弛 线性松弛问题的最优解可能不是整数 可以解释为将物品分解后背走也行 背包問題的线性松弛問題可以用贪婪算法求得最优解 即根据単位重量的价值vi si大小順序装包 分枝定界法 现实中的问题 运筹学基础 线性松弛问题的最优解 背包问题的上界值 単位重量的价值 8 6 333 5 75 5 6 以此顺序装包 最优値 16 19 23 2 46 5 分枝定界法 现实中的问题 运筹学基础 分枝定界法的探索原理 如某一探索时点的上界 如放弃极小熊时为42万 小于某一个可行解 背走大熊和极小熊时的44万 时 从该点以后没有必要再探索下去 分枝定界法 现实中的问题 运筹学基础 分枝定界法的探索效率 2 取决于分枝方法 分枝原则 例如 以熊的重量从小到大的顺序分枝 其他的分枝方法有 以熊的重量从大到小的顺序 以熊的价值从大到小的顺序 以 价值 重量 从大到小的顺序 取决于下界及上界的强度 松弛问题的上界 最小化问题是下界 近似解法所取得的下界 最小化问题是上界 的及早获取 3 取决于分枝点的选取顺序 分枝子问题优先原则 如从具有较大上界的点开始分枝 该点下存在较好解的可能性大 分枝定界法 理论升华 运筹学基础 分枝定界法 理论升华 运筹学基础 分枝定界法 理论升华 运筹学基础 分枝定界法 理论升华 运筹学基础 分枝定界法 理论升华 运筹学基础 分枝定界法 理论升华 运筹学基础 分枝定界法 理论升华 运筹学基础 分枝定界法 理论升华 运筹学基础 分枝定界法 理论升华 运筹学基础 分枝定界法 理论升华 运筹学基础 分枝定界法总结 动态规划法 现实中的问题 运筹学基础 小熊有4种每种有大量库存 满足背包的重量制約条件的前提下 带走尽可能高价值的物品 动态规划法 现实问题 运筹学基础 背包的重量上限 使 分别以0 1 7的順序計算 物品的种类集合N 极小 小 中 大 物品种类i的重量si 其价值vi重量上限为 时的最优値 现时点背包内价值的合計 f 对于函数f 以下的等式成立 Bellman方程式 重量上限 的最优値 上限为 si时的最优値 物品i的价值 动态规划法 现实中的问题 运筹学基础 整数背包问题的动态规划法 动态规划法 现实中的问题 运筹学基础 最优解的最短路图 各点表示可能的 值的状態 某一状態 点 和别的状態 点 之间的连线为枝枝上的数字表示状态之间变化所增加的背包内物品的价值 下图为状态从0至7的最短路图解 动态规划法 现实中的问题 运筹学基础 仅以背包的重量 来表现状態有缺陷 内装的物品种类及数量无法表现 内装的物品1 k種时的最优値f k Bellman方程式 内装物品为k个 且重量上限 时的最优値 带上第k个物品时