搜索
程序文件fenpei.mfunction[z,ans]=fenpei(marix)%//////////////////////////////////////////////////%输入效率矩阵marix为方阵;%若效率矩阵中有M,则用一充分大的数代替;%输出z为最优解，ans为最优分配矩阵；%//////////////////////////////////////////////////a=marix;b=a;%确定矩阵维数s=length(a);%确定矩阵行最小值，进行行减ml=min(a');fori=1:sa(i,:)=a(i,:)-ml(i);end%确定矩阵列最小值，进行列减mr=min(a);forj=1:sa(:,j)=a(:,j)-mr(j);end%startworkingnum=0;while(num~=s)%终止条件是“（0）”的个数与矩阵的维数相同%index用以标记矩阵中的零元素，若a(i,j)=0，则index(i,j)=1,否则index(i,j)=0index=ones(s);index=a&index;index=~index;%flag用以标记划线位，flag=0表示未被划线，%flag=1表示有划线过，flag=2表示为两直线交点%ans用以记录a中“（0）”的位置%循环后重新初始化flag,ansflag=zeros(s);ans=zeros(s);%一次循环划线全过程，终止条件是所有的零元素均被直线覆盖，%即在flag0位,index=0while(sum(sum(index)))%按行找出“（0）”所在位置，并对“（0）”所在列划线，%即设置flag,同时修改index,将结果填入ansfori=1:st=0;l=0;forj=1:sif(flag(i,j)==0&&index(i,j)==1)l=l+1;t=j;endendif(l==1)flag(:,t)=flag(:,t)+1;index(:,t)=0;ans(i,t)=1;endend%按列找出“（0）”所在位置，并对“（0）”所在行划线，%即设置flag,同时修改index,将结果填入ansforj=1:st=0;r=0;fori=1:sif(flag(i,j)==0&&index(i,j)==1)r=r+1;t=i;endendif(r==1)flag(t,:)=flag(t,:)+1;index(t,:)=0;ans(t,j)=1;endendend%对while(sum(sum(index)))%处理过程%计数器：计算ans中1的个数，用num表示num=sum(sum(ans));%判断是否可以终止，若可以则跳出循环if(s==num)break;end%否则，进行下一步处理%确定未被划线的最小元素，用m表示m=max(max(a));fori=1:sforj=1:sif(flag(i,j)==0)if(a(i,j)m)m=a(i,j);endendendend%未被划线，即flag=0处减去m；线交点，即flag=2处加上mfori=1:sforj=1:sif(flag(i,j)==0)a(i,j)=a(i,j)-m;endif(flag(i,j)==2)a(i,j)=a(i,j)+m;endendendend%对while(num~=s)%计算最优（min）值zm=ans.*b;z=0;z=sum(sum(zm));/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////运行实例：a=[37.732.938.83735.443.433.142.234.741.833.328.538.930.433.629.226.429.628.531.100000];[z,ans]=fenpei(a)z=127.8000ans=0000100010010001000000100111222202443311072244770355775504339966088811440666121211110599131312120