通信网理论基础(虞红芳)ling.ppt

《通信网理论基础(虞红芳)ling.ppt》由会员分享，可在线阅读，更多相关《通信网理论基础(虞红芳)ling.ppt（38页珍藏版）》请在三一办公上搜索。

1、Lingo,软件操作,2/16,2013年秋季Lingo by Rodan,软件操作,3/16,2013年秋季Lingo by Rodan,软件界面,4/16,2013年秋季Lingo by Rodan,How to,5/16,设起点为1，终点为n，引入01型决策变量Xij，如果弧(i,j)在最短路上，则Xij=1，否则Xij=0于是最短路问题可以用如下模型来描述：,式中E表示全体边的集合,2013年秋季Lingo by Rodan,优化中的两个变量概念,2009年春季图算法及其在通信网络中的应用,6/16,Lingo模型的基本要素,7/16,2013年秋季Lingo by Rodan,集合段

2、,8/16,示例,注意：用“”表示该部分内容可选。Setname是你选择的来标记集的名字，Member_list是集成员列表。如果集成员放在集定义中，那么对它们可采取显式罗列和隐式罗列两种方式。如果集成员不放在集定义中，那么可以在随后的数据部分定义它们。,Tips：参考C+中的变量定义功能,2013年秋季Lingo by Rodan,集合段,9/16,示例,Setname/member_list/:attribute_list;,原始集语法,当显式罗列成员时，必须为每个成员输入一个不同的名字，中间用空格或逗号搁开，允许混合使用。例如 可以定义一个名为students 的原始集，它具有成员Joh

3、n、Jill、Rose和Mike，属性有sex 和age：sets:students/John,Jill,Rose,Mike/:sex,age;endsets,2013年秋季Lingo by Rodan,集合段,示例,Setname/member_list/:attribute_list;,原始集语法,2.当隐式罗列成员时，不必罗列出每个集成员。可采用如下语法：setname/member1.memberN/:attribute_list;这里的member1是集的第一个成员名，memberN是集的最末一个成员名。LINGO将自动产生中间的所有成员名。LINGO也接受一些特定的首成员名和末成员

4、名，用于创建一些特殊的集。示例：,2013年秋季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_list)/member_list/:attribut

5、e_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):weight,capacity;Endsets,2013年秋季Lin

6、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)|Endsets,程序示例,2013年秋季Lingo by Rodan,派生集合,Setname(parent_set_list)/member_l

7、ist/:attribute_list;,派生集语法,SETS:node/1,2,3,4/;!节点集合;link1(node,node):weight,capacity;link2(node,node)|Endsets,成员列表充当了下标的角色,2013年秋季Lingo by Rodan,Lingo模型的基本要素,15/16,2013年秋季Lingo by Rodan,数据部分,对象列（object_list）包含要指定值的属性名、要设置集成员的集名，用逗号或空格隔开。一个对象列中至多有一个集名，而属性名可以有任意多。数值列（value_list）包含要分配给对象列中的对象的值，用逗号或空格隔

8、开。注意属性值的个数必须等于集成员的个数。,2013年秋季Lingo by Rodan,数据部分,sets:glass/A,B,C/:capacity,price;endsets data:capacity=1,2,3;price=4,5,6;enddata,sets:glass/A,B,C/:capacity,price;endsets data:capacity,price=1 4 2 5 3 6;enddata,2013年秋季Lingo by Rodan,Lingo模型的基本要素,2013年秋季Lingo by Rodan,18/16,模型的初始部分,一个初始部分以“init:”开始，以

9、“endinit”结束。初始部分的初始声明规则和数据部分的数据声明规则相同,init:X,Y=0,.1;endinit Y=log(X);X2+Y2=1;,没什么太大区别，减少求解时间？呵呵,2013年秋季Lingo by Rodan,Lingo模型的基本要素,20/16,2013年秋季Lingo by Rodan,2013年秋季Lingo by Rodan,目标与约束,算术运算符是针对数值进行操作的。LINGO提供了5种二元运算符：乘方乘除加减LINGO唯一的一元算术运算符是取反函数“”。这些运算符的优先级由高到底为：高（取反）低运算符的运算次序为从左到右按优先级高低来执行。运算的次序可以用

10、圆括号“（）”来改变。例如 算术运算符示例。253，(24)5等等。,(1)算术运算符,2013年秋季Lingo by Rodan,变量界定函数实现对变量取值范围的附加限制，共4种：bin(x)限制x为0或1 bnd(L,x,U)限制LxU free(x)取消对变量x的默认下界为0的限制，即x可以取任意实数 gin(x)限制x为整数 在默认情况下，LINGO规定变量是非负的，也就是说下界为0，上界为+。,目标与约束,2013年秋季Lingo by Rodan,#not#否定该操作数的逻辑值，not是一个一元运算符#eq#若两个运算数相等，则为true；否则为flase#ne#若两个运算符不相等

