用Lingo软件编程求解规划问题.ppt

《用Lingo软件编程求解规划问题.ppt》由会员分享，可在线阅读，更多相关《用Lingo软件编程求解规划问题.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、用Lingo软件编程求解规划问题刘甫北京师范大学什么是规划问题？求目标函数在约束条件下的最大值或最小值的问题，统称为规划问题。决策变量、约束条件、目标函数是线性规划的三要素.主要解决最优生产计划、最优分配、最优设计、最优决策、最佳管理等最优化问题。线性规划非线性规划实数规划整数规划0-1规划例1加工奶制品的生产计划获利24元/公斤 获利16元/公斤 1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 每天：每天：一奶制品加工厂用牛奶生产 A1,A2两种奶制品，1 桶牛奶可以在甲车间用12 小时加工成 3 公斤 A1

2、，或者在乙车间用 8 小时加工成 4 公斤 A2。根据市场需求，生产的 A1,A2全部能售出，且每公斤 A1获利 24 元，每公斤 A2获利 16 元。现在加工厂每天能得到 50 桶牛奶的供应，每天正式工人总的劳动时间 480 小时，并且甲车间每天至多能加工 100 公斤 A1，乙车间的加工能力没有限制。试为该厂制订一个生产计划，使每天获利最大例1加工奶制品的生产计划获利24元/公斤 获利16元/公斤 1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 每天：每天：x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶

3、生产A2 获利获利 243x1 获利获利 164 x2 原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性规线性规划模型划模型(LP)例1加工奶制品的生产计划求 的最大值？改变z，即移动直线z=72x1+64x2并使之与蓝色区域有交叉，即可找到最大值。见动画求 的最大值？用Lingo软件求解Lingo结果中其它项的意思！更多信息例1加工奶制品的生产计划例2军队供给问题corps需求量3537223241324338拥有量B1B2B3B4B5B6B7B8depot60A16267425955A24953

4、858251A35219743343A47673927141A52395726552A655228143军队有某种先进武器302台分别放在6个补给站(depot)中，现由于战争需要，8个军团(corps)分别需要此种武器数目如表中所示，并且给出了从各补给站送一台武器到任一军团的费用，问如何运输可使成本最小？capacity(i)V(i)demand(j)d(j)cost(i,j)c(i,j)number(i,j)n(i,j)例2军队供给问题corps需求量3537223241324338拥有量B1B2B3B4B5B6B7B8depot60A16267425955A24953858251A352

5、19743343A47673927141A52395726552A655228143capacity(i)V(i)demand(j)d(j)cost(i,j)c(i,j)number(i,j)n(i,j)例2军队供给问题用Lingo软件求解结果Lingo软件LINGO Help:LINGO is a simple tool for utilizing the power of linear and nonlinear optimization to formulate large problems concisely,solve them,and analyze the solution.Op

6、timization helps you find the answer that yields the best result;attains the highest profit,output,or happiness;or the one that achieves the lowest cost,waste,or discomfort.Often these problems involve making the most efficient use of your resourcesincluding money,time,machinery,staff,inventory,and

7、more.Lingo 是一个可以简洁地阐述、解决和分析复杂问题的简便工具。其特点是程序执行速度很快，易于输入、修改、求解和分析一个数学规划问题。Lingo软件 集合段（集合段（SETS ENDSETS）目标与约束段目标与约束段 数据段（数据段（DATA ENDDATA）初始段（初始段（INIT ENDINIT）LINGO模型的构成：模型的构成：4个段个段Lingo 是一个可以简洁地阐述、解决和分析复杂问题的简便工具。其特点是程序执行速度很快，易于输入、修改、求解和分析一个数学规划问题。Lingo软件集合 集是相联系的对象的集合，比如工厂、消费者群体、交通工具集是相联系的对象的集合，比如工厂、消

8、费者群体、交通工具和雇工等等；和雇工等等；集是集是 LINGO 建模语言的基础，是程序设计最强有力的基本构件建模语言的基础，是程序设计最强有力的基本构件目标与约束段；目标与约束段；借助于集，能够用一个单一的、长的、简明的复合公式表示一借助于集，能够用一个单一的、长的、简明的复合公式表示一系列相似的约束，从而可以快速方便地表达规模较大的模型；系列相似的约束，从而可以快速方便地表达规模较大的模型；集有成员和属性。集有成员和属性。集合集合 派生集合派生集合 基本集合基本集合 稀疏集合稀疏集合 稠密集合稠密集合 元素列表法元素列表法 元素过滤法元素过滤法 直接列举法直接列举法 隐式列举法隐式列举法Li

9、ngo软件集合setname/member_list/:attribute_list;setname(parent_set_list)/member_list/:attribute_list;Lingo软件基本集合元素的列举setname/member_list/:attribute_list;sets:students/John Jill,Rose Mike/:sex,age;endsets 集成员不放在集定义中，而在随后的数据部分来定义。sets:students:sex,age;endsets data:students,sex,age=John 1 16 Jill 0 14 Rose

10、0 17 Mike 1 13;enddata 一个原始集是由一些最基本的对象组成的。类类型型隐隐式列式列举举格式格式示例示例示例集合的元素示例集合的元素数字型数字型 1.n1.51,2,3,4,5字符字符-数字型数字型stringM.stringNCar101.car208Car101,car102,car208星期型星期型 dayM.dayNMON.FRIMON,TUE,WED,THU,FRI月份型月份型 monthM.monthNOCT.JANOCT,NOV,DEC,JAN年份年份-月份型月份型monthYearM.monthYearNOCT2001.JAN2002OCT2001,NOV2

11、001,DEC2001,JAN2002Lingo软件基本集合元素的隐式列举Lingo软件派生集setname(parent_set_list)/member_list/:attribute_list;一个派生集是用一个或多个其它集来定义的，也就是说，它的成员来自于其它已存在的集。稠密集：稠密集：派生集成员由父集成员所有组合构成；当成员列表被忽略时稀疏集：稀疏集：其成员为父集成员所有组合构成的集合的一个子集。如上例显式：links(depot,corps)/d1 c2,d2 c3,d3 c6,d4 c3,d5 c1,d6 c8/:cost,number;过滤：links(depot,corps)

12、|capacity(&1)#ge#demand(&2):cost;Lingo软件数据段与初始段数据段：数据段：输入集成员和数据，提供了模型相对静止部分和数据分离的可能性。object_list=value_list;对象列数值列；初始段：初始段：为决策变量设置初始值。在初始部分输入的值仅被 LINGO 求解器当作初始点来用，并且仅仅对并且仅仅对非线性模型有用非线性模型有用。和数据部分指定变量的值不同，LINGO求解器可以自由改变自由改变初始部分初始化的变量的值。以“init:”开始，以“endinit”结束。初始部分的初始声明规则和数据部分的数据声明规则相同。Lingo软件目标与约束段四个集合

13、循环函数：四个集合循环函数：FOR、SUM、MAX、MINfunction(setname (set_index_list)|condition:expression_list);例子：Lingo软件目标与约束段四个集合循环函数：四个集合循环函数：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

14、#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);例子：优优先先级级运算符运算符最高最高#NOT#（负负号）号）*/+（减法）（减法）#EQ#NE#GT#GE#LT#LE#AND#OR#最低最低(=)三类运算符：三类运算符：算术运算符算术运算符 逻辑运算符逻辑运算符 关系运算符关系运算符Lingo软件运算符与优先级主要用于集循环函数的条件表达式中形成模型的一个约束条件，指定一个表达式的左边是否等于、小

15、于等于、或者大于等于右边。针对数值进行操作Lingo软件函数abs(x)返回 x 的绝对值sin(x)返回 x 的正弦值，x 采用弧度制cos(x)返回 x 的余弦值tan(x)返回 x 的正切值exp(x)返回常数 e 的 x 次方log(x)返回 x 的自然对数lgm(x)返回 x 的 gamma 函数的自然对数sign(x)如果 x=0 时，返回不超过 x 的最大整数；当 x0 时，返回不低于 x 的最大整数。smax(x1,x2,xn)返回 x1，x2，xn 中的最大值smin(x1,x2,xn)返回 x1，x2，xn 中的最小值数学函数Lingo软件函数变量定界函数bin(x)限制

