2022年Lingo教程 .pdf

《2022年Lingo教程 .pdf》由会员分享，可在线阅读，更多相关《2022年Lingo教程 .pdf（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、谢金星： MATLAB 优化工具箱和LINDO/LINGO 优化软件 第 69 页 共 112 页 第 69 页 共 112 页第 4 章 LINGO 软件的使用方法LINGO 8.0 for Windows软件比以前的版本有了很大的改进，功能大大增强，性能更加稳定，解答结果更加可靠。 该软件安装程序的文件大小通常20M 多一点，安装过程与LINDO 6.1 for Windows的安装过程完全类似，我们下面假设该软件已经安装完毕。同样， LINGO 8.0也有两种命令模式：一种是常用的Windows模式 , 通过下拉式菜单命令驱动LINGO 运行（多数的菜单命令通常有快捷键，常用的菜单命令在

2、工具栏中有图标表示的快捷按钮） ， 界面是图形式的， 使用起来也比较方便；另一种是命令行 (Command-Line) 模式 , 仅在命令窗口(Command Window) 下操作，通过输入行命令驱动LINGO 运行，其使用界面不是图形式的，而是字符式的，初学者往往不太容易掌握。与上一章一样，我们仍然主要在 Windows菜单驱动模式下介绍LINGO 的使用方法，最后再简单介绍一下命令行模式下的主要行命令。第三章 3.1.1节说过， 从基本功能上看， 与 LINDO 相比， LINGO 软件主要有两大优点：1、 除具有 LINDO 的全部功能外，还可用于求解非线性规划问题，包括非线性整数规划

3、问题。2、 LINGO 包含了内置的建模语言，允许以简练、直观的方式描述较大规模的优化问题，模型中所需的数据可以以一定格式保存在独立的文件中。前一条是很容易理解的。那么后一条呢？从前一章的介绍中可以看到，虽然LINDO 输入模型的格式与我们数学上对数学规划的表达式非常接近，但是如果我们希望在LINDO 模型窗口下输入一个比较大规模的模型，那将是一件非常费时费力的事情。例如，如果决策变量有1000个，由于LINDO 不提供数组或类似的数据结构，我们除了用x1,x2, , x1000或类似方法表示决策变量外，完全没有其他办法。而对实际企业中的优化问题，决策变量达到几十万个也是常有的事， 显然用前面

4、那种在LINDO 模型窗口下输入模型的方法几乎是不可能的。而 LINGO 则在这方面通过引入建模语言有了很大改进. 也就是说，即使你只对解线性规划感兴趣，你也应该学习使用LINGO 。4.1 初识 LINGO 在 Windows操作系统下双击LINGO 图标， 启动 LINGO 软件， 屏幕上首先显示如图4-1所示的窗口。图 4-1名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 44 页 - - - - - - - - - 谢金星： MATLAB 优化工具箱和LINDO/

5、LINGO 优化软件 第 70 页 共 112 页 第 70 页 共 112 页图 4-1中最外层的窗口使LINGO 软件的主窗口， 所有其他窗口都在这个窗口之内。当前光标所在的窗口上标有“LINGO MODEL LING01”，这就是模型窗口，也就是用于输入优化模型的窗口。初步观察可以看到，图4-1这个界面与LINDO 软件的界面非常类似，只是在LINGO软件的主窗口中，最下面增加了一个状态行（仔细观察，可以发现菜单和工具栏也略有区别）。目前，状态行最左边显示的是“Ready ”，表示“准备就绪”；右下角显示的是当前时间，时间前面是当前光标的位置（1 行1 列）。将来，用户可以用选项命令（L

6、INGO|Options菜单命令）决定是否需要显示工具栏和状态行。作为一个最简单的例子，我们看看上一章3.2 节中输入的那个简单例子在LINGO 下应当如何输入 . 当时我们把它存入了一个名为EXAM0202.LTX的模型文件中， 为了对比LINDO 和LINGO 输入的差别， 我们现在重新用LINDO 的“File|Open” 菜单命令把它打开，看到该例子是图 4-2 所示的线性规划。图 4-2 图 4-3 在 LINGO 中，还有一个命令可以直接把LINDO 的模型文件转化成LINGO 模型。我们选择菜单命令FILE | IMPORT LINDO FILE (F12), 其意思是“导入LI

