线性规划和匈牙利法

二、生产任务分配的匈牙利法在实际的生产管理工作中，常会遇到这样的问题，就是如何根据生产作业汁划将不同任务在不同的工人（或班组）之间分配，使完成任务总的消耗时间或费用最小。解决这类问题的简便而有效的方法是匈牙利法，它是由匈牙利数学家D.Konig所提出。例有4项任务A、B、C、D，分别由甲、乙、丙、丁4个人去完成，规定每人承担其中一项任务，不同的人完成同一任务所花时间（h）不同，见表3-3，求如何分配，使完成这4项任务的总时间最小。匈牙利法求解此问题的步骤是：1）按表3-3列出矩阵rll]1810T16538481094110102）将矩阵作行、列约简：首先进行行约简。在矩阵的每一行中选取最小元素，然后将该行的各元素都减去此数，得到如下新矩阵-413632050465弟502-行约简是比较一名工人担任不同任务时所花的时间，各行中减去最小值后的时间表示该工人担任其它任务时，所多花费的时间，每行中的‘0”表示该工人承担这项任务最有利。然后将经过行约筒后的矩阵中没有“0”的列再进行约简，即从该列中选出最小元素，并将其它元素减去此数，得到新矩阵件030]31050365〔6402」列约简是比较一项任务有不同工人承担所托时间，各列中减去最小值后的时间表示任务由其他工人担任时，所多花费的时间，每列中的“0”表示这项任务由该工人承担最有利。3）检验是否已得最优分配方案；作零的覆盖线，即对有“0”的行和列，划上一条覆盖线，能覆盖所有零元素的最少覆盖线数称为维数，当覆盖线的维数等于矩阵阶数时，可知已得最优分配方案，若维数小于阶数，再作调整。本例可用三条覆盖线覆盖住所有零元素，维数是3,矩阵的阶数是4,维数不等于阶数，因此矩阵还必须调整。TOC\o"1-5"\h\z——&-\o"CurrentDocument"If3f5§42、/4）矩阵的调整。在上述矩阵中.有三种元素，一种是无线覆盖元素，另一种是单线覆盖元素，还有一种是双线覆盖元素。在无线覆荒元素中找出最小值，本例为1”，将无线覆盖得元素都减去1，而双线覆盖的元素加上“1”，单线覆盖的元素不变。这样得到新矩阵lr040'30040264〔6301-5）再检验一一作覆盖线，方法与步骤3相同。现在的最少覆盖线数为4,与矩阵阶数相等，可知已能进行最优分配。6）确定最优分配方案。进行具体分配时，可以对只有一个零元素的列（行）先分配（记”号），分配后，划去与该零元素同行（列）的其他零元素（记X号）这样依改做完各列（行），得到分配结果。如果矩阵能通过直接观察找到位于不同行不同列的零元素，那么就可以直接确定分配方案。/x；TOC\o"1-5"\h\z54时34"264、63W1最优分配方案：甲一一D，乙一一B，丙一一A，T——C。总消耗工时为：Z=7+5+4+5=21（h）。3141()51041210914151378119-01130'「中113O'604460*4405220*5220100［中100_211301「中1130*-6(T4460*44*0*，522*0*522_410*［中10*寺0001010010000010minT=3•。+14•0+1()•0+5•1