优化建模与LINGO第01章课件

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