通信网理论基础：LINGO

1、LingoLuo Dan 2013.5.20软件操作2 / 162013年秋季Lingo by Rodan软件操作3 / 162013年秋季Lingo by Rodan软件界面4 / 162013年秋季Lingo by RodanHow to5 / 16设起点为1，终点为n，引入01型决策变量Xij，如果弧(i , j)在最短路上，则Xij=1，否则Xij=0于是最短路问题可以用如下模型来描述：式中E表示全体边的集合 2013年秋季Lingo by Rodan优化中的两个变量概念2009年春季图算法及其在通信网络中的应用6 / 16通常是些给定的数据，如边容量capacity，安排单位流量耗费

2、的成本cost边界条件这个值到底取啥，是需要由优化来进行决定的。如最短路中选不选这条边Xij，ABC三种商品每样的进货量多少才能达到最大利润决策变量Lingo模型的基本要素7 / 16（1）集合段（SETS）（2）数据段（DATA）（3）初始段（INIT）赋初值（4）目标与约束段（5）计算段（CALC）预处理2013年秋季Lingo by Rodan集合段8 / 16集部分是LINGO模型的一个可选部分。在LINGO模型中使用集之前，必须在集部分事先定义。集部分以关键字“sets:”开始，以“endsets”结束。（前面的例子里面就没有集合定义）示例Setname /member_list/

3、:attribute_list; 原始集语法注意：用“ ”表示该部分内容可选。 Setname是你选择的来标记集的名字，Member_list是集成员列表。如果集成员放在集定义中，那么对它们可采取显式罗列和隐式罗列两种方式。如果集成员不放在集定义中，那么可以在随后的数据部分定义它们。Tips：参考C+中的变量定义功能2013年秋季Lingo by Rodan集合段9 / 16集部分是LINGO模型的一个可选部分。在LINGO模型中使用集之前，必须在集部分事先定义。集部分以关键字“sets:”开始，以“endsets”结束。（前面的例子里面就没有集合定义）示例Setname /member_li

4、st/ :attribute_list; 原始集语法 当显式罗列成员时，必须为每个成员输入一个不同的名字，中间用空格或逗号搁开，允许混合使用。例如 可以定义一个名为students 的原始集，它具有成员John、Jill、Rose和Mike，属性有sex 和age：sets:students/John, Jill, Rose, Mike/: sex, age;endsets2013年秋季Lingo by Rodan集合段示例Setname /member_list/ :attribute_list; 原始集语法2.当隐式罗列成员时，不必罗列出每个集成员。可采用如下语法： setname/mem

5、ber1.memberN/: attribute_list; 这里的member1是集的第一个成员名，memberN是集的最末一个成员名。LINGO将自动产生中间的所有成员名。LINGO也接受一些特定的首成员名和末成员名，用于创建一些特殊的集。示例：隐式成员列表格式示例所产生集成员1.n1.51,2,3,4,5StringM.StringNCar2.car14Car2,Car3,Car4,Car14DayM.DayNMon.FriMon,Tue,Wed,Thu,FriMonthM.MonthNOct.JanOct,Nov,Dec,JanMonthYearM.MonthYearNOct2001.

6、Jan2002Oct2001,Nov2001,Dec2001,Jan20022013年秋季Lingo by Rodan集合段示例Setname /member_list/ :attribute_list; 原始集语法 集成员不放在集定义中，而在随后的数据部分来定义。 !集部分;sets: students:sex,age; endsets !数据部分;data: students,sex,age= John 1 16 Jill 0 14 Rose 0 17 Mike 1 13; enddata不推荐2013年秋季Lingo by Rodan派生集合Setname (parent_set_lis

7、t) /member_list/ :attribute_list; 派生集语法setname是派生集的名字。parent_set_list是已定义的集的列表，多个时必须用逗号隔开。如果没有指定成员列表，那么LINGO会自动创建父集成员的所有组合作为派生集的成员。派生集的父集既可以是原始集，也可以是其它的派生集。指定成员： SETS: node/1,2,3,4/;!节点集合; link(node,node)/1,2 1,3 2,3 3,4/:weight,capacity;Endsets不指定成员： SETS: node/1,2,3,4/;!节点集合; link(node,node):weigh

