练习1：指派问题

练习一：指派问题摘要n项任务要分给n个人完成，由于每个人的专长不同，完成各项 任务的所需要的成本也不同。每个人完成一项工作，相当于一个人只 能选择一项任务，这是一个典型的0-1整数规划问题。基于此，设xij在第i个人完成第j项工作时为1,反之为0,并由此得出了总成本u =埜nxC，从而建立了线性规划模型。并利用Matlab程序对附表 ij iji=1 j=1的数据进行处理，求解模型得到最小总成本为32.关键字：0-1整数规划;一、问题重述n项任务要分给n个人完成，每个人完成一项工作，但是由于每 个人的个人专长不同，完成各项任务的所需要的成本也不同。基于现 实考虑，需要通过数学建模的手段，确定怎么分配这些工作任务，使 得总成本最小。二、问题分析n项任务要分给n个人完成，需要通过数学建模的手段，确定怎 么分配这些工作任务，使得总成本最小。每一个人只能完成一项任务， 相当于一个人只能选择一项任务，这是一个典型的0-1整数规划问题。三、符号说明符号符号说明xij当第i个人完成第j项任务时为1,反之为0Cij第i个人完成第j项任务的成本四、模型的建立与求解通过问题的分析，我们知道这个问题是一个典型的0-1整数规划 问题。设_（1当第i个人做第j个任务时xij - 0当第i个人不做第j个任务时此时，n个人完成n项任务的总成本可以表示为：u _工 KxCij ij因此，我们可以建立如下线性规划模型:X _ 0或1（第i个人做第j个任务时为1,反之为0）通过Matlab程序对附表1的数据进行处理，得到成本总小为u _ 32 附录:表：每个人员的成本人员工作123451127979289666371712149415146610Matlab数据处理程序：c=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;c=c(:);a=zeros(10,25);for i=1:5a(i,(i-1)*5+1:5*i)=1; a(5+i,i:5:25)=1;endb=ones(10,1);x,fval=bintprog(c,a,b);x=reshape(x,5,5),fval a=zeros(10,25);Optimization terminated.0 10 0 00 0 10 00 0 0 0 10 0 0 1 01 0 0 0 0fval =32