数学规划建模new.ppt

数学规划建模new_数学建模华中农业大学数学建模基地系列课件道, 在明明德, 在亲民, , 事有终始, 知所先后, 则近道矣. ------ 《大学》数学规划( Mathematical Programming )俗称最优化,首先是一种理念,其次才是一种方法,它所追求的是一种“至善”之道,一种追求卓越的精神. 小明同学,烧一壶水要 8 分钟,灌开水要 1 分钟,取牛奶和报纸要 5 分钟,整理书包要 6 分钟,为了尽快做完这些事,怎样安排才能使时间最少?最少需要几分钟? 十个人各提一只水桶,同时到水龙头前打水。设水龙头注满第一个人的桶需要 1 分钟,注满第二个人的桶需要 2 分钟,依此类推,注满第几个人的桶就需要几分钟,如果只有一只水龙头,适当安排这 10 个人的顺序,就可以使每个人所费的时间总和尽可能少,问这个总费时至少是几分钟? 数学规划(最优化)作为一门学科孕育于 20 世纪的 30 年代,诞生于第二次世界大战弥漫的硝烟中。数学规划指在一系列客观或主观限制条件下,寻求合理分配有限资源使所关注的某个或多个指标达到最大(或最小)的数学理论与方法,是运筹学里一个十分重要的分支。“夫运筹帷幄之中,决胜千里之外”《史记·高祖本纪》最优化问题的数学模型的一般形式为: ?? xfz opt ??????? s k j iRDx nkxt mjxg lixhts????????,,1,0 ,,1,0 ,,1,0 ..???(1) (2) 三个要素:决策变量 decision bariable ,目标函数 objective function ,约束条件 constraints 。(2 )所确定的 x 的范围称为可行域 feasible region , 满足( 2 )的解 x 称为可行解 feasible solution ,同时满足( 1 )( 2 )的解 x 称为最优解 Optimal solution ,整个可行域上的最优解称为全局最优解 global optimal solution ,可行域中某个领域上的最优解称为局部最优解 local optimal solution 。最优解所对应的目标函数值称为最优值 optimum 。优化模型的分类(一)按有无约束条件(2)可分为: unconstrained optimization 。 constrained optimization 。大部分实际问题都是约束优化问题。(二) 按决策变量取值是否连续可分为: 。可继续划分为线性规划( LP)Linear programming 和非线性规划( NLP) Nonlinear programming 。在非线性规划中有一种规划叫做二次规划( QP)Quadratic programming ,目标为二次函数, 约束为线性函数。 。包含: 整数规划( IP)Integer programming ,整数规划中又包含很重要的一类规划: 0-1 (整数)规划 Zero-one programming ,这类规划问题的决策变量只取 0或者 1。(三) 按目标的多少可分为: 。 。(四) 按模型中参数和变量是否具有不确定性可分为: 。 。(五) 按问题求解的特性可分为: 。 。 。 。 5.……等等。优化问题求解常用的软件 LINGO 软件和 MATLAB 软件。对于 LINGO 软件,线性优化求解程序通常使用单纯形法 simplex method ,单纯形法虽然在实际应用中是最好最有效的方法,但对某些问题具有指数阶的复杂性,为了能解大规模问题,也提供了内点算法 interior point method 备选( LINGO 中一般称为障碍法,即 barrier ),非线性优化求解程序采用的是顺序线性规划法,也可用顺序二次规划法,广义既约梯度法,另外可以使用多初始点( LINGO 中称 multistart )找多个局部最优解增加找全局最优解的可能,还具有全局求解程序—分解原问题成一系列的凸规划。