第七讲数学规划与Lingo课件.ppt

2013数学建模培训数学建模培训第七讲第七讲 数学规划与数学规划与Lingo一、引一、引一、引一、引 言言言言 在在实实际际中中，经经常常会会遇遇到到如如何何利利用用现现有有资资源源来来安安排排生生产产，以以取取得得最最大大经经济济效效益益的的问问题题，这这类类问问题题构构成成了了运运筹筹学的一个重要分支学的一个重要分支数学规划数学规划。数学规划包括线性规划、整数规数学规划包括线性规划、整数规划、目标规划、非线性规划、动态规划、目标规划、非线性规划、动态规划等。划等。数学规划是建模竞赛中最常见的数学规划是建模竞赛中最常见的1/12/20234模模型型，2005B,2006A,2007B,2011B等均与数学规划密切相关。等均与数学规划密切相关。可可以以用用Matlab求求解解数数学学规规划划,但但最最便便捷捷的的方方法法是是利利用用优优化化专专用用软软件件包包Lingo。Lingo不不仅仅能能精精确确、快快捷捷地地求求解解包包括括数数学学规规划划在在内内的的几几乎乎所所有有的的最最优优化化问问题题，而而且且Lingo内内含含一一种种建建模模语语言言，可可方方便便地地描描述述较较大大规规模模的的最最优优1/12/20235化问题。化问题。本本讲讲内内容容包包括括：(1)线线性性规规划划、整整数数规规划划、非非线线性性规规划划及及Lingo解解法法；(2)Lingo建建模模语语言言；(3)用用Lingo求求解解运运输输问问题题、指指派派问问题题、典典型型图图论论模模型型(最最短短路路、最最大大流流、最最小小费费用用最最大大流流、最最小小生生成成树树);(4)数数学学规规划划综综合合建模实例。建模实例。1/12/20236 下面给出本讲学习大纲，以方便下面给出本讲学习大纲，以方便大家学习。大家学习。1.能能熟熟练练建建立立并并用用Lingo求求解解线线性性规规划、整数规划、非线性规划。划、整数规划、非线性规划。2.理理解解、掌掌握握Lingo中中集集的的概概念念与与用用法。法。3.熟熟悉悉Lingo典典型型程程序序的的结结构构，特特别别是目标函数与约束部分。是目标函数与约束部分。1/12/202374.能能将将较较为为复复杂杂的的数数学学规规划划转转化化为为典典型的型的Lingo程序。程序。5.熟熟悉悉、掌掌握握Lingo中中的的常常用用算算符符和和函数。函数。6.能能应应用用Lingo求求解解运运输输、指指派派、最最短路、最大流、最小生成树等问题。短路、最大流、最小生成树等问题。1/12/20238二、数学规划及二、数学规划及二、数学规划及二、数学规划及LingoLingo求解求解求解求解1.线性规划线性规划 引引例例 某某工工厂厂生生产产的的机机床床每每台台需需要要2.9m,2.1m,1.5m的的轴轴各各一一根根。这这些些轴轴用用同同一一种种圆圆钢钢制制作作，圆圆钢钢的的长长度度为为7.4m。如如果果要要生生产产100台台机机床床,应应如何下料，才能使得用料最省？如何下料，才能使得用料最省？分分析析 将将7.4m的的圆圆钢钢截截成成三三种种轴轴,可以有如下几种下料方式：可以有如下几种下料方式：1/12/202310方式方式长度长度B1B2B3B4B5B6B7B8需求需求2.9211100001002.1021032101001.510130234100余料余料0.10.30.901.10.20.81.41/12/202311 设设用用B1,B8方方式式下下料料的的圆圆钢钢的的根根数数分分别别为为x1,x8，则则可可建建立立数数学学模型如下：模型如下：1/12/202312 这类优化问题称为数学规划。这类优化问题称为数学规划。xi称称为为决决策策变变量量，S称称为为目目标标函函数，数，s.t后的式子称为约束条件。后的式子称为约束条件。由由于于本本问问题题中中的的目目标标函函数数和和约约束束条件均为线性，故称为线性规划。条件均为线性，故称为线性规划。线线性性规规划划是是运运筹筹学学的的重重要要分分支支，许许多多问问题题都都可可以以归归结结为为线线性性规规划划。如如下料问题、资源配置问题、运输问题下料问题、资源配置问题、运输问题1/12/202313和指派问题等。和指派问题等。例例1 某某3种种产产品品需需要要原原材材料料和和劳劳动动力力两两种种资资源源。每每件件产产品品所所需需资资源源、现现有有资资源源及及产产品品价价格格如如下下表表。试试确确定定3种产品的日产量以使总产值最大。种产品的日产量以使总产值最大。产品产品资源资源123现有资源现有资源原材料原材料436120劳动力劳动力245100价格价格4531/12/202314 解解(资资源源配配置置问问题题)设设3种种产产品品的的日日产产量量分分别别为为x1,x2,x3，则则线线性性规规划划模型为：模型为：1/12/202315 例例2 砖砖厂厂A1,A2产产量量分分别别为为23万万和和27万万。它它们们产产生生的的砖砖供供应应B1,B2,B3三三个个工工地地，需需求求量量分分别别为为17万万,18万万,15万万。砖砖厂厂到到工工地地的的运运价价如如下下表表。应如何调运，才能使总运费最省？应如何调运，才能使总运费最省？平衡表平衡表运价表运价表B1B2B3供应量供应量B1B2B3A123506070A2276011060需求需求171815501/12/202316 解解(运运输输问问题题)设设砖砖厂厂Ai供供应应工工地地Bj的数量为的数量为xij，则线性规划模型为：，则线性规划模型为：1/12/202317 运运输输问问题题除除了了用用线线性性规规划划求求解解外外，还还可可用用专专门门方方法法 表表上上作作业业法法或或 Lingo编程语言求解。编程语言求解。本本例例为为供供求求平平衡衡运运输输问问题题。若若供供求求不不平平衡衡，可可通通过过虚虚拟拟生生产产商商或或销销售售地地的的方方法法将将其其转转化化为为供供求求平平衡衡运运输输问问题。题。1/12/202318 例例3 设设有有n件件工工作作B1,Bn指指派派给给n个个人人A1,An去去做做，每每人人只只做做一一件件工工作作,每每件件工工作作只只指指派派给给一一个个人人做做。设设Ai完完成成Bj的的工工时时为为cij，如如下下表表所所示示。问问如如何何指指派派，才才能能使使完完成成全全部部工工作作所所需的总工时最少？需的总工时最少？1/12/202319工作工作人员人员B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnn1/12/202320 解解(指派问题指派问题)设设则线性规划模型为：则线性规划模型为：1/12/202321 1/12/202322 指指派派问问题题除除了了用用线线性性规规划划求求解解外外，还可用专门方法还可用专门方法 匈牙利法求解。匈牙利法求解。若若决决策策变变量量为为整整数数，则则称称此此线线性性规规划划为为整整数数规规划划。特特别别地地,当当决决策策变变量只取量只取0或或1时，称之为时，称之为0-1规划。规划。显显然然，指指派派问问题题为为典典型型的的0-1规规划。划。1/12/2023232.线性规划的线性规划的Lingo求解求解 Lindo是是Chicago大大学学的的Schrage教教授授于于1980年年前前后后开开发发的的专专门门用用于于求求解解数数学学规规划划的的软软件件包包,版版权权现现归归属属美美国国Lindo系系统统公公司司。Lindo软软件件包包中中包包含含Lindo,Gino,Lingo,Lingo NL和和“Whats Best”等等，统统称称为为Lindo，其中以其中以Lindo和和Lingo最为常用。最为常用。1/12/202324 因因Lindo的功能已全部被的功能已全部被Lingo所所覆盖，覆盖，Lindo已逐渐淡出市场。已逐渐淡出市场。Lingo除了可以求解线性规划、除了可以求解线性规划、整数规划和二次规划外，还可以求解整数规划和二次规划外，还可以求解非线性规划和线性、非线性方程组。非线性规划和线性、非线性方程组。此外，它还内置的建模语言和一些常此外，它还内置的建模语言和一些常用的数学函数，可以简便、直观地描用的数学函数，可以简便、直观地描述大规模优化问题。述大规模优化问题。1/12/202325 Lingo有有多多种种版版本本，如如学学生生版版、演演示示版版、高高级级版版、发发行行版版、工工业业版版等等，主主要要区区别别在在于于对对优优化化规规模模(变变量量和和约约束个数束个数)有不同的限制。有不同的限制。下下面面简简要要介介绍绍如如何何用用Lingo求求解解线性规划、整数规划和非线性规划。线性规划、整数规划和非线性规划。引例的引例的Lingo程序如下：程序如下：1/12/202326 model:(可省略可省略)min=x1+x2+x3+x4+x5+x6+x7+x8;2*x1+x2+x3+x4100;2*x2+x3+3*x5+2*x6+x7100;x1+x3+3*x4+2*x6+3*x7+4*x8100;end(可省略可省略)然后点击工具条上的按钮然后点击工具条上的按钮 即可。即可。1/12/202327 (1)Lingo已已假假设设所所有有变变量量均均非非负负，非非负负约约束束不不必必再再写写入入程程序序。必必要要时时可可用用变变量量界界定定函函数数free(x)解解除除变量变量x的非负假设；的非负假设；(2)约约束束条条件件中中的的和和可可用用 和和代替。代替。例例1和例和例2的的Lingo程序分别为：程序分别为：1/12/202328 max=4*x1+5*x2+3*x3;4*x1+3*x2+6*x3120;2*x1+4*x2+5*x3100;min=50*x11+60*x12+70*x13+60*x21+110*x22+60*x23;x11+x12+x13=23;x21+x22+x23=27;x11+x21=18;x12+x22=17;x13+x23=15;1/12/202329 例例4 求解整数规划：求解整数规划：Lingo程序如下：程序如下：1/12/202330 max=2*x+3*y;4*x+3*y10;3*x+5*y0;bnd(0,x,5000);程序中的程序中的bnd为界定函数。为界定函数。1/12/202333三、三、三、三、LingoLingo中的集与建模语言中的集与建模语言中的集与建模语言中的集与建模语言 前前面面例例子子中中的的目目标标函函数数和和约约束束都都可可直直接接列列出出。但但在在许许多多大大型型模模型型中中，可可能能需需要要表表达达一一组组相相似似的的计计算算和和约约束束。若若再再使使用用直直接接列列出出的的方方法法，就就要要重重复复键入许多相似的计算和约束。键入许多相似的计算和约束。Lingo允允许许把把这这些些相相联联系系的的对对象象定定义义成成集集。借借助助集集，能能够够用用一一个个简简明明的复合公式表示一系列相似的约束，的复合公式表示一系列相似的约束，1/12/202335从而可以快速方便地表达规模较大的从而可以快速方便地表达规模较大的模型。集是模型。集是LINGO建模语言的基础建模语言的基础,是程序设计最强有力的基本构件。是程序设计最强有力的基本构件。下面介绍集的相关知识。只有掌下面介绍集的相关知识。只有掌握这些内容后，才能真正熟练掌握利握这些内容后，才能真正熟练掌握利用用Lingo描述数学模型的基本方法。描述数学模型的基本方法。1/12/2023361.集的基本概念集的基本概念 集集其其实实就就是是一一群群相相关关对对象象组组成成的的集集合合，这这些些对对象象称称为为集集的的成成员员。每每个个成成员员可可能能有有一一个个或或多多个个相相关关联联的的特特征征，称称之之为为属属性性。属属性性值值可可以以预预先先给给定定，也可以未知，有待也可以未知，有待Lingo求解。求解。集的概念比较抽象、难懂。下面集的概念比较抽象、难懂。下面通过一个例子加以说明。通过一个例子加以说明。1/12/202337 例例6 某某船船厂厂需需要要决决定定下下4个个季季度度的的产产量量。4个个季季度度的的需需求求量量分分别别是是40,60,72,25。每每季季度度正正常常生生产产能能力力是是40,每每船船的的生生产产费费用用为为400美美元元。若若加加班班，每每船船的的生生产产费费用用为为450美美元元。每每季季度度末末,每每船船的的库库存存费费用用为为20美美元元。假假定定生生产产提提前前期期为为0，初初始始库库存存为为10,问问如如何安排生产可使总费用最小？何安排生产可使总费用最小？1/12/202338 用用DEM,RP,OP,INV分分别别表表示示需需求求量量、正正常常产产量量、加加班班产产量量、库库存存量量，则则它它们们每每个个季季度度都都有有一一个个对对应应值值，即即它它们们均均为为四四个个元元素素构构成成的的数数组组。其其中中，DEM已已知知，其其余余未未知知。易易见见，问问题题的数学模型为：的数学模型为：1/12/202339 上上述述问问题题的的程程序序本本不不复复杂杂，但但遗遗憾憾的的是是Lingo没没有有数数组组的的概概念念,所所以以上上述模型的述模型的Lingo程序较为繁琐。程序较为繁琐。1/12/202340 考考虑虑到到DEM,RP,OP,INV均均与与季季度度有有关关，引引入入4个个季季度度组组成成的的集集合合QUARTERS=1,2,3,4,DEM,RP,OP,INV对对此此集集合合的的每每个个元元素素1,2,3,4分分别别对应一个值，见后图。对应一个值，见后图。QUARTERS=1,2,3,4称称为为集集合合,DEM,RP,OP,INV称称为为该该集集合合的的属属性。性。1/12/202341 其其实实，集集合合的的属属性性可可理理解解为为“数数组组”，而而集集合合中中的的元元素素即即为为数数组组的的“下标下标”。1/12/202342 Lingo有有两两种种集集：原原始始集集和和派派生生集。集。原始集由最基本的对象组成。原始集由最基本的对象组成。派派生生集集是是从从其其它它集集派派生生得得来来的的，它它可可以以是是另另一一个个集集的的子子集集，也也可可以以由由其其它它几几个个集集中中的的元元素素组组成成。也也就就是是说说，它的成员来自于其它已存在的集。它的成员来自于其它已存在的集。1/12/202343 原原始始集集的的定定义义包包括括：集集的的名名字字；集集的的成成员员(可可选选)；集集成成员员的的属属性性(可可选选)。定义原始集的语法为：定义原始集的语法为：setname/member_list/:attribute_list;“”表示该部分内容可选。表示该部分内容可选。setname是是集集的的名名字字,最最好好具具有有较较1/12/202344强强的的可可读读性性。集集名名字字、集集成成员员名名以以及及集属性名符合一般命名规则。集属性名符合一般命名规则。例如，例例如，例5中的集合可用中的集合可用 QUARTERS/1,2,3,4/:DEM,RP,OP,INV;来定义。来定义。1/12/202345 有有时时需需要要将将两两个个及及两两个个以以上上的的集集合组成一个新集合，称之为派生集。合组成一个新集合，称之为派生集。派派生生集集的的定定义义包包括括：集集的的名名字字；父父集集的的名名字字；集集成成员员(可可选选)；集集成成员员的属性的属性(可选可选)。定义派生集的语法为：定义派生集的语法为：setname(parent_set_list)/member_list/:attribute_list;1/12/202346 setname是是集集的的名名字字，parent_set _list是是已已定定义义的的集集的的列列表表，多多个个时时必必须须用用逗逗号号隔隔开开。如如果果没没有有指指定定成成员员列列表表，那那么么Lingo会会自自动动创创建建父父集集成成员员的的所所有有组组合合作作为为派派生生集集的的成成员员。派派生生集集的的父父集集既既可可以以是是原原始始集集，也也可可以以是其它的派生集。是其它的派生集。派生集的实例见例派生集的实例见例7。1/12/2023472.Lingo的程序结构的程序结构 一一个个典典型型的的Lingo程程序序由由model:开开头头，以以end结结尾尾，程程序序由由集集、目目标标函函数数与与约约束束、数数据据和和初初始始化化四四部部分分组组成成。其其中中只只有有目目标标函函数数与与约约束束部部分分是是必须的，其余三个部分为可选部分。必须的，其余三个部分为可选部分。在使用集之前，必须在集部分事在使用集之前，必须在集部分事先定义。集部分以关键字先定义。集部分以关键字sets:开始，开始，1/12/202348以以endsets结结束束。一一个个模模型型可可以以没没有有集集部部分分、有有一一个个集集部部分分或或有有多多个个集集部部分分。一一个个集集部部分分可可以以放放置置于于模模型型的的任任何何地地方方，但但是是一一个个集集及及其其属属性性在在模模型型约束中被引用之前必须先定义。约束中被引用之前必须先定义。数数据据部部分分的的作作用用是是为为决决策策变变量量设设置置初初始始值值，以以data:开开始始，以以enddata结束。结束。1/12/202349 初初始始部部分分为为部部分分参参数数指指定定初初始始值值,以以init:开始，以开始，以endinit结束。结束。目目标标函函数数与与约约束束部部分分是是Lingo程程序序的的核核心心部部分分，通通常常以以MIN或或MAX开头但没有明显的结束标记。开头但没有明显的结束标记。目目标标函函数数与与约约束束部部分分一一般般要要用用到到Lingo的的一一些些内内部部函函数数，如如FOR,SUM等。等。1/12/202350 这这部部分分是是初初学学者者感感到到困困难难、不不易易掌握的内容。掌握的内容。下面给出两个典型下面给出两个典型Lingo程序。程序。例例6的的Lingo程序程序MODEL:SETS:QUARTERS/1,2,3,4/:DEM,RP,OP,INV;ENDSETS MIN=SUM(QUARTERS:400*RP+450*OP+20*INV);1/12/202351 FOR(QUARTERS(I):RP(I)40);FOR(QUARTERS(I)|I#GT#1:INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I););INV(1)=10+RP(1)+OP(1)-DEM(1);DATA:DEM=40,60,75,25;ENDDATAEND1/12/202352 例例7 建建筑筑工工地地的的位位置置(用用平平面面坐坐标标a,b表表示示，单单位位km)及及水水泥泥用用量量d(单单位位t)由由下下表表给给出出。目目前前有有两两个个临临时时料料场场位位于于P(5,1),Q(2,7)，日日储储量量各各有有20t。求求从从A,B两两料料场场分分别别向向各各工工地地运运送送多多少少吨吨水水泥泥，使使总总的的吨吨公公里里数数最最小小？两两个个新新的的料料场场应应建建在在何何处处，节节省的吨公里有多少？省的吨公里有多少？1/12/202353 记记工工地地位位置置为为(ai,bi)，水水泥泥日日用用量量为为di，料料场场位位置置为为(xj,yj)，日日储储量量为为ej，从从料料场场j向向工工地地i的的运运送送量量为为cij，则数学模型为则数学模型为1/12/202354 当当使使用用现现有有料料场场时时，决决策策变变量量只只有有cij，属属线线性性规规划划；当当为为新新料料场场选选址址时时，决决策策变变量量为为cij和和xj,yj，属属非非线线性性规划。规划。1/12/202355 下面给出下面给出Lingo程序。程序。在在求求解解非非线线性性规规划划时时，为为了了尽尽可可能能求求得得全全局局最最优优解解，可可考考虑虑开开启启全全局局优优化化器器。但但可可能能需需耗耗费费很很长长时时间间，且且不能保证一定求得全局最优解。不能保证一定求得全局最优解。注注 试试用用版版不不一一定定可可用用全全局局优优化化器。器。1/12/202356使用现有料场时的线性规划使用现有料场时的线性规划MODEL:sets:demand/1.6/:a,b,d;supply/1.2/:x,y,e;link(demand,supply):c;endsetsdata:a=1.25,8.75,0.5,5.75,3,7.25;b=1.25,0.75,4.75,5,6.5,7.75;1/12/202357d=3,5,4,7,6,11;e=20,20;x,y=5,1,2,7;enddatamin=sum(link(i,j):c(i,j)*(x(j)-a(i)2+(y(j)-b(i)2)(1/2);for(demand(i):sum(supply(j):c(i,j)=d(i););for(supply(j):sum(demand(i):c(i,j)e(j););END1/12/202358 现对上述程序说明如下：现对上述程序说明如下：(1)link为为由由demand和和supply生生成的派生集，说明见后；成的派生集，说明见后；(2)料场位置料场位置x,y视为固定数据；视为固定数据；(3)x,y=5,1,2,7相相 当当 于于 x=5,2;y=1,7;,即即Lingo为按列赋值。为按列赋值。1/12/202359料场待定时的非线性规划料场待定时的非线性规划MODEL:sets:demand/1.6/:a,b,d;supply/1.2/:x,y,e;link(demand,supply):c;endsetsdata:a=1.25,8.75,0.5,5.75,3,7.25;b=1.25,0.75,4.75,5,6.5,7.75;1/12/202360d=3,5,4,7,6,11;e=20,20;enddatainit:x,y=5,1,2,7;endinitmin=sum(link(i,j):c(i,j)*(x(j)-a(i)2+(y(j)-b(i)2)(1/2);for(demand(i):sum(supply(j):c(i,j)=d(i););for(supply(j):sum(demand(i):c(i,j)e(j););1/12/202361for(supply:free(x);free(y););END (1)本本程程序序中中的的料料场场位位置置x,y为为初初始始数数据据，即即x,y与与其其它它变变量量一一样样可可以以被被优化；优化；此时，初始化段并无实际意义。此时，初始化段并无实际意义。(2)free(x)的的作作用用为为去去除除x的的非非负限制。负限制。1/12/202362 在在程程序序中中,由由于于运运送送量量cij和和需需求求量量di及及供供应应量量ej均均有有关关，即即cij相相当当于于二二维维数数组组，故故根根据据需需求求集集合合demand 和和供供应应集集合合 supply定定义义了了一一个个新新集集合合link，定义语句为：，定义语句为：link(demand,supply):c;link其其实实就就是是demand和和supply中中的所有元素组成的二元集合，即的所有元素组成的二元集合，即1/12/202363亦即亦即link是是demand和和supply的派生集。的派生集。1/12/202364四、四、四、四、LingoLingo的运算符与函数的运算符与函数的运算符与函数的运算符与函数 Lingo有有8种类型的函数：种类型的函数：1.基基本本运运算算符符:算算术术运运算算符符、逻逻辑运算符和关系运算符；辑运算符和关系运算符；2.数学函数数学函数;3.金融函数金融函数:；4.概率函数概率函数:概率和统计函数；概率和统计函数；5.变变量量界界定定函函数数：这这类类函函数数用用来来定义变量的取值范围；定义变量的取值范围；1/12/202366 6.集集操操作作、循循环环函函数数：这这类类函函数数对集的元素进行特定的操作；对集的元素进行特定的操作；7.数数据据输输入入输输出出函函数数：这这类类函函数数可以进行数据的输入输出；可以进行数据的输入输出；8.辅辅助助函函数数：各各种种Lingo特特有有的的函数。函数。1/12/2023671.基本运算符基本运算符 基基本本运运算算符符在在Lingo中中是是非非常常基基本，非常重要的。本，非常重要的。(1)算术运算符算术运算符 Lingo提供了提供了5种二元运算符：种二元运算符：乘方乘方;乘乘;除除;加加;减。减。Lingo唯唯一一的的一一元元算算术术运运算算符符是是取反函数取反函数“”。1/12/202368 这些运算符的优先级为：这些运算符的优先级为：高高（取反）（取反）低低 运算符的运算次序为从左到右按运算符的运算次序为从左到右按优先级高低来执行。运算的次序可以优先级高低来执行。运算的次序可以用圆括号用圆括号()()来改变来改变。1/12/202369(2)逻辑逻辑运算符运算符 在在 Lingo 中，中，逻辑逻辑运算符主要用运算符主要用于判断某一于判断某一变变量是否属于一个集合。量是否属于一个集合。如如对对某个集合元素求和某个集合元素求和时时就需要判断就需要判断某个元素是否属于某个元素是否属于该该集合。集合。Lingo具有下列具有下列9种种逻辑逻辑运算符：运算符：#not#否定否定该该操作数的操作数的逻辑值逻辑值，not是一个一元运算符；是一个一元运算符；1/12/202370#eq#若若两两边边相相等等，则则为为true，否则为否则为false；#ne#若若两两边边不不相相等等，则则为为true,否则为否则为false；#gt#若若左左边边严严格格大大于于右右边边，则则为为true,否则为否则为false;#ge#若若左左边边大大于于或或等等于于右右边边，则为则为true，否则为，否则为false；1/12/202371#lt#若若左左边边严严格格小小于于右右边边，则则为为true，否则为，否则为false；#le#若若左左边边小小于于或或等等于于右右边边，则为则为true，否则为，否则为false；#and#当当两两个个参参数数都都为为true时时，结果为结果为true，否则为，否则为false；#or#当当两两个个参参数数都都为为 false 时时，结果为结果为false，否则为，否则为true。1/12/202372 这些运算符的优先级为：这些运算符的优先级为：高高#not#eq#ne#gt#ge#lt#le#低低#and#or#(3)关系运算符关系运算符 在在Lingo中中，关关系系运运算算符符主主要要是是被被用用来来指指出出一一个个表表达达式式的的左左边边是是否否等等于、小于等于、或者大于等于右边，于、小于等于、或者大于等于右边，1/12/202373形形成成模模型型的的一一个个约约束束条条件件。关关系系运运算算符符与与逻逻辑辑运运算算符符#eq#、#le#、#ge#具具有有本本质质的的区区别别，前前者者是是模模型型中中该该关关系系运运算算符符所所指指定定关关系系的的为为真真描描述述，而而后后者者仅仅仅仅判判断断一一个个该该关关系系是是否否被被满满足足：满足为真，不满足为假。满足为真，不满足为假。Lingo有三种关系运算符：有三种关系运算符：“=”,“=”。1/12/202374 Lingo不不支支持持严严格格小小于于和和严严格格大大于于关关 系系 运运 算算 符符，Lingo默默 认认 “”即即表表示示“=”。如如果果需需要要严严格格小小于于和和严严格格大大于于关关系系，比比如如AB，可可以以把把它它变变成成小小于于等等于于表表达达式式:A+=B,这这里里是是一一个个小小的的正正数数，它它的的值值依依赖赖于于模模型型中中A小小于于B多多少少才才算算不不等。等。1/12/202375 上述三类操作符的优先级为：上述三类操作符的优先级为：高高#not#（取反）（取反）#eq#ne#gt#ge#lt#le#and#or#低低 =。1/12/2023762.数学函数数学函数 Lingo提提供供了了两两类类数数学学函函数数：一一般函数和三角函数。般函数和三角函数。abs(x)x的绝对值；的绝对值；sin(x)x的正弦值的正弦值;cos(x)x的余弦值；的余弦值；tan(x)x的正切值；的正切值；exp(x)常数常数e的的x次方；次方；1/12/202377 log(x)x的自然对数；的自然对数；sign(x)符号函数；符号函数；floor(x)x的的整整数数部部分分。当当x=0时时，返返回回不不超超过过x的的最最大大整整数数；当当x0时，返回不低于时，返回不低于x的最大整数；的最大整数；smax(smin)(x1,x2,xn)x1,x2,xn中的最大中的最大(小小)值。值。1/12/2023783.集合循环函数与操作函数集合循环函数与操作函数 集集合合循循环环函函数数可可对对集集合合中中的的元元素素(下标下标)进行循环操作，其用法为：进行循环操作，其用法为：function(setname(set_index_list)|condition:expression_list)；其其中中，function是是集集合合函函数数名名，例例如如,FOR,MAX,MIN,PROD,SUM；setna me是是集集合合名名；set_ index_list 是是集集合合1/12/202379索索引引列列表表；condition是是过过滤滤条条件件；exp ression_list是表达式列表。是表达式列表。集集合合操操作作函函数数是是指指对对集集合合进进行行操操作作的的函函数数，主主要要有有IN,INDEX,WRAP,SIZE。在在集集合合循循环环和和集集合合操操作作函函数数中中，最最常常用用的的是是FOR和和SUM。请请各各位位务务必必要结合实例熟练掌握。要结合实例熟练掌握。1/12/2023804.其它函数其它函数 除除前前述述函函数数外外，Lingo中中还还有有变变量量界界定定函函数数：BND,BIN,FREE,GIN；输输入入输输出出函函数数：FILE,TEXT;金金融融函函数数、概概率率函函数数、结结果果报告函数等。报告函数等。1/12/202381五、五、五、五、LingoLingo应用实例应用实例应用实例应用实例 本本节节简简要要介介绍绍用用Lingo编编程程语语言言求求解解的的几几个个典典型型运运筹筹与与图图论论问问题题：运运输输问问题题、指指派派问问题题、最最短短路路问问题题、最最大大流流问问题题、最最小小费费用用最最大大流流问问题题。目目的的是是进进一一步步熟熟悉悉、掌掌握握：集集的的概概念念和和用用法法；Lingo的的程程序序结结构构；循循环环、求求和和等等语语句句和和函函数数的的用用法法；知知晓晓Lingo能解决的典型问题。能解决的典型问题。1/12/202383 例例8 设设3 个个产产地地和和4个个销销地地的的运运输输问问题题的的产产量量、销销量量及及单单位位运运费费如如下下表表，试求总运费最小的运输方案。试求总运费最小的运输方案。B1B2B3B4产量产量A1626730A2495325A3881521销量销量151722121/12/202384运输问题的运输问题的Lingo程序程序model:sets:Warehouse/1.3/:a;Customer /1.4/:b;Routes(Warehouse,Customer):c,x;endsetsdata:a=30,25,21;b=15,17,22,12;1/12/202385c=6,2,6,7,4,9,5,3,8,8,1,5;enddatamin=sum(Routes:c*x);for(Warehouse(i):sum(Customer(j):x(i,j)=1;for(cities(i)|i#gt#1:1/12/2023104sum(cities(j)|j#ne#i:x(j,i)=1;for(cities(j)|j#gt#1#and#j#ne#i:level(j)level(i)+x(i,j)-(n-2)*(1-x(i,j)+(n-3)*x(j,i););bnd(1,level(i),999999);level(i)n-1-(n-2)*x(1,i););for(link:bin(x);1/12/2023105 经经计计算算，最最小小生生成成树树(最最优优连连线线)如下图，最小距离为如下图，最小距离为60。1/12/2023106六、上机练习六、上机练习六、上机练习六、上机练习 1.有有两两个个煤煤厂厂A,B，每每月月分分别别进进煤煤不不少少于于60t,100t，它它们们担担负负供供应应三三个个居居民民区区用用煤煤任任务务，这这三三个个居居民民区区每每月月用用煤煤分分别别为为45t,75t,40t。A厂厂离离这这三三居居民民区区分分别别是是10km,5k m,6km，B厂厂离离三三居居民民区区分分别别是是4km,8km,15 km。问问这这两两煤煤厂厂如如何何分分配配供供煤煤，才才能能使使运运量最小？量最小？1/12/2023108 2.已已知知有有6个个人人(1,2,3,4,5,6)可可以以做做6项项工工作作(1,2,3,4,5,6)，每每个个人人做做每每项项工工作作的的效效率率如如下下表表，问问如如何何安安排每人的工作，使总工作效率最大？排每人的工作，使总工作效率最大？1/12/2023109 3.求下图中从求下图中从v1到到v11的最短路。的最短路。1/12/2023110 4.求下列网络的最大流：求下列网络的最大流：1/12/2023111 5.求求下下网网络络的的最最小小费费用用最最大大流流，括括号号中中第第1个个数数是是容容量量，第第2个个数数是是单单位费用。位费用。1/12/2023112 6.已已知知北北京京(B)、纽纽约约(N)、巴巴黎黎(P)、伦伦敦敦(L)、东东京京(T)、墨墨西西哥哥(M)距离如下表，求网络最小生成树。距离如下表，求网络最小生成树。1/12/2023113 考考虑虑到到上上述述36属属图图论论问问题题，建建议议采用采用Lingo和和Matlab两种方法计算。两种方法计算。1/12/2023114