第五节 指派问题     (1) (2) (3)
    在实际问题中，常常会碰到这样的问题，要指派n个人去完成n项不同任务，每个人必须完成其中一项而且仅仅一项。但由于个人的专长不同，任务的难易程度不一样，所以完成不同任务的效率就不同，那么应该指派哪个人去完成哪项任务，能使总的效率最好呢？这就是典型的指派问题。
    例6 今欲指派张王李赵四人加工A、B、C、D四种不同的零件，每人加工四种零件所需要的时间如下表所示，问应该派谁加工何种零件可使总的花费时间最少？
        
    在类似问题中都必须给出一个像上表一样的矩阵C，称为效率矩阵。
        
    矩阵中的元素表示指派第i个人去完成第j项任务时的效率。
    求解这类问题时，通常引入0—1变量：
        
    于是，对于极小化问题，指派问题数学模型为：
        
    从模型看，指派问题是特殊的0—1规划，也是特殊的运输问题，可以用这两种问题的求解方法求解。但这样做是不合算的。