Lingo求解运输问题课件.ppt

1、（Linear Interactive General Optimizer）LINGO简介简介LINGO（Linear Interactive General Optimizer）是用来求解线性和非线性优化问题的简易工具。是用来求解线性和非线性优化问题的简易工具。LINGO内置了一种建立最优化模型的语言，可以简内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用便地表达大规模问题，利用LINGO高效的求解器可高效的求解器可快速求解并分析结果。快速求解并分析结果。0,6002100350.32min212112121xxxxxxxtsxx例例1 1 如何在如何在LINGOLINGO中求

2、解如下的中求解如下的LPLP问题：问题：min=2*x1+3*x2;x1+x2=350;x1=100;2*x1+x2=600;然后点击工具条上的按钮然后点击工具条上的按钮 即可。即可。在模型窗口中输入如下代码：在模型窗口中输入如下代码：例例2 直接用直接用LINGO来解如下二次规划问题：来解如下二次规划问题：40,322100.123.02779821212122212121为整数xxxxxxtsxxxxxxMax输入窗口如下：输入窗口如下：程序语句输入的备注：程序语句输入的备注：LINGO总是根据总是根据“MAX=”或或“MIN=”寻找目标函数，而除注寻找目标函数，而除注释语句和释语句和TI

3、TLE语句外的其他语句都是约束条件，因此语句的语句外的其他语句都是约束条件，因此语句的顺序并不重要顺序并不重要。限定变量取整数值的语句为限定变量取整数值的语句为“GIN(X1)”和和“GIN(X2)”，不可以写成不可以写成“GIN(2)”，否则，否则LINGO将把这个模型看成没有将把这个模型看成没有整数变量。整数变量。LINGO中函数一律需要以中函数一律需要以“”开头，其中整型变量函数开头，其中整型变量函数（BIN、GIN）和上下界限定函数（）和上下界限定函数（FREE、SUB、SLB）与）与LINDO中的命令类似。而且中的命令类似。而且0/1变量函数是变量函数是BIN函函数。数。LINGO的

4、基本用法的几点注意事项的基本用法的几点注意事项 LINGO中不区分大小写字母；变量和行名可以超过中不区分大小写字母；变量和行名可以超过8个字符，个字符，但不能超过但不能超过32个字符，且必须以字母开头。个字符，且必须以字母开头。用用LINGO解优化模型时已假定所有变量非负解优化模型时已假定所有变量非负(除非用限定变量取除非用限定变量取值范围的函数值范围的函数free或或sub或或slb另行说明另行说明)。变量可以放在约束条件的右端变量可以放在约束条件的右端(同时数字也可放在约束条件的左同时数字也可放在约束条件的左端端)。但为了提高。但为了提高LINGO求解时的效率，应尽可能采用线性表达求解时的

5、效率，应尽可能采用线性表达式定义目标和约束式定义目标和约束(如果可能的话如果可能的话)。语句是组成语句是组成LINGO模型的基本单位模型的基本单位,每个语句都以分号结尾，编每个语句都以分号结尾，编写程序时应注意模型的可读性。例如：一行只写一个语句，按照写程序时应注意模型的可读性。例如：一行只写一个语句，按照语句之间的嵌套关系对语句安排适当的缩进，增强层次感。语句之间的嵌套关系对语句安排适当的缩进，增强层次感。以感叹号开始的是说明语句以感叹号开始的是说明语句(说明语句也需要以分号结束说明语句也需要以分号结束)。LINGO模型最基本的组成要素模型最基本的组成要素 一般来说，一般来说，LINGO中建

6、立的优化模型可以由五个部分组成，或中建立的优化模型可以由五个部分组成，或称为五称为五“段段”（SECTION）：）：（1 1）集合段（）集合段（SETSSETS）：）：以以“SETS:”开始，开始，“ENDSETS”结束，定义必要的集合变量（结束，定义必要的集合变量（SET）及其元素（）及其元素（MEMBER，含义类似于数组的下标）和属性（含义类似于数组的下标）和属性（ATTRIBUTE，含义类似于，含义类似于数组）。数组）。基本集合的定义语法基本集合的定义语法 基本集合的定义格式为基本集合的定义格式为(方括号方括号“”中的内容是可选项中的内容是可选项,可以没可以没有有):setname/me

