第4章整数规划-指派问题

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

【例1】

某厂拟派4个维修小组去维修4台机车，他们相应的完成工作所需时间cij(i,j=1,2,

3,4)由右表给出。如何给每个

小组安排工作才能使完成任务

的总时间最少。4指派问题

指派问题也称分配或配置问题，是资源合理配置或最优匹配问题。指派问题通常划分为标准和非标准的指派问题。4.1指派问题的引入

机车1234小组12151342104141539141613478119

解：该指派问题是安排维修小组去维修机车，其决策变量为4指派问题

机车1234小组1x11x12x13x142x21x22x23x243x31x32x33x344x41x42x43x44该问题的数学模型为：任务约束

人员约束

4指派问题

【例2】

某商业

公司计划开办五家新商

店。为了尽早建成营业，

商业公司决定由5家建

筑公司分别承建。已知

建筑公司Ai(i=1,2,3,4,5)

对新商店Bj(j=1,2,3,4,5)

的建造费用的报价（万

元）为cij

，见下表。商

业公司应当对5家建筑公司怎样分派建筑任务，才能使总的建筑费用最少？商店B1B2B3B4B5建公A14871512A279171410A3691287A46714610A56912106

解：该指派问题是安排建筑公司承建商店，其决策变量为4指派问题

该问题的数学模型为：商店B1B2B3B4B5建公A1x11x12x13x14x15A2x21x22x23x24x25A3x31x32x33x34x35A4x41x42x43x44x45A5x51x52x53x54x55

显然指派问题与运输问题相类似，该问题的指派平衡表如下：4指派问题

商店B1B2B3B4B5任务建公A148715121x11x12x13x14x15A2791714101x21x22x23x24x25A36912871x31x32x33x34x35A467146101x41x42x43x44x45A569121061x51x52x53x54x55公司数111114指派问题

4.2标准指派问题的数学模型

一般地，指派问题的一般提法是：有n项任务，需分配给n个人员（或设备）去完成，已知每个人员完成某项工作的效率（或成本等）为cij，如何给每个人员指派一项工作，使得完成任务的总效率最高（或总成本最少），见下表。任务1…j…n人1c11…c1j…c1n………………ici1…cij…cin………………ncn1…cnj…cnn解：4指派问题

称矩阵C为效率矩阵（在其他问题中，可根据实际意义称为费用矩阵等），其元素cij体现了第i个人完成第j项工作时的效率，即

决策变量xij排成的n×n矩阵X称为决策变量矩阵,其中4指派问题

分析：指派问题解的特征是它有n个1，其它都是0，且这n个1位于决策变量矩阵的不同行、不同列，每一种情况为指派问题的一个可行解，共n!个解。指派问题是：把这n个1放到的n

2个位置的什么地方可使耗费的总资源最少？（解最优）【例3】

对于效率矩阵决策变量矩阵都是指派问题的最优解。4指派问题

4.3指派问题的求解

指派问题既是一类特殊的整数规划问题，又是特殊的运输问题，因此可以用多种相应的解法来求解，然而这些解法都没有充分利用指派问题的特殊性质，有效地减少计算量，直到1955年库恩（W.W.Kuhn）提出的匈牙利法才有效地解决了指派问题。匈牙利法的理论基础

定义2

独立零元素组在效率矩阵中，有一组在不同行不同列的零元素，称为独立零元素组，其每个元素称为独立零元素。【例4】

已知效率矩阵求其独立零元素组。4指派问题

解：可行解｛c12=0，c24=0，c31=0，c43=0｝是一个独立零元素组，c12=0，c24=0，c31=0，c43=0分别称为独立零元素；

｛c12=0，c23=0，c31=0，c44=0｝也是一个独立零元素组，而｛c14=0，c23=0，c31=0，c44=0｝就不是独立零元素组.

根据上述对效率矩阵中零元素的分析，将效率矩阵中出现的独立零元素组中零元素所处的位置，在决策变量矩阵中令相应的xij=1，其余的xij=0，就可找到指派问题的一个最优解,如例14。

问题：在有的问题中效率矩阵中独立零元素的个数不够n个，这样就无法求出最优指派方案，需作进一步的分析，首先给出下述定理。4指派问题

定理3

设指派问题的效率矩阵为C=[cij]n×n，若将该矩阵的某一行（或某一列）的各个元素都减去同一常数k（k可正可负），得到新的效率矩阵C’=[c’ij]n×n

，则以C’为效率矩阵的新的指派问题与原指派问题的最优解相同。

推论若将指派问题的效率矩阵每一行或每一列分别减去各行或各列的最小元素，则得到新指派问题与原指派问题有相同的最优解。

定理4

效率矩阵中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。4指派问题

匈牙利法求解步骤

第一步：变换效率矩阵，将各行各列都减去当前各行、各列中最小元素。

