01规划ppt课件.ppt

例例1 背包问题背包问题 有有n件物品，编号为件物品，编号为 1，，2，，…，，n第 件重为件重为 kg，价值为，价值为 元今一装包者欲将这些物品元今一装包者欲将这些物品装入一包，其质量不能超过装入一包，其质量不能超过 kg，问应装入哪几件价值最大？，问应装入哪几件价值最大？0-1规划应用背景1 解解 引入变量引入变量 将将 物品装包物品装包 不将不将 物品装包物品装包 于是得问题的模型为于是得问题的模型为 取取0或或1，，i=1，，2，，…，，n 背包问题看似简单，但应用很广，例如某些投资问题即可归入背包问题模背包问题看似简单，但应用很广，例如某些投资问题即可归入背包问题模型此类问题可以型此类问题可以2 描述为：设有总额为描述为：设有总额为 元的资金，投资几项事业，第元的资金，投资几项事业，第 项副业需投资项副业需投资 元，利润为元，利润为 元元,问应选择哪些项总利润为最大？问应选择哪些项总利润为最大？ 例例2 某钻井队要从以下某钻井队要从以下10个可供选择的井位中确定个可供选择的井位中确定5个钻井探油，使总个钻井探油，使总的钻探费用为最小。

若的钻探费用为最小若10个井位的代号为个井位的代号为 ，相，相应的钻探费用为应的钻探费用为 ，并且井位选择要满足下列限，并且井位选择要满足下列限制条件：制条件： （（1）或选）或选 和和 ，或选，或选 ；； （（2）选择了）选择了 或或 就不能选就不能选 ，反之亦然；，反之亦然； （（3）在）在 中最多只能选两个中最多只能选两个 试建立其数学模型：试建立其数学模型：3 解解 引入变量引入变量 选择选择 不选择不选择 于是以上问题的数学模型为：于是以上问题的数学模型为：4 5 例例3 指派问题。

有指派问题有 项任务，由项任务，由 个人来完成，每人只能干一件，个人来完成，每人只能干一件，第第 个人完成第个人完成第 项任务需要的时间为项任务需要的时间为 小时，问怎样安排能使总小时，问怎样安排能使总用时最少？用时最少？ 解解 引入引入0-1型变量型变量 人完成人完成 任务任务 人不去完成人不去完成 任务任务 于是该问题的数学模型为于是该问题的数学模型为6 S.t.7 0-1规划模型因其特殊性，不同于整数规划的解法如一般0-1规划的隐枚举法，指派问题中的匈牙利法，背包问题则可以用动态规划的方法求解0－1规划解法8 隐枚举法隐枚举法隐枚举法隐枚举法(Implicit Enumeration)(Implicit Enumeration)(Implicit Enumeration)(Implicit Enumeration) 基本上此法可以从所有变量等于零出发（初始点），然后依次指定一些变基本上此法可以从所有变量等于零出发（初始点），然后依次指定一些变基本上此法可以从所有变量等于零出发（初始点），然后依次指定一些变基本上此法可以从所有变量等于零出发（初始点），然后依次指定一些变量取值为量取值为量取值为量取值为1 1 1 1，直到获得一个可行解，于是把第一个可行解记作迄今为止最好，直到获得一个可行解，于是把第一个可行解记作迄今为止最好，直到获得一个可行解，于是把第一个可行解记作迄今为止最好，直到获得一个可行解，于是把第一个可行解记作迄今为止最好的可行解，再重复，依次检查变量为的可行解，再重复，依次检查变量为的可行解，再重复，依次检查变量为的可行解，再重复，依次检查变量为0 0 0 0，，，，1 1 1 1的各种组合，对迄今为止最好的可的各种组合，对迄今为止最好的可的各种组合，对迄今为止最好的可的各种组合，对迄今为止最好的可行解加以改进，直到获得最优解。

行解加以改进，直到获得最优解行解加以改进，直到获得最优解行解加以改进，直到获得最优解9例例例例5-9 5-9 5-9 5-9 求下列问题：求下列问题：求下列问题：求下列问题：Max Z=3xMax Z=3xMax Z=3xMax Z=3x1 1 1 1- 2x- 2x- 2x- 2x2 2 2 2 + 5x+ 5x+ 5x+ 5x3 3 3 3 s.t. xs.t. xs.t. xs.t. x1 1 1 1+2x+2x+2x+2x2 2 2 2 - x- x- x- x3 3 3 3     2 (1) 2 (1) 2 (1) 2 (1) x x x x1 1 1 1+4x+4x+4x+4x2 2 2 2 + x+ x+ x+ x3 3 3 3     4 (2) 4 (2) 4 (2) 4 (2) x x x x1 1 1 1 + x + x + x + x2 2 2 2     3 (3) 3 (3) 3 (3) 3 (3) 4x 4x 4x 4x2 2 2 2 + x+ x+ x+ x3 3 3 3     6 (4) 6 (4) 6 (4) 6 (4) x x x xj j j j = = = =0 0 0 0或或或或1 (5)1 (5)1 (5)1 (5)10解：解：解：解： 容易看出容易看出容易看出容易看出(1,0,0)(1,0,0)(1,0,0)(1,0,0)满足约束条件，对应满足约束条件，对应满足约束条件，对应满足约束条件，对应Z=3Z=3Z=3Z=3，对，对，对，对Max ZMax ZMax ZMax Z来说，希望来说，希望来说，希望来说，希望Z Z Z Z     3,3,3,3,所以增加约束条件：所以增加约束条件：所以增加约束条件：所以增加约束条件： Z=3xZ=3xZ=3xZ=3x1 1 1 1- 2x- 2x- 2x- 2x2 2 2 2 + 5x+ 5x+ 5x+ 5x3 3 3 3     3 3 3 3 (0)(0)(0)(0)称为过滤性条件。

