、指派问题与匈牙利法
三、指派问题与匈牙利法
1、指派问题的数学模型 设有n个工作,要由n个人来承12…j n 担,每个工作只能由一个人承 In 担,且每个人只能承担一个工2nc2e…c 作。c;表示第i个人做第j件事 的费用,求总费用最低的指派 方案 n 刀1C C 第个人做第j人件事指派问题模型: 角:x= 0第个人不做第j人件事 minz=∑∑cnx x1+x,2+…+x;+…+x i2 i=12 ,J- n S1x+x,+…+xn+…+x=1 Z表示总费用 x , n,y
设有n个工作，要由 n个人来承 担，每个工作只能由一个人承 担，且每个人只能承担一个工 作。cij表示第i个人做第j件事 的费用,求总费用最低的指派 方案。 1 2 … j … n 1 2 … i … n 指派问题模型： = j i ij ij min Z c x + + + + + = 1 . i1 i2 i j i n x x x x st i=1,2, …,n 1 1 2 + + + + + = j j i j nj x x x x j=1,2, …,n x i n j n i j = 0,1 = 1,2, , ; = 1,2, , 解： 第i个人做第j 人件事 Z表示总费用 i=1,2, …,n; j=1,2, …,n 第i个人不做第j 人件事 = 0 1 ij x n n nj n n i i ij i n j n j n c c c c c c c c c c c c c c c c 1 2 1 2 21 22 2 2 11 12 1 1 1、指派问题的数学模型
mIn Z=∑∑cx=1+212+…+n 十C,x十∴C nT2n ∴∴ nnt nn +x12+…+x;+…+x1n=1 x21+x2+…+x21+…+x2n x+x2+…+x+…+x=1 xn1+x,+…+xn+…+x .. st x1,十X;+……+x,+…+x x1+x21+…+x1+…÷心 121422 xn+x,n+…+xn+…+xn=1 当n=4时,有16变量,8个约束方程
= j i ij ij min Z c x n n n n n n n n n n n n c x c x c x c x c x c x c x c x c x + + + + + + + + + = + + + 1 1 2 2 2 1 2 1 2 2 2 2 2 2 1 1 1 1 1 2 1 2 1 1 + + + + + =1 . i1 i2 i j i n x x x x st 1 1 2 + + + + + = j j i j nj x x x x i=1,2, …,n j=1,2, …,n 当n=4时，有16变量，8个约束方程 + + + + + = + + + + + = + + + + + = 1 1 1 . 1 2 2 1 2 2 2 2 1 1 1 2 1 1 n n n j n n j n j n x x x x x x x x x x x x st 1 1 1 1 2 12 22 2 2 11 21 1 1 + + + + + = + + + + + = + + + + + = n n i n n n i n i n x x x x x x x x x x x x
例:现有4份工作,4个人应聘,由z表示总费用 于各人技术专长不同,他们承担mxz=3x1+5+41+53 各项工作所需费用如下表所示, +6x1,+7x2+6x,+8x 且规定每人只能做一项工作,每 +8x1+9x2+8x3+10x4 项工作只能由一人承担,试求 +10x41+10x2+9x3+11x4 使总费用最小的分派方案。 x1+x12+x13+x14= 234 x21+x22+x23+x24 x21+x2+x2+x24=1 x41+x42+x43+x4=1 6768 389810 +x21+x21+xn1=1 41010911 S.x12+x4x1 解: x13+x +x2+x12=1 第i人做第j件事 13 23 x4+x24+x34+x4=1 第人不做第j件事 0.1
例：现有4份工作，4个人应聘，由 于各人技术专长不同，他们承担 各项工作所需费用如下表所示， 且规定每人只能做一项工作，每 一项工作只能由一人承担，试求 使总费用最小的分派方案。 工作 人 1 2 3 4 1 2 3 4 3 5 4 5 6 7 6 8 8 9 8 10 10 10 9 11 解： = ij x 1 0 第i人做第j 件事 Z表示总费用 i=1,2, 3,4; j=1,2, 3,4 第i人不做第j 件事 11 12 13 14 max Z = 3x +5x + 4x +5x 21 22 23 24 + 6x + 7x + 6x +8x 31 32 33 34 +8x +9x +8x +10x 41 42 43 44 +10x +10x +9x +11x + + + = 1 . 1 1 1 2 1 3 1 4 x x x x st x21 + x22 + x23 + x24 =1 x31 + x32 + x33 + x34 =1 x41 + x42 + x43 + x44 =1 x11 + x21 + x31 + x41 =1 x12 + x22 + x32 + x42 =1 x13 + x23 + x33 + x43 =1 x14 + x24 + x34 + x44 =1 j n i n xij 1,2, , 1,2, , 0,1 = = =
2、费用矩阵 设有n个工作,要由n个人来承象12jn 担,每个工作只能由一个人承11c2…,…a 担,且每个人只能承担一个工21c2…c…c2 作。c表示第个人做第j件事 的费用,求总费用最低的指派 方案 n nIna n 取C 费用矩阵 c;表示第个人做第j件事的费用
2、费用矩阵 设有n个工作，要由 n个人来承 担，每个工作只能由一个人承 担，且每个人只能承担一个工 作。cij表示第i个人做第j件事 的费用,求总费用最低的指派 方案。 1 2 … j … n 1 2 … i … n n n nj n n i i ij i n j n j n c c c c c c c c c c c c c c c c 1 2 1 2 21 22 2 2 11 12 1 1 = n n n n n n c c c c c c c c c C 1 2 21 22 2 11 12 1 取 cij表示第i个人做第j件事的费用 费用矩阵