例:现有4份工作,4个人应聘,由于个人的技术专长不 同,他们承担各项工作所需费用如下表所示,且规定 每人只能做一项工作,每一项工作只能由一个人承担, 试求使总费用最小的分派方案。 收费用 工作 1234 3545 6768 3545 费用矩阵C 234 6768 89810 89810 1010911 1010911 2345 对应一个5个人5个工作的指派问题 02356 设C=10056第2个人做第4个工作的费用5 60539 第4个人做第2个工作的费用0 3570
例：现有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 费用矩阵 = 10 10 9 11 8 9 8 10 6 7 6 8 3 5 4 5 C = 1 3 5 7 0 6 0 5 3 9 1 0 0 5 6 0 2 3 5 6 1 2 3 4 5 设C 对应一个5个人5个工作的指派问题 第2个人做第4个工作的费用 5 第4个人做第2个工作的费用0
3、匈牙利法 定理:在费用矩阵C=(cn)的任一行(列)中 减去一个常数或加上一个常数不改变本 问题的最优解。 12 In 2 C,-b c-b .-b 2 b≥miny1,C12 n个人n个工作 n个人n个工作 的指派问题1 的指派问题2
定理：在费用矩阵C=（cij）的任一行（列）中 减去一个常数或加上一个常数不改变本 问题的最优解。 n个人n个工作 的指派问题1 = n n nn i i i n n n c c c c c c c c c c c c C 1 2 1 2 21 22 2 11 12 1 -b − − − = n n n n i i i n n n c c c c b c b c b c c c c c c C 1 2 1 2 21 22 2 11 12 1 b min ci1 ,ci2 , ,ci n 3、匈牙利法 n个人n个工作 的指派问题2
11 C b 二 min z min z C1x1+c12x12+…+C1nx1n =C1x1+c12x12+…+C1nxn +c21x21+ Xa t.+cx 22422 +CX+Caxa.+cx n2n cn1n+c2X12+…+ C. X +cu-b)x1+(c2-b)x 2+.+(cin -b)x +Cx,+ n2n2 +C X 十Cnxn+Cn2xn,+……+Cnx nn nn nn nn xn+x2+…+x;+…+x +x12+…+xn+…+x n S1x1+x,+…+x.+…+x1=1 s.t. x1,+x2;+…+x2+…+xn=1 0.1
min Z n n n n n n n n i i i i i n i n n n n n c x c x c x c x c x c x c x c x c x c x c x c x + + + + + + + + + + + + + + = + + + 1 1 2 2 1 1 2 2 21 21 22 22 2 2 11 11 12 12 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 x i n j n i j = 0,1 =1,2, , ; =1,2, , i=1,2, …,n j=1,2, …,n min Z n n n n n n n n i i i i i n i n n n n n c x c x c x c b x c b x c b x c x c x c x c x c x c x + + + + + + − + − + + − + + + + + = + + + 1 1 2 2 1 1 2 2 2 1 2 1 2 2 2 2 2 2 1 1 1 1 1 2 1 2 1 1 ( ) ( ) ( ) = n n nn i i i n n n c c c c c c c c c c c c C 1 2 1 2 21 22 2 11 12 1 − − − = n n nn i i i n n n c c c c b c b c b c c c c c c C 1 2 1 2 21 22 2 11 12 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 x i n j n i j = 0,1 =1,2, , ; =1,2, , i=1,2, …,n j=1,2, …,n -b
x1;十 1111 12412 C21X1+C22x2十…+CnX +(cn-b)xn+(c12-b)x2+……+(cm-b)xn t CnIxn t Cn2xn2 +,.+Cnnx 1111 十C12x1+ 12 C21X21+C22x2+……+c2nX2n t Cixi + Cixi t.+cinx Cn1xn1十C,Xn+…+Cn,x an nn b(x1+ +xn) 。。。。。。。。。●。。。。垂 1111 12~12 1n*1n 21x21 22422 C2n 2n ++十 x1十C;X;十+c;n,xX 2n2 b
min Z n n n n n n n n i i i i i n i n n n n n c x c x c x c b x c b x c b x c x c x c x c x c x c x + + + + + + − + − + + − + + + + + = + + + 1 1 2 2 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 1 2 2 1 2 1 1 2 2 2 1 2 1 2 2 2 2 2 2 1 1 1 1 1 2 1 2 1 1 n n n n n n n n i i i n i i i i i n i n n n n n c x c x c x b x x x c x c x c x c x c x c x c x c x c x + + + + − + + + + + + + + + + + + + = + + + c x c x c x b c x c x c x c x c x c x c x c x c x n n n n n n n n i i i i i n i n n n n n + + + + − + + + + + + + + + + = + + + 1 1 2 2 1 1 2 2 2 1 2 1 2 2 2 2 2 2 1 1 1 1 1 2 1 2 1 1
11 C b 二 b min Z=Z+bl min Xu+cn.+cx C1x1+C1X1干…+C1x1 II c21x21+c22X2+…+C2nx2m C21x21+C2X2+…+C2nx2n C;1x;1+C;x2+…+C,x +Ciriltci2xi2t',+cinx Cn1xn1+CnX+…+Cn,x +cx +cx+.+c x-b nn nn xn十X+…十x+…+X il x,+…+x+…+x x1+x2+…+xn+…+x S1x,+x,+…+x1+…+x=1 j=1,2 xn=0,1i=1,2,…,n,j=1,2,…,n x1=01i=12,…,nj=1,2;…,n
min Z min Z n n n n n n n n i i i i i n i n n n n n c x c x c x c x c x c x c x c x c x c x c x c x + + + + + + + + + + + + + + = + + + 1 1 2 2 1 1 2 2 21 21 22 22 2 2 11 11 12 12 1 1 c x c x c x b c x c x c x c x c x c x c x c x c x n n n n n n n n i i i i i n i n n n n n + + + + − + + + + + + + + + + = + + + 1 1 2 2 1 1 2 2 2 1 2 1 2 2 2 2 2 2 1 1 1 1 1 2 1 2 1 1 = n n nn i i i n n n c c c c c c c c c c c c C 1 2 1 2 21 22 2 11 12 1 − − − = n n nn i i i n n n c c c c b c b c b c c c c c c C 1 2 1 2 21 22 2 11 12 1 -b + + + + + = 1 . i1 i2 i j i n x x x x st 1 1 2 + + + + + = j j i j nj x x x x x i n j n i j = 0,1 =1,2, , ; =1,2, , i=1,2, …,n j=1,2, …,n + + + + + = 1 . i1 i2 i j i n x x x x st 1 1 2 + + + + + = j j i j nj x x x x x i n j n i j = 0,1 =1,2, , ; =1,2, , i=1,2, …,n j=1,2, …,n = Z +b = Z −b