PDF《最优化概述》

最优化概述 Liu Zheng 最优化方法概 述 经典极值问题 无约束极值问题 有约束最优化 有约束最优化问题的 数学建模 最优化方法主要内容 线性规划与整 数规划 整数规划 单纯形法 多目标规划 非线性规划 凸函数 下降迭代法 变分法与动态 规划 动态规划 智能优化方法 .

. . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . . .. . . . .. . . . .. . . . . . . . . 最优化概述 Liu Zheng 同济大学电信学院 April 22,

2014 Liu Zheng 最优化概述 最优化概述 Liu Zheng 最优化方法概 述 经典极值问题 无约束极值问题 有约束最优化 有约束最优化问题的 数学建模 最优化方法主要内容 线性规划与整 数规划 整数规划 单纯形法 多目标规划 非线性规划 凸函数 下降迭代法 变分法与动态 规划 动态规划 智能优化方法 .. . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . . .. . . . .. . . . .. . 概述 最优化理论和方法是近二十多年来发展十分迅速的一个 数学分支 在数学上,最优化是一种求极值的方法 最优化已经广泛的渗透到工程、经济、电子技术等领域 Liu Zheng 最优化概述 最优化概述 Liu Zheng 最优化方法概 述 经典极值问题 无约束极值问题 有约束最优化 有约束最优化问题的 数学建模 最优化方法主要内容 线性规划与整 数规划 整数规划 单纯形法 多目标规划 非线性规划 凸函数 下降迭代法 变分法与动态 规划 动态规划 智能优化方法 .. . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . . .. . . . .. . . . .. . 概述 在实际生活中,人们做任何事情,不管是分析问题,还 是进行决策,都要用一种标准衡量以下是否达到来最 优.(比如基金人投资) 在各种科学问题、工程问题、生产管理、社会经济问题 中,人们总是希望在有限的资源条件下,用尽可能小的 代价,获得最大的收益.(比如保险) Liu Zheng 最优化概述 最优化概述 Liu Zheng 最优化方法概 述 经典极值问题 无约束极值问题 有约束最优化 有约束最优化问题的 数学建模 最优化方法主要内容 线性规划与整 数规划 整数规划 单纯形法 多目标规划 非线性规划 凸函数 下降迭代法 变分法与动态 规划 动态规划 智能优化方法 .. . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . . .. . . . .. . . . .. . 几个概念 最优化是从所有可能方案中选择最合理的一种,以达到 最优目标的学科 最优方案是达到最优目标的方案 最优化方法是搜寻最优方案的方法 最优化理论就是最优化方法的理论 Liu Zheng 最优化概述 最优化概述 Liu Zheng 最优化方法概 述 经典极值问题 无约束极值问题 有约束最优化 有约束最优化问题的 数学建模 最优化方法主要内容 线性规划与整 数规划 整数规划 单纯形法 多目标规划 非线性规划 凸函数 下降迭代法 变分法与动态 规划 动态规划 智能优化方法 .. . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . . .. . . . .. . . . .. . 经典极值问题 包括 无约束极值问题 min x f(x) 约束条件下的极值问题 min x f(x) s.t. gi(x) ≤ 0, i = 1, 2,m hi(x) = 0, i = 1, 2,n 其中,极大值问题可以转换为极小值问题来进行求解. 如求: max x f(x) 可以转换为: min x ? f(x) Liu Zheng 最优化概述 最优化概述 Liu Zheng 最优化方法概 述 经典极值问题 无约束极值问题 有约束最优化 有约束最优化问题的 数学建模 最优化方法主要内容 线性规划与整 数规划 整数规划 单纯形法 多目标规划 非线性规划 凸函数 下降迭代法 变分法与动态 规划 动态规划 智能优化方法 .. . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . . .. . . . .. . . . .. . 无约束极值问题 Liu Zheng 最优化概述 最优化概述 Liu Zheng 最优化方法概 述 经典极值问题 无约束极值问题 有约束最优化 有约束最优化问题的 数学建模 最优化方法主要内容 线性规划与整 数规划 整数规划 单纯形法 多目标规划 非线性规划 凸函数 下降迭代法 变分法与动态 规划 动态规划 智能优化方法 .. . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . . .. . . . .. . . . .. . 有约束最优化 最优化方法分类 (1) 线性最优化:目标函数和约束条件都是线性的则称为线 性最优化. 非线性最优化:目标函数和约束条件如果含有非线性 的,则称为非线性最优化. (2) 静态最优化:如果可能的方案与时间无关,则是静态最 优化问题. 动态最优化:如果可能的方案与时间有关,则是动态最 优化问题 Liu Zheng 最优化概述 最优化概述 Liu Zheng 最优化方法概 述 经典极值问题 无约束极值问题 有约束最优化 有约束最优化问题的 数学建模 最优化方法主要内容 线性规划与整 数规划 整数规划 单纯形法 多目标规划 非线性规划 凸函数 下降迭代法 变分法与动态 规划 动态规划 智能优化方法 .. . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . . .. . . . .. . . . .. . 数学建模 有约束最优化模型一般具有以下形式: min x f(x) s.t. 或max x f(x) s.t. 其中 f(x) 为目标函数,省略号表示约束式子,可以是等式约 束,也可以是不等式约束. Liu Zheng 最优化概述 最优化概述 Liu Zheng 最优化方法概 述 经典极值问题 无约束极值问题 有约束最优化 有约束最优化问题的 数学建模 最优化方法主要内容 线性规划与整 数规划 整数规划 单纯形法 多目标规划 非线性规划 凸函数 下降迭代法 变分法与动态 规划 动态规划 智能优化方法 .. . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . . .. . . . .. . . . .. . 最优化方法主要内容 根据目标函数,约束条件的特点将最优化方法包含的主要内 容大致如下划分: 线性规划 整数规划 非线性规划 智能优化方法 变分法与动态规划 Liu Zheng 最优化概述 最优化概述 Liu Zheng 最优化方法概 述 经典极值问题 无约束极值问题 有约束最优化 有约束最优化问题的 数学建模 最优化方法主要内容 线性规划与整 数规划 整数规划 单纯形法 多目标规划 非线性规划 凸函数 下降迭代法 变分法与动态 规划 动态规划 智能优化方法 .. . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . . .. . . . .. . . . .. . 线性规划与整数规划 在许多线性规划问题中,要求最优解必须取整数.例如 所求 的解是机器的台数、人数车辆船只数等.如果所得的解 中决策 变量为分数或小数则不符合实际问题的要求. 对于一个规划问题,如果要求全部决策变量都取整数, 称为 纯(或全)整数规划;