第4讲LINGO基本使用方法续.ppt
《第4讲LINGO基本使用方法续.ppt》由会员分享,可在线阅读,更多相关《第4讲LINGO基本使用方法续.ppt(33页珍藏版)》请在三一文库上搜索。
1、2019/4/9,第4讲:LINGO基本使用方法,在LINGO中使用集合(续) 运算符和函数,2019/4/9,包含了两个基本集合构成的所有二元有序对的派生集合称为稠密集合(简称稠集)。有时候,在实际问题中,一些属性(数组) 只在笛卡儿积的一个真子集合上定义,这种派生集合称为稀疏集合(简称疏集)。,例1 (最短路问题) 在纵横交错的公路网中,货车司机希望找到一条从一个城市到另一个城市的最短路. 下图表示的是公路网, 节点表示货车可以停靠的城市,弧上的权表示两个城市之间的距离(百公里). 那么,货车从城市S出发到达城市T,如何选择行驶路线,使所经过的路程最短?,二、在LINGO中使用集合(续),
2、2.4 稠密集合与稀疏集合,2019/4/9,分析,假设从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)的最优行驶路线. 而
3、S到Ai(i=1,2,3)的最优行驶路线是很容易得到的(实际上, 此例中S到Ai(i=1,2,3)只有唯一的道路),2019/4/9,分析,此例中可把从S到T的行驶过程分成4个阶段,即 SAi (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的最优行驶路线的路长:,2019/4/9,本例的计算,所以, 从S到T的最优行驶路线的路长为20. 进一步分析以上求解过程, 可以得到从S到T的最优行驶路线为 S A3 B2 C1 T
4、.,这种计算方法在数学上称为动态规划(Dynamic Programming),2019/4/9,本例的LINGO求解,“CITIES”(城市):一个基本集合(元素通过枚举给出),L:CITIES对应的属性变量(我们要求的最短路长),“ROADS”(道路):由CITIES导出的一个派生集合(请特别注意其用法),由于只有一部分城市之间有道路相连,所以不应该把它定义成稠密集合,将其元素通过枚举给出,这就是一个稀疏集合。,D:稀疏集合ROADS对应的属性变量(给定的距离),2019/4/9,本例的LINGO求解,从模型中还可以看出:这个LINGO程序可以没有目标函数,这在LINGO中,可以用来找可行
5、解(解方程组和不等式组)。,在数据段对L进行赋值,只有L(S)=0已知,后面的值为空(但位置必须留出来,即逗号“,”一个也不能少,否则会出错)。如果这个语句直接写成“L=0;”,语法上看也是对的,但其含义是L所有元素的取值全部为0,所以也会与题意不符。,2019/4/9,本例的LINGO求解,虽然集合CITIES中的元素不是数字,但当它以CITIES(I)的形式出现在循环中时,引用下标I却实际上仍是正整数,也就是说I指的正是元素在集合中的位置(顺序),一般称为元素的索引(INDEX)。,在for循环中的过滤条件里用了一个函数“index”, 其作用是返回一个元素在集合中的索引值,这里index
6、(S)=1(即元素S在集合中的索引值为1),所以逻辑关系式“i#GT#index(S)”可以直接等价地写成“i#GT#1” 。这里index(S)实际上还是index(CITIES,S)的简写,即返回S在集合CITIES中的索引值。,2019/4/9,本例的LINGO求解结果,从S到T的最优行驶路线的路长为20(进一步分析,可以得到最优行驶路线为S A3 B2 C1 T)。,本例中定义稀疏集合ROADS的方法是将其元素通过枚举给出,有时如果元素比较多,用起来不方便。另一种定义稀疏集合的方法是“元素过滤”法,能够从笛卡儿积中系统地过滤下来一些真正的元素。,2019/4/9,例2 某班8名同学准备
7、分成4个调查队(每队两人)前往4个地区进行社会调查。这8名同学两两之间组队的效率如下表所示(由于对称性,只列出了严格上三角部分),问如何组队可以使总效率最高?,2019/4/9,分析,这是一个匹配(MATCHING)问题。把上表的效率矩阵记为BENEFIT(由于对称性,这个矩阵只有严格上三角部分共28个数取非零值)。 用MATCH(Si,Sj)=1表示同学Si,Sj组成一队 ,而MATCH(Si,Sj)=0表示Si,Sj不组队。由于对称性,只需考虑ij共28个0-1变量(而不是全部32个变量)。 显然,目标函数正好是BENEFIT(Si,Sj)*MATCH(Si,Sj)对I,j之和。 约束条件
8、是每个同学只能(而且必须在)某一组,即对于任意i有:只要属性MATCH的某个下标为i就加起来,此和应该等于1。,由上面的分析,因此,完整的数学模型如下(显然,这是一个0-1线性规划):,2019/4/9,问题的LINGO求解,“S1S8”等价于写成“S1 S2 S3 S4 S5 S6 S7 S8”, 它没有相关的属性列表,只用于表示是一个下标集合,在派生集合PAIRS定义中增加了过滤条件 “&2#GT#&1”,意思是第2个父集合的元素的索引值(用“&2”表示)大于第1个父集合的元素的索引值(用“&1”表示)。PAIRS中的元素对应于上表中的严格上三角部分的二维下标(共28个元素)。BENEFI
9、T和MATCH是PAIRS的属性。,注意数据段对BENEFIT的赋值方式,“LINGO按照列的顺序对属性变量的元素进行赋值。在约束部分,过滤条件“J #EQ# I #OR# K #EQ# I”是由逻辑运算符“#OR#(或者)”连接的一个复合的逻辑关系式,连接由“#EQ#(等于)”表示的两个逻辑关系。由于“#OR#”的运算级别低于“#EQ#”,所以这个逻辑式中没有必要使用括号指定运算次序。,2019/4/9,LINGO求解结果,“LINGO|SOLVE”运行这个程序,可以得到全局最优值为30,MATCH变量中多数为0,可以更清晰地浏览最优解解。 选择菜单命令“LINGO|SOLUTION”,可以
10、看到图示对话框。,选择属性MATCH(变量),选择Text(文本格式),选择Nonzeros Only(只显示非零值),点击“OK”按钮,得到关于最优解的非零分量的报告,学生最佳的组队方式是(1,8),(2,4),(3,7),(5,6).,2019/4/9,集合的使用小结,集合的不同类型及其关系,2019/4/9,基本集合的定义语法,基本集合的定义格式为(方括号“ ”中的内容是可选项, 可以没有): setname /member_list/ : attribute_list; 其中setname为定义的集合名,member_list为元素列表,attribute_list为属性列表。元素列表
11、可以采用显式列举法(即直接将所有元素全部列出,元素之间用逗号或空格分开),也可以采用隐式列举法。隐式列举法可以有几种不同格式,,2019/4/9,元素列表和属性列表都是可选的。 当属性列表不在集合定义中出现时,这样的集合往往只是为了将来在程序中作为一个循环变量来使用,或者作为构造更复杂的派生集合的父集合使用(匹配问题中的集合STUDENTS没有属性列表)。 而当元素列表不在基本集合的定义中出现时,则必须在程序的数据段以赋值语句的方式直接给出元素列表。 例如,前例中SAILCO公司决定四个季度的帆船生产量模型的集合段和数据段可以分别改为: SETS: QUARTERS:DEM,RP,OP,INV
12、; !注意没有给出集合的元素列表; ENDSETS DATA: QUARTERS DEM=1 40 2 60 3 75 4 25; !注意LINGO按列赋值的特点; ENDDATA,基本集合的定义语法,帆船生产量模型的源程序,匹配问题的源程序,2019/4/9,派生集合的定义语法,派生集合的定义格式为(方括号“ ”中的内容是可选项, 可以没有): setname(parent_set_list) /member_list/ : attribute_list; 与基本集合的定义相比较多了一个parent_set_list(父集合列表)。 父集合列表中的集合(如 set1,set2,等)称为派生集
13、合setname的父集合,它们本身也可以是派生集合。 当元素列表(member_list)不在集合定义中出现时,还可以在程序的数据段以赋值语句的方式给出元素列表; 若在程序的数据段也不以赋值语句的方式给出元素列表,则认为定义的是稠密集合,即父集合中所有元素的有序组合(笛卡儿积)都是setname的元素。 当元素列表在集合定义中出现时,又有“元素列表法”(直接列出元素)和“元素过滤法”(利用过滤条件)两种不同方式。,2019/4/9,3.1.1 算术运算符,算数运算符实际上就是加、减、乘、除、乘方等数学运算(即数与数之间的运算,运算结果也是数)。 LINGO中的算术运算符有以下5种: +(加法)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- LINGO 基本 使用方法
链接地址:https://www.31doc.com/p-2566672.html