单纯型法

单纯型法 ,,function,[X,obj]=dcxf(A,C,J),,,%本单纯形法程序只适应于已化为标准形式的线性规划问题的求解., ,,%,A为系数矩阵的增广矩阵., ,,%,C为目标中变量的系数., ,,%,J为初始基变量., ,,%当有人工变量时，其目标函数中的系数M取值应大于10,,,M=9999;,,%人工变量在目标函数中的系数., ,,[m,n]=size(A);,%求矩阵A的长度和宽度., ,,f=find(C<=-M);%找出人工变量的位置., ,,temp=1;, ,,while,temp, ,,,,,,,for,,i=1:n-1, ,,,,,,,,,,,,,pbs(i)=C(i)-sum(A(:,i).*(C(J))');,%求判别数.,,,,,,,,end, ,,,,,,,if,,pbs<=0,%判别数全部小于0时., ,,,,,,,,,,,%******下找基变量中是否有人工变量.*******%,,,,,,,,,,,,if,length(f),%原问题中有加人工变量., ,,,,,,,,,,,,,,for,i=1:length(f),,,,,,,,,,,,,,,,,,if,length(find(f(i)==J)), ,,,,,,,,,,,,,,,,,,,,t=0;,%基变量中有人工变量., ,,,,,,,,,,,,,,,,,,,,break;, ,,,,,,,,,,,,,,,,,else, ,,,,,,,,,,,,,,,,,,,,t=1;,%基变量中无人工变量., ,,,,,,,,,,,,,,,,,end, ,,,,,,,,,,,,,,end, ,,,,,,,,,,,else, ,,,,,,,,,,,,,,,t=1;,%原问题中没有加人工变量., ,,,,,,,,,,,end, ,,,,,,,,,,,,%*****下判断是否有非基变量判别数为0.*******%,,,,,,,,,,,,,,,if,t,,, ,,,,,,,,,,,,,,,g=1;,, ,,,,,,,,,,,,,,,,for,,i=1:n-1, ,,,,,,,,,,,,,,,,,,,,if,~length(find(i==J)),,,,,,,,,,,,,,,,,,,,,,,,h(g)=i;,%找出非基变量., ,,,,,,,,,,,,,,,,,,,,,,,g=g+1;,,,,,,,,,,,,,,,,,,,,,,,,end, ,,,,,,,,,,,,,,,,end, ,,,,,,,,,,,,,%******************************************%, ,,,,,,,,,,,,,,,,,if,,length(find(pbs(h)==0)),,%有非基变量判别 数为0., ,,,,,,,,,,,,,,,,,,,,,disp('无穷多最优解,现输出任一解:'), ,,,,,,,,,,,,,,,,,,,,,X=zeros(1,n-1);,,,,,,,,,,,,,,,,,,,,,,,,,,X(:,J)=A(:,n);,,, ,,,,,,,,,,,,,,,,,,,,,X,, ,,,,,,,,,,,,,,,,,,,,,obj=X*C',,,,,,,,,,,,,,,,,,else, ,,,,,,,,,,,,,,,,,,,,,,disp('有最优解:');, ,,,,,,,,,,,,,,,,,,,,,,X=zeros(1,n-1);,,,,, ,,,,,,,,,,,,,,,,,,,,,,X(:,J)=A(:,n);,, ,,,,,,,,,,,,,,,,,,,,,,X,,,,,,,,,,,,,,,,,,,,,,,obj=X*C',,,,,,,,,,,,,,,,,,end,,,,,,,,,,,,,,,,else, ,,,,,,,,,,,,,,,,disp('无可行解.');, ,,,,,,,,,,,,,,,,break;, ,,,,,,,,,,,,end, ,,,,,,,,,,,,temp=0;, ,,,,,,else,%判别数中有大于0的数时., ,,,,,,,,,,,,k=find(pbs==(max(pbs)));,%找出换入基的变量.,,,,,,,,,,,,,if,length(k)>1,,,,,,,,,,,,,,,,,k=k(1);,%若判别数有多个相同的最大值则默认取第一个值., ,,,,,,,,,,,,end, ,,,,,,,,,,,,if,,A(:,k)<=0,,,,,,,,,,,,,,,,,,disp('无界解.');, ,,,,,,,,,,,,,,,,break;, ,,,,,,,,,,,,else, ,,,,,,,,,,,,,,,,for,,j=1:m, ,,,,,,,,,,,,,,,,,,,,if,,A(j,k)<=0,,,,,,,,,,,,,,,,,,,,,,,,,d(j)=inf;,,,,,,,,,,,,,,,,,,,,,else, ,,,,,,,,,,,,,,,,,,,,,,,,d(j)=(A(j,n))/A(j,k);, ,,,,,,,,,,,,,,,,,,,,end, ,,,,,,,,,,,,,,,,end, ,,,,,,,,,,,,end, ,,,,,,,,,,,,s=find(d==min(d));,%找出换出基的变量., ,,,,,,,,,,,,if,length(s)>1, ,,,,,,,,,,,,,,,,s=s(find(s==max(s)));,,,,,,,,,,,,,end, ,,,,,,,,,,,,J(s)=k;,%换基., ,,,,,,,,,,,,A(s,:)=A(s,:)./A(s,k);,%将主元素化为1., ,,,,,,,,,,,,for,,i=1:m, ,,,,,,,,,,,,,,,,if,,i~=s, ,,,,,,,,,,,,,,,,,,,A(i,:)=A(i,:)-A(i,k).*A(s,:);,%与主元素所在列的其他元素化为0., ,,,,,,,,,,,,,,,,end, ,,,,,,,,,,,,end, ,,,,,,,,,,,,temp=1;, ,,,,,,,end, ,,,,end,