7、mber_list/:attribute_list;类型隐式列举格式示例示例集合表示的元素数字型1.n1.51,2,3,4,5字符-数字型stringM.stringNCar101.car208Car101,car102,car208日期（星期）型dayM.dayNMON.FRIMON,TUE,WED,THU,FRI月份型monthM.monthNOCT.JANOCT,NOV,DEC,JAN年份-月份型monthYearM.monthYearNOCT2001.JAN2002OCT2001,NOV2001,DEC2001,JAN2002 setname/member_list/:attribut

8、e_list;其中其中setname为定义的集合名，为定义的集合名，member_list为元素列表，为元素列表，attribute_list为属性列表。元素列表可以采用显式列举法为属性列表。元素列表可以采用显式列举法(即直即直接将所有元素全部列出接将所有元素全部列出,元素之间用逗号或空格分开元素之间用逗号或空格分开),也可以采也可以采用隐式列举法，隐式列举法可以有几种不同格式。用隐式列举法，隐式列举法可以有几种不同格式。（2 2）目标与约束段）目标与约束段：目标函数、约束条件等，没有段的开：目标函数、约束条件等，没有段的开始和结束标记，因此实际上就是除其它四个段始和结束标记，因此实际上就是除

9、其它四个段(都有明确的段都有明确的段标记标记)外的外的LINGO模型。模型。这里一般要用到这里一般要用到LINGO的内部函数，尤其是与集合相关的的内部函数，尤其是与集合相关的求和函数求和函数SUM和循环函数和循环函数FOR等。等。（3 3）数据段）数据段(DATA)(DATA)：以：以“DATA:”开始开始,“ENDDATA”结束，结束，对集合的属性对集合的属性(数组数组)输入必要的常数数据。输入必要的常数数据。格式为：格式为：“attribute(属性属性)=value_list(常数列表常数列表);”常数列表常数列表(value_list)中数据之间可以用逗号中数据之间可以用逗号“,”分开

10、，也可以用分开，也可以用空格分开空格分开(回车等价于一个空格回车等价于一个空格)。（4 4）初始段）初始段(INIT)(INIT)：以：以“INIT:”开始，开始，“ENDINIT”结束，结束，对集合的属性对集合的属性(数组数组)定义初值定义初值(因为求解算法一般是迭代算法，因为求解算法一般是迭代算法，所以用户如果能给出一个比较好的迭代初值，对提高算法的计所以用户如果能给出一个比较好的迭代初值，对提高算法的计算效果是有益的算效果是有益的)。如果有一个接近最优解的初值，对如果有一个接近最优解的初值，对LINGO求解模型是有帮求解模型是有帮助的。定义初值的格式为：助的。定义初值的格式为：“attr

11、ibute（属性）（属性）=value_list（常数列表）；（常数列表）；”这与数据段中的用法是类似的。这与数据段中的用法是类似的。（5 5）计算段）计算段(CALC)(CALC)：以：以“CALC:”开始，开始，“ENDCALC”结结束，对一些原始数据进行计算处理。束，对一些原始数据进行计算处理。在实际问题中，输入的数据通常是原始数据，不一定能在模在实际问题中，输入的数据通常是原始数据，不一定能在模型中直接使用，可以在这个段对这些原始数据进行一定的型中直接使用，可以在这个段对这些原始数据进行一定的“预预处理处理”，得到模型中真正需要的数据。，得到模型中真正需要的数据。逻辑运算符逻辑运算符运

