第4章整数规划第5节.ppt

第第5 5节节 指指 派派 问问 题题•n项任务由n个人完成，各人完成各任务的效率不同于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小)这类问题称为指派问题指派问题或分派问题或分派问题(assignment problem)•例7 有一份中文说明书，需译成英、日、德、俄四种文字分别记作E、J、G、R现有甲、乙、丙、丁四人他们将中文说明书翻译成不同语种的说明书所需时间如表5-7所示问应指派何人去完成何工作，使所需总时间最少?•对于每个指派问题，都有相应的效率矩阵或系数矩阵，其元素cij＞0(i , j=1,2，…，n)表示指派第i人去完成第j项任务时的效率(或时间、成本等)•引入变量xij：当问题要求极小化时数学模型是： ①②③④可行解矩阵的特点：与效率矩阵同阶数；每行只有一个非零元素，值为1，并且位于不同行不同列，其余元素均为0，这表示人与任务是一对一的关系•约束条件②说明第 j 项任务只能由1人去完成•约束条件③说明第 i 人只能完成1项任务•满足约束条件②～④的可行解 xij 也可写成表格或矩阵形式，称为解矩阵解矩阵。

•如例7的一个可行解矩阵 指派问题的求解方法——匈牙利法匈牙利法匈牙利法基本原理•定理定理 若将指派问题的效率矩阵的某行（列）都减去同一常数 t，则新效率矩阵对应的指派问题和原指派问题最优解相同推论推论 将指派问题的效率矩阵的各行各列分别减去相应的行或列的最小元素，则新指派问题与原指派问题有相同的最优解新效率矩阵中必然出现一些零元素，分两类：(1) 圈0元素，表示采取指派行为(2) 被划去的0元素，表示不采取指派行为•定义定义 效率矩阵中，有一组处在不同行不同列的零元素，称为独立零元素即圈0元素指派问题的匈牙利解法 步骤1 变换系数矩阵先对各行元素分别减去本行中最小元素，再对各列元素分别减去本列中最小元素步骤2 在变换后的系数矩阵中确定独立零元素，若独立零元素为n个，得到最优解，否则，作能覆盖所有零元素的最小直线数目的直线集合，转步骤3步骤3 继续变换系数矩阵，在未被覆盖的元素中找出一个最小元素，未被覆盖的元素所在行或列中各元素都减去这一最小元素，从而出现零元素•经第一步变换后，系数矩阵中每行每列都已有了经第一步变换后，系数矩阵中每行每列都已有了0 0元素；但需找出元素；但需找出n n个独立的个独立的0 0元素。

若能找出，就元素若能找出，就以这些独立以这些独立0 0元素对应解矩阵元素对应解矩阵( (x xijij) )中的元素为中的元素为1 1，，其余为其余为0 0，这就得到最优解当，这就得到最优解当n n较小时，可用观较小时，可用观察法、试探法去找出察法、试探法去找出n n个独立个独立0 0元素若n n较大时，较大时，就必须按一定的步骤去找，常用的步骤为：就必须按一定的步骤去找，常用的步骤为： (1) (1) 从只有一个从只有一个0 0元素的行元素的行( (列列) )开始，给这个开始，给这个0 0元素元素加圈，记作加圈，记作◎◎这表示对这行所代表的人，只有这表示对这行所代表的人，只有一种任务可指派然后划去一种任务可指派然后划去◎◎所在列所在列( (行行) )的其他的其他0 0元素，记作元素，记作ΦΦ这表示这列所代表的任务已指派这表示这列所代表的任务已指派完，不必再考虑别人了完，不必再考虑别人了2) (2) 给只有一个给只有一个0 0元素列元素列( (行行) )的的0 0元素加圈，记作元素加圈，记作◎◎；；然后划去然后划去◎◎所在行的所在行的0 0元素，记作元素，记作ΦΦ3) (3) 反复进行反复进行(1)(1)，，(2)(2)两步，直到所有两步，直到所有0 0元素都被圈出元素都被圈出和划掉为止。

