§5指派问题 在实际问题中,常常会碰到这样的问题,要指派n个人去完成n 项不同任务,每个人必须完成其中一项而且仅仅一项。但由于个人 的专长不同,任务的难易程度不一样,所以完成不同任务的效率就 不同,那么应该指派哪个人去完成哪项任务,能使总的效率最好呢 这就是典型的指派问题。 例6今欲指派张王李赵四人加工A、B、C、D四种不同的零件, 每人加工四种零件所需要的时间如下表所示,问应该派谁加工何种 零件可使总的花费时间最少? 零件 A B D 张 4 6 5 8 王 6 10 7 8 李 7 8 11 9 赵 9 3 84
§5 指派问题 ◼ 在实际问题中,常常会碰到这样的问题,要指派n个人去完成n 项不同任务,每个人必须完成其中一项而且仅仅一项。但由于个人 的专长不同,任务的难易程度不一样,所以完成不同任务的效率就 不同,那么应该指派哪个人去完成哪项任务,能使总的效率最好呢? 这就是典型的指派问题。 例6 今欲指派张王李赵四人加工A、B、C、D四种不同的零件, 每人加工四种零件所需要的时间如下表所示,问应该派谁加工何种 零件可使总的花费时间最少? 零件 人 A B C D 张 王 李 赵 4 6 5 8 6 10 7 8 7 8 11 9 9 3 8 4
在类似问题中都必须给出一个像上表一样的矩阵℃,称为效率矩阵。 C nn 矩阵中的元素C表示指派第个人去完成第项任务时的效率。 求解这类问题时,通常引入0一1变量: 1,指派第i人去完成第项任务 i,j=1,2,…,n 0,不指派第人去完成第项任务 于是,对于极小化问题,指派问题数学模型为: min2-含含 从模型看,指派问题是特 殊的0一1规划,也是特殊 含无=1j=12…n 的运输问题,可以用这两 含x=1i=1,2…n 种问题的求解方法求解。 但这样做是不合算的。 七1或0
在类似问题中都必须给出一个像上表一样的矩阵C,称为效率矩阵。 = n n nn n n C C C C C C C C C C 1 2 21 22 2 11 12 1 矩阵中的元素Cij表示指派第i个人去完成第j项任务时的效率。 求解这类问题时,通常引入0—1变量: i j n i j i j = , , =1,2,, 不指派第 人去完成第 项任务 指派第 人去完成第 项任务 , , 0 1 ij x 于是,对于极小化问题,指派问题数学模型为: = = = m i 1 n j 1 ij ij minZ c x x 1, j 1,2, ,n n i 1 ij = = = x 1,i 1,2, ,n n j 1 ij = = = xij=1或0 从模型看,指派问题是特 殊的0—1规划,也是特殊 的运输问题,可以用这两 种问题的求解方法求解。 但这样做是不合算的
根据指派问题的特殊结构,我们有更为简便的方法。这就是下 面将介绍的匈牙利法,这个方法是由匈牙利数学家康尼格(D.Koig) 给出的。 匈牙利算法是以指派问题最优解的性质为根据的。 指派问题最优解性质:如果将指派问题的效率矩阵的每一行 (列)的各个元素都减去该行(列)的最小元素,得到一新的矩阵 C',则以C为效率矩阵的指派问题的最优解与原问题的最优解相同。 证明:设C的第i行元素都减去该行最小元素a,第j列元素都减 去该列最小元素b,则新矩阵C第行第j列的元素为C=Ca,b, 以新矩阵C为效率矩阵的指派问题的目标函数为 Z'=ΣCj'xΣ(Ca-b)=2ΣC2a-b =Z-∑a-2b 可见新问题的最优解与原问题的最优解相同,只是目标值相差一个 常数。证毕
根据指派问题的特殊结构,我们有更为简便的方法。这就是下 面将介绍的匈牙利法,这个方法是由匈牙利数学家康尼格(D.Konig) 给出的。 匈牙利算法是以指派问题最优解的性质为根据的。 指派问题最优解性质:如果将指派问题的效率矩阵的每一行 (列)的各个元素都减去该行(列)的最小元素,得到一新的矩阵 C′ ,则以C′为效率矩阵的指派问题的最优解与原问题的最优解相同。 证明:设C的第i行元素都减去该行最小元素ai,第j列元素都减 去该列最小元素bj ,则新矩阵C′第i行第j列的元素为Cij′=Cij-ai-bj, 以新矩阵C′为效率矩阵的指派问题的目标函数为 Z′=ΣΣCij ′xij =ΣΣ(Cij-ai-bj)xij =ΣΣCijxij-Σai-Σbj =Z-Σai-Σbj 可见新问题的最优解与原问题的最优解相同,只是目标值相差一个 常数。证毕
利用这个性质,可以使原效率矩阵变换为含有多个0元素的新 效率矩阵,而最优解不变。在新的效率矩阵中如果能找到个不同 行且不同列的0元素,则可以令它们对应的等于1,其它等于0, 显然,该解一定是最优解。这就是匈牙利算法的基本思想。 具体步骤如下:· 第一步变换效率矩阵,使各行各列都出现0元素。 1°效率矩阵每行元素都减去该行最小元素; 2°效率矩阵每列元素都减去该列最小元素。 第二步圈出不同行且不同列的0元素,进行试指派。 1°(行搜索)给只有一个0元素的行中的0画圈,记作 “◎”,并划去与其同列的其余0元素: 2°(列搜索)给只有一个0元素的列中的0画圈,记作 “@”,并划去与其同行的其余0元素; 3°反复进行1°、2°,直至所有0元素都有标记为止。 4°若行(列)的0元素均多于一个,则在0元素最少的行(列) 中选定一个0元素,标“回”,并划去与其同行同列的其余0元素。 5°若不同行且不同列的“回”已达个,则令它们对应的 1,其余0,已得最优解,计算停,否则转第三步
利用这个性质,可以使原效率矩阵变换为含有多个0元素的新 效率矩阵,而最优解不变。在新的效率矩阵中如果能找到n个不同 行且不同列的0元素,则可以令它们对应的xij等于1,其它xij等于0, 显然,该解一定是最优解。这就是匈牙利算法的基本思想。 具体步骤如下: 第一步 变换效率矩阵,使各行各列都出现 0 元素。 1°效率矩阵每行元素都减去该行最小元素; 2°效率矩阵每列元素都减去该列最小元素。 第二步 圈出不同行且不同列的 0 元素,进行试指派。 1°(行搜索)给只有一个0 元素的行中的0 画圈,记作 “◎”,并划去与其同列的其余0元素; 2°(列搜索)给只有一个0 元素的列中的0 画圈,记作 “◎”,并划去与其同行的其余0元素; 3°反复进行1°、2°,直至所有0元素都有标记为止。 4°若行(列)的0元素均多于一个,则在0元素最少的行(列) 中选定一个0元素,标“◎”,并划去与其同行同列的其余0元素。 5°若不同行且不同列的 “◎”已达n个,则令它们对应的xij =1,其余xij =0,已得最优解,计算停,否则转第三步
第三步用最少直线覆盖效率矩阵中的0元素。 1°对没有“回”的行打“√”; 2°对打“√”行中的0元素所在列打“√”; 3°对打“V”列中“回”所在行打“√”; 4°反复进行2°、3°,直至打不由新“”为止。 5°对没打“√”的行画横线,对打“√”列画竖线,则效率矩 阵中所有0元素被这些直线所覆盖。 第四步调整效率矩阵,使出现新的0元素。 1°找出未被划去元素中的最小元素,以其作为调整量0; 2°矩阵中打“√”行各元素都减去0,打“√”列各元素都加0 (以保证原来的0元素不变),然后去掉所有标记,转第二步。 下面用上述算法求解例6
第三步 用最少直线覆盖效率矩阵中的0元素。 1°对没有“◎”的行打“√”; 2°对打“√”行中的0元素所在列打“√”; 3°对打“√”列中“◎”所在行打“√”; 4°反复进行2°、 3°,直至打不出新 “√”为止。 5°对没 打“√”的行画横线,对打“√”列画竖线,则效率矩 阵中所有0元素被这些直线所覆盖。 第四步 调整效率矩阵,使出现新的0元素。 1°找出未被划去元素中的最小元素,以其作为调整量θ; 2°矩阵中打“√”行各元素都减去θ,打“√”列各元素都加θ (以保证原来的0元素不变),然后去掉所有标记,转第二步。 下面用上述算法求解例6
解:先变换效率矩阵,然后圈出不同行不同列的0元素,结果如下: 5 8 0 2 O 10 7 8 0 2 0 811 9 0 14 2 3 3 8 4 605 6 O 4/0 由于不同行不同列的0元素仅有3个,所以要继续第三步及第四步。 02 3 调整量01,调整效率矩 0 O 2 040 1 阵使之出现更多0元素。 O 300 0131 而后,再重新圈出不同行 0 030 且不同列的0元素,进行 6-040 再指派。结果如右: 7050 由于回的个数已达n=4个,所以令⊙所对应的=1,其余=0,已 得最优解。即最优指派方案为:张一C;王一A;李一D;赵一B。 所需最少总时间为:5+6+9+3=23。注意,本例的最优方案不唯一, 张一A;王一C;李—B;赵一D也是最优方案
解:先变换效率矩阵,然后圈出不同行不同列的0元素,结果如下: 6 0 4 0 0 1 3 1 0 4 0 1 0 2 0 3 6 0 5 1 0 1 4 2 0 4 1 2 0 2 1 4 9 3 8 4 7 8 11 9 6 10 7 8 4 6 5 8 ○ ∕ ∕ ○ ∕ ○ ∕ 6 0 4 0 0 1 3 1 0 4 0 1 0 2 0 3 由于不同行不同列的0元素仅有3个,所以要继续第三步及第四步。 ○ ∕ ∕ ○ ∕ ○ ∕ √ √ √ √ √ 调整量θ=1,调整效率矩 阵使之出现更多0元素。 而后,再重新圈出不同行 且不同列的 0 元素,进行 再指派。结果如右: 7 0 5 0 0 0 3 0 0 3 0 0 ∕ 0 1 ○ 0 2 ○ ∕ ∕ ∕ ○ ∕ ∕ ○ 由于◎的个数已达n=4个,所以令◎所对应的xij =1,其余xij =0,已 得最优解。即最优指派方案为:张—C;王—A;李—D;赵—B。 所需最少总时间为:5+6+9+3=23。注意,本例的最优方案不唯一, 张—A;王—C;李—B;赵—D也是最优方案
以上讨论仅限于极小化问题,对于极大化问题,不能按 miZ'-2(-C)x求解,因为匈牙利法要求效率矩阵的元素C≥0,这 时可取M=max{C},令b,=M-C,以B=(b)nxn为效率矩阵求解。 ·c6为大 另外,如果任务数与人数不相等,可以象不平衡运输问题一样, 虚设一项任务或人,并且令相应的Ct1,或Ct1等于0,(ij=1,2n) 然后用匈牙利法求解
以上讨论仅限于极小化问题,对于极大化问题,不能按 minZ′=ΣΣ(-Cij)xij求解,因为匈牙利法要求效率矩阵的元素Cij≥0,这 时可取M=max{Cij},令bij=M-Cij,以B=(bij)n×n为效率矩阵求解。 ∵ΣΣ(M-Cij)xij=nM-ΣΣCijxij ∴当ΣΣ(M-Cij)xij取最小时,ΣΣCijxij便为最大。 另外,如果任务数与人数不相等,可以象不平衡运输问题一样, 虚设一项任务或人,并且令相应的Cn+1,j或Ci,n+1等于0,(i,j=1,2…n) 然后用匈牙利法求解
第四章作业 ■P77:1 ■P77: 2 ■P77:3 ■P77:4(1) ■P78:6
第四章作业 ◼ P77: 1 ◼ P77: 2 ◼ P77: 3 ◼ P77: 4(1) ◼ P78: 6