LINGO在图论中的应用

第2章LINGO在图论和网络模型中的应用 图是一种直观形象地描述已知信息的方式 它使事物之间的关系简洁明了 是分析问题的有用工具 很多实际问题可以用图来描述 一 图的基本概念 图论是以图为研究对象的数学分支 在图论中 图由一些点和点之间的连线所组成 称图中的点为顶点 节点 称连接顶点的没有方向的线段为边 称有方向的线段为弧 所有线段都没有方向的图称为无向图 所有线段都有方向的图称为有向图 既有边也有弧的图称为混合图 点与边相连接称为关联 与边e关联的顶点称为该边的端点 与同一条边关联的两个顶点称为相邻顶点 与同一个顶点关联的边称为相邻边 具有相同顶点的边称为平行边 两个端点重合的边称为环 在无向图中 没有环和平行边的图称为简单图 任意一对顶点都有一条边相连的简单图称为完全图 任意两个顶点之间有且只有一条弧相连的有向图称为竞赛图 在图中 两个顶点u和v之间由顶点和边构成的交错序列 使u和v相通 称为链 通道 没有重复边的通道称为迹 起点与终点重合的通道称为闭通道 不重合的称为开通道 没有重复顶点 必然边也不重复 的开通道称为路 起点与终点重合的路称为圈 回路 如果顶点u和v之间存在通道 称u和v是连通的 任意两个顶点都连通的图称为连通图 无圈的连通图称为树 如果一棵树T包含了图G的所有顶点 称T为G的生成树 如果图G的每条边e都对应一个实数C e 称C e 为该边e的权 称图G为赋权图 通常称赋权的有向图为网络 二 最短路问题 1 动态规划法 1 问题的描述给定N个点Pi i 1 2 n 组成集合 Pi 集合中任一点Pi到另一点Pj的距离用Wij表示 如果Pi到Pj没有弧联结 无通路 则规定Wij 又规定 Wii 0 i 1 2 n 指定一个终点PN 要求从Pi点出发到PN的最短路线 可以用动态规划的方法来求最短路问题 下面举例说明其算法原理 2 算法原理举例 图中A B G表示7个城市 连线表示城市之间有道路相通 连线旁的数字表示道路的长度Wij 现要从城市A到G找出一条最短路线 该问题有三个阶段 第一阶段从A到B或C 第二阶段到D E或F 第三阶段到终点G 我们从终点向前倒过来找 A G F E D C B 2 4 1 2 3 1 3 3 1 3 4 第三阶段 从D E F到G的最短路分别为1 3 4 记为f D 1 f E 3 f F 4 第二阶段 与D E F有连线的出发点为B和C 从B出发分别经过D E F 至终点G的里程分别为 WBD f D 3 1 4WBE f E 3 3 6WBF f F 1 4 5故B到G的最短路是上述三者的最小值 4 可以写成f B min WBj f j 4 j是上一步考察过的三个点D E F 同理f C min WCj f j 而WCD f D 2 1 3WCE f E 3 3 6WCF f F 1 4 5故F C 3 第一阶段 出发点只有一个A 从A出发分别经过B C 至终点G的里程分别为 WAB f B 2 4 6WAC f C 4 3 7故A到G的最短路是上述两者的最小值6 可以写成f A min WAj f j 6 j是上一步考察过的两个点B C 现在已经到了起点 结束运算 从A到G的最短路为6 上述算法可以简写成N是终点 1是起点 j是与i相联 上一步考察过 且与终点相通 f j 为已知的点 编写LINGO程序如下 model sets cities A B C D E F G FL 定义7个城市 roads cities cities A BA CB DB EB FC DC EC FD GE GF G W P 定义哪些城市之间有路相联 W为里程 P用来存放最短路的路径 endsets data W 24331231134 enddataN SIZE CITIES FL N 0 终点的F值为0 for cities i i lt N FL i min roads i j W i j FL j 递推计算各城市F值 显然 如果P i j 1 则点i到点n的最短路径的第一步是i j 否则就不是 由此 我们就可方便的确定出最短路径 for roads i j P i j if FL i eq W i j FL j 1 0 end 部分计算结果 FL A 6FL B 4FL C 3FL D 1FL E 3FL F 4FL G 0最短路线为ABDG以上计算程序是通用程序 对其它图 只需在此程序基础上对数据作一些修改即可 程序中的语句roads cities cities A BA CB DB EB FC DC EC FD GE GF G W P 定义的集合称为稀疏集合 本例中cities有7个成员 但是并非每个城市到其它6个城市都有路相通 只有部分城市之间有路 故定义衍生集合roads时用列举法列出有路相通的每对城市 2 0 1规划法用0 1规划法也能求解最短路问题 其思路如下 设起点为1 终点为n 引入0 1型决策变量Xij 如果弧 i j 在最短路上 则Xij 1 否则Xij 0 对于除了起点1和终点n以外的任意一个顶点i 如果 说明从i出发的所有弧中必然有一条弧在最短路上 也就是说最短路经过该顶点 此时所有从其它顶点到达该顶点的弧中必然也有一条弧在最短路上 因而必有 如果 说明最短路不经过顶点i 故必有两种情况可以合并写成 对于起点1 则必然满足 对于终点n 则必有 目标函数是最短路上的各条弧的长度之和 总里程 最小 于是最短路问题可以用如下0 1规划来描述 式中表示全体边的集合 对于上例 编写LINGO程序如下 model sets cities A B C D E F G 定义7个城市 roads cities cities A BA CB DB EB FC DC EC FD GE GF G W X 定义哪些城市之间有路相联 W为里程 X为0 1型决策变量 endsetsdata W 24331231134 enddata N SIZE CITIES MIN SUM roads W X FOR cities i i GT 1 AND i LT N SUM roads i j X i j SUM roads j i X j i SUM roads i j i EQ 1 X i j 1 SUM roads i j j EQ N X i j 1 end 计算结果与动态规划法相同 程序中的最后一个约束方程可以去掉 因为有了前面两个约束条件 共n 1个约束方程 可以导出最后一个约束方程 即终点的约束方程与前面n 1个约束方程线性相关 保留该约束方程 LINGO求解时也不会产生任何问题 因为LINGO会自动删除多余的方程 该方法与前面的方法相比 灵活性稍差 它一次只能求出指定起点到指定终点的最短路 如果更改起点 则必须改动程序然后重新求解 三 旅行售货商模型 旅行售货商问题 又称货郎担问题 TravelingSalesmanProblem简称TSP模型 是运筹学的一个著名命题 模型 有一个推销商 从某个城市出发 要遍访若干城市各一次且仅一次 最后返回出发城市 已知从城市i到j的旅费为Cij 问他应按怎样的次序访问这些城市 使得总旅费最少 称能到每个城市一次且仅一次的路线为一个巡回 圈 TSP是典型的组合优化问题 也是公认的NP完全难题 不算出发地 n个城市有 n 1 种排列方法 每一种旅行路线是排列中的一种 当n变大时 计算量呈指数增长 穷举法所费时间是难以承受的 为此 多年以来有许多人研究了一些近似算法 我们把TSP问题转化为0 1规划 然后用LINGO来求解 1 方法一 判断各边是否包含在旅行路线中引入0 1整数变量xij 且i j xij 1表示路线从i到j 即边i j在旅行路线中 而xij 0则表示不走i j路线目标函数首先必须满足约束条件 对每个城市访问一次且仅一次 从城市i出发一次 到其它城市去 表示为 引入0 1整数变量xij 且i j xij 1表示路线从i到j xij 0则表示不走i j路线目标函数首先必须满足约束条件 对每个城市访问一次且仅一次 从城市i出发一次 到其它城市去 表示为从某个城市到达j一次且仅一次 表示为 以上建立的模型类似于指派问题的模型 对TSP问题只是必要条件 并不充分 例如 用图示路线连接六个城市 满足以上两个约束条件 但这样的路线出现了两个子回路 两者之间不通 不构成整体巡回路线 为此需要考虑增加充分的约束条件以避免产生子巡回 下面介绍一种方法 增加变量ui i 2 3 n 它的大小可以取整数 例如从起点出发所达到的城市u 2 依此类推 附加约束条件 ui uj nxij n 1 i 1 n j 2 n 且i j 下面证明 1 任何含子巡回的路线都必然不满足该约束条件 不管ui如何取值 2 全部不含子巡回的整体巡回路线都可以满足该约束条件 只要ui取适当值 用反证法证明 1 假设存在子巡回 则至少有两个子巡回 那么 必然 至少有一个子巡回中不含起点城市1 如上图中的4 5 6 4 则必有u4 u5 n n 1 u5 u6 n n 1 u6 u4 n n 1 把这三个不等式加起来得到n n 1 不可能 故假设不能成立 而对整体巡回 因为附加约束中j 2 不包含起点城市1 故不会发生矛盾 对于整体巡回路线 只要ui取适当值 都可以满足该约束条件 对于总巡回上的边 xij 1 ui可取访问城市i的顺序数 则必有ui uj 1 约束条件ui uj nxij n 1变成 1 n n 1 必然成立 对于非总巡回上的边 因为xij 0 约束条件ui uj nxij n 1变成 1 n 1 肯定成立 综上所述 该约束条件只限止子巡回 不影响其它 于是TSP问题转化成了一个混合整数线性规划问题 TSP问题可以表示为规划 TSP问题的LINGO模型 旅行售货员问题 model sets city 1 6 u 定义6个城市 link city city dist 距离矩阵 x 决策变量 endsetsn size city data 距离矩阵 dist 070245484223961196702032410932136764454324011372180798842109311370161618572396213621801616029001196764798185729000 这里可改为你要解决的问题的数据 enddata 目标函数 min sum link dist x FOR city K 进入城市K sum city I I ne K x I K 1 离开城市K sum city J J ne K x K J 1 保证不出现子圈 for city I I gt 1 for city J J gt 1 and I ne J u I u J n x I J n 1 限制u的范围以加速模型的求解 保证所加限制并不排除掉TSP问题的最优解 for city I u I n 1 for link bin x 定义X为0 1变量 end 计算结果 目标函数值 6610路线 1 3 6 2 5 4 1 2 方法二 对城市排序 找出最优排序在现实中的城市交通图中 有些城市之间有直接道路 有些则没有 如果两点之间没有直接的通路 则两点之间的距离取最短路 经过其它点 即用任意两点之间的最短路Cij作为图的距离矩阵 于是该图可以看成是一个完全图 即任意一对顶点都有一条边相连的图 此时形式上的环形巡回路线实际上个别点有可能不止经过一次 设某个城市为旅行的出发地和终点 相当于总部所在地 旅行者从该城市出发到其它n个城市各一次且仅一次 最后回到出发地 我们把行进路线分成n步 每一步到一个城市 第n 1步返回出发地 于是一条旅行路线就相当于n个城市的一种排列 n个城市共有n 种排列方式 排序不同则总里程 或费用 可能不同 总里程 或总费用 最小的排序就是我们要寻找的最优路线 引入0 1型决策变量Xkj 下标k表示旅行的步数 下标j表示到达哪一个城市 Xkj 1表示旅行者第k个目的地 到达点 是城市j Xkj 0则表示否 用lj表示总部到各城市的距离 用Cij表示城市i与城市j之间的最短路 从出发地到第1个点的路程为从最后一个点返回出发地的里程为 假设在第k步邮车达到城市i 在第k 1步达到支局j 即Xki Xk 1 j 1 则走过的里程为 Cij Xki Xk 1 j从第1点到第n点走过的总里程为目标函数为 约束条件有以下2条 1 每一步到达一个城市 即 2 每一个城市必须到一次且只需一次 即 综上所述 可以把TSP问题转化成如下非线性0 1规划 以上规划种允许包含其它约束条件 用LINGO可以求解该规划 举例如下 某县邮局和10个乡镇支局组成该县的邮政运输网络 已知县局到各支局的距离和支局之间的距离矩阵 数据在程序中 用一辆邮车完成邮件运输任务 邮车从县局出发到各支局去一次且只需一次 最后回到县局 求总路程最短的行驶路线 编写LINGO程序如下 MODEL SETS CITY 1 10 JL STEP 1 10 LINE STEP CITY X LINKS CITY CITY C ENDSETS DATA JL 71 56 27 30 28 26 15 9 30 27 C 0 15 44 47 64 83 86 75 93 9815 0 29 32 49 68 71 60 78 8344 29 0 20 37 53 42 31 49 5447 32 20 0 17 36 42 39 60 5764 49 37 17 0 19 37 37 58 5583 68 53 36 19 0 18 35 56 4786 71 42 42 37 18 0 24 38 2975 60 31 39 37 35 24 0 21 2693 78 49 60 58 56 38 21 0 2998 83 54 57 55 47 29 26 29 0 ENDDATA FOR LINE BIN X M1 SIZE STEP FOR CITY I SUM STEP N X N I 1 FOR STEP N SUM CITY I X N I 1 L1 SUM CITY I X 1 I X M1 I JL I LX SUM STEP N N LT M1 SUM LINKS I J C I J X N I X N 1 J MIN L1 LX END 在程序运行前需要对LINGO的参数作必要的设置 对于非线性规划 LINGO提供两种求解方法 一种是 GlobalSolver 称为全局优化求解器 另一种是 MultistartSolver 称为多起点算法 全局优化求解器优点是确保找到全局最优解 缺点是有时需要较长运行时间 多起点算法的优点是节省运行时间 但不能保证找到的解就是全局最优解 多设置起点数往往找到的解就是全局最优解 点击菜单 Options 再打开全局优化求解器 GlobalSolver 选项 可以选或不选 GlobalSolver 当选择多起点算法 MultistartSolver 时 需要设置起点数 若选择 SolverDecides 表示由LINGO决定 对以上程序 我们选择 GlobalSolver 点击菜单 Options 在全局优化求解器 GlobalSolver 选项框内打 再点击 确定 运行以上程序 费时4分多钟 得到最优解 目标函数值 总路程 260公里邮车的行驶路线为 县局 8 9 10 7 6 5 4 1 2 3 县局 3 多旅行商问题在现实中问题中 有时候不是由一人走遍所有点 而是由几个人分工合作 每个人只到其中部分城市 每个点都有人来过一次且只需一次 事先不指定谁到哪些点 求出使总路程最小的旅行规划 每个人的行走路线 例如邮路规划中 为了在允许的时间内完成邮件运输任务 县局的邮车往往不止1辆 而是用若干辆邮车分工运输 只要保证每个支局有邮车来过即可 为了节省行驶费用 需要规划几辆邮车的最佳路线 这就是多旅行商问题 多旅行商问题的提法如下 有n 1个城市 相互间的路程 或旅行费用 为已知 有k个旅行商都从总部所在城市出发 赴其它城市旅行推销 分工遍历其余n个城市 即每个城市各有任意一名旅行商来过一次且仅一次 最后都回到出发地 目标是总路程最短或总费用最省 多旅行商问题在物流配送 邮路优化等方面具有较高的实用价值 而在现实问题中 研究对象往往不是单纯的旅行商问题 而要考虑各种约束条件 例如时间约束 载重量约束等等 研究这一类带约束条件的多旅行商问题具有很强的现实意义 在现实的多旅行商问题中 往往带有约束条件 例如时间约束 载重量约束等等 带约束条件的多旅行商问题具有广泛现实意义 且是极具挑战性的难题 我们仍然把它转化为0 1非线性规划并编成LINGO程序来求解 实例某县邮政局管辖16个支局 已知县局到各支局的距离以及16个支局之间的距离矩阵 寄达各支局和各支局收寄的邮件 袋 如下表所示 县邮局和各支局分布图 每一辆邮车最多装载65袋邮件 邮车的运行成本为3元 公里 试用最少邮车 并规划邮车的行驶路线使总费用最省 分析 首先考虑最少邮车数量 由题目所给表中数据 寄达16个支局的邮件总数为176袋 从各支局收寄的邮件总数为170袋 每一辆邮车最多容纳65袋邮件 至少需要176 65 2 7辆邮车 由于邮车数量为整数 故最少需要3辆邮车 如果3辆邮车能够完成邮件运输任务 则3辆车就是邮车数量的最优解 运输费用与行驶里程成正比 总里程最短对应总费用最省 把16个支局放在一起作为一个整体考虑 找出3条邮路 每条邮路都从县局出发 到若干支局进行卸装 最后回到县局 各邮车路过的支局数量未知 合理安排各邮车的行驶路线 由3辆邮车分别承包运输 在满足运载量约束前提下 把3条巡回路线的总里程最小作为优化的目标 该问题相当于附带约束条件的多旅行商模型 引入0 1型决策变量Xkj Ykj Zkj 分别表示3辆邮车第k步到达支局j 下标k表示邮车行走的步数 下标j表示到达哪一个支局 当决策变量Xkj Ykj Zkj等于1时分别表示某邮车第k个装卸点是支局j 等于0时表示否 设各邮车管辖的支局数量分别为m1 m2 m3 则m1 m2 m3 16 约束条件有以下3条 1 任何一辆车在任何一步到达一个支局 即 2 任何一个支局必须有一辆邮车到达一次且只需要一次 即 3 在邮车行进的任何路段上 装载的邮件不超过65袋 设寄达各支局的邮件量为Pj 各支局收寄的邮件量为Qj 装载量是动态变化的 以第1辆邮车为例 出发时的装载量为 到第1个支局卸装以后 装载量变为在行驶过程中 装载量的递推公式为约束条件为 综上所述 建立多旅行商问题的0 1规划模型如下 装载量的计算公式为 编写LINGO程序如下 MODEL SETS STATION 1 16 JL P Q STEPX 1 6 WX STEPY 1 5 WY STEPZ 1 5 WZ LINEX STEPX STATION X LINEY STEPY STATION Y LINEZ STEPZ STATION Z LINKS STATION STATION C ENDSETS DATA JL 27361711243144403020252121182736 P 10 15 6 9 13 6 11 4 13 17 11 2 11 21 13 14 Q 9 14 5 10 9 10 13 9 15 9 6 7 13 15 10 16 C 0312738515871675747524821415261310193327324564534761575248566327190142734474939294238382938443833140132033352515333232152430512727130921372626434545282938583234209013323235475252353342714547332113019303950656548444067644935373219011203154613425215753392526323011010204351241413474729152635392010018364114918 526142334347503120180234625142348573832455265544336230272233422152383245526561514146270394857414829152835483424142522390112052563824293344251491433481109616344303842402113182342572090 ENDDATA FOR LINEX BIN X FOR LINEY BIN Y FOR LINEZ BIN Z M1 SIZE STEPX M2 SIZE STEPY M3 SIZE STEPZ FOR STATION I SUM STEPX N X N I SUM STEPY N Y N I SUM STEPZ N Z N I 1 FOR STEPX N SUM STATION I X N I 1 FOR STEPY N SUM STATION I Y N I 1 FOR STEPZ N SUM STATION I Z N I 1 WX0 SUM STATION I P SUM STEPX N X N I WY0 SUM STATION I P SUM STEPY N Y N I WZ0 SUM STATION I P SUM STEPZ N Z N I WX 1 WX0 SUM STATION J P J Q J X 1 J WY 1 WY0 SUM STATION J P J Q J Y 1 J WZ 1 WZ0 SUM STATION J P J Q J Z 1 J FOR STEPX N N GE 2 WX N WX N 1 SUM STATION J P J Q J X N J FOR STEPY N N GE 2 WY N WY N 1 SUM STATION J P J Q J Y N J FOR STEPZ N N GE 2 WZ N WZ N 1 SUM STATION J P J Q J Z N J WX0 65 WY0 65 WZ0 65 FOR STEPX N WX N 65 FOR STEPY N WY N 65 FOR STEPZ N WZ N 65 L1 SUM STATION I X 1 I X M1 I JL I L2 SUM STATION I Y 1 I Y M2 I JL I L3 SUM STATION I Z 1 I Z M3 I JL I LX SUM STEPX N N LT M1 SUM LINKS I J C I J X N I X N 1 J LY SUM STEPY N N LT M2 SUM LINKS I J C I J Y N I Y N 1 J LZ SUM STEPZ N N LT M3 SUM LINKS I J C I J Z N I Z N 1 J MIN L1 L2 L3 LX LY LZ END 三辆邮车各自负责的支局数量有若干种分配方法 例如有6 5 5 6 6 4 7 5 4等不同分组法 经过试验 以6 5 5方案最优 目标函数值 3条邮路的总里程 为343km 第一条邮路 县局 10 9 8 7 5 6 县局 总里程121km 沿途各段邮件的装载量为64 56 58 63 65 61 65袋 注意 如果支局5和6的先后次序倒过来 即走7 6 5 县局 则里程为106km 减少15km 但是在支局6卸装以后 邮件达69袋 超过了装载量约束 看来先到支局5 后到支局6是因为避免超载的原因 被迫绕路 整体上仍然保持最优 第二条邮路 县局 14 15 16 11 12 县局 总里程105km 沿途各段邮件的装载量为61 55 52 54 49 54袋 第三条邮路 县局 13 1 2 3 4 县局 总里程117km 沿途各段邮件的装载量为51 53 52 51 50 51袋 三条邮路的图形如图所示 四 最小生成树和最优连线 问题的提出 要建造一个连接若干城市的通讯网络 已知城市i与j之间架设通讯线路所需费用为cij 请设计一个既能使所有城市都能接通 又使总费用最小的的方案 在图论中 连通并且无圈的无向图称为树 设G是具有n个顶点的无向连通图 则G是树的充分必要条件是G有n 1条边 若T是包含G的全部顶点的子图 它又是树 则称T是G的生成树 如果图的边有权 对应于边的实数 则权的和最小的生成树称为最小生成树 最优连线就是寻找图的最小生成树 MinimalSpanningTree 简称MST 许多实际问题都可以归结为最小生成树 例如 如何修筑一些公路把若干个城镇连接起来 如何架设通讯网络将若干个地区连接起来 如何修筑水渠将水源和若干块待灌溉的土地连接起来等等 为了说明问题 以下面的问题作为范例 范例 假设某电力公司计划在七个村庄架设电线 各村庄之间的距离如图所示 试求出使电线总长度最小的架线方案 节点1表示树根 点i到点j的距离用Cij表示 当两个节点之间没有线路相通时 两点之间距离用M 很大的实数 表示 引入0 1整数变量xij xij 1 且i j 表示从i到j的边在树中 xij 0则表示边不在树中 目标函数约束条件 1 除树根外每个点都有线路通到 且只需要一次 表示为 2 至少有一条线路从1出来 以上约束条件是必要条件 但不充分 类似于TSP问题 增加一个变量u 再附加约束条件 1 限制uj的取值范围为 u1 0 1 uj n 1 j 2 3 n 用以下不等式可以达到目的 uj 1且uj n 1 n 2 x1j j 1 2 如果线路从j到k 则uk uj 1 且避免来回重复和圈 约束条件为 uj uk xkj n 2 1 xkj n 3 xjk 1 k n 2 j nj k 最优连线 最小生成树 转化为混合整数规划 编写LINGO程序如下 MODEL sets city 1 7 u 定义7个城市 link city city dist x 距离矩阵和决策变量 endsetsn size city data dist是距离矩阵 dist 034710010010030324100100430100571007210002100610045201410010071001021001001006420 这里可改为你要解决的问题的数据 enddata min sum link dist x 目标函数 U 1 0 for link bin x 定义X为0 1变量 FOR city K K GT 1 sum city I I ne K x I K 1 for city J J gt 1 and J ne K u J u K X K J N 2 1 X K J N 3 X J K sum city J J GT 1 x 1 J 1 for city K K gt 1 U K 1 U K N 1 N 2 X 1 K end 计算结果 目标函数值 最优连线的长度 为13 最优连线的构成如图所示 五 最大流问题 1 问题的描述设有一批物资 要从A市通过公路网络 内含一些中转站 运往B市 已知每段公路的运输能力有限制 流量限制 问应如何安排运输方案 才能使总运量最大 这就是网络最大流问题 例 下图是从发货地 到目的地 的有向运输网络 称点 为发点 源 点 为收点 汇 有向边 弧 旁边的数字是该弧的流量 运输能力 限制 求 的最大流 2 数学模型 对每一条弧 顶点i到j 定义f i j 为该弧上从顶点i到顶点j的流量 用Cij表