《数学建模竞中的优化问题》由会员分享，可在线阅读，更多相关《数学建模竞中的优化问题（127页珍藏版）》请在金锄头文库上搜索。
1、数学建模竞赛中的优化问题数学建模竞赛中的优化问题 数学建模 培训组 2009.3本次讲座目的v让大家了解数学建模中常常遇到的问题优化问题；v初步认识数学建模需要准备的算法，软件。优化问题v优化问题的解题步骤： 1、确定最优目标函数。 2、寻找构成目标函数的各元素应该遵守的约束条件。 3、利用相应软件或算法求解。数学规划数学规划线性规划线性规划(linear programming) 是康托洛维奇是康托洛维奇1939年提年提出的，出的， 1947年（年（G.B.Dantzig）提出求线性规划的单提出求线性规划的单纯形法（纯形法（simplemethod），），理论上趋向成熟，实际理论上趋向成熟，
2、实际上的应用也越来越广泛，几乎各行各业都可建立线上的应用也越来越广泛，几乎各行各业都可建立线性规划模型。性规划模型。 某企业要在计划期内安排生产甲、乙两种产某企业要在计划期内安排生产甲、乙两种产品，这个企业现有的生产资料是：设备品，这个企业现有的生产资料是：设备18台时，台时，原材料原材料A 4吨，原材料吨，原材料 B 12吨；已知单位产品所吨；已知单位产品所需消耗生产资料及利润如下表。问应如何确定生需消耗生产资料及利润如下表。问应如何确定生产计划使企业获利最多。产计划使企业获利最多。1 . 1 线性规划问题线性规划问题例例1生产计划问题生产计划问题表表1 产品产品资源资源甲甲乙乙资源量资源量
3、设备设备/台时台时3218原料原料A/吨吨104原料原料B/吨吨0212单位赢利单位赢利/万万元元35Formulation as a linear programming problemvx1=number of units of product 1v x2 =number of units of product 2vz=total profit from producting these two products x1, x2 are the decision variables for the model. maximize z=3x1+5x2非负约束非负约束 产品产品资源资源甲甲乙乙资
4、源量资源量设备设备/台时台时3218原料原料A/吨吨104原料原料B/吨吨0212单位赢利单位赢利/万元万元35182321+xx 设备限制设备限制 原料原料A的限制的限制 原料原料B的限制的限制相应的数学模型相应的数学模型 产品产品资源资源甲甲乙乙资源量资源量设备设备/台时台时3218原料原料A/吨吨104原料原料B/吨吨0212单位赢利单位赢利/万元万元35资源的合理利用问题资源的合理利用问题 -the allocating resources to activities一般的资源利用问题可表述为：一般的资源利用问题可表述为： 设某企业利用设某企业利用 m 种资源来生产种资源来生产 n 种
5、产品，已知种产品，已知该企业拥有的第该企业拥有的第 i 种资源的数量是种资源的数量是b i , 生产单位第生产单位第 j 种产品所消耗的第种产品所消耗的第 i 种资源的数量为种资源的数量为 aij ，第，第j种产品的种产品的单位利润是单位利润是 c j。现制定一个生产计划方案，使总利润。现制定一个生产计划方案，使总利润最大。最大。ResourceResource Usage per Unit of ActivityAmount of Resource AvailableActivity 1 2 n 12 m a11 a12 a1n a21 a22 a2n am1 am2 amnb1b2bmCo
6、ntribution to z per unit of activity c1 c1 c1z=value of overall measure of performancexj=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-价值系数价值系数ResourceResource Usage per Unit of ActivityAmount of Resource AvailableActivity 1 2 n
7、12 m a11 a12 a1n a21 a22 a2n am1 am2 amnb1b2bmContribution to z per unit of activity c1 c1 c1aij=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) )-资源系数资源系数ResourceResource Usage per Unit of Activi
8、tyAmount of Resource AvailableActivity 1 2 n 12 m a11 a12 a1n a21 a22 a2n am1 am2 amnb1b2bmContribution to z per unit of activity c1 c1 c1x1,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. 资源利用问题的数学模型为资源利用问题的数学模型为：
9、 the objective functionfunctional constrainsnonegativeconstrains假设企业决策者不考虑自己生产产品甲乙，而是将假设企业决策者不考虑自己生产产品甲乙，而是将厂里的现有资源（见表厂里的现有资源（见表1）买出。试问该厂的决策者应给）买出。试问该厂的决策者应给每种资源制定一个怎样的价格，才能获得良好收益？每种资源制定一个怎样的价格，才能获得良好收益？ 产品产品资源资源甲甲乙乙资源量资源量设备设备/台时台时3218原料原料A/吨吨104原料原料B/吨吨0212单位赢利单位赢利/万元万元35例例2资源定价问题资源定价问题问题分析问题分析解：决策
10、者显然要考虑两个因素：解：决策者显然要考虑两个因素：第一，每种资源所收回的费用应不底于自己生产第一，每种资源所收回的费用应不底于自己生产 时所获得的利润；时所获得的利润；第二，定价又不能太高，要使对方容易接受。第二，定价又不能太高，要使对方容易接受。 总之，定价要公平合理，使双方都能接受。总之，定价要公平合理，使双方都能接受。问题分析问题分析v设设y1,y2,y3分别表示这三种资源的收费单价。则分别表示这三种资源的收费单价。则由第一条原则：将用于加工产品甲或乙的所有资由第一条原则：将用于加工产品甲或乙的所有资源，如用来加工外来产品所获得的收回的费用，源，如用来加工外来产品所获得的收回的费用，应
11、不低于可获得的利润，即应不低于可获得的利润，即从工厂的决策者来看当然是越大越好。但是根据从工厂的决策者来看当然是越大越好。但是根据第二条原则，也应该使对方的支出尽可能的少；第二条原则，也应该使对方的支出尽可能的少；从而这个问题就可以转化为下述数学问题：从而这个问题就可以转化为下述数学问题：当然对价格还要有非负限制。即：当然对价格还要有非负限制。即：将该厂所有的资源都用来加工外来产品，其将该厂所有的资源都用来加工外来产品，其总收入（即对方的总支出）是总收入（即对方的总支出）是定价问题的数学模型定价问题的数学模型设某单位现有设某单位现有n个人员个人员A1,A2,An来完成来完成n项工作项工作B1,
12、B2,Bn。按工作要求，每按工作要求，每个人员需干一项工作，每项工作也需一人个人员需干一项工作，每项工作也需一人去完成。已知人员去完成。已知人员A i做工作做工作B j的效率是的效率是c ij。问应如何分配，才使总效率最好。问应如何分配，才使总效率最好。 例例3人员分配问题人员分配问题问题分析问题分析令令x ij表示分配人员表示分配人员A i完成工作完成工作 B j的决策变量。的决策变量。 x ij = 1 表示分配表示分配Ai干工作干工作Bj xij = 0 表示不分配表示不分配Ai干工作干工作Bj 按问题要求，每人要做一项工作，每项工作需一人去做。按问题要求，每人要做一项工作，每项工作需一
13、人去做。建立该问题的数学模型的过程：建立该问题的数学模型的过程：问题分析问题分析派工方案的总效益派工方案的总效益对工作对工作Bj；要求一人员去完成要求一人员去完成对人员对人员Ai；要求承担一项工作：要求承担一项工作：分配问题的数学模型分配问题的数学模型某公司要运销一种物资。该物资有甲、乙两个产地，某公司要运销一种物资。该物资有甲、乙两个产地，产量分别是产量分别是2000吨、吨、1000吨；另有吨；另有A、B、C三个销三个销地，销量分别是地，销量分别是1700吨、吨、1100吨、吨、200吨。已知该物吨。已知该物资的单位运价如表资的单位运价如表1-2。问应如何确定调运方案，才。问应如何确定调运方
14、案，才能使在产销平衡的条件下，总运费最低？能使在产销平衡的条件下，总运费最低？例例4物资运输问题物资运输问题销销地地单位运价单位运价产产地地甲甲乙乙销销量量ABC2125751513717001100200产产量量20001000表表3v分析分析确定调运方案就是确定从不同产地到各个销地的确定调运方案就是确定从不同产地到各个销地的运输量运输量。设设xij表示这些要找的运量。表示这些要找的运量。即即x11、x12、x13分别表示从甲地调往分别表示从甲地调往A、B、C三地的运量。三地的运量。x21、x22、x23分别表示从已地调往分别表示从已地调往A、B、C三地的运量。三地的运量。由于要求产销平衡：
15、由于要求产销平衡：从两产地甲、乙分别调往三销地从两产地甲、乙分别调往三销地A、B、C的物资数的物资数量应该分别等于两产地甲、乙的产量，所以量应该分别等于两产地甲、乙的产量，所以xij应应满足：满足：运到运到A、B、C三销地的物资数量应分别等于三销地的物资数量应分别等于A、B、C三销地的销量，所以三销地的销量，所以x ij 还应该满足：还应该满足： 由于由于xij是运量，不能是负数：是运量，不能是负数：调运方案的总运费为：调运方案的总运费为：建立产销平衡下运费最省的调运问题的建立产销平衡下运费最省的调运问题的数学模型数学模型：运输问题的数学模型运输问题的数学模型销销地地单位运价单位运价产产地地甲
16、甲乙乙销销量量ABC2125751513717001100200产产量量20001000 某种物资有某种物资有 m 个产地，个产地，A1 ,A2, ,Am ，产量分别产量分别a1,a2, ,am个单位，另有个单位，另有 n 个销地个销地B1,B2 , ,Bn , 销销量分别是量分别是b1,b2, ,bn个单位。假设产销是平衡的，个单位。假设产销是平衡的，即总产量等于总销量。已知由产地即总产量等于总销量。已知由产地A i 向销地向销地B j 运输一运输一个单位物资的运价个单位物资的运价x ij ；问应该怎样调运物资才能使总；问应该怎样调运物资才能使总运费最省。运费最省。令令xij表示表示由产地由
17、产地Ai向销地向销地Bj的运量的运量运输问题的一般提法运输问题的一般提法：运输问题的运输问题的数学模型数学模型为：为：上述例子，虽然有不同的实际内容，上述例子，虽然有不同的实际内容，但是它们都是要求一组变量的值，这组值满足一但是它们都是要求一组变量的值，这组值满足一定的约束条件，如资源限制、供求关系等。定的约束条件，如资源限制、供求关系等。这种约束条件都可以用一组这种约束条件都可以用一组线性不等式线性不等式或或线性方线性方程程来表示，同时使某个来表示，同时使某个线性函数指标线性函数指标达到最大或最达到最大或最小。具有这些特征的问题，称为小。具有这些特征的问题，称为线性规划问题线性规划问题。1.
18、2 图解法图解法-graphical method 图解法适用于来解只有图解法适用于来解只有两个变量两个变量的线性规划问题的线性规划问题.The feasible regionisthecollectionofallfeasiblesolutions.A feasible solutionisasolutionforwhichalltheconstraintsaresatisfied.Itispossibleforaproblemtohavenotfeasiblesolutions.An in feasible solutionisasolutionforwhichatleastonecons
19、traintisviolated.An optimal solutionisafeasiblesolutionthathasthemostfavorablevalue(thelargestorthesmallest)oftheobjectivefunction.Itispossibleforaproblemtohavemorethanoneoptimalsolution.Anyproblemhavingmultipleoptimalsolutionswillhaveaninfinitenumberofthem.例例1 图解法求解线性规划问题图解法求解线性规划问题图解法简单直观，有助于了解线性规
20、划问题求解图解法简单直观，有助于了解线性规划问题求解的基本原理和思想。的基本原理和思想。下面举例说明图解法求解线性规划问题的步骤。下面举例说明图解法求解线性规划问题的步骤。解解该线性规划问题的可行域见图该线性规划问题的可行域见图1。 2 4 6 8 x1x2 8 6 4 2 0x1=42 x 2 = 123x1+2x2=18QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)图解法解题过程图解法解题过程图图1-1可行域可行域-thefeasibleregion 2 4 6 x1x2 8 6 4 2 0x1=42 x 2 = 123x1+2x2=18QQ0(0,0)Q1(0,
21、6)Q2(2,6)Q3(4,3)Q4(4,0)3x1+5x2=z=363x1+5x2=z=203x1+5x2=z=0图解法解题过程图解法解题过程图图1-1让直线束让直线束沿正法线沿正法线在可行域在可行域Q移动，移动，通过点通过点(2,6)的直线：的直线：注：本问题只有唯一最优解。注：本问题只有唯一最优解。 例例例例1 1的最优生产方案为：的最优生产方案为：的最优生产方案为：的最优生产方案为： 生生生生产产品甲为产产品甲为产产品甲为产产品甲为2 2件，生产产品乙件，生产产品乙件，生产产品乙件，生产产品乙6 6件，最大利润为件，最大利润为件，最大利润为件，最大利润为3636万元。万元。万元。万元。
22、x1 8 6 4 2 0x1=4QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)x1注：注：问题的问题的可行域可行域是是一个有界的一个有界的凸多边形凸多边形，其边界由其边界由5条直线所围成：条直线所围成：X1=0,X2=0X1=42x2=123x1+2x2=18最优解最优解(2,6)在在凸多边形的顶点凸多边形的顶点Q2上。上。x2 8 6 4 2 0x1=4QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)x1例例2解解该问题的可行域该问题的可行域Q是一个有界的凸多边形（是一个有界的凸多边形（如图如图1-2）。）。-x1+x2=0X1+x2=56x
23、1+2x2=213x 1 + x 2 = z =03x 1 + x 2 = z =63x 1 + x 2 = z =21/2A(11/4,9/4)B(21/6,0)x1x2让直线束让直线束3x1+x2=z沿正法线向移动，到沿正法线向移动，到达线段达线段AB时，使时，使Z达到最大。所以线段达到最大。所以线段AB上的每一点都可上的每一点都可使使Z达到最大值，达到最大值，注：本问题有无穷多注：本问题有无穷多个最优解。个最优解。 -x1+x2=0x1+x2=56x1+2x2=213x 1 + x 2 = z =03x 1 + x 2 = z =63x 1 + x 2 = z =21/2A(11/4,9
24、/4)B(21/6,0)x1x2例例3图图1-3解解该问题的可行域是一个无界的凸多边形该问题的可行域是一个无界的凸多边形让直线束让直线束沿其负法线方向移动，可以无限沿其负法线方向移动，可以无限制地移动下去，一直与制地移动下去，一直与相交，所以其最小值为相交，所以其最小值为；即；即函数函数在在上无下界。上无下界。注：本问题有可行解，注：本问题有可行解，但无最优解。但无最优解。例例4解解该问题的可行域是空的，即无可行解该问题的可行域是空的，即无可行解X1-x2=-1x1+x2=-1注：本问题无可行解，更无最优解。注：本问题无可行解，更无最优解。 进一步讨论进一步讨论给定只有给定只有两个变量两个变量
25、的线性规划问题：的线性规划问题：图解法求解线性规划问题的步骤如下：图解法求解线性规划问题的步骤如下：若若若若是空集，则说明线性规划问题无可行解。是空集，则说明线性规划问题无可行解。是空集，则说明线性规划问题无可行解。是空集，则说明线性规划问题无可行解。 如果如果如果如果不是空集，那么不是空集，那么不是空集，那么不是空集，那么是平面上的一个凸多边形，是平面上的一个凸多边形，是平面上的一个凸多边形，是平面上的一个凸多边形，这个凸多边形可能是有界的（封闭的），也可能是无界的这个凸多边形可能是有界的（封闭的），也可能是无界的这个凸多边形可能是有界的（封闭的），也可能是无界的这个凸多边形可能是有界的（封
26、闭的），也可能是无界的（不封闭的）。（不封闭的）。（不封闭的）。（不封闭的）。表示一个以表示一个以表示一个以表示一个以 z z为参数的平行直线束。为参数的平行直线束。为参数的平行直线束。为参数的平行直线束。沿正法线方向沿正法线方向移动可得最大值，沿负移动可得最大值，沿负法线方向法线方向移动可得最小值。移动可得最小值。注意注意:一定要精确一定要精确在平面在平面在平面在平面上取定直角坐标系，画出上取定直角坐标系，画出上取定直角坐标系，画出上取定直角坐标系，画出可行域可行域可行域可行域，记为，记为，记为，记为。通过以上例子可以看出，两个变量的线性规划的解可通过以上例子可以看出，两个变量的线性规划的解
27、可能有以下能有以下4种情况：种情况： 有唯一的最优解。有唯一的最优解。 最优解一定是可行域的一个顶点。最优解一定是可行域的一个顶点。 有无穷多的最优解。有无穷多的最优解。 最优解是可行域的一段边界。最优解是可行域的一段边界。 有可行解，但无最优解。目标函数值无界有可行解，但无最优解。目标函数值无界. 无可行解。无可行解。 （最大值点（最小值点）一定在可行域的边界上）（最大值点（最小值点）一定在可行域的边界上） 问题是对于一般的线性规划问题有无类似结论，问题是对于一般的线性规划问题有无类似结论，结论成立的判定准则如何。结论成立的判定准则如何。 1.3 整数规划整数规划例例1、集装箱运货、集装箱运
28、货货物货物体积体积(米米3/箱箱)重量重量(百公斤百公斤/箱箱)利润利润(千元千元/箱箱)甲甲5220乙乙4510装运限制装运限制2413解：设解：设X1 , X2 为甲、乙两货物各托运箱数为甲、乙两货物各托运箱数5X1+4X2 242X1+5X2 13X1 ,X2 0 0X1 ,X2为整数为整数maxZmaxZ = 20 = 20 X1 + 10 X2例例2、背包问题、背包问题背包可再装入背包可再装入8单位重量，单位重量，10单位体积物品单位体积物品物品物品名称名称重量重量体积体积价值价值1书书52202摄像机摄像机31303枕头枕头14104休闲食品休闲食品23185衣服衣服4515解：解
29、：Xi为是否带第为是否带第i 种物品种物品maxZ=20X1 + 30X2 +10X3+18X4 +15X55X1+3X2 +X3 +2X4 +4X5 82X1+X2 +4X3 +3X4 +5X5 10Xi为为0, 1一般形式：一般形式：,整数整数(1)、Xi为为i 物品携带数量物品携带数量 ai为为i 物品单位重量物品单位重量 ci为为i 物品重要性估价物品重要性估价b为最大负重为最大负重(2)、投资决策投资决策Xi为在为在i 地区建厂规模地区建厂规模 ai为在为在i 地区建厂基建费用地区建厂基建费用 ci为在为在i 地区建厂单位利润地区建厂单位利润b为最大资本为最大资本(3)、Xi 取取0
30、或或1时，可作项目投资模型时，可作项目投资模型例例3、选址问题、选址问题A1A3B2B4B3B1A2Ai:可建仓库地点，容量可建仓库地点，容量ai ,投资费用投资费用bi ，建，建2个个Bj:商店，需求商店，需求dj ( j=14)Cij:仓库仓库i 到商店到商店j 的单位的单位运费运费问：选择适当地点建仓库，在满足商店需问：选择适当地点建仓库，在满足商店需求条件下，总费用最小。求条件下，总费用最小。解：设解：设Xi ( i=1,2,3)为是否在为是否在Ai 建仓库建仓库 yij ( i=1,2,3, j=14)由由i仓库向仓库向 j商店运货量商店运货量y11 + y21 = d= d1 1y
31、12 + y22 + y32 = d= d2 2y23+ y33 = d= d3 3y14 + y24 + y34 = d= d4 4x1 + x2 + x3= = 2y11 + y12 + y14 a a1 1x1y21 + y22 + y23 + y24 a a2 2x2y32 + y33 + y34 a a3 3x3xi 为为01， yij 0 0混合整数规划混合整数规划01决策变量的应用决策变量的应用可用于相互排斥计划中可用于相互排斥计划中例例1、运输方式：火车、船。、运输方式：火车、船。火车：火车：5X1+4X2 24 (体积体积)船：船：7X1+3X2 45 (体积体积)maxZ=
32、20X1 + 10X2 2X1+5X2 135X1+4X2 24+MX37X1+3X2 45+M(1-X3 )X1 , X2 0 整数整数X3为为0或或1 M0当当X3 =0 =0 火车火车 X3 =1 =1 船船 例例2、ai1x1+ai2x2 +ainxn b bi i ( (i=1,m) )互相排斥互相排斥m个约束，只有一个起作用个约束，只有一个起作用ai1x1+ainxn b bi i+yi M M ( (i=1,m) )y1 +ym =m-1yi为为0或或1M0例例4:聘用方案聘用方案决策变量决策变量：周一至周日每天：周一至周日每天(新新)聘用人数聘用人数x1, x2,x7目标函数目
33、标函数：7天天(新新)聘用人数之和聘用人数之和约束条件约束条件：周一至周日每天需要人数：周一至周日每天需要人数连续工作连续工作5天天周一工作的应是周一工作的应是(上上)周四至周一聘用周四至周一聘用的的设系统已进入稳态（不是开始的几周）设系统已进入稳态（不是开始的几周）聘用方案聘用方案整数规划整数规划模型模型(IP)(IP)丁的蛙泳成绩退步到丁的蛙泳成绩退步到115”2；戊的自由泳成绩进戊的自由泳成绩进步到步到57”5,组成接力队的方案是否应该调整组成接力队的方案是否应该调整？如何选拔队员组成如何选拔队员组成4 4 100100米混合泳接力队米混合泳接力队? ?0-1规划规划 混合泳接力队的选拔
34、混合泳接力队的选拔 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”4例例5：5名候选人的名候选人的百米成绩百米成绩穷举法穷举法：组成接力队的方案共有组成接力队的方案共有5!=120种种。目标目标函数函数若选择队员若选择队员i参加泳姿参加泳姿j 的比赛，记的比赛，记xij=1, , 否则记否则记xij=0 0-1规划模型规划模型 cij( (秒秒) )队员队员i 第第j 种泳姿的百米成绩种泳姿的百米成绩约束约束条
35、件条件每人最多入选泳姿之一每人最多入选泳姿之一ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有每种泳姿有且只有1 1人人 0-1规划规划:整数规划的特例整数规划的特例整数规划问题整数规划问题一般形式一般形式整数线性规划整数线性规划(ILP)目标和约束均为线性函数目标和约束均为线性函数整数非线性规划整数非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数整数规划问题的分类整数规划问题的分类纯纯(全全)整数规划整数规
36、划(PIP)决策变量均为整数决策变量均为整数混合整数规划混合整数规划(MIP)决策变量有整数，也有实数决策变量有整数，也有实数0-1规划规划决策变量只取决策变量只取0或或1取消整数规划中决策变量为整数的限制（松弛），对取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题应的连续优化问题称为原问题的松弛问题整数规划问题对应的松弛问题整数规划问题对应的松弛问题松弛问题松弛整数规划问题最优解最优解整数非整数整数舍入下界（对Min问题）上界（对Max问题）非最优解用连续优化方法求解松弛问题，如果松弛问题最优解（分量）全为整数，则也是原整数规划问题的最优解对松弛问题的最优解
37、（分量）舍入为整数，得到的往往不是原整数规划问题的最优解（甚至不是可行解）IPIP可行解对应于整点可行解对应于整点A(2,2)A(2,2)和和B(1,1),B(1,1),而最优解为而最优解为A A点点. .但但LPLP松弛的最优解为松弛的最优解为C(3.5,2.5)C(3.5,2.5) 目标函数下降方向目标函数下降方向 x1 1x2 2CABOx1x20Po69Zmax56去掉整数限制后，可行域为点（0,0), (6,0), (0,5), P (2.25,3.75) 围成的4边形从LP最优解经过简单的 “移动”不一定能得到IP最优解例例1.6基本思想：基本思想：隐式地枚举一切可行解（隐式地枚举
38、一切可行解（“分而治之”）所所谓谓分分枝枝，就就是是逐逐次次对对解解空空间间（可可行行域域）进进行行划划分分；而而所所谓谓定定界界，是是指指对对于于每每个个分分枝枝（或或称称子子域域），要要计计算算原原问问题题的的最最优优解解的的下下界界（对对极极小小化化问问题题）. . 这这些些下下界界用用来来在在求求解解过过程程中中判判定定是是否否需需要要对对目目前前的的分分枝枝进进一一步步划划分分，也就是尽可能去掉一些明显的非最优点，避免完全枚举也就是尽可能去掉一些明显的非最优点，避免完全枚举. . 分枝定界法（分枝定界法（B&B:BranchandBound）对于极小化极小化问题，在子域上解LP，其最
39、优值是IP限定在该子域时的下界；IP任意可行点的函数值是IP的上界。这里仅介绍整数线性规划的分枝定界算法这里仅介绍整数线性规划的分枝定界算法假设假设A产销平衡产销平衡假设假设Bp随随x(两种牌号两种牌号)增加而减小，呈线性关系增加而减小，呈线性关系例例1：产销计划问题：产销计划问题某厂生产两个牌号的同一种产品，如何确定产量使利润最大某厂生产两个牌号的同一种产品，如何确定产量使利润最大1.4 二次规划模型二次规划模型目标目标利润最大利润最大=（100-x1-0.1 x2-2）x1+（280-0.2x1-2x2-3）x2=98 x1+277 x2x120.3 x1 x22x22约束约束x1+ x2
40、100x12 x2x1, x20二次规划模型二次规划模型(QP)若还要求产量为整数，则是整数二次规划模型若还要求产量为整数，则是整数二次规划模型(IQP)1.5 非线性规划模型非线性规划模型例例2：选址问题：选址问题某公司有某公司有6个建筑工地，位置坐标为个建筑工地，位置坐标为(ai,bi)(单位：公里单位：公里),水泥日用量水泥日用量di(单位：吨）单位：吨）假设：假设：料场料场和工地之间和工地之间有直线道路有直线道路用例中数据计算，最优解为总吨公里数为总吨公里数为总吨公里数为总吨公里数为136.2136.2线性规划模型线性规划模型(LP)决策变量：决策变量：ci j(料场料场j到到工地工地
41、i的运量）的运量）12维维选址问题：选址问题：NLPNLP2）改建两个新料场，需要确定新料场位置）改建两个新料场，需要确定新料场位置(xj,yj)和运量和运量cij，在其它条件不变下使总吨公里数最小。在其它条件不变下使总吨公里数最小。决策变量：决策变量：ci j，(xj,yj)16维维非线性规划模型非线性规划模型(NLP)优化建模与优化建模与LINDO/LINGO软件软件原书相关信息原书相关信息谢金星谢金星,薛毅编著薛毅编著,清华大学出版社清华大学出版社,2005年年7月第月第1版版.http:/ : 在一定条件下，寻求使目标最大在一定条件下，寻求使目标最大( (小小) )的决策的决策 优化问
42、题三要素：优化问题三要素：决策变量决策变量；目标函数目标函数；约束条件约束条件约约束束条条件件决策变量决策变量优化问题的一般形式优化问题的一般形式无约束优化无约束优化(没有约束没有约束)与约束优化与约束优化(有约束有约束)可行解（只满足约束）与最优解可行解（只满足约束）与最优解(取到最优值取到最优值)目标函数目标函数局部最优解与整体最优解局部最优解与整体最优解局部最优解局部最优解(LocalOptimalSolution,如如x1)整体最优解整体最优解(GlobalOptimalSolution,如如x2)x*f(x)x1x2o优化模型的优化模型的简单分类简单分类线性规划线性规划(LP)目标和
43、约束均为线性函数目标和约束均为线性函数非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数二次规划二次规划(QP)目标为二次函数、约束为线性目标为二次函数、约束为线性整数规划整数规划(IP)决策变量决策变量(全部或部分全部或部分)为整数为整数整数整数线性线性规划规划(ILP)，整数，整数非线性非线性规划规划(INLP)纯整数规划纯整数规划(PIP),混合整数规划混合整数规划(MIP)一般整数规划，一般整数规划，0-1（整数）规划（整数）规划连连续续优优化化离离散散优优化化数学规划数学规划优化模型的简单分类和求解难度优化模型的简单分类和求解难度 优化线性规划非线性规
44、划二次规划连续优化整数规划 问题求解的难度增加2.优化问题的建模实例优化问题的建模实例例例1: 1: 家具厂生产计划家具厂生产计划例例2: 2: 奶制品生产计划奶制品生产计划 例例3: 3: 运输问题运输问题线性规划模型线性规划模型1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶时间时间480小时小时 至多加工至多加工100公斤公斤A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工
45、人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：例例2:奶制品生产计划奶制品生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天
46、每天线性规划模型的解的几种情况线性规划模型的解的几种情况 线性规划问题线性规划问题有有可可行行解解(Feasible)无无可可行行解解（Infeasible）有有最最优优解解（Optimal）无无最最优优解解(Unbounded)无无约约束束优优化化更多的优化问题更多的优化问题线线性性规规划划非非线线性性规规划划网网络络优优化化组组合合优优化化整整数数规规划划不不确确定定规规划划多多目目标标规规划划目目标标规规划划动动态态规规划划连续优化连续优化离散优化离散优化从其他角度分类从其他角度分类应用广泛：应用广泛：生产和运作管理、经济与金融、图论和网生产和运作管理、经济与金融、图论和网络优化、目标规
47、划问题、对策论、排队论、存储论，络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等以及更加综合、更加复杂的决策问题等实际问题规模往往较大，用软件求解比较方便实际问题规模往往较大，用软件求解比较方便LINDO / LINGO软件使用简介软件使用简介使用使用LINDOLINDO的一些注意事项的一些注意事项1.“”（或（或“=”（或（或“=”）功能相）功能相同同2.变量与系数间可有空格变量与系数间可有空格(甚至回车甚至回车), 但无运算符但无运算符3.变量名以字母开头，不能超过变量名以字母开头，不能超过8个字符个字符4.变量名不区分大小写（包括变量名不区分大小写（包括L
48、INDO中的关键字）中的关键字）5.目标函数所在行是第一行，第二行起为约束条件目标函数所在行是第一行，第二行起为约束条件6.行号行号(行名行名)自动产生或人为定义。行名以自动产生或人为定义。行名以“）”结结束束7.行中注有行中注有“!”符号的后面部分为注释。如符号的后面部分为注释。如: ! Its Comment.8.在模型的任何地方都可以用在模型的任何地方都可以用“TITLE” 对模型命名对模型命名（最多（最多72个字符），如：个字符），如： TITLE This Model is only an Example9.变量不能出现在一个约束条件的右端变量不能出现在一个约束条件的右端10.表达式
49、中不接受括号表达式中不接受括号“( )”和逗号和逗号“,”等任何符号等任何符号, 例例: 400(X1+X2)需写为需写为400X1+400X211.表达式应化简，如表达式应化简，如2X1+3X2- 4X1应写成应写成 -2X1+3X212.缺省假定所有变量非负；可在模型的缺省假定所有变量非负；可在模型的“END”语句后语句后用用“FREE name”将变量将变量name的非负假定取消的非负假定取消13.可在可在 “END”后用后用“SUB” 或或“SLB” 设定变量上下界设定变量上下界 例如：例如： “sub x1 10”的作用等价于的作用等价于“x1=10” 但用但用“SUB”和和“SLB
50、”表示的上下界约束不计入模型表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析。的约束，也不能给出其松紧判断和敏感性分析。14. “END”后对后对0-1变量说明：变量说明：INT n 或或 INT name15. “END”后对整数变量说明：后对整数变量说明：GIN n 或或 GIN name使用使用LINDOLINDO的一些注意事项的一些注意事项二次规划规划(QP)问题vLINDO可求解二次规划可求解二次规划(QP)问题，但输入方式较问题，但输入方式较复杂，因为在复杂，因为在LINDO中不许出现非线性表达式中不许出现非线性表达式v需要为每一个实际约束增加一个对偶变量需要为每
51、一个实际约束增加一个对偶变量（LAGRANGE乘子），在实际约束前增加有关乘子），在实际约束前增加有关变量的一阶最优条件，转化为互补问题变量的一阶最优条件，转化为互补问题v“END”后面使用后面使用QCP命令指明实际约束开始的行命令指明实际约束开始的行号，然后才能求解号，然后才能求解v建议总是用建议总是用LINGO解解QP注意注意对对QP和和IP: 敏感性分析意义不大敏感性分析意义不大状态窗口状态窗口（LINDO Solver Status） v当前状态：已达最优解当前状态：已达最优解v迭代次数：迭代次数：18次次v约束不满足的约束不满足的“量量”(不不是是“约束个数约束个数”)：0v当前的目
52、标值：当前的目标值：94v最好的整数解：最好的整数解：94v整数规划的界：整数规划的界：93.5v分枝数：分枝数：1v所用时间：所用时间：0.00秒（太快秒（太快了，还不到了，还不到0.005秒）秒）v刷新本界面的间隔刷新本界面的间隔:1(秒秒)选项设置选项设置Preprocess：预处理预处理(生成割平面生成割平面)；PreferredBranch：优先的分枝方式：优先的分枝方式：“Default”（缺省方式）、缺省方式）、“Up”（向上取整优先）、向上取整优先）、“Down”（向下取整优先）；向下取整优先）；IPOptimalityTol：IP最优值允许的误最优值允许的误差上限（一个百分数
53、，如差上限（一个百分数，如5%即即0.05）；）；IPObjectiveHurdle：IP目标函数的篱目标函数的篱笆值，即只寻找比这个值更优最优解笆值，即只寻找比这个值更优最优解（如当知道当前模型的某个整数可行解（如当知道当前模型的某个整数可行解时，就可以设置这个值）；时，就可以设置这个值）；IPVarFixingTol：固定一个整数变量固定一个整数变量取值所依据的一个上限（如果一个整数取值所依据的一个上限（如果一个整数变量的判别数（变量的判别数（REDUCEDCOST）的的值很大，超过该上限，则以后求解中把值很大，超过该上限，则以后求解中把该整数变量固定下来）。该整数变量固定下来）。Nonz
54、eroLimit：非零系数的个数上限；非零系数的个数上限；IterationLimit：最大迭代步数；最大迭代步数；InitialContraintTol：约束的初始误差上限；约束的初始误差上限；FinalContraintTol：约束的最后误差上限；约束的最后误差上限；EnteringVarTol：进基变量的进基变量的REDUCEDCOST的误差限；的误差限；PivotSizeTol：旋转元的误差限旋转元的误差限Report/Statistics第一行：模型有第一行：模型有5行（约束行（约束4行），行），4个变量，两个整数变量（没有个变量，两个整数变量（没有0-1变量），从第变量），从第4行
55、开始是二次规划的实际约束。行开始是二次规划的实际约束。第二行：非零系数第二行：非零系数19个，约束中非零系数个，约束中非零系数12个个(其中其中6个为个为1或或-1)，模型密度为模型密度为0.760(密度密度=非零系数非零系数/行数行数(变量数变量数)。第三行的意思：按绝对值看，系数最小、最大分别为第三行的意思：按绝对值看，系数最小、最大分别为0.3和和277。第四行的意思：模型目标为极小化；小于等于、等于、大于等于约第四行的意思：模型目标为极小化；小于等于、等于、大于等于约束分别有、个；广义上界约束（束分别有、个；广义上界约束（GUBS）不超过个；不超过个；变量上界约束（变量上界约束（VUB
56、S）不少于个。所谓不少于个。所谓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 CON
57、STRAINT 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= 0LINGO软件简介软件简介目标与约束段目标与约束段集合段（集合段（SETSENDSETS）数据段（数据段（DATAENDDATA）初始段（初始段（INITENDINIT）计算段计算段(CALCENDCALC)-LINGO9.0LINGO模型的构成：模型的构成：5个段
58、个段LINGO模型的优点模型的优点包含了包含了LINDO的全部功能的全部功能提供了灵活的编程语言（矩阵生成器）提供了灵活的编程语言（矩阵生成器）集合的类型集合的类型集合集合派生集合派生集合基本集合基本集合稀疏集合稀疏集合稠密集合稠密集合元素列表法元素列表法元素过滤法元素过滤法直接列举法直接列举法隐式列举法隐式列举法setname /member_list/ : attribute_list;setname(parent_set_list) /member_list/ : attribute_list;SETS: CITIES /A1,A2,A3,B1,B2/; ROADS(CITIES, CI
59、TIES)/ A1,B1 A1,B2 A2,B1 A3,B2/:D; ENDSETSSETS: STUDENTS /S1.S8/; PAIRS( STUDENTS, STUDENTS) | &2 #GT# &1: BENEFIT, MATCH;ENDSETS集合元素的集合元素的隐式列举隐式列举类型型隐式列式列举格式格式示例示例示例集合的元素示例集合的元素数字型数字型 1.n1.51, 2, 3, 4, 5字符字符-数字型数字型stringM.stringNCar101.car208Car101, car102, , car208星期型星期型 dayM.dayNMON.FRIMON, TUE,
60、WED, THU, FRI月份型月份型 monthM.monthNOCT.JANOCT, NOV, DEC, JAN年份年份-月份型月份型monthYearM.monthYearNOCT2001.JAN2002OCT2001, NOV2001, DEC2001, JAN2002运算符的优先级运算符的优先级 优先先级运算符运算符最高最高#NOT# （负负号）号）* /+ （减法）（减法）#EQ# #NE# #GT# #GE# #LT# #LE# #AND# #OR#最低最低(=)三类运算符：三类运算符：算术运算符算术运算符逻辑运算符逻辑运算符关系运算符关系运算符集合循环函数集合循环函数四个集合循
61、环函数：四个集合循环函数：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(PAIR
62、S( I, J): BENEFIT( I, J);MINB=MIN(PAIRS( I, J): BENEFIT( I, J);Example:状态窗口状态窗口Solver Type:B-and-BGlobal MultistartModel Class: LP， QP，ILP， IQP，PILP, PIQP，NLP，INLP，PINLP State:Global OptimumLocal OptimumFeasibleInfeasibleUnboundedInterruptedUndetermined7 7个选项卡个选项卡( (可设置可设置80-9080-90个控制参数个控制参数) ) 程序与
63、数据分离程序与数据分离文文本本文文件件使用外部数据文件使用外部数据文件Cut(orCopy)Paste方法方法FILE输入数据、输入数据、TEXT输出数据（文本文件）输出数据（文本文件）OLE函数与电子表格软件（如函数与电子表格软件（如EXCEL）连接连接ODBC函数与数据库连接函数与数据库连接LINGO命令脚本文件命令脚本文件LG4（LONGO模型文件）模型文件）LNG（LONGO模型文件）模型文件）LTF（LONGO脚本文件）脚本文件）LDT（LONGO数据文件）数据文件）LRP（LONGO报告文件）报告文件）常用文件后缀常用文件后缀FILEFILE和和TEXTTEXT：文本文件输入输出文
64、本文件输入输出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) NEED( I); CON2 SHIP( I) SUPPLY( I);DATA: MYSET =OLE(D:JXIEBJ2004MCMmydata.xls,CITIES); COST,NEED,SUPPLY =OLE(mydata.xls); OLE(mydat
65、a.xls,SOLUTION)=SHIP; ENDDATAEND mydata.xls文件中必须有下列名称(及数据)： CITIES， COST，NEED，SUPPLY，SOLUTION在在EXCEL中还可以通过中还可以通过“宏宏”自动调用自动调用LINGO(略略)也可以将也可以将EXCEL表格嵌入到表格嵌入到LINGO模型中模型中(略略)ODBC ODBC ：与数据库连接与数据库连接输入基本集合元素：输入基本集合元素：setname/ODBC(datasource,tablename,columnname)/输入派生集合元素：输入派生集合元素：setname/ODBC(source,tabl
66、e,column1,column2)/目前支持下列目前支持下列DBMS:(如为其他数据库，则需自行安装驱动如为其他数据库，则需自行安装驱动)ACCESS，DBASE，EXCEL，FOXPRO，ORACLE，PARADOX，SQLSERVER，TEXEFILES使用数据库之前，数据源需要在使用数据库之前，数据源需要在ODBC管理器注册管理器注册输入数据：输入数据：Attr_list=ODBC(source,table,column1,column2)输出数据：输出数据：ODBC(source,table,column1,column2)=Attr_list具体例子略具体例子略需要掌握的几个重要方
67、面需要掌握的几个重要方面1、LINDO:正确阅读求解报告（尤其要掌握敏感性分析）正确阅读求解报告（尤其要掌握敏感性分析）2、LINGO：掌握集合掌握集合(SETS)的应用；的应用；正确阅读求解报告；正确阅读求解报告；正确理解求解状态窗口；正确理解求解状态窗口；学会设置基本的求解选项学会设置基本的求解选项(OPTIONS)；掌握与外部文件的基本接口方法掌握与外部文件的基本接口方法常用优化软件常用优化软件 1.LINDO/LINGO软件软件2.MATLAB优化工具箱优化工具箱/Mathematic的优化功能的优化功能3.SAS(统计分析统计分析)软件的优化功能软件的优化功能4.EXCEL软件的优化
68、功能软件的优化功能5.其他（如其他（如CPLEX等）等）MATLABMATLAB优化工具箱优化工具箱能求解的优化模型能求解的优化模型优化工具箱优化工具箱3.0(MATLAB7.0R14)连续优化连续优化离散优化离散优化无约束优化无约束优化非线性非线性极小极小fminunc非光滑非光滑(不可不可微微)优化优化fminsearch非线性非线性方方程程(组组)fzerofsolve全局全局优化优化暂缺暂缺非线性非线性最小二乘最小二乘lsqnonlinlsqcurvefit线性规划线性规划linprog纯纯0-1规划规划bintprog一般一般IP(暂缺暂缺)非线性规划非线性规划fminconfmin
69、imaxfgoalattainfseminf上下界约束上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性约束线性最小二乘最小二乘lsqnonneglsqlin约束优化约束优化二次规划二次规划quadprogLINDO LINDO 公司软件产品简要介绍公司软件产品简要介绍 美国芝加哥美国芝加哥(Chicago)大学的大学的LinusSchrage教授于教授于1980年前后开发年前后开发,后来成立后来成立LINDO系统公司（系统公司（LINDOSystemsInc.），），网址：网址：http:/LINDO:LinearINteractiveandDiscret
70、eOptimizer(V6.1)LINDOAPI:LINDOApplicationProgrammingInterface(V4.1)LINGO:LinearINteractiveGeneralOptimizer(V10.0)WhatsBest!:(SpreadSheete.g.EXCEL)(V8.0)演演示示(试用试用)版、高级版、超级版、工业版、扩展版版、高级版、超级版、工业版、扩展版（求解（求解问题规模问题规模和和选件选件不同）不同）LINDO/LINGO软件能求解的模型软件能求解的模型优化优化线性规划线性规划非线性规划非线性规划二次规划二次规划连续优化连续优化整数规划整数规划LINDO
71、LINGOLINGO软件的功能与特点软件的功能与特点LINGO模型的优点模型的优点集成了线性集成了线性(非线性非线性)/连续连续(整数整数)优化功能优化功能具有多点搜索具有多点搜索/全局优化功能全局优化功能提供了灵活的编程语言提供了灵活的编程语言(矩阵生成器矩阵生成器)，可方便地，可方便地输入模型输入模型提供与其他数据文件的接口提供与其他数据文件的接口提供与其他编程语言的接口提供与其他编程语言的接口LINDOAPI可用于自主开发可用于自主开发运行速度较快运行速度较快LPQPNLPIP全局优化全局优化(选选)ILPIQPINLPLINGOLINGO软件的求解过程软件的求解过程 LINGO预处理程
72、序预处理程序线性优化求解程序线性优化求解程序非线性优化求解程序非线性优化求解程序分枝定界管理程序分枝定界管理程序1.确定常数确定常数2.识别类型识别类型1.单纯形算法单纯形算法2.内点算法内点算法(选选)1、顺序线性规划法、顺序线性规划法(SLP)2、广义既约梯度法、广义既约梯度法(GRG)(选选)3、多点搜索、多点搜索(Multistart)(选选)建模时需要注意的几个基本问题建模时需要注意的几个基本问题 1、尽量使用实数优化，减少整数约束和整数变量尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符
73、号函数、多个变量求最如：尽量少使用绝对值、符号函数、多个变量求最大大/最小值、四舍五入、取整函数等最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量尽量使用线性模型，减少非线性约束和非线性变量的个数的个数（如（如x/y5改为改为x5y）4、合理设定变量上下界，尽可能给出变量初始值合理设定变量上下界，尽可能给出变量初始值5、模型中使用的参数数量级要适当模型中使用的参数数量级要适当(如小于如小于103)解决优化问题常用的算法遗传算法遗传算法 遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。 Darwin进化论最重要的是适者生存原理。它认为每一物种在发
74、展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。 Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质； 所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。 遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些 假设解置于
75、问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体” 群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。 模拟退火算法模拟退火算法模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。 数学建模的常用算法 1、蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时通过模拟可以来检验自己模型的正确性。2、数据
76、拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具。 3、线性规划、整数规划、多元规划、二次规划等规划类问题。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo、MATLAB软件实现。 4、图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中。 6、最优化理论的三大非经典算法：模
77、拟退火法、神经网络、遗传算法。这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7、网格算法和穷举法。网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8、一些连续离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9、数值分析算法。如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算
78、法就需要额外编写库函数进行调用。 10、图象处理算法。赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理。 从历年竞赛题来看，常用的方法：线性规划 整数规划 非线性规划 动态规划 层次分析法 图论方法 拟合方法 插值方法随机方法 微分方程 方法一些小建议一些小建议1、多多阅读数学建模论文，熟悉常见题型及其解法。2、熟悉常用数学软件的基本命令。3、熟练掌握论文的写作格式，熟练掌握word的各项功能。建模时主要用到的工具vWordvMathtype（公式编辑器）vExcel（数据处理功能超强）vMatl
79、ab（无所不能）vLingo（优化）vOrigin（简单易用的数据分析软件）其他工具vWhats best!lindo公司出品的一个优化软件，是以插件的形式存在于excel中，简单易用。vSasspss国际权威数据统计、分析软件。vautocad专业绘图软件其他工具，有待根据你们的需要去发现。常用的网址v数模网v北峰数模网http:/ 每位同学选择完成大学生数模竞赛每位同学选择完成大学生数模竞赛19951995年年A A题题 19991999年年B B、C C题题 20002000年年B B、D D题题 20012001年年C C题题 20032003年年B B、D D题题 20042004年年B B题题写清学院学号姓名，发至写清学院学号姓名，发至EmailEmail：，一个月内完成。，一个月内完成。布置作业内容布置作业内容 祝大家祝大家 学有所成！学有所成！ 校校数学建模数学建模 组委会组委会
