管理运筹学——匈牙利法

第一步：效率矩阵的初始变换----零元素的获得

（1）行变换：找出每行的最小元素，该行各元素减去这个最小元素。

（2）列变换：找出每列的最小元素，该列各元素减去这个最小元素。

经变换后的效率矩阵，其每行、每列至少有一个零元素。

第二步：最优性检验

检查能否找到m个位于不同行、不同列的零元素，即检查覆盖所有零元素的直线是否为m条

（1）逐行检查：从第一行开始，如果该行只有一个零元素，就在这个

零元素上打上括号，并划去打括号零元素同列的其他零元素。

如果该行没有零元素，或有两个或多个零元素（已划去的不记在

内），则转下行

（2）逐列检查：依照行检查的方法从第一列开始逐列检查。

最优性检验后可能可能出现的情况

①每行都有一个零元素标有括号，显然这些括号零在不同行

和不同列，因此得到最优解。

②每行、每列都有两个或更多的零，这是从剩有零元素最少的

行开始，比较这行各零元素所在列中零元素的个数，选择零

元素少的那列的这个零元素打括号，划掉同行同列的其他零

元素，然后重复以上步骤，直到所有零都做了标记。

③矩阵中所有零都做了标记，但标有（）的零元素个数少于

m，此时就可以找出能覆盖矩阵中所有零元素的最少直线的

集合。

步骤如下：

步骤如下：

对无（）的行打√

对打√行上所有零元素的列打√

在打√的列上有（）的行打√

重复步骤，直到过程结束

对没有打√的行划横线，对所有打√的列划垂线，这时得

到覆盖矩阵中所有零的最少直线数

第三步：非最优阵的变换——零元素的移动

当表中的覆盖所有零的直线数小于m时，得到的不是最优解，因此需要对表中矩阵进一步进行变换，过程如下：

①在未被直线覆盖的所有元素中找出最小元素

②所有未被直线覆盖的元素都减去这个最小元素

③覆盖线十字交叉处的元素都加上这个最小元素

④只有一条直线覆盖的元素的值保持不变。

由此，得到新的效率矩阵，以此更易标出m个不同的行和列的零元素。

第四步：重新标号

抹掉原来的标号，回到最优性检验，并进行重新标号，直到得到最优解7 9 10 12

13 12 16 17

15 16 14 15

11 12 15 16

第九章分批法练习题参考答案

第九章分批法练习题参考答案 一、某工业企业生产甲、乙两种产品。生产组织属于小批生产，采用分批法计算成本。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

运筹学试题及答案

运筹学A卷) 一、单项选择题(从下列各题四个备选答案中选出一个正确答案,答案选错或未选者,该题不得分。每小题1分,共10分) 1.线性规划具有唯一最优解就是指 A.最优表中存在常数项为零 B.最优表中非基变量检验数全部非零 C.最优表中存在非基变量的检验数为零 D.可行解集合有界 2.设线性规划的约束条件为 则基本可行解为 A.(0, 0, 4, 3) B.(3, 4, 0, 0) C.(2, 0, 1, 0) D.(3, 0, 4, 0) 3.则 A.无可行解 B.有唯一最优解medn C.有多重最优解 D.有无界解 4.互为对偶的两个线性规划, 对任意可行解X 与Y,存在关系 A.Z > W B.Z = W C.Z≥W D.Z≤W 5.有6 个产地4个销地的平衡运输问题模型具有特征 A.有10个变量24个约束

B.有24个变量10个约束 C.有24个变量9个约束 D.有9个基变量10个非基变量 6、下例错误的说法就是 A.标准型的目标函数就是求最大值 B.标准型的目标函数就是求最小值 C.标准型的常数项非正 D.标准型的变量一定要非负 7、m+n－1个变量构成一组基变量的充要条件就是 A.m+n－1个变量恰好构成一个闭回路 B.m+n－1个变量不包含任何闭回路 C.m+n－1个变量中部分变量构成一个闭回路 D.m+n－1个变量对应的系数列向量线性相关 8.互为对偶的两个线性规划问题的解存在关系 A.原问题无可行解,对偶问题也无可行解 B.对偶问题有可行解,原问题可能无可行解 C.若最优解存在,则最优解相同 D.一个问题无可行解,则另一个问题具有无界解 9、有m个产地n个销地的平衡运输问题模型具有特征 A.有mn个变量m+n个约束…m+n-1个基变量 B.有m+n个变量mn个约束 C.有mn个变量m+n－1约束 D.有m+n－1个基变量,mn－m－n－1个非基变量 10.要求不超过第一目标值、恰好完成第二目标值,目标函数就是

