第4章整数规划_第5节.pptVIP

第5节 指 派 问 题;对于每个指派问题，都有相应的效率矩阵或系数矩阵，其元素cij＞0(i , j=1,2，…，n)表示指派第i人去完成第j项任务时的效率(或时间、成本等)。 引入变量xij：;可行解矩阵的特点：与效率矩阵同阶数；每行只有一个非零元素，值为1，并且位于不同行不同列，其余元素均为0，这表示人与任务是一对一的关系;匈牙利法基本原理;定义 效率矩阵中，有一组处在不同行不同列的零元素，称为独立零元素。即圈0元素 ;指派问题的匈牙利解法;;;(1) 从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎。这表示对这行所代表的人，只有一种任务可指派。然后划去◎所在列(行)的其他0元素，记作Φ。这表示这列所代表的任务已指派完，不必再考虑别人了。;注意：矩阵中符号 即是文中的◎符号。;(4) 若仍有没有划圈的0元素，且同行(列)的0元素至少有两个(表示对这个可以从两项任务中指派其一)。这可用不同的方案去试探。从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其他0元素。可反复进行，直到所有0元素都已圈出和划掉为止。 ;;;;第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数。为此按以下步骤进行： (1) 对没有◎的行打√号； (2) 对已打√号的行中所有含Φ元素的列打√ 号； (3) 再对打有√号的列中含◎元素的行打√号； (4) 重复(2)，(3)直到得不出新的打√号的行、 列为止。 (5) 对没有打√号的行画一横线，有打√号的列画一纵线，这就得到覆盖所有0元素的最少直线数。 ;由此可见l=4＜n。所以应继续对②矩阵进行变换。 转第四步。;令这直线数为l。若l＜n，说明必须再变换当前的系数矩阵，才能找到n个独立的0元素，为此转第四步：;;;;;;;;非标准型的指派问题;系数矩阵不是方阵，目标仍为最小化问题： 系数矩阵化为方阵 m人分配n项工作，系数矩阵 为 矩阵，且 (1)若 ，则增添虚构的 行，补成方阵，但是新增的行元素均为0： ; (2)若 ，则增添虚构的 列，补成方阵，但是新增的列元素均为0：