指派问题的算法分析与实现.doc

《指派问题的算法分析与实现.doc》由会员分享，可在线阅读，更多相关《指派问题的算法分析与实现.doc（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date指派问题的算法分析与实现编号： 33 编号： 20 运 筹 学 基 础课 程 设 计题 目：指派问题的算法分析与实现院 系： 专 业： 姓名学号： 指导教师： 日 期： 2011 年 1 月 15 日摘 要在企业、公司的运营与管理中，管理者总是希望把人员最佳分派以发挥其最大工作效率，从而降低成本、提高效益。然而，如果没有科学的方法是很难实现优化管理的，由此我们引入了指

2、派问题。指派问题多是求项目的工时最少，而很多情况下人们并不关心项目总工时的多少，而只关心项目能否在最短的时间内完成，即历时最少的指派问题。这类问题研究的是n个人执行n项任务，执行每项任务的人数以及总的指派人项数均有限制，要求最优指派。在运筹学中求解整数规划的指派问题通常是通过匈牙利算法来求解，但指派问题也可以归结为一个0-1整数规划问题，本文先对指派问题进行陈述，引出对实际问题的求解。在指派问题的背景、描述中充分理解该问题，先运用匈牙利算法实现指派问题，然后再建立一个0-1整数规划模型，并运用matlab和lingo编译程序对问题进行编译，运用软件解决模型问题，最终实现指派问题在实际问题中的运

3、用。通过运用匈牙利算法和0-1整数规划同时对指派问题求解，我们发现用0-1整数规划的方法来求解可以更简单，也更方便程序的阅读和理解。与此同时，我们还对0-1整数规划问题由整数数据深入研究到小数数据。最后通过实例来说明运用matlab，lingo编译程序来解决整数规划问题的简便和有效性。关键词：指派问题；匈牙利算法；0-1整数规划；matlab模型；lingo模型AbstractIn business, the companys operations and management, managers always want the best distribution of the staff t

4、o maximize their efficiency, reduce costs and improve efficiency. However, if there is no scientific method is difficult to achieve optimal management, which we introduced the assignment problem. Multi-assignment problem is to get the project working hours at least, and in many cases people do not c

5、are about how much the total project work, but only care about whether the project can be completed within the shortest possible time, that lasted for at least the assignment problem. Such problems is the n individual execution of tasks n, the number of people to perform each task and assign the tot

6、al number of items are restricted to two people, requiring the optimal assignment. Integer programming in operations research for solving the assignment problem is usually solved by Hungarian algorithm, but the assignment problem can be reduced to a 0-1 integer programming problem, this paper first

7、to make a statement on the assignment problem, leads to the solution of practical problems. Assignment problem in the background to fully understand the problem description, the first assignment problem using Hungarian algorithm, and then a 0-1 integer programming model and compiler using matlab and

8、 the lingo of the problem to be compiled using the software solution model problem Ultimately in the assignment of the application in practical problems. By using the Hungarian algorithm and the 0-1 integer programming to solve assignment problems simultaneously, we found that 0-1 integer programmin

9、g method to solve a more simple and easier to read and understand the program. At the same time, we also 0-1 integer programming problem in-depth study by the integer data to a decimal data. Finally, an example to illustrate the use of matlab, lingo compiler to solve the integer programming problem

10、is simple and effective.Keywords: assignment problem; Hungarian algorithm; 0-1 integer programming; matlab model; lingo model目录1. 问题陈述12. 指派问题的背景13. 指派问题的描述13.1 指派问题的一般形式13.2 问题的数学模型一般形式23.3 目标函数极大化的指派问题24指派问题实现34.1 匈牙利算法34.1.1 匈牙利算法的理论基础34.1.2 匈牙利算法的实现步骤34.1.3 匈牙利算法实现指派问题44.2 0-1整数规划54.2.1 模型假设54.2

11、.2 模型建立64.2.3 模型求解75. 问题的深入（0-1整数规划）105.1 模型建立105.2 模型求解115.2.1 用matlab求解问题115.2.2 用lingo求解问题126. 结论146.1 总结概论146.2 具体分工146.3 个人感言147. 参考文献17- 1. 问题陈述指派问题又称分配问题，其用途非常广泛，比如某公司指派n个人去做n件事，各人做不同的事，如何安排人员使得总费用最少？若考虑每个职工对工作效率（如熟练程度等），怎样安排会使总销量达到最大？这些都是一个企业经营管理者必须考虑的问题，所以该问题有重要的应用价值。假设有n件工作分派给n个人来做，每项工作只能由

