当前位置：文档之家 › 匈牙利法

匈牙利法

  • 格式：docx
  • 大小：40.47 KB
  • 文档页数：3

二、匈牙利法 P96～98
假定甲单位有甲、乙、丙、丁、戊五个员工，需要在一定的生产技术组织条件下，完成
A、B、C、D、E五项任务，每个员工完成每项工作所需要耗费的工作时间，如表2－6所示。
请求出：员工与任务之间应当如何进行配置，才能保证完成工作任务的时间最短？

表2－6 各员工完成任务时间汇总表单位：小时
员工
任务
甲 乙 丙 丁 戊

A
10 5 9 18 11

B
13 19 6 12 14

C
3 2 4 4 5

D
18 9 12 17 15

E
11 6 14 19 10

注意：由于存在以下两种情况，匈牙利法的计算过程不唯一，最终矩阵的形式也不唯一，
但最终配置结果一定相同，
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。
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

图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。

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

矩阵五a




0 0 4 7 2
2 13 0 0 4
0 4 6 0 3
4 0 3 2 2
0 0 8 7 0

矩阵五b
表2－11 矩阵六
0 0 4 7 2
2 13 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 13 0 √⑤ 0  4
0  4 6 0 √④ 3
4 0 √① 3 2 2
0  0  8 7 0 √③

表2－13 员工配置最终结果单位：小时
员工
任务
甲 乙 丙 丁 戊

A
10

B
6

C
4

D
9

E
10

合集下载

分配问题与匈牙利法

分配问题与匈牙利法


0 1 0 5
2 0 4 4
2
6
0
0

试指派
3 4 3 ◎
◎ 1 Ø 5
2 ◎ 4 4
2
6
◎
Ø

得到4个独立零元素， 所以最优解矩阵为：
0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0
即完成4个任务的总时间最少 为：2＋4＋1+8=15
2 ◎0 4 2 4 2 5 Ø0 3 ◎0 4 1 ◎0 1 3 4 Ø0 3 5 1 0◎ 2 3 Ø0 5
独立0元素的个数l＝4<5，故画直线调整矩阵。
分配问题与匈牙利法
Page 17
2 ◎0 4 2 4 √
2 5 Ø0 3 ◎0
选择直线外的最小元素 为1；直线外元素减1， 直线交点元素加1，其
总费用为=8+9+4+3+4=28
分配问题与匈牙利法
Page 22
课堂练习：用匈牙利法求解下列指派问题。
练习1：
练习2：
7 9 10 12
13
12
16
17

15 16 14 15
11 12 15 16
3 8 2 10 3

8
7
29
7

6 4 2 7 5
分配问题与匈牙利法
Page 4
指派问题的求解步骤：
1) 变换指派问题的系数矩阵(cij)为(bij)，使在(bij)的各行各列 中都出现0元素，即
从(cij)的每行元素都减去该行的最小元素； 再从所得新系数矩阵的每列元素中减去该列的最小元素。
2) 进行试指派，以寻求最优解。
运输问题的匈牙利解法和表上作业法

运输问题的匈牙利解法和表上作业法

运输问题的解法运输问题是一类特殊的线性规划问题，最早是从物质调运工作中提出的，后来又有许多其它问题也归结到这一类问题中。

正是由于它的特殊结构，我们不是采用线性规划的单纯方法求解，而是根据单纯形方法的基本原理结合运输问题的具体特性须用表上作业的方法求解。

§1 运输问题的数学模型及其特性1.1 运输问题的数学模型设有 个地点（称为产地或发地） 的某种物资调至 个地点（称为销地或收地），各个发点需要调出的物资量分别为个单位，各个收点需要调进的物资量分别为 个单位。

已知每个发点到每个收点的物资每单位运价为 ，现问如何调运，才能使总的运费最小。

我们把它列在一张表上（称为运价表）。

设表示从产地运往销地的运价（ =1，2，…， ； =1，2，…，）。

表3-1如果（总发量）（总收量），我们有如下线性规划问题：m mA A A ,,,21 n nB B B ,,,21 ma a a ,,,21 nb b b ,,,21 iA jB ijc ijx iA jB i m jn（3.1）（3.1）式称为产销平衡运输问题的数学模型。

当（总发量）（总收量）时。

即当产大于销（）时，其数学模型为（3.2）当销大于产（）时，其数学模型为（3.3）因为产销不平衡的运输问题可以转化为产销平衡的运输问题。

所以我们先讨论产销平衡的运输问题的求解。

运输问题有个未知量,个约束方程。

例如当≈40,=70时（3.1）式就有2800个未知量，110个方程,若用前面的单纯形法求解，计算工作量是相当大的。

我们必须寻找特殊解法。

