例:现有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   = = =