12、算结果只有运算结果只有“真真”(TRUE)和和“假假”(FALSE)两个值两个值(称为称为“逻逻辑值辑值”)，LINGO中用数字中用数字1代表代表TRUE，其他值，其他值(典型的值是典型的值是0)都都是是FALSE。在在LINGO中，逻辑运算中，逻辑运算(表达式表达式)通常作为过滤条件使用通常作为过滤条件使用,逻辑运逻辑运算符有算符有9种，可以分成两类：种，可以分成两类：#AND#(与与),#OR#(或或),#NOT#(非非)：逻辑值之间的运算，它们操：逻辑值之间的运算，它们操作的对象本身已经是逻辑值或逻辑表达式，计算结果也是逻辑值。作的对象本身已经是逻辑值或逻辑表达式，计算结果也是逻辑值。#

13、EQ#(等于等于),#NE#(不等于不等于),#GT#(大于大于),#GE#(大于等于大于等于),#LT#(小小于于),#LE#(小于等于小于等于)：是：是“数与数之间数与数之间”的比较的比较,也就是它们操作也就是它们操作的对象本身必须是两个数的对象本身必须是两个数,计算得到的结果是逻辑值。计算得到的结果是逻辑值。关系运算符关系运算符表示是表示是“数与数之间数与数之间”的大小关系，在的大小关系，在LINGO中用来表示优中用来表示优化模型的约束条件。化模型的约束条件。LINGO中关系运算符有中关系运算符有3种：种：(即即(即即=，大于等于，大于等于)(在优化模型中在优化模型中约束一般没有严格小于

14、、严格大于关系约束一般没有严格小于、严格大于关系)运算符的优先级运算符的优先级 优先级最高 最低运算符#NOT#(负号)*/+(减法)#EQ#NE#GT#GE#LT#LE#AND#OR#例例4 4 使用使用LINGOLINGO软件计算软件计算6 6个发点个发点8 8个收点的最小费用运输问个收点的最小费用运输问题。产销单位运价如下表。题。产销单位运价如下表。单单位位 销地销地 运运 价价 产地产地B B1 1B B2 2B B3 3B B4 4B B5 5B B6 6B B7 7B B8 8产量产量A A1 16 62 26 67 74 42 25 59 96060A A2 24 49 95 5

15、3 38 85 58 82 25555A A3 35 52 21 19 97 74 43 33 35151A A4 47 76 67 73 39 92 27 71 14343A A5 52 23 39 95 57 72 26 65 54141A A6 65 55 52 22 28 81 14 43 35252销量销量35353737222232324141323243433838 6 8 min z=cijxij i=1 j=1 8 s.t.xijai （i=1,2,6)j=1 6 xij=bj （j=1,2,8)i=1 xij 0 （i=1,2,6；j=1,2,8)建立模型建立模型：（产大于