7、NDO 文件”，则屏幕上会名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 44 页 - - - - - - - - - 谢金星： MATLAB 优化工具箱和LINDO/LINGO 优化软件 第 71 页 共 112 页 第 71 页 共 112 页显示一个标准的“打开文件”的对话框，我们在目录下找到EXAM0202.LTX，选定该文件后，屏幕显示如图4-3。这个命令在LINGO主窗口中又打开了两个子窗口，一个是命令窗口（Command Window ），另一个是名为“ex

8、am0202”的模型窗口。可以看出，当前光标位于命令窗口（从主窗口左上角的显示结果也可以知道当前的活动窗口），命令窗口显示的正是从 EXAM0202.LTX读出的原始文本文件；而“exam0202” 窗口才是由EXAM0202.LTX转化而来的等价的LINGO 模型。比较图 4-2 和图 4-3 可以发现转化工作主要在于以下几个方面（这也是LINGO 模型的最基本特征）：（1） 将目标函数的表示方式从“MAX ”变成了“ MAX= ”; （2） “ST”在 LINGO 模型中不再需要，所以被删除了；（3） 在每个系数与变量之间增加了运算符“* ”（即乘号不能省略）；（4） 每行（目标、约束和说

9、明语句）后面均增加了一个分号“;”; （5） 约束的名字被放到了一对方括号“ ”中，而不是放在右半括号“）”之前；（6） 模型结束标志“END”也被删除了（LINGO 中只有当模型以“MODEL ：”开始时才能以“ END ” 结束）。注意：在上一章的最后，我们曾经用行命令“SAVE ”把同样的LINDO模型存入了一个名为 MODEL01.LTX的模型文件中。 但是经过试验， 笔者发现菜单命令FILE | IMPORT LINDO FILE (F12) 不能把 MODEL01.LTX正确地转化成LINGO 模型。即使对于在LINDO中用菜单命令保存下来的模型，笔者也多次发现有时不能正确地转化（

10、转化时出现严重错误）。因此，本人的经验是： 为了保证将来能将LINDO 模型移植到LINGO 中去，在 LINDO 模型输入时应尽量采用“规范化”的格式（例如：说明语句最好单独占据一行；行名（目标和约束的名字）不要以数字开头；尽量避免少出现汉字和非标准的英文字符；二次规划（QP）模型不能被正确转化；等等）。无论如何，幸运的是我们的LINGO 模型“ exam0202”已经成功地得到了。现在把光标移动到“ exam0202” 模型窗口，然后选择菜单命令“LINGO|SOLVE ”对该模型进行求解（求解时 LINGO 自然还是先对模型进行编译，模型编译没有发现语法错误才开始求解）；求解结束得到的结

11、果与LINDO 下得到的结果相同（但不询问是否进行敏感性分析），结果仍然在报告窗口中显示（这里我们就不给出这个报告窗口的示意图了）。图 4-4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 44 页 - - - - - - - - - 谢金星： MATLAB 优化工具箱和LINDO/LINGO 优化软件 第 72 页 共 112 页 第 72 页 共 112 页现在我们可以把模型和结果报告保存在文件中。例如，当光标位于“exam0202” 模型窗口时选择菜单命令“Fil

12、e|Save As ”，则出现图4-4 所示的对话框。后缀“LG4”表示 LINGO格式的模型文件，是一种特殊的二进制格式文件，保存了我们在模型窗口中所能够看到的所有文本和其他对象及其格式信息，只有LINGO 能读出它，用其他系统打开这种文件时会出现乱码。“ LNG ”表示 LINGO 文本文件，以这个格式保存模型时LINGO 将给出警告，因为模型中的格式信息（如字体、颜色、嵌入对象等）将会丢失。“LDT ”表示 LINGO 数据文件，“LTF ”表示 LINGO 命令脚本文件，“LGR ”表示 LINGO 报告文件。除“LG4”文件外，这里除“ LG4”格式外的文件其实都是普通的文本文件，可

