《数学建模讲座优化建模与LINGO优化软件ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模讲座优化建模与LINGO优化软件ppt课件.ppt（97页珍藏版）》请在三一办公上搜索。
1、数学建模讲座优化建模与LINGO优化软件,例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20,Lingo 基 础,Lingo 程序MIN=-2*X1-6*X2+X1*X1-2*X1*X2+2*X1*X1;X1+X2=2;-X1+2*X2=2;,Lingo 基 础,计算结果Objective value: -9.777778X1 = 0.6666667 X2 = 1.333333,Lingo 基 础,例2,x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0,Lingo 基
2、 础,Lingo程序min=exp(x1)*(4*x1*x1+2*x2*x2+4*x1*x2+2*x2+1);x1+x2=0;1.5+x1*x2-x1-x2=0;-x1*x2-10=0;free(x1);free(x2);,Lingo 基 础,计算结果Objective value: 5.276848X1 = 1.224745 X2 = -1.224745这是局部最优值,Lingo 基 础,Lingo菜单中Options，选Global Solver ，在Use Global Solver 中打钩，再次计算。,Objective value: 1.156627X1=-3.162278 X2=3
3、.162278,Lingo 基 础,例三,Lingo 基 础,例三中,x,y ,e是一维数组，长度为2，a,b,d 也是一维数组，长度为6，c是二维数组（62矩阵）Lingo中如何定义它们？,Lingo 基 础,Lingo 程序 example3_2sets:demand/1.6/:a,b,d;supply/1.2/:x,y,e;link(demand,supply):c;endsetsdata:a=1.25,8.75,0.5,5.75,3,7.25;b=1.25,0.75,4.75,5,6.5,7.75;d=3,5,4,7,6,11; e=20,20;enddata,Lingo 基 础,in
4、it:x,y=5,1,2,7;endinit min=sum(link(i,j):c(i,j)*(x(j)-a(i)2+(y(j)-b(i)2)(1/2) );for(demand(i): sum(supply(j):c(i,j) =d(i););for(supply(i): sum(demand(j):c(j,i) =e(i); );for(supply:bnd(0.5,X,8.75); bnd(0.75,Y,7.75); );END,Lingo 基 础,计算结果为 Objective value:89.88349,模型的集部分,LINGO有两种类型的集：原始集(primitiveset)和
5、派生集(derived set)。一个原始集是由一些最基本的对象组成的。一个派生集是用一个或多个其它集来定义的，也就是说，它的成员来自于其它已存在的集。,定义一个原始集，用下面的语法：setname/member_list/:attribute_list;注意：用“”表示该部分内容可选。,Member_list是集成员列表。如果集成员放在集定义中，那么对它们可采取显式罗列和隐式罗列两种方式。如果集成员不放在集定义中，那么可以在随后的数据部分定义它们,模型的数据部分,数据部分以关键字“data:”开始，以关键字“enddata”结束。在这里，可以指定集成员、集的属性。,数据部分的未知数值,有时只
6、想为一个集的部分成员的某个属性指定值，而让其余成员的该属性保持未知，以便让LINGO去求出它们的最优值。在数据声明中输入两个相连的逗号表示该位置对应的集成员的属性值未知。两个逗号间可以有空格,数据部分的未知数值,sets: years/1.5/: capacity;endsetsdata: capacity = ,34,20,;enddata属性capacity的第2个和第3个值分别为34和20，其余的未知,模型的初始部分,一个初始部分以“init:”开始，以“endinit”结束。初始部分的初始声明规则和数据部分的数据声明规则相同。,模型的初始部分,init:x,y=5,1,2,7;endi
7、nit,LINGO函数,基本运算符数学函数金融函数概率函数变量界定函数集操作函数集循环函数数据输入输出函数辅助函数,算术运算符,乘方乘除加减,逻辑运算符,#not#eq#ne#gt#ge#lt# #le# #and# #or#,关系运算符,LINGO有三种关系运算符：“=”、“=”。 LINGO并不支持严格小于和严格大于关系运算符。然而，如果需要严格小于和严格大于关系，比如让A严格小于B：AB，那么可以把它变成如下的小于等于表达式：A+=B，,数学函数,abs(x) sin(x) cos(x) tan(x) exp(x)log(x) lgm(x) 返回x的gamma函数的自然对数sign(x)
8、 如果x0返回-1；否则，返回1floor(x) 返回x的整数部分。smax(x1,x2,xn) smin(x1,x2,xn),变量界定函数,bin(x) 限制x为0或1bnd(L,x,U) 限制LxUfree(x) 取消对变量x的默认下界为0的限制，即x可以取任意实数gin(x) 限制x为整数,集操作函数,index(set_name,primitive_set_element)该函数返回在集set_name中原始集成员primitive_set_element的索引。,集操作函数,wrap(index,limit) 该函数为index模limit再加1 size(set_name)该函数返
9、回集set_name的成员个数,集合循环函数,四个集合循环函数：FOR、SUM 、 MAX、MINfunction( setname ( set_index_list) | condition : expression_list);,例:,SUM( PAIRS( I, J): BENEFIT( I, J) * MATCH( I, J);,例:,FOR(STUDENTS( I): SUM( pair( j, k) | j #EQ#i #OR# k #EQ# i: match( j, k) =1);,FILE和TEXT：文本文件输入输出,data:a=file(example3_3.ldt);b=
10、file(example3_3.ldt);d=file(example3_3.ldt);e=file(example3_3.ldt);enddatainit:x,y=file(example3_3.ldt);endinit,1.25,8.75,0.5,5.75,3,7.251.25,0.75,4.75,5,6.5,7.753,5,4,7,6,1120,205,1,2,7,Example3_3.ldt的格式,FILE和TEXT：文本文件输入输出,比较,a=1.25,8.75,0.5,5.75,3,7.25;b=1.25,0.75,4.75,5,6.5,7.75;d=3,5,4,7,6,11; e
11、=20,20;x,y=5,1,2,7;,OLE ：与EXCEL连接,使用格式OLE(“filename” ，range_name_list) filename 为电子表 文件名 , range_name_list 为数据的单元范围。,OLE 的使用例子Excel文件example3_4.xls 的内容,注意 要将表格中的数据进行命名 :选中数据,选菜单“插入|名称|定义” 在这里分别命名为 a,b,d,e,x,y,result,OLE 的使用例子Lingo文件example3_4.lg4 的内容,data:a,b,d,e=OLE(d:数学建模EXAMPLE3_4.XLS);enddataini
12、t:x,y=Ole(d:数学建模Example3_4.xls);endinit,OLE 的使用例子如果在Lingo文件example3_4.lg4 加上以下内容其他不变,data:ole(d:数学建模EXAMPLE3_4.XLS,result)=c;ole(d:数学建模EXAMPLE3_4.XLS,x)=x;ole(d:数学建模EXAMPLE3_4.XLS,y)=y;enddata,OLE 的使用例子,则example3_4.xls 变为,注意其中x,y ,result 的变化,例 加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可
13、买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,模型求解,max =72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100;,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED CO
14、ST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,20桶牛奶生产A1, 30桶生产A2，利润3360元。,模型求解,reduced cost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题),OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE
15、VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000
16、 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000,原料无剩余,时间无剩余,加工能力剩余40,max 72x1+64x2stx1+x25012x1+8x24803x1100,三种资源,“资源” 剩余为零的约束为紧约束（有效约束）,结果解释,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.00000
17、0 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000,结果解释,最优解下“资源”增加1单位时“效益”的增量,原料增1单位, 利润增48,时间加1单位, 利润增2,能力增减不影响利润,影子价格,35元可买到1桶牛奶，要买吗？,35 48, 应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT R
18、ANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.00000
19、0,最优解不变时目标系数允许变化范围,DO RANGE(SENSITIVITY) ANALYSIS?,Yes,x1系数范围(64,96),x2系数范围(48,72),A1获利增加到 30元/千克，应否改变生产计划,x1系数由243= 72 增加为303= 90，在允许范围内,不变！,(约束条件不变),结果解释,结果解释,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.
20、000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶，每天最多买多少？,最多买10桶？,(目标函数不变),注意: 充
21、分但可能不必要,LINGO模型例：选址问题,某公司有6个建筑工地，位置坐标为(ai, bi) (单位：公里),水泥日用量di (单位：吨）,假设：料场和工地之间有直线道路,用例中数据计算，最优解为,总吨公里数为136.2,线性规划模型,决策变量：ci j (料场j到工地i的运量）12维,选址问题：NLP,2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij ，在其它条件不变下使总吨公里数最小。,决策变量：ci j，(xj,yj)16维,非线性规划模型,LINGO模型的构成：4个段,集合段（SETS ENDSETS）,数据段（DATA ENDDATA）,初始段（INIT ENDINI
22、T）,目标与约束段,局部最优：89.8835(吨公里 ),LP：移到数据段,问题1. 如何下料最节省 ?,例 钢管下料,问题2. 客户增加需求：,节省的标准是什么？,由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？,按照客户需要在一根原料钢管上安排切割的一种组合。,切割模式,合理切割模式的余料应小于客户需要钢管的最小尺寸,钢管下料,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,合理切割模式,2. 所用原料钢管总根数最少,钢管下料问题1,两种标准,1. 原料钢管剩余总余量最小,xi 按第i 种模式切割的原料钢管根数(i=1,
23、2,7),约束,满足需求,决策变量,目标1（总余量）,按模式2切割12根,按模式5切割15根，余料27米,最优解：x2=12, x5=15, 其余为0；最优值：27,整数约束： xi 为整数,当余料没有用处时，通常以总根数最少为目标,目标2（总根数）,钢管下料问题1,约束条件不变,最优解：x2=15, x5=5, x7=5, 其余为0；最优值：25。,xi 为整数,按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米,虽余料增加8米，但减少了2根,与目标1的结果“共切割27根，余料27米” 相比,钢管下料问题2,对大规模问题，用模型的约束条件界定合理模式,增加一种需求：
24、5米10根；切割模式不超过3种。,现有4种需求：4米50根，5米10根，6米20根，8米15根，用枚举法确定合理切割模式，过于复杂。,决策变量,xi 按第i 种模式切割的原料钢管根数(i=1,2,3),r1i, r2i, r3i, r4i 第i 种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量,满足需求,模式合理：每根余料不超过3米,整数非线性规划模型,钢管下料问题2,目标函数（总根数）,约束条件,整数约束： xi ,r1i, r2i, r3i, r4i (i=1,2,3)为整数,增加约束，缩小可行域，便于求解,原料钢管总根数下界：,特殊生产计划：对每根原料钢管模式1：切割成
25、4根4米钢管，需13根；模式2：切割成1根5米和2根6米钢管，需10根；模式3：切割成2根8米钢管，需8根。原料钢管总根数上界：31,模式排列顺序可任定,钢管下料问题2,需求：4米50根，5米10根，6米20根，8米15根,每根原料钢管长19米,LINGO求解整数非线性规划模型,Local optimal solution found at iteration: 12211 Objective value: 28.00000Variable Value Reduced CostX1 10.00000 0.000000X2 10.00000 2.000000X3 8.000000 1.00000
26、0R11 3.000000 0.000000R12 2.000000 0.000000R13 0.000000 0.000000R21 0.000000 0.000000R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000,模式1：每根原料钢管切割成3根4米和1根6米钢管，共10根；模式2：每根原料钢
27、管切割成2根4米、1根5米和1根6米钢管，共10根；模式3：每根原料钢管切割成2根8米钢管，共8根。原料钢管总根数为28根。,露天矿里铲位已分成矿石和岩石: 平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间5分钟,卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。,露天矿生产的车辆安排(CUMCM-2003B),矿石卸点需要的铁含量要求都为29.5%1%(品位限制），搭配量在一个班次（8小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为154吨，平均
28、时速28km,平均卸车时间为3分钟。,问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次 ?,平面示意图,问题数据,问题分析,与典型的运输问题明显有以下不同：这是运输矿石与岩石两种物资的问题；属于产量大于销量的不平衡运输问题；为了完成品位约束，矿石要搭配运输；产地、销地均有单位时间的流量限制；运输车辆只有一种，每次满载运输，154吨/车次；铲位数多于铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地；最后求出各条路线上的派出车辆数及安排。,近似处理：先求出产位、卸点每条线路上的运输量(MIP模型)然后求出各条路线上的派出车辆数及安排,模型假设,卡车在一个班
29、次中不应发生等待或熄火后再启动的情况；在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；空载与重载的速度都是28km/h，耗油相差很大；卡车可提前退出系统，等等。,如理解为严格不等待，难以用数学规划模型来解 个别参数队找到了可行解 （略）,符号,xij ：从i铲位到j号卸点的石料运量 （车） 单位： 吨；cij ：从i号铲位到j号卸点的距离 公里；Tij :从i号铲位到号j卸点路线上运行一个周期平均时间 分；Aij ：从号铲位到号卸点最多能同时运行的卡车数 辆；Bij ：从号铲位到号卸点路线上一辆车最多可运行的次数 次；pi：i
30、号铲位的矿石铁含量 p=(30,28,29,32,31,33,32,31,33,31) %qj : j号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 吨cki ：i号铲位的铁矿石储量 万吨cyi ：i号铲位的岩石储量 万吨fi :描述第i号铲位是否使用的0-1变量，取1为使用；0为关闭。,(近似),优化模型,（1）道路能力(卡车数)约束（2）电铲能力约束（3）卸点能力约束（4）铲位储量约束（5）产量任务约束（6）铁含量约束（7）电铲数量约束（8）整数约束,.,xij为非负整数fi 为0-1整数,计算结果（LINGO软件）,计算结果（派车）,结论：铲位1、2、3、4、
31、8、9、10处各放置一台电铲。一共使用了13辆卡车；总运量为85628.62吨公里；岩石产量为32186吨；矿石产量为38192吨。,此外：6辆联合派车（方案略）,2005年全国大学生数学建模竞赛B题 DVD在线租赁,随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。例如，音像制品的在线租赁就是一种可行的服务。这项服务充分发挥了网络的诸多优势，包括传播范围广泛、直达核心消费群、强烈的互动性、感官性强、成本相对低廉等，为顾客提供更为周到的服务。 。,考虑如下的在线DVD租赁问题。顾客缴纳一定数量的月费成为会
32、员，订购DVD租赁服务。会员对哪些DVD有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要求。会员提交的订单包括多张DVD，这些DVD是基于其偏爱程度排序的。网站会根据手头现有的DVD数量和会员的订单进行分发。每个会员每个月租赁次数不得超过2次，每次获得3张DVD。会员看完3张DVD之后，只需要将DVD放进网站提供的信封里寄回（邮费由网站承担），就可以继续下次租赁,请考虑以下问题：1、2、表2中列出了网站手上100种DVD的现有张数和当前需要处理的1000位会员的在线订单（表2的数据格式示例如下表），如何对这些DVD进行分配，才能使会员获得最大的满意度？请具体列出前30位会员（即C0
33、001C0030）分别获得哪些DVD。,注：D001D100表示100种DVD, C0001C1000表示1000个会员, 会员的在线订单用数字1,2,表示，数字越小表示会员的偏爱程度越高，数字0表示对应的DVD当前不在会员的在线订单中。,问题二的解答1、如何定义满意度？满意度是在线订单表格数字的减函数,满意度的几种定义方式,2、0-1规划模型对于问题中的分配问题,我们可以设0-1 决策变量 , =1 表示将j 号DVD分配给i 号会员, =0 表示不分配.,2005 DVD问题数学模型,lingo程序! Excel 表b2005table2.xls A(i,j) 为零改为 11；!Excel
34、表b2005table3.xls 为未改动数据model:sets:user/1.1000/:y;dvd/1.100/:C;link(user,dvd):A,S,X;endsets,2005 DVD问题,data:S=ole(d:lingo8B2005table2.xls);C=ole(d:lingo8B2005table2.xls,CC);A=ole(d:ling8b2005table3.xls);enddata,2005 DVD问题,max=sum(link(i,j):(11-S(i,j)/10*X(i,j);for(dvd(j):sum(user(i):X(i,j)=C(j);for(u
35、ser(i):sum(dvd(j):X(i,j)=3*y(i);for(link(i,j):bnd(0,X(i,j),A(i,j);for(link(i,j):bin(X);,货郎担问题，Traveling Salesman Problem,有一个推销员，从城市1出发，要遍访城市2，3，n各一次，最后返回城市1。已知从城市i到j的旅费为cij，问他应按怎样的次序访问这些城市，使得总旅费最少？,Traveling Salesman Problem,引入一些0-1整数变量：,目标是使为最小,Traveling Salesman Problem,TSP问题有两种理解，一种是找顶点不重复的最小权的Ha
36、milton圈，另外一种是找一条经过每个顶点且有最小权的闭链(顶点可以重复)。对于满足三角不等式的完全图，两者是一致的。,Traveling Salesman Problem,两个约束条件：访问城市i后必须要有一个即将访问的确切城市；访问城市j前必须要有一个刚刚访问过的确切城市。,Traveling Salesman Problem,但以上两个条件对于TSP来说并不充分，仅仅是必要条件。例如：,以上两个条件都满足，但它显然不是TSP的解，它存在两个子巡回。,Traveling Salesman Problem,把额外变量 (表示城市I在巡回中的次序)附加到问题中,附加下面形式的约束条件,Tra
37、veling Salesman Problem,可以证明：（1）任何含子巡回的路线都不满足该约束条件；（2）全部巡回都满足该约束条件。,Traveling Salesman Problem,TSP转化成了一个混合整数线性规划问题,TSP Lingo程序,sets: cities/1.10/:u; link(cities, cities): distance, x; endsetsdata: distance = 0 8 5 9 12 14 12 16 17 22enddata,TSP Lingo程序,enddatan=size(cities); min=sum(link(i,j)|i #ne#
38、 j: distance(i,j)*x(i,j),TSP Lingo程序,for(cities(i) : sum(cities(j)| j #ne# i: x(j,i)=1; sum(cities(j)| j #ne# i: x(i,j)=1; for(cities(j)| j #gt# 1 #and# j #ne# i : u(i)-u(j) +n* x(i,j)=n-1; ););for(link : bin(x);for(cities(i) | i #gt# 1 : u(i)=n-2;,TSP Lingo程序,但是,这个程序运行太慢, 如果加上界for(cities(i) | i #gt
39、# 1 : u(i)=1+(n-2)*x(i,1);很快就得到结果,TSP问题二 18个节点,TSP问题二,min=sum(link(i,j)|i#ne#j:distance(i,j)*x(i,j);for(cities(i) : sum(cities(j)| j #ne# i: x(j,i)=1; sum(cities(j)| j #ne# i: x(i,j)=1;for(cities(j)| j #gt# 1 #and# j #ne# i :u(i)-u(j) +n* x(i,j)=1+(n-2)*x(i,1););,TSP问题三,29个节点的问题（tsp3.lg4)。Lingo 运行时间为1分40秒 找到最优解,TSP问题4,Tsp4.lg4, 48个节点 最优解为 5046运行4小时，找到解为 5074利用模拟退火法（C程序simu_tsp.c，数据文件tsp4.txt) 几分钟后找到最优解5046 29 7 28 44 41 46 18 34 23 25 3 19 4 30 38 20 35 42 39 40 2 45 43 47 37 24 15 10 12 31 5 33 8 22 21 17 27 32 9 14 6 26 36 11 16 48 13 1,
