运输问题的匈牙利解法和表上作业法
运输问题的解法
运输问题是一类特殊的线性规划问题，最早是从物质调运工作中提出的，后来又有许
多其它问题也归结到这一类问题中。正是由于它的特殊结构，我们不是采用线性规划的单纯方法求解，而是根据单纯形方法的基本原理结合运输问题的具体特性须用表上作业的方法求解。
§1 运输问题的数学模型及其特性
1.1 运输问题的数学模型
设有 个地点（称为产地或发地）
的某种物资调至
个地点（称为销
地或收地） ，各个发点需要调出的物资量分别为 个单位，各个收点需要调进的物资量分别为 个单位。已知每个发点 到每个收点 的物
资每单位运价为 ，现问如何调运，才能使总的运费最小。我们把它列在一张表上（称为
运价表）。设 表示从产地 运往 销地的运价（ =1，2，…， ； =1，2，…，
）。
表3-1
如果（总发量）
（总收量），我们有如下线性规划问题：
m m A A A ,,,21 n n B B B ,,,2
1 m a a a ,,,21 n b b b ,,,21 i A
j B ij c
ij x i A j B i m j
n ∑∑===m i n
j ij
ij x c z 11
min
（3.1）
（3.1）式称为产销平衡运输问题的数学模型。当（总发量）
（总收量）
时。即当产大于销（
）时，其数学模型为
（3.2）
当销大于产（
）时，其数学模型为
（3.3）
因为产销不平衡的运输问题可以转化为产销平衡的运输问题。所以我们先讨论产销平衡的运输问题的求解。
运输问题有个未知量,个约束方程。例如当≈40,=70时（3.1）式就有2800个未知量，110个方程,若用前面的单纯形法求解，计算工作量是相当大的。我们必须寻找特殊解法。 1.2 运输问题的特性
由于运输问题也是线性规划问题，根据线性规划的一般原理，如果它的最优解存在，一
?????
??????==≥====∑∑==),,2,1;,2,1(0),,2,1(),,2,1(1
1n j m i x n j b x m I a x ij j m
i ij i n
j ij ∑∑==≠n
j j
m i i b
a 1
1
∑∑==>n
j j
m i i b
a 1
1
∑∑===m i n
j ij
ij x c z 11
min ?????
??????==≥===≤∑∑==),,2,1;,2,1(0),,2,1(),,2,1(1
1n j m i x n j b x m I a x ij j m
i ij i n
j ij ∑∑== j j m i i b a 1 1 ∑∑===m i n j ij ij x c z 11 min ????? ??????==≥=≤==∑∑==),,2,1;,2,1(0),,2,1(),,2,1(1 1n j m i x n j b x m I a x ij j m i ij i n j ij mn n m +m n 定可以在基可行解中找到。因此，我们先求运输问题（3.1）的约束方程组的系数矩阵的秩()等于多少。 （3.1）式有个约束，将前个约束相加得 , （3.4） 将后个约束相加，得 , （3.5） 因为， , 所以，（3.4）式与（3.5）式是相同得。由此可见，这个约束不是独立的。我们可以证明：当所有的 ，都大于零时，任何个约束都是相互独立的。即，系数矩阵 A 的秩，事实上， … … … … 注意到在 中去掉第1行而取出第2，第3，…，第行，又取出与 所对对应的列，则由这些取出的行和列的交叉处的元素构成 的一个级子式 r A n m +m ∑∑∑====m i i m i n j ij a x 111 n ∑∑∑====n i j n j m i ij b x 1 11 ∑∑===n j j m i i b a 1 1 n m +i a j b 1-+n m 1)(-+=n m A r 11x 12x n x 121x 22x n x 21m x 2m x mn x ?? ?? ? ??? ???????????? ??????=111111111111111111 A n m +1312111211,,,,,,,m n x x x x x x A 1-+n m D 0 11 1111 11 11≠=????????????= D 所以，由此可知，运输问题的任何一组基都由个变量组成。 第一，所有未划去的行列中找出最小元素（若有几个元素同时最小，则可任取其一），在该元素所在的变量处填上尽可能大的数字，并作上标记； 第二，划去已被满足的行或列的空格，若表中某一变量处填入一数后，使该变量所在之行和所在之列同时被满足，遇只能划去一行或一列，而不能将两者同时划去； 第三.上述步骤，直至所有的空格都已填数或被划去为止。 §2 运输问题的表上作业法 2.1 初始解的求法 同单纯形法一样，首先要求初始调运方案必须是一个基可行解，初始解一般来说不是最优解，主要希望给出求初始解的方法简便可行，且有较好的效果。这种方法很多，最常见的是左上角法（或西北角法）、最小元素法和Vogl近似法(VAM)。后两法的效果较好，在此我们仅对最小元素法加以介绍。 最小元素法的所谓元素就是指单位运价。此法的基本思想是：运价最便宜的优先调运，现通过例子来说明。 例1设有某种物质要从三个仓库运往四个销售点。各发点（仓库）的发货量、各收点（销售点）的收货量以及到的单位运费如表3-2（ =1,2,3；=1,2,3,4）.组织运输才能使总运费最少？ 表3-2 由表3-2知，总的发量=总的收量，供销平衡。现从取最小值的格子开始（若有几个同时取最小值，则可取其中之一）。在本例中最小。这说明，将的物质调1 ) (- + =n m A r1 - +n m 3 2 1 , ,A A A. , , , 4 3 2 1 B B B B i A j B ij C i j ij c ij c1 13 = c 1 A 给 是最便宜的，故应给 所对应的变量 以尽可能大的数值。显然应取 。在 处填上7。由于 的 需求已经得到满足（或者说 列已 被满足），故 应为零，在 处打×将 列划去，并将 的发量相应地改为2 （见表3-3）。 在表3-3未划线的格子中，最小的 为 。有 即令 ，并在第二列的其它空格（即在 ）处打×，于是第二列又被划去，且 的发量只有 1了。 接下去的做法是： 在 处填上2，此时， 的发量已分配完毕（一般说成： 行被满足），故应在第一行的其它空格处（实际上只有 ）打上×，划去第一行。 在 处填上1，在第二行的其它空格处（实际上只有 了）打上×，划去第二行。在 处填上1，在第一列的其它空格处（实际上已无空格）打上×，划去第一列。 在 处填上5，在第四列（或第3行）的其它空格处（实际上已无空格）打上×，划去第四列（或第三行），见表3-4。 3B 13c 13x 7)7,9min(13==x 13x 3B 3B 3323,x x 3323,x x 3B 1A ij c 622=c )9,10min( 22=x 922=x 3212,x x 2A 11x 1A 1A 14x 21x 24x 31x 34x 至此，所有方格都已填上数或打上×，总共填了3＋4－1=6个数（等于基变量的个数）其余方格均已打×。每填一数就划去了一行或一列，总共划去的行数与列数之和也是6。可以证明，用最小元素法所得到的一组解 是基可行解，而且填数处是基变量，打×处是非 基变量。它对应的目标函数为 在用最小元素法确定初始调运方案的 基本步骤： 值得注意的是，如 是空格，但 的需求已满足，（或 的物质已调完）不需要（或 不可能） 再调运物质到 ，此时必须禽 ，以保证最后填数的个数 个。 这一点对于以下的计算是重要的。 2.2验数的求法 表上作业法同单纯形法一样，也是利用检验数判别已取得的解是否为最优解。表上作业法求检验数一般有两种方法：位势法和闭回路法。这里我们先介绍位势法。 1 位势法 首先构造位势表 我们将运价表中对应于表3-4有运量处划方格，然后在表的右边添加一列，下面添加一行。并且在添加的行、列里填上一些数，使得表中任何划了方格的对应运价正好等于它所在行及所在列中新填入数字之和。（见表3-5）具体作法如下： ij x 184516114961117129=?+?+?+?+?+?=z ij x j B i A i A j B =ij x 1-+n m 将 行右边空格填入零，则 列、 列下面的空格中必须分别填入9、1。由于11=9 ＋2，所以， 行的右边空格必须填入2。类似地， 列的下面应该填入4（因6=4＋2）， 行的右边只能填5（因14=9＋5），最后，由 ，所以, 列必须填入11。这样 就得到了表3-5.这个表称为位势表，新填入的数字分别称为行位势和列位势。并分别记为 和 （ =1,2,3； =1,2,3,4）。 再求检验数 设 所在的格子的检验数为 ，则我们可以证明 = －( ＋ )( =1，2，…， ； =1，2，…， ),(3.6)并且当 所有的 0时，对应的调运方案是最优方案。 表3-5 1A 1B 3B 2A 2B 3A 1634=C 4B i αj βi j ij x ij σij σij c i αj βi m j n ≥ ij σ 显然，对于那些在方中已确定了调运量的格子的检验数 应该为零，即有 = ＋ ，上面我们在求行位势与列位势时就利用了这一关系。下面我们来求其余格子所对 应的检验数。 ； ； ； ； ； ； 2 闭回路法 首先介绍闭回路的概念：如果已确定了某一调运方案，我们从某一空格出发（无调运量的格子），沿水平方向或垂直方向前进，遇到某一个适当有调运量的格子就转向 继续前进。如此继续下去，经过若干次，就一定回到原来出发的空格。这样形成 的一条由水平和垂直线段组成的封闭折线称为闭回路。 在表上作业法中，闭回路中重要的概念之一，它既可以计算检验数又可以调整调运方案。由于数字格对应着基变量，其检验数均为零，而我们考虑的是非基变量的检验数，所以只研究从空格出发所形成的闭回路。 由闭回路的构成可见，除起点是空格外，其余所有的拐角点都是填有调运量的。我们可以证明一个重要的事实：从每一个空格出发都存在唯一的闭回路。 例如在表3-5所示的初始调运方案中作出从（3.2）对应的空格为起点的闭回路为 （3,2） (2,2) (2,1) (3,1) (3,2) ij σij c i αj β14)40(18)(211212=+-=+-=βασc 1)110(10)(211414-=+-=+-=βασc 5)12(8)(322323=+-=+-=βασc 5)112(18)(422424=+-=+-=βασc 3)45(12)(233232=+-=+-=βασc 4)15(2)(333333-=+-=+-=βασc ?90→→→→ 这条闭合回路，除出发格（3,2）为空格外，其余都是数字格，如表3-6所示。 为确定空格（ ）的检验数，便可以从空格（ ）出发作闭回路，并对该回路的顶点进行编号，即以（ ）格为第一个顶点，所经过的顶点依次为第二个、第三个……。则闭回路上奇数顶点的单位运价之和减去偶数顶点的单位运价之和所得到的差，就是空格（ ）的检验数。其经济意义是非基变量 取值增加一个单位所引起的总运费的 变化量。 现以计算（3,2）格的检验数为例加以说明。若让（3,2）格的调运量增加一个单位，为保证产销平衡，则其奇数顶点的调运量也都要增加一个单位此同时，所有偶数顶点的调运量也都要减少一个单位。如表3-7所示。经过这样调整后，就会得到一个新的调运方案如表3-8。 t k ,t k ,t k ,t k ,kt x 现在考虑按上述方法调整方案后，总运费将如何变化。因为闭回路上所有奇数顶点的调运量都增加了1个单位，单考虑这一因素，总运费的增加量等于闭回路奇数顶点单位运价之和；另一方面，闭回路上所有偶数顶点的调运量都减少了1个单位，单考虑这一因素，总运费的减少量等于闭回路偶数顶点单位运价之和。如果同时考虑这两方面的因素，总运费的增加量就等于该闭回路上奇数顶点的单位运价之和减去偶数顶点单位运价之和所得的差，其差值 就是空格的检验数。所以，（2,3）格的检验数为 这表明，如果让（3,2）格的调运量（ 运往 的货物量）增加一个单位，总运费将 32023)614()1112()()(3122113232=-=+-+=+-+=c c c c σ3 A 2B 增加3元（这与前面用位势法求检数的结果是一致的。）同样可以求得表3-7所示的基本可行方案每个空格检验数列于表3-9每个相应方格的括号内。 表3-9 2.3最优方案的判别准则 在讨论闭回路法求检验数时，我们看到如果某人空格的检验数为正，那么若使该空格的调运量增加（即由非基变量变为基变量），总运费就会增加之，如果某个空格的检验数为负，若使该空格的调运量增加，总运费就会减少。我们自然会想到：如果没有负的检验，总运费就不能再减少了。一般我们有如下结论，即判别最优方案准则： 对于运输问题的一个基本可行方案，如果所有的检验数非负，即 ,那么该方案 就是一具最优方案。这里的结论和前面线性规划的结论是一致的。因为运输问题是极小化线性规划问题。所以，最优判别准则乃是所有检验数非负。 用上述最优判别准则检查表3-9，由于表中还有负的检验，所以，现在得到的方案还不是最优方案。 2.4调运方案的改进 如果所得的基本可行方案不是最优的，就要对其进行改进，这一步工作想当于普通 单纯形法的换基迭代，其运算法则和步骤是： 第一步 确定进基格。选取绝对值最大的负检验数格为进基格，标以“*”，进基格所对 应的变量就是单纯形法所对应的变量； 第二步 作从进基格出发作闭回路，并沿任一方向对该闭回路的顶点进行编号，但进基格必须为第一个顶点； ≥ij σ 第三步 确定调整量，求出闭回路上所有偶数顶点调运量的极小值 , 叫做调整量； 第四步 调整方案，令此闭回路上所有奇数顶点的调运量加 ，所有偶数顶点的调运量减 ，其余调运量不变。调整后进基格由空格变为数字格，在闭回路的偶数顶点中选取一个调运量为零的顶点改为空格，如果有几个偶数顶点的调运量同时变为零，只能选取其中一个顶点改为空格，如果有几个偶数顶点的调运量同时变为零，只能选取其中一个顶点改为空格，这个变为空格的偶数顶点所对应的变量，就是单纯形法是所说的出基变量。 如表3-9， 是绝对值最大的负检验数，以（3,3）格为空格出发的闭合回路（3,3） →(1,3)→(1,1)→(3,1)用 表示该闭合回路上的调整量，则 。沿着该闭合回路奇数顶点的调运量加 ，偶数顶点的 调运量减 ，得表3-10。 对表3-10所示的基本可行方案，用闭合回路法重新计算检验数，见表3-11。 其中以（2,4）格为空格的闭回路是(2,4)→(2,1)→(1,1)→(1,3)→(3,3)→(3,4)→(2,4),因此， 现在， 是唯一的负检验数，以(1,4)格为空格对偶调运量进行调整， θθθθ33σ1θ1)17min(),min(31131===，x x θ1θ1 θ1)()(34132133112424=++-++=c c c c c c σ514-=σ ，调整后的结果见表3-12的第一表。 对调整后的调运方案继续求检验数，见表3-12的第二表。 由表3-12的第二表可见，所有的检验数 ，当前的方案为最优调运方案。此时， 总的调运费为： , 表3-12 即当 时为最优，最小费用为155个单位。 [第一节] [第二节] [返回] 5)5,6min(2==θ0 ≥ij σ15562961115101139=?+?+?+?+?+?= z 6,9,1,5,1,3332221141311======x x x x x x 指派问题的匈牙利解法 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 / / / / / \/ \/ 运输问题的求解方法 ——表上作业法 产销平衡表与单位运价表 表上作业法 一、产销平衡表与单位运价表 运输问题还可用产销平衡表与单位运价表进行描述。 假设某种物资有m个生产地点Ai（i=1，2，…，m），其产量（供应量）分别为ai（i=1，2，…，m），有n个销地Bj（j=1，2，…，n），其销量（需求量）分别为bj（j=1，2，…，n）。从Ai到Bj运输单位物资的运价（单价）为Cij。将这些数据汇总可以得到产销平衡表和单位运价表5.3.1。 表5.3.1 产销平衡表与单位运价表 二、表上作业法 运输这一类特殊问题可用更加简便的求解方法———表上作业法求解，实质仍是单纯形法，步骤如下： （1）确定初始调运方案，即找出初始基可行解,在产销平衡表上给出m+n-1个数字格。 （2）求非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解：是否存在负的检验数？如果存在负的检验数，则初始调运方案不是最优方案；如果所有检验数都非负，则初始调运方案已经是最优方案了。如果已经得到最优调运方案，则停止计算，否则转入下一步。 （3）确定换入变量和换出变量，找出新的调运方案（新的基可行解），即在表上用闭回路法进行调整。 (4）重复（1）～（2），直到求出最优解为止。 （一）确定初始可行基的方法 ?最小元素法 从单位运价表中最小的运价开始确定供销关系，然后考虑运价次小的，一直到给出初始基可行解为止。 ?伏格尔法 采用最小元素法可能造成其他处的更多浪费，伏格尔法考虑最小运费与次小运费之间的差额，差额越大，就按次小运费调运。 （二）最优解的判别 计算非基变量（空格）的检验数,当所有的检验数时，为最优解。 求空格检验数的方法有： ?闭回路法 以某一空格为起点找一条闭回路，用水平或垂直线向前划，每碰到一数字格转900后，继续前进，直到回到起始空格为止。 闭回路如图5.3.1的（a）、（b）、（c）等所示。从每一个空格出发一定存在并且可以找到唯一的闭回路。因为，m+n-1个数字格（基变量）对应的系数向量是一个基，任一空格（非基变量）对应的系数向量是这个基的线性组合。 ?位势法 一种较为简便的求检验数的方法。 设是对应运输问题的m+n个约束条件的对偶变量。B是含有一个人工变量X a的初始基矩阵。X a在目标函数中的系数Ca ，由线性规划的对偶理论可知 而每一个决策变量Xij的系数向量，所以 由单纯形法可知，所有基变量的检验数等于0，即 下面用具体例子说明表上作业法的计算步骤。 例1：假设某种物资共有3个产地，其日产量分别是：A1为7 t，A2为4 t，A3为9 t；该种物资的4个销售地，其日销量分别：B1为3 t，B2为6 t，B3为5 t，B4为6 t；各产地到销售地的单位物资的运价如表5.3.2所示。在满足各销售点需要量的前提下，如何调运该种物资，才能使总运费达到最小？ 表5.3.2 谢荣华、林建、岳钱华、叶俊君 【摘要】在物资调运问题中,希望运输费用最少总是人们最为关心的一个 目标。在各种设定条件的约束下,如何寻找使得总运输费用最少的最优的运输方案是运输问题的核心。为给社会生产(生活)提供既便捷又经济实惠的物资调运方案,运输问题模型的求解方法可以产生最优的决策方案。因此对运输问题的深入研究具有极其重要的理论意义和实际应用价值。表上作业法是解决运输问题的重要方法本文讨论了产销平衡运输问题的表上作业法，利用伏格尔法求初始方案，位势法求检验数，闭合回路发对可行解进行调整和改进，直至求出最优解。 【关键词】运筹学、运输问题、改善优化、表上作业法 一、理论依据 运输问题的表上作业法步骤 1、制作初始平衡表 用“西北最大运量，然后，每增加角方法”：即在左上角先给予最大运量，然后，每增加一个运量都使一个发量或手里饱。如果所有运量的数字少于 （m+n-1），则补0使之正好（m+n-1）个。 （注:补零时不能使这些书构成圈。） 2、判断初始方案是否最优 （1）求位势表：对运价表加一行一列，圈出运价表中相应于有运量的项，在增加的行列上分别添上数，使这些元素之和等于圈内的元素。这些元素称为位势数。 （2）求检验数，从而得到检验数表。 结论：若对任意检验数小于等于0，则该方案最优，否则进入3进行调整. 3、调整 （1）找回路：在检验数大于0对应的应量表上对应元素为起点，沿横向或纵向前进，如遇到有运量的点即转向，直至起点，可得到一个回路。 （2）找调整量：沿上述找到的回路，从起点开始，在该回路上奇数步数字的最小者作为调整量ε。 （3）调整方式：在该回路上奇数步-ε，偶数步+ε，得到新回路。 重复上述步骤，使所有检验数小于0，即得到最优方案。 二、背景 鉴于市场竞争日益激烈，消费者需求渐趋多样，工厂作为市场消费品的产出源头，唯有对这种趋势深刻理解、深入分析，同事具体的应用于实际中，才能使自身手艺，断发展壮大，不被新新行业所淘汰。对于今天的重点研究对象食品工厂而言，由于在不同产品在原料使用、物料损耗、市场价格等方面均存在各种差异，如何确定各产品的生产配比，以及在最优的生产配比方案之下工厂能够达到最大的产值，都是值得进行探讨研究的现实问题。 三、实例 运筹学 课 程 设 计 报 告 专业： 班级： 学号： ： 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）步。 在未被直线覆盖的元素中总有一个最小元素。对未被直线覆盖的元素所在的行（或列）中各元素都减去这一最小元素，这样，在未被直线覆盖的元素中势必会出现零元素，但同时却又是以被直线覆盖的元素中出现负元素。为了消除负元素，只要对它们所在的列（或行）中个元素都加上这一最小元素（可以看作减去这一最小元素的相反数）即可。 四、算法源程序。 指派问题的解法总结 问题引入：在工作的时候，常常需要对一些人进行工作安排，由于某些条件的限制， 每个人只能进行一种工作，怎么安排才能使得总工作时间最小。我们把这一类问题称 为指派问题。在这里，我只对人和工作刚好一对一的指派问题的解法进行总结，而对 于不是一对一的，则可以通过文献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、制作初始平衡表 用“西北最大运量，然后，每增加角方法”：即在左上角先给予最大运量，然后，每增加一个运量都使一个发量或手里饱。如果所有运量的数字少于 （m+n-1），则补0使之正好（m+n-1）个。 （注:补零时不能使这些书构成圈。） 2、判断初始方案是否最优 （1）求位势表：对运价表加一行一列，圈出运价表中相应于有运量的项，在增加的行列上分别添上数，使这些元素之和等于圈内的元素。这些元素称为位势数。 （2）求检验数，从而得到检验数表。 结论：若对任意检验数小于等于0，则该方案最优，否则进入3进行调整. 3、调整 （1）找回路：在检验数大于0对应的应量表上对应元素为起点，沿横向或纵向前进，如遇到有运量的点即转向，直至起点，可得到一个回路。 （2）找调整量：沿上述找到的回路，从起点开始，在该回路上奇数步数字的最小者作为调整量ε。 （3）调整方式：在该回路上奇数步-ε，偶数步+ε，得到新回路。 重复上述步骤，使所有检验数小于0，即得到最优方案。 二、背景 鉴于市场竞争日益激烈，消费者需求渐趋多样，工厂作为市场消费品的产出源头，唯有对这种趋势深刻理解、深入分析，同事具体的应用于实际中，才能使自身手艺，断发展壮大，不被新新行业所淘汰。对于今天的重点研究对象食品工厂而言，由于在不同产品在原料使用、物料损耗、市场价格等方面均存在各种差异，如何确定各产品的生产配比，以及在最优的生产配比方案之下工厂能够达到最大的产值，都是值得进行探讨研究的现实问题。 三、实例 甲、乙、丙三个城市每年需要煤炭分别为：320、250、350万吨，由A、B 两处煤矿负责供应。已知煤炭年供应量分别为：A—400万吨，B—450万吨。 第3章运输问题 第三章运输问题 一、选择 1.运输问题在用表上作业法计算的时候，用闭回路法进行调整检验时，通过任 一空格可以找到（）闭回路 A、惟一 B、多个 C、零个 D 不能确定 2.在产销不平衡的运输问题中，如果产大于销，我们（B ）把他变成一个产销 平衡的运 输问题 A 假想一个产地 B 假想一个销地 C 去掉一个产地 D 没有办法 3.最小元素法的基本思想就是（ D）。 A依次供应B全面供应 C 选择供应 D就近供应 4.运输问题中在闭回路调整中，使方案中有数字的格为（ C ）。 A m B n C m+n D m+n-1 5.在表上作业法中，调运方案中有数字的格为（ C ） A m+n B m-n C m+n-1 D m*n 6.运输问题的数学模型中，包含有（ D）变量。 A m+n B m-n C m+n-1 D m*n 7. 运输问题的数学模型中，包含有（ A）个约束条件。 A m+n B m-n C m+n-1 D m*n 8. 运输问题的数学模型中,系数矩阵中线性独立的列向量的最大个数为（C ） A m+n B m-n C m+n-1 D m*n 9. 运输问题的解中的基变量数一般为（C ） A m+n B m-n C m+n-1 D m*n 10.运输问题中，在检验数表上所有检验数都（C ），此时运输表中给出的方案就是最优方案。 A大于零B等于零C大于等于零D小于零 11.在产销不平衡的运输问题中，如果销大于产时，可以在产销平衡表上 （ A），把他变成 一个产销平衡的运输问题 A 假想一个产地 B 假想一个销地 C 去掉一个产地 D 没有办法 12.运输问题数学模型的特点之一是（） A 一定有最优解 B 不一定有最优解 C 一定有基可行解 D 不一定有基可行解 13.运输问题的数学模型的约束条件的系数矩阵的元素由（）组成。 A 0B1C0,1D 不确定 14. 二、填空 1.求解不平衡的运输问题的基本思想是(设立虚供地或虚需求点，化为供求平衡的标准形式) 。 2.运输问题中求初始基本可行解的方法通常有 (最小元素法 )、 (伏格尔法 ) 两种方法。 3.伏格尔法有时就用作求运输问题最优方案的（近似解） 4.运输问题最优性检验通常有（闭回路法、位势法）两种方法。 5. 第32卷第3期2000年6月 南 京 航 空 航 天 大 学 学 报 Jo urnal o f Nanjing Univ ersity o f Aeronautics&Astronautics V o l.32No.3 Jun.2000 运输问题表上作业法的改进研究 李时椿 (南京经济学院管理系 南京,210042) 摘要 在传统的“闭回路法”和“位势法”基础上,提出利用“流水原理”来寻求运输问题最优解。即以“最小元素法”求得初始调运方案后,将表中各栏单位物资的运价视为“水位”的高低,将已安排的运输量视为处于一定水位高度的“蓄水量”,依据“水往低处流”的自然界基本原理,考察处于最高“水位”的“蓄水量”沿其所在的行或列的“渠道”流向最低“水位”的可能性,来确定“流向”及其相应的“闭回路”,据此调配运输方案,直至总体“蓄水量”处于最低水位状态,则方案达最优。 关键词:输运理论;流水原理;闭回路法 中图分类号:F224.3 引 言 运输问题通常用“表上作业法”求解——先以“最小元素法”或“西北角法”给出一个初始方案,再以“闭回路法”或“位势法”进行调整改进,直至获得最优方案。但在实际优化调整时,无论采用何种方法,都必须逐一计算每个空栏处的检验数,才可分析比较并作出调整,其过程重复、计算繁冗,极大地影响了实际应用和推广。本文借助自然界“水往低处流”的基本规律,利用“流水原理”寻求最有效的调配路线进行优化,从而使求解过程简捷而又直观,大大克服了传统方法繁锁重复的弊端。 1 流水原理求解供求平衡的运输问题 某运输问题如下,运价(元/吨)标在图1中各栏斜线左上方,问该如何调运可使总运费支出为最少[1](图中O表示产量,S表示销售量或需求量,下同)。 解 (1)以“最小元素法”确定初始方案。图1中圈内数据表示初始方案所安排的运输量,初始方案总运费为86元。 (2)以“流水原理”对初始方案优化调整。 (A)确定“最高水位”。“水位”指各栏中单位运量的运价,“最高水位”系指已安排有运 收稿日期:1999-06-02;修改稿收到日期:1999-09-13 作者:李时椿,男,副教授,1949年9月生。 第八章运输及配送路线的优化 教学目的：使学生理解各种运输方式的特点及运输方式选择的原则，掌握运输方式选择的定量分析法，理解存在中间运转的物资调配方法，掌握旅行 商问题和中国邮递员问题的解法以及扫描法和节约法。 基本要求：1、理解各种运输方式的特点； 2、掌握运输方式选择的定量分析法； 3、理解存在中间运转的物资调配方法； 4、掌握旅行商问题和中国邮递员问题的解法。 教学重点：扫描法、节约法 教学时数：6学时 第一节运输方式的选择 ?运输方式选择的原则 当同时存在多种运输方式可供选择的情况下，就需要进行选优抉择。通常根据各种运输方式的经济特性和服务特征来选择合适的运输方式，即主要依据运输成本、运输速度、可靠性、安全性等指标进行判断和选择。 安全性原则——首要的原则 及时性原则 准确性原则 经济性原则——主要原则 货物运输的六大方式： 根据运输工具的不同，可分为：水路、公路、铁路、航空、管道和多式联运等运输形式。 在各种运输方式中，如何选择适当的运输方式是物流合理化的重要问题。可以选择一种运输方式也可以选择使用联运的方式。 运输方式的选择，需要根据运输环境、运输服务的目标要求，采取定性分析与定量分析的方法进行考虑。 ?运输方式选择的定性分析法 定性分析法主要是依据完成运输任务可用的各种运输方式的运营特点及主要功能、货物的特性以及货主的要求等因素对运输方式进行直观选择的方法。 1.单一运输方式的选择 单一运输方式的选择，就是选择一种运输方式提供运输服务。公路、铁路、水路、航空和管道五种基本运输方式各有自身的优点与不足，可以根据五种基本运输方式的优势、特点，结合运输需求进行恰当的选择。 一般要考虑的因素是： 匈牙利法解决人数与任务数不等的指派问题 于凯 重庆科技学院经济管理学院物流专业重庆沙坪坝区 摘要：本文将讨论运筹学中的指派问题，而且属于非标准指派问题，即人数与任务数不相等的指派问题，应当视为一个多目标决策问题，首先要求指派给个人任务数目两两之间相差不能超过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）对没有√号的行画一横线，有√号的列画一竖线。如此便可以覆盖所有 任务1.3 优化物流运输的线路 ●任务描述 面对高油价以及公路计重收费的到来，物流运输企业的成本剧增，如何应对挑战？运输公司普遍的做法是：强化经营管理，在降本减耗上下功夫，抵御高物流成本经营风险。其中重要的一条就是不断优化运输线路，减少人为加大的运距，节约油耗，避免油资源浪费，提高运输效率。案例1.3就是广西运德物流公司成功地为康鑫全药业集团运输药品的经验。 ■案例放送 【案例1.3】康鑫全药业集团公司有4个药品生产厂：A1（南宁四塘）、A2（巴马）、A3（南丹）和A4（柳州），2008年第二季度生产供应高科技产品——“护肝王”特效药（针剂）分别为＋20、＋60、＋100、＋20万盒（供应量记“+”）；有5个批发配送中心B1（平果）、B2（合山）、B3（宜州）、B4（河池）、B5（贵州黔南县），负责推销配送“护肝王”分别是-30、-30、-50、-70、-20万盒（需求量或销售量记“-”）。“护肝王”配送的交通线路用图表示，见图1.3-1。图中○表示生产供应点，□表示配送点，站点旁边的数字表示生产（正数）或配送（负数）“护肝王”数量。线路旁括号内标注的数字表示相邻两点间的距离（为了计算方便，未取实际准确数）。 ■案例研讨 优化物流运输线路与运输线路开发有区别，它是在已知货物名称及数量、货源地和目的地的情况下，根据运输合理化原则对运输线路的选择与优化。 物流运输合理化要求以最佳的运输线路、最快的运输速度和最低的运输费用等将物品从原产地运送到目的地，案例中康鑫全集团的4个生产供应点，5个批发配送点，线路图中有成圈的，有不成圈的，属于相对复杂的情况。应该如何安排，才能达到路程最近和时间及费用最省？经过本单元以下内容的学习，可以找到解决问题的办法。 浅析指派问题的匈牙利解法 胡小芹 数学科学学院数学与应用数学学号: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 指派问题的解法——匈牙利解法 指派问题的算法分析与实现 摘要 在企业、公司的运营与管理中，管理者总是希望把人员最佳分派以发挥其最大工作效率，从而降低成本、提高效益。然而，如果没有科学的方法是很难实现优化管理的，由此我们引入了指派问题。指派问题多是求项目的工时最少，而很多情况下人们并不关心项目总工时的多少，而只关心项目能否在最短的时间内完成，即历时最少的指派问题。这类问题研究的是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 ），也称为效益矩阵或价值矩阵。矩阵的元 3.2 求解指派问题的匈牙利算法 由于指派问题的特殊性，又存在着由匈牙利数学家D.Konig 提出的更为简便的解法—匈牙利算法。算法主要依据以下事实：如果系数矩阵)(ij c C =一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵)(ij b B = ，则以C 或B 为系数矩阵的指派问题具有相同的最优指派。 利用上述性质，可将原系数阵C 变换为含零元素较多的新系数阵B ，而最优解不变。若能在B 中找出n 个位于不同行不同列的零元素，令解矩阵中相应位置的元素取值为1，其它元素取值为零，则所得该解是以B 为系数阵的指派问题的最优解，从而也是原问题的最优解。 由C 到B 的转换可通过先让矩阵C 的每行元素均减去其所在行的最小元素得矩阵D ，D 的每列元素再减去其所在列的最小元素得以实现。 下面通过一例子来说明该算法。 例7 求解指派问题，其系数矩阵为 ????? ???????=16221917171822241819211722191516C 解 将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得 ????? ???????=06310157124074011B 再将第3列元素各减去1，得 ????? ???????=****20531005711407301B 以2B 为系数矩阵的指派问题有最优指派 ??? ? ??43124321 由等价性，它也是例7的最优指派。 有时问题会稍复杂一些。 例8 求解系数矩阵C 的指派问题 ??????? ?????????=61071041066141512141217766698979712C 解：先作等价变换如下 ∨∨ ∨????????????????→????????????????----- 26360 40*089 57510*00*0032202*056107104106614151214121776669897971246767 容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但5=n ，最优指派还无法看出。此时等价变换还可进行下去。步骤如下： (1) 对未选出0元素的行打∨； (2) 对∨行中0元素所在列打∨； (3) 对∨列中选中的0元素所在行打∨； 重复（2）、（3）直到无法再打∨为止。 可以证明，若用直线划没有打∨的行与打∨的列，就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令∨行元素减去此数，∨列元素加上此数，则原先选中的0元素不变，而未覆盖元素中至少有一个已转变为0，且新矩阵的指派问题与原问题也等价。上述过程可反复采用，直到能选取出足够的0元素为止。例如，对例5变换后的矩阵再变换，第三行、第五行元素减去2，第一列元素加上2，得 ??????? ?????????0414******* 353800003420207 现在已可看出，最优指派为???? ??5314254321。 龙源期刊网 https://www.sodocs.net/doc/1f3431675.html, 关于几种不平衡指派问题的修正匈牙利解法作者：杜金玲;周杰 来源：《价值工程》2010年第13期 摘要:本文利用实例验证了在用匈牙利算法求解指派问题时,不平衡的指派问题转化为平衡指派问题的必要性;总结对于几种不平衡的指派问题转化为平衡指派问题的方法,从理论上作出解释,并给出了相应的例题,特别对于任务数多于人数的指派问题,本文提出了新的更有针对性的转化方法,如“一人化成p人法”、“加边补小法”、“加边补零(M)法”等。 Abstract: In this paper, the necessity of the transformation of the unbalanced assignment problem to the balanced assignment problem is tested with examples. The methods of transformation are summarized and explained from theory; and gived an example of the problem, especially, the methods of the transformation are brought up. For example, the method of "one to p persons", the method of "the adding rows with zero or M",the method of "the adding rows with min" and so on. 关键词:指派问题;匈牙利算法;一人化成p人法;加边补小法;加边补零(M)法 Key words: assignment problem;the Hungaryalgorithm;the method of "one to p persons";the method of "the adding rows with min";the method of “the adding rows with zero or M” 中图分类号:TP301.6文献标识码:A文章编号:1006-4311(2010)13-0120-03 0引言 在实际生活和生产安排中,经常遇到要指派不同的工作人员去完成不同的工作。由于每个 人的专长不同,不同的人去完成各项任务的效率(或所花时间或成本等)一般地也不同。这样,就 产生了指派何人去完成何任务,使总效率最高(或所花时间最少或成本最低等)的问题。这类问题称为指派问题(Assignment Problem),又称为分配问题。 1平衡指派问题的数学模型 对于有n项任务且恰好有n个人去完成的指派问题(称为平衡指派问题),规定每人只完成一项任务,且每项任务只能由一个人去完成。已知aij表示第i个人完成第j项任务时的效率(所用时间或成本等),[aij]称为效率矩阵。设决策变量: xij=1,第i个人完成第j项任务0,否则(i,j=1,2,…,n),于是指派问题的数学模型为: min z=aijxij指派问题的匈牙利解法
表上作业法
表上作业法解决运输问题
运筹学指派问题的匈牙利法实验报告
指派问题的解法
表上作业法解决运输问题演示教学
第3章 运输问题复习过程
运输问题表上作业法的改进研究
运输及配送路线的规划
匈牙利法解决人数及任务数不等的指派问题
运输线路优化.
浅析指派问题的匈牙利解法成稿讲解
指派问题的算法
求解指派问题的匈牙利算法.doc
关于几种不平衡指派问题的修正匈牙利解法