指派问题及其标准形式

1．指派问题及其标准形式

在现实生活中，有各种性质的指派问题。例如，有若干项工作需要分配给若干人（或部门）来完成；有若干项合同需要选择若干个投标者来承包；有若干班级需要安排在各教室上课等等。诸如此类的问题，它们的基本要求是在满足特定的指派要求条件下，使指派方案的总体效果最佳。由于指派问题的多样性，有必要定义指派问题的标准形式。

指派问题的标准形式（以人和事为例）是：有n个人和n件事，已知第i个人作第j件事的费用为c_ij（i，j=1，2，…，n），要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费用最少。

一般称矩阵

为指派问题的系数矩阵。在实际问题中，根据c_ij的具体意义，矩阵C可以有不同的名称，如费用矩阵、成本矩阵、时间矩阵等。系数矩阵C中，第i行各元素表示第i人做各事的费用，第j列各元素表示第j事由各人做的费用。

为了建立标准指派问题的数学模型，引入n²个0—1变量

模型中，约束条件组式②表示每个人必做且只做一件事每件事必有且只有一个人去做，约束条件组式③表示每件事必有且只有一个人去做。

对于问题的每一个可行解，可用矩阵

来表示。当然，作为可行解，矩阵中每一行都有且只有一个1，以满足约束条件组式②，每一列都有且只有一个1，以满足约束条件组式③。容易知道，像这样的指派问题有n!个可行解。

例3.24某公司计划装修五家新商店B₁，B₂，B₃，B₄，B₅。为了尽早装修完毕开始营业，公司计划由五家装修公司A₁，A₂，A₃，A₄，A₅，每家装修一个新商店。装修公司A_i对新商店B_j的装修费用的投标为c_ij，（万元）均见表3.67。该公司应当对五家装修公司怎样分配装修任务，才能使总装修费用最少?

表3.67

这是一个标准的指派问题。设0—1变量