初看起来，增加约束条件需增加计算量，实际减少了计称为过滤性条件初看起来，增加约束条件需增加计算量，实际减少了计称为过滤性条件初看起来，增加约束条件需增加计算量，实际减少了计称为过滤性条件初看起来，增加约束条件需增加计算量，实际减少了计算量11循环循环循环循环(X(X1 1,X,X2 2,X,X3 3) )s.t.0s.t.0s.t.1s.t.1s.t.2s.t.2s.t.3s.t.3s.t.4s.t.4满足满足满足满足Z Z值值值值1 1(0,0,0)(0,0,0)0 0nono2 2(0,0,1)(0,0,1)5 5-1-11 10 01 1yesyes5 53 3(0,1,0)(0,1,0)-2-2nono4 4(0,1,1)(0,1,1)3 31 15 5nono5 5(1,0,0)(1,0,0)3 31 11 11 10 0yesyes3 36 6(1,0,1)(1,0,1)8 80 02 21 11 1yesyes8 87 7(1,1,0)(1,1,0)1 1nono8 8(1,1,1)(1,1,1)6 62 26 6nono最优解最优解最优解最优解（（（（1 1，，，，0 0，，，，1 1）））） Z=8Z=812增加约束条件（增加约束条件（增加约束条件（增加约束条件（0 0 0 0）（）（）（）（Z Z Z Z     3) 3) 3) 3)后实际做了后实际做了后实际做了后实际做了24242424次运算，而次运算，而次运算，而次运算，而原问题需要计算原问题需要计算原问题需要计算原问题需要计算2 2 2 23 3 3 3*4=32*4=32*4=32*4=32次运算（次运算（次运算（次运算（3 3 3 3个变量，个变量，个变量，个变量，4 4 4 4个约束条个约束条个约束条个约束条件）。

