Matlab线性规划单纯形发单步迭代算法

% 实现一步单纯形法 % 输入参数： % A - (m,n) m行n列系数矩阵 % b - (m,1) (正)右端向量 % c - (1,n) 目标函数系数 % iB - (1,m) 整数向量记录当前基本变量指标数 % iN - (1, n-m) 整数向量记录当前非基本变量指标数 % xB - (m, 1) 向量代表当前基本变量的值 % 输出参数： % istatus - 整数标记单纯形法执行状态 % istatus=0 正常单纯形法步完成 % istatus=32 问题无界 % istatus=-1 找到最优基本可行解 % iB - (1,m) 整数向量记录运行单纯形法之后的基本变量的指标数 % iN - (1, n-m) 整数向量记录运行单纯形法之后的非基本变量的指标数 % xB - (m, 1) 向量记录运行单纯形法之后的基本变量的值 function [istatus,iB,iN,xB]=simplex_step(A,b,c,iB,iN,xB) [m,n]=size(A); mA=m+1; nA=n+1; AA=zeros(mA,nA); % 以下求非基变量初始检验数,基变量的初始检验值即为0 B=zeros(m,m); % 创建初始基 cB=zeros(1,m); for i=1:m ii=iB(1,i); B(:,i)=A(:,ii); cB(1,i)=c(1,ii); end w=cB*inv(B); for i=1:n-m ii=iN(1,i); AA(mA,ii)=w*A(:,ii)-c(ii); end % 以下加入右端向量的值 for i=1:m AA(i,nA)=b(i,1); end %以下加入系数矩阵的值 for i=1:m for j=1:n AA(i,j)=A(i,j); end end kk=0; % 迭代次数 flag=1; istatus=0; while flag kk=kk+1; if AA(mA,:)<=0 % 已找到最优解 flag=0; for i=1:mA-1 xB(i,1)=AA(i,nA); end fmin=AA(mA,nA); istatus=-1; else for i=1:nA-1 if AA(mA,i)>0&AA(1:mA-1,i)<=0 % 问题有无界解 disp('have infinite solution!'); istatus=32; flag=0; break; end end if flag % 还不是最优表，进行转轴运算 temp=0; for i=1:nA-1 if AA(mA,i)>temp temp=AA(mA,i); inb=i; % 进基变量的下标 end end sita=zeros(1,mA-1); for i=1:mA-1 if AA(i,inb)>0 sita(i)=AA(i,nA)/AA(i,inb); end end temp=inf; for i=1:mA-1 if sita(i)>0&sita(i)<temp temp=sita(i); outb=i; % 出基变量下标 end end % 以下更新iB,iN for i=1:n-m if i==inb iN(1,i)=iB(outb); end end for i=1:mA-1 if i==outb iB(1,i)=inb; end end % 以下进行转轴运算 AA(outb,:)=AA(outb,:)/AA(outb,inb); for i=1:mA if i~=outb AA(i,:)=AA(i,:)-AA(outb,:)*AA(i,inb); end end end end end %测试程序 1 % A=[-1 2 1 0 0;2 3 0 1 0;1 -1 0 0 1;] % b=[4 12 3] % c=[-4 -1 0 0 0] % iB=[3 4 5] % iN=[1 2] % xB=[4;12;3;] % [istatus,iB,iN,xB]=simplex_step(A,b,c,iB,iN,xB) % 输出： % istatus = % -1 % iB = % 3 2 1 % iN = % 5 4 % xB = % 5.8000 % 1.2000 % 4.2000