(7.3.1)--指派问题及其求解（NO20）.pdf

1 运运 筹筹 学学 第二十讲第二十讲 指派问题及其解法指派问题及其解法 2 指派问题及其解法指派问题及其解法 在生活中经常遇到这样的问题，有在生活中经常遇到这样的问题，有n项任务需项任务需要完成，正好有要完成，正好有n个人可承担这些任务。由于每个个人可承担这些任务。由于每个人的专长与经验不同，各人完成任务所需的时间人的专长与经验不同，各人完成任务所需的时间不同，效率也不同。那么则产生应派哪个人去完不同，效率也不同。那么则产生应派哪个人去完成哪项任务的问题，才能够使完成项任务的总效成哪项任务的问题，才能够使完成项任务的总效率最高（所需总时间最少）。这类问题就是指派率最高（所需总时间最少）。这类问题就是指派问题问题.3 例题例题1 1：假设有假设有4 4个人去完成个人去完成4 4项任务，每个人由于技术、项任务，每个人由于技术、专长不同，完成任务的时间如下表，且规定每人只能做专长不同，完成任务的时间如下表，且规定每人只能做一项工作，每项工作只能由一人完成，问应如何分配任一项工作，每项工作只能由一人完成，问应如何分配任务使总费用最小？务使总费用最小？任务 人员 E J G R 甲 3 14 10 5 乙 10 4 12 10 丙 9 14 15 13 丁 7 8 11 9 解：设Xij表示第i人从事第j项工作，且 01jiX因此，该问题的数学模型为当指派第i人去完成第j项工作 否则 目标总费用最小 ninjijijXCMinZ110约束条件为 111213142122322431323334414243441111xxxxxxxxxxxxxxxx4 MinZ=3X11+14X12+10X13+5X14+10X21+4X22+12X23+10X24 +9X31+14X32+15X33+13X34+7X41+8X42+11X43+9X44 111144342414433323134232221241312111XXXXXXXXXXXXXXXX表示第j项工作只指派1人完成 111144434241343332312423222114131211XXXXXXXXXXXXXXXX表示第i人被指派完成一项工作 Xij=0或1(i,j=1,2,3,4)该指派问题的数学模型为：5 诸如此类，有n项任务，恰好有n个人可承担这些任务，但由于每人的技术专长不同，完成任务的效率(所费时间不同，为使完成n项任务的总效率最高（即所需总时间最少），应如何指派（分派）人员的问题统称为指派（分派）问题。一、指派问题的数学模型及其特点一、指派问题的数学模型及其特点 1.1.数学模型：数学模型：ninjijijijCXCMinZ11)0(),.,2,1(10),.,2,1(1),.,2,1(111nijXniXnjXijnjijniij或6 2 2.特点特点 （1）给定一个指派问题时，必须给出效率矩阵（系数矩 阵）C=(Cij)nxn,且 Cij0，因 此 必 有 最 优 解()。ninjijijXCMinZ110（2）指派问题是一种特殊的平衡运输问题，由于模型结构的特殊性（看作每个产地的产量均为1，每个销地的销量均为1），故可用更为简便的匈牙利算法进行求解。（3 3）若从效率矩阵若从效率矩阵(C(Cijij)nxnnxn的一行的一行（列列）各元素中分别减各元素中分别减去该行去该行（列列）的最小元素的最小元素，得到的新效率矩阵得到的新效率矩阵(b(bijij)nxnnxn不改不改变原指派问题的最优解变原指派问题的最优解。这条性质可用如下语言来解释这条性质可用如下语言来解释 7 则新的目标函数为ninjijijXbZ11ninjijjiijXdtC11)(ninjninjniijjnjijiijijXdXtXC111111)()()(11ninjjidtZ其中ninjjidt11为常数对同一项工作（任务）j来说，同时提高或降低每人相同的效率（常数ti），不影响其最优指派；同样，对同一个人i来说，完成各项工作的效率都提高或降低相同的效率（常数dj），也不影响其最优指派。将效率矩阵C=(Cij)nn变换后，得到新的效率矩阵(bij)nxn，其中 bij=Cij+ti+dj （对所有的i,j）这说明这说明Z Z 与与Z Z同时达到最小值。同时达到最小值。因而最优解相同。因而最优解相同。8 匈牙利法是求解指派问题的一种好算法，它只能求解目标函数为最小化的情况，它由匈牙利数学家柯尼格（D.Konig)提出，因此而得名。二、指派问题的解法二、指派问题的解法匈牙利法匈牙利法 1 1、匈牙利法的基本思想、匈牙利法的基本思想 匈牙利法主要基于指派问题的第（匈牙利法主要基于指派问题的第（3 3）个特点。即从效）个特点。即从效率矩阵的每行或每列减去一个常数，指派问题的最优解不率矩阵的每行或每列减去一个常数，指派问题的最优解不变。由此，我们可以让每行或每列减去一个数后，出现变。由此，我们可以让每行或每列减去一个数后，出现0 0元元素，然后，再给费用为素，然后，再给费用为0 0元素的相应变量指派为元素的相应变量指派为1 1，以使变，以使变换后的目标函数为换后的目标函数为0 0，从而达到最优。，从而达到最优。9 2.2.匈牙利法的计算步骤匈牙利法的计算步骤 第一步：第一步：变换指派问题的系数矩阵，使在各行各列中都出变换指派问题的系数矩阵，使在各行各列中都出现现0 0元素。元素。(1)(1)从系数矩阵的每行元素中减去该行的最小元素；从系数矩阵的每行元素中减去该行的最小元素；(2)(2)再从所得系数矩阵的每列元素中减去该列的最小元素，再从所得系数矩阵的每列元素中减去该列的最小元素，若某行（列）已有若某行（列）已有0 0元素，则不需再减了；元素，则不需再减了；第二步：第二步：进行试指派，以寻求最优解。按以下步骤进行。进行试指派，以寻求最优解。按以下步骤进行。经第一步变换后，系数矩阵中每行每列中都已有经第一步变换后，系数矩阵中每行每列中都已有0元素，但元素，但需要找出需要找出n个独立的个独立的0元素。如能找出，就以这些独立的元素。如能找出，就以这些独立的0元元素对应解矩阵（素对应解矩阵（xij）中的元素为）中的元素为1，其余为，其余为0，这就得到最，这就得到最优解。具体步骤为：优解。具体步骤为：10 从只有一个从只有一个0 0元素的行（列）开始，给这个元素的行（列）开始，给这个0 0元素加圈，元素加圈，记作。然后划去所在列（行）的其它记作。然后划去所在列（行）的其它0 0元素，记作元素，记作 给只有一个给只有一个0 0元素列（行）的元素列（行）的0 0元素加圈，记作；然后元素加圈，记作；然后划去所在行的划去所在行的0 0元素，记作元素，记作。反复进行、步骤，直到所有反复进行、步骤，直到所有0 0元素都被圈出和划掉元素都被圈出和划掉为止。为止。若仍有没有划圈的若仍有没有划圈的0 0元素，且同行（列）的元素，且同行（列）的0 0元素至少有元素至少有两个（表示对这人可以从两项任务中指派其一），则从剩两个（表示对这人可以从两项任务中指派其一），则从剩有有0 0元素最少的行（列）开始，比较这行各元素最少的行（列）开始，比较这行各0 0元素所在列中元素所在列中0 0元素的数目，选择元素的数目，选择0 0元素少的那列的这个元素少的那列的这个0 0元素加圈（表示元素加圈（表示选择性多的应该先满足选择性少的），然后划掉同行同列选择性多的应该先满足选择性少的），然后划掉同行同列的其它的其它0 0元素。可反复进行，直到所有元素。可反复进行，直到所有0 0元素都已划圈或划元素都已划圈或划掉为止。掉为止。若元素的数目若元素的数目m等于矩阵的阶数等于矩阵的阶数n，那么这指派问题的，那么这指派问题的最优解已得到；若最优解已得到；若mn，则转入下一步。，则转入下一步。11 第三步：第三步：作最少的直线覆盖所有作最少的直线覆盖所有0 0元素，以确定该系数矩元素，以确定该系数矩阵中能找到最多的独立阵中能找到最多的独立0 0元素。为此按以下步骤进行：元素。为此按以下步骤进行：对没有的行打对没有的行打；对已打对已打的行中所有含的行中所有含0 0元素的列打元素的列打；再对打有再对打有的列中含有元素的行打的列中含有元素的行打；重复、直到得不出新的打重复、直到得不出新的打的行、列为止；的行、列为止；对没有打对没有打的行画一横线，有打的行画一横线，有打的列画一纵线，这就的列画一纵线，这就得到覆盖所有得到覆盖所有0 0元素的最少直线数。元素的最少直线数。12 例题例题2:2:用匈牙利法求解费用矩阵如下的指派问题用匈牙利法求解费用矩阵如下的指派问题.9118713151491012410510143ijC00102250440603110所以，该问题的最优解为X14=1，X22=1，X31=1，X34=1，其余为0.该问题的最优值 minZ=5+4+9+11=29 011726086056401422636040089575100000322020513 例题例题3:3:用匈牙利法求解费用矩阵如下的指派问题用匈牙利法求解费用矩阵如下的指派问题.61071041066141512141217766698979712ijC04140400811353800003420207 个数个数只有只有4 4个，个，小于小于n=5n=5，进入调整进入调整 26360400895751000003220205最小费用最小费用为为minz=7+6+minz=7+6+7+6+6=327+6+6=32 1723211919161726182223192421181514 练习：练习：某公司要把四个有关能源工程项目承包给四个互不某公司要把四个有关能源工程项目承包给四个互不相关的外商投标者，规定每个承包商只能且必须承包一个相关的外商投标者，规定每个承包商只能且必须承包一个项目，求在总费用最小的条件下确定各个项目的承包者，项目，求在总费用最小的条件下确定各个项目的承包者，总费用为多少？各承包商对工程的报价如表所示。总费用为多少？各承包商对工程的报价如表所示。人 任务 I II III IV 甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁 19 21 23 17 解：解：0642301100451963015 解：解：17232119191617261822231924211815 06423011004519630 0632300100441962016 对于求最大化的指派问题（即求 ）,可采 用构造新的效率矩阵(MCij)nxn，其中M=maxCij，（显 然MCij0），将其转化为 ninjijijXCMaxZ11ninjijijXCMZMin11)(则所得到的最优解就是原问题的最优解。事实上 由于nM为常数，因此，使Z取得最小的最优解就是使Z取得最大的最优解。ijninjijninjijninjijijXCXMXCMZ111111)(ZnMXCnMijninjij11三、关于求最大化的指派问题三、关于求最大化的指派问题 17 例题例题4 4 某工厂有某工厂有4 4个工人个工人A1,A2,A3,A4,A1,A2,A3,A4,分别均能操作分别均能操作B1,B2,B3,B4B1,B2,B3,B4四台车床中一台四台车床中一台,每小时的产值如下表所示每小时的产值如下表所示,求求产值最大的分配方案产值最大的分配方案.B1 B2 B3 B4 A1 10 9 8 7 A2 3 4 5 6 A3 2 1 1 2 A4 4 3 5 6 解解:0022000000133100457689984567321065342112654378910ijC18 以上讨论的指派问题是效率矩阵的行数等于列数，即m+n的情况。当mn时，则可用增加虚设的零元数行（列）使效率矩阵变成方阵后，再用匈牙利法求解。n-m行 000000,2111211mnmmnCCCCCC当mn时 四、非平衡的指派问题四、非平衡的指派问题 19 例题例题5 5 某企业集团计划在市内四个点投资四个专业超市，某企业集团计划在市内四个点投资四个专业超市，考虑的商品有家电、服装、食品、家具和计算机考虑的商品有家电、服装、食品、家具和计算机5 5个类别。个类别。通过评估，家具超市不能放在第三个点，计算机超市不能通过评估，家具超市不能放在第三个点，计算机超市不能放在第四个点，不同类别的商品投资到各点的年利润（万放在第四个点，不同类别的商品投资到各点的年利润（万元）预测值见下表。该商业集团如何做出投资决策可使年元）预测值见下表。该商业集团如何做出投资决策可使年利润最大？利润最大？0420150160200024042022033001204026027001600703400206012030020 解：解：这是求最大值、人数与任务数不相等的一个综合指派这是求最大值、人数与任务数不相等的一个综合指派问题，分别对上表进行转换。问题，分别对上表进行转换。0400150900022042015013001004019017001400014000605010021 04201501602000240420220330012040260270016007034002060120300 04001509000220420150130010040190170014000140006050100 40400150900018038011090060015013040140001404006050100 0000110000001000001001000最优最优方案方案 22 整数规划问题的整数规划问题的EXCELEXCEL求解求解 一、整数规划的一、整数规划的EXCELEXCEL求解求解 例题例题6 6 用EXCEL求解下列整数规划问题的最优解 1231232312312313max3324432.323,0,Zxxxxxxxxstxxxx x xx x并且为整数23 最优方案最优方案 24 二、二、0 0-1 1规划的规划的EXCELEXCEL求解求解 例题例题7 7 用EXCEL求解下列0-1规划的最优解 1231231231223123max3252244.346,01Zxxxxxxxxxstxxxxx xx或25 最优方案最优方案 26 三、指派问题的三、指派问题的EXCELEXCEL求解求解 例题例题8 8 下表给出了每位工人执行各项任务所需的工时，用EXCEL求解下列指派问题的最优指派方案，使总的工时量最小。人员 任务 A B C D E 甲 12 7 9 7 9 乙 8 9 6 6 6 丙 7 17 12 14 9 丁 15 14 6 6 10 戊 4 10 7 10 9 解：指派问题是运输问题的一个特例，因此我们可以把指解：指派问题是运输问题的一个特例，因此我们可以把指派问题看成是供应量和需求量都等于派问题看成是供应量和需求量都等于1 1的产销平衡运输问的产销平衡运输问题，同时注意变量的取值是题，同时注意变量的取值是0 0或者或者1 1，那么就可以利用，那么就可以利用EXCELEXCEL直接求解了。直接求解了。27 最优表最优表 A B C D E 科学家1 100 400 200 200 100 科学家2 0 200 800 0 0 科学家3 100 100 100 100 600 科学家4 133 33 34 800 28 综合案例：综合案例：下表给出了一个项目投标问题。有4位科学家对5个项目进行投标，每位科学家有1000点可以投向他感兴趣的项目，具体投标情况如下表所示。其中“-”表示某科学家由于没有某项技能而不能从事某项目，科学家1和科学家3由于能力较强，可以承担1至2个项目的工作。问应该如何指派可以使总投标点最高？科学家项目投标情况科学家项目投标情况 29 投标问题的最优解投标问题的最优解 30 敬请指教！谢谢！