件）13注意：注意：注意：注意：ØØ改进过滤性条件，在计算过程中随时调整右边常数改进过滤性条件，在计算过程中随时调整右边常数改进过滤性条件，在计算过程中随时调整右边常数改进过滤性条件，在计算过程中随时调整右边常数ØØ价值系数按递增排列价值系数按递增排列价值系数按递增排列价值系数按递增排列以上两种方法可减少计算量以上两种方法可减少计算量以上两种方法可减少计算量以上两种方法可减少计算量14循环循环循环循环(X(X2 2,X,X1 1,X,X3 3) )s.t.0s.t.0s.t.1s.t.1s.t.2s.t.2s.t.3s.t.3s.t.4s.t.4满足满足满足满足Z Z值值值值1 1(0,0,0)(0,0,0)0 0nono2 2(0,0,1)(0,0,1)5 5-1-11 10 01 1yesyes5 5改进过滤性条件改进过滤性条件改进过滤性条件改进过滤性条件Z Z Z Z     5 (0 5 (0 5 (0 5 (0’ ’) ) ) )循环循环循环循环(X(X2 2,X,X1 1,X,X3 3) )s.t.0’s.t.0’s.t.1s.t.1s.t.2s.t.2s.t.3s.t.3s.t.4s.t.4满足满足满足满足Z Z值值值值3 3(0,1,0)(0,1,0)3 3nono4 4(0,1,1)(0,1,1)8 80 02 21 11 1yesyes8 815改进过滤性条件改进过滤性条件改进过滤性条件改进过滤性条件Z Z     8 (0’’) 8 (0’’)循环循环循环循环(X(X2 2,X,X1 1,X,X3 3) )s.t.0’’s.t.0’’s.t.1s.t.1s.t.2s.t.2s.t.3s.t.3s.t.4s.t.4满足满足满足满足Z Z值值值值5 5(1,0,0)(1,0,0)-2-2nono6 6(1,0,1)(1,0,1)3 3nono7 7(1,1,0)(1,1,0)1 1nono8 8(1,1,1)(1,1,1)6 6nono最优解最优解最优解最优解(X(X2 2,X,X1 1,X,X3 3) =) =（（（（0 0，，，，1 1，，，，1 1）））） Z=8Z=8实际只计算了实际只计算了实际只计算了实际只计算了1616次次次次16例例例例5-10 5-10 5-10 5-10 求下列问题：求下列问题：求下列问题：求下列问题：Max Z=3xMax Z=3xMax Z=3xMax Z=3x1 1 1 1+ 4x+ 4x+ 4x+ 4x2 2 2 2 + 5x+ 5x+ 5x+ 5x3 3 3 3 + 6x+ 6x+ 6x+ 6x4 4 4 4 s.t. 2xs.t. 2xs.t. 2xs.t. 2x1 1 1 1+ 3x+ 3x+ 3x+ 3x2 2 2 2 + 4x+ 4x+ 4x+ 4x3 3 3 3 + 5x+ 5x+ 5x+ 5x4 4 4 4     15 15 15 15 x x x xj j j j     0 0 0 0且为整数且为整数且为整数且为整数解：先变换解：先变换解：先变换解：先变换x x x xj j j j为为为为0-10-10-10-1变量变量变量变量 x=yx=yx=yx=y0 0 0 0+2y+2y+2y+2y1 1 1 1+2+2+2+22 2 2 2y y y y2 2 2 2+ + + +…….2.2.2.2k k k ky y y yk k k k17解：先变换解：先变换解：先变换解：先变换x x x xj j j j为为为为0-10-10-10-1变量变量变量变量 x=yx=yx=yx=y0 0 0 0+2y+2y+2y+2y1 1 1 1+2+2+2+22 2 2 2y y y y2 2 2 2+ + + +…….2.2.2.2k k k ky y y yk k k kx x x x1 1 1 1     7 x 7 x 7 x 7 x1 1 1 1=y=y=y=y01010101+2y+2y+2y+2y11111111+2+2+2+22 2 2 2y y y y21212121x x x x2 2 2 2     5 x 5 x 5 x 5 x2 2 2 2=y=y=y=y02020202+2y+2y+2y+2y12121212+2+2+2+22 2 2 2y y y y22222222x x x x3 3 3 3     3 x 3 x 3 x 3 x3 3 3 3=y=y=y=y03030303+2y+2y+2y+2y13131313x x x x4 4 4 4     3 x 3 x 3 x 3 x4 4 4 4=y=y=y=y04040404+2y+2y+2y+2y14141414代入原问题，得到：代入原问题，得到：代入原问题，得到：代入原问题，得到：18Max Z= 3 yMax Z= 3 y0101+6y+6y1111+12y+12y21 21 + 4y + 4y0202+8y+8y1212+16y+16y22 22 + 5 y + 5 y0303+10y+10y13 13 + 6 y+ 6 y0404+12y+12y14 14 s.t. 2ys.t. 2y0101+4y+4y1111+8y+8y21 21 +3y+3y0202+6y+6y1212 +12y +12y22 22 + 4 y+ 4 y0303+8y+8y13 13 + 5 y+ 5 y0404 +10y+10y14 14     15 15 y yij ij=0=0或或或或=1=119用隐枚举法可得到：用隐枚举法可得到：用隐枚举法可得到：用隐枚举法可得到：y y y y11111111=y=y=y=y21 21 21 21 =y=y=y=y02 02 02 02 =1 =1 =1 =1 其他全为零其他全为零其他全为零其他全为零最优解（最优解（最优解（最优解（6 6 6 6，，，，1 1 1 1，，，，0 0 0 0，，，，0 0 0 0）））） Z=22Z=22Z=22Z=22 20指派问题（分配问题）指派问题（分配问题）指派问题（分配问题）指派问题（分配问题）(Assignment Problem)(Assignment Problem)(Assignment Problem)(Assignment Problem)例例例例 有一份中文说明书，需翻译成英、日、德、俄四种文字，分有一份中文说明书，需翻译成英、日、德、俄四种文字，分有一份中文说明书，需翻译成英、日、德、俄四种文字，分有一份中文说明书，需翻译成英、日、德、俄四种文字，分别记作别记作别记作别记作E E E E、、、、J J J J、、、、G G G G、、、、R R R R，现有甲、乙、丙、丁四人，他们将中文说明，现有甲、乙、丙、丁四人，他们将中文说明，现有甲、乙、丙、丁四人，他们将中文说明，现有甲、乙、丙、丁四人，他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分配工作，使所需总时间最少？配工作，使所需总时间最少？配工作，使所需总时间最少？配工作，使所需总时间最少？21任务任务任务任务人员人员人员人员E EJ JGGR R甲甲甲甲2 2151513134 4乙乙乙乙10104 414141515丙丙丙丙9 9141416161313丁丁丁丁7 78 811119 922类似有：有类似有：有类似有：有类似有：有n n n n项加工任务，怎样分配到项加工任务，怎样分配到项加工任务，怎样分配到项加工任务，怎样分配到n n n n台机床上分别完成；台机床上分别完成；台机床上分别完成；台机床上分别完成；有有有有n n n n条航线，怎样指定条航线，怎样指定条航线，怎样指定条航线，怎样指定n n n n艘船分别去航行艘船分别去航行艘船分别去航行艘船分别去航行…….. .. .. .. 等。

