第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