第二步：标记新矩阵的独立零元素。1）行检验对变换后的效率矩阵进行逐行检验，若某行只有一个未标记的零元素时，用“*”将该零元素做标记，然后将被标记的零元素所在的列的其它未标记的零元素用“×”将该零元素标记。2）列检验与行检验过程类似，对进行了行检验的矩阵逐列进行检验，对每列只有一个未被标记的零元素，用“*”将该零元素做一标记，然后将该元素所在行的其他未被标记的零元素打“×”将该零元素标记。重复上述列检验，直到每一列都没有未被标记的零元素或有两个未被标记的零元素为止。

这时可能出现以下三种情况：

①每一行均有标记“*”出现，“*”的个数m恰好等于n；

②存在未标记的零元素，但他们所在的行和列中，未标记过的零元素均至少有两个；

③不存在未被标记过的零元素，“*”的个数m<n。4指派问题

3）试指派

若情况①出现，则可进行试指派：令“*”记号的决策变量取值为1，其他决策变量取值均为零，得到一个最优指派方案，停止计算。

若情况②出现，则对每行、每列的其它未被标记的零元素任选一个，加上标记“*”，即给该零元素标记“*”，然后给同行、同列的其它未被标记的零元素加标记“×”，然后再进行行、列检验，可能出现情况①或③，出现情况①就会得到最优指派，停止计算。

若情况③出现，则要转入下一步。

第三步：作最少直线覆盖当前所有零元素。4指派问题

1）对新矩阵中所有不含“*”元素的行打√；2）对打√的行中，所有打×零元素所在的列打√；

3）对所有打√列中标记“*”元素所在行打√；4）重复上述2），3）步，直到不能进一步打√为止；5）对未打√的每一行划一直线，对已打√的每一列划一纵线，即得到覆盖当前0元素的最少直线数。

第四步：对矩阵未被直线覆盖过的元素中找最小元素，将打√行的各元素减去这个最小元素，将打√列的各元素加上这个最小元素（以避免打√行中出现负元素），这样就增加了零元素的个数，返回第二步。【例5】

求解例1和例24指派问题

解：

故可得到指派问题的最优解X，这样安排能使总的维修时间最少，维修时间为z=4＋4＋9＋11=28（小时）。

故可得到指派问题的最优解X，这样安排能使总的建造费用最少，建造费用为z=7＋9＋6＋6＋6=34（万元）。4指派问题

4指派问题

4.4非标准指派问题

在实际应用中，常会遇到非标准形式，如求最大值，人数与工作数不相等以及不可接受的配置（某人不可完成某项任务）等特殊指派问题。解决的思路是先化成标准形式，然后再用匈牙利法求解，即对效率矩阵通过适当变换使得满足匈牙利算法的条件再求解。最大化的指派问题

最大化指派问题的一般形式为

解决办法：设最大化的指派问题的系数矩阵为C=[cij]n×n

，M=max{c11,c12,…,cnn}，令B=[bij]n×n=[M-cij]n×n

，则以B为效率矩阵的最小化指派问题和以C为效率矩阵的原最大化指派问题有相同的最优解。

4指派问题

【例6】

某工厂有4名工人A1,A2,A3,A4,分别操作4台车床B1,B2,B3,B4,每小时单产量如

右表，求产值最大的分配方

案。车间B1B2B3B4工人A110987A23456A32112A44356

解：令M=max{10,9,…,6}=10人数和事数不等的指派问题4指派问题

B’中有4个独立零元素，所以为最优解，最大产值为z=10＋6＋1＋5=22。

若人数小于事数，添一些虚拟的“人”，此时这些虚拟的“人”做各件事的费用系数取为0，理解为这些费用实际上不会发生；若人数大于事数，添一些虚拟的“事”，此时这些虚拟的“事”被各个人做的费用系数同样也取为0。【例7】

现有4个人，5件工作，每人做每件工作所耗时间如下表：4指派问题

工作B1B2B3B4B5工人A11011428A2711101412A35691214A4131511107问指派哪个人去完成哪项工作，可使总耗时最小？

解：添加虚拟人A5，构造耗时矩阵C，

应用匈牙利法求解，得到最优解X，

最少耗时为z=2＋7＋6＋7=22。一个人可做几件事的指派问题4指派问题

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

对例13中的指派问题，为了保证工程质量，经研究决定，舍弃建筑公司A4和A5，让技术力量较强的建筑公司A1,A2,A3来承建5家商店，其

投标费用见右表。根据实

际情况，允许每家建筑公

司承建一家或两家商店，

求使总费用最少的指派方

案。商店B1B2B3B4B5建公A14871512A279171410A3691287

解：由于每家建筑公

司最多可承建两家新商店，因此，把每家建筑公司化作Ai’和Ai’’(i=1,2,3)相同的两家建筑公司因而费用矩阵变为：4指派问题

上面的系数矩阵有6行5列，为了使“人”和“事”的数目相同，引入一件虚拟“事”，使之成为标

准的指派问题，其效率矩