12、一人来做，每个人只能做一项工作。若给出各人对各项工作所具有的工作效率。问应该如何安排人选，及发挥个人特长又能使总的效率最大。为此用0-1整数规划来实现指派问题即如何安排人选。2. 指派问题的背景在现实生活中，有各种性质的指派问题（Assignment Problem）。例如，在生产管理中，总希望把人员进行最佳分配，以发挥最大的工作效率；某部门有n项任务要完成，而该部门正好有n个人可以分别去完成其中任何一项，但由于任务性质和个人的专长不同，因此各人完成各项不同任务的效益（所费时间或所花费用）也有差别，如果分配每个人完成一项任务且仅为一项任务，则把每项任务分配给哪个人去完成，使完成所有n项任务的总

13、效益为最高（总时间、总费用为最小或创造的价值最大）？这是典型的分配问题或指派问题。又如有n项加工任务，怎样指定n台机器分别去完成，以使总的加工时间最少或总收入最大；有n条航线，怎样指定n艘船分别航行，使总收入最大，等等，都属于指派问题。3. 指派问题的描述3.1 指派问题的一般形式指派问题的标准形式（以人和事为例）如下。有n个人和n项任务，已知第i个人做第j件事的费用为，要求确定人和事之间的一一对应的指派方案，使完成这n项任务的费用最少。一般把目标函数的系数写为矩阵形式，称矩阵为系数矩阵（Coefficient Matrix），也称为效益矩阵或价值矩阵。矩阵的元素（i,j=1,2,n）表示分配

14、第i个人去完成第j项任务时的效益。一般地，以表示给定的资源分配用于给定活动时的有关效益（时间，费用，价值等），且3.2 问题的数学模型一般形式在模型中，约束条件式（2）表示每个人只能做一件事，约束条件式（3）表示每件事只能由一个人去做。对于问题的每个可行解，可用解矩阵来表示：当然，作为可行解，矩阵的每列元素中都有且只有一个1，以满足约束条件式（3）。每行元素中也有且只有一个1，以满足约束条件（2）。指派问题n!个可行解。3.3 目标函数极大化的指派问题求解时，我们将构造一个新的矩阵，使，其中是一个足够大的常数。一般取中最大的元素作为，求解，所得的解就是原问题的解。事实上，由可的此结论。4指派问

15、题实现4.1 匈牙利算法4.1.1 匈牙利算法的理论基础定理1 如果从分配问题的效率矩阵的每一行元素中分别减去（或加上）一个常数，从每一列中分别减去（或加上）一个常数，得到一个新的效率矩阵，则以为效率矩阵的分配问题与以为效率矩阵的分配问题具有相同的最优解。定理2 若矩阵A的元素可以分为0与非0的两部分，则覆盖0元素最少直线数等于位于不同行不同列的0元素的最大个数。4.1.2匈牙利算法的实现步骤第一步：找出矩阵每行的最小元素，分别从每行中减去这个最小元素；第二步：再找去矩阵每列的最小元素，分别从各列减去这个最小元素；第三步：经过这两步变换后，矩阵的每行每列至少都有了一个零元素，接着根据以下准则进

16、行试指派，找出覆盖上面矩阵中所有零元素至少需要多少条直线；（1）从第一行开始，若该行只有一个零元素打上（）号。对打（）号零元素所在列划一条直线。若该行没有零元素或有两个以上零元素（已划去的不计在内），则转下一行，一直到最后一行为止；（2）从第一列开始，若该列只有一个零元素就对这个零元素打上（）号（同样不考虑已划去的零元素），对打（）号零元素所在行划一条直线。若该列没有零元素或 还有两个以上零元素，则转下一列，并进行到最后一列；（3）重复（1）、（2）两个步骤，可能出现三种情况： 矩阵每行都有一个打（）号零元素，很显然，按照上述步骤得到的打（）的零元素都位于不同行不同列，因此就找到了问题的答案；

17、 有多于两行或两列存在两个以上零元素，即出现了零元素的闭回路，这个时候可顺着闭回路的走向，对每个间隔的零元素打上（）号，然后对所有打（）号零元素或所有列或所在行划一条直线。 矩阵中所有零元素或打上（）号，或被划去，但打（）号零元素个数小于m。第四步：为了设法使每行都有一个打（）的零元素，就要继续对矩阵进行变换；（1）从矩阵未被直线覆盖的元素找出最小元素k；（2）对矩阵的每行，当该行有直线覆盖时，令=0，无直线覆盖的，令=k；（3）对矩阵的每列，当该列有直线覆盖时，令=-k，无直线覆盖的，令=0；（4）得列一个变换后的矩阵，其中每个元素=-。第五步：回到第三步，反复进行，一直到矩阵中每一行都有一

18、个打（）的零元素为止，即找到最优分配方案为止。4.1.3 匈牙利算法实现指派问题为了便于对模型进行求解与分析，假设有4件事4个人去做，各变量对应的数据假设如表1。表1 每个人完成各项任务需要的时间人任务ABCD甲25293142乙39382620丙34272840丁24423623用匈牙利算法求解过程如下： Min -1 -1 -1 -4 -4 -1 -1所以最优解为x11，x23，x32，x44，即甲负责任务A，乙负责任务C，丙负责任务B，丁负责任务D，可以使总花费时间最少。代入求出目标函数值Z=25+26+27+23=101。4.2 0-1整数规划0-1规划（0-1 Programming

