一般的指派问题

3．一般的指派问题

在实际应用中，常会遇到各种非标准形式的指派问题。通常的处理方法是先将它们化为标准形式，然后再用匈牙利解法解之。

3.1最大化指派问题

设最大化指派问题系数矩阵C=（cij）n×n，其中最大元素为m。令矩阵B=（bij）n×n=（m－cij）n×n，则以B为系数矩阵的最小化指派问题和以C为系数矩阵的原最大化指派问题有相同最优解。

例3.25指派问题系数矩阵

的最大元素为c₃₃=16，取m=16，令

则以C为系数矩阵的最大化指派问题和以B为系数矩阵的最小化指派问题有相同最优解。

当系数矩阵为利润矩阵、产量矩阵等时，就产生最大化指派问题。

3.2人数和事数不等的指派问题

若人少事多，则添上一些虚拟的“人”。这些虚拟的“人”做各事的费用系数可取0（理解为这些费用实际上不会发生），也可取足够大的数M（理解为若指派这些虚拟的“人”去做那些事，则那些事实际上没人去做）。

若人多事少，则添上一些虚拟的“事”，这些“事”被各人做的费用系数同样可取0，也可取足够大的数M。

3.3一个人可做几件事的指派问题

若某人可做几件事，则可将该人化作相同的几个“人”来接受指派，这几个“人”做同一件事的费用系数当然都一样。

3.4某事一定不能由某人做的指派问题

若某事一定不能由某人做，则可将相应的费用系数取作足够大的数M。

例3.26对于例3.24的指派问题，经公司研究决定，舍弃装修公司A₄和A₅，而让技术力量较强的装修公司A₁，A₂和A₃来承包。根据实际情况，可以允许每家装修公司承包一个或两个商店。求使总费用最少的指派方案。

反映投标费用的系数矩阵为表3.68所示。

表3.68

由于每家装修公司最多可以承包两个新商店，因此，把每家装修公司化作相同的两家，这样系数矩阵为表3.69所示。

表3.69

上面的系数矩阵有六行五列，为了使“人”和“事”的数目相同，引入一件虚拟事B₆，使之成为标准指派问题的系数矩阵，如表3.70。

表3.70

现在，就可以利用匈牙利解法求最优指派方案，具体过程略。

最终，最优指派方案应由A₁承包B₁和B₃，A₂承包B₂，A₃承包B₄和B₅。这样，总的装修费用最省，是4+7+9+8+7=35万元。