LINGO基本使用方法(续).ppt

2020 2 24 第4讲 LINGO基本使用方法 在LINGO中使用集合 续 运算符和函数 2020 2 24 包含了两个基本集合构成的所有二元有序对的派生集合称为稠密集合 简称稠集 有时候 在实际问题中 一些属性 数组 只在笛卡儿积的一个真子集合上定义 这种派生集合称为稀疏集合 简称疏集 例1 最短路问题 在纵横交错的公路网中 货车司机希望找到一条从一个城市到另一个城市的最短路 下图表示的是公路网 节点表示货车可以停靠的城市 弧上的权表示两个城市之间的距离 百公里 那么 货车从城市S出发到达城市T 如何选择行驶路线 使所经过的路程最短 二 在LINGO中使用集合 续 2 4稠密集合与稀疏集合 2020 2 24 分析 假设从S到T的最优行驶路线P经过城市C1 则P中从S到C1的子路也一定是从S到C1的最优行驶路线 假设P经过城市C2 则P中从S到C2的子路也一定是从S到C2的最优行驶路线 因此 为得到从S到T的最优行驶路线 只需要先求出从S到Ck k 1 2 的最优行驶路线 就可以方便地得到从S到T的最优行驶路线 同样 为了求出从S到Ck k 1 2 的最优行驶路线 只需要先求出从S到Bj j 1 2 的最优行驶路线 为了求出从S到Bj j 1 2 的最优行驶路线 只需要先求出从S到Ai i 1 2 3 的最优行驶路线 而S到Ai i 1 2 3 的最优行驶路线是很容易得到的 实际上 此例中S到Ai i 1 2 3 只有唯一的道路 2020 2 24 分析 此例中可把从S到T的行驶过程分成4个阶段 即S Ai i 1 2或3 Ai Bj j 1或2 Bj Ck k 1或2 Ck T 记d Y X 为城市Y与城市X之间的直接距离 若这两个城市之间没有道路直接相连 则可以认为直接距离为 用L X 表示城市S到城市X的最优行驶路线的路长 2020 2 24 本例的计算 所以 从S到T的最优行驶路线的路长为20 进一步分析以上求解过程 可以得到从S到T的最优行驶路线为S A3 B2 C1 T 这种计算方法在数学上称为动态规划 DynamicProgramming 2020 2 24 本例的LINGO求解 CITIES 城市 一个基本集合 元素通过枚举给出 L CITIES对应的属性变量 我们要求的最短路长 ROADS 道路 由CITIES导出的一个派生集合 请特别注意其用法 由于只有一部分城市之间有道路相连 所以不应该把它定义成稠密集合 将其元素通过枚举给出 这就是一个稀疏集合 D 稀疏集合ROADS对应的属性变量 给定的距离 2020 2 24 本例的LINGO求解 从模型中还可以看出 这个LINGO程序可以没有目标函数 这在LINGO中 可以用来找可行解 解方程组和不等式组 在数据段对L进行赋值 只有L S 0已知 后面的值为空 但位置必须留出来 即逗号 一个也不能少 否则会出错 如果这个语句直接写成 L 0 语法上看也是对的 但其含义是L所有元素的取值全部为0 所以也会与题意不符 2020 2 24 本例的LINGO求解 虽然集合CITIES中的元素不是数字 但当它以CITIES I 的形式出现在循环中时 引用下标I却实际上仍是正整数 也就是说I指的正是元素在集合中的位置 顺序 一般称为元素的索引 INDEX 在 for循环中的过滤条件里用了一个函数 index 其作用是返回一个元素在集合中的索引值 这里 index S 1 即元素S在集合中的索引值为1 所以逻辑关系式 i GT index S 可以直接等价地写成 i GT 1 这里 index S 实际上还是 index CITIES S 的简写 即返回S在集合CITIES中的索引值 2020 2 24 本例的LINGO求解结果 从S到T的最优行驶路线的路长为20 进一步分析 可以得到最优行驶路线为S A3 B2 C1 T 本例中定义稀疏集合ROADS的方法是将其元素通过枚举给出 有时如果元素比较多 用起来不方便 另一种定义稀疏集合的方法是 元素过滤 法 能够从笛卡儿积中系统地过滤下来一些真正的元素 2020 2 24 例2某班8名同学准备分成4个调查队 每队两人 前往4个地区进行社会调查 这8名同学两两之间组队的效率如下表所示 由于对称性 只列出了严格上三角部分 问如何组队可以使总效率最高 2020 2 24 分析 这是一个匹配 MATCHING 问题 把上表的效率矩阵记为BENEFIT 由于对称性 这个矩阵只有严格上三角部分共28个数取非零值 用MATCH Si Sj 1表示同学Si Sj组成一队 而MATCH Si Sj 0表示Si Sj不组队 由于对称性 只需考虑i j共28个0 1变量 而不是全部32个变量 显然 目标函数正好是BENEFIT Si Sj MATCH Si Sj 对I j之和 约束条件是每个同学只能 而且必须在 某一组 即对于任意i有 只要属性MATCH的某个下标为i就加起来 此和应该等于1 由上面的分析 因此 完整的数学模型如下 显然 这是一个0 1线性规划 2020 2 24 问题的LINGO求解 S1 S8 等价于写成 S1S2S3S4S5S6S7S8 它没有相关的属性列表 只用于表示是一个下标集合 在派生集合PAIRS定义中增加了过滤条件 2 GT 1 意思是第2个父集合的元素的索引值 用 2 表示 大于第1个父集合的元素的索引值 用 1 表示 PAIRS中的元素对应于上表中的严格上三角部分的二维下标 共28个元素 BENEFIT和MATCH是PAIRS的属性 注意数据段对BENEFIT的赋值方式 LINGO按照列的顺序对属性变量的元素进行赋值 在约束部分 过滤条件 J EQ I OR K EQ I 是由逻辑运算符 OR 或者 连接的一个复合的逻辑关系式 连接由 EQ 等于 表示的两个逻辑关系 由于 OR 的运算级别低于 EQ 所以这个逻辑式中没有必要使用括号指定运算次序 2020 2 24 LINGO求解结果 LINGO SOLVE 运行这个程序 可以得到全局最优值为30 MATCH变量中多数为0 可以更清晰地浏览最优解解 选择菜单命令 LINGO SOLUTION 可以看到图示对话框 选择属性MATCH 变量 选择Text 文本格式 选择NonzerosOnly 只显示非零值 点击 OK 按钮 得到关于最优解的非零分量的报告 学生最佳的组队方式是 1 8 2 4 3 7 5 6 2020 2 24 集合的使用小结 集合的不同类型及其关系 2020 2 24 基本集合的定义语法 基本集合的定义格式为 方括号 中的内容是可选项 可以没有 setname member list attribute list 其中setname为定义的集合名 member list为元素列表 attribute list为属性列表 元素列表可以采用显式列举法 即直接将所有元素全部列出 元素之间用逗号或空格分开 也可以采用隐式列举法 隐式列举法可以有几种不同格式 2020 2 24 元素列表和属性列表都是可选的 当属性列表不在集合定义中出现时 这样的集合往往只是为了将来在程序中作为一个循环变量来使用 或者作为构造更复杂的派生集合的父集合使用 匹配问题中的集合STUDENTS没有属性列表 而当元素列表不在基本集合的定义中出现时 则必须在程序的数据段以赋值语句的方式直接给出元素列表 例如 前例中SAILCO公司决定四个季度的帆船生产量模型的集合段和数据段可以分别改为 SETS QUARTERS DEM RP OP INV 注意没有给出集合的元素列表 ENDSETSDATA QUARTERSDEM 140260375425 注意LINGO按列赋值的特点 ENDDATA 基本集合的定义语法 帆船生产量模型的源程序 匹配问题的源程序 2020 2 24 派生集合的定义语法 派生集合的定义格式为 方括号 中的内容是可选项 可以没有 setname parent set list member list attribute list 与基本集合的定义相比较多了一个parent set list 父集合列表 父集合列表中的集合 如set1 set2 等 称为派生集合setname的父集合 它们本身也可以是派生集合 当元素列表 member list 不在集合定义中出现时 还可以在程序的数据段以赋值语句的方式给出元素列表 若在程序的数据段也不以赋值语句的方式给出元素列表 则认为定义的是稠密集合 即父集合中所有元素的有序组合 笛卡儿积 都是setname的元素 当元素列表在集合定义中出现时 又有 元素列表法 直接列出元素 和 元素过滤法 利用过滤条件 两种不同方式 2020 2 24 3 1 1算术运算符 算数运算符实际上就是加 减 乘 除 乘方等数学运算 即数与数之间的运算 运算结果也是数 LINGO中的算术运算符有以下5种 加法 减法或负号 乘法 除法 求幂 三 运算符和函数 3 1运算符 2020 2 24 逻辑运算即运算结果只有 真 TRUE 和 假 FALSE 两个值 称为 逻辑值 LINGO中用数字1代表TRUE 其他值 典型的值是0 都是FALSE 在LINGO中 逻辑运算 表达式 通常作为过滤条件使用 逻辑运算符有9种 可以分成两类 AND 与 OR 或 NOT 非 逻辑值之间的运算 它们操作的对象本身已经是逻辑值或逻辑表达式 计算结果也是逻辑值 EQ 等于 NE 不等于 GT 严格大于 GE 大于等于 LT 严格小于 LE 小于等于 是 数与数之间 的比较 也就是它们操作的对象本身必须是两个数 计算得到的结果是逻辑值 3 1 2逻辑运算符 2020 2 24 关系运算符表示是 数与数之间 的大小关系 在LINGO中用来表示优化模型的约束条件 LINGO中关系运算符有3种 即 大于等于 在优化模型中约束一般没有严格小于 严格大于关系 运算符的优先级 注2 关系运算符与逻辑运算符 eq le ge 截然不同 前者是模型中该关系运算符所指定关系的为真描述 而后者仅仅判断一个该关系是否被满足 满足为真 不满足为假 注1 LINGO并不支持严格小于和严格大于关系运算符 3 1 3关系运算符 2020 2 24 2 3 2基本的数学函数 在LINGO中建立优化模型时可以引用大量的内部函数 这些函数以 打头 LINGO中包括相当丰富的数学函数 这些函数的用法非常简单 下面一一列出 ABS X 绝对值函数 返回X的绝对值 COS X 余弦函数 返回X的余弦值 X的单位是弧度 EXP X 指数函数 返回 FLOOR X 取整函数 返回X的整数部分 向最靠近0的方向取整 LGM X 返回X的伽玛 gamma 函数的自然对数值 当X为整数时LGM X LOG X 1 当X不为整数时 采用线性插值得到结果 LOG X 自然对数函数 返回X的自然对数值 的值 其中e 2 718281 2020 2 24 基本的数学函数 MOD X Y 模函数 返回X对Y取模的结果 即X除以Y的余数 这里X和Y应该是整数 POW X Y 指数函数 返回XY的值 SIGN X 符号函数 返回X的符号值 X 0时返回 1 SIN X 正弦函数 返回X的正弦值 X的单位是弧度 SMAX list 最大值函数 返回一列数 list 的最大值 SMIN list 最小值函数 返回一列数 list 的最小值 SQR X 平方函数 返回X的平方 即X X 的值 SQRT X 开平方函数 返回X的正的平方根的值 TAN X 正切函数 返回X的正切值 X的单位是弧度 2020 2 24 集合循环函数 集合上的元素 下标 进行循环操作的函数 一般用法如下 function setname set index list condition expression list 其中 function集合函数名 FOR MAX MIN PROD SUM之一 Setname集合名 set index list集合索引列表 不需使用索引时可以省略 Condition用逻辑表达式描述的过滤条件 通常含有索引 无条件时可以省略 expression list一个表达式 对 FOR函数 可以是一组表达式 2020 2 24 集合循环函数 五个集合函数名的含义 FOR 集合元素的循环函数 对集合setname的每个元素独立地生成表达式 表达式由expression list描述 通常是优化问题的约束 MAX 集合属性的最大值函数 返回集合setname上的表达式的最大值 MIN 集合属性的最小值函数 返回集合setname上的表达式的最小值 PROD 集合属性的乘积函数 返回集合setname上的表达式的积 SUM 集合属性的求和函数 返回集合setname上的表达式的和 2020 2 24 集合操作函数 INDEX set name primitive set element 给出元素primitive set element在集合set name中的索引值 即按定义集合时元素出现顺序的位置编号 省略set name LINGO按模型中定义的集合顺序找到第一个含有该元素的集合 并返回索引值 如果没有找到该元素 则出错 注 Set name的索引值是正整数且只能位于1和元素个数之间 例 定义一个女孩姓名集合 GIRLS 和男孩姓名集合 BOYS SETS GIRLS DEBBIE SUE ALICE BOYS BOB JOE SUE FRED ENDSETS都有SUE GIRLS在BOYS前定义 调用 INDEX SUE 将返2 相当于 INDEX GIRLS SUE 要找男孩中名为SUE的小孩的索引 应该使用 INDEX BOYS SUE 返3 2020 2 24 集合操作函数 IN set name primitive index 1 primitive index 2 判断一个集合中是否含有某个索引值 如果集合set name中包含由索引primitive index 1 primitive index 2 所对应元素 则返回1 逻辑值 真 否则返回0 逻辑值 假 索引用 ENDSETS 2020 2 24 如果集合C是由集合A B派生的 例如 SETS A 1 3 B XYZ C A B 1 X1 Z2 Y3 X ENDSETS判断C中是否包含元素 2 Y 则可以利用以下语句 X IN C INDEX A 2 INDEX B Y 对本例 结果是X 1 真 注 X既是集合B的元素 又对X赋值1 在LINGO中这种表达是允许的 因为前者是集合的元素 后者是变量 逻辑上没有关系 除了同名外 所以不会出现混淆 集合操作函数 IN set name primitive index 1 primitive index 2 2020 2 24 WRAP I N 此函数对N 1无定义当I位于区间 1 N 内时直接返回I 一般地 返回J I K N 其中J位于区间 1 N K为整数 即 WRAP I N MOD I N 但当 MOD I N 0时 WRAP I N N 此函数可以用来防止集合的索引值越界 用户在编写LINGO程序时 应注意避免LINGO模型求解时出现集合的索引值越界的错误 集合操作函数 SIZE set name 返回数据集set name中包含元素的个数 2020 2 24 变量定界函数 对变量的取值范围附加限制 共有以下四种 BND L X U 限制L X U 注意LINGO中没有与LINDO命令SLB SUB类似的函数 SLB和 SUB BIN X 限制X为0或1 注意LINDO中的命令是INT 但LINGO中这个函数的名字却不是 INT X FREE X 取消对X的符号限制 即可取负数 0或正数 GIN X 限制X为整数 2020 2 24 通过文本文件输入数据 FILE函数通常可以在集合段和数据段使用 但不允许嵌套使用 调用格式 FILE filename filename为存放数据的文件名 可以包含完整的路径名 没有指定路径表示在当前目录下寻找这个文件 数据文件中记录之间必须用 分开 调用一个filename文件用一个 分开 FILE filename 当前模型引用其他ASCII码文件中的数据或文本时可以采用该语句 但不允许嵌套使用 其中filename为存放数据的文件名 该文件中记录之间用 分开 2020 2 24 例3 MODEL SETS MYSET FILE myfile ldt FILE myfile ldt ENDSETSMIN SUM MYSET I ORDERED I COST I FOR MYSET I ORDERED I NEED I ORDERED I SUPPLY I DATA COST FILE myfile ldt NEED FILE myfile ldt SUPPLY FILE myfile ldt ENDDATAEND 数据文件myfile ldt的内容 Lingo程序exam0402 LG4 每调用一次 FILE myfile ldt 就输入一个数据记录 Seattle Detroit Chicago Denver COST NEED SUPPLY ORDERED 12 28 15 20 1600 1800 1200 1000 1700 1900 1300 1100 如输入数据发生变化 则只要修改数据文件myfile ldt中的内容 程序不变 实现数据与程序分离 2020 2 24 习题用LINGO软件中的集合求解 2020 2 24 谢谢