Brnach&bound

Solo disponible en BuenasTareas
  • Páginas : 2 (316 palabras )
  • Descarga(s) : 0
  • Publicado : 9 de noviembre de 2011
Leer documento completo
Vista previa del texto
function [ incumbente,xincumb ] = BB(A,b,c)
contador=1;
total=1;
Conjunto(1).A=A;
Conjunto(1).b=b;
Conjunto(1).c=c;

incumbente=999999999;
xincumb=0;while contador<=length(Conjunto)

A=Conjunto(contador).A;
b=Conjunto(contador).b;
c=Conjunto(contador).c;
[x,z]=linprog(c,A,b);

i=1;while(i<=length(x))
if mod(x(i),1)~=0
P.c=c;
Q.c=c;
j=1;
v=[];
while j<=size(A,2)
v=[v,0];
j=j+1;end
P.A=[A;v];
P.A(size(A,1)+1,i)=1;
P.b=b;
P.b=[P.b;floor(x(i))]
P.b

Q.A=[A;v];Q.A(size(A,1),i)=-1;
Q.b=b;
Q.b=[Q.b;-ceil(x(i))]
Q.b
break
else i=i+1;
end
end
q=1;
K=0;
while q<=length(x)if mod(x(q),1)~=0
K=K+1;
end
q=q+1;
end
if z<incumbente
P.b
P.A

[j,k,l]=linprog(P.c,P.A,P.b);
[o,p,q]=linprog(Q.c,Q.A,Q.b);if (l~=-2 && q~=-2)
Conjunto(total+1).A=P.A;
Conjunto(total+1).b=P.b;
Conjunto(total+1).c=P.c;
Conjunto(total+2).A=Q.A;Conjunto(total+2).b=Q.b;
Conjunto(total+2).c=Q.c;
total=total+2;
end

if (l==-2 && q~=-2)
Conjunto(total+1).A=Q.A;
Conjunto(total+1).b=Q.b;Conjunto(total+1).c=Q.c;
total=total+1;
end

if (l~=-2 && q==-2)
Conjunto(total+1).A=P.A;
Conjunto(total+1).b=P.b;
Conjunto(total+1).c=P.c;
total=total+1;end
contador=contador+1
length(Conjunto)
if (z<incumbente && K==0)
incumbente=z;
xincumb=x;
end
end
end
end
tracking img