和划掉为止注意：矩阵中符号 即是文中的◎符号(4) (4) 若若仍仍有有没没有有划划圈圈的的0 0元元素素，，且且同同行行( (列列) )的的0 0元元素素至至少少有有两两个个( (表表示示对对这这个个可可以以从从两两项项任任务务中中指指派派其其一一) )这这可可用用不不同同的的方方案案去去试试探探从从剩剩有有0 0元元素素最最少少的的行行( (列列) )开开始始，，比比较较这这行行各各0 0元元素素所所在在列列中中0 0元元素素的的数数目目，，选选择择0 0元元素素少少的的那那列列的的这这个个0 0元元素素加加圈圈( (表表示示选选择择性性多多的的要要“礼礼让让”选选择择性性少少的的) )然然后后划划掉掉同同行行同同列列的的其其他他0 0元元素素可可反反复复进进行行，，直直到到所所有有0 0元素都已圈出和划掉为止元素都已圈出和划掉为止5) (5) 若若◎◎元素的数目元素的数目m m等于矩阵的阶数等于矩阵的阶数n n，那么这指派，那么这指派问题的最优解已得到若问题的最优解已得到若m m＜＜n n，则转入下一步则转入下一步第5节  指派问题•例8 求表中所示效率矩阵的指派问题的最小解。

第5节  指派问题•解解 按上述第一步，将这系数矩阵进行变换经一次运算即得每行每列都有0元素的系数矩阵，第5节  指派问题•再按上述步骤运算，得到这里◎的个数m=4，而n=5；所以解题没有完成，这时应按以下步骤继续进行 注意：矩阵中符号即是文中的◎符号•第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数为此按以下步骤进行：(1) 对没有◎的行打√号；(2) 对已打√号的行中所有含Φ元素的列打√ 号；(3) 再对打有√号的列中含◎元素的行打√号；(4) 重复(2)，(3)直到得不出新的打√号的行、 列为止5) 对没有打√号的行画一横线，有打√号的列画一纵线，这就得到覆盖所有0元素的最少直线数由此可见l=4＜n所以应继续对②矩阵进行变换转第四步•令这直线数为l若l＜n，说明必须再变换当前的系数矩阵，才能找到n个独立的0元素，为此转第四步：第四步：对②矩阵进行变换的目的是增加0元素为此在没有被直线覆盖的部分中找出最小元素然后在打√行各元素中都减去这最小元素，而在打√列的各元素都加上这最小元素，以保证原来0元素不变这样得到新系数矩阵(它的最优解和原问题相同)。

若得到n个独立的0元素，则已得最优解，否则回到第三步重复进行在例8的矩阵②中，在没有被覆盖部分(第3、5行)中找出最小元素为2，然后在第3、5行各元素分别减去2，给第1列各元素加2，得到新矩阵③按第二步，找出所有独立的0元素，得到矩阵④第5节  指派问题④③第5节  指派问题•已具有n个独立0元素这就得到了最优解，相应的解矩阵为• 由解矩阵得最优指派方案：甲—B，乙—D，丙—E，丁—C，戊—A还可以得到另一最优指派方案甲—B，乙—C，丙—E，丁—D，戊—A所需总时间为min z=32•当指派问题的系数矩阵，经过变换得到了同行和同列中都有两个或两个以上0元素时这时可以任选一行(列)中某一个0元素，再划去同行(列)的其他0元素这时会出现多重解非标准型的指派问题•目标函数为max的问题，系数矩阵为方阵： 化为目标函数min的问题 对 令 其中M是足够大的常数(如选 中最大元素为M)，这时系数矩阵变为 ， ， 目标函数经变换后，即解 新指派问题符合匈牙利法的条件•系数矩阵不是方阵，目标仍为最小化问题： 系数矩阵化为方阵 m人分配n项工作，系数矩阵 为 矩阵，且 (1)若 ，则增添虚构的 行，补成方阵，但是新增的行元素均为0： (2)若 ，则增添虚构的 列，补成方阵，但是新增的列元素均为0： 。