匈牙利法的Matlab代码及测试

代码：

function [z,x_ij]=xiongyalifa(a)
%输出z为最小值，x_ij为最优解；
b=a;
%确定矩阵维数
s=length(a);

%第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。
%减去每行的最小值
ml=min(a');
for i=1:s
  a(i,:)=a(i,:)-ml(i);
end
%减去每列的最小值
mr=min(a);
for j=1:s
  a(:,j)=a(:,j)-mr(j);
end
% 第二步：进行试指派，以寻求最优解。
num=0;
while(num~=s) %终止条件是独立0元素的个数与s相等
%index为独立0元素：若a(i,j)=0，则index(i,j)=1,否则index(i,j)=0
%flag为线：flag=0无线，flag=1有线过，flag=2交点
%x_ij用以记录a中独立0元素的位置
  index=ones(s);
  index=a&index;
  index=~index;
  %循环后重新初始化flag,x_ij
  flag = zeros(s);
  x_ij = zeros(s);
  %一次循环划线全过程，终止条件是所a=有的零元素均被直线覆盖
  while(sum(sum(index)))
    %找出只有一个0元素的行，对其所在列划线
    for i=1:s
      t=0;
      l=0;
      for j=1:s
        if(flag(i,j)==0&&index(i,j)==1)
          l=l+1;
          t=j;
        end
      end
      if(l==1)
        flag(:,t)=flag(:,t)+1;
        index(:,t)=0;
        x_ij(i,t)=1;
      end
    end
    %找出只有一个0元素的列，对其所在行划线
    for j=1:s
      t=0;
      r=0;
      for i=1:s
        if(flag(i,j)==0&&index(i,j)==1)
          r=r+1;
          t=i;
        end
      end
      if(r==1)
        flag(t,:)=flag(t,:)+1;
        index(t,:)=0;
        x_ij(t,j)=1;
      end
    end
  end 
  %处理过程
  %x_ij中1的个数，即独立0元素的个数，用num表示
  num=sum(sum(x_ij));
  if(s==num)
    break;
  	end
 %第三步：增加0元素。 
  %确定未被划线的最小元素，用m表示
  m=max(max(a));
  for i=1:s
    for j=1:s
      if(flag(i,j)==0)
        if(a(i,j)<m)
          m=a(i,j);
        end
      end
    end
  end
  %未被划线，即flag=0处减去m；线交点，即flag=2处加上m
  for i=1:s
    for j=1:s
      if(flag(i,j)==0)
        a(i,j)=a(i,j)-m;
      end
      if(flag(i,j)==2)
          a(i,j)=a(i,j)+m;
      end
    end
  end
end %对while(num~=s)
%计算最优值
zm=x_ij.*b;
z=0;
z=sum(sum(zm));

测试：

系数矩阵a=

[2 15 13 5

10 4 14 15

9 14 16 13

7 8 11 9]

 文章来源地址https://uudwc.com/A/Vmg5o