19、）一种特殊形式的整数规划 。这种规划的决策变量仅取值0或1，故称为0-1变量或二进制变量 ，因为一个非负整数都可以用二进制记 数法用若干个0-1变量表示 。0-1变量可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件 ，因此0-1规划非常适合描述和解决如线路设计 、工厂选址 、生产计划安排、旅行购物、背包问题、人员安排、代码选取、可靠性等人们所关心的多种问题。实际上，凡是有界变量的整数规划都可以转化为0-1规划来处理。当然也包括运筹学中的指派问题。4.2.1 模型假设为了便于对模型进行求解与分析，假设有4件事4个人去做，各变量对应的数据假设

20、如表1。表1 每个人完成各项任务需要的时间人任务ABCD甲25293142乙39382620丙34272840丁24423623表2 变量假设i第i个人j第j项任务第i个人分配第j项任务=1第i个人被分配去做第j项任务=0第i个人不被分配到第j项任务4.2.2 模型建立根据前面的假设，因此，每个人只完成一项任务的约束条件为：每项任务必有一个人负责的约束条件为： 由此，建立的数学模型为： s.t. 或1，i，j=1，2，3，44.2.3 模型求解 用matlab求解根据上面建立的模型，代入相应的数据，利用matlab软件编程求解，具体程序如下：function y,fval=minzp(C) %