13、以用任何文本编辑器打开和编辑。图 4-5 求解时也会显示状态窗口（如图4-5 所示），包含的内容比LINDO 求解时的状态窗口中的内容要多一些 （注意： 可能由于 LINDO 和 LINGO 对中文 WINDOWS系统的兼容性不太好，所以图 4-5 中有些显示字符和单词被截掉了）。下面我们给出相应的解释：右边的5 个框分别给出变量数量（其中包括变量总数、非线性变量数、整数变量数）、约束数量（约束总数、非线性约束个数）、非零系数数量（总数、非线性项的个数）、内存使用量、求解花费的时间。需要注意的是，凡是可以从一个约束直接解出变量取值时，这个变量就不认为是决策变量而是固定变量，不列入统计中；只含有

14、固定变量的约束也不列入约束统计中（参见第三章3.1.3 节的说明）。总的来说，这些统计值的意义比较清楚，图4-5 中最下面一行的含义也与LINDO状态窗口类似，我们下面主要详细介绍一下图4-5 左边的两个框中内容。左上角是求解器（求解程序） 状态框 （Solver Status），含义见表4-1；左下角是扩展的求解器（求解程序）状态框（ Extended Solver Status），含义见表4-2。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 44 页 - - - -

15、 - - - - - 谢金星： MATLAB 优化工具箱和LINDO/LINGO 优化软件 第 73 页 共 112 页 第 73 页 共 112 页域名含义可能的显示Model Class 当前模型的类型 （请参阅前面章节）LP，QP，ILP，IQP，PILP， PIQP ，NLP，INLP ，PINLP （以 I 开头表示IP，以 PI 开头表示PIP）State 当前解的状态Global Optimum, Local Optimum, Feasible, Infeasible （不可行）, Unbounded （无界） , Interrupted （中断） , Undetermined

16、（未确定）Objective 当前解的目标函数值实数Infeasibility 当前约束不满足的总量（不是不满足的约束的个数）实数（即使该值 =0，当前解也可能不可行，因为这个量中没有考虑用上下界形式给出的约束）Iterations 目前为止的迭代次数非负整数表 4-1 域名含义可能的显示Solver Type 使用的特殊求解程序 B-and-B （分枝定界算法）Global （全局最优求解程序）Multistart （用多个初始点求解的程序）Best Obj 目前为止找到的可行解的最佳目标函数值实数Obj Bound 目标函数值的界实数Steps 特殊求解程序当前运行步数：分枝数（对 B-a

17、nd-B 程序）；子问题数（对 Global 程序）；初始点数（对Multistart程序）非负整数Active 有效步数非负整数表 4-2 作为一个例子，我们现在再用LINGO 来解第 1 章 1.4节给出的如下二次规划问题：Max 98 x1 + 277 x2 x12 0.3 x1 x2 2x22s.t. x1 + x2 100 x1 2 x2 x1 , x2 0 为整数该模型输入LINGO1 模型窗口后的形式见图4-6。对照第3 章 3.6节，我们可以看出用LINGO 解 QP 比用 LINDO 解要容易输入模型。注意：原来的整数限定语句“GIN X1”和“GIN X2”这里变成了“GI

18、N(X1) ”和“ GIN(X2) ”；但在 LINDO 下也可以写成“GIN 2 ”，这里却不可写成“GIN(2) ”，否则 LINGO 将把这个模型看成没有整数变量。在LINGO 中，以“ ”开头的都是函数调用，我们将在本章4.5 节详细介绍LINGO 中能够使用的所有函数。图 4-6 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 44 页 - - - - - - - - - 谢金星： MATLAB 优化工具箱和LINDO/LINGO 优化软件 第 74 页 共 1

