第5章  整数线性规划

       第5节  指 派 问 题

       在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每人的专长不同，各人完成任务不同(或所费时间)，效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小)。这类问题称为指派问题或分派问题(assignment problem)。

       指派问题的解法：

       第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。

       第二步：进行试指派，以寻求最优解。为此，按以下步骤进行。

       经第一步变换后，系数矩阵中每行每列都已有了0元素；但需找出n个独立的0元素。若能找出，就以这些独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。当n较小时，可用观察法、试探法去找出n个独立0元素。若n较大时，就必须按一定的步骤去找，常用的步骤为：

       (1) 从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎。这表示对这行所代表的人，只有一种任务可指派。然后划去◎所在列(行)的其他0元素，记作Φ。这表示这列所代表的任务已指派完，不必再考虑别人了。

       (2) 给只有一个0元素列(行)的0元素加圈，记作◎；然后划去◎所在行的0元素，记作Φ。

       (3) 反复进行(1)，(2)两步，直到所有0元素都被圈出和划掉为止。

       (4) 若仍有没有划圈的0元素，且同行(列)的0元素至少有两个(表示对这个可以从两项任务中指派其一)。这可用不同的方案去试探。从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其他0元素。可反复进行，直到所有0元素都已圈出和划掉为止。

       (5) 若◎元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m＜n，则转入下一步。

       第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数。为此按以下步骤进行：

       (1) 对没有◎的行打√号；

       (2) 对已打√号的行中所有含Φ元素的列打√号；

       (3) 再对打有√号的列中含◎元素的行打√号；

       (4) 重复(2)，(3)直到得不出新的打√号的行、列为止。

       (5) 对没有打√号的行画一横线，有打√号的列画一纵线，这就得到覆盖所有0元素的最少直线数。

       第四步：对②矩阵进行变换的目的是增加0元素。为此在没有被直线覆盖的部分中找出最小元素。然后在打√行各元素中都减去这最小元素，而在打√列的各元素都加上这最小元素，以保证原来0元素不变。这样得到新系数矩阵(它的最优解和原问题相同)。若得到n个独立的0元素，则已得最优解，否则回到第三步重复进行。

       当指派问题的系数矩阵，经过变换得到了同行和同列中都有两个或两个以上0元素时。这时可以任选一行(列)中某一个0元素，再划去同行(列)的其他0元素。这时会出现多重解。

下载需要: 0 积分

附件：  第5章 整数线性规划-第5节.ppt