用改进的匈牙利算法求解运输问题
用改进的匈牙利算法求解运输问题
李雪娇，于洪珍
中国矿业大学信电学院，江苏徐州 (221008)
Email ：liaohuchushan@https://www.sodocs.net/doc/114775194.html,
摘 要：本文提出用改进的匈牙利算法求解运输问题。此算法不但可以直接求取最优解，而且在运量受限制的运输问题中有很好的应用。
关键词：改进，匈牙利算法，运输问题，最优解
0. 引言
在现实生活中，我们常常会遇到许多运输问题。运输问题的求解多采用表上作业法。在此方法中，我们需要先利用最小元素法或西北角法求出一组基本可行解，再对此解检验其最优性。若此解非最优解，则又要进行解的改进。这一过程比较麻烦，尤其对一些结构不太大的模型，编程时往往过于繁琐。
同时，经典运输问题在实际应用中有很大的局限性, 对一些运输量受限制或运输能力受限制的运输问题，我们无法用表上作业法直接求取。在此，我们采用改进的匈牙利算法处理这类运输问题。为了便于描述，设物资供应量12[...]m A a a a =，物资需求量12[...]n B b b b =，从到i A j B 的单物的物资运价，最小运输量 (假设m )。
i j C i j L n >1. 匈牙利算法[1][4]
匈牙利算法的基本思想是修改效益矩阵的行和列，使得每行和每列中至少有一个零元素。经过一定的变换，得到不同行、不同列只有一个零元素。从而得到一个与这些零元素相匹配的完全分配方案。这种方法总是在有限步内收敛于一个最优解。该方法的理论基础是：在效益矩阵的任何行或列中，加上或减去一个常数后不会改变最优解的分配。求解步骤如下：
第一步：使指派问题的系数矩阵经变换后，在各行各列中都出现零元素，即从系数矩阵的每行（或列）元素中减去该行（或列）的最小元素。
第二步：寻求找n 个独立的零元素，以得到最优解：（1）从只有一个0元素的行（或列）开始，对这个0元素加圈，记为θ。然后划去此元素所在列（或行）的其他0元素，记作?。反复进行，直到所有的0元素被划完。（2）若仍有没有划圈的0元素，则从剩有0元素最少的行开始，比较这行0元素所在各列中0元素的数目，选择0元素少的那列的0元素加圈θ，然后划掉同行同列的其他0元素，反复进行直到所有的0元素被划掉或圈出。
（3）若元素的数目m 等于矩阵的阶数，那么指派问题的最优解已得到。若m ，则转入下一步。
n n <第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数：若l ，必须再变换当前的系数矩阵，才能找到个独立的0元素，为此转第四步；若l ，而，应回到第二步（2），另行试探。
n √ 2. 改进的匈牙利算法 2.1 算法思想 以最小运输量为分配目标，每次分配都为当前已分配的最优解，因此，当完成所有运输任务后，得到的是一个全局最优解。同时，由于匈牙利算法解决的指派问题具有0-1整形和运输问题的双重特点。因此，改进的匈牙利算法可以解决有运量限制或存在相互排斥条件的运输问题。 由于在匈牙利算法中，效益矩阵的任何行或列加上或减去一个常数后不会改变最优解的分配，所以运用匈牙利算法可以使得初始可行解对应的目标函数值显著减小,使之更为逼近最优解，从而减少迭代次数、减少计算量。 2.2 具体实现步骤 1. 将不平衡指派转化为平衡指派问题 设置一些虚拟的行或列向量，以0元素填充，使得矩阵变为一个C m m ×的方阵。 2. 找出Α,向量中的最小值，记录下该最小值所在的向量及坐标。将此最小值和L 中的最小非零值比较，得出三者中的最小。若L 中的非零值较小且L 较大时，只需记录此非零值及其对应的行和列。 Βi j L 3. 若最小值在或A B 向量中，直接对矩阵C 运用匈牙利算法求得最优指派矩阵()M i 。若在中，则将最小值在中对应的行和列删除，再用匈牙利算法求得一最优分配矩阵L i j L C ()M i ，在()M i 矩阵中添加第i 行和第j 列，使得ij M 处为1，其余添加元素为0。将向量、A B 中已分配部分减去该最小值，除去含零向量中的零元素，得到一组新的向量、A B 。将的最小非零值置零。 L 4. 将缩减的矩阵中恢复成m 矩阵。对已缩减掉的元素用0填充。若最小值在中，则将第行、n ×L i j 列的元素置1，其它元素不变。 5. 重置矩阵C 。假设该最小值为行（或列）的第个元素，则删除C 中第k 行（或第列），得到一个新的效益矩阵C 。 k k 6. 重复1~5，直到、A B 中的元素全为0。 7. 将矩阵()M i 经加权后得矩阵。则矩阵即为最优分配方案。 ()d i S S 3. 算例分析 3.1 问题 某公司经销甲产品。它下设三个加工厂。每日的产量分别为：A 1为7吨， 为4吨，为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销售为：A 2A 3B 1为3吨，B 2为6吨，B 3为5吨，B 4为6吨。要求A 1厂的产品至少分配2吨给B 3。已知从各工厂到销售点的单位产品的运价如表1下：问该公司如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。 表1 3.2 求解过程 第一步：添加（假设）个虚拟的加工厂，并赋予加工厂到销售点完成这些虚拟运输的费用为0。此时，问题转化为产地和销售点数目相等的指派问题。 m n ?m n >3113101928741050000C ??????=?????? 第二步：列出描述生产量和销售量的向量及约束矩阵，比较得出最小值。 13L [749]A = [3656]B =(1)min(,)d A B = 132L = 第三步；用匈牙利算法求解，得出运输量都为的分配方案，矩阵中的表示第个生产商运输货物到第13L (1)M 1ij m =i j 个销售点。完成第一次分配以后，重新计算各生产点的货物量和销售点的需求量,得到新的向量、A B 。 10010(1)10000100C M 6θ4??????θ5?3????=?=????6θ8??????????θ?? [527]A = [1436]B = 3113101928741050000C ??????=?????? 第四步：从上面的分配可以看出，B 1销售点的需求量得到满足。将B 1（最小值所在的位置）从B 删除。重新组合、A B 得到新的矩阵。 C 10010(2)10000100C M 6θ4??????θ5?3????=?=????6θ8??????????θ?? [416]A =[0326]B =[326]B = 第五步：重复步骤1~4，实现剩余量的再分配： 1）.循环三： 113103*********(3)00014105110100C C M θθθ??????????=?=??=????????????????????? [35]A =[215]B =113104105C ??=???? 在此分配过程中，我们得到第二次分配方案。此时，A (3)M 2产品全部销售完，还有、A A 13、B 2、B 3、B 4尚待分配，重新组合后得到上面的矩阵C 。 2）.循环四：对矩阵设置虚拟的行，然后用匈牙利算法直接求取。 C (3)1d = 113575001041057(4)00000000100C C M θθθ??????????=?=??=?????????????????????? [24]A =[15]B = 在此过程中，B 3的需求量得到满足，B 3不再参与分配。 3）.循环五、六、七的结果如下： (4)1d = 000111101(5)00004510100C C M θθ????????=?=?=?????????????? [13]A = [4]B =00001005(6)0000500001C C M θθ????????=?=?=???????????????0001(7)00000000M ????=?????? 执行完以上三次循环后，、A B 矩阵全都为空。此时，分配完成。 第六步：利用系数加权，我们求得分配结果为S ，S 得到最优运输方案。 01000100010000131 0001000110000100000 1000100010001000 0000001005230 000100003001000100000603S ????????????????=×+×+×+×????????????????????????????????????+×+×=?????????????????? 随着产品的不断分配，生产点和销售点的生产和需求不断被满足，反映在矩阵C不断变小，从而在若干步长内收敛完全，完成整个运输过程。 4 结论 本文主要研究了运输量受约束的运输问题，并提出了改进的匈牙利算法求得最优解，给出了算法实例，说明了改进的匈牙利算法应用于运输问题的求解时可以实现对运输量限制的最优分配，具有较强的可行性。在结构不大的运输问题中或产量和销量中有许多相等量的大结构中，可以实现算法的快速收敛。 参考文献 [1]《运筹学》教材编写组. 《运筹学》（第三版）,北京清华大学出版社 2005 [2] 朱德通编. 《运筹学》, 上海人民出版社 2000 [3] 胡运全主编郭耀煌副主编.《运筹学教程》（第二版） , 北京清华大学出版社 2003 [4]焦吉成《对匈牙利算法的改进及其应用实例》山东冶金第22卷第二期 2000.4 Use the Improved Hungry Algorithm to Solve Transportation Problem Li Xuejiao，Yu Hongzhen The School of Information and Electrical Engineering of China University of Mining and Technology, Xuzhou (221008) Abstract Developed Hungry algorithm was given to solve the transportation problem in this paper. Using this algorithm you can get the optimal solution directly,and while ,it can make good use in transport problems with quantity limits . Keywords:Improved Hungry Algorithm Transportation problem Optimal solution 作者简介：李雪娇，20岁，女，汉族，山东省临沂市郯城县。中国矿业大学信息与电气工程学院信息专业03级大学生。主要从事信息处理方面的学习。在数学学习上有很大的兴趣，曾在全国大学生数学建模竞赛中获得江苏赛区二等奖。 第九章分批法练习题参考答案 一、某工业企业生产甲、乙两种产品。生产组织属于小批生产，采用分批法计算成本。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; 分批法课堂练习 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； 匈牙利法解决人数与任务数不等的指派问题 于凯 重庆科技学院经济管理学院物流专业重庆沙坪坝区 摘要：本文将讨论运筹学中的指派问题，而且属于非标准指派问题，即人数与任务数不相等的指派问题，应当视为一个多目标决策问题，首先要求指派给个人任务数目两两之间相差不能超过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）对没有√号的行画一横线，有√号的列画一竖线。如此便可以覆盖所有 简化分批法例题 [例]某厂生产有第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．企业机构的设置 指派问题的算法分析与实现 摘要 在企业、公司的运营与管理中，管理者总是希望把人员最佳分派以发挥其最大工作效率，从而降低成本、提高效益。然而，如果没有科学的方法是很难实现优化管理的，由此我们引入了指派问题。指派问题多是求项目的工时最少，而很多情况下人们并不关心项目总工时的多少，而只关心项目能否在最短的时间内完成，即历时最少的指派问题。这类问题研究的是n个人执行n项任务，执行每项任务的人数以及总的指派人项数均有限制，要求最优指派。在运筹学中求解整数规划的指派问题通常是通过匈牙利算法来求解，但指派问题也可以归结为一个0-1整数规划问题，本文先对指派问题进行陈述，引出对实际问题的求解。在指派问题的背景、描述中充分理解该问题，先运用匈牙利算法实现指派问题，然后再建立一个0-1整数规划模型，并运用matlab和lingo编译程序对问题进行编译，运用软件解决模型问题，最终实现指派问题在实际问题中的运用。通过运用匈牙利算法和0-1整数规划同时对指派问题求解，我们发现用0-1整数规划的方法来求解可以更简单，也更方便程序的阅读和理解。与此同时，我们还对0-1整数规划问题由整数数据深入研究到小数数据。最后通过实例来说明运用matlab，lingo编译程序来解决整数规划问题的简便和有效性。 关键词：指派问题；匈牙利算法；0-1整数规划；matlab模型；lingo模型1. 问题陈述 指派问题又称分配问题，其用途非常广泛，比如某公司指派n个人去做n 件事，各人做不同的事，如何安排人员使得总费用最少？若考虑每个职工对工作效率（如熟练程度等），怎样安排会使总销量达到最大？这些都是一个企业经营 管理者必须考虑的问题，所以该问题有重要的应用价值。 假设有n 件工作分派给n 个人来做，每项工作只能由一人来做，每个人只能做一项工作。若给出各人对各项工作所具有的工作效率。问应该如何安排人选，及发挥个人特长又能使总的效率最大。为此用0-1整数规划来实现指派问题即如何安排人选。 2.背景 在现实生活中，有各种性质的指派问题（Assignment Problem ）。例如，在生产管理中，总希望把人员进行最佳分配，以发挥最大的工作效率；某部门有n 项任务要完成，而该部门正好有n 个人可以分别去完成其中任何一项，但由于任务性质和个人的专长不同，因此各人完成各项不同任务的效益（所费时间或所花费用）也有差别，如果分配每个人完成一项任务且仅为一项任务，则把每项任务分配给哪个人去完成，使完成所有n 项任务的总效益为最高（总时间、总费用为最小或创造的价值最大）？这是典型的分配问题或指派问题。又如有n 项加工任务，怎样指定n 台机器分别去完成，以使总的加工时间最少或总收入最大；有n 条航线，怎样指定n 艘船分别航行，使总收入最大，等等，都属于指派问题。 3. 指派问题的描述 3.1 指派问题的一般形式 指派问题的标准形式（以人和事为例）如下。有n 个人和n 项任务，已知第i 个人做第j 件事的费用为 ij c ，要求确定人和事之间的一一对应的指派方案，使 完成这n 项任务的费用最少。 一般把目标函数的系数写为矩阵形式，称矩阵 ? ? ? ? ?? ? ? ? ? ??????????==?nn n n n n n n ij c c c c c c c c c c C ..................)(212222111211 为系数矩阵（Coefficient Matrix ），也称为效益矩阵或价值矩阵。矩阵的元 简化分批法例题 ［例］某厂生产有第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 产品名称：甲 匈牙利算法是一种组合优化算法，可以在多项式时间内解决任务分配问题，并在以后推广原始的对偶方法。美国数学家哈罗德·库恩（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），直到找不到扩展路径。 时间复杂度邻接矩阵：最差的是邻接表： 空间复杂度的邻接矩阵：邻接表： 浅析指派问题的匈牙利解法 胡小芹 数学科学学院数学与应用数学学号: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 指派问题的解法——匈牙利解法 《成本会计》复习题 一、判断题 l．“废品损失”科目月末应无余额。 2．划分产品成本计算基本方法的标志是成本计算对象。 3．在月末未完工产品批数较多的情况下，不适宜采用简化的分批法。 4．在平行结转分步法下，只能采用定额比例法进行产成品和在产品之间的费用分配。 5．分类法不需要分产品品种计算成本，因而产品成本明细账可按类别设置。 6．产品的定额成本与计划成本的相同之处在于，它们均是以产品生产耗费的消耗定额和计划价格为依据确定的目标成本。 7．为了规范企业成本信息的对外披露，国家对成本报表的种类、项目、格式和编制方法均作了统一规定。 8．在实际工作中，某些不形成产品价值的损失，也可作为生产费用计入产品成本。 9．产品成本是指企业在一定时期内发生的、用货币表现的生产耗费。 10．在成本核算中，应该正确划分完工产品与在产品的费用界限防止任意提高或降低月末在产品费用，人为调节完工产品的成本。 11．在只生产一种产品的工业企业或车间中，直接生产费用和间接生产费用都是直接计入费用。（） 12．凡是费用发生时间和企业受益时间不一致的费用，?均通过"待摊费用"帐户进行核算。( ) 13．如果将生产经营管理费用误记为非生产经营管理费用，企业将虚增本期的利润，而以后相关期间的利润被虚减。（） 14．在成本核算中，应该正确划分完工产品与在产品的费用界限，防止任意提高或降低月末在产品费用，人为调节完工产品的成本。（） 15．采用分项逐步结转分步法时，月末在产品应负担的上车间(步骤)?转入费用应该等于上车间转入费用除以上车间转入的半成品数，再乘以在产品的约当产量。( ) 16．在实际工作中，为简化核算，有关三包范围内的废品损失，?发生时可直接计入"管理费用"科目。( ) 17．工业企业的生产费用是指企业在生产经营管理过程中发生的费用总额。（）18．采用分批法计算产品成本，在批内部分完工产品按计划单位成本计算结转后，待该批产品全部完工后，还应计算该批产品实际总成本，并调整前期完工产品实际成本与计划成本的差异。（） 19．企业必须按时对外披露成本信息。（） 20．辅助生产费用按直接分配法分配最简单；按代数分配法分配最正确；按计划成本法分配可简化计算工作并能分清经济责任。（） 参考答案：1―5．√√×××6―10．√×√×√ 11.－15. √××√× 16.－20. √×××√第九章分批法练习题参考答案
指派问题的匈牙利解法
人力资源级匈牙利法解题思路
分批法例题及答案
运筹学指派问题的匈牙利法实验报告
匈牙利算法
可以直接用的匈牙利算法
成本会计练习分批法及答案
指派问题的解法
匈牙利法解决人数及任务数不等的指派问题
简化分批法例题
匈牙利算法
匈牙利解法的步骤
(完整版)成本会计期末考试试题及答案
指派问题的算法
简化分批法例题
匈牙利算法
浅析指派问题的匈牙利解法成稿讲解
《成本会计》习题含答案