等表中数据称为效率矩阵或系数矩阵，其元素大于零，表示表中数据称为效率矩阵或系数矩阵，其元素大于零，表示表中数据称为效率矩阵或系数矩阵，其元素大于零，表示表中数据称为效率矩阵或系数矩阵，其元素大于零，表示分配第分配第分配第分配第i i i i人去完成第人去完成第人去完成第人去完成第j j j j 项任务时的效率（或时间、成本等）项任务时的效率（或时间、成本等）项任务时的效率（或时间、成本等）项任务时的效率（或时间、成本等）23 引入引入引入引入0-10-10-10-1变量变量变量变量x x x xijijijij=1=1=1=1分配第分配第分配第分配第i i i i人去完成第人去完成第人去完成第人去完成第j j j j 项任务，项任务，项任务，项任务，x x x xijijijij=0=0=0=0不不不不分配第分配第分配第分配第i i i i人去完成第人去完成第人去完成第人去完成第j j j j 项任务分配问题的数学模型：分配问题的数学模型：分配问题的数学模型：分配问题的数学模型：Min Z=Min Z=Min Z=Min Z=        c c c cijijijijx x x xijijijij     x x x xijijijij =1 =1 =1 =1 (j=1,2(j=1,2(j=1,2(j=1,2…………n)n)n)n)     x x x xij ij ij ij =1=1=1=1 (i=1,2(i=1,2(i=1,2(i=1,2…………n)n)n)n) x x x xij ij ij ij     0 0 0 0或或或或1 1 1 1(i=1,2(i=1,2(i=1,2(i=1,2……..m; j=1,2..m; j=1,2..m; j=1,2..m; j=1,2…………n)n)n)n)24     x xij ij =1=1 (j=1,2……n)(j=1,2……n)表示表示表示表示第第第第j j 项任务只能由一人去完成。

项任务只能由一人去完成项任务只能由一人去完成项任务只能由一人去完成S Sx xij ij =1 =1 (i=1,2……n)(i=1,2……n)第第第第i i人只能完成一项任务人只能完成一项任务人只能完成一项任务人只能完成一项任务满足约束条件的解称为可行解可写成矩阵形式：满足约束条件的解称为可行解可写成矩阵形式：满足约束条件的解称为可行解可写成矩阵形式：满足约束条件的解称为可行解可写成矩阵形式：X=X=0 1 0 00 1 0 00 0 1 00 0 1 01 10 0 00 0 00 0 0 10 0 0 1称为解矩阵其各行各列元称为解矩阵其各行各列元称为解矩阵其各行各列元称为解矩阵其各行各列元素之和为素之和为素之和为素之和为1 125匈牙利算法基本思想：匈牙利算法基本思想：匈牙利算法基本思想：匈牙利算法基本思想： 对同一工作对同一工作对同一工作对同一工作i i i i来说，所有机床的效率都提高或降低同一常来说，所有机床的效率都提高或降低同一常来说，所有机床的效率都提高或降低同一常来说，所有机床的效率都提高或降低同一常数，不会影响最优分配；同样，对同一机床数，不会影响最优分配；同样，对同一机床数，不会影响最优分配；同样，对同一机床数，不会影响最优分配；同样，对同一机床j j j j来说来说来说来说, , , ,做所有工做所有工做所有工做所有工作的效率都提高或降低同一常数，也不会影响最优分配。

作的效率都提高或降低同一常数，也不会影响最优分配作的效率都提高或降低同一常数，也不会影响最优分配作的效率都提高或降低同一常数，也不会影响最优分配26分配问题性质：分配问题性质：分配问题性质：分配问题性质： 分配问题的最优解有这样的性质，若从系数矩阵分配问题的最优解有这样的性质，若从系数矩阵分配问题的最优解有这样的性质，若从系数矩阵分配问题的最优解有这样的性质，若从系数矩阵C C C C的一行的一行的一行的一行（列）各元素中分别减去该行（列）的最小元素得到的新矩（列）各元素中分别减去该行（列）的最小元素得到的新矩（列）各元素中分别减去该行（列）的最小元素得到的新矩（列）各元素中分别减去该行（列）的最小元素得到的新矩阵阵阵阵B B B B，那么，那么，那么，那么B B B B为系数矩阵求得的最优解和用原来的系数矩阵为系数矩阵求得的最优解和用原来的系数矩阵为系数矩阵求得的最优解和用原来的系数矩阵为系数矩阵求得的最优解和用原来的系数矩阵C C C C求求求求得的最优解相同得的最优解相同得的最优解相同得的最优解相同27匈牙利算法：匈牙利算法：匈牙利算法：匈牙利算法： 系数矩阵中独立系数矩阵中独立系数矩阵中独立系数矩阵中独立0 0 0 0元素的最多个数等于能覆盖所有元素的最多个数等于能覆盖所有元素的最多个数等于能覆盖所有元素的最多个数等于能覆盖所有0 0 0 0元素元素元素元素的最少直线数。