19、12 页 第 74 页 共 112 页图 4-7 现在运行菜单命令“LINGO|Solve ”，则可以得到图4-7 所示的解答报告，最优整数解X=（35 ，65 ），最大利润 =11077.5。结果中最优整数解与第3 章 3.6节相同，但最优值略有不同，估计是计算误差引起的。此外，LINGO 是将它作为PINLP （纯整数非线性规划）来求解，因此只告诉我们找到的是局部最优解（为什么LINGO 不将它作为PIQP（纯整数二次规划）来求解？本人也不清楚）。你还可以选择运行菜单命令“WINDOW|Status Window”看到图 4-8 所示的状态窗口（这时我们已经把该规划模型保存到了文件IQP0

20、302B.LG4 中，所以这个名字现在也出现在状态窗口中），从中可以看到目前为止找到的最佳目标值“Best Obj”与问题的上界“Obj Bound ”已经是一样的，当前解的最大利润与这两个值非常接近，估计是计算误差引起的差异。 实际上，如果采用全局最优求解程序（我们将在后面介绍 “LINGO|Options ”菜单命令时介绍如何激活全局最优求解程序），可以验证它就是全局最优解。图 4-8 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 44 页 - - - - - -

21、- - - 谢金星： MATLAB 优化工具箱和LINDO/LINGO 优化软件 第 75 页 共 112 页 第 75 页 共 112 页在本节的最后，我们对LINGO 的基本用法指出几点注意事项：1)变量和行名可以超过8 个字符，但不能超过32 个字符，且必须以字母开头。2)与 LINDO 相同，用LINGO 解规划时已假定各变量非负（除非用限定变量取值范围的函数free或sub 或slb 另行说明）。3)与 LINDO 不同，变量可以放在约束条件的右端（同时数字也可放在约束条件的左端）。但为了提高LINGO 求解时的效率， 应尽可能采用线性表达式定义目标和约束（如果可能） 。4.3 在

22、LINGO 中使用集合4.3.1 集合的基本用法我们前面说过，LINGO同时也是优化问题的一种建模语言。有了它，使用者可以只用键入一行文字就可以建立起含有大规模变量的目标函数和成千上万条约束。掌握这种最优化模型语言是非常重要的，与LINDO 相比，这可使输入较大规模问题的过程得到简化。理解 LINGO 建模语言最重要的是理解“集合”（SET）及其“属性”（Attribute）的概念。什么是集合呢？我们通过下面的一个简单例子开始来进行介绍。例： SAILCO公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是40 条， 60 条， 75 条， 25 条，这些需求必须按时满足。每个季度

