20 16
图 16
从图 14 可以看出，此时目标函数值的下界（Obj Bound=85.2638）与目前得到的最好的可行解 的目标函数值（Best Obj=85.2661）相差已经非常小，可以认为已经得到了全局最优解。 部分结果
见图 15，这就可以认为是我们模型的最后结果。在图 16 中，我们可以画出料场和工地的位置示意
图，其中标有―*‖号的是料场，标有―+‖号的是工地。
我们还可以指出：如果要把料厂 P(5, 1), Q (2, 7)的位置看成是已知并且固定的，这时是 LP 模型。 只需要在图 13 中把初始段的―X Y =5，1，2，7；‖语句移到数据段就可以了。此时，运行结果告
诉我们得到全局最优解（变量 C 的取值这里略去），最小运量 136.2275(吨公里)。
13
Page 14 3．3．3 稠密集合与稀疏集合
上节我们介绍了在 LINGO 中可以定义和使用两类集合：基本集合和派生集合。前面的例子中 我们把派生集合 MATCH 的元素定义为 DEMAND 和 SUPPLY 的笛卡儿积，这种派生集合称为稠密
集合（简称稠集）。其实在 LINGO 中，派生集合的元素可以只是这个笛卡儿积的一个真子集合，
这种派生集合称为稀疏集合（简称疏集）。下面我们通过一个例子来说明。
最短路问题 在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一个城市的最短 路. 假设图 17 表示的是该公路网, 节点表示货车可以停靠的城市,弧上的权表示两个城市之间的距
离（百公里）. 那么,货车从城市 S 出发到达城市 T,如何选择行驶路线,使所经过的路程最短? A
1
6 6 6 5 B
1
C
1
5 8 7 S 3 A
2
T 6 8 3 7 B
2
C
2
6 A
3
4 9
图 17 最短路问题的例子
假设从S到T的最优行驶路线 P 经过城市C
1
, 则P中从S到C
1
的子路也一定是从S到C
1
的最优行
驶路线; 假设 P 经过城市C
2
, 则P中从S到C
2
的子路也一定是从S到C
2
的最优行驶路线. 因此, 为了
得到从S到T的最优行驶路线, 我们只需要先求出从S到C
k
(k=1,2)的最优行驶路线, 就可以方便地得
到从S到T的最优行驶路线. 同样,为了求出从S到C
k
(k=1,2)的最优行驶路线, 只需要先求出从S到 B
j
(j=1,2)的最优行驶路线; 为了求出从S到B
j
(j=1,2)的最优行驶路线, 只需要先求出从S到A
i
(i=1,2,3)
的最优行驶路线. 而S到A
i
(i=1,2,3)的最优行驶路线是很容易得到的(实际上, 此例中S到A
i
(i=1,2,3)只 有唯一的道路).
也就是说,此例中我们可以把从S到T的行驶过程分成 4 个阶段,即 S→A
i
(i=1,2 或 3), A
i
→ B
j
(j=1 或 2), B
j
→ C
k
(k=1 或 2), C
k
→ T. 记d(Y,X)为城市Y与城市X之间的直接距离（若这两个城市之间没
有道路直接相连，则可以认为直接距离为无穷大），用L(X)表示城市S到城市X的最优行驶路线的路 长, 则: L(S)=0;
S X X Y d Y L X L
X Y
≠ + =
≠
)}, , ( ) ( { min
) (
对本例的具体问题，可以直接计算如下： L(A
1
)=6, L(A
2
)=3, L(A
3
)=3; L(B
1
)=min{ L(A
1
)+6, L(A
2
)+8, L(A
3
)+7}= 10 = L(A
3
)+7, L(B
2
)=min{ L(A
1
)+5, L(A
2
)+6, L(A
3
)+4}= 7 = L(A
3
)+4; L(C
1
)=min{ L(B
1
)+6, L(B
2
)+8}= 15 = L(B
2
)+8, L(C
2
)=min{ L(B
1
)+7, L(B
2
)+9}= 16 = L(B
2
)+9;
L(T)=min{ L(C
1
)+5, L(C
2
)+6}= 20 = L(C
1
)+5.
所以, 从S到T的最优行驶路线的路长为 20. 进一步分析以上求解过程, 可以得到从S到T的最优
行驶路线为S→ A
3
→ B
2
→ C
1
→ T.
上面这种计算方法在数学上称为动态规划（Dynamic Programming）. 动态规划也是最优化的一 个分之。
作为一个例子，我们用 LINGO 来解这个最短路问题。我们可以编写如图 18 的 LINGO 程序。 集合段定义的 CITIES 是一个基本集合（元素通过枚举给出），L 是其对应的属性变量（我们要求的
最短路长）；ROADS 是由 CITIES 导出的一个派生集合（请特别注意其用法），由于只有一部分城市
之间有道路相连，所以我们进一步将其元素通过枚举给出，这就是一个稀疏集合。D 是 ROADS 对
应的属性变量（给定的距离）。
14
Page 15 图 18
从模型中还可以看出：这个 LINGO 程序可以没有目标函数，这在 LINGO 中是允许的，可以用
来找可行解（解方程组和不等式组）。此外，在数据段我们对 L 进行了赋值，但只有 L（S）=0 是已
知的，所以后面的值为空（但位置必须留出来，即逗号―，‖一个也不能少，否则会出错）。如果这
个语句直接写成―L=0；‖，语法上看也是对的，但其含义是 L 所有元素的取值全部为 0，所以也会
与题意不符。