运筹学__指派问题

在实际中经常会遇到这样的问题，有n项不同的任务，需要n个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题:应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。例7：有一份中文说明书，要分别译成英、日、德、俄四种文字，分别记作E、J、G、R,交与甲、乙、丙、丁四个人去完成.因个人专长不同，他们完成翻译不同语种的说明书所需的时间(h)如表所示.应如何指派，使四个人分别完成这四项任务总时间为最小？任务人员EJGR甲215134乙1041415丙9141613丁78119一、指派问题的数学模型（一）举例这是一个标准型的指派问题类似有：有n项加工任务，怎样指派到n台机床上分别完成；有n条航线，怎样指定n艘船分别去航行…..等。对应每个指派问题，需有类似上表那样的数表，表中数据称为效率矩阵或系数矩阵，其元素cij0(i,j=1,2,…n)，表示指派第i人去完成第j项任务时的效率（或时间、成本等）效率矩阵或系数矩阵C=(cij)n×n=c11c12…c1nc21c22…c2n………………cn1cn1…cnnC=(cij)４×４=2151341041415914161378119则该指派问题的数学模型为：11121314434441412151341191141140114min(,,)..(,,)(,,)ijjijiijzxxxxxxxistxjxij或，求解题时通常需引入0-1变量：∑xij=1(i=1,2,3,4)表示第i人只能完成一项任务xij=1(j=1,2,3,4)表示第j项任务只能由一人去完成。满足约束条件的解称为可行解，可写成矩阵形式，叫作解矩阵。)4,,1j;4,,1i(ji,0ji,1xij项任务个人去完成第不分配第项任务个人去完成第分配第1000000101000010xij如本例的一个可行解矩阵（但不一定是最优解）指派问题的解矩阵应具有如下特点：（1）解矩阵(xij)中各行各列的元素之和都是1；（2）可行解（最优解）中恰含有４个非零元，即4个1；（3）可行解（最优解）矩阵中的1恰取于不同行不同列。人工作甲乙丙丁人数译成英文210971译成日文1541481译成德文131416111译成俄文4151391任务1111可以看到指派问题既是0-1规划问题，也是运输问题，所以也可用整数规划，0-1规划，或运输问题的解法去求解。（二）指派问题的数学模型1.指派问题的一般提法：设m个人被指派去做m件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j件工作的的效率（时间或费用）为cij(i=1.2…m;j=1.2…m)，并假设cij≥0。问应如何指派才能使总效率最高或总时间﹑总费用最低？设[cij]表示指派问题的效率矩阵，令)m,,1j;n,,1i(ji,0ji,1xij项任务个人去完成第不分配第项任务个人去完成第分配第则指派问题的数学模型一般形式为：)m,,1jn,,1i(10x)m,,1j(1x)n,,1i(1x.t.sxczmax)(minijn1iijm1jijm1im1jijij；或或xij为第i个人指派去做第j项任务；cij为第i个人为完成第j项任务时的工时消耗，或称效率；{cij}nm为效率矩阵2.指派问题数学模型—一般形式如果一个指派模型满足以下三个条件：1)目标要求为min2)效率矩阵(cij)为m阶方阵3)效率矩阵中所有元素cij≥0,且为常数则称上面的数学模型为指派问题的标准形.3.指派问题数学模型—标准形式4.指派模型的标准形的特点:含有m×m个决策变量,均为0-1变量m+m＝2m个约束方程给定一个指派问题时，必须给出效率矩阵（系数矩阵）C=(cij)mxm,且cij0，因此必有最优解。m1im1jijij0xcMinZ指派问题有2m个约束条件，但可行解（即解矩阵）中有且只有m个是非零值，即m个值取为１，其余取为０,是自然高度退化的。指派问题是0-1规划的特例，也是运输问题的特例，所以可用整数规划，0-1规划或运输问题的解法去求解，但这就如同用单纯形法去求解运输问题一样，是不合算的。根据指派问题的特点可以有更简便的解法，就是匈牙利算法，其重要依据是：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。二匈牙利算法思路算法原理算法步骤匈牙利法基于这样一个明显的事实：如果在m阶效率矩阵中，所有元素cij≥0，而其中有m个位于不同行不同列的一组0元素，则在解矩阵中，只要令对应于这些0元素位置的xij＝1，其余的xij＝0，就得到最优解。此时的最优解为０（一）思路0141208302323020939140令x11=1，x23=1，x32=1，x44=1，即可得最优解，其解矩阵为•如效率矩阵为•恰有4个不同行不同列的0系数1000001001000001问题是如何找到位于不同行、不同列的m个0元素？minZ=Z＊＝0匈牙利算法基本思想：对同一工作i来说，所有人的效率都提高或降低同一常数，不会影响最优分配；同样，对同一人j来说,做所有工作的效率都提高或降低同一常数，也不会影响最优分配。匈牙利数学家狄·康尼格(D·Konig)证明的两个定理（二）算法的基本原理定理1如果从指派问题效率矩阵[cij]的每一行元素中分别减去(或加上)一个常数ui(被称为该行的位势)，从每一列分别减去(或加上)一个常数vj(称为该列的位势)，得到一个新的效率矩阵[bij]，若其中bij=cij-ui-vj，则[bij]的最优解的结构等价于[cij]的最优解的结构.证明：将从[bij]中得到的解代入分配问题模型的目标函数式，有m1jjm1im1iim1jijijm1iijm1jjm1im1jijm1iim1jijijm1im1jijjiijm1im1jijijvuxcxvxuxcx)vuc(xbz指派问题最优解的性质：若从效率矩阵(cij)的一行（列）各元素中分别减去该行（列）的最小元素得到的新矩阵(bij)，那么以(bij)为效率矩阵求得的最优解的结构和用原来的效率矩阵(cij)求得的最优解的结构相同。---匈牙利算法基本思想1利用这个性质，可使原系数矩阵变换为含有很多0元素的新系数矩阵，而最优解保持不变，在系数矩阵(bij)中，把位于不同行不同列的0元素，简称为独立的0元素。问题是：能否找到位于不同行、不同列的m个0元素？若能在系数矩阵(bij)中找出m个独立的0元素；则令解矩阵(xij)中对应这m个独立的0元素的xij取值为1，其他元素取值为0。将其代入目标函数中得到zb=0，它一定是最小值。这就是以(bij)为系数矩阵的指派问题的最优解。从而也就得到了原问题的最优解。库恩（W.W.Kuhn）于1955年给出了指派问题的解法，他引用匈牙利数学家狄·康尼格（d.konig)关于矩阵中独立零元素的定理(即定理2)：系数矩阵中独立的“0”元素的最多个数等于覆盖所有“0”元素的最少直线数---匈牙利算法基本思想2库恩给出的指派问题的解法称为匈牙利算法定理2若效率矩阵C的元素可分成“0”与非“0”两部分，则覆盖所有“0”元素的最少直线数=独立的“0”元素的最多个数证明：已知矩阵中有若干0元素，设覆盖全部0元素最少需m条直线，又设位于不同行不同列的0有M个.•因覆盖M中的每个0至少用一条直线，故有mM•下面要证明Mm.i1i2irj1j2jc如图假定覆盖所有0元素的m条直线有r行、c列，m=r+c.所有r行上不在j1，…，jc列上的0元素个数≥r，这些0元素至少有r个位于不同列同理：所有c列上不在i1，…，ir行上的0元素个数≥c，且这些0元素至少有c个位于不同若上述两部分0个数总和为S，则S≥m；其中有m个，又它们必无重复元素，彼此独立，则SM,故有m≤M，故可得M=m.定理2说明：1.只要表中含有不同行或不同列的“0”元素，都可以通过直线覆盖的方式来找到它们2.当覆盖直线的最少条数达到m条时，必恰有m个独立“0”元素存在于表中推论1：覆盖所有“0”元素的直线数≥不同行不同列的“0”元素的最多个数（m）推论2：覆盖所有“0”元素的最少直线数≥不同行不同列的“0”元素的个数覆盖所有“0”元素的最少直线数=独立的“0”元素的最多个数2.系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。1.若从效率矩阵(cij)的一行（列）各元素中分别减去该行（列）的最小元素得到的新矩阵(bij)，那么以(bij)为效率矩阵求得的最优解的结构和用原来的效率矩阵(cij)求得的最优解的结构相同。匈牙利算法依据：(三)匈牙利算法的步骤任务人员EJGR甲215134乙1041415丙9141613丁78119例7:第一步：变换系数矩阵,使指派问题的系数矩阵经变换，在各行各列中都出现0元素：从系数矩阵的每行元素减去该行的最小元素。再从所得系数矩阵的每列元素减去该列的最小元素。若某行已经有0元素，就不必再减了。(cij)=21513410414159141613781192497013112601011057401424201370606905320100第二步：圈出不同行且不同列的０元素，进行试指派，以寻找最优解。经第一步变换后，系数矩阵中每行每列都已有了0元素但需找出m个独立的0元素。若能找出，就以这些独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。当m较小时，可用观察法、试探法去找出m个独立0元素。若m较大时，就必须按一定的步骤去找，常用的步骤为:从只有一个0元素的行（或列）开始，给这个0元素加圈，记，这表示对这行所代表的人，只有一种任务可指派。然后划去所在的列（或行）的其他0元素，记作Ø。这表示这列所代表的任务已指派完，不必再考虑别人013706695320100给只有一个0元素的列（或行）中的0元素加圈，记，然后划去所在的行（或列）的其他0元素，记作Ø。这表示这行所代表的人已指派完，不必再考虑他做别的任务了。反复进行上述两步，直到所有的0元素都被圈出和划掉为止。0137066905320100从只有一个0元素的行（或列）开始，给这个0元素加圈，记。再给第三行的这个唯一的0元素加圈，记，得013706695320100然后划去所在的列的其他0元素，记作Ø，得Ø1370669532Ø100给只有一个0元素的列的0元素加圈，记，得Ø1370669532Ø10然后划去所在的行的其他0元素，记作Ø，得Ø1370669532Ø1Ø给最后一个0元素加圈，记，得Ø137669532Ø1Ø0001010010000010可得独立的0元素的个数就是矩阵的阶数,即n=m=4,故得到最优解：即甲译俄文、乙译日文、丙译英文、丁译德文所需时间最少。Z=28小时若不同行不同列的元素的数目n等于系数矩阵阶数m,则令它们对应的xij＝１，其余xij=0,那么这分配问题的最优解已得到,计算停．若nm，说明尚未找到最优解，则转下一步。即设法进一步变换矩阵，增加新的０元素.步骤目标效率矩阵的变换：使表中有足够多的0行变换各行都有0生成的0对应的工时最小列变换各列都有0生成的0对应的工时最小检查矩阵：确定是否有m个独立0＝覆盖直线数列检查只有一个0，则标出以示该任务以优势方案派出并将该行划掉以示该人以优势方案安排如有多个0，则暂不标记该任务可派给多个人，哪个最优未定覆盖线数不能达到“最小”行检查只有一个0，则标出以示该人以优势方案安排并将该列划掉以示该任务以优势方案派