算法实现与分析
算法1．单纯形法
具体算例：
min z =−3x1+x2+2x3
{3x1+2x2−3x3=6
x1−2x2+x3+x5=4x1,x2,x3≥0
标准化后：
min z =−3x1+x2+2x3+Mx4+Mx5
{3x1+2x2−3x3+x4=6
x1−2x2+x3+x5=4x1,x2,x3,x4,x5≥0
用单纯形法求解，程序如下：
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];
Xt=[4 5];
for i=1:length(C)-1
D=0;
for j=1:length(Xt)
D=D+A(j,i)*C(Xt(j));
end
xi(i)=C(i)-D;
end
s=[];
for i=1:length(xi)
if xi(i)<0
s=[s,i];
end
end
f=length(s);
h=1;
while (f)
for k=1:length(s)
j=1;
A
x=[];
for i=1:length(Xt)
if A(i,s(k))>0
x(j)=i;
j=j+1;
end
end
x
if(length(x)+1==1)
break;
end
y=1
x
for i=1:length(x)
if B(x(i))/A(x(i),s(k))end
end
y=x(y);
end
y1=Xt(y);%»»³ö±äÁ¿
s
k
aa=A(y,s(k))%s(k)Ϊ»»Èë±äÁ¿
A(y,:)=A(y,:)./aa;
B(y,:)=B(y,:)./aa;
z=[];
for i=1:length(Xt)
z=[z,i];
end
z
z(y)=[];
z
Xt
for i=1:length(z);
yz=-A(z(i),s(k))
A(z(i),:)=A(z(i),:)+A(y,:).*yz
B(z(i))
B(y)
yz
B(z(i))=B(z(i))+B(y).*yz
end
for i=1:length(Xt)
if Xt(i)==y1
Xt(i)=s(k);
break
end
end
Xt
disp('ת»»ºó')
A=A
B=B
AB=[A,B];
for i=1:length(C)
D=0;
for j=1:length(Xt)
D=D+AB(j,i)*C(Xt(j));
end
xi(i)=C(i)-D;
end
xi
s=[];
for i=1:length(xi)-1
if xi(i)<0
s=[s,i];
end
end
s
vpa([A,B;C]);
f=length(s);
h=h+1;
if h==5
break
end
end
-xi(length(xi))