8、t,capacity;Endsets2013年秋季Lingo by Rodan派生集合Setname (parent_set_list) /member_list/ :attribute_list; 派生集语法不是全部，但是满足某些条件？比如完全图（每个点都跟别的点邻接）加过滤条件派生集合名 (父集合) |过滤条件 :属性列表; 不指定成员： SETS: node/1,2,3,4/;!节点集合; link1(node,node):weight,capacity; ！成员个数为几个？ link2(node,node)|&2 #ne# &1: price;Endsets程序示例2013年秋季Lin

9、go by Rodan派生集合Setname (parent_set_list) /member_list/ :attribute_list; 派生集语法SETS: node/1,2,3,4/;!节点集合; link1(node,node):weight,capacity; link2(node,node)|&2 #ne# &1: price;Endsets成员列表充当了下标的角色2013年秋季Lingo by RodanLingo模型的基本要素15 / 16（1）集合段（SETS）（2）数据段（DATA）（3）初始段（INIT）赋初值（4）目标与约束段（5）计算段（CALC）预处理2013年

10、秋季Lingo by Rodan数据部分LINGO为用户提供了两个可选部分：输入集成员和数据的数据部分和为决策变量设置初始值的初始部分。数据部分以关键字“data:”开始，以关键字“enddata”结束。在这里，可以指定集成员、集的属性。语法： object_list = value_list; 对象列（object_list）包含要指定值的属性名、要设置集成员的集名，用逗号或空格隔开。一个对象列中至多有一个集名，而属性名可以有任意多。 数值列（value_list）包含要分配给对象列中的对象的值，用逗号或空格隔开。注意属性值的个数必须等于集成员的个数。2013年秋季Lingo by Roda

11、n数据部分语法： object_list = value_list; sets: glass/A,B,C/: capacity, price;endsets data: capacity =1,2,3; price =4,5,6; enddatasets: glass /A,B,C/: capacity, price; endsets data: capacity, price =1 4 2 5 3 6; enddata2013年秋季Lingo by RodanLingo模型的基本要素2013年秋季Lingo by Rodan18 / 16（1）集合段（SETS）（2）数据段（DATA）（3）

12、初始段（INIT）赋初值（4）目标与约束段（5）计算段（CALC）预处理模型的初始部分一个初始部分以“init:”开始，以“endinit”结束。初始部分的初始声明规则和数据部分的数据声明规则相同init: X, Y = 0, .1; endinit Y=log(X); X2+Y2 #eq# #ne# #gt# #ge# #lt# #le# #and# #or#目标与约束（2 ）逻辑运算符 2013年秋季Lingo by Rodan个人感觉：过滤条件condition处使用逻辑运算符，表达式中使用,=目标与约束（3 ）关系运算符关系运算符与逻辑运算符#eq#、#le#、#ge#截然不同，前者是

13、模型中该关系运算符所指定关系的为真描述，而后者仅仅判断一个该关系是否被满足：满足为真，不满足为假。LINGO有三种关系运算符：“=”、“=”。LINGO中还能用“”表示大于等于关系。LINGO并不支持严格小于和严格大于关系运算符。然而，如果需要严格小于和严格大于关系，比如让A严格小于B：AB，那么可以把它变成如下的小于等于表达式：A+=B，这里是一个小的正数，它的值依赖于模型中A小于B多少才算不等。2013年秋季Lingo by RodanLINGO提供了大量的标准数学函数：abs(x) 返回x的绝对值sin(x) 返回x的正弦值，x采用弧度制cos(x) 返回x的余弦值tan(x) 返回x的

14、正切值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中的最小值 目标与约束2013年秋季Lingo by Rodan集循环函数。function相应于下面罗列的四个集循环函数之一；setname是要遍历的集；set_ index_list是集索引列表；conditional_qualifier是用来限制集循环函数的范围，当集循环函数遍历集

