日志
单源最短路径数学表达式-线性规划模型
|
--备忘--
简单的示例，如何建立约束条件，利用一般的规划软件处理问题。
线性规划模型以最短路径问题为例：
对上面边界条件的理解应为：
1、以顶点的角度来分析每条路线上各弧的关系
2、对于顶点（非1和n）来说，每一条路径上，进入该顶点的弧的数量等于1，从该顶点出去的弧的数量为1，
3、对于顶点1来说，每一条路径上，限定进入该顶点的弧的数量为0，同时从该顶点出去的弧的数量为1，
4、对于顶点n来说，每一条路径上，进入该顶点的弧的数量为1，并限定从该顶点出去的弧的数量为0。
5、通过2、3和4的约制，可以让模型在构建每条路径时，非回路，且一定以顶点1和n作为起点和终点。
6、注意进出边的标记形式。
7、无向图是增加一个约束条件：
与有向图相比较，从顶点1 离开后，再不能回到该顶点。
利用lingo软件很容易建立该模型，并求解。
已同步至 风树的微博
