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

1、现代优化技术,第2讲：现代优化技术基础之数学基础,第2讲：主要内容,高等数学 基础 运筹学 基础,高等数学基础 集合、排列与组合 凸集、凸函数 凸组合、凸规划 运筹学基础 穷举法、分枝定界法、 动态规划法、 ,高等数学基础,基本概念,高等数学基础,基本概念,高等数学基础,基本概念,高等数学基础,基本概念,凸组合,凸组合性质,高等数学基础,基本概念,高等数学基础,基本概念,高等数学基础,基本概念,高等数学基础,基本性质,高等数学基础,基本性质,高等数学基础,基本概念,高等数学基础,基本性质,高等数学基础,基本性质,凸规划例：凸可行域,高等数学基础,基本性质,凸规划例：凸目标函数,高等数学基础,基

2、本性质,高等数学基础,基本概念,非凸规划,高等数学基础,基本性质,非凸规划,高等数学基础,基本性质,非凸规划,高等数学基础,基本性质,非凸规划,运筹学基础,运筹学的方法论基础： 穷举法（完全枚举法、列举树法） 分枝定界法（分支限定法、B 以熊的价值从大到小的顺序; 以（价值重量）从大到小的顺序,取决于下界及上界的强度- 松弛问题的上界（最小化问题是下界）- 近似解法所取得的下界（最小化问题是上界） 的及早获取,3. 取决于分枝点的选取顺序(分枝子问题优先原则) 如从具有较大上界的点开始分枝 （该点下存在较好解的可能性大）,分枝定界法：理论升华,运筹学基础,分枝定界法：理论升华,运筹学基础,分枝

3、定界法：理论升华,运筹学基础,分枝定界法：理论升华,运筹学基础,分枝定界法：理论升华,运筹学基础,分枝定界法：理论升华,运筹学基础,分枝定界法：理论升华,运筹学基础,分枝定界法：理论升华,运筹学基础,分枝定界法：理论升华,运筹学基础,分枝定界法：理论升华,运筹学基础,分枝定界法总结：,动态规划法：现实中的问题,运筹学基础,小熊有4种 每种有大量库存,满足背包的重量制約条件 的前提下，带走尽可能高 价值的物品！,动态规划法：现实问题,运筹学基础,背包的重量上限，使分别以0,1,7的順序計算 物品的种类集合N=极小，小，中，大 物品种类 i 的重量 si，其价值 vi 重量上限为时的最优値 （现时

4、点背包内价值的合計）f () 对于函数 f ()，以下的等式成立（Bellman方程式）,重量上限的最优値,上限为si时的最优値,物品i 的价值,动态规划法：现实中的问题,运筹学基础,整数背包问题的动态规划法,动态规划法：现实中的问题,运筹学基础,最优解的最短路图,各点表示可能的值的状態某一状態（点）和别的状態（点）之间的连线为枝 枝上的数字表示状态之间变化所增加的背包内物品的价值 下图为状态从0至7的最短路图解,动态规划法：现实中的问题,运筹学基础,仅以背包的重量来表现状態有缺陷:内装的物品种类及数量无法表现！ 内装的物品 1.k 種时的最优値 f(k ,) Bellman方程式,内装物品为 k个, 且 重量上限时的最优値,带上第 k 个物品时的 背包中物品的价值合計,没有带上第k个物品时的背包中物品的价值合計,动态规划法：现实中的问题,运筹学基础,双参数表述的动态规划过程,动态规划法：现实中的问题