第12章货物运输的优化求解概念.ppt

* 现 代 物 流 学 * 已知5用户间距离如表，其中d(i,j)=∞表示从第i个用户到第j个用户是没有意义的，用户1为物流网点所在位置，如果只考虑将每个用户都当作一个达到用户，则对每个出发用户都要选择一个到达用户，尔每个到达用户只能有一个出发用户到达该地，将问题变成了一个分配问题，可用匈牙利算法求解。 到达 出发 1 2 3 4 5 1 2 3 4 5 ∞ 2 1 1 7 1 ∞ 6 5 5 7 6 ∞ 4 4 4 3 2 ∞ 5 3 4 1 6 ∞ 用户间距表 例题 * 现 代 物 流 学 * 解: 第一步：令d(i,i)=∞，不存在通路的也记为∞，的距离阵，通常d(i,j)与d(j,i)不一定相同，即矩阵不一定对称。 第二步：对距离矩阵用匈牙利法求解，若得到无环路的路线，则就是最优路线；如路线有环路，就不是最优路线，但所走总距离给出了旅行商问题总距离的下界。 * 现 代 物 流 学 * 得不考虑环路下的最优方案： 1→2，2→4，4→1，3→5，5→3 则，所走总距离为：1+3+1+1+4=10 可以看出上述路线存在环路，不是原问题的最优路线，但给出了原问题的下界10。 * 现 代 物 流 学 * 第三步：出现环路时，打开节点个数最少的环路。即在此环路上考虑某段路线不通的各种情况，分别用匈牙利法求解，其中距离最短又无环路的路线即为最优路线。 本例中，出现两个环路， 1→2→4→1和3→5→3，打开节点数少的环路，分别令d(3,5)=∞和d(5,3)=∞求解。 * 现 代 物 流 学 * （1）当d(3,5)=∞时，用匈牙利法求解。 可得无环路的最优方案： 5→3→4→1→2→5 则，所走总距离为：1+4+2+1+4=12。 * 现 代 物 流 学 * （2）当d(5, 3)=∞时，用匈牙利法求解。 可得无环路的最优方案： 1→2, 2→1, 3→5, 4→3, 5→4 则，所走总距离为：1+2+1+4+5=13。 * 现 代 物 流 学 * 可以看到，上述方案出现环路1→2→1和3→5→4 →3，如果打开环路求解，其总距离一定不小于13，而已经得到总距离为12的路线，故不必再作计算。因此得上述旅行上的最优路线为： 5→3→4→1→2→5；总距离为：12。 * 现 代 物 流 学 * 12.2.4 旅行商问题的神经网络求解 1、连续Hopfield神经网络模型 （a）Hopfield神经元 * 现 代 物 流 学 * （b）Hopfield神经网络 * 现 代 物 流 学 * 设有n个神经元互连，则可用下述非线性微分方程描述： 上式可以定义系统的能量函数为： * 现 代 物 流 学 * 可以证明，对于该能量函数，恒有 ，即当 ，网络达到稳定。应用网络的这一特性，可以进行优化问题的求解。求解时，只需将优化问题的目标函数转化成能量函数的形式，然后应用上述微分方程运算到网络收敛即可。通常在用Hopfield神经网络求解实际问题时，一般忽略能量式中得积分项，将能量函数简化为下式，以便目标函数的映射。 * 现 代 物 流 学 * 12.3 网络流问题12.3 Network Flow Problem 12.3.1 网络最大流问题 1、问题的提出 已知连接产地V1与销地Vn的交通网，每一弧（Vi,Vj）代表从Vi到Vj的运输线，产品经由Vi输送到Vj，弧旁括号外的数字cij为弧的容量，括号内的数字xij为Vi到Vj的货运量，要求合理安排xij，使V1到Vn的货运量最大。 * 现 代 物 流 学 * 2、寻求最大流的标号法 对于包含n个顶点V1,V2,…,Vn的网络流，V1为发点，Vn为收点，各段弧（Vi,Vj）上容量为cij，设 是一个可行流，判断它是否最大流及对它进行调整，关键在于求出其增广链，标号法就是基于此来寻求最大流的。 3、最小费用最大流问题 解最小费用最大流问题的基本思想是，通过已知的由V1到收点Vn的最小费用流x，寻求其对应的最小费用增广链，沿此增广链去调整x，实现最大流。 * 现 代 物 流 学 * 第三步：重复第二步，直到所有的顶点都标号为止，每个顶点标号内的第二个数字即为V1到该顶点得最短距离，运用反向追踪可找出此最短路径。 4、最短路径问题