11、，则为true；否则为flase#gt#若左边的运算符严格大于右边的，则为true；否则为flase#ge#若左边的运算符大于或等于右边的，则为true；否则为flase#lt#若左边的运算符严格小于右边的，则为true；否则为flase#le#若左边的运算符小于或等于右边的，则为true；否则为flase#and#仅当两个参数都为true时，结果为true；否则为flase#or#仅当两个参数都为false时，结果为false；否则为true 这些运算符的优先级由高到低为：#not#eq#ne#gt#ge#lt#le#and#or#,目标与约束,（2）逻辑运算符,2013年秋季Lingo b

12、y Rodan,个人感觉：过滤条件condition处使用逻辑运算符，表达式中使用,=,目标与约束,（3）关系运算符,关系运算符与逻辑运算符#eq#、#le#、#ge#截然不同，前者是模型中该关系运算符所指定关系的为真描述，而后者仅仅判断一个该关系是否被满足：满足为真，不满足为假。,LINGO有三种关系运算符：“=”、“=”。,LINGO中还能用“”表示大于等于关系。LINGO并不支持严格小于和严格大于关系运算符。然而，如果需要严格小于和严格大于关系，比如让A严格小于B：AB，那么可以把它变成如下的小于等于表达式：A+=B，这里是一个小的正数，它的值依赖于模型中A小于B多少才算不等。,2013

13、年秋季Lingo by Rodan,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中的最小值,目标与约束,2013年秋季Lingo by Rodan,集循环函数,。function相应于下面罗列的四

14、个集循环函数之一；setname是要遍历的集；set_ index_list是集索引列表；conditional_qualifier是用来限制集循环函数的范围，当集循环函数遍历集的每个成员时，LINGO都要对conditional_qualifier进行评价，若结果为真，则对该成员执行function操作，否则跳过，继续执行下一次循环。expression_list是被应用到每个集成员的表达式列表，当用的是for函数时，expression_list可以包含多个表达式，其间用逗号隔开。这些表达式将被作为约束加到模型中。当使用其余的三个集循环函数时，expression_list只能有一个表达式

15、。如果省略set_index_list，那么在expression_list中引用的所有属性的类型都是setname集。,function(setname(set_index_list)|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)=I

16、2);end,Feasible solution found.Total solver iterations:0 Variable Value X(1)1.000000 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)for,2013年秋季Lingo by Rodan,该函数用来产生对集成员的约束。基于建模语言的标量需要显式输入每个约束，不过for函数允许只输入一个约束，然后LING

17、O自动产生每个集成员的约束。例如 带过滤条件的：model:sets:number/1.5/:x;endsets for(number(i)|i#ne#2: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)for,function(setname(set_index_list)|conditional_qualifier:（expression_li

18、st);,2013年秋季Lingo by Rodan,30,(2)sum该函数返回遍历指定的集成员的一个表达式的和。例4.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)sum,2013年秋季Lingo by Rodan,31,Feasible solution found.Total solver iterations:0 Variable Value N 6.000000

19、S 19.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,2013年秋季Lingo by Rodan,32,（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(

20、number(I)|I#le#5:x);maxv=max(number(I)|I#ge#N-2:x);end,结果如下,2013年秋季Lingo by Rodan,33,Feasible 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

21、 0.000000,2013年秋季Lingo by Rodan,34/16,图中有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

22、,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*X);for(nodes(i)|i#gt#1#and#i#lt#N:sum(links(i,j):X(i,j)=sum(links(j,i):X(j,i);sum(links(i,j)|i#eq#1:X(i,j)=1;sum(links(i,j)|j#eq#N:X(i,j)=1;end,2013年秋季Lingo by Rodan,图示网络的每一条弧上括号内有两个数字，

23、前一个数字代表该弧上的容量，后一个数字是单位费用用capij表示弧(i,j)上的容量，xij表示弧(i,j)上的流量，cij表示单位费用，设有s到t的需求为h=14，求最小费用。模型如下：,2013年秋季Lingo by Rodan,MODEL:sets:nodes/s,1,2,3,4,t/;links(nodes,nodes)/s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/:cost,cap,x;endsetsdata:h=14;cost=2 8 5 2 3 1 6 4 7;cap=8 7 5 9 9 2 5 6 10;enddata min=sum(links:cost*x);N=size(nodes);for(nodes(i)|i#ne#1#and#i#ne#N:sum(links(i,j):x(i,j)-sum(links(j,i):x(j,i)=0);sum(links(i,j)|i#eq#1:x(i,j)=h;sum(links(i,j)|j#eq#N:x(i,j)=h;for(links:bnd(0,x,cap);END,2013年秋季Lingo by Rodan,