23、正常的生产能力是40 条帆船，每条船的生产费用为400 美元。如果加班生产，每条船的生产费用为450 美元。每个季度末，每条船的库存费用为20 美元。假定生产提前期为0，初始库存为10 条船。如何安排生产可使总费用最小？我们用 DEM,RP,OP,INV分别表示需求、正常生产的产量、加班生产的产量、库存量，则 DEM,RP,OP,INV对每个季度都应该有一个对应的值，也就说他们都应该是一个由4 个元素组成的数组，其中DEM是已知的，而RP,OP,INV是未知数。现在我们可以写出这个问题的模型。首先，目标函数是所有费用的和：MIN =+4,3, 2, 1)(20)(450)(400IIINVIO

24、PIRP约束条件主要有两个：1）能力限制：RP(I)1 ；“ #GT# ”是逻辑运算符号，意思是“大于”（其他逻辑运算符将在本章后面3.4节介绍）。QUARTERS 集合的属性DEM RPOP INV QUARTERS 集合234 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 44 页 - - - - - - - - - 谢金星： MATLAB 优化工具箱和LINDO/LINGO 优化软件 第 77 页 共 112 页 第 77 页 共 112 页现在运行菜单命令“

25、LINGO|Solve ”，则可以得到图4-11 所示的解答报告，全局最优解RP=（40 ，40 ，40 ， 25 ）， OP=（0，10 ，35 ，0），最小成本=78450 。这就是我们模型的计算结果。图 4-11 一般来说， LINGO中建立的优化模型由四个部分组成，或称为四“段”（SECTION ）：（1）集合段（ SETS）：这部分要以 SETS: 开始，以 ENDSETS结束，作用在于定义必要的集合变量 （SET）及其元素 （MEMBER ，含义类似于数组的下标）和属性（ATTRIBUTE ，含义类似于数组）。如上例中定义了集合quarters（含义是季节），这里它包含四个元素即四

26、个季节指标（1,2,3,4），每个季节都有需求（DEM）、正常生产量（RP）、加班生产量（ OP）、库存量（ INV ）等属性（相当于数组，数组下标由quarters元素决定）。一旦这样的定义建立起来，如果quarters的数量不是4而是1000,只需扩展其元素为1,2 ，.,1000,每个季节仍然都有DEM,RP,OP,INV这样的属性 ( 这些量的具体数值如果是常量，则可在数据段输入；如果是未知数，则可在初始段输入初值) 。自然，当quarters的数量不是4 而是 1000 时，我们也没有必要枚举，而是可以如下定义quarters集合：quarters/1.1000/:DEM,RP,OP

27、,INV; 即“ 1.1000”的意识就是从1 到 1000 的所有整数。（2）目标与约束段：这部分实际上定义了目标函数，约束条件等。一般要用到LINGO的内部函数，可在具体使用中体会其功能和用法( 详见4.5节) 。上例中定义的目标函数与quarters的元素数目是 4 或 1000并无具体的关系。约束的表示也类似。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 44 页 - - - - - - - - - 谢金星： MATLAB 优化工具箱和LINDO/LINGO 优

28、化软件 第 78 页 共 112 页 第 78 页 共 112 页（3）数据段（ DATA）：这部分要以 DATA: 开始，以 ENDDATA 结束，作用在于对集合的属性（数组）输入必要的常数数据。格式为：attribute = value_list。常数值列表（value_list）中数据之间可以用逗号“，”分开，也可以用空格分开（回车的作用也等价于一个空格），如上面对DEM的赋值也可以写成“DEM=40 60 75 25”。在 LINGO 模型中，如果想在运行时才对参数赋值，可以在数据段使用输入语句。但这仅用于对单个变量赋值，而不能用于属性变量（数组），输入语句格式为：“变量名 = ？；”

29、。例如，上面的例子中如果需要在求解模型时才给出初始库存量（记为A），则可以在模型中数据段写上“ A = ?；”语句，在求解时LINDO 系统给出提示界面，等待用户输入变量A 的数值。（4）初始段（ INIT）：这部分要以 INIT: 开始，以 ENDINIT结束，作用在于对集合的属性（数组）定义迭代初值，如果有一个接近最优解的初值，对LINGO 求解模型是有帮助的。格式为：attribute = value_list;上例中没有初始化部分，我们将在下一个例子中举例说明。实际上， LINGO 模型在求解时也是要展开成与LINDO 模型类似的形式的。选择菜单命令“LINGO|Generate|Di

30、sply model ” （Ctrl+G），可以得到展开形式的模型如图4-12所示，这与我们在LINDO 下的模型输入形式很类似，只是在LINDO 中不允许有这种数组形式的变量。注意：如果目标或约束中有非线性变量项，对应的非线性变量前的系数将以问号（“？”）显示。图 4-12 432 基本集合与派生集合我们下面再用LINGO 来解在第一章1.5 节中介绍的如下料场选址问题：222161)()(minijijjiijbyaxcf-+-=s.t. 6, 1,21L=idcijij2, 1,61=jecjiij当使用现有临时料场时，决策变量只有cij，是 LP 模型；当为新建料场选址时决策变量为ij

31、c和jjyx ,，由于目标函数f对jjyx ,是非线性的，所以在新建料场时是NLP 模型。我们现在先解 NLP 模型，而把现有临时料场的位置作为初始解告诉LINGO 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 44 页 - - - - - - - - - 谢金星： MATLAB 优化工具箱和LINDO/LINGO 优化软件 第 79 页 共 112 页 第 79 页 共 112 页输入后的程序如图4-13 所示。我们在集合段定义了三个集合，其中 DEMAND 和

32、SUPPLY集合的及其属性的含义与上一个例子类似，而 LINK 则是在前两个集合的基础上定义的一个集合。 LINK 中的元素就是DEMAND 和 SUPPLY 的笛卡儿积，也就是LINK= （S，T）|SDEMAND ，TSUPPLY 因此，其属性C 也就是一个6*2 的矩阵（或数组）。正是由于这种表示方式，LINGO 建模语言也称为矩阵生成器（MATRIX GENERATOR ）。 DEMAND 和 SUPPLY 这种直接把元素列举出来的集合，称为基本集合 （primary set，也可译为“原始集合”），而把LINK 这种基于基本集合构造的集合称为派生集合 （derived set, 也可

33、译为“导出集合”）。图 4-13 本模型中包括了初始段，请特别注意其中“X Y =5 ，1，2，7；”语句的实际赋值顺序是X=(5,2), Y=(1,7), 而不是 X=(5,1), Y= （2,7)。也就是说， LINGO 对数据是按列赋值的，而不是按行。当然，你直接写成两个语句“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；请注意我们前面说过，这时空格与逗号“，”或“回车”的作用是等价的。由于新建料场的位置可以是任意的，所

