利用lingo建立最优化模型

《利用lingo建立最优化模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、利用LINGO建立最优化模型洪文1，朱云鹃1，金震1，王其文21（安徽大学商学院合肥230039）2（北京大学光华管理学院北京100871）摘要：本文借助于最优化软件LINGO建立了最小树、最短路、最大流、最小费用流和货郎担问题的LINGO模型，并对模型中的难点给出了注释。利用本文提供的模型，可以很容易地求出上述5个最优化问题的最优解。关键词：最小树、最短路、最大流、最小费用流、货郎担问题、LINGO中图分类号：0211.6文献标识码：A文章编号：0引言求解最小树、最短路、最大流、最小费用流和货郎担问

2、题的方法虽然很多，但是利用最优化求解软件LINGO建立相应的模型来求解上述5个问题是一种新的尝试。本文建立的模型有两个突出的特点。第一个特点是模型的数据与公式完全分离，这样使得问题的求解变得特别方便（对于不同的问题只要更换数据即可）。第二个特点是这五个模型都是利用最优化求解软件LINGO编写而成，可进行快速求解。1LINGO简介LINGO是一个简单而实用的最优化软件。利用线性和非线性最优化的方法，LINGO可以用公式简明地表示复杂的规划问题，并可以快速地求出问题的最优解。LINGO是由美国芝加哥LIN

3、DO系统公司研制。该公司根据用户信息、线性和非线性规划的理论和方法及计算机发展的需要不断推出新的版本。目前LINGO已成为世界上最为流行的最优化软件之一。LINGO在我国已经有了相当多的用户。它的主要特点是：1）LINGO含有一系列的接口函数。这些接口函数可用在文本文件、电子表格和数据库中，可与外部的输入/输出源进行连接。2）LINGO可以直接嵌入到Excel中，也可以将Excel嵌入到LINGO模型中。这样就可以将数据与模型分离，使得模型的维护和调试变得非常容易。3）LINGO使用Windows的窗

4、口展开优化分析功能，使用对话框展示各种功能。清晰、直观、易学易用。104）LINGO具有强大的计算功能。众所周知，建模难，求解模型更难。利用LINGO就可以摆脱复杂繁琐的计算烦恼。2LINGO与LINDO的关系LINGO与LINDO都是美国LINDO系统公司的产品。利用它们都可以求解线性规划，这是它们的共同点。但是两者还是有区别的。1）如果要输入5x+4y<70这样一个约束，在LINDO模型中可以直接输入，不需要变动。而在LINGO模型中一定要改成：5*x+4*y<70。后者比前者复杂，但这也正是后者

5、的特点：LINGO可以求解非线性规划，而LINDO只能求解线性规划。2）LINGO的集合函数功能非常强大，它可以使我们很容易地处理数据。例如可以利用集合语言将电子表格中数据调入模型，计算后将结果输出到电子表格中。这样，数据和模型就完全分离了，LINGO模型可以不因数据的变动而改动。3）利用LINGO的集合函数可以使我们摆脱处理复杂冗长表达式的烦恼。例如，假设a表示一个单位的职工集合，x表示职工的工资，工资总和就可以用@sum(a:x)来表示。不管这个单位是10个人，100个人人还是1000个人，表达式

6、不变，4）如果要在LINGO模型中输入已经建立的LINDO模型，只要使用importlindofile命令即可；如果要将已经建立的LINGO模型变成LINDO模型，只要使用generate命令即可。也就是说LINDO与LINGO线性模型可以相互转换。鉴于LINGO集合函数的强大功能，下面5个最优化问题实例都是LINGO模型。3最小树问题和模型3.1最小生成树问题在图论中，称无圈的连通图为树。现实中树的例子很多。例如通讯网、电网、自来水管网和暖气供应网都可以看成是树。这些网络的特点一是连通，二是不会形成

7、圈。在一个连通图G中，如果保留全部顶点，并选择适当的边构成一个子图，并且使这个子图是一棵树，则称这个子图为图G的生成树（或支撑树）。连通图G生成树上各边的权数之和称为该生成树的权。连通图G的权数最小的生成树为图G的最小生成树或称最小树。许多实际问题都可以归结为求最小生成树。例如，如何修筑一些公路把若干个城镇连接起来；如何架设通讯网络将若干个地区连接起来；如何修筑水渠将水源和若干块待灌溉的土地连接起来等等。为了说明问题，请看下面的范例1。范例1：假设某电话公司计划在六个村庄架设电话线，各村庄之间的距离如

8、图1所示。试求出使电话线总长度最小的架线方案。图1六个村庄电话线路图103.2最小树模型规定：节点V1表示树根；当两个节点之间没有线路时，规定两个节点之间的距离为M（利用计算机进行求解时换成一个大数，在本例中所有权重之和小于100，可以设M=100）。最小树整数规划模型如下（加重黑线部分根据问题大小做相应调整）：MODEL[1]SETS:[2]CITY/1..6/:;!定义了图1的点集CITY;[3]LINK(CITY,CITY):DIST,X,Y;!定