《运筹学-44 指派问题 (讲义8)-精品文档整理.ppt》由会员分享，可在线阅读，更多相关《运筹学-44 指派问题 (讲义8)-精品文档整理.ppt（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Page 1第四节第四节指派问题指派问题Page 2设设n 个人被分配去做个人被分配去做n 件工作，规定每个人只做一件工作，件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第每件工作只有一个人去做。已知第i个人去做第个人去做第j 件工作的效率件工作的效率（ 时间或费用）为时间或费用）为Cij(i=1.2n;j=1.2n)并假设并假设Cij 0。问应。问应如何分配才能使总效率（如何分配才能使总效率（ 时间或费用）最高？时间或费用）最高？设设决策变量决策变量 ),.,2 , 1,(ji0ji1njixij 件事件事个人做第个人做第不指派第不指派第件事件事个人做第个人做第指派第指派第称称
2、（Cij）n 为为效率矩阵效率矩阵Page 3指派问题的数学模型为：指派问题的数学模型为： ).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxcZijniijnjijninjijij或或取取Page 4例例1 有一份中文说明书，需译成英、日、德、俄四种文字，分有一份中文说明书，需译成英、日、德、俄四种文字，分别记作别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？何分派任务，可使总时间最少？
3、 任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁5982Page 5ij671124598(c ) 311045982 Page 6 从从效率效率矩阵矩阵cij的某行（列）元素的某行（列）元素中分别减去中分别减去(或加上或加上)一个常数一个常数ui，得到，得到一个新的效率矩阵一个新的效率矩阵bij，则以，则以bij为效率为效率矩阵的分配问题与以矩阵的分配问题与以cij为效率矩阵的分配问题具有相同为效率矩阵的分配问题具有相同的最优解。的最优解。11121n21212nijn1n2nncc.cccc(c ) .cc.c 11121n21212nn1n2nnckck.ckccc
4、 .cc.c（匈牙利法仅适用于最小化问题，且（匈牙利法仅适用于最小化问题，且cij非负）非负）Page 7解：解：1）变换效率矩阵，增加变换效率矩阵，增加0元素元素。2142 289541013895421176)( ijc 06733902451009545 01733402401004542）试指派（找独立试指派（找独立0元素）元素） 17334241454 找到找到 3 个个独立零元素：独立零元素：（位于不同行不同列的（位于不同行不同列的零元素）零元素） Page 83）检验检验 若圈出的若圈出的 0元素每行每列有且仅有一个，则将圈出的元素每行每列有且仅有一个，则将圈出的0元素对应的变量
5、取为元素对应的变量取为1，其余变量取为，其余变量取为0，即得到最优指，即得到最优指派方案。派方案。 否则，转入下一步。否则，转入下一步。Page 94）作最少的直线覆盖所有作最少的直线覆盖所有0元素元素 17334241454Th：独立零元素的最多个数：独立零元素的最多个数=能覆盖所有零元素的最少能覆盖所有零元素的最少直线数直线数 （位置不唯一）（位置不唯一）步骤参见：步骤参见： P150Page 105）增加零元素增加零元素在在 没有被直线覆盖的元素中选择最小元素；没有被直线覆盖的元素中选择最小元素；在没有在没有被直线覆盖被直线覆盖的行中所有元素的行中所有元素都减去该最小元素；都减去该最小元
6、素；在已被直线覆盖的列中的所有元素都加上在已被直线覆盖的列中的所有元素都加上该最小元素；该最小元素； 得到新的矩阵，重复得到新的矩阵，重复2）步进行试指派）步进行试指派Page 11 6244251343000 0 00试指派试指派 6244251343得到得到4个独立零元素，个独立零元素， 所以最优解矩阵为：所以最优解矩阵为： 0100001000011000即完成即完成4个任务的总时间最少个任务的总时间最少为：为：241+8=15Page 121) 变换指派问题的效率矩阵变换指派问题的效率矩阵(cij)为为(bij)，使在，使在(bij)的各行各列的各行各列中都出现中都出现0元素，即元素，
7、即 从从(cij)的每行元素都减去该行的最小元素；的每行元素都减去该行的最小元素； 再从所得新系数矩阵的每列元素中减去该列的最小元素。再从所得新系数矩阵的每列元素中减去该列的最小元素。2) 进行试指派，以寻求最优解。进行试指派，以寻求最优解。 在在(bij)中找尽可能多的独立中找尽可能多的独立0元素，若能找出元素，若能找出n个独立个独立0元元素，就以这素，就以这n个独立个独立0元素对应解矩阵元素对应解矩阵(xij)中的元素为中的元素为1，其余，其余为为0，这就得到最优解。，这就得到最优解。Page 13找独立找独立0元素，常用的步骤为：元素，常用的步骤为： 从只有一个从只有一个0元素的行开始，
8、给该行中的元素的行开始，给该行中的0元素加圈，记作元素加圈，记作 。然后划去然后划去 所在列的其它所在列的其它0元素，记作元素，记作 ；这表示该列所代表的；这表示该列所代表的任务已指派完，不必再考虑别人了。依次进行到最后一行。任务已指派完，不必再考虑别人了。依次进行到最后一行。 从只有一个从只有一个0元素的列开始（画元素的列开始（画的不计在内），给该列中的的不计在内），给该列中的0元素加圈，记作；然后划去元素加圈，记作；然后划去 所在行的所在行的0元素，记作元素，记作 ，表示，表示此人已有任务，不再为其指派其他任务了。依次进行到最后一列。此人已有任务，不再为其指派其他任务了。依次进行到最后一列
9、。 若仍有没有划圈的若仍有没有划圈的0元素，且同行元素，且同行(列列)的的0元素至少有两个，比元素至少有两个，比较这行各较这行各0元素所在列中元素所在列中0元素的数目，选择元素的数目，选择0元素少的那列的这元素少的那列的这个个0元素加圈元素加圈(表示选择性多的要表示选择性多的要“礼让礼让”选择性少的选择性少的)。然后划。然后划掉同行同列的其它掉同行同列的其它0元素。可反复进行，直到所有元素。可反复进行，直到所有0元素都已圈出元素都已圈出和划掉为止。和划掉为止。Page 14 若若 元素的数目元素的数目m 等于矩阵的阶数等于矩阵的阶数n（即：（即：mn），那么这指，那么这指派问题的最优解已得到。
10、若派问题的最优解已得到。若m n, 则转入下一步。则转入下一步。3) 用最少的直线通过所有用最少的直线通过所有0元素。其方法：元素。其方法： 对没有的行打对没有的行打“”； 对已打对已打“” 的行中所有含的行中所有含元素的列打元素的列打“” ； 再对打有再对打有“”的列中含的列中含 元素的行打元素的行打“” ； 重复重复、直到得不出新的打直到得不出新的打号的行、列为止；号的行、列为止； 对没有打对没有打号的行画横线，有打号的行画横线，有打号的列画纵线，这就得到覆盖号的列画纵线，这就得到覆盖所有所有0元素的最少直线数元素的最少直线数 l 。注：注：l 应等于应等于m，若不相等，说明试指派过程有误
11、，回到第，若不相等，说明试指派过程有误，回到第2步，另行试步，另行试指派；若指派；若 lm n，表示还不能确定最优指派方案，须再变换当前的系，表示还不能确定最优指派方案，须再变换当前的系数矩阵，以找到数矩阵，以找到n个独立的个独立的0元素，为此转第元素，为此转第4步。步。Page 154) 变换矩阵变换矩阵(bij)以增加以增加0元素元素在没有被直线通过的所有元素中找出最小值，没有被直线通过在没有被直线通过的所有元素中找出最小值，没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍相同。转回
12、第小值。新系数矩阵的最优解和原问题仍相同。转回第2步。步。Page 16例例2 已知四人分别完成四项工作所需时间如下表，求最优分已知四人分别完成四项工作所需时间如下表，求最优分配方案。配方案。 任务任务人员人员ABCD甲甲215134乙乙1041415丙丙9141613丁丁78119Page 17解：解：1）变换系数矩阵，增加变换系数矩阵，增加0元素。元素。79429118713161491514410413152 2424104750111006211130 00102350960607130 001023509606071302）试指派（找独立）试指派（找独立0元素）元素） 独立独立0元素
13、的个数为元素的个数为4 , 指派问题的最优指指派问题的最优指派方案即为甲负责派方案即为甲负责D工作，乙负责工作，乙负责B工作，工作，丙负责丙负责A工作，丁负责工作，丁负责C工作。这样安排工作。这样安排能使总的工作时间最少，为能使总的工作时间最少，为4491128。Page 18例例3 已知四人分别完成四项工作所需时间如下表，求最优分已知四人分别完成四项工作所需时间如下表，求最优分配方案。配方案。 任务任务人员人员ABCD甲甲21097乙乙154148丙丙13141611丁丁415139Page 19例例4 已知五人分别完成五项工作耗费如下表，求最优分配已知五人分别完成五项工作耗费如下表，求最优
14、分配方案。方案。 任务任务人员人员ABCDE甲甲759811乙乙9127119丙丙85468丁丁73696戊戊467511Page 204347511576469637964589117129118957 7132036304520142405263402-1 -2解：解：1）变换系数矩阵，增加）变换系数矩阵，增加0元素。元素。Page 21 5032015304310140305242402 50320153043101403052424022）试指派（找独立）试指派（找独立0元素）元素） 独立独立0元素的个数元素的个数l45，故画直线调整矩阵。，故画直线调整矩阵。Page 22 50320
15、15304310140305242402选择直线外的最小元素选择直线外的最小元素为为1；直线外元素减；直线外元素减1，直线交点元素加直线交点元素加1，其，其他保持不变。他保持不变。Page 23 5033004203310240306231301l =m=4 n=5选择直线外最小元素为选择直线外最小元素为1，直线外元素减直线外元素减1，直线交，直线交点元素加点元素加1，其他保持不，其他保持不变，得到新的系数矩阵。变，得到新的系数矩阵。Page 24 6044003202300230206130300总费用为总费用为=5+7+6+6+4=28=5+7+6+6+4=28注：此问题有多个最优解注：此
16、问题有多个最优解Page 25 6044003202300230206130300总费用为总费用为=7+9+4+3+5=28=7+9+4+3+5=28Page 26 6044003202300230206130300总费用为总费用为=8+9+4+3+4=28=8+9+4+3+4=28Page 27例例5 已知五人分别完成四项工作耗费如下表，求最优分配已知五人分别完成四项工作耗费如下表，求最优分配方案。方案。 任务任务人员人员ABCD甲甲1051520乙乙210515丙丙3151413丁丁5276戊戊94158要求：要求：1）甲必须保证分配一件工作；）甲必须保证分配一件工作； 2）丁由于某种原因
17、不能承担工作）丁由于某种原因不能承担工作DPage 2810515 202105150315 14 13052709415MM80 解：增加虚拟工作解：增加虚拟工作E，相应的效率矩阵为，相应的效率矩阵为Page 29最优指派为：最优指派为： 甲甲-B乙乙-C丙丙-A丁丁-休息休息戊戊-DPage 30注注：1）最大化指派问题）最大化指派问题 选择效率矩阵选择效率矩阵cij中最大中最大 元素元素m, 变换效率矩阵为变换效率矩阵为bij=m-cij，则以，则以bij为效率矩阵的最小化指派问题与原为效率矩阵的最小化指派问题与原最大化指派问题有相同的最优解。最大化指派问题有相同的最优解。2）人数和工作数不等）人数和工作数不等 增加虚拟的人或工作。增加虚拟的人或工作。3）一个人可以做几件工作）一个人可以做几件工作 把这把这“一个人一个人”拆成拆成“几个人几个人”去处理。去处理。Page 31练习：练习： 已知五人分别完成五项工作耗费如下表，求最优分已知五人分别完成五项工作耗费如下表，求最优分 配方案。配方案。 任务任务人员人员ABCDE甲甲127979乙乙89666丙丙71212149丁丁10146610戊戊4107109