指派问题的算法

1/15指派问题的算法分析与实现摘要，从而降低成本、提高效益。然而，如果没有科学的方法是很难实现问题通常是通过匈牙利算法来求解，但指派问题也可以归结为一个法来求解可以更简单，也更方便程序的阅读和理解。与此同时，我们还对0-1题由整数数据深入研究到小数数据。最后通过实例来说明运用指派问题又称分配问题，其用途非常广泛，比如某公司指派n个人去做n效率(如熟练程度等)，怎样安排会使总销量达到最大？这些都是一个企业经营2/15m生产管理中，总希望把人员进行最佳分配，以发挥最大的工作效率；某部门有n3.指派问题的描述指派问题的标准形式(以人和事为例)如下。有n个人和n项任务，已知第i个人做第j件事的费用为cij，要求确定人和事之间的一一对应的指派方案，使阵|..|C=(cij)nn|..|为系数矩阵(CoefficientMatrix)，也称为效益矩阵或价值矩阵。矩阵的元3/15ijijl1,分配第i单位资源用于第j项活动表示给定的资源分配用于给定活动时的有关效益(时间，费用，价值等)，且型一般形式ijijijj=1iji=1 ij在模型中，约束条件式(2)表示每个人只能做一件事，约束条件式(3)表式(3)。每行元素中也有且只有一个1，以满足约束条件(2)。指派问题n!个可极大化的指派问题ijijijijijijijijij4/15ijijijijijijijijij.1匈牙利算法4.1.1匈牙利算法的理论基础ij个常数u，从每一列中分别减去(或加上)一个常数v，得到一个新的ij效率矩阵[b]，则以[b]为效率矩阵的分配问题与以[a]为效率矩阵ijijij素最少直线数等于位于不同行不同列的‘0’元素的最大个数。(1)从第一行开始，若该行只有一个零元素打上()号。对打()号零元素所 (2)从第一列开始，若该列只有一个零元素就对这个零元素打上()号(同样不考虑已划去的零元素)，对打()号零元素所在行划一条直线。若该列没有零(3)重复(1)、(2)两个步骤，可能出现三种情况：5/15①矩阵每行都有一个打()号零元素，很显然，按照上述步骤得到的打()的两个以上零元素，即出现了零元素的闭回路，这个时候可顺着闭回路的走向，对每个间隔的零元素打上()号，然后对所有打()③矩阵中所有零元素或打上()号，或被划去，但打()号零元素个数小于m。第四步：为了设法使每行都有一个打()的零元素，就要继续对矩阵进行变换；(1)从矩阵未被直线覆盖的元素找出最小元素k；(2)对矩阵的每行，当该行有直线覆盖时，令u=0，无直线覆盖的，令u=k；ii(3)对矩阵的每列，当该列有直线覆盖时，令v=-k，无直线覆盖的，令v=0；jj(4)得列一个变换后的矩阵，其中每个元素b=a-u-v。ijijij第五步：回到第三步，反复进行，一直到矩阵中每一行都有一个打()的零元素4.1.3匈牙利算法实现指派问题任务任务CB2D20A人甲乙丙丁n6/15-1|-14|||||7|-129316272842364-1661|-1→→||740661|L1-44550-4|7→→→|||||L147(0)」Z101。0-1规划(0-1Programming)一种特殊形式的整数规划。这种规划的数都可以用二进制记数法用若干个0-1变量表示。0-1变量可以数量化地描无等现象所反映的离散变量间的逻辑关系、顺计、工厂选址、生产计划安排、旅行购物、背包问题、人员安排、代码选种问题。实际上，凡是有界变量的整数规划都4.2.1模型假设7/15人人甲乙丙丁任务AAjxijx=1ijx=0ij4.2.2模型建立1421222324313233344142434421314112223242132333431424344414222324414243448/1514s.t.212223243132333441424344213141122232421323334314243444ij4.2.3模型求解Aeqzerosn,n*n);*n行n*n列的等式约束0系数矩阵Aeq(1:n,1+(i-1)*n:i*n)=eye(n,n);%eye表示生成n阶单位阵Aeq(n+i,1+(i-1)*n:i*n)=ones(1,n);%生成1行n列元素为1的向量beq=ones(2*n,1);%生成2*n行1列元素为1的等式约束右端项lb=zeros(n*n,1);%生成n*n行1列元素为0的不等式约束左端项ub=ones(n*n,1);%生成n*n行1列元素为1的不等式约束右端项x=linprog(f,[],[],Aeq,beq,lb,ub);%求目标函数达到极小值的x值y=reshape(x,n,n);%将上式求出的x值组成的向量变成n阶矩阵y=round(y);%对y中的元素取整，生成匹配矩阵值的目标函数值C20];y=y1000fval=101terminated.0001model:sets:data:2024423623;Globaloptimalsolutionfound.Objectivevalue:101.0000Extendedsolversteps:0Totalsolveriterations:0VariableC(1,1)Value25.00000ReducedCost0.0000009/15C(1,2)29.000000.000000C(1,3)31.000000.000000C(1,4)42.000000.000000C(2,1)39.000000.000000C(2,2)38.000000.000000C(2,3)26.000000.000000C(2,4)20.000000.000000C(3,1)34.000000.000000C(3,2)27.000000.000000C(3,3)28.000000.000000C(3,4)40.000000.000000C(4,1)24.000000.000000C(4,2)42.000000.000000C(4,3)36.000000.000000C(4,4)23.000000.000000X(1,1)0.00000025.00000X(1,2)1.00000029.00000X(1,3)0.00000031.00000X(1,4)0.00000042.00000X(2,1)0.00000039.00000X(2,2)0.00000038.00000X(2,3)0.00000026.00000X(2,4)1.00000020.00000X(3,1)0.00000034.00000X(3,2)0.00000027.00000X(3,3)1.00000028.00000X(3,4)0.00000040.00000X(4,1)1.00000024.00000X(4,2)0.00000042.00000X(4,3)0.00000036.00000X(4,4)0.00000023.00000RowSlackorSurplusDualPrice1101.0000-1.00000020.0000000.00000030.0000000.00000040.0000000.00000050.0000000.00000060.0000000.00000070.0000000.00000080.0000000.00000090.0000000.0000000/15445.问题的深入(0-1整数规划)小数数据且目标函数由最小值化为最大值问题人甲乙丙丁CABDijijij14212223243132333441424344条件为2131411222324213233343142434442/1521222324313233344142434414s.t.212223243132333441424344213141122232421323334314243444ijMCC=M+zeros(n)-C;%将求极小值的目标函数系数矩阵转换成求极大值的系M=1.0;Aeqzerosn,n*n);Aeq:n,1+(i-1)*n:i*n)=eye(n,n);Aeqni1+(i-1)*n:i*n)=ones(1,n);beqonesnrogfAeqbeqlbubfval=M*n-fval;%求出极大值的目标函数值C=[0.60.20.30.10.70.40.30.20.81.00.70.30.70.70.50.4];>>[y,fval]=maxzp(M,C)Optimizationterminated.y=y0000100fval=2.400010000001ren/1..4/;gongzuo/1..4/;Assign(ren,gongzuo):C,X;endsets0.60.20.30.10.70.40.30.20.81.00.70.30.70.70.50.4;enddatamaxsumAssignCX极大值jGlobaloptimalsolutionfound.Objectivevalue:Extendedsolversteps:2.40000003/154/15Totalsolveriterations:VariableC(1,1)C(1,2)C(1,3)C(1,4)C(2,1)C(2,2)C(2,3)C(2,4)C(3,1)C(3,2)C(3,3)C(3,4)C(4,1)C(4,2)C(4,3)C(4,4)X(1,1)X(1,2)X(1,3)X(1,4)X(2,1)X(2,2)X(2,3)X(2,4)X(3,1)X(3,2)X(3,3)X(3,4)X(4,1)X(4,2)X(4,3)X(4,4)Value0.60000000.20000000.30000000.10000000.70000000.40000000.30000000.200