指派问题运筹4-27.ppt

《指派问题运筹4-27.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、指派问题在实际中经常会遇到这样的问题，有n项不同的任务，需要n个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题:应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。例7：有一份中文说明书，要分别译成英、日、德、俄四种文字，分别记作E、J、G、R,交与甲、乙、丙、丁四个人去完成.因个人专长不同，他们完成翻译不同语种的说明书所需的时间(h)如表所示.应如何指派，使四个人分别完成这四项任务总时间为最小？任务人员EJGR甲215134乙1041415丙9141

2、613丁78119一、指派问题的数学模型（一）举例这是一个标准型的指派问题类似有：有n项加工任务，怎样指派到n台机床上分别完成；有n条航线，怎样指定n艘船分别去航行…..等。对应每个指派问题，需有类似上表那样的数表，表中数据称为效率矩阵或系数矩阵，其元素cij>0(i,j=1,2,…n)，表示指派第i人去完成第j项任务时的效率（或时间、成本等）效率矩阵或系数矩阵C=(cij)n×n=c11c12…c1nc21c22…c2n………………cn1cn1…cnnC=(cij)４×４=2151341041415914161378119则该指派问题的数学模型为：求解题时通常需引入0-1变量：∑xij=1(

3、i=1,2,3,4)表示第i人只能完成一项任务xij=1(j=1,2,3,4)表示第j项任务只能由一人去完成。满足约束条件的解称为可行解，可写成矩阵形式，叫作解矩阵。如本例的一个可行解矩阵（但不一定是最优解）指派问题的解矩阵应具有如下特点：（1）解矩阵(xij)中各行各列的元素之和都是1；（2）可行解（最优解）中恰含有４个非零元，即4个1；（3）可行解（最优解）矩阵中的1恰取于不同行不同列。可以看到指派问题既是0-1规划问题，也是运输问题，所以也可用整数规划，0-1规划，或运输问题的解法去求解。（二）指派问题的数学模型1.指派问题的一般提法：设m个人被指派去做m件工作，规定每个人只做一件工作，

4、每件工作只有一个人去做。已知第i个人去做第j件工作的的效率（时间或费用）为cij(i=1.2…m;j=1.2…m)，并假设cij≥0。问应如何指派才能使总效率最高或总时间﹑总费用最低？设[cij]表示指派问题的效率矩阵，令则指派问题的数学模型一般形式为：xij为第i个人指派去做第j项任务；cij为第i个人为完成第j项任务时的工时消耗，或称效率；{cij}nm为效率矩阵2.指派问题数学模型—一般形式如果一个指派模型满足以下三个条件：1)目标要求为min2)效率矩阵(cij)为m阶方阵3)效率矩阵中所有元素cij≥0,且为常数则称上面的数学模型为指派问题的标准形.3.指派问题数学模型—标准形式4

5、.指派模型的标准形的特点:含有m×m个决策变量,均为0-1变量m+m＝2m个约束方程给定一个指派问题时，必须给出效率矩阵（系数矩阵）C=(cij)mxm,且cij0，因此必有最优解。指派问题有2m个约束条件，但可行解（即解矩阵）中有且只有m个是非零值，即m个值取为１，其余取为０,是自然高度退化的。指派问题是0-1规划的特例，也是运输问题的特例，所以可用整数规划，0-1规划或运输问题的解法去求解，但这就如同用单纯形法去求解运输问题一样，是不合算的。根据指派问题的特点可以有更简便的解法，就是匈牙利算法，其重要依据是：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。二匈牙利算法思路

6、算法原理算法步骤匈牙利法基于这样一个明显的事实：如果在m阶效率矩阵中，所有元素cij≥0，而其中有m个位于不同行不同列的一组0元素，则在解矩阵中，只要令对应于这些0元素位置的xij＝1，其余的xij＝0，就得到最优解。此时的最优解为０（一）思路令x11=1，x23=1，x32=1，x44=1，即可得最优解，其解矩阵为如效率矩阵为恰有4个不同行不同列的0系数问题是如何找到位于不同行、不同列的m个0元素？minZ=Z＊＝0匈牙利算法基本思想：对同一工作i来说，所有人的效率都提高或降低同一常数，不会影响最优分配；同样，对同一人j来说,做所有工作的效率都提高或降低同一常数，也不会影响最优分配。匈牙利数

7、学家狄·康尼格(D·Konig)证明的两个定理（二）算法的基本原理定理1如果从指派问题效率矩阵[cij]的每一行元素中分别减去(或加上)一个常数ui(被称为该行的位势)，从每一列分别减去(或加上)一个常数vj(称为该列的位势)，得到一个新的效率矩阵[bij]，若其中bij=cij-ui-vj，则[bij]的最优解的结构等价于[cij]的最优解的结构.证明：将从[bij]中得到的解代入分配问题模型的