数学建模竞赛中的优化问题.ppt

数学建模竞赛中的优化问题,数学建模 培训组 2009.3,本次讲座目的,让大家了解数学建模中常常遇到的问题优化问题；初步认识数学建模需要准备的算法，软件。,优化问题,优化问题的解题步骤：1、确定最优目标函数。2、寻找构成目标函数的各元素应该遵守的约束条件。3、利用相应软件或算法求解。,数学规划,线性规划(linear programming)是康托洛维奇1939年提出的，1947年（）提出求线性规划的单纯形法（simple method），理论上趋向成熟，实际上的应用也越来越广泛，几乎各行各业都可建立线性规划模型。,某企业要在计划期内安排生产甲、乙两种产品，这个企业现有的生产资料是：设备18台时，原材料A 4吨，原材料 B 12吨；已知单位产品所需消耗生产资料及利润如下表。问应如何确定生产计划使企业获利最多。,1.1 线性规划问题,例1 生产计划问题,表1,Formulation as a linear programming problem,x1=number of units of product 1 x2=number of units of product 2z=total profit from producting these two products x1,x2 are the decision variables for the model.maximize z=3x1+5x2,非负约束,设备限制,原料A的限制,原料B的限制,相应的数学模型,资源的合理利用问题-the allocating resources to activities,一般的资源利用问题可表述为：设某企业利用 m 种资源来生产 n 种产品，已知该企业拥有的第 i 种资源的数量是b i,生产单位第 j 种产品所消耗的第 i 种资源的数量为 aij，第j种产品的单位利润是 c j。现制定一个生产计划方案，使总利润最大。,z=value of overall measure of performance,xj=level of activities j(for j=1,2,n),cj=increase in z that would resule from each unit increase in level of activity j-价值系数,aij=amount of resource i consumed by each unit of activity j.-技术系数,bi=amount of resource i that is available for allocation to activities(for i=1,2,m)-资源系数,x1,x2,xn are called the decision variables.,cj,bi,aij(for i=1,2,m and j=1,2,n)are the input constants or the parameters for the model.,资源利用问题的数学模型为：,the objective function,functional constrains,nonegativeconstrains,假设企业决策者不考虑自己生产产品甲乙，而是将厂里的现有资源（见表1）买出。试问该厂的决策者应给每种资源制定一个怎样的价格，才能获得良好收益？,例2 资源定价问题,问题分析,解：决策者显然要考虑两个因素：第一，每种资源所收回的费用应不底于自己生产 时所获得的利润；第二，定价又不能太高，要使对方容易接受。总之，定价要公平合理，使双方都能接受。,问题分析,设y1,y2,y3分别表示这三种资源的收费单价。则由第一条原则：将用于加工产品甲或乙的所有资源，如用来加工外来产品所获得的收回的费用，应不低于可获得的利润，即,从工厂的决策者来看当然是越大越好。但是根据第二条原则，也应该使对方的支出尽可能的少；从而这个问题就可以转化为下述数学问题：,当然对价格还要有非负限制。即：,将该厂所有的资源都用来加工外来产品，其总收入（即对方的总支出）是,定价问题的数学模型,设某单位现有n个人员A1,A2,An来完成n项工作B1,B2,Bn。按工作要求，每个人员需干一项工作，每项工作也需一人去完成。已知人员A i做工作B j的效率是c ij。问应如何分配，才使总效率最好。,例3 人员分配问题,问题分析,令x ij表示分配人员A i完成工作 B j的决策变量。x ij=1 表示分配Ai干工作Bj xij=0 表示不分配Ai干工作Bj 按问题要求，每人要做一项工作，每项工作需一人去做。建立该问题的数学模型的过程：,问题分析,派工方案的总效益,对工作B j；要求一人员去完成,对人员A i；要求承担一项工作：,分配问题的数学模型,某公司要运销一种物资。该物资有甲、乙两个产地，产量分别是2000吨、1000吨；另有A、B、C三个销地，销量分别是1700吨、1100吨、200吨。已知该物资的单位运价如表1-2。问应如何确定调运方案，才能使在产销平衡的条件下，总运费最低？,例4 物资运输问题,表3,分析 确定调运方案就是确定从不同产地到各个销地的运输量。设 x ij 表示这些要找的运量。即x 11、x 12、x 13分别表示从甲地调往A、B、C三地的运量。x 21、x 22、x 23分别表示从已地调往A、B、C三地的运量。,由于要求产销平衡：从两产地甲、乙分别调往三销地A、B、C的物资数量应该分别等于两产地甲、乙的产量，所以 x ij 应满足：,运到A、B、C三销地的物资数量应分别等于A、B、C三销地的销量，所以x ij 还应该满足：,由于x ij 是运量，不能是负数：,调运方案的总运费为：,建立产销平衡下运费最省的调运问题的数学模型：,运输问题的数学模型,某种物资有 m 个产地，A1,A2,Am，产量分别a1,a2,am个单位，另有 n 个销地B1,B2,Bn,销量分别是b1,b2,bn个单位。假设产销是平衡的，即总产量等于总销量。已知由产地A i 向销地B j 运输一个单位物资的运价x ij；问应该怎样调运物资才能使总运费最省。,令 x ij 表示由产地A i 向销地B j 的运量,运输问题的一般提法：,运输问题的数学模型为：,上述例子，虽然有不同的实际内容，但是它们都是要求一组变量的值，这组值满足一定的约束条件，如资源限制、供求关系等。这种约束条件都可以用一组线性不等式或线性方程来表示，同时使某个线性函数指标达到最大或最小。具有这些特征的问题，称为线性规划问题。,1.2 图解法-graphical method,图解法适用于来解只有两个变量的线性规划问题.,The feasible region is the collection of all feasible solutions.,A feasible solution is a solution for which all the constraints are satisfied.It is possible for a problem to have not feasible solutions.,An in feasible solution is a solution for which at least one constraint is violated.,An optimal solution is a feasible solution that has the most favorable value(the largest or the smallest)of the objective function.,It is possible for a problem to have more than one optimal solution.Any problem having multiple optimal solutions will have an infinite number of them.,例1,图解法求解线性规划问题,图解法简单直观，有助于了解线性规划问题求解的基本原理和思想。下面举例说明图解法求解线性规划问题的步骤。,解 该线性规划问题的可行域见图1。,2 4 6 8 x1,x2 8 6 4 2 0,x1=4,2 x 2=12,3x1+2x2=18,Q,Q0(0,0),Q1(0,6),Q2(2,6),Q3(4,3),Q4(4,0),图解法解题过程,图1-1,可行域-the feasible region,2 4 6 x1,x2 8 6 4 2 0,x1=4,2 x 2=12,3x1+2x2=18,Q,Q0(0,0),Q1(0,6),Q2(2,6),Q3(4,3),Q4(4,0),3x1+5x2=z=36,3x1+5x2=z=20,3x1+5x2=z=0,图解法解题过程,图1-1,让直线束,沿正法线,在可行域Q移动，,通过点(2,6)的直线：,注：本问题只有唯一最优解。,例1的最优生产方案为：生产产品甲为2件，生产产品乙6件，最大利润为36万元。,x1 8 6 4 2 0,x1=4,Q,Q0(0,0),Q1(0,6),Q2(2,6),Q3(4,3),Q4(4,0),x1,注：问题的可行域是一个有界的凸多边形，其边界由5条直线所围成：X 1=0,X 2=0X 1=42 x 2=123 x1+2 x2=18最优解(2,6)在凸多边形的顶点Q2上。,x2 8 6 4 2 0,x1=4,Q,Q0(0,0),Q1(0,6),Q2(2,6),Q3(4,3),Q4(4,0),x1,例2,解 该问题的可行域 Q 是一个有界的凸多边形（如图1-2）。,-x1+x2=0,X1+x2=5,6x1+2x2=21,3x 1+x 2=z=0,3x 1+x 2=z=6,3x 1+x 2=z=21/2,A(11/4,9/4),B(21/6,0),x1,x2,让直线束3x 1+x 2=z 沿正法线向移动，到达线段AB时，使 Z 达到最大。所以线段 AB上的每一点都可使Z达到最大值，注：本问题有无穷多个最优解。,-x1+x2=0,x1+x2=5,6x1+2x2=21,3x 1+x 2=z=0,3x 1+x 2=z=6,3x 1+x 2=z=21/2,A(11/4,9/4),B(21/6,0),x1,x2,例3,图1-3,解 该问题的可行域是一个无界的凸多边形,让直线束 沿其负法线方向移动，可以无限制地移动下去，一直与 相交，所以其最小值为；即函数 在 上无下界。,注：本问题有可行解，但无最优解。,例4,解 该问题的可行域是空的，即无可行解,X1-x2=-1,x1+x2=-1,注：本问题无可行解，更无最优解。,进一步讨论给定只有两个变量的线性规划问题：,图解法求解线性规划问题的步骤如下：,若 是空集，则说明线性规划问题无可行解。,如果 不是空集，那么 是平面上的一个凸多边形，这个凸多边形可能是有界的（封闭的），也可能是无界的（不封闭的）。,表示一个以 z 为参数的平行直线束。,沿正法线方向 移动可得最大值，沿负法线方向 移动可得最小值。,注意:一定要精确,在平面 上取定直角坐标系，画出可行域，记为。,通过以上例子可以看出，两个变量的线性规划的解可能有以下4种情况：有唯一的最优解。最优解一定是可行域的一个顶点。有无穷多的最优解。最优解是可行域的一段边界。有可行解，但无最优解。目标函数值无界.无可行解。（最大值点（最小值点）一定在可行域的边界上）问题是对于一般的线性规划问题有无类似结论，结论成立的判定准则如何。,1.3 整数规划,例1、集装箱运货,解：设X1,X2 为甲、乙两货物各托运箱数,maxZ=20 X1+10 X2,例2、背包问题,背包可再装入8单位重量，10单位体积物品,解：Xi为是否带第 i 种物品,maxZ=20X1+30X2+10X3+18X4+15X5,一般形式：,整数,(1)、Xi为i 物品携带数量 ai为i 物品单位重量 ci为i 物品重要性估价 b为最大负重,(2)、投资决策 Xi为在i 地区建厂规模 ai为在i 地区建厂基建费用 ci为在i 地区建厂单位利润 b为最大资本,(3)、Xi 取0或1时，可作项目投资模型,例3、选址问题,问：选择适当地点建仓库，在满足商店需求条件下，总费用最小。,解：设Xi(i=1,2,3)为是否在 Ai 建仓库 yij(i=1,2,3,j=14)由 i仓库向 j商店运货量,y11+y21=d1y12+y22+y32=d2y23+y33=d3y14+y24+y34=d4x1+x2+x3=2y11+y12+y14 a1x1y21+y22+y23+y24a2x2y32+y33+y34 a3x3xi 为01，yij 0,混合整数规划,01决策变量的应用,可用于相互排斥计划中,例1、运输方式：火车、船。火车：5X1+4X2 24(体积)船：7X1+3X2 45(体积),maxZ=20X1+10X2,当 X3=0 火车 X3=1 船,例4:聘用方案,决策变量：周一至周日每天(新)聘用人数 x1,x2,x7,目标函数：7天(新)聘用人数之和,约束条件：周一至周日每天需要人数,连续工作5天,设系统已进入稳态（不是开始的几周）,聘用方案,整数规划模型(IP),丁的蛙泳成绩退步到115”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？,如何选拔队员组成4100米混合泳接力队?,0-1规划 混合泳接力队的选拔,例5：5名候选人的百米成绩,穷举法：组成接力队的方案共有5!=120种。,目标函数,若选择队员i参加泳姿j 的比赛，记xij=1,否则记xij=0,0-1规划模型,cij(秒)队员i 第j 种泳姿的百米成绩,约束条件,每人最多入选泳姿之一,每种泳姿有且只有1人,0-1规划:整数规划的特例,整数规划问题一般形式,整数线性规划(ILP)目标和约束均为线性函数 整数非线性规划(NLP)目标或约束中存在非线性函数,整数规划问题的分类,纯(全)整数规划(PIP)决策变量均为整数 混合整数规划(MIP)决策变量有整数，也有实数,0-1规划 决策变量只取0或1,取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题,整数规划问题对应的松弛问题,下界（对Min问题）上界（对Max问题）,用连续优化方法求解松弛问题，如果松弛问题最优解（分量）全为整数，则也是原整数规划问题的最优解,对松弛问题的最优解（分量）舍入为整数，得到的往往不是原整数规划问题的最优解（甚至不是可行解）,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,基本思想：隐式地枚举一切可行解（“分而治之”）,所谓分枝，就是逐次对解空间（可行域）进行划分；而所谓定界，是指对于每个分枝（或称子域），要计算原问题的最优解的下界（对极小化问题）.这些下界用来在求解过程中判定是否需要对目前的分枝进一步划分，也就是尽可能去掉一些明显的非最优点，避免完全枚举.,分枝定界法（B&B:Branch and Bound）,对于极小化问题，在子域上解LP，其最优值是IP限定在该子域时的下界；IP任意可行点的函数值是IP的上界。,这里仅介绍整数线性规划的分枝定界算法,例1：产销计划问题某厂生产两个牌号的同一种产品，如何确定产量使利润最大,1.4 二次规划模型,=（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 x2x1,x2 0,二次规划模型(QP),若还要求产量为整数，则是整数二次规划模型(IQP),1.5 非线性规划模型,例2：选址问题 某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）,假设：料场和工地之间有直线道路,用例中数据计算，最优解为,总吨公里数为136.2,线性规划模型(LP),决策变量：ci j(料场j到工地i的运量）12维,选址问题：NLP,2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij，在其它条件不变下使总吨公里数最小。,决策变量：ci j，(xj,yj)16维,非线性规划模型(NLP),优化建模与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.优化问题的建模实例,例1:家具厂生产计划例2:奶制品生产计划 例3:运输问题,线性规划模型,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,例2:奶制品生产计划,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,线性规划模型的解的几种情况,无约束优化,更多的优化问题,线性规划,非线性规划,网络优化,组合优化,整数规划,不确定规划,多目标规划,目标规划,动态规划,连续优化,离散优化,从其他角度分类,应用广泛：生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等 实际问题规模往往较大，用软件求解比较方便,LINDO/LINGO软件使用简介,使用LINDO的一些注意事项,“”（或“=”（或“=”）功能相同变量与系数间可有空格(甚至回车),但无运算符变量名以字母开头，不能超过8个字符变量名不区分大小写（包括LINDO中的关键字）目标函数所在行是第一行，第二行起为约束条件行号(行名)自动产生或人为定义。行名以“）”结束行中注有“!”符号的后面部分为注释。如:!Its Comment.在模型的任何地方都可以用“TITLE”对模型命名（最多72个字符），如：TITLE This Model is only an Example,变量不能出现在一个约束条件的右端表达式中不接受括号“()”和逗号“,”等任何符号,例:400(X1+X2)需写为400X1+400X2表达式应化简，如2X1+3X2-4X1应写成-2X1+3X2缺省假定所有变量非负；可在模型的“END”语句后用“FREE name”将变量name的非负假定取消可在“END”后用“SUB”或“SLB”设定变量上下界 例如：“sub x1 10”的作用等价于“x1=10”但用“SUB”和“SLB”表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析。14.“END”后对0-1变量说明：INT n 或 INT name15.“END”后对整数变量说明：GIN n 或 GIN name,使用LINDO的一些注意事项,二次规划(QP)问题,LINDO可求解二次规划(QP)问题，但输入方式较复杂，因为在LINDO中不许出现非线性表达式需要为每一个实际约束增加一个对偶变量（LAGRANGE乘子），在实际约束前增加有关变量的一阶最优条件，转化为互补问题“END”后面使用QCP命令指明实际约束开始的行号，然后才能求解建议总是用LINGO解QP注意对QP和IP:敏感性分析意义不大,状态窗口（LINDO Solver Status）,当前状态：已达最优解迭代次数：18次约束不满足的“量”(不是“约束个数”)：0当前的目标值：94最好的整数解：94整数规划的界：93.5分枝数：1所用时间：0.00秒（太快了，还不到0.005秒）刷新本界面的间隔:1(秒),选项设置,Preprocess：预处理(生成割平面)；Preferred Branch：优先的分枝方式：“Default”（缺省方式）、“Up”（向上取整优先）、“Down”（向下取整优先）；IP Optimality Tol：IP最优值允许的误差上限（一个百分数，如5%即0.05）；IP Objective Hurdle：IP目标函数的篱笆值，即只寻找比这个值更优最优解（如当知道当前模型的某个整数可行解时，就可以设置这个值）；IP Var Fixing Tol：固定一个整数变量取值所依据的一个上限（如果一个整数变量的判别数（REDUCED COST）的值很大，超过该上限，则以后求解中把该整数变量固定下来）。,Nonzero Limit：非零系数的个数上限；Iteration Limit：最大迭代步数；Initial Contraint Tol：约束的初始误差上限；Final Contraint Tol：约束的最后误差上限；Entering Var Tol：进基变量的REDUCED COST的误差限；Pivot Size Tol：旋转元的误差限,Report/Statistics,第一行：模型有5行（约束4行），4个变量，两个整数变量（没有0-1变量），从第4行开始是二次规划的实际约束。第二行：非零系数19个，约束中非零系数12个(其中6个为1或-1)，模型密度为0.760(密度=非零系数/行数(变量数)。第三行的意思：按绝对值看，系数最小、最大分别为0.3和277。第四行的意思：模型目标为极小化；小于等于、等于、大于等于约束分别有、个；广义上界约束（GUBS）不超过个；变量上界约束（VUBS）不少于个。所谓GUBS，是指一组不含有相同变量的约束；所谓VUBS，是指一个蕴涵变量上界的约束，如从约束X1+X2-X3=0可以看出，若X3=0，则X1=0，X2=0（因为有非负限制），因此X1+X2-X3=0是一个VUBS约束。第五行的意思：只含个变量的约束个数=个；冗余的列数=个,ROWS=5 VARS=4 INTEGER VARS=2(0=0/1)QCP=4NONZEROS=19 CONSTRAINT NONZ=12(6=+-1)DENSITY=0.760SMALLEST AND LARGEST ELEMENTS IN ABSOLUTE VALUE=0.300000 277.000OBJ=MIN,NO.:2 0 2,GUBS=0SINGLE COLS=0 REDUNDANT COLS=0,LINGO软件简介,目标与约束段 集合段（SETS ENDSETS）数据段（DATA ENDDATA）初始段（INIT ENDINIT）计算段(CALC ENDCALC)-LINGO9.0,LINGO模型的构成：5个段,LINGO模型的优点,包含了LINDO的全部功能 提供了灵活的编程语言（矩阵生成器）,集合的类型,集合 派生集合 基本集合 稀疏集合 稠密集合 元素列表法 元素过滤法 直接列举法 隐式列举法,setname/member_list/:attribute_list;,setname(parent_set_list)/member_list/:attribute_list;,SETS:CITIES/A1,A2,A3,B1,B2/;ROADS(CITIES,CITIES)/A1,B1 A1,B2 A2,B1 A3,B2/:D;ENDSETS,SETS:STUDENTS/S1.S8/;PAIRS(STUDENTS,STUDENTS)|ENDSETS,集合元素的隐式列举,运算符的优先级,三类运算符：算术运算符 逻辑运算符 关系运算符,集合循环函数,四个集合循环函数：FOR、SUM、MAX、MINfunction(setname(set_index_list)|condition:expression_list);,objective MAX=SUM(PAIRS(I,J):BENEFIT(I,J)*MATCH(I,J);FOR(STUDENTS(I):constraints SUM(PAIRS(J,K)|J#EQ#I#OR#K#EQ#I:MATCH(J,K)=1);FOR(PAIRS(I,J):BIN(MATCH(I,J);MAXB=MAX(PAIRS(I,J):BENEFIT(I,J);MINB=MIN(PAIRS(I,J):BENEFIT(I,J);,Example:,状态窗口,Solver Type:B-and-BGlobal Multistart,Model Class:LP，QP，ILP，IQP，PILP,PIQP，NLP，INLP，PINLP,State:Global OptimumLocal OptimumFeasibleInfeasibleUnboundedInterruptedUndetermined,7个选项卡(可设置80-90个控制参数),程序与数据分离,文本文件,使用外部数据文件,Cut(or Copy)Paste 方法FILE 输入数据、TEXT输出数据（文本文件）OLE函数与电子表格软件（如EXCEL）连接ODBC函数与数据库连接LINGO命令脚本文件,LG4（LONGO模型文件）LNG（LONGO模型文件）LTF（LONGO脚本文件）LDT（LONGO数据文件）LRP（LONGO报告文件）,常用文件后缀,FILE和TEXT：文本文件输入输出,MODEL:SETS:MYSET/FILE(myfile.txt)/:FILE(myfile.txt);ENDSETSMIN=SUM(MYSET(I):SHIP(I)*COST(I);FOR(MYSET(I):CON1 SHIP(I)NEED(I);CON2 SHIP(I)SUPPLY(I);DATA:COST=FILE(myfile.txt);NEED=FILE(myfile.txt);SUPPLY=FILE(myfile.txt);TEXT(result.txt)=SHIP,DUAL(SHIP),DUAL(CON1);ENDDATAEND,myfile.txt文件的内容、格式：Seattle,Detroit,Chicago,DenverCOST,NEED,SUPPLY,SHIP12,28,15,201600,1800,1200,10001700,1900,1300,1100,演示 MyfileExample.lg4,OLE：与EXCEL连接,MODEL:SETS:MYSET:COST,SHIP,NEED,SUPPLY;ENDSETSMIN=SUM(MYSET(I):SHIP(I)*COST(I);FOR(MYSET(I):CON1 SHIP(I)NEED(I);CON2 SHIP(I)SUPPLY(I);DATA:MYSET=OLE(D:JXIEBJ2004MCMmydata.xls,CITIES);COST,NEED,SUPPLY=OLE(mydata.xls);OLE(mydata.xls,SOLUTION)=SHIP;ENDDATAEND,mydata.xls文件中必须有下列名称(及数据)：CITIES，COST，NEED，SUPPLY，SOLUTION,在EXCEL中还可以通过“宏”自动调用LINGO(略)也可以将EXCEL表格嵌入到LINGO模型中(略),ODBC：与数据库连接,输入基本集合元素：setname/ODBC(datasource,tablename,columnname)/输入派生集合元素：setname/ODBC(source,table,column1,column2)/,目前支持下列DBMS:(如为其他数据库，则需自行安装驱动)ACCESS，DBASE，EXCEL，FOXPRO，ORACLE，PARADOX，SQL SERVER，TEXE FILES,使用数据库之前，数据源需要在ODBC管理器注册,输入数据：Attr_list=ODBC(source,table,column1,column2)输出数据：ODBC(source,table,column1,column2)=Attr_list,具体例子略,需要掌握的几个重要方面,1、LINDO:正确阅读求解报告（尤其要掌握敏感性分析）2、LINGO：掌握集合(SETS)的应用；正确阅读求解报告；正确理解求解状态窗口；学会设置基本的求解选项(OPTIONS)；掌握与外部文件的基本接口方法,常用优化软件,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,LINGO软件的功能与特点,LINGO模型的优点,集成了线性(非线性)/连续(整数)优化功能 具有多点搜索/全局优化功能 提供了灵活的编程语言(矩阵生成器)，可方便地输入模型 提供与其他数据文件的接口 提供与其他编程语言的接口 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),解决优化问题常用的算法,遗传算法,遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。,Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些 假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。,模拟退火算法,模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。,数学建模的常用算法,1、蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时通过模拟可以来检验自己模型的正确性。,2、数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关,键就在于这些算法，通常使用Matlab作为工具。,3、线性规划、整数规划、多元规划、二次规划等规划类问题。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo、MATLAB软件实现。,4、图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。,5、动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中。,6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法。这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。,7、网格算法和穷举法。网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。,8、一些连续离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。,9、数值分析算法。如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外