Metodo Simplex Con Matlab 5x3u19

Universidad Michoacana de San Nicolás de Hidalgo Facultad de Ingeniería Eléctrica Métodos Numéricos Proyecto 2:

8.- Visualización gráfica del método Simplex.

En este proyecto se deberá implementar un programa que resuelva mediante el método gráfico el problema de optimización con restricciones en el caso bidimensional: Maximizar z = c x con respecto a las variables de decisión x , sujeto a: A x = b , x ≥ 0 Dónde:

x  x =  1,  x2 

 a11 a12   b1  a  b  a22  2 A =  21 , c = [ c1 c2 ] b =    ... ...   ...       am1 am 2  bm 

Programa

A continuación mostramos un código meramente grafico para poder hallar la solución mediante la visualización y criterio del que lo está manejando. function simplex_graphic(A,b,c,direccion) %Método Simplex gráfico para resolver el problema de maximizar z=c*x sujeta %a A*x<=b % %Donde: %- A = Matriz de la parte A del sistema de restricciones: % * A=[a11,a12,...,a1n;a21,a22,...,a2n;am1,am2,...,amn] %- b = Vector columna de la parte b del sistema de restricciones: % * b=[b1;b2;...;bm] % %- c = Vector de la parte c del sistema del problema a resolver: % * c=[c1,c2,...,cn] %- direccion = Vector columnna de las igualdades o desigualdades del sistema % de restricciones: % * direccion=['==';'<=';'~=';'<'] (Por ejemplo) % %Da como resultado una grafica donde se muestran las soluciones posibles

%soluciones de una a una haciendo clic en la tecla 1 para que así el % pueda elejir la que mas le convenga. [m,n]=size(A); if n~=2 string='El problema es solo para dos variables'; mfgbox(string,'ErrorWindow','Help'); return end A=[A, eye(m)]; n=n+m; vertices=corner1(A,b); if length(vertices)==0 error('No existe region factible'); end vertices=vertices(1:2,:); vertices=deleteCol1(vertices); d=corner1([A;ones(1,n)],[zeros(m,1);1]); if length(d)>0 error('Noexiste region factible acotada'); end x1=vertices(1,:); x2=vertices(2,:); k=convhull(x1,x2); hold on; fill(x1(k),x2(k),[0.7 0.7 0.7]); xlabel('x_1','FontSize',15); ylabel('x_2','FontSize',15); z=c*vertices; z0=max(z); [~,nvert]=size(vertices); %xmax=max(vertices(1,:)); xmin=min(vertices(1,:)); for j=1:nvert clc; x0=vertices(1,j); y0=vertices(2,j); if c(1)*c(2)~=0 x=[0.7*x0,1.3*x0]; y=y0+(-c(1)/c(2))*(x-x0); plot(x,y,'r--','LineWidth',2); end title(['Región de solución factible, con z=',num2str(z0)],'FontSize',15) text(x0,y0,[' (',num2str(x0),',',num2str(y0),')'],'Fontsize',15) plot(x0,y0,'o',... 'MarkerEdgeColor','k',... 'MarkerFaceColor','r',... 'MarkerSize',5) grid on respuesta=input('\n-Presione la tecla 1 para mostrar el siguiente vertice\n-Presione la tecla 0 para salir\n(De lo contrario dará error)\nRespuesta: '); switch(respuesta); case 1 case 0 break end

end display('Se ha alcanzado el numero máximo de posibles soluciones (elija uno)') display('Se recomienda la que coincida con la sol factible mostrada al evaluar') end

El anterior código requiere de unas funciones externas las cuales llama dentro de él, que son las siguientes: function puntos=corner1(A,b) %Puntos extremos [m,n]=size(A); puntos=[]; if n>=m combin=nchoosek(n,m); %Coeficientes binomiales v=nchoosek(1:n,m); for k=1:combin y=zeros(n,1); x=inv(A(:,v(k,:)))*b; if all(x>=0 & (x~=inf & x~=-inf)) y(v(k,:))=x; puntos=[puntos y]; end end else error('Número de ecuaciones es > número de variables'); end puntos puntos=deleteCol1(puntos); end

y function puntos=deleteCol1(puntos) %Borra columnas repetidas [nn,L]=size(puntos); v=[]; for i=1:L-1 for j=i+1:L x=puntos(:,i); y=puntos(:,j); if all(x==y) v=[v,j]; end end end puntos(:,v)=[]; end

Para el problema ejemplo visto en clase (gasera), cuyos datos de entrada son los siguientes: >> A=[7 11;10 8;1 0;0 1] A = 7

11

10

8

1

0

0

1

>> b=[77;80;9;6] b = 77 80 9 6 >> c=[150 175] c = 150

175

>> direccion=['<=';'<=';'<=';'<='] direccion = <= <= <= <=

De esta manera el resultado que arroja es la visualización gráfica:

EL problema se resolvió mediante la localización los vértices del polígono dando así las coordenadas del mismo y mostrándolo de manera gráfica para que el determine cuál es la región factible del máximo incremento de Z, aun así en el programa implementamos el valor de z de máximo crecimiento, localizado en uno de los puntos anteriormente descritos.

Lo mismo sucede con el siguiente problema.

Segundo problema: Una fábrica de bibliotecas metálicas y combinadas con madera, utiliza 3 procesos en su producción: cerrajería, carpintería y pintura, cada proceso requiere 72, 50 y 40 horas respectivamente, producir una biblioteca metálica requiere 3 horas de cerrajería, 1 hora de carpintería y 1.5 horas de pintura, la biblioteca combinada de madera requiere de 1 hora de cerrajería, 2 horas de carpintería y una de pintura. Si la utilidad que produce una biblioteca metálica es de $50 y una combinada de madera es de $80. ¿Cuántas bibliotecas debe producir la fábrica para generar la máxima ganancia? Proceso Cerrajería Carpintería Pintura Utilidad

(x1) Metálica 3 1 1.5 $50

(x2) Combinada 1 2 1 $80

Función Objetivo Z=50x1 + 80x2 Restricciones 3x1 + x2 ≤ 72 x1 + 2x2 ≤ 50 1.5 x1 + x2 ≤ 40 Además x1 ≤0 y x2 ≤0 Para Z le damos un valor cualquiera ejemplo 3000 3000 = 50x1 + 80x2 Implementamos los datos de entrada: >> A A = 3.0000

1.0000

Horas disponibles 72 50 40

1.0000

2.0000

1.5000

1.0000

>> b b = 72 50 40 >> c c = 50

80

De esta manera el resultado que arroja es la visualización gráfica:

Conclusiones En base a lo visto en el salón, el código utilizado en este proyecto es diferente al pseudocódigo proporcionado debido a que la diferencia es que el utilizado en el salón de clases muestra la solución numéricamente y este implementado lo hace de manera gráfica, como se describió en la descripción del proyecto. Cabe mencionar que fue armado mediante búsquedas y ayudas en internet y mejorando las mismas, así como un código base al cual le hicimos adaptaciones para que se apegara a los requisitos del proyecto y lo cual resulto satisfactoriamente.

Comentarios: Profesor el pseudocódigo visto en clases no pudimos adaptarlo a Matlab por eso nos vimos en la necesidad de hacerlo de manera diferente para cumplir con las expectativas del proyecto, de igual forma es la forma en que se pide al inicio del enunciado en el proyecto 8 “se deberá implementar un programa que resuelva mediante el método gráfico” .