danchunxing.m

一个最短路的c实现

%  求最大值
% a为约束条件矩阵(n*m)；b为约束条件边界(n*1)；c价值系数(1*m)
function [z,X]=danchunxing(f,A,b)  
echo on
q1=size(A);
q2=size(b);
n=q1(1);             % n为约束条件个数
m=q2(1);             %为约束条件边界的个数
if m~=n
    fprintf('A与b的行数不相等？\n');
    break
end
f1=zeros(1,n);       % 松弛变量在目标函数中的系数
f2=[f,f1];
A1=eye(n,n);         % 松弛变量在约束条件中的系数矩阵
A2=[A,A1];
b1=b;   
N=(q1(2)+1):1:(q1(2)+n);
while 1    
    s=f2-f1*A2;      % 求检验数
    if s<=0          % 判断检验数是否全大于零
        break
    end
    [Y,k]=max(s);    %  寻找换出变量
    for i=1:n        
        if A2(i,k)>0
            t=b1(i)/A2(i,k);
            l=i;
            break
        end
    end
    for i=1:n         % 寻找换入变量   
        if A2(i,k)>0&b1(i)/A2(i,k)<t
            t=b1(i)/A2(i,k);
            l=i;
        end
    end
    f1(l)=f2(k);
    N(l)=k;
    for i=1:n         % 高斯迭代
        if i~=l
            b1(i)=b1(i)-A2(i,k)*b1(l)/A2(l,k);
            A2(i,:)=A2(i,:)-A2(i,k).*(A2(l,:)./A2(l,k));
        end
    end
    b1(l)=b1(l)/A2(l,k);
    A2(l,:)=A2(l,:)/A2(l,k);
end
p=1:1:(q1(2)+n);
p0=p;
p0(N)=[];
if s(p0)<0 
   z=-f1*b1;            %  求解
   X=b1;
   fprintf('唯一最优解是 : %f\n',-z);
   fprintf('基变量是：\n');
   for i=1:length(N)
       fprintf(' x%d  ',N(i));
       if rem(i,10)==0
           fprintf('\n');
       end
   end
   fprintf('\n');
   fprintf('各检验数为：\n');
   for i=p  
       fprintf('r%d=%0.3f \n',i,s(i));
       if rem(i,8)==0
           fprintf('\n');
       end
   end
else
   fprintf('无穷最优解！\n');
end
echo off