三网络流与图( 二 ) _网络流

令集合A表示可行的(i,j)对,cij表示表里的时间。上面的问题可以转化为用最小化总时间的方法将工作分配给工作站。由于工作站数量多于工作，需要引入伪成员解决这一问题。
若分配问题中需要配对的两个集合大小不一致，则小的一个可以利用伪成员进行扩张。这些伪对象可以被分配给另一个集合里的所有成员，且相应费用为零。
CAM应用中，引入伪工作i=9,10.则其标准形式可表示为：
求解该问题，可以用到前两节提到的算法（消圈算法、单纯圈形法），也可以用线性规划的任一种算法（单纯形法、内点法、对偶法）。但对于这类分配问题，我们有一种更高效的算法求解——匈牙利算法（）
2
匈牙利算法
先直接给出算法步骤：
举个例子来消化这个算法。下表展示了源集I={1,2,3,4}四个对象需要配对给汇集J={5,6,7,8}对象的费用/权重：
初始化，先计算源集对偶值：
接着计算汇集对偶解：
计算边际减少费用：

文章插图
然后构建相等子图：
进入解扩张，首先，标记为“偶”的根i=1被分配给未分配、未标记的j=5 ，将(1,5)加入解集；接着对“偶”的根i=2被分配给j=6,对根i=4被分配给j=7 。由于5已分配，故根i=3不被分配。得到（红色粗线表示已分配）：
然后进行树生长,只剩下“偶”节点i=3,指向已分配但未标记的节点j=5 。故将（3 ， 5）和分配给j=5的(1,5)插入树，标记j=5为“奇” ， i=1为“偶” ，得到（虚线表示被包含在树中）：
转回步骤1 ，但此时不存在“偶”标记到未分配、未标记的节点。因此进入步骤2 ，也不存在满足条件的弧，进入步骤3.
A是源集到汇集的完整图={(1,5),(1,6),(1,7),(1,8),(2,5),(2,6),...,(4,7),(4,8)} ，根据定义，
接着更新对偶值及矩阵：
更新相等子图（绿色是新的边）:
然后返回步骤1 ，节点5已被标记，故不满足“未标记”条件；节点6已被未配，也不满足“未分配”条件；因此进入步骤2 ，（3 ， 6）满足条件，进行树生长及记录路径(3,6),(2,6)：
然后返回步骤1 ，没有满足条件的情况，再次进入步骤2 ，记录路径(2,7)(4,7),得到：
返回步骤1 ，（4 ， 8）满足条件，进行解集扩张：
至此，迭代结束。最优解已找到！

三 网络流与图( 二 )

三网络流与图( 二 )