仓储及运输系统规划.ppt

【例6.1】已知起点A与终点G之间有节点B，C，D，E，F，它们共同构成一运输网络，如图6.1所示，途中标明了各节点间的距离。求A到G的最短运输路线。 补充 * 解：使用标号法： （0，S） （A，50） （A，52） （C，82） （B，83） （B，108） （F，116） 补充 * （2）起终点相同——周游路径问题 这类问题主要指从设施点出发访问一定数量顾客后又回到原来的出发点的线路确定问题，即运筹学中常见的旅行商（TSP）问题，其目标是确定回到出发点前服务顾客的次序，使总旅行距离最小。通常的数学模型为： 式中：Cij表示旅行商经过对应路段（i，j）所花费用；决策变量Xij表示如果路段（i，j）在路线上，其值为1，否则为0。 补充 * 通常采用简单贪婪算法，其步骤如下： 选择距出发点最近的顾客位置 再从没有选择的位置中选距离当前已选择的位置最近的顾客位置 如果所有位置都选了便停止，否则回到第二步 补充 * 【例6.2】一奶厂从站点A送奶，服务3个顾客B，C，D，从站点A到3个顾客的距离如表6.1所示，确定最优的送奶路线。 解：①B距A最近。 ② C距B最近。 ③只剩D没选，D即为继C之后的顾客，然后返回A。 ?求出的配送顺序为A—B—C—D—A。 节点 A B C D A 22 31 45 B 22 18 27 C 31 18 38 D 45 27 38 补充 * 邮递员问题 若把它抽象为图的语言，就是给定一个连通图。在每边ei上赋予一个非负的权w（ei），要求一个圈（未必是简单的），并使圈的总权数最小。这个问题是我国的管梅谷同志在1962年提出的，因此在国际上统称为中国邮递员问题。 求解这个问题的方法被称为奇偶点图上作业法。 奇偶点图上作业法算法口诀： 先分奇偶点，奇点对对联； 联线不重迭，重迭要改变； 圈上联线长，不得过半圈。 补充 * 中国邮递员问题也可以表示为：在一个有奇点的连通图中。要求增加一些重复边，使得新的连通图不含有奇点，并且增加的重复边总权最小。 我们把增加重复边后不含奇点的新的连通图叫做邮递路线，而总权最小的邮递路线叫做最优邮递路线。 下面我们来介绍初始邮递路线的确定，改进，以及一个邮递路线是否是最优路线的判定标准的方法-----图上作业法。 补充 * （一）初始邮递路线的确定方法 由于任何一个图中，奇点的个数为偶数，所以如果一个连通图有奇点，就可以把它们两两配成对，而每对奇点之间必有一条链（图是连通的），我们把这条链的所有边作为重复边追加到图中去，这样得到的新连通图必无奇点，这就给出了初始投递路线。 例如，在图1中，v1是邮局所在地，并有四个奇点v2,v4,v6,v8,将它们两两配对，比如v2和v4为一对，v6和v8为一对。 补充 * 图 1 补充 * 在连接v2和v4的链中任取一条，比如链（v2,v1,v8,v7,v6,v5,v4）,在加入重复边[v2,v1],[v1,v8],[v8,v7],[v7,v6],[v6,v5],[v5,v4]。 同样，任取连接v6和v8的一条链(v8,v1,v2,v3,v4,v5,v6),在加入重复边[v8,v1],[v1,v2],[v2,v3],[v3,v4],[v4,v5],[v5,v6].于是，得到图2。 补充 * 图 2 在连通图2中，没有奇点，故它是欧拉图。对于这条邮递路线，重复边的总长为:2W12+W23+W34+2W45+2W56+W67+W78+2W18=51。 补充 * （二）改进邮递路线，使重复边的总长不断减少。 从图2中可以看出，在边[v1,v2]旁边有两条重复边，但是如果把他们都从图中去掉，所得到的连通图仍然无奇点，还是一个邮递路线，而总长度却有所减少。同理，在边[v1,v8],[v4,v5],[v5,v6]旁边的重复边也是一样的。 一般地，在邮递路线上，如果在边[vi,vj]旁边有两条以上的重复边，从中去掉偶数条，那么可以得到一个总长度较少的邮递路线。 补充 * 判定标准1：在最优邮递路线上，图中的每一条边至多有一条重复边。 按此判定标准，将图2改为图3，这时重复边的总权减少为21。 图 3 补充 * 判定标准2。在最优邮递路线上，图中每一个圈的重复边的总权小于或者等于该圈总权的一半。 在图3中，圈（v2,v3,v4,v9,v2）的总权为24，但圈上重复边的总权为14，大于该圈总权的一半。因此作一次改进，在该圈上去掉重复边[v2,v3],[v3,v4],加上重复边[v2,v9],[v9,v4]，如图4所示。这时重复边的总权减少为10。 图 4 补充 * 在图4中，圈(v1,v2,v9,v6,v7,v8,v1)中重复边总权为13，而该圈的总权为24，不满足