单纯形法的MATLAB实现_单纯形法的matlab实现

单纯形法的MATLAB实现由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“单纯形法的matlab实现”。

clear clc M=1000000;A=[3,2,-3,1,0;1,-2,1,0,1];%约束矩阵 C=[-3,1,2,M,M,0];%价值矩阵 B=[6,4]';%右端向量 s=find(C

for k=1:length(s)

x=find(A(:,s(k))>0);

y=find(B(x)./A(x,s(1))==min(B(x)./A(x,s(1))));%选择的要有正元素

if(length(x)+1==1)

break;

end

end

y=x(y);%找到的xj的行数

aa=A(y,s(k));%找到的xj

A(y,:)=A(y,:)./aa;

B(y,:)=B(y,:)./aa;

z=find(A(:,s(k)));%除去找到的行

z(find(z==y))=[];for i=1:length(z);

yz=-A(z(i),s(k));

A(z(i),:)=A(z(i),:)+A(y,:)*yz;

disp('*')

B(z(i),:)=B(z(i),:)+B(y,:).*yz;end disp('转换后')A=A B=B AB=[A,B];

C=C+AB(y,:)*(-C(s(k)))

s=find(C

vpa([A,B;C]);

s=find(C

f=length(s);end-C(length(C))%最有解

：max 2*x1+3*x2

s.t.x1+2*x2

4*x1

4*x2

x1,x2>=0

加入松驰变量，化为标准型，得到

A=[1 2 1 0 0 8;4 0 0 1 0 16;0 4 0 0 1 12;2 3 0 0 0 0];

N=[3 4 5];

然后执行? [sol,val,kk]=implex(A,N)就可以了。

注：基变量对应的基矩阵一定是单位阵。（这一局限将在后面的升级是改善）

% 求解标准型线性规划:max c*x;s.t.A*x=b;x>=0 % 本函数中的A是单纯初始表，包括:最后一行是初始的检验数，最后一列是资源向量b % N是初始的基变量的下标

%输出变量sol是最优解

%输出变量val是最优值，kk是迭代次数 function [sol,val,kk]=implex(A,N)[mA,nA]=size(A);kk=0;%迭代次数 flag=1;while flag kk=kk+1;if A(mA,:)0&A(1:mA-1,i)

disp('have infinite solution!');flag=0;break;end end if flag % 还不是最优表，进行转轴运算 temp=0;for i=1:nA-1 if A(mA,i)>temp temp=A(mA,i);inb=i;% 进基变量的下标 end end sita=zeros(1,mA-1);for i=1:mA-1 if A(i,inb)>0 sita(i)=A(i,nA)/A(i,inb);end end temp=inf;for i=1:mA-1 if sita(i)>0&sita(i)

A(outb,:)=A(outb,:)/A(outb,inb);for i=1:mA if i~=outb A(i,:)=A(i,:)-A(outb,:)*A(i,inb);end end end end end