21、y为最佳匹配矩阵，fval为目标函数值，C为目标函数系数矩阵C=C;f=C(:);m,n=size(C);Aeq=zeros(2*n,n*n); %生成2*n行n*n列的等式约束0系数矩阵for i=1:nAeq(1:n,1+(i-1)*n:i*n)=eye(n,n); %eye表示生成n阶单位阵endfor i=1:nAeq(n+i,1+(i-1)*n:i*n)=ones(1,n); %生成1行n列元素为1的向量endbeq=ones(2*n,1); %生成2*n行1列元素为1的等式约束右端项lb=zeros(n*n,1); %生成n*n行1列元素为0的不等式约束左端项ub=ones(n*n

22、,1); %生成n*n行1列元素为1的不等式约束右端项x=linprog(f,Aeq,beq,lb,ub); %求目标函数达到极小值的x值y=reshape(x,n,n); %将上式求出的x值组成的向量变成n阶矩阵y=y;y=round(y); %对y中的元素取整，生成匹配矩阵sol=zeros(n,n);for i=1:nfor j=1:nif y(i,j)=1sol(i,j)=C(j,i);endendendfval=sum(sol(:); %求出极小值的目标函数值其中， C=25 29 31 4239 38 26 2034 27 28 4024 42 36 23; y,fval=minz

23、p(C)输出结果为：Optimization terminated.y = 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1fval =101用lingo软件求解根据上面建立的模型，代入相应的数据，利用lingo软件编程求解，具体程序如下：model:sets:ren/1.4/;renwu/1.4/;Assign(ren,renwu):C,X; ！X为最佳匹配矩阵，C为目标函数系数endsetsdata:C=25 29 31 4239 38 26 2034 27 28 4024 42 36 23;enddatamin=sum(Assign:C*X);！求目标函数极小值FOR(re

24、n(i):sum(renwu(j):X(i,j)=1);！行和为1约束FOR(renwu(j):sum(ren(i):X(i,j)=1);！列和为1约束for(Assign:bin(x);！0-1约束End运行结果为：Global optimal solution found. Objective value: 101.0000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost C( 1, 1) 25.00000 0.000000 C( 1, 2) 29.00000 0.000000

25、C( 1, 3) 31.00000 0.000000 C( 1, 4) 42.00000 0.000000 C( 2, 1) 39.00000 0.000000 C( 2, 2) 38.00000 0.000000 C( 2, 3) 26.00000 0.000000 C( 2, 4) 20.00000 0.000000 C( 3, 1) 34.00000 0.000000 C( 3, 2) 27.00000 0.000000 C( 3, 3) 28.00000 0.000000 C( 3, 4) 40.00000 0.000000 C( 4, 1) 24.00000 0.000000 C(

26、4, 2) 42.00000 0.000000 C( 4, 3) 36.00000 0.000000 C( 4, 4) 23.00000 0.000000 X( 1, 1) 0.000000 25.00000 X( 1, 2) 1.000000 29.00000 X( 1, 3) 0.000000 31.00000 X( 1, 4) 0.000000 42.00000 X( 2, 1) 0.000000 39.00000 X( 2, 2) 0.000000 38.00000 X( 2, 3) 0.000000 26.00000 X( 2, 4) 1.000000 20.00000 X( 3,

27、1) 0.000000 34.00000 X( 3, 2) 0.000000 27.00000 X( 3, 3) 1.000000 28.00000 X( 3, 4) 0.000000 40.00000 X( 4, 1) 1.000000 24.00000 X( 4, 2) 0.000000 42.00000 X( 4, 3) 0.000000 36.00000 X( 4, 4) 0.000000 23.00000 Row Slack or Surplus Dual Price 1 101.0000 -1.000000 2 0.000000 0.000000 3 0.000000 0.0000

28、00 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 0.000000 0.000000由以上两种方法求解的结果知：甲负责任务A，乙负责任务C，丙负责任务B，丁负责任务D，可以使总花费时间最少。代入求出目标函数值 。5. 问题的深入（0-1整数规划）将约束条件由整数数据变为小数数据且目标函数由最小值化为最大值问题的求解。假设有4件工作分派给4个人来做，每项工作只能由一人来做，每个人只能做一项工作。下表为各人对各项工作所具有的工作效率。问应该

29、如何安排人选，及发挥个人特长又能使总的效率最大。表3 每个人完成各项任务需要的时间 工人人ABCD甲0.60.20.30.1乙0.70.40.30.2丙0.81.00.70.3丁0.70.70.50.45.1 模型建立设 表示第i 个人被安排做第j项工作，则当第i个人被安排去做第j项工作时=1；当第i个人不被安排到第j项工作时=0。因此，每个人只完成一项工作的约束条件为每项工作必有一个人负责的约束条件为 数学模型为s.t. 或1，i，j=1，2，3，45.2 模型求解5.2.1 用matlab求解问题根据上面建立的模型，利用matlab进行求解，具体程序如下：function y,fval=m

30、axzp(M,C) %M为C中元素的最大值m,n=size(C);C=M+zeros(n)-C; %将求极小值的目标函数系数矩阵转换成求极大值的系数矩阵M=1.0;C=C;f=C(:);Aeq=zeros(2*n,n*n);for i=1:nAeq(1:n,1+(i-1)*n:i*n)=eye(n,n);endfor i=1:nAeq(n+i,1+(i-1)*n:i*n)=ones(1,n);endbeq=ones(2*n,1);lb=zeros(n*n,1);ub=ones(n*n,1);x=linprog(f,Aeq,beq,lb,ub);y=reshape(x,n,n);y=y;y=ro

31、und(y);sol=zeros(n,n);for i=1:nfor j=1:nif y(i,j)=1sol(i,j)=C(j,i);endendendfval=sum(sol(:);fval=M*n-fval; %求出极大值的目标函数值其中，C=0.6 0.2 0.3 0.1 0.7 0.4 0.3 0.2 0.8 1.0 0.7 0.3 0.7 0.7 0.5 0.4; y,fval=maxzp(M,C)输出结果为：Optimization terminated.y = 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1fval =2.40005.2.2 用lingo求解问题根

32、据上面建立的模型，利用lingo进行求解，具体程序如下：model:sets:ren/1.4/;gongzuo/1.4/;Assign(ren,gongzuo):C,X;endsetsdata:C=0.6 0.2 0.3 0.1 0.7 0.4 0.3 0.2 0.8 1.0 0.7 0.3 0.7 0.7 0.5 0.4;enddatamax=sum(Assign:C*X); ！求目标函数极大值FOR(ren(i):sum(gongzuo(j):X(i,j)=1);FOR(gongzuo(j):sum(ren(i):X(i,j)=1);for(Assign:bin(x);end输出结果为：G

33、lobal optimal solution found.Objective value: 2.400000Extended solver steps: 0Total solver iterations: 0Variable Value Reduced Cost C( 1, 1) 0.6000000 0.000000 C( 1, 2) 0.2000000 0.000000 C( 1, 3) 0.3000000 0.000000 C( 1, 4) 0.1000000 0.000000 C( 2, 1) 0.7000000 0.000000 C( 2, 2) 0.4000000 0.000000

34、C( 2, 3) 0.3000000 0.000000 C( 2, 4) 0.2000000 0.000000 C( 3, 1) 0.8000000 0.000000 C( 3, 2) 1.000000 0.000000 C( 3, 3) 0.7000000 0.000000 C( 3, 4) 0.3000000 0.000000 C( 4, 1) 0.7000000 0.000000 C( 4, 2) 0.7000000 0.000000 C( 4, 3) 0.5000000 0.000000 C( 4, 4) 0.4000000 0.000000 X( 1, 1) 0.000000 -0.6000000 X( 1, 2) 0.000000 -0.2000000 X( 1, 3) 1.000000 -0.3000000 X( 1, 4) 0.000000 -0.1000000 X( 2,