人力资源级匈牙利法解题思路

匈牙利法 假定甲单位有甲、乙、丙、丁、戊五个员工，需要在一定的生产技术组织条件下，完成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

运筹学试题及答案汇总

3）若问题中 x2 列的系数变为（3，2）T，问最优解是否有变化； 4）c2 由 1 变为 2，是否影响最优解，如有影响，将新的解求出。 Cj CB 0 0 Cj-Zj 0 4 Cj-Zj 3 4 Cj-Zj 最优解为 X1=1/3,X3=7/5,Z=33/5 2对偶问题为Minw=9y1+8y2 6y1+3y2≥3 3y1+4y2≥1 5y1+5y2≥4 y1,y2≥0 对偶问题最优解为 y1=1/5,y2=3/5 3 若问题中 x2 列的系数变为（3，2）T 则P2’=(1/3,1/5σ2=-4/5＜0 所以对最优解没有影响 4）c2 由 1 变为2 σ2=-1＜0 所以对最优解没有影响 7. 求如图所示的网络的最大流和最小截集(割集，每弧旁的数字是（cij , fij ）。（10 分） V1 (9,5 (4,4 V3 (6,3 T 3 XB X4 X5 b 9 8 X1 6 3 3 X4 X3 1 8/5 3 3/5 3/5 X1 X3 1/3 7/5 1 0 0 1 X2 3 4 1 -1 4/5 -11/5 -1/3 1 - 2 4 X 3 5 5 4 0 1 0 0 1 0 0 X4 1 0 0 1 0 0 1/3 -1/ 5 -1/5 0 X5 0 1 0 -1 1/5 -4/5 -1/3 2/5 -3/5 VS (3,1 (3,0 (4,1 Vt (5,3 V2 解： (5,4 (7,5 V4 V1 (9,7 (4,4 V3 (6,4 (3,2 Vs (5,4 (4,0 Vt (7,7 6/9 V2 最大流＝11 (5,5 V4 8. 某厂Ⅰ、Ⅱ、Ⅲ三种产品分别经过 A、B、C 三种设备加工。已知生产单位各种产品所需的设备台时，设备的现有加工能力及每件产品的预期利润见表：ⅠⅡⅢ设备能力(台.h A 1 1 1 100 B 10 4 5 600 C 2 2 6 300 单

运筹学试题及答案4套

《运筹学》试卷一 一、（15分）用图解法求解下列线性规划问题 二、（20分）下表为某求极大值线性规划问题的初始单纯形表及迭代后的表，、 为松弛变量，试求表中到的值及各变量下标到的值。 -13 1 1 6 1 1-200 2-1 1 1/2 1/2 1 4 07 三、（15分）用图解法求解矩阵对策， 其中 四、（20分） （1）某项工程由8个工序组成，各工序之间的关系为 工序a b c d e f g h 紧前工序——a a b,c b,c,d b,c,d e 试画出该工程的网络图。 （2）试计算下面工程网络图中各事项发生的最早、最迟时间及关键

线路（箭线下的数字是完成该工序的所需时间，单位：天） 五、（15分）已知线性规划问题 其对偶问题最优解为，试根据对偶理论求原问题的最优解。 六、（15分）用动态规划法求解下面问题：

七、（30分）已知线性规划问题 用单纯形法求得最优单纯形表如下，试分析在下列各种条件单独变化的情况下，最优解将如何变化。 2 -1 1 0 0 2 3 1 1 3 1 1 1 1 1 6 10 0 -3 -1 -2 0 （1）目标函数变为； （2）约束条件右端项由变为； （3）增加一个新的约束： 八、（20分）某地区有A、B、C三个化肥厂向甲、乙、丙、丁四个销地供应同一种化肥，已知产地产量、销地需求量和各产地运往不同销地单位运价如下表，试用最小元素法确定初始调运方案，并调整求最优运输方案 销地 产地 甲乙丙丁产量 A41241116 B2103910

C8511622需求量814121448 《运筹学》试卷二 一、（20分）已知线性规划问题： （a）写出其对偶问题； （b）用图解法求对偶问题的解； （c）利用（b）的结果及对偶性质求原问题的解。 二、（20分）已知运输表如下： 销地 产地B1B2B3B4供应量 50 A 1 3 2 7 6 A 2 60 7 5 2 3 25 A 3 2 5 4 5 需求量60 40 20 15 （1）用最小元素法确定初始调运方案； （2）确定最优运输方案及最低运费。 三、（35分）设线性规划问题 maxZ=2x1+x2+5x3+6x4

匈牙利算法

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于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。

运筹学试题及答案.

运筹学试题及答案 一、填空题(本大题共8小题，每空2分，共20分) 1．线性规划问题中，如果在约束条件中出现等式约束，我们通常用增加__人工变量_的方法来产生初始可行基。2．线性规划模型有三种参数，其名称分别为价值系数、_技术系数 __和__限定系数_。 3．原问题的第1个约束方程是“=”型，则对偶问题相应的变量是__无非负约束(或无约束、或自由)_变量。 4．求最小生成树问题，常用的方法有：避圈法和 _破圈法__。 5．排队模型M／M／2中的M，M，2分别表示到达时间为__负指数_分布，服务时间服从负指数分布和服务台数为2。 6．如果有两个以上的决策自然条件，但决策人无法估计各自然状态出现的概率，那么这种决策类型称为__不确定__型决策。 7．在风险型决策问题中，我们一般采用__效用曲线_来反映每个人对待风险的态度。 8．目标规划总是追求目标函数的_ 最小 __值，且目标函数中没有线性规划中的价值系数，而是在各偏差变量前加上级别不同的__ 优先因子(或权重)__。 二、单项选择题(本大题共l0小题，每小题3分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。多选无分。 9．使用人工变量法求解极大化线性规划问题时，当所有的检验数在基变量中仍含有非零的人工变量，表明该线性规划问题【 D 】 A．有唯一的最优解 B．有无穷多最优解 C．为无界解 D．无可行解 10．对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中【 D 】 A．b列元素不小于零 B．检验数都大于零 C．检验数都不小于零 D．检验数都不大于零 11．已知某个含10个结点的树图，其中9个结点的次为1，1，3，1，1，1，3，1，3，则另一个结点的次为【 A 】A．3 B．2 C．1 D．以上三种情况均有可能 12．如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足【 B 】 13．在运输方案中出现退化现象，是指数字格的数目【 C 】 A．等于 m+n B．等于m+n-1 C．小于m+n-1 D．大于m+n-1 16．关于线性规划的原问题和对偶问题，下列说法正确的是【 B 】 A．若原问题为无界解，则对偶问题也为无界解 B．若原问题无可行解，其对偶问题具有无界解或无可行解 c．若原问题存在可行解，其对偶问题必存在可行解

最全的运筹学复习题及答案78213

最全的运筹学复习题及 答案78213

四、把下列线性规划问题化成标准形式： 2、minZ=2x1-x2+2x3 五、按各题要求。建立线性规划数学模型 1、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示：

根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销售量分别为250，280和120件。月销售分别为250 ，280和120件。问如何安排生产计划，使总利润最大。 2、某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋 90根，长度为4米的 钢筋60根，问怎样下料，才能使所使用的原材料最省? 1．某运输公司在春运期间需要24小时昼夜加班工作，需要的人员数量如下表所示：起运时间服务员数 2—6 6—10 10一14 14—18 18—22 22—2 4 8 10 7 12 4 每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数最少?

五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相 当于图解法可行域中的哪一个顶点。

六、用单纯形法求解下列线性规划问题： 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。

八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x1+3x2，约束形式为“≤”，X3，X4为松驰变量．表中解代入目标函数后得Z=10 X l X2X3X4 —10 b -1 f g X3 2 C O 1 1／5 X l a d e 0 1 (1)求表中a～g的值 (2)表中给出的解是否为最优解? （1）a=2 b=0 c=0 d=1 e=4/5 f=0 g=－5 （2）表中给出的解为最优解 第四章线性规划的对偶理论 五、写出下列线性规划问题的对偶问题 1．minZ=2x1+2x2+4x3

可以直接用的匈牙利算法

将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日

线性规划和匈牙利法

二、生产任务分配的匈牙利法 在实际的生产管理工作中，常会遇到这样的问题，就是如何根据生产作业汁划将不同任务在不同的工人(或班组)之间分配，使完成任务总的消耗时间或费用最小。解决这类问题的简便而有效的方法是匈牙利法，它是由匈牙利数学家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件

最全的运筹学复习题及答案

四、把下列线性规划问题化成标准形式： 2、minZ=2x1-x2+2x3 五、按各题要求。建立线性规划数学模型 1、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示：

根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销售量分别为250，280和120件。月销售分别为250，280和120件。问如何安排生产计划，使总利润最大。 2、某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋90根，长度为4米的钢筋60根，问怎样下料，才能使所使用的原材料最省 1．某运输公司在春运期间需要24小时昼夜加班工作，需要的人员数量如下表所示： 起运时间服务员数 2—6 6—10 10一14 14—18 18—22 22—2 4 8 10 7 12 4 每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数最少

五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相当 于图解法可行域中的哪一个顶点。

六、用单纯形法求解下列线性规划问题： 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。

八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x1+3x2，约束形式为“≤”，X3，X4为松驰变量．表中解代入目标函数后得Z=10 X l X2X3X4 —10b-1f g X32C O11／5 X l a d e01 (1)求表中a～g的值 (2)表中给出的解是否为最优解 （1）a=2 b=0 c=0 d=1 e=4/5 f=0 g=－5 （2）表中给出的解为最优解 第四章线性规划的对偶理论 五、写出下列线性规划问题的对偶问题 1．minZ=2x1+2x2+4x3

匈牙利算法

匈牙利算法(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个。不断执行上述操作，直到找不到这样的路径为止。 下面给出此算法的一个例子：

运筹学试题及答案.doc

运筹学A 卷） 一、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分。每小题1 分，共10 分） 1．线性规划具有唯一最优解是指 A ．最优表中存在常数项为零 B ．最优表中非基变量检验数全部非零 C．最优表中存在非基变量的检验数为零 D．可行解集合有界 2．设线性规划的约束条件为 则基本可行解为 A ．(0, 0, 4, 3) B ．(3, 4, 0, 0) C．(2, 0, 1, 0) D ．(3, 0, 4, 0) 3．则 A ．无可行解 B ．有唯一最优解medn C．有多重最优解D．有无界解 4．互为对偶的两个线性规划,对任意可行解X 和Y，存在关系 A ．Z > W B．Z = W C．Z≥W D ．Z≤W 5．有6 个产地4 个销地的平衡运输问题模型具有特征 A ．有10 个变量24 个约束 B ．有24 个变量10 个约束 C．有24 个变量9 个约束 D．有9 个基变量10 个非基变量

6. 下例错误的说法是 A ．标准型的目标函数是求最大值 B ．标准型的目标函数是求最小值 C．标准型的常数项非正 D．标准型的变量一定要非负 7. m+n －1 个变量构成一组基变量的充要条件是 A ．m+n－1 个变量恰好构成一个闭回路 B ．m+n－1 个变量不包含任何闭回路 C．m+n－1 个变量中部分变量构成一个闭回路 D．m+n－1 个变量对应的系数列向量线性相关 8．互为对偶的两个线性规划问题的解存在关系 A ．原问题无可行解，对偶问题也无可行解 B ．对偶问题有可行解，原问题可能无可行解 C．若最优解存在，则最优解相同 D．一个问题无可行解，则另一个问题具有无界解 9. 有m个产地n 个销地的平衡运输问题模型具有特征 A．有mn个变量m+n个约束?m+n-1 个基变量 B ．有m+n个变量mn个约束 C．有mn个变量m+n－1约束 D．有m+n－1 个基变量，mn－m－n－1 个非基变量10．要求不超过第一目标值、恰好完成第二目标值，目标函数是 A ． B ． C．

匈牙利解法的步骤

指派问题的匈牙利法求解步骤： 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步。

运筹学课后习题答案

第一章 线性规划 1、 由图可得：最优解为 2、用图解法求解线性规划： Min z=2x 1+x 2 ????? ??≥≤≤≥+≤+-01058 2442 12121x x x x x x 解： 由图可得：最优解x=1.6,y=6.4

Max z=5x 1+6x 2 ? ?? ??≥≤+-≥-0 ,23222212 121x x x x x x 解： 由图可得：最优解Max z=5x 1+6x 2, Max z= +∞

Maxz = 2x 1 +x 2 ????? ? ?≥≤+≤+≤0,5242261552121211x x x x x x x 由图可得：最大值?????==+35121x x x ， 所以?????==2 3 21x x max Z = 8.

12 12125.max 2328416412 0,1,2maxZ .j Z x x x x x x x j =+?+≤? ≤?? ≤??≥=?如图所示，在（4，2）这一点达到最大值为2 6将线性规划模型化成标准形式： Min z=x 1-2x 2+3x 3 ????? ??≥≥-=++-≥+-≤++无约束 321 321321321,0,05232 7x x x x x x x x x x x x 解：令Z ’=-Z,引进松弛变量x 4≥0，引入剩余变量x 5≥0，并令x 3=x 3’-x 3’’,其中 x 3’≥0,x 3’’≥0 Max z ’=-x 1+2x 2-3x 3’+3x 3’’ ????? ? ?≥≥≥≥≥≥-=++-=--+-=+-++0 ,0,0'',0',0,05 232 '''7'''543321 3215332143321x x x x x x x x x x x x x x x x x x x

(完整版)成本会计期末考试试题及答案

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．企业机构的设置