三级
一、P259
目标人工费用率
目标劳动分配率＝
目标净产值
改为：
目标人工费用
目标劳动分配率＝
目标净产值
二、匈牙利法 P96～98
假定甲单位有甲、乙、丙、丁、戊五个员工，需要在一定的生产技术组织条件下，完成A、B、C、D、E五项任务，每个员工完成每项工作所需要耗费的工作时间，如表2－6所示。
请求出：员工与任务之间应当如何进行配置，才能保证完成工作任务的时间最短？
表2－6 各员工完成任务时间汇总表单位：小时
注意：由于存在以下两种情况，匈牙利法的计算过程不唯一，最终矩阵的形式也不唯一，但最终配置结果一定相同，
1．约减时，可先进行行约减，再进行列约减；也可先进行列约减，再进行行约减。2．“盖0”线的画法不唯一。
现列举两种解法如下：
解法一：
1．以各个员工完成各项任务的时间构造矩阵一。
表2－7矩阵一
10 5 9 18 11
13 19 6 12 14
3 2
4 4 5
18 9 12 17 15
11 6 14 19 10
2．对矩阵一进行行约减，即每一行数据减去本行数据中的最小数，得矩阵二。
表2－8 矩阵二
5 0 4 13 6
7 13 0 6 8
1 0
2 2 3
9 0 3 8 6
5 0 8 13 4
3．检查矩阵二，若矩阵二各行各列均有“0”，则跳过此步，否则进行列约减，即每一列数据减去本列数据中的最小数，得矩阵三。
表2－9 矩阵三
4 0 4 11 3
6 13 0 4 5
0 0 2 0 0
8 0 3 6 3
4 0 8 11 1
4．画“盖0”线。即画最少的线将矩阵三中的0全部覆盖住，得图2－5。
图2－5 矩阵四
操作技巧：从含“0”最多的行或列开始画“盖0”线。
5．数据转换。若“盖0”线的数目等于矩阵的维数则跳过此步，若“盖0”线得数目小于矩阵得维数则进行数据转换，本例属于后一种情况，应进行转换，操作步骤如下：
（1）找出未被“盖0”线覆盖的数中的最小值λ，例中λ＝1。
（2）将未被“盖0”线覆盖住的数减去λ。
（3）将“盖0”线交叉点的数加上λ。
本例结果见表2－10 矩阵五。
表2－10 矩阵五
3 0
4 10 2
5 13 0 3 4
0 1 3 0 0
7 0 3 5 2
3 0 8 10 0
6．重复4步和5步（计算过程见矩阵五a和矩阵五b），直到“盖0”线的数目等于矩阵的维数。本例最终矩阵见表2－11。
矩阵五a
矩阵五b
表2－11 矩阵六
0 0 4 7 2
2 1
3 0 0 4
0 4 6 0 3
4 0 3 2 2
0 0 8 7 0
7．求最优解。对n维矩阵，找出不同行、不同列的n个“0”，每个“0”的位置代表一对配置关系，具体步骤如下：
（1）先找只含有一个“0”的行（或列），将该行（或列）中的“0”打“√”。
（2）将带“√”的“0”所在列（或行）中的“0”打“?”。
（3）重复（1）步和（2）步至结束。若所有行列均含有多个“0”，则从“0”的数目最少的行或列中任选一个“0”打“√”。
其结果如表2－12矩阵七所示，即员工甲负责任务A，员工乙负责任务D，员工丙负责任务B，员工丁负责任务C，员工戊负责任务E，参照表2－6各员工完成任务时间汇总表，得出表2－13所示的员工配置最终结果。
表2－12 矩阵七
0 √0 ? 4 7 2
2 1
3 0 √0 ? 4
0 ? 4 6 0 √3?
4 0 √ 3 2 2
0 ?0 ?8 7 0 √
表2－13 员工配置最终结果单位：小时
解法二：
1．以各个员工完成各项任务的时间构造矩阵一。
表2－7矩阵一
10 5 9 18 11
13 19 6 12 14
3 2
4 4 5
18 9 12 17 15
11 6 14 19 10
2．对矩阵一进行行约减，即每一行数据减去本行数据中的最小数，得矩阵二。
表2－8 矩阵二
5 0 4 13 6
7 13 0 6 8
1 0
2 2 3
9 0 3 8 6
5 0 8 13 4
3．检查矩阵二，若矩阵二各行各列均有“0”，则跳过此步，否则进行列约减，即每一列数据减去本列数据中的最小数，得矩阵三。
表2－9 矩阵三
4 0 4 11 3
6 13 0 4 5
0 0 2 0 0
8 0 3 6 3
4 0 8 11 1
4．画“盖0”线。即画最少的线将矩阵三中的0全部覆盖住，得图2－5。
图2－5 矩阵四
操作技巧：从含“0”最多的行或列开始画“盖0”线。
5．数据转换。若“盖0”线的数目等于矩阵的维数则跳过此步，若“盖0”线得数目小于矩阵得维数则进行数据转换，本例属于后一种情况，应进行转换，操作步骤如下：
（1）找出未被“盖0”线覆盖的数中的最小值λ，例中λ＝1。
（2）将未被“盖0”线覆盖住的数减去λ。
（3）将“盖0”线交叉点的数加上λ。
本例结果见表2－10 矩阵五。
表2－10 矩阵五
3 0
4 10 2
5 13 0 3 4
0 1 3 0 0
7 0 3 5 2
3 0 8 10 0
6．重复4步和5步（计算过程见矩阵五a和矩阵五b），直到“盖0”线的数目等于矩阵的维数。本例最终矩阵见表2－11。
矩阵五a
0 0 1 7 2
5 1
6 0 3 7
0 4 3 0 3
4 0 0 2 2
0 0 5 7 0
矩阵五b
表2－11 矩阵六
0 0 1 7 2
5 1
6 0 3 7
0 4 3 0 3
4 0 0 2 2
0 0 5 7 0
7．求最优解。对n维矩阵，找出不同行、不同列的n个“0”，每个“0”的位置代表一对配置关系，具体步骤如下：
（1）先找只含有一个“0”的行（或列），将该行（或列）中的“0”打“√”。
（2）将带“√”的“0”所在列（或行）中的“0”打“?”。
（3）重复（1）步和（2）步至结束。若所有行列均含有多个“0”，则从“0”的数目最少的行或列中任选一个“0”打“√”。
其结果如表2－12矩阵七所示，即员工甲负责任务A，员工乙负责任务D，员工丙负责任务B，员工丁负责任务C，员工戊负责任务E，参照表2－6各员工完成任务时间汇总表，得出表2－13所示的员工配置最终结果。
表2－12 矩阵七
0√0 1 7 2
5 1
6 0√ 3 7
0 ? 4 3 0 √ 3
4 0√0 ? 2 2
0 ?0 ? 5 7 0√
第九章分批法练习题参考答案 一、某工业企业生产甲、乙两种产品。生产组织属于小批生产，采用分批法计算成本。2002年4月份的生产情况和生产费用资料如下： （1）本月份生产的产品批号有： 2051批号：甲产品12台，本月投产，本月完工8台。 2052批号：乙产品10台，本月投产，本月完工3台。 （2）本月份的成本资料：（单位：元） 2051批号甲产品完工数量较大，完工产品与在产品之间分配费用采用约当产量法。在产品完工率为50%，原材料在生产开始时一次投入。 2052批号乙产品完工数量少，完工产品按计划成本结转。 每台计划成本为：原材料880元，燃料140元，工资及福利费720元，制造费用450元。 要求：根据上列资料，采用分批法，登记产品成本明细账，计算各批产品的完工产品成本和月末在产品成本。
解： 甲产品费用分配情况： 材料费用分配率=6840/12=570 燃料费用分配率=1452/（8+4×50%）=145.2 工资及福利费分配率=4200/（8+4×50%）=420 制造费用分配率=2450/（8+4×50%）=245 产品成本明细账 产品批号：2051 投产日期：4月 产品名称：甲批量：12台完工日期：4月完工8台
乙产品完工产品成本按计划成本转出 完工产品原材料计划成本=880×3=2640 完工产品燃料计划成本=140×3=420 完工产品工资及福利费计划成本=720×3=2160 完工产品制造费用=450×3=1350 产品成本计算单 产品批号：2052 投产日期：4月 产品名称：乙批量：10台完工日期：4月完工3台
二、某企业生产属于小批生产，产品批数多，每月末都有很多批号没有完工，因而采用简化的分批法计算产品成本。 （1）8月份生产的产品批号有： 8210号：甲产品6件，7月投产，8月25日全部完工。 8211号：乙产品14件，7月投产，8月完工8件。 8212号：丙产品8件，7月末投产，尚未完工。 8213号：丁产品6件，8月投产，尚未完工。 （3）各批号产品8月末累计原材料费用（原材料在生产开始时一次投入）和生产工时为： 8210号：原材料32000元，工时9200小时。 8211号：原材料98000元，工时29600小时。 8212号：原材料62400元，工时18200小时。 8213号：原材料42600元，工时8320小时。 （4）8月末，该企业全部产品累计原材料费用235000元，工时65320小时，工资及福利费26128元，制造费用 32660元。 （5）8月末，完工产品工时25200小时，其中乙产品16000
指派问题的匈牙利解法 1、 把各行元素分别减去本行元素的最小值；然后在此基础上再把每列元素减去本列中的最小值。 ???????? ??????????? ? ?0 4 3 2 04 0 5 0 01 2 3 2 03 7 7 1 08 11 0 3 06 10 12 9 610 6 14 7 67 8 12 9 610 14 17 9 712 15 7 8 4 此时每行及每列中肯定都有0元素了。 2、 确定独立零元素，并作标记。 （1）、首先逐行判断是否有含有独立0元素的行，如果有，则按行继续处理；如没有，则要逐列判断是否有含有独立0元素的列，若有，则按列继续处理。若既没有含有独立0元素的行，也没有含有独立0元素的列，则仍然按行继续处理。 （2）在按行处理时，若某行有独立0元素，把该0元素标记为a ，把该0所在的列中的其余0元素标记为b ；否则，暂时越过本行，处理后面的行。把所有含有独立0元素的行处理完毕后，再回来处理含有2个以及2个以上的0元素的行：任选一个0做a 标记，再把该0所在行中的其余0元素及所在列中的其余0元素都标记为b 。
（3）在按列处理时，若某列有独立0元素，把该0元素标记为a ，把该0所在的行中的其余0元素标记为b ；否则，暂时越过本列，处理后面的列。把所有含有独立0元素的列处理完毕后，再回来处理含有2个以及2个以上的0元素的列：任选一个0做a 标记，再把该0所在列中的其余0元素及所在行中的其余0元素都标记为b 。 （4）、重复上述过程，即得到独立零元素（标记a 的“0”） ???????? ??a b b a b b a 0 4 3 2 04 0 5 0 01 2 3 2 03 7 7 1 08 11 0 3 0a b 3、 若独立零元素等于矩阵阶数，则已经得到最优解，若小于矩阵阶数，则继续以下步骤： （1）、对没有标记a 的行作标记c （2）、在已作标记c 的行中，对标记b 所在列作标记c （3）、在已作标记c 的列中，对标记a 所在的行作标记c （4）、对没有标记c 的行划线，对有标记c 的列划线 ??????? ? ??04320405001232037710 811030 / / / / / \/ \/
匈牙利法 假定甲单位有甲、乙、丙、丁、戊五个员工，需要在一定的生产技术组织条件下，完成A、B、C、D、E五项任务，每个员工完成每项工作所需要耗费的工作时间，如表2－6所示。 请求出：员工与任务之间应当如何进行配置，才能保证完成工作任务的时间最短？ 表2－6 各员工完成任务时间汇总表单位：小时 注意：由于存在以下两种情况，匈牙利法的计算过程不唯一，最终矩阵的形式也不唯一，但最终配置结果一定相同， 1．约减时，可先进行行约减，再进行列约减；也可先进行列约减，再进行行约减。2．“盖0”线的画法不唯一。 现列举两种解法如下： 解法一： 1．以各个员工完成各项任务的时间构造矩阵一。 表2－7矩阵一 10 5 9 18 11 13 19 6 12 14 3 2 4 4 5 18 9 12 17 15 11 6 14 19 10 2．对矩阵一进行行约减，即每一行数据减去本行数据中的最小数，得矩阵二。 表2－8 矩阵二 5 0 4 13 6 7 13 0 6 8 1 0 2 2 3 9 0 3 8 6 5 0 8 13 4 3．检查矩阵二，若矩阵二各行各列均有“0”，则跳过此步，否则进行列约减，即每一列数据减去本列数据中的最小数，得矩阵三。 表2－9 矩阵三 4 0 4 11 3 6 13 0 4 5 0 0 2 0 0 8 0 3 6 3 4 0 8 11 1
4．画“盖0”线。即画最少的线将矩阵三中的0全部覆盖住，得图2－5。 图2－5 矩阵四 操作技巧：从含“0”最多的行或列开始画“盖0”线。 5．数据转换。若“盖0”线的数目等于矩阵的维数则跳过此步，若“盖0”线得数目小于矩阵得维数则进行数据转换，本例属于后一种情况，应进行转换，操作步骤如下： （1）找出未被“盖0”线覆盖的数中的最小值λ，例中λ＝1。 （2）将未被“盖0”线覆盖住的数减去λ。 （3）将“盖0”线交叉点的数加上λ。 本例结果见表2－10 矩阵五。 表2－10 矩阵五 3 0 4 10 2 5 13 0 3 4 0 1 3 0 0 7 0 3 5 2 3 0 8 10 0 6．重复4步和5步（计算过程见矩阵五a和矩阵五b），直到“盖0”线的数目等于矩阵的维数。本例最终矩阵见表2－11。 矩阵五a
（一）基本情况 某企业属单件小批多步骤生产企业，按购货单位要求小批生产甲、乙、丙三种产品，产品成本计算采用分批法，该企业9月份的有关成本计算资料如下： 1、各生产批别产量、费用资料 （1）901号甲产品50件，7月份投产，本月全部完工，7、8两月累计费用为：直接材料4000元，直接人工1000元，制造费用1200元。本月发生费用：直接人工400元，制造费用500元。 （2）902号乙产品100件，8月份投产，本月完工60件，未完工40件，8月份发生生产费用为：直接材料60000元，直接人工15000元，制造费用13000元。本月发生费用：直接人工7000元，制造费用6000元。 （3）903号丙产品7件，本月份投产，尚未完工，本月发生生产费用为：直接材料20000元，工资福利费5600元，制造费用4800元。 2、其他资料 （1）三种产品的原材料均在生产开始时一次投入。 （2）902号乙产品本月完工产品数量在批内所占比重较大（60%），根据生产费用发生情况，其原材料费用按照完工产品和在产品的实际数量比例分配外，其他费用采用约当产量比例法在完工产品和月末在产品之间进行分配，在产品完工程度为50%。 （二）成本计算过程 1、901号成本计算 901号产品，本月全部完工，7、8、9三个月份累计生产费用全部为完工产品成本，除以完工产品数量，为完工产品单位成本。 表8—1 901号产品成本计算单 批号：901 产品名称甲投产日期：7月份 会计分录: 借:库存商品7100 贷:基本生产成本—甲产品7100 2、902号产品成本计算 902号本月完工60件，尚有40件未完工，属于是跨月陆续完工，且完工产品数量在批内所占比重较大，生产费用应在完工产品和月末在产品之间进行分配。因原材料一次投入，完工产品和在产品负担的原材料费用相同，按产品数量分配。其余按约当产量比例分配。 约当产量=完工产品数量+在产品约当产量 直接材料项目的约当产量=60+40×100%=100 直接人工项目约当产量=60+40×50%=80
运筹学 课 程 设 计 报 告 专业： 班级： 学号： ： 2012年6月20日
目录 一、题目。 二、算法思想。 三、算法步骤。 四、算法源程序。 五、算例和结果。 六、结论与总结。
一、题目：匈牙利法求解指派问题。 二、算法思想。 匈牙利解法的指派问题最优解的以下性质： 设指派问题的系数矩阵为C=()c ij n n?，若将C的一行（或列）各元素分别减去一个常数k（如该行或列的最小元素），则得到一个新的矩阵C’=()'c ij n n?。那么，以C’位系数矩阵的指派问题和以C位系数矩阵的原指派问题有相同最优解。 由于系数矩阵的这种变化不影响约束方程组，只是使目标函数值减少了常 数k，所以，最优解并不改变。必须指出，虽然不比要求指派问题系数矩阵中无 负元素，但在匈牙利法求解指派问题时，为了从以变换后的系数矩阵中判别能否 得到最优指派方案，要求此时的系数矩阵中无负元素。因为只有这样，才能从总 费用为零这一特征判定此时的指派方案为最优指派方案。 三、算法步骤。 （1）变换系数矩阵，使各行和各列皆出现零元素。 各行及各列分别减去本行及本列最小元素，这样可保证每行及每列中都有 零元素，同时，也避免了出现负元素。 （2）做能覆盖所有零元素的最少数目的直线集合。
因此，若直线数等于n，则以可得出最优解。否则，转第（3）步。 对于系数矩阵非负的指派问题来说，总费用为零的指派方案一定是最优指派方案。在第（1）步的基础上，若能找到n个不同行、不同列的零元素，则对应的指派方案总费用为零，从而是最优的。当同一行（或列）上有几个零元素时，如选择其一，则其与的零元素就不能再被选择，从而成为多余的。因此，重要的是零元素能恰当地分布在不同行和不同列上，而并在与它们的多少。但第（1）步并不能保证这一要求。若覆盖所有零元素的最少数目的直线集合中的直线数目是n，则表明能做到这一点。 此时，可以从零元素的最少的行或列开始圈“0”，每圈一个“0”，同时把位于同行合同列的其他零元素划去（标记为），如此逐步进行，最终可得n个位于不同行、不同列的零元素，他们就对应了最优解；若覆盖所有零元素的最少数目的直线集合中的元素个数少于n，则表明无法实现这一点。需要对零元素的分布做适当调整，这就是第（3）步。 （3）变换系数矩阵，是未被直线覆盖的元素中出现零元素。回到第（2）步。 在未被直线覆盖的元素中总有一个最小元素。对未被直线覆盖的元素所在的行（或列）中各元素都减去这一最小元素，这样，在未被直线覆盖的元素中势必会出现零元素，但同时却又是以被直线覆盖的元素中出现负元素。为了消除负元素，只要对它们所在的列（或行）中个元素都加上这一最小元素（可以看作减去这一最小元素的相反数）即可。 四、算法源程序。
匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes K?nig和Jen? Egerváry的工作之上创建起来的。 匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。 二分图： 二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。图一就是一个二分图。 匈牙利算法： 匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是一种用增广路径求二分图最大匹配的算法。 Hall定理： 二部图G中的两部分顶点组成的集合分别为X, Y; X={X1, X2, X3,X4, .........,Xm}, Y={y1, y2, y3, y4 , .........,yn}, G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是：X中的任意k个点至少与Y中的k个点相邻。（1≤k≤m) 匹配： 给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。图一中红线为就是一组匹配。 未盖点： 设Vi是图G的一个顶点，如果Vi 不与任意一条属于匹配M的边相关联，就称Vi 是一个未盖点。如图一中的a 3、b1。
将xyl程序存入M文件，在matlab中先写入邻接矩阵marix，而后再写function [z,ans]=xyl(marix) 回车得出结果 程序文件 xyl.m function [z,ans]=xyl(marix) %输入效率矩阵 marix 为方阵; %若效率矩阵中有 M,则用一充分大的数代替; %输出z为最优解，ans为最优分配矩阵； %////////////////////////////////////////////////// a=marix; b=a; %确定矩阵维数 s=length(a); %确定矩阵行最小值，进行行减 ml=min(a'); for i=1:s a(i,:)=a(i,:)-ml(i); end %确定矩阵列最小值，进行列减 mr=min(a); for j=1:s a(:,j)=a(:,j)-mr(j); end % start working num=0; while(num~=s) %终止条件是“（0）”的个数与矩阵的维数相同 %index用以标记矩阵中的零元素，若a(i,j)=0，则index(i,j)=1,否则index(i,j)=0 index=ones(s); index=a&index; index=~index; %flag用以标记划线位，flag=0 表示未被划线， %flag=1 表示有划线过，flag=2 表示为两直线交点 %ans用以记录 a 中“（0）”的位置 %循环后重新初始化flag,ans flag = zeros(s); ans = zeros(s); %一次循环划线全过程，终止条件是所有的零元素均被直线覆盖， %即在flag>0位,index=0 while(sum(sum(index))) %按行找出“（0）”所在位置，并对“（0）”所在列划线， %即设置flag,同时修改index,将结果填入ans for i=1:s t=0;
匈牙利法真题演练（07年5月）： 某车间产品装配组有王成、赵云、江平、李鹏四位员工.现有A、B、C、D 四项任务，在现有生产技术组织条件下，每位员工完成每项工作所需要的工时如表1所示。问：请运用匈牙利法求出员工与任务的配置情况，以保证完成任务的总时间最短，并求出完成任务的量短时间。 表1 王成赵云江平李鹏 工作 任务 员工 A 10 5 9 18 B 13 18 6 12 C 3 2 4 4 D 18 9 10 16 解题步骤： 1、建立矩阵 105918（-5） 1318612（-6） 3244（-2） 1891016（-9） 2、行列约减 5 0 4 13 7 12 0 6 1 0 2 2 9 0 1 7 （-1）（-2） PS：行约减以后需要检查列是否都有“0”
3、盖“0” 4 0 4 11 6 12 0 4 0 0 2 0 8 0 1 5 “盖0”只有三条，需要找出剩下数字中最小约数 4、继续约减，交叉处加上约数 3 0 3 10 6 13 0 4 0 1 2 0 7 0 0 4 当我们做完第三步会发现盖0线的数目仍然小于矩阵维数，继续寻找最小约数 将未被盖0线覆盖的数字都减去最小约数，同时在盖0线交叉点上的数字加上这个最小约数 5、数据转化 0 0 3 7 3 13 0 1 0 4 5 0 4 0 0 1 四条盖0线，四个维度，进行求最优解，首先只有一个0的行列，打钩 6、求最优解 0√0× 3 7 3 13 0√ 1 0× 4 5 0√ 4 0√0× 1 得到最优解如下：王—A；赵—D；江—B；李—C。 对照工时消耗表，完成任务的总时间为10+9+6+4=29
分批法课堂练习 1、资料：某企业第一车间生产501批次甲产品、601批次乙产品、502批次 丙产品三批产品，6月份有关成本计算资料如下： （1）月初在产品成本 501批次甲产品为104000元，其中直接材料84000元，直接人工12000元，制造费用8000元；502批次丙产品124000元，其中直接材料120000元，直接人工2000元，制造费用2000元。 （2）本月生产情况 501甲产品为5月2日投产40件，本月26日已全部完工验收入库，本月实际生产工时为8000小时。601乙产品为本月4日投产120件，本月已完工入库12件，本月实际生产工时为4400小时。502丙产品为5月6日投产60件，本月尚未完工，本月实际生产工时为4000小时。 （3）本月发生生产费用 本月投入原材料396000元，全部为601乙产品耗用。本月产品生产工人工资为49200元，提取应付福利费为6888元，制造费用总额为44280元。 （4）单位产品定额成本 601乙产品单位产品定额成本为4825元，其中直接材料3300元，直接人工825元，制造费用700元。 要求：根据上述资料材料采用分批法计算产品成本，具体计算程序如下：（1）按产品批别开设产品成本计算单并登记月初在产品成本。 （2）编制601批产品耗用原材料的会计分录并记入产品成本计算单。 （3）用生产工时分配法在各批产品之间分配本月发生的直接人工费用，根据分配结果编制会计分录并记入有关产品成本计算单。 （4）采用生产工时分配法在各批产品之间分配本月发生的制造费用，根据分配结果编制会计分录并记入有关产品成本计算单。 （5）计算本月完工产品和月末在产品成本，编制结转完工产品成本的会计分录。601乙产品本月少量完工，其完工产品成本按定额成本结转。 产品成本成本计算单批量：40件 开工日期：5月2日批别：501批次 产品：甲产品完工日期：6月26日
指派问题的解法总结 问题引入：在工作的时候，常常需要对一些人进行工作安排，由于某些条件的限制， 每个人只能进行一种工作，怎么安排才能使得总工作时间最小。我们把这一类问题称 为指派问题。在这里，我只对人和工作刚好一对一的指派问题的解法进行总结，而对 于不是一对一的，则可以通过文献1中的一些方法进行变换。 目前问题解法的总结。 1：最广泛应用的解法：匈牙利算法。 算法简介：库恩（fW．W．Kuhn)于1955年提出了指派问题的解法．他引用了匈牙利数学家康尼格一个关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等 于覆盖所有0元素的最少直线数。这个解法称为匈牙利解法。 匈牙利算法虽是运用最广泛的算法，但其操作过程却过于复杂。在划0的时候也不方 便记忆，对于初学者来说掌握不便。于是国内很多学者对指派问题给出了几个较简单，方便易记的算法。 2：指派问题新解法——目标值子矩阵法。 算法描述：任取变量矩阵X某一行中的最小元素，为该行元素目标值的最优解(但 不一定是系统目标函数的最优解)，应该是系统目标函数满意解中的一个元素，记作 a11 划去a11 所在的行和列，取剩下的子矩阵中某一行的最小元素，记作a22。依次 类推，直到最后一个元素a nn．这些元素相加得系统目标函数的一个满意解，此为一 次运算．第二次运算取变量矩阵X中含a 以外的任一行，做与上面相同运算，又可以 得到系统的第二个满意解．相同地，对于n行做n次运算，共得到系统的n个满意解，系统的最优解即应该是这 n个满意解当中的最小值．若第i的最小元素在前面以被取 用过，则在进行第i的运算时，不选取该元素，取该行中未被选用过的元素中最小的一个进行运算。 算法分析：相对于匈牙利算法，此算法简单，方便操作。但不能给出所有最优解，得出的最优解唯一，若要给出全部最优解，则算法的次数将大大增加。 当矩阵维数较大的时候，可以对矩阵进行划分，以更快计算。 算法举例：对于变量矩阵x；
二、生产任务分配的匈牙利法 在实际的生产管理工作中，常会遇到这样的问题，就是如何根据生产作业汁划将不同任务在不同的工人(或班组)之间分配，使完成任务总的消耗时间或费用最小。解决这类问题的简便而有效的方法是匈牙利法，它是由匈牙利数学家D. Konig所提出。 例有4项任务A、B、C、D，分别由甲、乙、丙、丁4个人去完成，规定每人承担其中一项任务，不同的人完成同一任务所花时间(h)不同，见表3-3，求如何分配，使完成这4项任务的总时间最小。 匈牙利法求解此问题的步骤是： 1）按表3-3列出矩阵 2)将矩阵作行、列约简：首先进行行约简。在矩阵的每一行中选取最小元素， 然后将该行的各元素都减去此数，得到如下新矩阵 行约简是比较一名工人担任不同任务时所花的时间，各行中减去最小值后的时间表示该工人担任其它任务时，所多花费的时间，每行中的“0”表示该工人承担这项任务最有利。然后将经过行约筒后的矩阵中没有“0”的列再进行约简，即从该列中选出最小元素，并将其它元素减去此数，得到新矩阵 列约简是比较一项任务有不同工人承担所托时间，各列中减去最小值后的时间表示任务由其他工人担任时，所多花费的时间，每列中的“0”表示这项任务由该工人承担最有利。 3) 检验是否已得最优分配方案；作零的覆盖线，即对有“0”的行和列，划上一条覆盖线，能覆盖所有零元素的最少覆盖线数称为维数，当覆盖线的维数等于矩阵阶数时，可知已得最优分配方案，若维数小于阶数，再作调整。本例可用三条覆盖线覆盖住所有零元素，维数是3，矩阵的阶数是4，维数不等于阶数，因此矩阵还必须调整。
4) 矩阵的调整。在上述矩阵中．有三种元素，一种是无线覆盖元素，另一种是单线覆盖元素，还有一种是双线覆盖元素。在无线覆荒元素中找出最小值，本例为“1”，将无线覆盖得元素都减去“1”，而双线覆盖的元素加上“1”，单线覆盖的元素不变。这样得到新矩阵 5) 再检验——作覆盖线，方法与步骤3相同。现在的最少覆盖线数为4，与矩阵阶数相等，可知已能进行最优分配。 6) 确定最优分配方案。进行具体分配时，可以对只有一个零元素的列(行)先分配(记√号)，分配后，划去与该零元素同行(列)的其他零元素(记×号)这样依改做完各列(行)，得到分配结果。如果矩阵能通过直接观察找到位于不同行不同列的零元素，那么就可以直接确定分配方案。 最优分配方案：甲——D，乙——B，丙——A，丁——C。 总消耗工时为：Z=7+5+4+5=21 (h)。
匈牙利算法是一种用于在多项式时间内解决任务分配问题的组合优化算法，它推广了后来的原始对偶方法。美国数学家哈罗德·库恩（Harold Kuhn）于1955年提出了该算法。该算法之所以称为匈牙利算法，是因为该算法的很大一部分是基于前匈牙利数学家DéNESK?nig和Jen?egerváry的工作。 概念 在介绍匈牙利算法之前，我想介绍一些概念。接下来的M是G 的匹配项。 如果是，则边缘已经在匹配的M上。 M交织路径：P是G的路径。如果P中的边缘是属于m的边缘，而不属于m但属于G的边缘是交替的，则p是M交织的路径。例如：路径。 M饱和点：例如，如果V与M中的边相关联，则称V为m饱和，否则V为非m饱和。如果它们全部属于m饱和点，则其他点都属于非m饱和点。 M扩展路径：P是m隔行扫描路径。如果P的起点和终点均为非m饱和点，则p称为m增强路径。例如（不要与流网络中的扩展路径混淆）。 寻找最大匹配数的一种显而易见的算法是先找到所有匹配项，然后保留匹配数最大的匹配项。但是该算法的时间复杂度是边数的指数函数。因此，我们需要找到一种更有效的算法。本文介绍了一种使用扩展路径查找最大匹配的方法（称为匈牙利算法，由匈牙利的
Edmonds于1965年提出）。 增强导轨（也称为增强导轨或交错导轨）的定义 如果P是连接图G中两个不匹配顶点的路径，并且属于m和不属于m的边缘（即，匹配边缘和待匹配边缘）在P上交替，则p称为相对于M. 从增强路径的定义可以得出三个结论 （1）P的路径数必须为奇数，并且第一个边缘和最后一个边缘都不属于M。 （2）通过将m和P取反可以获得更大的匹配度。 （3）当且仅当没有M的增强路径时，M是G的最大匹配。 算法概述： （1）将M设置为null （2）通过XOR操作找到扩展路径P并获得更大的匹配项而不是m （3）重复（2），直到找不到增强路径
简化分批法例题 [例]某厂生产有第0102009、0103004、0104001等定单产品，其成本和工时总数汇总登记在“生产成本——基本生产成本”二级账中，如表7-5所示。第0102009、0103004、0104001定单的生产成本，如表7-6、7-7、7-8所示。 基本生产成本二级账 累计工资及福利费分配率=5000/1000=5（元/工时） 累计制造费用分配率=6000/1000=6（元/工时） 基本生产成本二级账月末在产品直接材料费用 =23840+50000=73840（元） 基本生产成本二级账月末在产品生产工时 =300+180=480（工时） 产品成本明细账 表1 产品批号：0102009 开工日期：200×年2月 表2 产品批号：0103004 开工日期：200×年3月15 产品名称：批量：5台完工日期： 产品成本明细账
表3 产品批号：0104001 开工日期：200×年4月5日
（分批法）习题 1、资料：某厂属于小批生产，采用简化的分批法计算成本。4月份生产情况如 下： （1）（1）月初在产品成本：101批号，直接材料3750元；102批号，直接材料2200元；103批号，直接材料1600元。月初直接人工1725 元，制造费用2350元。 （2）（2）月初在产品耗用累计工时：101批号1800小时；102批号590小时；103批号960小时。 （3）（3）本月的生产情况，发生的工时和直接材料如下表所示： （4）（4）本月发生的各项间接费用为：直接人工1400元，制造费用2025元。 要求：根据上述资料，登记基本生产成本二级帐和产品成本明细帐；计算完工产品成本。 答案如下： 基本生产成本二级帐 产品成本明细帐 批号：101 投产日期：2月 产品名称：甲完工日期：4月 产量：10件
匈牙利算法(Edmonds算法)步聚： (1)首先用（*）标记X中所有的非M顶点，然后交替进行步骤（2），（3）。 (2)选取一个刚标记（用（*）或在步骤（3）中用（y i）标记）过的X中顶点，例如顶点x ，如果x i与y为同一非匹配边的两端点，且在本步骤中y尚未被标记过,则用（x i）i 去标记Y中顶点y。重复步骤(2)，直至对刚标记过的X中顶点全部完成一遍上述过程。 (3)选取一个刚标记（在步骤(2)中用(x i)标记）过的Y中结点，例如y i，如果y i与x为 同一匹配边的两端点，且在本步骤中x尚未被标记过，则用(y i)去标记X中结点x。 重复步骤(3)，直至对刚标记过的Y中结点全部完成一遍上述过程。 (2),(3)交替执行，直到下述情况之一出现为止： (I)标记到一个Y中顶点y，它不是M顶点。这时从y出发循标记回溯，直到（*）标 记的X中顶点x，我们求得一条交替链。设其长度为2k+1，显然其中k条是匹配 边，k+1条是非匹配边。 (II)步骤(2)或(3)找不到可标记结点，而又不是情况(I)。 (4)当(2),(3)步骤中断于情况(I)，则将交替链中非匹配边改为匹配边，原匹配边改为非 匹配边(从而得到一个比原匹配多一条边的新匹配)，回到步骤(1)，同时消除一切现有 标记。 (5)对一切可能,(2)和(3)步骤均中断于情况(II),或步骤(1)无可标记结点,算法终止 (算法找不到交替链). 以上算法说穿了，就是从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过交替出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。 下面给出此算法的一个例子：
指派问题的匈牙利法求解步骤： 1) 变换指派问题的系数矩阵(c ij)为(b ij)，使在(b ij)的各行各列中都出现0元素，即 从(cij)的每行元素都减去该行的最小元素； 再从所得新系数矩阵的每列元素中减去该列的最小元素。 2) 进行试指派，以寻求最优解。 在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0 元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。 找独立0元素，常用的步骤为： 从只有一个0元素的行开始，给该行中的0元素加圈，记作◎。然后划去◎所 在列的其它0元素，记作?；这表示该列所代表的任务已指派完，不必再考虑别人了。依次进行到最后一行。 从只有一个0元素的列开始（画?的不计在内），给该列中的0元素加圈，记作◎； 然后划去◎所在行的0元素，记作?，表示此人已有任务，不再为其指派其他任务了。依次进行到最后一列。 若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，比较这行各0元素所 在列中0元素的数目，选择0元素少这个0元素加圈(表示选择性多的要“礼让” 选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。 若◎元素的数目m 等于矩阵的阶数n（即：m＝n），那么这指派问题的最优解已 得到。若m < n, 则转入下一步。 3) 用最少的直线通过所有0元素。其方法： 对没有◎的行打“√”； 对已打“√”的行中所有含?元素的列打“√”； 再对打有“√”的列中含◎元素的行打“√”； 重复①、②直到得不出新的打√号的行、列为止； 对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最 少直线数l 。 注：l 应等于m，若不相等，说明试指派过程有误，回到第2步，另行试指派；若 l＝m < n，表示还不能确定最优指派方案，须再变换当前的系数矩阵，以找到n 个独立的0元素，为此转第4步。 4) 变换矩阵(b ij)以增加0元素 在没有被直线通过的所有元素中找出最小值，没有被直线通过的所有元素减去这 个最小元素；直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍相同。转回第2步。
2．采用简化的分批法，累计间接计人费用分配率( )。 A. 只是各批产品之间分配间接计人费用依据 B．只是各批在产品之间分配间接计人费用依据 C．即是各批产品之间又是完工产品与月末在产品之间分配间接计人费用的依据D．是完工产品与月末在产品之间分配间接计人费用的依据 3．制造费用( )。 A．都是直接计人费用 B．都是间接计人费用 C. 都是间接生产费用 D．既包括间接生产费用，又包括直接生产费用 6．技术经济指标变动对产品成本的影响主要表现在对( )指标的影响。 A. 产品总成本B，产品单位成本 C. 产品产量 D. 产品总成本和产品产量 8)。 A．“基本生产成本”B．“辅助生产成本” C. “制造费用”D．“管理费用” 9．简化分批法是( )。 A. 分批计算在产品成本的分批法B．不分批计算在产品成本的分批法 C．不计算在产品成本的分批法 D. 不分批计算完工产品成本的分批法 10．为基本生产车间租用设备预付的租金按月摊销时，应借记的账户是( )。 A．“待摊费用”账户B．贷记“预提费用”账户 C. “制造费用”账户 D. “基本生产成本”账户 二、多项选择题(每小题2分，共14分) 1．下列各项中，不属于工业企业费用要素的是( )。 A．废品损失 B. 外购燃料 C. 制造费用 D. 直接材料 E．工资及福利费 4．下列各项中，不属于产品生产成本项目的是( )。 A．外购动力 B. 工资费用 C. 折旧费 D. 直接材料 E．燃料及动力 5．下列项目中，属于制造费用的有( )。 A. 生产车间的保险费B．厂部办公楼折旧 C. 在产品盘亏和毁损D．低值易耗品摊销 E. 季节性停工损失 7．一般来说，企业应根据本单位( )等具体情况与条件来组织成本会计工作。 A. 生产规模的大小B．生产经营业务的特点 C. 成本计算方法D．企业机构的设置
浅析指派问题的匈牙利解法 胡小芹 数学科学学院数学与应用数学学号:040414057 指导教师:苏孟龙 摘要:对于指派问题,可以利用许多理论进行建模并加以解决,但匈牙利解法是解决指派问题的一种非常简单有效的方法,并且可以解决多种形式的指派问题,但匈牙利算法本身存在着一些问题,本文主要介绍了匈牙利算法的基本思想,基本步骤,以及它的改进方法.在匈牙利算法的基础上,本文还介绍了两种更简便实用的寻找独立零元素的方法——最小零元素消耗法和对角线法. 关键词:指派问题;匈牙利解法;最小零元素消耗法;对角线法 0 引言 在现实生活中经常会遇到把几个任务分派给几个不同的对象去完成,由于每个对象的条件不同,完成任务的效率和效益亦不同.指派问题的目标就是如何分派使所消耗的总资源最少（或总效益最优）,如给工人分派工作,给车辆分配道路,给工人分配机床等等,同时许多网络问题（如旅行问题,任务分配问题,运输问题等）,都可以演化成指派问题来解决.在现实生活中,指派问题是十分常见的问题,而匈牙利解法是解决指派问题的一种非常简单有效的方法.本文主要介绍匈牙利解法的基本原理及思想,解题步骤,不足与改进,以使匈牙利法更能有效地解决指派问题. 1 指派问题及其数学模型 指派问题是指由m项任务,需要n个人来承担,每人只能承担一项任务,且每项
任务只能有一人来承担,由于各人的专长不同,各人完成的任务不同,导致其效率也各不相同.因此,就产生怎样科学地指派任务,才能使完成各项任务所消耗的总资源最少（或总成本最低等）,由于n m ,不同,指派问题可分为以下三种情况: 第一、当n m =时,即为每人指派一项任务. 第二、当n m >时,即任务数〉人数,这时可虚设)(n m -个人构成m m ?的 效率矩阵,并且这)(n m -个人在执行这m 项任务时的效率应该是效率最高. 第三、当n m <时,即配置人数〉任务数,这时应虚设)(m n -项任务,并且这n 个人在执行这)(m n -项任务时的成本最低. 通过虚设任务或人,指派问题的效率矩阵都可以转化成方阵.匈牙利解法要求指派问题最小化,其数学模型为 设用0ij c >(,1,2, ,)i j n =表示指派第i 个人去完成第j 项任务时所用的时间, 定义决策变量 10ij i j x i j ?=??表示第个人完成第项任务, 表示不指派第个人完成第项任务. 则问题可转化为0-1线性规划问题: ∑∑===n j ij n i c Z 11min t s ? 1 1 1,1,2,,, 1,1,2,,,01,i,j 1,2,,n n ij i n ij j ij x j n x i n x ==?==???==???==?? ∑∑或. 如果指派问题要求的是最大化问题如F max ,则可以转化为最小化问题,一般方法是:取max (,1,2 ),ij M c i j n ==令(,1,2,)ij ij b M c i j n =-=,则11 min ,n n ij i j f b ===∑∑,max F nM f F =-有从而求. 2 指派问题的解法——匈牙利解法
简化分批法例题 ［例］某厂生产有第0102009、记在“生产成本一一基本生产成本”定单的生产成本，如表7-6、7-7、0103004、0104001等定单产品，其成本和工时总数汇总登二级账中，如表7-5所示。第0102009、0103004、0104001 7-8所示。 基本生产成本二级账 表7- 200 X年4 累计工资及福利费分配率=5000/1000=5 （元/工时） 累计制造费用分配率=6000/1000=6 （元/工时）基 本生产成本二级账月末在产品直接材料费用 =23840+50000=73840 （元） 基本生产成本二级账月末在产品生产工时 =300+180=480 （工 时） 产品成本明细账表1 产品批号：0102009 开工日期：200 X年2月 产品名称: 批量：10台完工日期：200 X年4月 产品成本明细账 表2 产品成本明细账
开工日期：200 X 年4月5日 完工日期： 表3 产品批号：0104001
某厂属于小批生产，采用简化的分批法计算成本。 4月份生产情况如 （1） 月初在产品成本：101批号，直接材料3750元；102批号，直 接材料2200 元；103批号，直接材料1600元。月初直接人工1725 元，制造费用2350元。 （2） 小时； （3） 本月的生产情况，发生的工时和直接材料如下表所示： （4） （4）本月发生的各项间接费用为：直接人工1400元，制造费用2025 丿元。 要求：根据上述资料，登记基本生产成本二级帐和产品成本明细帐；计算完 工产品成本。 答案如下: 基本生产成本二级帐 产品成本明细帐 投产日期：2月 完工日期：4月 产量：10件 （分批法） 1、资料: 下： (1) (3) 习题 月初在产品耗用累计工时：101批号1800小时；102批号590 103批号960小时。 批号：101 产品名称：甲
匈牙利法解决人数与任务数不等的指派问题 于凯 重庆科技学院经济管理学院物流专业重庆沙坪坝区 摘要：本文将讨论运筹学中的指派问题，而且属于非标准指派问题，即人数与任务数不相等的指派问题，应当视为一个多目标决策问题，首先要求指派给个人任务数目两两之间相差不能超过1，其次要求所需总时间最少，并且给出了该类问题的求解方法。 关键词：运筹学指派问题匈牙利算法系数矩阵解矩阵 引言：在日常的生产生活中常遇到这样的问题：有n项任务，有n个人员可以去承担这n 项任务，但由于每位人员的特点与专长不同，各对象完成各项任务所用的时间费用或效益不同；有因任务性质要求和管理上需要等原因，每项任务只能由一个人员承担来完成，这就涉及到应该指派哪个人员去完成哪项任务，才能使完成n项任务花费总时间最短，总费用最少，产生的总效益最佳。我们把这类最优匹配问题称为指派问题或分配问题。 1.指派问题的解法——匈牙利法 早在1955年库恩（，该方法是以匈牙利数学家康尼格（koning）提出的一个关于矩阵中0元素的定理为基础，因此得名匈牙利法（The Hungonrian Method of Assignment） 1.1匈牙利解法的基本原理和解题思路 直观的讲，求指派问题的最优方案就是要在n阶系数矩阵中找出n个分布于不用行不同列的元素使得他们的和最小。 而指派问题的最优解又有这样的性质：若从系数矩阵C（ij）的一行（列）各元素都减去该行（列）的最小元素，得到新矩阵CB（ij），那么以CB（ij）为系数矩阵求得的最优解和原系数矩阵C（ij）求得的最优解相同。 由于经过初等变换得到的新矩阵CB（ij）中每行（列）的最小元素均为“○”，因此求原指派问题C（ij）的最优方案就等于在新矩阵CB（ij）中找出n个分布于不同行不同列的“○”元素（简称为“独立○元素”），这些独立○元素就是CB（ij）的最优解，同时与其对应的原系数矩阵的最优解。 1.2匈牙利法的具体步骤 第一步：使指派问题的系数矩阵经过变换在各行各列中都出现○元素。 （1）先将系数矩阵的每行中的每个元素减去本行中的最小元素。 （2）再从系数矩阵的每列中的每个元素减去本列的最小元素。 第二步：进行试指派，以寻求最优解。 （1）从含有○元素个数最少的行（列）开始，给某个○元素加圈，记作◎，然后划去与◎所在同行（列）杂其他○元素，记作?。（注：从含元素 少的开始标记◎的原则） （2）重复进行（1）的操作，直到所有○元素都记作◎或?，称作“礼让原则”。 （3）按以上方法操作后，若◎元素数目m’等于矩阵阶数n，那么指派问题最优解已得到。若m﹤n，则转入下一步。 第三步：做最少的直线覆盖所有的○元素，以确定该系数矩阵中能找到最多的独立○元素。 （1）对没有◎的行打√号； （2）对已打√号的行中含有?元素所在的列打√号； （3）对已打√号的列中含有◎元素所在的行打√号； （4）重复（2）、（3）直到得不到新√号的行和列为止； （5）对没有√号的行画一横线，有√号的列画一竖线。如此便可以覆盖所有
匈牙利算法是一种组合优化算法，可以在多项式时间内解决任务分配问题，并在以后推广原始的对偶方法。美国数学家哈罗德·库恩（Harold Kuhn）在1955年提出了该算法。该算法之所以称为匈牙利算法，是因为它很大程度上是基于前匈牙利数学家Denes K nig和Jen Egervary的工作。 假设它是无向图。如果顶点集V可以分为两个不相交的子集，则在该子集中选择具有最大边数的子集称为图的最大匹配问题。 如果存在匹配项和匹配项数，则该匹配项称为完美匹配项，也称为完全匹配项。称为完美匹配时的特殊。 在介绍匈牙利算法之前，只有几个概念，M是G的匹配项。 如果，则边缘已经在匹配的M上。 M交错的路径：P是G的路径。如果P中的边是属于M的边和不属于M而是属于G的边交替，则称P为M交错的路。如：路径，。 M饱和点：例如，如果V与M中的边关联，则V为m饱和点；否则，V为非M饱和点。例如，它们都属于M饱和点，而其他所有点都属于非M饱和点。 M扩展路径：P是M交错的路径。如果P的起点和终点均为非M饱和点，则P称为m增强路径。例如（不要与流网络中的增强路径混淆）。 寻找最多匹配项的一种明显算法是找到所有匹配项，然后保留最多匹配项。但是该算法的时间复杂度是边数的指数函数。因
此，我们需要找到一种更有效的算法。下面介绍使用增强路径查找最大匹配的方法（称为匈牙利算法，由匈牙利数学家爱德蒙兹（Edmonds）于1965年提出）。 增强轨道（也称为增强轨道或交错轨道）的定义： 如果P是连接图G中两个不匹配顶点的路径，并且属于M的边和不属于M的边（即已匹配和待匹配）在P上交替，则称P为扩充路径相对于M 从增强路径的定义可以得出以下三个结论： （1）到P的路径数必须是奇数，并且第一个边缘和最后一个边缘都不属于M。 （2）通过将M和P取反可以获得更大的匹配度。 （3）当且仅当没有M的增加路径时，M是G的最大匹配。 算法简介： （1）令M为空 （2）通过异或运算找到增强路径P并获得更大的匹配项而不是M （3）重复（2），直到找不到扩展路径。 时间复杂度邻接矩阵：最差的是邻接表： 空间复杂度的邻接矩阵：邻接表：