运筹学通论实验二单纯形法
一、实验目的:通过对单纯形法的程序实现,得出最优解、无穷多最优解、无界解、无可行
解。
二、实验环境:MATLAB
三、实验内容
max z=-3x1+x2+2x3
s.t﹛3x1+2x2-3x3<=6 ;x1-2x2+x3<=4; x1,x2,x3 >=0
化为标准型{3x1+2x2-3x3+x4=8; x1-2x2+x3+x5=4;x1,x2,x3,x4,x5>=0
四、实验过程
1、实验编码
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<0);
f=length(s);
while(f)
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);
aa=A(y,s(k));
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<0);
vpa([A,B;C]);
s=find(C<0);
f=length(s);
end
-C(length(C))
2、实验结果
*
转换后
A =
1.0000 0.6667 -1.0000 0.3333 0
0 -2.6667 2.0000 -0.3333 1.0000
B =
2
2
C =
0 3 -1 1000001 1000000 6
*
转换后
A =
1.0000 -0.6667 0 0.1667 0.5000
0 -1.3333 1.0000 -0.1667 0.5000
B =
3
1
C =
1.0e+006 *
0 0.0000 0 1.0000 1.0000 0.0000 ans =
-7
即最优解为7