Lec1---一些优化问题介绍.ppt

2017-2-22 一些优化问题介绍 2017-2-22 最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题, 如:结构设计、资源分配、生产计划、运输方案优化模型和算法的重要意义解决优化问题的手段: 1)经验积累,主观判断; 2)作试验,比优劣; 3)建立数学模型, 求解最优策略最优化:在一定条件下,寻求使目标最大(小)的决策 2017-2-22 优化问题三要素: 决策变量;目标函数;约束条件约束条件决策变量优化问题的一般形式 n j iDx ljxg m ixhts xf???????,..., 1,0)( ,..., 1,0)(.. )( min ?无约束优化(没有约束)与约束优化(有约束) ?可行解(只满足约束)与最优解(取到最优值) 目标函数 2017-2-22 局部最优解与整体最优解?局部最优解(Local Optimal Solution, 如x 1 ) ?整体最优解(Global Optimal Solution, 如x 2 ) x * f(x)x 1x 2o 2017-2-22 连续优化离散优化整数规划(IP) 决策变量(全部或部分)为整数整数线性规划(ILP) ,整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) 一般整数规划, 0-1 (整数)规划优化模型的简单分类线性规划(LP): 目标和约束均为线性函数非线性规划(NLP): 目标或约束中存在非线性函数二次规划(QP): 目标为二次函数、约束为线性 2017-2-22 单目标优化模型: 多目标优化模型: 光滑优化模型: 非光滑优化模型: 仅一个目标多个目标目标函数、约束条件函数全部都可微否则凸优化模型非凸优化模型 2017-2-22 优化模型的简单分类和求解难度优化线性规划非线性规划二次规划连续优化整数规划问题求解的难度增加 2017-2-22 单目标优化问题光滑优化问题多目标优化问题非光滑优化问题问题求解的难度增加凸优化问题非凸优化问题 2017-2-22 线性规划( LP ):目标和约束均为线性函数????????????????????????????0,,, , , , 21 2211 2 2222 121 1 1212 1 11n m n mn m m nn nnxxx bxaxaxa bxaxaxa bxaxaxa????????????????) (或) (或) (或目标函数约束条件 nnxcxcxcz????? 2211 min max ) (或 2017-2-22 简写形式: ????????????????) , , ( ) , , ( ) , (或) (或nj x m ib xa xcz j i nj j ij nj jj?? 1 0 1 min max 1 1