34、以我们在约束的最后（模型最后的END 上面一行）用free 函数取消了变量X、Y 非负限制。 此外， 我们用 TITLE 语句对这个模型取了一个标题“LOCATION PROBLEM” （见模型开始的 “MODEL ：”下面一行） ；并且对目标行 （OBJ ）和两类约束（ DEMAND_CON 、SUPPLY_CON ）分别进行了命名(请特别注意这里约束命名的特点 )。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 44 页 - - - - - - - - - 谢金星：

35、 MATLAB 优化工具箱和LINDO/LINGO 优化软件 第 80 页 共 112 页 第 80 页 共 112 页大家仔细阅读、理解了图4-13 的程序后，现在就可以运行菜单命令“LINGO|Solve ”，很快得到解答报告（显示界面略，请特别注意结果中约束名称也是有下标的）：局部最优解X(1)=7.249997， X(2)=5.695940，Y(1)=7.749998， Y(2)=4.928524，C（略），最小运量 =89.8835(吨公里 ) 。现在我们来看看对于这个问题的NLP 模型，最小运量89.8835是不是全局最优。我们考虑用全局最优求解程序（我们将在后面介绍“LINGO|

36、Options ”菜单命令时介绍如何激活全局最优求解程序），解图4-13 中的模型。全局最优求解程序花费的时间可能是很长的，所以为了减少计算工作量，我们对 X， Y 的取值再做一些限制。虽然新建料场的位置可以是任意的，但我们可以很直观地想到，最佳的料场位置不应该离工地太远，无论如何至少不应该超出现在 6 个工地所决定的坐标的最大、最小值决定的矩形之外，即: 0.5=x=8.75, 0.75=y=7.75.可以用 bnd 函数加上这个条件取代模型END 上面的行，运行 NLP 模型，发现全局最优求解程序花费的时间仍然很长，图4-14 是运行 27 分 35 秒时人为终止求解的求解状态窗口。从图

37、14 可以看出，此时目标函数值的下界（Obj Bound=85.2638 ）与目前得到的最好的可行解的目标函数值 （Best Obj=85.2661） 相差已经非常小， 可以认为已经得到了全局最优解。部分结果见图4-15，这就可以认为是我们模型的最后结果。在图4-16 中，我们可以画出料场和工地的位置示意图，其中标有“*”号的是料场，标有“+”号的是工地。我们还可以指出： 如果要把料厂P(5, 1), Q (2, 7)的位置看成是已知并且固定的，这时是 LP模型。只需要在图4-13 中把初始段的“X Y =5 ，1，2，7；”语句移到数据段就可以了。此时，运行结果告诉我们得到全局最优解（变量

