LINGO软件的基本使用方法 - 图文

图3-7 例3.4的模型窗口

表示集合link中的元素就是集合demand和supply就是的元素组合成的有序二元组，从数学上看link就是demand和supply的笛卡积，也就是说 link?{(s,t)|s?DEMAND,t?supply}

因此，其属性c也就是一个6?2的矩阵（或者说是含有12个元素的二维数组）。

正是由于这种表示方式与矩阵的表示非常类似，LINGO建模语言也称为矩阵生成器（matrix generator）。类似于demand和suply这种直接把元素列举出来的集合称为基本集合（primary set，也称为“原始集合”），而把link这种基于其他集合而派生出来的二维或多维集合称为派生集合（derived set 也为“导出集合”）。由于demand和supply生成派生集合link的父集合。

本模型中数据段的含义也是容易理解的。本模型中还包括了初始段，请特别注意其中“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.25; 请注意我们前面说过,这时分割数据的空格与逗号“，”或“回车”的作用是等价的。 程序接下来定义目标约束，与前面例3。3中的方法是类似的（但这里包含了派生集合），请特别注意进一步体会集合函数@SUM和@FOR的用法.由于新建料场的位置理论上讲可以是任意的,所以我们在约束的最后(模型的“END”语句上面的一行)用@free函数取消了变量x,y的非负限制。此外，我们在程序开头用Title语句对这个模型取了一个标题“Location Problem”（见模型开始的“MODEL：”下面一行）；并且对目标行（[OBJ]）和两类约束（DEMAND-CON、SUPPLY-CON）分别进行了命名（请特别注意这里命名的特点）。

大家仔细阅读、理解了图3-17的程序后，现在就可以运行菜单命令“LINGO|Solve”，很快得到解答报告（显示界面略，请特别注意结果中的约束条件（行名）也好似有下标的）：局部最优解x(1)=7.249997,x(2)=5.695940,y(1)=7.749998,y(2)=4.928524,c(略)，最小运量=89.8835（t?km）。

现在我们来看看对于这个问题的NLP模型，最小运量89.8835是不是全局最优解。我们考虑用全局最优求解器，求解图3-17中的模型（如果你使用的是试用版软件，则可能不能用全局最优求解器求解本例，因为问题规模已经太大了）。激活全局最优求解程序的方法，

17

是用“LINGO|Options”菜单命令打开选项对话框，在“Global Solver”选项卡上选择“Use Global Solver”（我们将在后面介绍“LINGO|Options”菜单命令的具体用法）。全局最优求解程序花费的时间可能是很长的，所以为了减少计算工作量，我们对x,y的取值再做一些限制。虽然理论上新建料场的位置可以是任意的，但我们可以很直观地想到，最佳的料场位置不应该离工地太远，无论如何至少不应该超出现在6个工地所决定的坐标的最大、最小值决定的矩形之外，即：0.5〈=x<=8.75,0.75<=y<=7.75。可以用@bnb函数加上这个条件取代模型END上面的行，运行NLP模型，发现全局最优求解程序花费的时间仍然很长，图3-18是运行27分35秒时人为终止求解（按下“Interrupt Solver”按钮）时对应的求解状态窗口。

图3-18 例3.4的模型窗口和全局求解器的状态窗口

从图3-18可以看出，此时目标函数值的下界（Obj Bound=85.2638）与目前得到的最好的可行解的目标函数值（Best=85.2661）相差已经非常小，可以认为已经得到了全局最优解。部分结果见图3-19，这就可以认为是我们模型的最后结果。在图3-20中，我们可以画出料场和工地的位置示意图，其中标有“*”号的是料场，标有“+”号的是工地。

18

图3-19 例3.4计算结果

图3-20 工地与料场示意图

我们还可以指出：如果要把料场P（5，1），Q（2，7）的位置看成是已知并且固定的，这时LP模型。只需要在图3-17中把初阶段的“x,y=5,1,2,7；”语句移到数据段就可以了。此时，运行结果告诉我们得到全局最优解（变量c的取值这里略去），最小运量136.2275（t?km）。请读者自己不妨一试。

3.2.3 稠密集合与稀疏集合

在3.2.3节我们介绍了在LINGO中可以定义和使用两类集合：基本集合和派生集合。前面的例子中我们把派生集合link的元素定义为demand和supply的笛卡儿积，即包含了两个基本集合构成的所有二元有序对。这种派生集合称为稠密集合（简称稠集）。有时候，在实际问题中，一些属性（数组）可能只在笛卡儿积的一个真子集合上定义，而不是在整个稠集上

19

定义，LINGO能不能做到这一点呢？

答案是肯定的。其实，在LINGO中，派生集合的元素可以定义为只是这个笛卡儿积的一个真子集合，这种派生集合称为稀疏集合（简称疏集）。下面我们通过一个例子来说明。 例3.5（最短路问题） 在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一个城市的最短路。假设图3-21表示的是该公路网，节点表示货车可以停靠的城市，弧上的权表示两个城市之间的距离（百公里）。那么，货车从城市S出发到达城市，如何选择行驶路线，使所经过的路程最短？

图3-21 最短路问题的例子

假设从 S到T的最优行驶路线P经过城市C1，则P中从 S到C1的子路也一定是从S到C1的最优行驶路线；假设P经过城市C2，则P中从 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）的最优行驶路线.而从Ai（i=1，2）的最优行驶路线是很容易得到的（实际上，此例中S到Ai（i=1，2，3）只有唯一的道路）。

也就是说，此例中我们可以把从 S到T的行驶过程分成4个阶段，即S到Ai（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的最优行驶路线的路长，则有

L(S)?0;??????????（12）L(X)?minY?X{L(Y)?d(Y,X)},X?S??????（13）

对于本例的具体问题，可以直接计算如下：

20