的最少直线数的最少直线数的最少直线数28例例例例 有一份中文说明书，需翻译成英、日、德、俄四种文字，分有一份中文说明书，需翻译成英、日、德、俄四种文字，分有一份中文说明书，需翻译成英、日、德、俄四种文字，分有一份中文说明书，需翻译成英、日、德、俄四种文字，分别记作别记作别记作别记作E E E E、、、、J J J J、、、、G G G G、、、、R R R R，现有甲、乙、丙、丁四人，他们将中文说明，现有甲、乙、丙、丁四人，他们将中文说明，现有甲、乙、丙、丁四人，他们将中文说明，现有甲、乙、丙、丁四人，他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分配工作，使所需总时间最少？配工作，使所需总时间最少？配工作，使所需总时间最少？配工作，使所需总时间最少？29任务任务任务任务人员人员人员人员E EJ JGGR R甲甲甲甲2 2151513134 4乙乙乙乙10104 414141515丙丙丙丙9 9141416161313丁丁丁丁7 78 811119 930匈牙利算法的步骤：匈牙利算法的步骤：匈牙利算法的步骤：匈牙利算法的步骤：第一步：使分配问题的系数矩阵经变换，在各行各列中都出现第一步：使分配问题的系数矩阵经变换，在各行各列中都出现第一步：使分配问题的系数矩阵经变换，在各行各列中都出现第一步：使分配问题的系数矩阵经变换，在各行各列中都出现0 0 0 0元素：元素：元素：元素：ØØ从系数矩阵的每行元素减去该行的最小元素。

从系数矩阵的每行元素减去该行的最小元素从系数矩阵的每行元素减去该行的最小元素从系数矩阵的每行元素减去该行的最小元素ØØ再从所得系数矩阵的每列元素减去该列的最小元素再从所得系数矩阵的每列元素减去该列的最小元素再从所得系数矩阵的每列元素减去该列的最小元素再从所得系数矩阵的每列元素减去该列的最小元素若某行已经有若某行已经有若某行已经有若某行已经有0 0 0 0元素，就不必再减了元素，就不必再减了元素，就不必再减了元素，就不必再减了31(cij)=(cij)=2 15 13 42 15 13 41010 4 4 14 1514 159 9 14 16 1314 16 13 7 7 8 11 98 11 92 2 4 4 9 9 7 70 13 11 20 13 11 26 0 10 116 0 10 110 5 7 40 5 7 40 1 4 20 1 4 24 24 20 13 7 00 13 7 06 0 6 96 0 6 90 5 3 20 5 3 20 1 0 00 1 0 032第二步：进行试分配，以寻找最优解。

第二步：进行试分配，以寻找最优解第二步：进行试分配，以寻找最优解第二步：进行试分配，以寻找最优解ØØ从只有一个从只有一个从只有一个从只有一个0 0 0 0元素的行（或列）开始，给这个元素的行（或列）开始，给这个元素的行（或列）开始，给这个元素的行（或列）开始，给这个0 0 0 0元素加圈，记元素加圈，记元素加圈，记元素加圈，记  ，，，，然后划去然后划去然后划去然后划去  所在的列（或行）的其他所在的列（或行）的其他所在的列（或行）的其他所在的列（或行）的其他0 0 0 0元素，记作元素，记作元素，记作元素，记作ØØØØ给只有一个给只有一个给只有一个给只有一个0 0 0 0元素的列（或行）的元素的列（或行）的元素的列（或行）的元素的列（或行）的0 0 0 0元素元素元素元素加圈，记加圈，记加圈，记加圈，记  ，然后划去，然后划去，然后划去，然后划去  所在的所在的所在的所在的行行行行（或列）（或列）（或列）（或列）的其他的其他的其他的其他0 0 0 0元素，记作元素，记作元素，记作元素，记作ØØØØ反复进行上述两步，直到所有的反复进行上述两步，直到所有的反复进行上述两步，直到所有的反复进行上述两步，直到所有的0 0 0 0元素都被圈出和划掉为止。

元素都被圈出和划掉为止元素都被圈出和划掉为止元素都被圈出和划掉为止33ØØ若还有没有划若还有没有划若还有没有划若还有没有划圈的圈的圈的圈的0 0 0 0元素，且同元素，且同元素，且同元素，且同行（或列）行（或列）行（或列）行（或列）的的的的0 0 0 0元素元素元素元素至少有二个，从至少有二个，从至少有二个，从至少有二个，从剩有剩有剩有剩有0 0 0 0元素最少的元素最少的元素最少的元素最少的行（或列）开始，比较这行各行（或列）开始，比较这行各行（或列）开始，比较这行各行（或列）开始，比较这行各0 0 0 0元素所在列中元素所在列中元素所在列中元素所在列中0 0 0 0元素元素元素元素的数目，选择的数目，选择的数目，选择的数目，选择0 0 0 0元素少的那列的元素少的那列的元素少的那列的元素少的那列的0 0 0 0元素加圈，然后划掉同行同列的其元素加圈，然后划掉同行同列的其元素加圈，然后划掉同行同列的其元素加圈，然后划掉同行同列的其他他他他0 0 0 0元素，可反复进行，元素，可反复进行，元素，可反复进行，元素，可反复进行，直到所有的直到所有的直到所有的直到所有的0 0 0 0元素都被圈出和划掉为止。