38、C 的取值这里略去） ， 最小运量136.2275( 吨公里 ) 。图 4-14 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 44 页 - - - - - - - - - 谢金星： MATLAB 优化工具箱和LINDO/LINGO 优化软件 第 81 页 共 112 页 第 81 页 共 112 页图 4-15 图 4-16 433 稠密集合与稀疏集合上节我们介绍了在LINGO 中可以定义和使用两类集合：基本集合和派生集合。前面的例子中我们把派生集合MATCH的元素

39、定义为DEMAND 和 SUPPLY 的笛卡儿积，这种派生集合称为 稠密集合 （简称稠集）。其实在LINGO 中，派生集合的元素可以只是这个笛卡儿积的一个真子集合，这种派生集合称为稀疏集合 （简称疏集）。下面我们通过一个例子来说明。最短路问题在复杂的公路网中，货车司机希望找到一条从一个城市到另一个城市的最短路. 假设图4-17 表示的是该公路网, 节点表示货车可以停靠的城市,弧上的权表示两个城市之间的距离（百公里） 。货车从城市S 出发到达城市T,如何选择行驶路线,使所经过的路程最短? 012345678901234567835476112016名师资料总结 - - -精品资料欢迎下载 - -

40、 - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 44 页 - - - - - - - - - 谢金星： MATLAB 优化工具箱和LINDO/LINGO 优化软件 第 82 页 共 112 页 第 82 页 共 112 页A1 6 6 6 5 B1 C1 5 8 7 S 3 A2 6 8 T 7 B2C2 6 3 A34 9 图 4-17 最短路问题的例子假设从 S 到 T 的最优行驶路线 P 经过城市C1, 则 P 中从 S 到 C1的子路也一定是从S 到C1的最优行驶路线; 假设 P 经过城市 C2, 则 P 中

41、从 S 到 C2的子路也一定是从S 到 C2的最优行驶路线 . 因此 , 为了得到从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)只有唯一的道路). 也就是说

