线性规划单纯形法matlab解法

线性规划单纯形法matlab解法%单纯形法matlab程序-ssimplex%求解标准型线性规划:maxc*x;s.t.A*x=b;x=0%本函数中的A是单纯初始表，包括:最后一行是初始的检验数，最后一列是资源向量b%N是初始的基变量的下标%输出变量sol是最优解,其中松弛变量（或剩余变量）可能不为0%输出变量val是最优目标值，kk是迭代次数%例：max2*x1+3*x2%s.t.x1+2*x2=8%4*x1=16%4*x2=12%x1,x2=0%加入松驰变量，化为标准型，得到%A=[121008;%4001016;%0400112;%230000];%N=[345];%[sol,val,kk]=ssimplex(A,N)%然后执行[sol,val,kk]=ssimplex(A,N)就可以了。function[sol,val,kk]=ssimplex(A,N)[mA,nA]=size(A);kk=0;%迭代次数flag=1;whileflagkk=kk+1;ifA(mA,:)=0%已找到最优解flag=0;sol=zeros(1,nA-1);fori=1:mA-1sol(N(i))=A(i,nA);endval=-A(mA,nA);elsefori=1:nA-1ifA(mA,i)0&A(1:mA-1,i)=0%问题有无界解disp('haveinfinitesolution!');flag=0;break;endendifflag%还不是最优表，进行转轴运算temp=0;fori=1:nA-1ifA(mA,i)temptemp=A(mA,i);inb=i;%进基变量的下标endendsita=zeros(1,mA-1);fori=1:mA-1ifA(i,inb)0sita(i)=A(i,nA)/A(i,inb);endendtemp=inf;fori=1:mA-1ifsita(i)0&sita(i)temptemp=sita(i);outb=i;%出基变量下标endend%以下更新Nfori=1:mA-1ifi==outbN(i)=inb;endend%以下进行转轴运算A(outb,:)=A(outb,:)/A(outb,inb);fori=1:mAifi~=outbA(i,:)=A(i,:)-A(outb,:)*A(i,inb);EndEndEndEndend