元素都被圈出和划掉为止元素都被圈出和划掉为止元素都被圈出和划掉为止ØØ若若若若  元素的数目元素的数目元素的数目元素的数目m m m m等于等于等于等于矩阵阶数矩阵阶数矩阵阶数矩阵阶数n n n n，那么这分配问题的最优解已得到那么这分配问题的最优解已得到那么这分配问题的最优解已得到那么这分配问题的最优解已得到若若若若m

37Ø Ø 13 7 0 13 7 0 6 6    6 9 6 9   5 3 2 5 3 2ØØ 1 1    0 0ØØ给只有一个给只有一个给只有一个给只有一个0 0 0 0元素的列的元素的列的元素的列的元素的列的0 0 0 0元素元素元素元素加圈，记加圈，记加圈，记加圈，记  38Ø Ø 13 7 0 13 7 0 6 6    6 9 6 9   5 3 2 5 3 2ØØ 1 1    ØØ然后划去然后划去然后划去然后划去  所在的所在的所在的所在的行行行行的其他的其他的其他的其他0 0 0 0元素，记作元素，记作元素，记作元素，记作ØØ39Ø Ø 13 7 13 7    6 6    6 9 6 9   5 3 2 5 3 2ØØ 1 1    ØØØØ给最后一个给最后一个给最后一个给最后一个0 0 0 0元素元素元素元素加圈，记加圈，记加圈，记加圈，记  。

400 0 0 0 0 0 1 10 0 1 1 0 0 0 01 1 0 0 0 0 0 00 0 0 0 1 1 0 0可见可见可见可见m=n=4,m=n=4,得到最优解得到最优解得到最优解得到最优解即甲译俄文、乙译日文、丙译英文、丁译德文所需时间即甲译俄文、乙译日文、丙译英文、丁译德文所需时间即甲译俄文、乙译日文、丙译英文、丁译德文所需时间即甲译俄文、乙译日文、丙译英文、丁译德文所需时间最少Z=28Z=28Z=28Z=28小时小时小时小时41分配问题效率矩阵分配问题效率矩阵分配问题效率矩阵分配问题效率矩阵任务任务任务任务人人人人员员员员A AB BC CD DE E甲甲甲甲12127 79 97 79 9乙乙乙乙8 89 96 66 66 6丙丙丙丙7 71717121214149 9丁丁丁丁151514146 66 61010戊戊戊戊4 410107 710109 94212127 79 97 79 98 89 96 66 66 67 71717121214149 9151514146 66 610104 410107 710109 97 7 6 6 7 7 6 6 4 4435 50 02 20 02 22 23 30 00 00 00 010105 57 72 29 98 80 00 04 40 06 63 36 65 5445 50 02 20 02 22 23 30 00 00 0  10105 57 72 29 98 80 00 04 40 06 63 36 65 5ØØ从只有一个从只有一个从只有一个从只有一个0 0 0 0元素的行开始，给这个元素的行开始，给这个元素的行开始，给这个元素的行开始，给这个0 0 0 0元素加圈，记元素加圈，记元素加圈，记元素加圈，记  455 50 02 20 02 22 23 30 00 00 0  10105 57 72 29 98 80 00 04 4ØØ6 63 36 65 5然后划去然后划去然后划去然后划去  所在的列的其他所在的列的其他所在的列的其他所在的列的其他0 0 0 0元素，记作元素，记作元素，记作元素，记作ØØ。

465 5  2 20 02 22 23 30 00 00 0  10105 57 72 29 98 80 00 04 4ØØ6 63 36 65 5ØØ从只有一个从只有一个从只有一个从只有一个0 0 0 0元素的列开始，给这个元素的列开始，给这个元素的列开始，给这个元素的列开始，给这个0 0 0 0元素加圈，记元素加圈，记元素加圈，记元素加圈，记  475 5  2 2ØØ2 22 23 30 00 00 0  10105 57 72 29 98 80 00 04 4ØØ6 63 36 65 5然后划去然后划去然后划去然后划去  所在的行的其他所在的行的其他所在的行的其他所在的行的其他0 0 0 0元素，记作元素，记作元素，记作元素，记作ØØ485 5  2 2ØØ2 22 23 30 00 0    10105 57 72 29 98 80 00 04 4ØØ6 63 36 65 5ØØ从只有一个从只有一个从只有一个从只有一个0 0 0 0元素的列开始，给这个元素的列开始，给这个元素的列开始，给这个元素的列开始，给这个0 0 0 0元素加圈，记元素加圈，记元素加圈，记元素加圈，记  495 5  2 2ØØ2 22 23 3ØØØØ    10105 57 72 29 98 80 00 04 4ØØ6 63 36 65 5然后划去然后划去然后划去然后划去  所在的行的其他所在的行的其他所在的行的其他所在的行的其他0 0 0 0元素，记作元素，记作元素，记作元素，记作ØØ。

