《优化建模与LINGO第01章.ppt》由会员分享，可在线阅读，更多相关《优化建模与LINGO第01章.ppt（40页珍藏版）》请在三一文库上搜索。
1、优化建模与LINDO/LINGO软件 第 1 章 引 言,原书相关信息 谢金星, 薛毅编著, 清华大学出版社, 2005年7月第1版. http:/ 优化模型的基本概念 2. 优化问题的建模实例 3. LINDO/LINGO 软件简介,1. 优化模型的基本概念,最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题, 如:,优化模型和算法的重要意义,结构设计,资源分配,生产计划,运输方案,解决优化问题的手段,经验积累，主观判断,作试验，比优劣,建立数学模型，求解最优策略,最优化: 在一定条件下，寻求使目标最大(小)的决策,优化问题三要素：决策变量；目标函数；约束条件,优化问题的一般形式
2、,无约束优化(没有约束)与约束优化(有约束) 可行解（只满足约束）与最优解(取到最优值),局部最优解与整体最优解,局部最优解 (Local Optimal Solution, 如 x1 ) 整体最优解 (Global Optimal Solution, 如 x2 ),优化模型的 简单分类,线性规划(LP) 目标和约束均为线性函数 非线性规划(NLP) 目标或约束中存在非线性函数 二次规划(QP) 目标为二次函数、约束为线性 整数规划(IP) 决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) 一般整数规划，0-1（整
3、数）规划,连续优化,离散优化,数学规划,优化模型的简单分类和求解难度,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,问题求解的难度增加,2. 优化问题的建模实例,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,线性规划模型例1.1: 奶制品生产计划,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件
4、,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,模型分析与假设,比例性,可加性,连续性,xi对目标函数的“贡献”与xi取值成正比,xi对约束条件的“贡献”与xi取值成正比,xi对目标函数的“贡献”与xj取值无关,xi对约束条件的“贡献”与xj取值无关,xi取值连续,A1,A2每公斤的获利是与各自产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数,A1,A2每公斤的获利是与相互产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数,加工A1,A2的牛奶桶数是实数,线性规划模型,模型求解,图解法,约束条件,目标函数,z=c (常
5、数) 等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,求解LP的基本思想,思路：从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到最优解。,LP的约束和目标函数均为线性函数,2维,可行域 线段组成的凸多边形,目标函数 等值线为直线,最优解 凸多边形的某个顶点,n维,超平面组成的凸多面体,等值线是超平面,凸多面体的某个顶点,LP的通常解法是单纯形法(G. B. Dantzig, 1947),内点算法(Interior point method) 20世纪80年代人
6、们提出的一类新的算法内点算法 也是迭代法，但不再从可行域的一个顶点转换到另一个顶点，而是直接从可行域的内部逼近最优解。,LP其他算法,有效集(Active Set)方法 LP是QP的特例（只需令所有二次项为零即可） 可以用QP的算法解QP(如: 有效集方法),线性规划模型的解的几种情况,某厂生产两个牌号的同一种产品，如何确定产量使利润最大,二次规划模型例1.2：产销计划问题,= （100-x1-0.1 x2-2）x1 +（280-0.2x1-2x2-3）x2 =98 x1 + 277 x2 x12 0.3 x1 x2 2x22,约束,x1 + x2 100 x1 2 x2 x1 , x2 0,
7、二次规划模型(QP),若还要求产量为整数，则是整数二次规划模型(IQP),非线性规划模型例1.3：选址问题,某公司有6个建筑工地，位置坐标为(ai, bi) (单位：公里),水泥日用量di (单位：吨）,假设：料场和工地之间有直线道路,用例中数据计算，最优解为,总吨公里数为136.2,线性规划模型(LP),决策变量：ci j (料场j到工地i的运量）12维,选址问题：NLP,2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij ，在其它条件不变下使总吨公里数最小。,决策变量： ci j，(xj,yj)16维,非线性规划模型 (NLP),整数规划 - 例1.4: 聘用方案,决策变量：
8、周一至周日每天(新)聘用人数 x1, x2,x7,目标函数：7天(新)聘用人数之和,约束条件：周一至周日每天需要人数,连续工作5天,设系统已进入稳态（不是开始的几周）,聘用方案,整数规划 模型(IP),丁的蛙泳成绩退步到115”2；戊的自由泳成绩进步到57”5, 组成接力队的方案是否应该调整？,如何选拔队员组成4100米混合泳接力队?,0-1规划 混合泳接力队的选拔,例1.5： 5名候选人的百米成绩,穷举法：组成接力队的方案共有5!=120种。,目标函数,若选择队员i参加泳姿j 的比赛，记xij=1, 否则记xij=0,0-1规划模型,cij(秒)队员i 第j 种泳姿的百米成绩,约束条件,每人
9、最多入选泳姿之一,每种泳姿有且只有1人,0-1规划: 整数规划的特例,整数规划问题一般形式,整数线性规划(ILP) 目标和约束均为线性函数 整数非线性规划(NLP) 目标或约束中存在非线性函数,整数规划问题的分类,纯(全)整数规划(PIP) 决策变量均为整数 混合整数规划(MIP) 决策变量有整数，也有实数,0-1规划 决策变量只取0或1,取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题,整数规划问题对应的松弛问题,下界（对Min问题） 上界（对Max问题）,用连续优化方法求解松弛问题，如果松弛问题最优解（分量）全为整数，则也是原整数规划问题的最优解,对松弛问
10、题的最优解（分量）舍入为整数，得到的往往不是原整数规划问题的最优解（甚至不是可行解）,IP可行解对应于整点A(2,2)和B(1,1),而最优解为A点. 但LP松弛的最优解为C(3.5,2.5),去掉整数限制后，可行域为点（0,0), (6,0), (0,5), P (2.25,3.75) 围成的4边形,从LP最优解经过简单的 “移动”不一定能得到IP最优解,例1.6,基本思想：隐式地枚举一切可行解（“分而治之”）,所谓分枝，就是逐次对解空间（可行域）进行划分；而所谓定界，是指对于每个分枝（或称子域），要计算原问题的最优解的下界（对极小化问题）. 这些下界用来在求解过程中判定是否需要对目前的分枝
11、进一步划分，也就是尽可能去掉一些明显的非最优点，避免完全枚举.,分枝定界法（B&B: Branch and Bound）,对于极小化问题，在子域上解LP，其最优值是IP限定在该子域时的下界；IP任意可行点的函数值是IP的上界。,这里仅介绍整数线性规划的分枝定界算法,无约束优化,更多的优化问题,线性规划,非线性规划,网络优化,组合优化,整数规划,不确定规划,多目标规划,目标规划,动态规划,连续优化,离散优化,从其他角度分类,应用广泛：生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等 实际问题规模往往较大，用软件求解比较方便,3.
12、 LINDO/LINGO软件简介,常用优化软件,1. LINDO/LINGO软件 2. MATLAB优化工具箱 / Mathematic的优化功能 3. SAS(统计分析)软件的优化功能 4. EXCEL软件的优化功能 5. 其他（如CPLEX等）,MATLAB优化工具箱能求解的优化模型,优化工具箱3.0 (MATLAB 7.0 R14),连续优化,离散优化,无约束优化,非线性 极小 fminunc,非光滑(不可 微)优化 fminsearch,非线性 方程(组) fzero fsolve,全局 优化 暂缺,非线性 最小二乘 lsqnonlin lsqcurvefit,线性规划 linprog
13、,纯0-1规划 bintprog 一般IP(暂缺),非线性规划 fmincon fminimax fgoalattain fseminf,上下界约束 fminbnd fmincon lsqnonlin lsqcurvefit,约束线性 最小二乘 lsqnonneg lsqlin,约束优化,二次规划 quadprog,LINDO 公司软件产品简要介绍,美国芝加哥(Chicago)大学的Linus Schrage教授于1980年前后开发, 后来成立 LINDO系统公司（LINDO Systems Inc.）， 网址：http:/,LINDO: Linear INteractive and Disc
14、rete 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,LINGO软件的功能与特点,LINGO模型的优点
15、,集成了线性(非线性) / 连续(整数) 优化功能 具有多点搜索 / 全局优化功能 提供了灵活的编程语言(矩阵生成器)，可方便地输入模型 提供与其他数据文件的接口 提供与其他编程语言的接口 LINDO API 可用于自主开发 运行速度较快,LP QP NLP IP 全局优化(选) ILP IQP INLP,LINGO软件的求解过程,LINGO预处理程序,线性优化求解程序,非线性优化求解程序,分枝定界管理程序,1. 确定常数 2. 识别类型,1. 单纯形算法 2. 内点算法(选),1、顺序线性规划法(SLP) 2、广义既约梯度法(GRG) (选) 3、多点搜索(Multistart) (选),建模时需要注意的几个基本问题,1、尽量使用实数优化，减少整数约束和整数变量 2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等 3、尽量使用线性模型，减少非线性约束和非线性变量的个数 （如x/y 5 改为x5y） 4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当 (如小于103),自己练习，或课上布置,布置作业内容,Thank you very much!,