《优化建模与》PPT课件.ppt
优化建模与计算,许顺维,参考书优化建模与LINDO/LINGO软件,谢金星,薛毅编著,清华大学出版社,2005年7月第1版.http:/,内容提要,1.优化模型的基本概念2.优化问题的建模实例3.LINDO/LINGO 软件简介,1.优化模型的基本概念,最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题,如:,优化模型和算法的重要意义,结构设计,资源分配,生产计划,运输方案,解决优化问题的手段,经验积累，主观判断,作试验，比优劣,建立数学模型，求解最优策略,最优化:在一定条件下，寻求使目标最大(小)的决策,优化问题三要素：决策变量；目标函数；约束条件,优化问题的一般形式,无约束优化(没有约束)与约束优化(有约束)可行解（只满足约束）与最优解(取到最优值),局部最优解与整体最优解,局部最优解(Local Optimal Solution,如 x1)整体最优解(Global Optimal Solution,如 x2),优化模型的简单分类,线性规划(LP)目标和约束均为线性函数 非线性规划(NLP)目标或约束中存在非线性函数 二次规划(QP)目标为二次函数、约束为线性 整数规划(IP)决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)一般整数规划，0-1（整数）规划,连续优化,离散优化,数学规划,优化模型的简单分类和求解难度,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,问题求解的难度增加,2.优化模型实例,目标函数,约束条件,例2.1 线性规划模型(LP),模型求解,图解法,约束条件,目标函数,z=c(常数)等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,求解LP的基本思想,思路：从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到最优解。,LP的约束和目标函数均为线性函数,2维,可行域 线段组成的凸多边形,目标函数 等值线为直线,最优解 凸多边形的某个顶点,n维,超平面组成的凸多面体,等值线是超平面,凸多面体的某个顶点,LP的通常解法是单纯形法(G.B.Dantzig,1947),内点算法(Interior point method)20世纪80年代人们提出的一类新的算法内点算法也是迭代法，但不再从可行域的一个顶点转换到另一个顶点，而是直接从可行域的内部逼近最优解。,LP其他算法,有效集(Active Set)方法 LP是QP的特例（只需令所有二次项为零即可）可以用QP的算法解QP(如:有效集方法),线性规划模型的解的几种情况,目标,98 x1+277 x2 x12 0.3 x1 x2 2x22,约束,x1+x2 100 x1 2 x2x1,x2 0,二次规划模型(QP),若还要求产量为整数，则是整数二次规划模型(IQP),二次规划模型(QP)-例1.2,决策变量：ci j，(xj,yj)16维,非线性规划模型(NLP),非线性规划模型(NLP)例1.3：,整数规划问题一般形式,整数线性规划(ILP)目标和约束均为线性函数 整数非线性规划(NLP)目标或约束中存在非线性函数,整数规划问题的分类,纯(全)整数规划(PIP)决策变量均为整数 混合整数规划(MIP)决策变量有整数，也有实数,0-1规划 决策变量只取0或1,取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题,整数规划问题对应的松弛问题,基本思想：隐式地枚举一切可行解（“分而治之”）,所谓分枝，就是逐次对解空间（可行域）进行划分；而所谓定界，是指对于每个分枝（或称子域），要计算原问题的最优解的下界（对极小化问题）.这些下界用来在求解过程中判定是否需要对目前的分枝进一步划分，也就是尽可能去掉一些明显的非最优点，避免完全枚举.,分枝定界法（B&B:Branch and Bound）,整数线性规划的分枝定界算法,无约束优化,更多的优化问题,线性规划,非线性规划,网络优化,组合优化,整数规划,不确定规划,多目标规划,目标规划,动态规划,连续优化,离散优化,从其他角度分类,应用广泛：生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等 实际问题规模往往较大，用软件求解比较方便,3.LINDO/LINGO软件简介,常用优化软件,1.LINDO/LINGO软件2.MATLAB优化工具箱/Mathematic的优化功能3.SAS(统计分析)软件的优化功能4.EXCEL软件的优化功能5.其他（如CPLEX等）,MATLAB优化工具箱能求解的优化模型,优化工具箱3.0(MATLAB 7.0 R14),连续优化,离散优化,无约束优化,非线性极小fminunc,非光滑(不可微)优化fminsearch,非线性方程(组)fzerofsolve,全局优化暂缺,非线性最小二乘lsqnonlinlsqcurvefit,线性规划linprog,纯0-1规划 bintprog一般IP(暂缺),非线性规划fminconfminimaxfgoalattainfseminf,上下界约束fminbndfminconlsqnonlinlsqcurvefit,约束线性最小二乘lsqnonneglsqlin,约束优化,二次规划quadprog,LINDO 公司软件产品简要介绍,美国芝加哥(Chicago)大学的Linus Schrage教授于1980年前后开发,后来成立 LINDO系统公司（LINDO Systems Inc.），网址：http:/,LINDO:Linear INteractive and Discrete Optimizer(V6.1)LINDO API:LINDO Application Programming Interface(V4.1)LINGO:Linear INteractive General Optimizer(V10.0)Whats Best!:(SpreadSheet e.g.EXCEL)(V8.0),演示(试用)版、高级版、超级版、工业版、扩展版（求解问题规模和选件不同）,LINDO/LINGO软件能求解的模型,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,LINDO,LINGO,建模时需要注意的几个基本问题,1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y 5 改为x5y）4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当(如小于103),