∑∑===m i nj ijij x c z 11min ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≥====∑∑==),,2,1;,2,1(0),,2,1(),,2,1(11n j m i x n j b x m I a x ij j mi ij i nj ij ∑∑==≠nj jm i i ba 11∑∑==>nj jm i i ba 11∑∑===m i nj ijij x c z 11min ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≥===≤∑∑==),,2,1;,2,1(0),,2,1(),,2,1(11n j m i x n j b x m I a x ij j mi ij i nj ij ∑∑==<nj jm i i ba 11∑∑===m i nj ijij x c z 11min ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≥=≤==∑∑==),,2,1;,2,1(0),,2,1(),,2,1(11n j m i x n j b x m I a x ij j mi ij i nj ij mn n m +m n1.2 运输问题的特性由于运输问题也是线性规划问题，根据线性规划的一般原理，如果它的最优解存在，一定可以在基可行解中找到。

解读“匈牙利法”——对《“匈牙利法”存在的问题及改进方法》一文的质疑

解读“匈牙利法”——对《“匈牙利法”存在的问题及改进方法》一文的质疑

＿＿＿。＿＿。＿。。＿・・— ・ —
Ｑｕ ｓｉｎ ａ ｏ ｔＡｒｉ ｅ Ｅｘｓ ｎ ｒｂ ｅ ａ ｄ Ｉ ｒ ｖ ｍｅ ｔｏ ｎ ａ ｉｎ Ａｌｏ ｉ ｍ ｅｔ ｂ ｕ ｔ ｌ ｉ ｉｇ Ｐ ｏ ｌｍ ｎ ｍｐ ｏ ｅ ｎ ｆＨｕ ｇ ｒａ ｇ ｒ ｈ ｏ ｃ ｔ ｔ
ＺＨＡＮＧ — ｅ Ｙｕ ｙ
些误解。文章详 细解读 了“ 匈牙利 法” 及其 求解步骤 ， 并通过 两个 实例详细 演示了“ 匈牙利 法” 的具体求解过程 ， 以助 学习 者更好地理 解和运 用“ 匈牙利 法” 来解决 实际问题 ， 同时也 澄清 了对 “ 匈牙利 法” 的某些错误认 识。为保证 求解结果的正
确 性 ， 用 Ｅ ｃｌ 供 的 “ 划 求 解 ” 块 对 求 解 结 果 进 行 了验 证 。 利 ｘｅ提 规 模
法” 处理一些特殊 数据时算法不收敛 ， 无法找 出最优解 ， 指出该 的专长不 同导致 完成任务的工作效 率、 费用等不 同 。如何将这
算法存 在 问题 并给 出了一改进 方法 ， 于文 中提 出的观 点笔 ｎ 对 项任 务合理安排给这 ｎ 个人 ， 得总工作效 率最高 、 使 费用最少 者不能 苟 同。本文针 对顾大权 等人给 出的 两个 实例 ， 利用“ 匈 就 具有很 重要 的现实意义 。这类 问题统 称为指派 问题 。指派 牙利法 ” 对此两 例求解 ， 完全能 够求得最优解 ； 且第二 例原文作 者求得 的最 小 目标函数值是 ２ ， ７ 而笔者利用 “ 匈牙利法 ” 求得的 算此例求 得的结果也 是 ２ ， ６ 这说 明文 献［】 １中给出 的匈牙 利改 进方法 并不可取 ， 因为它并不 能求得最优 解 ， 这样文 献［】 １中作
０ 引言
在 《 机发展 》 微 的第 １ 卷 第 ４ （０３ ４ ） 大权 等人 ３ 期 ２０ 年 月 顾
运筹学基础及应用第4章-整数规划与分配问题

运筹学基础及应用第4章-整数规划与分配问题


整数规划的特点及应用
解：对每个投资项目都有被选择和不被选择两种可能，因此 分别用0和1表示，令xj表示第j个项目的决策选择，记为：
j投 资 1 对 项 目 xj ( j 1,2,..., n) j不 投 资 0 对 项 目
投资问题可以表示为：
max z
c
j 1
n
j
xj
n a j x j B j 1 x2 x1 s .t x 3 x4 1 x5 x6 x7 2 ） x j 0或者1 （j 1, 2, L n
B1 B2 B3 B4 年生产能力
A1
A2 A3 A4 年需求量
2
8 7 4 350
9
3 6 5 400
3
5 1 2 300
4
7 2 5 150
400
600 200 200
工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。 现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。
0-1型整数线性规划：决策变量只能取值0或1的整数线性 规划。
整数规划的特点及应用
整数规划的典型例子
例4.1 工厂A1和A2生产某种物资。由于该种物资供不应求，故需要 再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地 有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各 需求地的单位物资运费cij，见下表：
例4.3 设整数规划问题如下
max Z x1 x 2 14x1 9 x 2 51 6 x1 3 x 2 1 x , x 0且 为 整 数 1 2
首先不考虑整数约束，得到线性规划问题（一般称为松弛问 题）。