42、 ,此例中我们可以把从S到 T的行驶过程分成4个阶段 ,即 SAi(i=1,2 或 3), AiBj(j=1 或 2), Bj Ck(k=1 或 2), Ck T. 记 d(Y,X)为城市 Y 与城市 X 之间的直接距离（若这两个城市之间没有道路直接相连，则可以认为直接距离为无穷大），用 L(X) 表示城市S 到城市X 的最优行驶路线的路长, 则: L(S)=0; SXXYdYLXLXY+=),()(min)(对本例的具体问题，可以直接计算如下：L(A1)=6, L(A2)=3, L(A3)=3; L(B1)=min L(A1)+6, L(A2)+8, L(A3)+7= 10 = L(A3)+

43、7, L(B2)=min L(A1)+5, L(A2)+6, L(A3)+4= 7 = L(A3)+4; L(C1)=min L(B1)+6, L(B2)+8= 15 = L(B2)+8, L(C2)=min L(B1)+7, L(B2)+9= 16 = L(B2)+9; L(T)=min L(C1)+5, L(C2)+6= 20 = L(C1)+5. 所以 , 从 S到 T 的最优行驶路线的路长为20. 进一步分析以上求解过程, 可知从 S到 T 的最优行驶路线为S A3 B2 C1 T. 这种方法称为动态规划（Dynamic Programming ） 。作为一个例子，我们用LINGO 来

44、解这个最短路问题。我们可以编写如图4-18 的 LINGO程序。集合段定义的CITIES 是一个基本集合 （元素通过枚举给出） ， L 是其对应的属性变量 （我们要求的最短路长） ；ROADS 是由 CITIES 导出的一个派生集合（请特别注意其用法），由于只有一部分城市之间有道路相连，所以我们进一步将其元素通过枚举给出，这就是一个稀疏集合。 D 是 ROADS 对应的属性变量（给定的距离）。从模型中还可以看出：这个LINGO 程序可以没有目标函数，这在LINGO 中是允许的，可以用来找可行解（解方程组和不等式组）。此外，在数据段我们对L 进行了赋值，但只有L（S）=0 是已知的，所以后面的值

45、为空（但位置必须留出来，即逗号“，”一个也不能少，否则会出错）。如果这个语句直接写成“L=0； ” ，语法上看也是对的，但其含义是L 所有元素的取值全部为0，所以也会与题意不符。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 44 页 - - - - - - - - - 谢金星： MATLAB 优化工具箱和LINDO/LINGO 优化软件 第 83 页 共 112 页 第 83 页 共 112 页图 4-18 图 4-19 从这个例子还可以看出，虽然集合CITIES 中

46、的元素不是数字，但当它以CITIES （I）的形式出现在循环中时，引用下标I 却实际上是正整数，也就是说I 指的正是元素在集合中的位置（顺序），一般称为元素的索引（INDEX ） 。我们在 for 循环中故意用了一个函数“index”, 其 作 用 是 返 回 一 个 元 素 在 集 合 中 的 索 引 值 ， 这 里 index(S )=1， 所 以 逻 辑 关 系 式“ I#GT#index(S )” 可 以 直 接 等 价 地 写 成 “ I#GT#1 ”。 这 里 index(S )实 际 上 还 是index(CITIES ，S )的简写，即返回S在集合 CITIES 中的索引值。运

47、行以上程序后得到结果（图4-19） 。可以看出 , 从 S 到 T 的最优行驶路线的路长为20（进一步分析，可以得到从S 到 T 的最优行驶路线为S A3 B2 C1 T） 。上面这个例子中定义稀疏集合ROADS的方法是将其元素通过枚举给出，有时这还是太麻烦了，用起来不方便。LINGO提供了另一种定义稀疏集合的方法，这就是“元素过滤”法，能够从构成派生集合的父集合的笛卡儿积中系统地过滤下来一些真正的元素。请看下面的例子。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 4

48、4 页 - - - - - - - - - 谢金星： MATLAB 优化工具箱和LINDO/LINGO 优化软件 第 84 页 共 112 页 第 84 页 共 112 页某班 8 名同学准备分成4 个调查队（每队两人）前往4 个地区进行社会调查。假设这8名同学两两之间组队的效率如表4-3 所示（由于对称性，只列出了上三角部分），问如何组队可以使总效率最高？学生S1 S2 S3 S4 S5 S6 S7 S8 S1 - 9 3 4 2 1 5 6 S2 - - 1 7 3 5 2 1 S3 - - - 4 4 2 9 2 S4 - - - - 1 5 5 2 S5 - - - - - 8 7 6

49、 S6 - - - - - - 2 3 S7 - - - - - - - 4 表 4-3 这是一个典型的匹配 （MATCHING ） 问题。把上面的效率矩阵记为BENEFIT ，用 MATCH（Si，Sj）=1 表示同学Si，Sj 组成一队，而0 表示不组队。由于对称性，只需考虑ij 共 32个 0-1 变量。显然，目标函数为BENEFIT （Si，Sj）* MATCH （Si，Sj）之和；约束条件是每个同学只能（而且必须在）某一组，即对于任意i 有：只要 MATCH 属性的某个下标为i 就加起来，此和 =1。显然，这是一个0-1 线性规划。模型输入见图4-20，其中 STUDENTS 集合的

50、元素列表 “S1.S8”等价于写成 “S1 S2 S3 S4 S5 S6 S7 S8”, 它没有相关的属性列表，主要用于表示下标集合。我们看到在派生集合PAIRS的定义中，增加了过滤条件，即逻辑关系式“&2#GT#&1 ”, 意思是第2 个父集合的元素的索引值（用“ &2”表示）大于第1 个父集合的元素的索引值（用“&1”表示）。图 4-20 选择菜单命令“ LINGO|SOLVE ”运行这个程序，可以得到全局最优值=30。由于 MATCH变 量 中 多 数 为0， 我 们 这 里 练 习 一 下 如 何 更 清 晰 地 浏 览 最 优 解 解 。 选 择 菜 单 命 令“LINGO|SOLU