dant.m

Matlab的Optimization软件包

%打印特殊LP模型的单纯形表
function D=dant(c,A,b,p)
%本程序编于2006-12-12
%处理系数矩阵中含有单位矩阵的情况
%c为目标函数系数向量,A为约束系数矩阵,b为右边向量
%本程序默认处理的对象是非退化的,因为这种处理方式能加快收敛速度,
%若处理的对象是退化的,则输入参数p为2
if nargin==3,p=1;end
[m,n]=size(A);
if m~=length(b)|n~=length(c)|min(b)<0,disp('输入有误！');D=[];
else    
    B=[];for k=1:m,temp=aeye(m,k);for l=1:n,if A(:,l)==temp,B=[B,l];break;end,end,end%寻找基阵
    D=[B',A,b;0,c-c(sort(B))*inv(A(:,sort(B)))*A,-1];%组装
    d=D;h=0;
    while size(d)>0&h==0
        B=d(1:m,1);A=d(1:m,2:n+1);b=d(1:m,n+2);lamda=d(m+1,2:n+1);times=d(m+1,n+2);%分离
        N_negative=find(lamda<0); N_zero=find(lamda==0);T=intersect(setdiff(1:n,B),N_zero);f=1;
        for k=1:length(N_negative),if A(:,N_negative(k))<0,d=[];f=0;break;end,end%无解
        if f==1&length(N_negative)>0
            if p==1,[temp,C]=min(lamda);%按最快收敛的方式变换
            else [temp,C]=max(lamda<0);%按Bland法则变换
            end    
        elseif f==1&length(T)>0&length(N_negative)==0
            f=0;for k=1:length(T),if max(A(:,T(k)))>0,f=1;C=T(k);h=1;break;end,end%无穷多个解
            if f==0,d=[];end%唯一解
        elseif min(lamda)>=0,d=[];f=0;%唯一解
        end
        if f==1%变换
            N_positive=find(A(:,C)>0);T=b(N_positive)./A(N_positive,C);[temp,T]=min(T);            
            R=N_positive(T);B(R)=C;RE=rce(d(:,2:n+2),R,C,2);RE(m+1,n+1)=times-1;d=[[B;0] RE];  
        end
        D=[D;d];x=size(D,1);lamda=D(x,2:n+1);
        if min(lamda)>=0,B=D(x-m:x-1,1);T=zeros(n,1);T(B)=D(x-m:x-1,n+2);D(x,1)=c*T;end%最优值
    end
end