15、的每个成员时，LINGO都要对conditional_qualifier进行评价，若结果为真，则对该成员执行function操作，否则跳过，继续执行下一次循环。expression_list是被应用到每个集成员的表达式列表，当用的是for函数时，expression_list可以包含多个表达式，其间用逗号隔开。这些表达式将被作为约束加到模型中。当使用其余的三个集循环函数时，expression_list只能有一个表达式。如果省略set_index_list，那么在expression_list中引用的所有属性的类型都是setname集。function(setname(set_index_li

16、st) |conditional_qualifier:（expression_list);2013年秋季Lingo by Rodan该函数用来产生对集成员的约束。基于建模语言的标量需要显式输入每个约束，不过for函数允许只输入一个约束，然后LINGO自动产生每个集成员的约束。例如 产生序列1,4,9,16,25model:sets: number/1.5/:x;endsets for(number(I): x(I)=I2);end Feasible solution found. Total solver iterations: 0 Variable Value X( 1) 1.000000

17、X( 2) 4.000000 X( 3) 9.000000 X( 4) 16.00000 X( 5) 25.00000 Row Slack or Surplus 1 0.000000 2 0.000000 3 0.000000 4 0.000000 5 0.000000(1) for2013年秋季Lingo by Rodan该函数用来产生对集成员的约束。基于建模语言的标量需要显式输入每个约束，不过for函数允许只输入一个约束，然后LINGO自动产生每个集成员的约束。例如 带过滤条件的：model:sets: number/1.5/:x;endsets for(number(i)|i#ne#2

18、: x(i)=i2);end(1) for将数据赋值放在约束里面2013年秋季Lingo by Rodan容量约束？（注意哪些值是给定了的) for( link(i,j):（ x(i,j) #LE# capacity(i,j) ）= 1 ); for( link(i,j) | I #lt# j: X(i ,j ) = 0 );(1) forfunction(setname(set_index_list) |conditional_qualifier:（expression_list);2013年秋季Lingo by Rodan30(2) sum该函数返回遍历指定的集成员的一个表达式的和。例4.

19、11 求向量5，1，3，4，6，10前5个数的和。model:data: N=6;enddatasets: number/1.N/:x;endsetsdata: x = 5 1 3 4 6 10;enddata s=sum(number(I) | I #le# 5: x);end(2) sum2013年秋季Lingo by Rodan31 Feasible solution found. Total solver iterations: 0 Variable Value N 6.000000 S 19.00000 X( 1) 5.000000 X( 2) 1.000000 X( 3) 3.00

20、0000 X( 4) 4.000000 X( 5) 6.000000 X( 6) 10.00000 Row Slack or Surplus 1 0.0000002013年秋季Lingo by Rodan32（3）min和max返回指定的集成员的一个表达式的最小值或最大值。例如 求向量5，1，3，4，6，10前5个数的最小值，后3个数的最大值。model:data: N=6;enddatasets: number/1.N/:x;endsetsdata: x = 5 1 3 4 6 10;enddata minv=min(number(I) | I #le# 5: x); maxv=max(nu

21、mber(I) | I #ge# N-2: x);end结果如下2013年秋季Lingo by Rodan33Feasible solution found. Total solver iterations: 0 Variable Value N 6.000000 MINV 1.000000 MAXV 10.00000 X( 1) 5.000000 X( 2) 1.000000 X( 3) 3.000000 X( 4) 4.000000 X( 5) 6.000000 X( 6) 10.00000 Row Slack or Surplus 1 0.000000 2 0.0000002013年秋季

22、Lingo by Rodan34 / 16AGFEDCB24123133134图中有7个顶点A,B,.,G，边上的数字表示权重Wij，求从顶点A到G距离最短的路径。设起点为1，终点为n，引入01型决策变量Xij，如果弧(i , j)在最短路上，则Xij=1，否则Xij=0于是最短路问题可以用如下模型来描述：式中E表示全体边的集合 2013年秋季Lingo by Rodan对于上例，编写LINGO程序如下：model:sets:nodes/A,B,C,D,E,F,G/; !定义7个顶点;links(nodes,nodes)/ A,B A,C B,D B,E B,F C,D C,E C,F D,G E,G F,G/: W, X;!定义哪些顶点之间有边相联，W为权重，X为01型决策变量;endsetsdata: W=2 4 3 3 1 2 3 1 1 3 4;enddata N=size(nodes); min=sum(links:W*