505 5  2 2ØØ2 22 23 3ØØØØ    10105 57 72 29 98 8  0 04 4ØØ6 63 36 65 5ØØ从只有一个从只有一个从只有一个从只有一个0 0 0 0元素的列开始，给这个元素的列开始，给这个元素的列开始，给这个元素的列开始，给这个0 0 0 0元素加圈，记元素加圈，记元素加圈，记元素加圈，记  515 5  2 2ØØ2 22 23 3ØØØØ    10105 57 72 29 98 8  ØØ4 4ØØ6 63 36 65 5然后划去然后划去然后划去然后划去  所在的行的其他所在的行的其他所在的行的其他所在的行的其他0 0 0 0元素，记作元素，记作元素，记作元素，记作ØØ525 5  2 2ØØ2 22 23 3ØØØØ    10105 57 72 29 98 8  ØØ4 4ØØ6 63 36 65 5  的个数的个数的个数的个数m=4,m=4,m=4,m=4,而而而而n=5, m

转下一步转下一步转下一步53第三步：作最少的直线覆盖所有的第三步：作最少的直线覆盖所有的第三步：作最少的直线覆盖所有的第三步：作最少的直线覆盖所有的0 0 0 0元素，以确定该系数矩阵中能找到最多元素，以确定该系数矩阵中能找到最多元素，以确定该系数矩阵中能找到最多元素，以确定该系数矩阵中能找到最多的独立元素数的独立元素数的独立元素数的独立元素数ØØ对没有对没有对没有对没有  的行，打的行，打的行，打的行，打   ；；；；ØØ对已打对已打对已打对已打   行中所有含行中所有含行中所有含行中所有含0 0 0 0元素的列元素的列元素的列元素的列打打打打   ；；；；ØØ再对打再对打再对打再对打   列中含列中含列中含列中含0 0 0 0元素的行元素的行元素的行元素的行打打打打   ；；；；ØØ重复上述两步，直到得不出新的重复上述两步，直到得不出新的重复上述两步，直到得不出新的重复上述两步，直到得不出新的打打打打   行列为止行列为止行列为止行列为止ØØ对没有对没有对没有对没有打打打打   行画横线，有行画横线，有行画横线，有行画横线，有打打打打   列画纵线，就得到覆盖所有列画纵线，就得到覆盖所有列画纵线，就得到覆盖所有列画纵线，就得到覆盖所有0 0 0 0元素的最少直线元素的最少直线元素的最少直线元素的最少直线数。

数545 5  2 2ØØ2 22 23 3ØØØØ    10105 57 72 29 98 8  ØØ4 4ØØ6 63 36 65 5   对没有对没有对没有对没有  的行，打的行，打的行，打的行，打   555 5  2 2ØØ2 22 23 3ØØØØ    10105 57 72 29 98 8  ØØ4 4ØØ6 63 36 65 5      对已打对已打对已打对已打   行中所有含行中所有含行中所有含行中所有含0 0 0 0元素的列元素的列元素的列元素的列打打打打   565 5  2 2ØØ2 22 23 3ØØØØ    10105 57 72 29 98 8  ØØ4 4ØØ6 63 36 65 5         再对打再对打再对打再对打   列中含列中含列中含列中含0 0 0 0元素的行元素的行元素的行元素的行打打打打   575 5  2 2ØØ2 22 23 3ØØØØ    10105 57 72 29 98 8  ØØ4 4ØØ6 63 36 65 5         对没有对没有对没有对没有打打打打   行画横线行画横线行画横线行画横线585 5  2 2ØØ2 22 23 3ØØØØ    10105 57 72 29 98 8  ØØ4 4ØØ6 63 36 65 5         有有有有打打打打   列画纵线列画纵线列画纵线列画纵线59第四步：在没有被直线覆盖的部分中找出最小元素，然后第四步：在没有被直线覆盖的部分中找出最小元素，然后第四步：在没有被直线覆盖的部分中找出最小元素，然后第四步：在没有被直线覆盖的部分中找出最小元素，然后在在在在打打打打   行各元素都减去这行各元素都减去这行各元素都减去这行各元素都减去这最小元素，最小元素，最小元素，最小元素，而在打而在打而在打而在打   列中各元素都列中各元素都列中各元素都列中各元素都加上这加上这加上这加上这最小元素，以保证原来最小元素，以保证原来最小元素，以保证原来最小元素，以保证原来0 0 0 0元素不变，这样得到新的系元素不变，这样得到新的系元素不变，这样得到新的系元素不变，这样得到新的系数矩阵（它的最优解和原问题相同）。

若得到数矩阵（它的最优解和原问题相同）若得到数矩阵（它的最优解和原问题相同）若得到数矩阵（它的最优解和原问题相同）若得到n n n n个独立的个独立的个独立的个独立的0 0 0 0元素，则已经得到最优解否则回到第三步重复进行元素，则已经得到最优解否则回到第三步重复进行元素，则已经得到最优解否则回到第三步重复进行元素，则已经得到最优解否则回到第三步重复进行605 5  2 2ØØ2 22 23 3ØØØØ    10105 57 72 29 98 8  ØØ4 4ØØ6 63 36 65 5         没有被直线覆盖的最小元素为没有被直线覆盖的最小元素为没有被直线覆盖的最小元素为没有被直线覆盖的最小元素为2 2 2 2615 50 02 20 02 22 23 30 00 00 00 010105 57 72 29 98 80 00 04 40 06 63 36 65 5         625 50 02 20 02 22 23 30 00 00 0-2-28 83 35 50 09 98 80 00 04 4-2-24 41 14 43 3         在在在在打打打打   行各元素都减去这行各元素都减去这行各元素都减去这行各元素都减去这最小元素最小元素最小元素最小元素2 2 2 2。