16、销）（产大于销）设设xij为从第为从第i个产地调运给第个产地调运给第j个销地的物资数量个销地的物资数量model:!6发点8收点运输问题;sets:warehouses/wh1.wh6/:capacity;vendors/v1.v8/:demand;links(warehouses,vendors):cost,volume;endsets!目标函数;min=sum(links:cost*volume);!需求约束;for(vendors(J):sum(warehouses(I):volume(I,J)=demand(J);!产量约束;for(warehouses(I):sum(vendors(

17、J):volume(I,J)=capacity(I);!这里是数据;然后点击工具条上的按钮然后点击工具条上的按钮 即可。即可。使用使用LINGO软件，编制程序如下：软件，编制程序如下：data:capacity=605551434152;demand=3537223241324338;cost=626742954953858252197433767392712395726555228143;enddataend集合的属性相当于以集合的元素为下标的数组。这里的集合的属性相当于以集合的元素为下标的数组。这里的 相相当于二维数组。它的两个下标分别来自集合当于二维数组。它的两个下标分别来自集合ware

18、houses 和和vendors，因此可以定义一个由二元对组成的新的集合，然，因此可以定义一个由二元对组成的新的集合，然后将后将 定义成这个新集合的属性。定义成这个新集合的属性。ijcijc本例中集合的概念本例中集合的概念利用集合的概念，可以定义产地利用集合的概念，可以定义产地warehouses和销地和销地vendors两个两个集合，分别有集合，分别有6个和个和8个元素个元素(下标下标)，其属性分别为产量，其属性分别为产量capacity和销量和销量demand。但从各个产地到销地的单位运价。但从各个产地到销地的单位运价 和决策变量和决策变量(运送量运送量)与集合与集合warehouses和

19、集合和集合vendors都有关系的。该如都有关系的。该如何定义这样的属性？何定义这样的属性？ijcijx输入程序输入程序 定义了三个集合，其中定义了三个集合，其中links在前两在前两个集合个集合warehouses 和和vendors的基的基础上定义础上定义model:!6发点8收点运输问题;sets:warehouses/wh1.wh6/:capacity;vendors/v1.v8/:demand;links(warehouses,vendors):cost,volume;endsets!目标函数;min=sum(links:cost*volume);!需求约束;for(vendors(

20、J):sum(warehouses(I):volume(I,J)=demand(J);!产量约束;for(warehouses(I):sum(vendors(J):volume(I,J)=capacity(I);!这里是数据;LINGO建模语言也称为矩阵生成器（建模语言也称为矩阵生成器（MATRIX GENERATOR）。类似）。类似warehouses 和和vendors直接把元素列举出直接把元素列举出来的集合，称为来的集合，称为基本集合基本集合(primary set),而把而把links这种基于其它这种基于其它集合而派生出来的二维或多维集合称为集合而派生出来的二维或多维集合称为派生集合派

21、生集合(derived set)。由于是由于是warehouses 和和vendors 生成了派生集合生成了派生集合links，所以，所以warehouses 和和vendors 称为称为links的的父集合父集合。data:capacity=605551434152;demand=3537223241324338;cost=626742954953858252197433767392712395726555228143;enddataend表示集合表示集合links中的元素就是集合中的元素就是集合warehouses 和和vendors的元素组合的元素组合成的有序二元组，从数学上看成的有序二

22、元组，从数学上看link是是warehouses 和和vendors的笛卡儿的笛卡儿积，也就是说积，也就是说links=（S，T）|Swarehouses，Tvendors因此，其属性因此，其属性cost和和volume也就是也就是一个一个6*8的矩阵（或者说是含有的矩阵（或者说是含有48个元素的二维数组）。个元素的二维数组）。18目标函数的定义方式目标函数的定义方式SUM(集合（下标）：关于集合的属性的表达式集合（下标）：关于集合的属性的表达式)对语句中冒号对语句中冒号“：”后面的表达式，按照后面的表达式，按照“：”前面的集合前面的集合指定的下标（元素）进行求和。指定的下标（元素）进行求和。

23、约束的定义方式约束的定义方式循环函数循环函数FOR(集合集合(下标下标)：关于集合的属性的约束关系式：关于集合的属性的约束关系式)对冒号对冒号“：”前面的集合的每个元素（下标），冒号前面的集合的每个元素（下标），冒号“：”后后面的约束关系式都要成立面的约束关系式都要成立。1,0,2,1,1,2,1,1.min1111ijnjijniijninjijijxnixnjxtsxc例例5 5 分配问题（指派问题，分配问题（指派问题，Assignment ProblemAssignment Problem）要求给每个人分配一项工作，并要求分配完这些工作，以使完成全部任务的总时间为最小。该问题可表示如下：这是个给n个人分配n项工作以获得某个最高总效果的问题。第i个人完成第j项工作需要平均时间。ijc 显然，此问题可看作是运输问题的特殊情况。可将此问题看 作具有n个源和n个汇的问题，每个源有1单位的可获量，而 每个汇 有1单位的需要量。从表面看，这问题要求用整 数规划以保证能取0或1。然而，幸运的是，此问题是运ijx输问题的特例，因此即使不限制取0或1，最优解也将取0或1。ijx显然，分配问题可以作为线性规划问题来求解，尽管模型可能很大。例如，给100人分配100项工作将使所得的模型具有10000个变量。这时，如采用专门算法效果会更好。时间复杂度为 的匈牙利算法便是好选择。)(3nO