Lingo 稠密与稀疏集合 0/1 规划

Lingo-稠密集合与稀疏集合分析

1.研究背景与概述

将派生集合 MATCH 的组成元素界定为 DEMAND 与 SUPPLY 两者的笛卡儿积，此类派生集合被称作稠密集合，简称为稠集。实际上，在 LINGO 系统中，派生集合的成员可以仅为该笛卡儿积的一个真子集，此类派生集合则被称为稀疏集合，简称为疏集。

1.例题解析与应用

最短路径问题 在错综复杂的道路网络中，运输车辆驾驶员通常期望寻找到一条连接两个城市之间的最优行驶路线。如图4-17所示，该图示反映了所研究的公路网络结构，其中各节点代表货车可停靠的城镇，而弧线上的数值则表示相邻城市间的距离（单位为百公里）。现假设货车需从起点城市S出发，最终抵达终点城市T，那么应当如何规划行驶路径，以确保全程行驶距离达到最小值？

1.3分析：

【若从S至T的最短行驶路径P途经城市C1，则P中由S至C1的路径必为S到C1的最短行驶路线；若P经过城市C2，则P中由S至C2的部分也必定是S到C2的最优行驶路线。因此，为获取从S到T的最优行驶路径，只需先求得从S到Ck（k=1,2）的最优行驶路线