637 70 02 20 02 24 43 30 00 00 00 08 83 35 50 011118 80 00 04 40 04 41 14 43 3         在打在打在打在打   列中各元素都加上这列中各元素都加上这列中各元素都加上这列中各元素都加上这最小元素最小元素最小元素最小元素2 2 2 2647 70 02 20 02 24 43 30 00 00 00 08 83 35 50 011118 80 00 04 40 04 41 14 43 3重复第二步，寻找独立重复第二步，寻找独立重复第二步，寻找独立重复第二步，寻找独立0 0 0 0元素657 70 02 20 02 24 43 30 00 00 00 08 83 35 50 011118 80 00 04 4  4 41 14 43 3ØØ从只有一个从只有一个从只有一个从只有一个0 0 0 0元素的行开始，给这个元素的行开始，给这个元素的行开始，给这个元素的行开始，给这个0 0 0 0元素加圈，记元素加圈，记元素加圈，记元素加圈，记  667 70 02 20 02 24 43 30 00 00 0ØØ8 83 35 50 011118 80 00 04 4  4 41 14 43 3然后划去然后划去然后划去然后划去  所在的列的其他所在的列的其他所在的列的其他所在的列的其他0 0 0 0元素，记作元素，记作元素，记作元素，记作ØØ。

677 70 02 20 02 24 43 30 00 00 0ØØ8 83 35 5  11118 80 00 04 4  4 41 14 43 3ØØ从只有一个从只有一个从只有一个从只有一个0 0 0 0元素的行开始，给这个元素的行开始，给这个元素的行开始，给这个元素的行开始，给这个0 0 0 0元素加圈，记元素加圈，记元素加圈，记元素加圈，记  687 70 02 20 02 24 43 30 00 0ØØØØ8 83 35 5  11118 80 00 04 4  4 41 14 43 3然后划去然后划去然后划去然后划去  所在的列的其他所在的列的其他所在的列的其他所在的列的其他0 0 0 0元素，记作元素，记作元素，记作元素，记作ØØ697 7  2 20 02 24 43 30 00 0ØØØØ8 83 35 5  11118 80 00 04 4  4 41 14 43 3ØØ从只有一个从只有一个从只有一个从只有一个0 0 0 0元素的列开始，给这个元素的列开始，给这个元素的列开始，给这个元素的列开始，给这个0 0 0 0元素加圈，记元素加圈，记元素加圈，记元素加圈，记  707 7  2 2ØØ2 24 43 30 00 0ØØØØ8 83 35 5  11118 80 00 04 4  4 41 14 43 3然后划去然后划去然后划去然后划去  所在的行的其他所在的行的其他所在的行的其他所在的行的其他0 0 0 0元素，记作元素，记作元素，记作元素，记作ØØ。

717 7  2 2ØØ2 24 43 30 00 0ØØØØ8 83 35 5  11118 80 00 04 4  4 41 14 43 3下面有二种分配方案：下面有二种分配方案：下面有二种分配方案：下面有二种分配方案：727 7  2 2ØØ2 24 43 3ØØ  ØØØØ8 83 35 5  11118 8  ØØ4 4  4 41 14 43 3下面有二种分配方案：第一种下面有二种分配方案：第一种下面有二种分配方案：第一种下面有二种分配方案：第一种730 01 10 00 00 00 00 00 01 10 00 00 00 00 01 10 00 01 10 00 01 10 00 00 00 0最优解如下：最优解如下：最优解如下：最优解如下：Z=32Z=32Z=32Z=3274分配问题结果如下：分配问题结果如下：分配问题结果如下：分配问题结果如下：Z=32Z=32Z=32Z=32任务任务任务任务人人人人员员员员A AB BC CD DE E甲甲甲甲12127 79 97 79 9乙乙乙乙8 89 96 66 66 6丙丙丙丙7 71717121214149 9丁丁丁丁151514146 66 61010戊戊戊戊4 410107 710109 9757 7  2 2ØØ2 24 43 3  ØØØØØØ8 83 35 5  11118 8ØØ  4 4  4 41 14 43 3下面有二种分配方案：第二种下面有二种分配方案：第二种下面有二种分配方案：第二种下面有二种分配方案：第二种760 01 10 00 00 00 00 01 10 00 00 00 00 00 01 10 00 00 01 10 01 10 00 00 00 0最优解如下：最优解如下：最优解如下：最优解如下：Z=32Z=3277分配问题结果如下：分配问题结果如下：分配问题结果如下：分配问题结果如下：Z=32Z=32任务任务任务任务人人人人员员员员A AB BC CD DE E甲甲甲甲12127 79 97 79 9乙乙乙乙8 89 96 66 66 6丙丙丙丙7 71717121214149 9丁丁丁丁151514146 66 61010戊戊戊戊4 410107 710109 978。