指派问题 匈牙利算法实现

若能在系数矩阵(bij)中找出n个独立的0元素；则令解矩阵(xij)中对应这n个独立的0元素取值为1，其它元素取值为0。将其代入目标函数中得到zk=0，它一定是最小。这就是以(bij)为系数矩阵的指派问题的最优解。也就得到了问题的最优解。

function [zans]=success（marix）

count=0;
%//////////////////////////////////////////////////
            %输入效率矩阵 marix 为方阵;
            %若效率矩阵中有 M则用一充分大的数代替;
            %输出z为最优解，ans为 最优分配矩阵；
%//////////////////////////////////////////////////

[hl]=size（marix）;
aamarix=marix;
if h>l
    marix=zeros（h）;
    for i=1:h
        for j=1:l
            marix（ij）=aamarix（ij）;
        end
    end
elseif l>h
    marix=zeros（l）;
    for i=1:h
        for j=1:l
            marix（ij）=aamarix（ij）;
        end
    end
end

a=marix;
b=a;

%确定矩阵维数
s=length（a）;
%确定矩阵行最小值，进行行减
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
% start working
num=0;


me=a;


while（num~=s）  %终止条件是“（0）”的个数与矩阵的维数相同
    %index用以标记矩阵中的零元素，若a（ij）=0，则index（ij）=1否则index（ij）=0
    index=ones（s）;
   % sum（sum（index））
  %  sum（sum（a））
    me=a;
   % index=a&index;
   index=me&index;
   % sum（ sum（index））
    index=~index;
%    sum（sum（index））
    %flag用以标记划线位，flag=0 表示未被划线，
    %flag=1 表示有划线过，flag=2 表示为两直线交点
    %ans用以记录 a 中“（0）”的位置
    %循环后重新初始化flagans
    flag = zeros（s）;
    ans0 = zeros（s）;
    %一次循环划线全过程，终止条件是所有的零元素均被直线覆盖，
    %即在flag>0位index=0
    
   
    
    while（sum（sum（index）））
        %按行找出“（0）”所在位置，并对“（0）”所在列划线，
        %即设置flag同时修改index将结果填入ans
       k =0; 
       p = 0;
       for i=1:s
            t=0;
            
            l=0;
            for j=1:s
                if（flag（ij）==0&&index（ij）==1）
                    l=l+1;
                    t=j;
                end
            end
            if（l==1）
                k = 1;
                flag（:t）=flag（:t）+1;
                index（:t）=0;
                ans0（it）=1;
            else
                k=0;
            end
        end
        %按列找出“（0）”所在位置，并对“（0）”所在行划线，
        %即设置flag同时修改index将结果填入ans
        
        for j=1:s
            t=0;
            r=0;
            for i=1:s
                if（flag（ij）==0&&index（ij）==1）
                    r=r+1;
                    t=i;
                end
            end
            if（r==1）
                p = 1;
                flag（t:）=flag（t:）+1;
                index（t:）=0;
                ans0（tj）=1;
            else
                p=0;
            end
        end
        
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

        if （0 ==p && k ==0）    %44 
            sto1 = s+1;
           
            pos = 1;
            for numb = 1:s;%55
                sto =0;