Deja un comentario

Método Simplex

Para comprender el funcionamiento de este tema basta con recordar el método gráfico, el cual se iban buscando esquinas del grafico hasta llegar la solución óptima. El método simplex se basa en ir buscando esquina por esquina a fin de encontrar  el punto esquina optimo, pero al contrario del método grafico este se logra mediante un proceso algebraico, no obstante es necesario convertir cada restricción de desigualdades a igualdades con el objetivo de manipular estas ecuaciones de forma sistemática.

Conversión de desigualdades a igualdades:

Sean las desigualdades:

Para la primera desigualdad,  representa un valor más pequeño o igual que 8, por lo tanto si quisiéramos convertir  esta desigualdad en igualdad deberíamos sumar un valor de holgura (denotada usualmente como ) que represente el número necesario para llegar a 8, de esta manera si  tomara un valor de 3 y un valor de 2 el valor de holgura será 3. La primera restricción se transforma como sigue:

Para la segunda restricción,   representa un valor más grande o igual a 5 por lo tanto se debe buscar un valor de holgura que le reste a la desigualdad y llegue al valor de 5, por ejemplo si  vale 4 y  tiene un valor de 6 el número de holgura será 3 de manera que cuando restemos el valor de holgura llegue al valor de 5. La segunda ecuación queda como sigue:

Siguiendo con nuestro tema, tomaremos un ejemplo en particular e iremos describiendo paso a paso la solución del problema.

Supondremos el siguiente caso:

Maximizar:

Sujeto a:

Como se vio anteriormente las restricciones tomaran el valor de:

Y la función objetivo tomara la forma:

Si reordenamos en una tabla las restricciones y la función objetivo tomaría la siguiente forma:

Se denominara las posibles variables de entrada a todos los valores de  la fila z como sigue:

Cuando se trata de maximizar se debe seleccionar el valor más negativo, en este caso será -2 y posteriormente se debe seleccionar la respectiva columna (columna pivote):

Para la última tabla se le ha agregado una columna (razón, denotada a menudo como  ) este indica la razón entre  el número de la columna “resultado” y el posterior numero de la columna pivote (Obviando la columna z), en forma más grafica el procedimiento para hallar la razón se hace del siguiente modo:

El segundo paso es hallar la fila pivote, y este se hace seleccionando el valor más pequeño positivo en la columna “razón” (variable de salida), en este caso será el 5, y posteriormente seleccionando toda la fila:

Normalmente se dividiría toda la fila pivote por el número sombreado en rojo, pero esta vez no es necesario, puesto que tiene valor 1, y por ende cada división resultaría el mismo número.

El tercer paso se basara en transformar toda la columna pivote en cero, a excepción del numero tocado por la fila pivote. Para este procedimiento se usa el método gauss, el cual se detallara a continuación:

Para transformar la columna R1 en forma adecuada se usa la siguiente ecuación:

Esto indica que cada cuadro de la columna  deberá ser restado por el respectivo valor de , así cuando se transforme el número de la columna pivote este tome el valor de cero:

Igualmente el valor de Z será transformado con la ecuación:

Para una mayor comprensión hacia el lector se detallara los procesos para la ecuación anterior:

En general la columna nueva será el valor de la columna antigua menos el número pivote de la columna multiplicado por el número de la fila pivote.

La grafica final queda como sigue:

Para este sistema ya no es posible encontrar una solución más óptima, esto es porque los valores de  y  en la fila z son cero, por lo tanto el valor de z será 10, x1 será 0 (esto es porque la columna x no puede ser transformada en valores de cero) y x2 será igual a 5.

Transformar las desigualdades

Es posible a veces manipular las desigualdades de tal manera que se transformen en desigualdades “<=”  por ejemplo se tienen la ecuación:

Es posible transformar esta desigualdad multiplicando cada miembro por -1:

Posteriormente es posible transformar un problema de minimización a maximización multiplicando cada variable por -1, por ejemplo se tiene la función objetivo:

Es posible transformar esta función objetivo de la siguiente forma:

Es muy usual hacer este tipo de procedimientos cuando se tiene mucha más experiencia haciéndolo de la forma maximizar con restricciones de desigualdad <=.

Método de la gran M

Supongamos el siguiente problema:

Minimizar:

S.A:

Si reordenamos las restricciones de la forma común, tomaría la forma:

Para el reglón 1, si se multiplicara por -1 la variable de holgura podría tomar valores negativos, y violaría la restricción . Es por eso que para este tipo de problema se le asigna una variable artificial (a), de tal manera que su valor sea lo suficientemente alto para no convertir s1 en un número negativo.

De una forma similar pasara con el reglón 3, si se multiplicara esta por -1 tanto x como y podrían tomar valores negativo, y por consiguiente se le debe agregar una variable artificial

Las restricciones quedaran como sigue:

Desafortunadamente no hay garantía para que las últimas restricciones tengan los mismos resultados que se piden en el enunciado. Puede existir la posibilidad de que se consiga algún valor a  en el resultado final. Para solucionar este problema se hace lo siguiente:

La M agregado representan valores extremadamente grandes por lo tanto si se trata de minimización los valores serán iguales a cero, y el resultado final serán iguales a los que se piden en el problema primero

Reordenando la función objetivo quedará como sigue:

En tabla la función objetivo y las restricciones tomara la siguiente forma:

Antes de seguir nuestro estudio miraremos un último problema:

Si la columna z tiene un resultado final de 0 las variables z, x, y tomarían valores de cero también, por consiguiente en el reglón R1 por ejemplo los valores de a1+a2 seria 4, por ende toda la tabla seria inconsistente. Para solucionar este problema se transforma cada una de las M en cero utilizando el método gauss, la formula a utilizar será:

La tabla modificada será:

En este punto ya es posible proceder con el método gauss ordinario, pero tratándose de minimización se buscara el valor más positivo en la columna Z, el cual resulta 3M-2

De igual manera se selecciona la variable de salida como el valor más pequeño de la razón de la fila “total” con la fila “x” (en este caso seria 1), posteriormente la columna pivote será las casillas consecutivas a este. La tabla 6 muestra la columna y fila pivote sombreadas en azul.

El ejercicio continúa normalmente como se mostró en el primer ejemplo, recordando que:

  • Ha de tener en cuenta que este es un ejercicio de minimización por ende la variable de entrada será el de valor más positivo, pero a su vez solo se deben tener en cuenta las variables del problema y no las holguras o los valores artificiales.
  • Se llega al óptimo cuando los valores de zx y zy son cero o mayores a este.

El resultado final será:      

Como ayuda al lector se ha especificado que se debe hacer con los diferentes criterios de decisión en la siguiente tabla:


Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

Únete a otros 28 seguidores

%d personas les gusta esto: