数学模型与lingo软件 西南交通大学数学系 需要掌握的几个重要方面 ?掌握集合(SETS)的应用； ?正确阅读求解报告； ?正确理解求解状态窗口； ?学会设置基本的求解选项(OPTIONS) ； ?应用实例 LINGO 8.0有两种命令模式 Windows 模式, 通过下拉式菜单命令驱动LINGO 运行 命令行(Command-Line) 模式,仅在命令窗口下操作 与LINDO 相比，LINGO 软件主要具有两大优点 1、除具有LINDO 的全部功能外，还可用于求解非线性 规划问题，包括非线性整数规划问题 2、LINGO 包含了内置的建模语言，允许以简练、直观 的方式描述较大规模的优化问题，模型中所需的数据可 以以一定格式保存在独立的文件中 LP问题在lindo和lingo中不同的输入形式 Lindo: max 2x+3y st 4x+3y<10 3x+5y<12 end Lingo: max=2*x+3*y; 4*x+3*y<10; 3*x+5*y<12; （1）将目标函数的表示方式从 “MAX”变成了“MAX=” （2）“ST”在LINGO 模型中不 再需要，所以被删除了 （3）每个系数与变量间增加 了运算符“*”（即乘号不能省略） （4）每行（目标、约束和说明 语句）后面均增加了一个分号“;” （5）模型结束标志“END”也被 删除了（LINGO 中只有当模型 以“MODEL：”开始时才能以 “END”结束）。 这是LINGO 模型的最基本 特征 直接将lindo模型文件转化为lingo文件 Lindo: max 2x+3y st 4x+3y<10 3x+5y<12 end Lingo: max=2*x+3*y; 4*x+3*y<10; 3*x+5*y<12; 为保证能将LINDO 模型移植到LINGO 中去，在LINDO 模型输入时应尽量采 用“规范化”的格式 Lingo的不同保存类型 “LG4”表示LINGO 格式的 模型文件，是一种特殊的二 进制格式文件，保存了我们 在模型窗口中所能够看到的 所有文本和其他对象及其格 式信息，只有LINGO 能读 出它，用其他系统打开这种 文件时会出现乱码 “LNG”表示LINGO文本文 件，以这个格式保存模型时 系统将给出警告，因为模 型中的格式信息（如字体、 颜色等）将会丢失 “LDT”表示数据文件 “LTF”表示命令脚本文件 “LGR”表示报告文件 除“LG4”文件外，这里的另外几 种格式的文件其实都是普通的 文本文件，可以用任何文本编 辑器打开和编辑 状态窗口的参数解释 约束数量 （约束总数、 非线性约束 个数） 变量数量（其中包括变量总数、 非线性变量数、整数变量数） 非零系数数量 （总数、非线 性项的个数） 内存使用量、求 解花费的时间 状态窗口的参数解释(2) 求解器状态框 扩展的求解器 （求解程序） 状态框 用LINGO 来解二次规划问题 22 121122 12 12 12 98 277 0.3 2 .. 100 2 ,0 MAXzxxxxxx stx x xx xx =+ ?? ? +≤ ≤ ≥为整数 注意事项： max=98*x1+277*x2-x1^2- 0.3*x1*x2-2*x2^2; x1+x2<100; x1<2*x2; @gin(x1);@gin(x2); 1) 变量和行名可以超过8 个 字符，但不能超过32 个字符， 且必须以字母开头 2) LINGO 已假定各变量非 负（除非用函数@free或 @sub 或@slb 另行说明） 3) 变量可以放在约束条件的 右端（同时数字也可放在约束 条件的左端）。但为了提高效 率，应尽可能采用线性表达式 定义目标和约束（如果可能） Lingo的编程 优化问题的一种建模语言。使用者可以只用键 入一行文字就可以建立起含有大规模变量的目 标函数和成千上万条约束 LINGO模型的构成:4个段 集合段（SETS ENDSETS） 数据段（DATA ENDDATA） 初始段（INIT ENDINIT） 目标与约束段 最重要的是理解“集合”（SET）及其“属性”（Attribute）的概念 例1：SAILCO 公司需要决定下四个季度的帆船生产量。 下四个季度的帆船需求量分别是40 条，60 条，75 条， 25 条，这些需求必须按时满足。每个季度正常的生产能 力是40 条帆船，每条船的生产费用为400 美元。如果 加班生产，每条船的生产费用为450 美元。每个季度末， 每条船的库存费用为20 美元。 假定生产提前期为0，初始库存为10 条船。如何安排 生产可使总费用最小？ 用DEM,RP,OP,INV 分别表示需求、正常生产的产量、 加班生产的产量、库存量，则DEM,RP,OP,INV 对每个 季度都应该有一个对应的值，也就说他们都应该是一个由 4 个元素组成的数组，其中DEM 是已知的，而 RP,OP,INV 是未知数。 { } 1,2,3,4 400 ( ) 450 ( ) 20 ( ) i MIN RP I OP I INV I = ++ ∑ 目标函数: 约束条件1(能力限制)：RP(I)<40，I=1,2,3,4; 约束条件2(产品数量的平衡方程)： INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I),I=1,2,3,4; INV(0)=10; 利用数组的概念 约束条件3: 变量的非负约束 QUARTERS ={1，2，3， 4}称为集合， DEM,RP,O P,INV 称 为该集合的 属性 MODEL: SETS: QUARTERS/1..4/:DEM,RP,OP,INV;! 定义集合及其属性; ENDSETS DATA: DEM=40,60,75,25; ENDDATA !初始段省略; MIN=@SUM(QUARTERS:400*RP+450*OP+20*INV); !目标函数; @FOR(QUARTERS(I):RP(I)<40);!能力约束; @FOR(QUARTERS(I)|I#GT#1:!产品数量的平衡方程; INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I);); INV(1)=10+RP(1)+OP(1)-DEM(1); END 作用在于对集合的属性（数组）输入必要 的常数数据。 格式为：attribute = value_list 用求和函数”@SUM(集合：表达式)”的方式定义的，这 个函数的功能是对冒号“：”后面的表达式，按照冒号“：” 前面的下标集合指定的下标进行求和。由于本例中目标 函数对所有下标都要求和，所以我们连下标i 也省去了； 如果不省略，目标函数也可以等价地写成 “@SUM(QUARTERS(i): 400*RP(i) +450*OP(i) +20*INV(i) )” 循环函数”@FOR(集合：约束关系式)”的方式定义的， 意思是对冒号“：”前面的集 合的每个元素（下标），冒号“：”后面的约束关系式都 要成立。由于下标i=1 时的约束关系式与i=2，3，4 时有所区别，所以对下标集合的元素（下标）加了一个 “i#GT#1”的限制条件，而把i=1 时的约束关系式单独 写出。限制条件“i#GT#1”是一个逻辑表达式，意思就 是i>1 基本集合与派生集合 例2:某公司有6 个建筑工地要开工，每个工地的位置（用平面坐标 a, b 表示，距离单位：公里）及水泥日用量d（吨）由下表给出。 目前有两个临时料场位于P (5, 1), Q (2, 7) ，日储量各有20 吨。假设 从料场到工地之间均有直线道路相连，试制定每天的供应计划，即 从A, B 两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。 为了进一步减少吨公里数，打算舍弃两个临时料场，改建两个新的， 日储量仍各为20 吨，问应建在何处，节省的吨公里数有多大。 (1):LINK中的元素就是DEMAND 和 SUPPLY 的笛卡儿积，也就是 LINK={（S，T）|S∈DEMAND， T∈SUPPLY}.因此，其属性C 也就是一个 6*2 的矩阵（或数组）。正是由于这种表示 方式，LINGO 建模语言也称为矩阵生成器。 DEMAND 和SUPPLY 这种直接把元素列举 出来的集合，称为基本集合（primary set）， 而把LINK 这种基于基本集合构造的集合称 为派生集合（derived set） (3):@free 函数取消了变量X、Y 非负限制 局部最优解 X(1)=7.249997， X(2)=5.695940， Y(1)=7.749998， Y(2)=4.928524， （略），最小运量 =89.8835(吨公里) (2):LINGO对数据是按列赋值的，而不是 按行.其中“X Y =5，1，2，7；”语句的实 际赋值顺序是X=(5,2),Y=(1,7), NLP中局部最优解不一定就是全局最优解,在help中有这样的叙述： “Thus, when a nonlinear model is solved, we say the solution is merely a local optimum, and the user must be aware other local optimums may, or may not, exist with better objective values.” 第一步:利用LINGO|Options”菜单命令激活全局最优求解程序 第二步:为减少计算工作量，对X，Y 的取值再做一些限制。由于 最佳料场位置至少不应该超出现在6 个工地所决定的坐标的最大、 最小值决定的矩形之外，即:0.5<=x<=8.75, 0.75<=y<=7.75. 可以 加上@bnd 函数 最优解X(1)=3.2549，X(2)=7.2500， Y(1)=5.6526，Y(2)=7.7500，最小运量= 85.26(吨公里) 把料厂P(5, 1), Q (2, 7)的位置看成是已知并且固定的，这时是LP 模型。只需把初始段的“X Y =5，1，2，7；”移到数据段就可。 此时，得到全局最优解，最小运量136.2275(吨公里) 稠密集合与稀疏集合 若派生集合是基本集合构成的笛卡儿积,则称它为稠密集合;派生 集合的元素可以只是这个笛卡儿积的一个真子集合，这种派生集 合称为稀疏集合 例3 最短路问题在公路网中，司机希望找到一条从一个城市到 另一个城市的最短路. 假设图表示的是该公路网, 节点表示货车 可以停靠的城市,弧上的权表示两个城市之间的距离（百公里）. 那么,货车从城市S 出发到达城市T,如何选择行驶路线,使所经过 的路程最短? S到Bj(j=1,2)的最优行驶路线 S到Ai(i=1,2,3)的最优行 驶路线(易求) S到T的最优行驶路线P 先求出从S到Ck(k=1,2) 的最优行驶路线0 模型的建立 记d(Y,X)为城市Y与城市X之间 的直接距离（若这两个城市之 间没有道路直接相连，则可以 认为直接距离为无穷大），用 L(X)表示城市S到城市X的最 优行驶路线的路长, 则: 定义稀疏集合ROADS 方 法:元素枚举法 从S到T的行驶过程分成4 个 阶段,即S→Ai(i=1,2 或3), Ai →Bj(j=1或2), Bj→Ck(k=1 或2), Ck →T {} L(S)=0 () (, ), YX MIN L Y d Y X X S ≠ +≠ 从S到T的最优行驶路线的路 长为20（进一步分析，可以 得到从S到T的最优行驶路线 为S→A3→B2→C1 →T） 另一种定义稀疏集合的方法:“元素过滤”法 匹配（MATCHING）问题:8 名同学准备分成4 个调查队（每队两人） 前往4 个地区进行社会调查。设两两之间组队的效率如表所示（由 于对称性只列出了上三角部分），问如何组队可以使总效率最高？ BENEFIT为效率矩阵，MATCH（Si，Sj）=1 表示Si，Sj 组成一队， 0 表示不组队。由于对称性只需考虑i<j 共32 个0-1 变量。 目标函数为BENEFIT（Si，Sj）* MATCH（Si，Sj）之和；约束条 件是每个同学只能（而且必须在）某一组，即对于任意i 有：只要 MATCH 属性的某个下标为i 就加起来，此和=1。显然，这是一个0- 1 线性规划 由于MATCH 变量中多数为0 setname[/member_list/] [: attribute_list]; 其中setname 为定义的集合 名，member_list 为元素列表， attribute_list 为属性列表 显式:CITIES/1,2,3,4/:L 隐式: CITIES/1..4/:L 当元素列表不在集合定 义中出现时，则必须在 程序的数据段以赋值语 句的方式直接给出元素 列表 派生集合一般定义格式为:setname(parent_set_list) [/member_list/] [: attribute_list]; 称parent_set_list为父集合列表 运算符及其优先级 算术运算符：+（加法），—（减法或负号），*（乘法），/ （除法），^(求幂) 关系运算符：<（即<=，小于等于),=（等于），>（即>=，大于 等于) 逻辑运算符：#AND#（与），#OR#（或），#NOT#（非）， #EQ#（等于），#NE#（不等于），#GT#（大于），#GE#（大 于等于），#LT#（小于），#LE#（小于等于）。结果只有“真” （1）和“假”（0）两个值 LINGO 函数一览(1) LINGO 函数一览(2) LINGO 函数一览(3) LINGO 函数一览(4) LINGO 函数一览(5) LINGO 函数一览(6) @smax(x1,x2,…,xn) 给定一个直角三角形，求包含该三角形的最小正方形 @qrand(seed) @rand(seed) 返回0和1间的伪随机数，依赖于指定的种子。典型用法是 U(I+1)=@rand(U(I))。注意如果seed不变，那么产生的随 机数也不变 利用@rand产生15个标准正态分布的随机数和自由度为2的t分 布的随机数 @for 函数@sum 函数 产生序列{1,4,9,16,25} 求向量[5，1，3，4，6，10] 前5个数的和 该函数用来产生对集成员的约 束。基于建模语言的标量需要 显式输入每个约束，不过@for 函数允许只输入一个约束，然 后LINGO自动产生每个集成员 的约束 该函数返回遍历指定的集成 员的一个表达式的和 @min和@max 返回指定的集成员的一个表达式的最小值或最大值 求向量[5，1，3，4，6，10]前5个数最小值，后3个数最大值 LINGO的主要菜单命令 与LINDO 主菜单比较，LINGO 相当于合并了LINDO 中的 Solve（求解）菜单和REPORTS（报告）菜单。这些菜单的 用法都是和WINDOWS 下其他应用程序的标准用法类似的， 下面只对前3 个主菜单中与LINDO 不同而有一定LINGO 特 色的主要命令进行简要介绍。 1）文件主菜单 File|Import LINDO File:将以LINDO 文件格式保存的模型转换 为LINGO 格式的模型 File|User Database Info:输入用户使用的数据库需要验证的用户 名（User ID）和密码（Password） 编辑（Edit）主菜单 Paste Special:用于剪贴板中的内容不是文本 的情形，如可以插入其它应用程序中生成的 对象（Object）或对象的链接（Link） Match Parenthesis:匹配模型中的括号 Edit|Paste Function:选择LINDO 的某个函 数，粘贴到当前光标处 Select Font:控制显示字体、字形、大小、颜 色、效果等。注意：这些显示特性只有当文 件保存为LINGO 格式（*.LG4）的文件时 才能保存下来， Edit|Link:在模型窗口中选择一个外部对象的链接，可以修改 这个对象的属性;Object Properties:在模型窗口中选择修改一 个链接或嵌入对象（OLE）的属性， LINGO 主菜单 Generate:以线性形式显示目标函数和约 束（只有非零项会显示）。如果有非线性 变量项，对应的非线性变量前的系数将以 问号（“？”）显示.按照是否在屏幕上显 示结果的要求，“Display”和“Don’t display”两个子菜单供选择。在屏幕上 不显示时，运行该命令的目的可能仅仅是 为了以后选择适当的求解程序使用。 Picture: 按照矩阵形 式以图形方式给出.非 线性项的系数以黑色 显示为“？”，线性项 的系数为正时显示为 兰色，为负则为红色 此部分结束