16、x 为 0 或 1bnd(L,x,U)限制 LxUfree(x)取消对变量 x 的默认下界为 0 的限制，即 x 可以取任意实数gin(x)限制 x 为整数例3Lingo与Excel的连接corps需求量3537223241324338拥有量B1B2B3B4B5B6B7B8depot60A16267425955A24953858251A35219743343A47673927141A52395726552A655228143capacity(i)V(i)demand(j)d(j)cost(i,j)c(i,j)number(i,j)n(i,j)ole函数 是从 EXCEL 中引入或输出数据的接口

17、函数，它是基于传输的 OLE 技术。OLE传输直接在内存中传输数据，并不借助于中间文件。例3Lingo与Excel的连接OLE 可以同时读集成员和集属性（读写）OLE 只能读一维或二维的 Ranges绝对路径 ole(data.xls);相对路径 ole(D:data.xls);某矿厂现有某矿厂现有6个采矿能力不同的矿厂和个采矿能力不同的矿厂和3个精加工能力不同的加工厂，其坐标个精加工能力不同的加工厂，其坐标及生产能力如表所示。现需新建一所粗加工厂，要求运输成本最低，试求出及生产能力如表所示。现需新建一所粗加工厂，要求运输成本最低，试求出其位置。其位置。例4工厂选址问题矿厂矿厂1 12 23

18、34 45 56 6xa1.258.750.55.7537.25xb1.250.754.7556.57.75output3547611精加工厂精加工厂123xc3.156.59.25xd0.259.57.35capacity141210非线性规划模型非线性规划模型 某班准备从5名游泳队员中选择4人组成接力队，参加学校的4*100m混合泳接力比赛。5名队员4中用字的百米平均成绩如下表所示，问应如何让选拔队员组成接力队？例50-1规划问题甲 乙 丙 丁 戊蝶泳 106 572 118 110 107 仰泳 115 106 107 114 111 蛙泳 127 106 124 109 123 自由泳

19、 586 53 594 572 102我们可以：用穷举法：一种组合一种组合的试！数据量大，需要时间长！用Lingo中的0-1规划求解！例50-1规划问题甲 乙 丙 丁 戊蝶泳 106 572 118 110 107仰泳 115 106 107 114 111 蛙泳 127 106 124 109 123自由泳 586 53 594 572 102五个人的成绩：甲乙丙丁戊分别为队员 i=1，2，3，4，5；记：蝶泳、仰泳、蛙泳、自由泳分别为泳姿 j=1，2，3，4；记队员i的第j种泳姿的百米最好成绩为 Cij，并将成绩以秒为单位列出为：例50-1规划问题五个人的成绩：Cij I=1 I=2 I=

20、3 I=4 I=5 J=1 66 57.03 78 70 67 J=2 75 66 67 74 71 J=3 87 66 84 69 83 J=4 58.1 53 59.07 57.03 62引入0-1变量Xij，表示队员i是否参加了第j种泳姿的比赛，即目标：使其最小那么，混合泳接力比赛的成绩就可以表示为：Xij只能为0或1每一个人最多只能入选四种泳姿之一：每种泳姿必须有一人而且只能有1人入选：例50-1规划问题五个人的成绩：Cij I=1 I=2 I=3 I=4 I=5 J=1 66 57.03 78 70 67 J=2 75 66 67 74 71 J=3 87 66 84 69 83 J

21、=4 58.1 53 59.07 57.03 62变量Xij满足的约束条件为：例50-1规划问题最终问题：问题求解：Lingo8.0软件求解，调用excel表中的数据。Summary规划问题Lingo软件的集合、函数、语法几个例子加工奶制品的生产计划(线性规划)运输问题(整数规划)工厂选址问题(非线性规划)游泳比赛问题(0-1规划)Thank you for your attention!Thank you for your attention!Fu Liu(刘甫)Department of Physics,Beijing Normal UniversityEmail:Website:http:/ Questions?