?2340?
\\ 4、 在未被直线覆盖的所有元素中找出一个最小元素（Xmin），未被直线覆盖的行（或列）
中所有元素都减去这个数。（注：若未被直线覆盖部分是行数<列数，则是按行减，反之则按列）。
（2）、在已作标记c的行中，对标记b所在列作标记c （3）、在已作标记c的列中，对标记a 所在的行作标记c （4）、对没有标记c的行划线，对有标记c的列划线
?0 30118?
??
?01773? \\ ?02321? ? ? \\ ?0 050 4?///?0?/ ////?0???1??1??0?0?30118??0662?1210?
?0504?2340??5、 这样必然出现负元素，所以对负元素所在列（或行）中各元素都加上这一最小元素（Xmin）
以消除负数。这样，再返回步骤2，确定独立零元素个数。 重复上述操作，直到找出最优解。
?0 3 0 11 8???
0 6 6 2?/ ?0 ?0 1 2 ?1 0 / ???1 0 5 0 4? / ??1 2 3 4 0?? ??特殊问题：
1、 若人数和工作数不等，则用“0”来补全空位
2、 若一个人可作几件事，则可化为相同的“几个人”来接受指派，费用系数相同。
练习题：
1、用匈牙利法求解如下效率矩阵的指派问题
7 9 10 12 13 12 16 17 15 16 14 15 11 12 15 16
2、分配甲、乙、丙、丁四人去完成五项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定
21
总花费时间为最少的指派方案。
人 任务 A B C D E
甲 25 29 31 42 37 乙 39 38 26 20 33 丙 34 27 28 40 32 丁 24 42 36 23 45
3、已知下列五人各种姿势的游泳成绩（各为50米），试问如何进行指派，从中选拔一个参加200米混合泳的接力队，使预期比赛成绩为最好。
仰 泳 蛙 泳 蝶 泳 自由泳
赵 37.7 43.4 33.3 29.2 钱 32.9 33.1 28.5 26.4 张 33.8 42.2 38.9 29.6 王 37.0 34.7 30.4 28.5 周 35.4 41.8 33.6 31.1 四、最大流问题
例题：设容量网络D具有二个供应量皆为20（吨）的发点s1与s2，具有二个需求量分别为15、20的收点n1与n2。其上的容量函数如图7所示；试求D的最大流网络。
图7 具有二个发点和二个收点容量网络D
解：（1） 增设一个总发点s，并置cs,s1=20，cs,s2=20；同时增设一个总收点n，并置cn1,n=15，Cn2,n=20。把D化为一个只有一个发点和一个收点的标准容量网络D1，如图8所示。
22
图8 化D为标准容量网络D1
（1） 接下来的求解过程，与求解例1的过程完全相同。需要注意的是，这时在Number of
Nodes栏中填上10。根据容量网络图8输入每条弧的容量数据，如图9所示。 点击工具栏上的“Solve and Analyze\\ Solev of Problem”，在如图10的对话框中点击“Solve”，即得结果，见图11。
图9 例2的数据输入框
图10 选择起始点的对话框 图11 例2的计算结果 据此，我们可归结得到本容量网络离散的最大流量函数f*（E）：
f*(s,s1)?20，f*(s,s2)?15，f*(s1,1)?10，f*(s1,2)?10，f*(s2,2)?5，f*(s2,3)?5f*(s2,4)?5，f*(1,n1)?10，f*(2,3)?5，f*(2,n1)?10，f*(3,4)?5，f*(3,n2)?10
f*(4,n2)?10，f*(n1,3)?5，f*(n1,n)?15，f*(n2,n)?20
而对表内未列入的弧上的流量皆取为零，本例是以下弧上的流量为零：
f*(s2,2)?f*(2,n1)?f*(n1,3)?f*(3,4)?0。
计算结果表同时指出：本例的最大总流量W（f*）=35。至此，我们得所求之最大流网络（图12）：
23
图12 非标准容量网络最大流f*
练习题：
9.1 十名学生参加六门课程的考试。由于选修内容不同，考试门数也不一样。下表给出了每个学生应参加考试的课程（打⊙的）：
学生 考试课程 A B C D E F
1 ⊙ ⊙ ⊙ 2 ⊙ ⊙
3 ⊙ ⊙ 4 ⊙ ⊙ ⊙ 5 ⊙ ⊙ ⊙ 6 ⊙ ⊙ 7 ⊙ ⊙ ⊙ 8 ⊙ ⊙
9 ⊙ ⊙ ⊙ 10 ⊙ ⊙ ⊙
规定考试在三天内结束，每天上下午各安排一门。学生希望每人每天最多考一门，又课程A必须安排在第一天上午考，课程F安排在最后一门，课程B只能安排在下午考，试列出一张满足各方面要求的考试日程表。
9.3 下图表示某生产队的水稻田，用堤埂分割为很多小块。为了用水灌溉，需要挖开一些堤埂。问最少挖开多少堤埂，才能使水浇灌到每小块稻田。
24
9.8 用标号法求下图所示的最大流问题，弧上数字为容量和初始可行流量：
v1 （7，4） v3
（8，8） （3，1） （8，6）
vs （3，3） （3，0） vt
（9，4） （2，2） （9，6）
v2 （5，5） v4
9.10 如下图，从三口油井1、2、3经管道将油输至脱水处理厂7和8，中间经4、5、6三个泵站。已知图中弧旁数字为各管道通过的最大能力（吨/小时），求从油井每小时能输送到处理厂的最大流量。
1 7
20 4 10 10 2 50 20 10 6 50 30 20 20 3 15 5 30 8
9.11 某单位招收懂俄、英、日、德、法文的翻译各一人，有5人应聘。已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这5个人是否都能得到聘书？最多几个得到招聘，招聘后每人从事哪一方面翻译任务？
9.12. 下表给出某运输问题的产销平衡表与单位运价表。将此问题转化为最小费用最大流问题，画出网络图并求数值解。
产地 销地 1 2 3 产 量
A 20 24 5 8 B 30 22 20 7 销 量 4 5 6
五、最短路问题
例题：设6个城市v1,v2,?,v6之间的一个公路网(图1)每条公路为图中的边,边上的权数表示该段公路的长度(单位:百公里),设你处在城市v1,那么从v1到v6应选择哪一路径使你的费用最省。
25