lingo教程--有图.ppt

LINGO软件软件Hanguang XiaoChongqing University of Technology2024/5/21 周二周二1主要内容主要内容LINGO软件软件LINGO中建模语言（集合、运算符和函数等）中建模语言（集合、运算符和函数等）LINGO编程实例编程实例露天矿生产的车辆安排露天矿生产的车辆安排2LINGO软件软件（1）美国芝加哥(Chicago)大学的Linus Schrage（莱纳斯.施拉盖）教授于1980年前后开发。（2）LINGO:Linear Interactive General Optimizer(线性交互式通用优化器)。（3）用来求解的优化模型（连续优化和整数规划（IP）。类型：线性规划（LP）、二次规划(QP)、非线性规划(NLP)。3LINDO/LINGO软件能求解的模型软件能求解的模型优化优化线性规划线性规划非线性规划非线性规划二次规划二次规划连续优化连续优化整数规划整数规划 LINDOLINGO4学习学习LINGO需掌握的方面需掌握的方面LINGO:Linear Interactive General Optimizer (V12.0)求解数学规划问题 Min Z=f(x)s.t x D(Rn)需要掌握：软件操作基本语法结构掌握集合(SETS)的应用正确阅读求解报告正确理解求解状态窗口学会设置基本的求解选项(OPTIONS)5LINGO软件的主窗口（用软件的主窗口（用户界面），所有其他窗口户界面），所有其他窗口都在这个窗口之内都在这个窗口之内。模型窗口（模型窗口（Model Window），用于输入），用于输入LINGO优化模型（即优化模型（即LINGO程序）。程序）。状态行（最左边显状态行（最左边显示示“Ready”，表，表示示“准备就绪准备就绪”）当前时间当前时间 当前光标当前光标的位置的位置 LINGO软件界面软件界面6LINGO软件菜单软件菜单FILE1 1新建（新建（NewNew）单击“新建”按钮或直接按F2键可以创建一个新的“Model”窗口。在这个新的“Model”窗口中能够输入所要求解的模型。2 2 打开（打开（OpenOpen）单击“打开”按钮或直接按F3键可以打开一个已经存在的文本文件。这个文件可能是一个Model文件。3 3 保存保存(Save)(Save)单击“保存”按钮或直接按F4键用来保存当前活动窗口（最前台的窗口）中的模型结果、命令序列等保存为文件。4 4 另存另存为为(Save As(Save As)“另存为”命令或按F5键可以将当前活动窗口中的内容保存为文本文件，其文件名为你在“另存为”对话框中输入的文件名。利用这种方法你可以将任何窗口的内容如模型、求解结果或命令保存为文件。5 5 关关闭闭（CloseClose）在文件菜单中选用“关闭”(Close)命令或按F6键将关闭当前活动窗口。如果这个窗口是新建窗口或已经改变了当前文件的内容，LINGO系统将会提示是否想要保存改变后的内容6 6 打印打印(Print)(Print)“打印”(Print)命令、单击“打印”按钮或直接按F7键可以将当前活动窗口中的内容发送到打印机7 7 打印打印设设置置(Print Setup(Print Setup)“打印设置”命令或直接按F8键可以将文件输出到指定的打印机。8 8 打印打印预览预览(Print Preview)(Print Preview)“打印预览”命令或直接按Shift+F8键可以进行打印预览。9 9 输输出到日志文件出到日志文件(Log Output(Log Output)从文件菜单中选用“Log Output”命令或按F9键打开一个对话框，用于生成一个日志文件，它存储接下来在“命令窗口”中输入的所有命令。1010提交提交LINGOLINGO命令脚本文件命令脚本文件(Take Commands(Take Commands)“Take Commands”命令或直接按F11键就可以将LINGO命令脚本（command script）文件提交给系统进程来运行。1111引入引入LINGOLINGO文件文件(Import Lingo File(Import Lingo File)从文件菜单中选用“Import Lingo File”命令或直接按F12键可以打开一个LINGO格式模型的文件，然后LINGO系统会尽可能把模型转化为LINGO语法允许的程序。1212退出（退出（ExitExit）从文件菜单中选用“Exit”命令或直接按F10键可以退出LINGO系统。7LINGO软件菜单软件菜单EIDT1 恢复恢复(Undo)从编辑菜单中选用“恢复”（Undo）命令或按Ctrl+Z组合键，将撤销上次操作、恢复至其前的状态。2 剪切剪切(Cut)从编辑菜单中选用“剪切”（Cut）命令或按Ctrl+X组合键可以将当前选中的内容剪切至剪贴板中。3 复制复制(Copy)从编辑菜单中选用“复制”（Copy）命令、单击“复制”按钮或按Ctrl+C组合键可以将当前选中的内容复制到剪贴板中。4 粘贴粘贴(Paste)从编辑菜单中选用“粘贴”（Paste）命令、单击“粘贴”按钮或按Ctrl+V组合键可以将粘贴板中的当前内容复制到当前插入点的位置。5 粘贴特定粘贴特定.（Paste Special。）。）与上面的命令不同，它可以用于剪贴板中的内容不是文本的情形.6 全选全选(Select All)从编辑菜单中选用“Select All”命令或按Ctrl+A组合键可选定当前窗口中的所有内容。7 匹配小括号匹配小括号(Match Parenthesis)从编辑菜单中选用“Match Parenthesis”命令、单击“Match Parenthesis”按钮或按Ctrl+P组合键可以为当前选中的开括号查找匹配的闭括号。8 粘贴函数粘贴函数(Paste Function)从编辑菜单中选用“Paste Function”命令可以将LINGO的内部函数粘贴到当前插入点。8LINGO软件菜单软件菜单LINGO 1 求解模型（求解模型（Slove）从LINGO菜单中选用“求解”命令、单击“Slove”按钮或按Ctrl+S组合键可以将当前模型送入内存求解。2 求解结果（求解结果（Solution）从LINGO菜单中选用“Solution”命令、单击“Solution”按钮或直接按Ctrl+O组合键可以打开求解结果的对话框。这里可以指定查看当前内存中求解结果的那些内容。3灵敏性分析（灵敏性分析（Range，Ctrl+R）用该命令产生当前模型的灵敏性分析报告：研究当目标函数的费用系数和约束右端项在什么范围（此时假定其它系数不变）时，最优基保持不变。灵敏性分析是在求解模型时作出的，因此在求解模型时灵敏性分析是激活状态，但是默认是不激活的。为了激活灵敏性分析，运行LINGO|Options，选择General Solver Tab，在Dual Computations列表框中，选择Prices and Ranges选项。灵敏性分析耗费相当多的求解时间，因此当速度很关键时，就没有必要激活它。4选项（选项（Options）从LINGO菜单中选用“Options”命令、单击“Options”按钮或直接按Ctrl+I组合键可以改变一些影响LINGO模型求解时的参数。该命令将打开一个含有7个选项卡的窗口，你可以通过它修改LINGO系统的各种参数和选项。5 模型通常形式（模型通常形式（Generate）从LINGO菜单中选用“Generate”命令或直接按Ctrl+G组合键可以创建当前模型的代数形式、LINGO模型或MPS格式文本。6.图片（图片（Picture）7.调试（调试（Debug）8.模型统计（模型统计（Model Statistics）6查看（查看（Look）从LINGO菜单中选用“Look”命令或直接按Ctrl+L组合键可以查看全部的或选中的模型文本内容。9LINGO软件菜单软件菜单WINDOW1 命令行窗口（命令行窗口（Open Command Window）从窗口菜单中选用“Open Command Window”命令或直接按Ctrl+1可以打开LINGO的命令行窗口。在命令行窗口中可以获得命令行界面，在“:”提示符后可以输入LINGO的命令行命令。2 状态窗口（状态窗口（Status Window）从窗口菜单中选用“Status Window”命令或直接按Ctrl+2可以打开LINGO的求解状态窗口。3.回到模型窗口（回到模型窗口（Sent To Back）Ctrl+B4.关闭所有窗口（关闭所有窗口（Close All）Ctrl+35.并行放置窗口并行放置窗口(Tile)Ctrl+46.层叠放置窗口（层叠放置窗口（Cascade）Ctrl+57.放置图标放置图标(Arrange Icons)Ctrl+610LINGO软件菜单软件菜单HELP1 帮助主题（帮助主题（Help Menu）从帮助菜单中选用“Help Menu”可以打开LINGO的帮助文件。2.注册信息（注册信息（Register）填写注册信息。2.自动更新（自动更新（AutoUptate）自动升级。2 关于关于LINGO(About Lingo)关于当前LINGO的版本信息等。11打开文件：F3打印文件：F7复制：Ctrl+C取消操作：Ctrl+Z查找：Ctrl+F显示解答:Alt+O匹 配 括 号:Ctrl+P选 项 设 置:Ctrl+I关闭所有窗口:Alt+X在线帮助:F1新建文件：F2保存文件：F4剪切：Ctrl+X粘贴：Ctrl+V恢 复 操 作：Ctrl+Y定位某行：ctrl+T求解模型:Ctrl+S模型图示:Ctrl+K窗口后置:Ctrl+B 平铺窗口:Alt+T上下文相关的帮助LINGO软件工具栏软件工具栏12“LG4LG4”表示表示LINGO LINGO 格式的格式的模型文件，是一种特殊的二模型文件，是一种特殊的二进制格式文件，保存了我们进制格式文件，保存了我们在模型窗口中所能够看到的在模型窗口中所能够看到的所有文本和其他对象及其格所有文本和其他对象及其格式信息，只有式信息，只有LINGO LINGO 能读能读出它，用其他系统打开这种出它，用其他系统打开这种文件时会出现乱码文件时会出现乱码 “LNGLNG”表示表示LINGOLINGO文本文文本文件，以这个格式保存模型时件，以这个格式保存模型时系统系统 将给出警告，因为模将给出警告，因为模型中的格式信息（如字体、型中的格式信息（如字体、颜色等）将会丢失颜色等）将会丢失 “LDTLDT”表示数据文件表示数据文件“LTFLTF”表示表示 命令脚本文件命令脚本文件 “LGRLGR”表示表示 报告文件报告文件 除除“LG4LG4”文件外，这里的另外文件外，这里的另外几种格式的文件其实都是普通几种格式的文件其实都是普通的文本文件，可以用任何文本的文本文件，可以用任何文本编辑器打开和编辑编辑器打开和编辑 LINGO软件文件保存类型软件文件保存类型13Variables（变量数量）：（变量数量）：变量总数（变量总数（Total）、）、非线性变量数（非线性变量数（Nonlinear）、）、整数变量数（整数变量数（Integer）。）。Constraints（约束数量）：（约束数量）：约束总数（约束总数（Total）、）、非线性约束个数非线性约束个数(Nonlinear)。Nonzeros（非零系数数量）：（非零系数数量）：总数（总数（Total）、）、非线性项系数个数非线性项系数个数(Nonlinear)。Generator Memory Used(K)(内存使内存使用量用量)Elapsed Runtime(hh:mm:ss)（求解花费的时间）（求解花费的时间）LINGO软件运行状态窗口的参数解释软件运行状态窗口的参数解释14LINGO软件运行状态窗口的参数解释软件运行状态窗口的参数解释求解求解器器(求求解程解程序序)状状态框态框当前模型的类型当前模型的类型:LP，QP，ILP，IQP，PILP，PIQP，NLP，INLP，PINLP（以（以I开头表示开头表示IP，以，以PI开头表示开头表示PIP）当前解的状态当前解的状态:Global Optimum,Local Optimum,Feasible,Infeasible“(不可行不可行),Unbounded“(无界无界),Interrupted“(中断中断),Undetermined“(未确定未确定)解的目标函数值解的目标函数值 当前约束不满足的总量当前约束不满足的总量(不是不不是不满足的约束的个数满足的约束的个数):实数（即使实数（即使该值该值=0，当前解也可能不可行，当前解也可能不可行，因为这个量中没有考虑用上下界因为这个量中没有考虑用上下界命令形式给出的约束）命令形式给出的约束）目前为止的目前为止的迭代次数迭代次数 15运行状态窗口运行状态窗口扩展扩展的求的求解器解器(求解求解程序程序)状态状态框框使用的特殊求解程序使用的特殊求解程序:B-and-B(分枝定界算法分枝定界算法)Global(全局最优求解程序全局最优求解程序)Multistart(用多个初始点求解的程序用多个初始点求解的程序)目前为止找到的可行目前为止找到的可行解的最佳目标函数值解的最佳目标函数值 目标函数值的界目标函数值的界 特殊求解程序当前运行步数：特殊求解程序当前运行步数：分枝数分枝数(对对B-and-B程序程序)；子问题数子问题数(对对Global程序程序)；初始点数初始点数(对对Multistart程序程序)有效步数有效步数 16主要内容主要内容LINGO软件简介软件简介LINGO建模语言（集合、运算符和函数等）建模语言（集合、运算符和函数等）LINGO编程实例编程实例露天矿生产的车辆安排露天矿生产的车辆安排17一个简单的一个简单的LINGO程序程序例 直接用LINGO来解如下二次规划问题：输入窗口如下：输入窗口如下：目标函数目标函数约束条件约束条件 变量取整变量取整 每个语句每个语句以以“；”结束结束顺序无关顺序无关程序程序:eg1.lg4 18输出结果：输出结果：运行菜单命令运行菜单命令“LINGO|Solve”最优整数解最优整数解X=(35，65)最大利润最大利润=11077.5 一个简单的一个简单的LINGO程序程序19例例1 SAILCO公司需要决定下四个季度的帆船生产量。公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是下四个季度的帆船需求量分别是40条，条，60条，条，75条，条，25条，这些需求必须按时满足。每个季度正常的生产条，这些需求必须按时满足。每个季度正常的生产能力是能力是40条帆船，每条船的生产费用为条帆船，每条船的生产费用为400美元。如果美元。如果加班生产，每条船的生产费用为加班生产，每条船的生产费用为450美元。每个季度末，美元。每个季度末，每条船的库存费用为每条船的库存费用为20美元。假定生产提前期为美元。假定生产提前期为0，初，初始库存为始库存为10条船。如何安排生产可使总费用最小？条船。如何安排生产可使总费用最小？20集合及其属性集合及其属性QUARTERS集合的属性DEM RPOP INVQUARTERS集合2341quarters/1,2,3,4/:dem,rp,op,inv;21LINGO中定义集合及其属性中定义集合及其属性以以“MODEL：”开始开始 以以“END”结束结束集合定义部分从集合定义部分从(“SETS：”到到“ENDSETS”)：定：定义集合及其属性义集合及其属性数据输入部分从数据输入部分从(“DATA：”到到“ENDDATA”)给出优化目标给出优化目标和约束和约束 程序程序:eg2.lg4 22目标函数的定义方式对语句中冒号对语句中冒号“：”后面的表达式，按照后面的表达式，按照“：”前前面的集合指定的下标（元素）进行求和。面的集合指定的下标（元素）进行求和。本例中目标函数也可以等价地写成本例中目标函数也可以等价地写成SUM(QUARTERS(i):400*RP(i)+450*OP(i)+20*INV(i)“SUM”相当于求和符号相当于求和符号“”，由于本例中目标函数对集合由于本例中目标函数对集合QUARTERS的所有元素的所有元素(下下标标)都要求和，所以可以将下标都要求和，所以可以将下标i省去。省去。SUM(集合（下标）：关于集合的属性的表达式集合（下标）：关于集合的属性的表达式)23约束条件的定义方式约束条件的定义方式循环函数循环函数FOR(集合集合(下标下标)：关于集合的属性的约束关系式：关于集合的属性的约束关系式)对冒号对冒号“：”前面的集合的每个元素（下标），冒号前面的集合的每个元素（下标），冒号“：”后面的约束关系式都要成立后面的约束关系式都要成立 本例中，每个季度正常的生产能力是本例中，每个季度正常的生产能力是40条帆船，这条帆船，这正是语句正是语句“FOR(QUARTERS(I):RP(I)=40);”的含的含义。义。这个语句可以简化成这个语句可以简化成“FOR(QUARTERS:RP40);”。24问题求解：运行菜单命令“LINGO|SOLVE”全局最优解全局最优解RP=(40,40,40,25),OP=(0,10,35,0)最小成本最小成本=78450 25LINGO模型最基本的组成要素模型最基本的组成要素（1）集合段（集合段（SETS）：以：以“SETS:”开始，开始，“ENDSETS”结束，定义必要的集合变量（结束，定义必要的集合变量（SET）及）及其元素（其元素（MEMBER，含义类似于数组的下标）和属，含义类似于数组的下标）和属性（性（ATTRIBUTE，含义类似于数组）。，含义类似于数组）。（2）目标与约束段目标与约束段：目标函数、约束条件等，没有：目标函数、约束条件等，没有段的开始和结束标记，因此实际上就是除其它四个段段的开始和结束标记，因此实际上就是除其它四个段(都有明确的段标记都有明确的段标记)外的外的LINGO模型。模型。这里一般要用到这里一般要用到LINGO的内部函数，尤其是与集合的内部函数，尤其是与集合相关的求和函数相关的求和函数SUM和循环函数和循环函数FOR等。等。26LINGO模型最基本的组成要素模型最基本的组成要素（3）数据段数据段(DATA)：以：以“DATA:”开始开始,“ENDDATA”结束，对集合的属性结束，对集合的属性(数组数组)输入必要的常输入必要的常数数据。数数据。格式为：格式为：“attribute(属性属性)=value_list(常数列表常数列表);”常数列表常数列表(value_list)中数据之间可以用逗号中数据之间可以用逗号“,”分开，分开，也可以用空格分开也可以用空格分开(回车等价于一个空格回车等价于一个空格),如上面对如上面对DEM的赋值也可以写成的赋值也可以写成“DEM=40 60 75 25；”。27LINGO模型最基本的组成要素模型最基本的组成要素（4）初始段初始段(INIT)：以：以“INIT:”开始，开始，“ENDINIT”结束，对集合的属性结束，对集合的属性(数组数组)定义初值定义初值(因因为求解算法一般是迭代算法，所以为求解算法一般是迭代算法，所以，如果能给出一个如果能给出一个比较好的迭代初值，对提高算法的计算效果是有益的比较好的迭代初值，对提高算法的计算效果是有益的)。如果有一个接近最优解的初值，对如果有一个接近最优解的初值，对LINGO求解模型求解模型是有帮助的。定义初值的格式为：是有帮助的。定义初值的格式为：“attribute（属性）（属性）=value_list（常数列表）；（常数列表）；”（5）计算段计算段(CALC)：以：以“CALC:”开始，开始，“ENDCALC”结束，对一些原始数据进行计算处理。结束，对一些原始数据进行计算处理。28基本集合与派生集合基本集合与派生集合例例2 建筑工地的位置建筑工地的位置(用平面坐标用平面坐标a,b表示，距离单位：表示，距离单位：公里公里)及水泥日用量及水泥日用量d(吨吨)下表给出。有两个临时料场位下表给出。有两个临时料场位于于P(5,1),Q(2,7),日储量各有日储量各有20吨。从吨。从A,B两料场分别两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。两向各工地运送多少吨水泥，使总的吨公里数最小。两个新的料场应建在何处，节省的吨公里数有多大？个新的料场应建在何处，节省的吨公里数有多大？a1.258.750.55.7537.25b1.250.754.7556.57.75d354761129基本集合与派生集合基本集合与派生集合建立模型建立模型记工地的位置为记工地的位置为 ，水泥日用量为，水泥日用量为 ；料；料场位置为场位置为 ，日储量为，日储量为 ；从料场；从料场 向工地向工地 的运送量为的运送量为 。30基本集合与派生集合基本集合与派生集合本例中集合的概念本例中集合的概念利用集合的概念，可以定义需求点利用集合的概念，可以定义需求点DEMAND和供应点和供应点SUPPLY两个集合，分别有两个集合，分别有6个和个和2个元素个元素(下标下标)。集合的属性相当于以集合的元素为下标的数组。这里的集合的属性相当于以集合的元素为下标的数组。这里的 相当于二维数组。它的两个下标分别来自集合相当于二维数组。它的两个下标分别来自集合DEMAND和和SUPPLY，因此可以定义一个由二元对组，因此可以定义一个由二元对组成的新的集合，然后将成的新的集合，然后将 定义成这个新集合的属性。定义成这个新集合的属性。link(demand,supply):c;31基本集合与派生集合定义了三个集合，其中定义了三个集合，其中LINK在前在前两个集合两个集合DEMAND 和和SUPPLY的的基础上定义基础上定义表示集合表示集合LINK中的元素就是集合中的元素就是集合DEMAND 和和SUPPLY的元素组合成的有序二元组，的元素组合成的有序二元组，从数学上看从数学上看LINK是是DEMAND 和和SUPPLY的笛的笛卡儿积，也就是说卡儿积，也就是说LINK=（S，T）|SDEMAND，TSUPPLY因此，其属性因此，其属性C也就是一个也就是一个6*2的矩阵（或者说的矩阵（或者说是含有是含有12个元素的二维数组）。个元素的二维数组）。LINGO建模语言也称为矩阵生成器（建模语言也称为矩阵生成器（MATRIX GENERATOR）。）。类似类似DEMAND 和和SUPPLY直接把元素列举出来的集合，称为直接把元素列举出来的集合，称为基基本集合本集合(primary set),而把而把LINK这种基于其它集合而派生出来的这种基于其它集合而派生出来的二维或多维集合称为二维或多维集合称为派生集合派生集合(derived set)。由于是。由于是DEMAND 和和SUPPLY生成了派生集合生成了派生集合LINK，所以，所以DEMAND 和和SUPPLY 称为称为LINK的的父集合父集合。程序程序:eg3.lg4 32基本集合与派生集合初始段初始段 LINGO对数据是按列赋值的对数据是按列赋值的 语句的实际赋值顺序是语句的实际赋值顺序是X=(5,2),Y=(1,7),而不是而不是X=(5,1),Y=(2,7)等价写法：等价写法：“X=5,2；Y=1,7；”同理，数据段中对常数数组同理，数据段中对常数数组A，B的赋值语句也可以写成的赋值语句也可以写成A,B=1.25 1.25 8.75 0.75 0.5 4.75 5.75 5 3 6.5 7.25 7.75；33基本集合与派生集合定义目标和约束，与前例的方法是类似定义目标和约束，与前例的方法是类似(这里这里包含了派生集合包含了派生集合)，请特别注意进一步体会集，请特别注意进一步体会集合函数合函数SUM和和FOR的用法。的用法。由于新建料场的位置理论上讲可以是任意的，由于新建料场的位置理论上讲可以是任意的，所以在约束的最后所以在约束的最后(模型的模型的“END”语句上面语句上面的一行的一行)用用free函数取消了变量函数取消了变量X、Y的非负的非负限制限制在程序开头用在程序开头用TITLE语句语句对这个模型取了一个标题对这个模型取了一个标题“LOCATION PROBLEM；并且对目标行（并且对目标行（OBJ）和两类约束和两类约束（DEMAND_CON、SUPPLY_CON）分别进）分别进行了命名行了命名(请特别注意这里请特别注意这里约束命名的特点约束命名的特点)。34基本集合与派生集合解答解答:运行菜单命令运行菜单命令“LINGO|Solve”局部最优解局部最优解X(1)=7.249997，X(2)=5.695940，Y(1)=7.749998，Y(2)=4.928524，C（略），（略），最小运量最小运量=89.8835(吨公里吨公里)。问题问题:最小运量最小运量89.8835是不是全局最优是不是全局最优 使用使用“LINGO|Options”菜单命令打开选项对话框，在菜单命令打开选项对话框，在“Global Solver”选项卡上选择选项卡上选择“Use Global Solver”,激激活全局最优求解程序。活全局最优求解程序。35基本集合与派生集合问题问题:最小运量最小运量89.8835是不是全局最优是不是全局最优 为减少计算工作量，对为减少计算工作量，对X，Y的取值再做一些限制。虽然理论上的取值再做一些限制。虽然理论上新建料场的位置可以是任意的，但显然最佳的料场位置不应该离新建料场的位置可以是任意的，但显然最佳的料场位置不应该离工地太远，至少不应该超出现在工地太远，至少不应该超出现在6个工地所决定的坐标的最大、个工地所决定的坐标的最大、最小值决定的矩形之外，即最小值决定的矩形之外，即:0.5=x=8.75,0.75=y=7.75.此时目标函数值的下界（此时目标函数值的下界（Obj Bound=85.2638）与目前得到的最好）与目前得到的最好的可行解的目标函数值（的可行解的目标函数值（Best Obj=85.2661）相差已经非常小，可）相差已经非常小，可以认为已经得到了全局最优解。以认为已经得到了全局最优解。36基本集合与派生集合计算结果计算结果 工地与料场示意图工地与料场示意图:“*”表示料场，表示料场，“+”表示工地表示工地 可以认为是模型的最后结果可以认为是模型的最后结果 如果要把料厂如果要把料厂P(5,1),Q(2,7)的位置看成是已的位置看成是已知并且固定的，这时是知并且固定的，这时是LP模型。只需要把初始模型。只需要把初始段的段的“X Y=5，1，2，7；”语句移到数据段就语句移到数据段就可以了。此时，运行结果告诉我们得到全局最可以了。此时，运行结果告诉我们得到全局最优解（变量优解（变量C的取值这里略去），最小运量的取值这里略去），最小运量136.2275(吨公里吨公里)。37稠密集合与稀疏集合稠密集合与稀疏集合包含了两个基本集合构成的所有二元有序对的派生集合称为包含了两个基本集合构成的所有二元有序对的派生集合称为稠密集合稠密集合(简简称稠集称稠集)。有时候，在实际问题中，一些属性。有时候，在实际问题中，一些属性(数组数组)只在笛卡儿积的一个只在笛卡儿积的一个真子集合上定义，这种派生集合称为真子集合上定义，这种派生集合称为稀疏集合稀疏集合(简称疏集简称疏集)。例例3(最短路问题最短路问题)在纵横交错的公路网中，货车司机希望找到一条从一在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一个城市的最短路个城市到另一个城市的最短路.下图表示的是公路网下图表示的是公路网,节点表示货车可以节点表示货车可以停靠的城市停靠的城市,弧上的权表示两个城市之间的距离弧上的权表示两个城市之间的距离(百公里百公里).那么那么,货车从城货车从城市市S出发到达城市出发到达城市T,如何选择行驶路线如何选择行驶路线,使所经过的路程最短使所经过的路程最短?STA1 A2 A3 B1 B2 C1 C2 63366587467895638稠密集合与稀疏集合稠密集合与稀疏集合STA1 A2 A3 B1 B2 C1 C2 633665874678956分析分析 为得到从为得到从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)的最优行驶路线的最优行驶路线.而而S到到Ai(i=1,2,3)的最优行的最优行驶路线是很容易得到的驶路线是很容易得到的(实际上实际上,此例中此例中S到到Ai(i=1,2,3)只有唯一的道路只有唯一的道路)39稠密集合与稀疏集合稠密集合与稀疏集合分析分析 可把从可把从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的最优行驶路线的路长的最优行驶路线的路长:STA1 A2 A3 B1 B2 C1 C2 63366587467895640稠密集合与稀疏集合稠密集合与稀疏集合计算计算STA1 A2 A3 B1 B2 C1 C2 633665874678956所以所以,从从S到到T的最优行驶路线的路长为的最优行驶路线的路长为20.进一步分析以上进一步分析以上求解过程求解过程,可以得到从可以得到从S到到T的最优行驶路线为的最优行驶路线为S A3 B2 C1 T.这种计算方法在这种计算方法在数学上称为数学上称为动态动态规划规划(Dynamic Programming)41本例的本例的LINGO求解求解“CITIES”(城市城市):一个基本集合一个基本集合(元素通过枚举给出元素通过枚举给出)L:CITIES对应的属性变量对应的属性变量(我们要求的最短路长我们要求的最短路长)“ROADS”(道路道路):由由CITIES导出的一个派生集合导出的一个派生集合(请请特别注意其用法特别注意其用法),由于只有一部分城市之间有道路由于只有一部分城市之间有道路相连，所以不应该把它定义成稠密集合，将其元素相连，所以不应该把它定义成稠密集合，将其元素通过枚举给出，这就是一个稀疏集合。通过枚举给出，这就是一个稀疏集合。D:稀疏集合稀疏集合ROADS对应的属性变量对应的属性变量(给定的距离给定的距离)程序程序:eg4.lg4 42稠密集合与稀疏集合从模型中还可以看出：这个从模型中还可以看出：这个LINGO程序可以没有目标程序可以没有目标函数，这在函数，这在LINGO中，可以用来找可行解中，可以用来找可行解(解方程组和解方程组和不等式组不等式组)。在数据段对在数据段对L进行赋值，只有进行赋值，只有L(S)=0已已知，后面的值为空知，后面的值为空(但位置必须留出来，但位置必须留出来，即逗号即逗号“，”一个也不能少，否则会出一个也不能少，否则会出错错)。如果这个语句直接写成。如果这个语句直接写成“L=0；”，语法上看也是对的，但其含义是，语法上看也是对的，但其含义是L所所有元素的取值全部为有元素的取值全部为0，所以也会与题，所以也会与题意不符。意不符。43稠密集合与稀疏集合稠密集合与稀疏集合虽然集合虽然集合CITIES中的元素不是数字，但当中的元素不是数字，但当它以它以CITIES(I)的形式出现在循环中时，引的形式出现在循环中时，引用下标用下标I却实际上仍是正整数，也就是说却实际上仍是正整数，也就是说I指指的正是元素在集合中的位置的正是元素在集合中的位置(顺序顺序)，一般称，一般称为元素的索引为元素的索引(INDEX)。在在for循环中的过滤条件里用了一个函数循环中的过滤条件里用了一个函数“index”,其作用是返回一个元素在集合其作用是返回一个元素在集合中的索引值，这里中的索引值，这里index(S)=1(即元素即元素S在在集合中的索引值为集合中的索引值为1)，所以逻辑关系式，所以逻辑关系式“I#GT#index(S)”可以可以直接等价地可以可以直接等价地写成写成“I#GT#1”。这里。这里index(S)实际上还实际上还是是index(CITIES,S)的简写，即返回的简写，即返回S在集在集合合CITIES中的索引值。中的索引值。44稠密集合与稀疏集合本例的本例的LINGO求解结果求解结果从从S到到T的最优行驶路线的路长为的最优行驶路线的路长为20(进一步分析，可以得到进一步分析，可以得到最优行驶路线为最优行驶路线为S A3 B2 C1 T)。45集合的类型 集合集合 派生集合派生集合 基本集合基本集合 稀疏集合稀疏集合 稠密集合稠密集合 元素列表法元素列表法 元素过滤法元素过滤法 直接列举法直接列举法 隐式列举法隐式列举法setname/member_list/:attribute_list;setname(parent_set_list)/member_list/:attribute_list;SETS:CITIES/A1,A2,A3,B1,B2/;ROADS(CITIES,CITIES)/A1,B1 A1,B2 A2,B1 A3,B2/:D;ENDSETSSETS:STUDENTS/S1.S8/;PAIRS(STUDENTS,STUDENTS)|&2#GT#&1:BENEFIT,MATCH;ENDSETS46集合使用小结基本集合的定义语法基本集合的定义语法 setname/member_list/:attribute_list;其中其中setname为定义的集合名，为定义的集合名，member_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,JAN200247派生集合的定义语法派生集合的定义语法 setname(parent_set_list)/member_list/:attribute_list;与基本集合的定义相比较多了一个与基本集合的定义相比较多了一个parent_set_list(父集合列表父集合列表)。父集合列表中的集合父集合列表中的集合(如如 set1，set2，等，等)称为派生集合称为派生集合setname的的父集合，它们本身也可以是派生集合。父集合，它们本身也可以是派生集合。48算术运算符算术运算符LINGO中的算术运算符有以下中的算术运算符有以下5种：种：+（加法），（加法），-（减法或负号），（减法或负号），*（乘法），（乘法），/（除法），（除法），(求幂求幂)。49逻辑运算符逻辑运算符在在LINGO中，逻辑运算中，逻辑运算(表达式表达式)通常作为过滤条件使用通常作为过滤条件使用,逻辑逻辑运算符有运算符有9种，可以分成两类：种，可以分成两类：#AND#(与与)#OR#(或或)#NOT#(非非)：逻辑值之间的运算，它们操作的对象本身已经是：逻辑值之间的运算，它们操作的对象本身已经是逻辑值或逻辑表达式