Metodo simplex

MÉTODO SIMPLEX

Ejemplo de Simplex:
Vamos a resolver el siguiente problema:

Maximizar Sujeto a:

Z = f(x,y) = 3x + 2y 2x+ y ” 18 2x + 3y ” 42 3x + y ” 24 x•0,y•0

Se consideran los siguientes pasos:

Convertir las desigualdades en igualdades

Se introduce una variable de holgura por cada una de las restricciones, este caso n, s, h para convertirlas en igualdades y formar elsistema de ecuaciones estandar. Usando en simplex el siguiente criterio: Signo: Introducir
(Letra para variable de holgura Ej: h)

”

Forma estandar:

2x + y + n = 18 2x + 3y + s = 42 3x + y + h = 24

Igualar la función objetivo a cero y despues agregar la variables de holgura del sistema anterior

Z-3x-2y=0 Para este caso en particular la funcion objetivo ocupa la ultima fila del tablero,pero de preferencia siempre se devera de colocar como la primer fila Cuando minimizamos se toma el valor (+) positivo de Fo para convertirlo en negativo y cuando maximizamos tomamos el valor (+) negativo de Fo para convertirlo en positivo.

Escribir el tablero inicial simplex

‡ En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes de las igualdadesobtenidas, una fila para cada restricción y la última fila con los coeficientes de la función objetivo:

Tablero Inicial Base Variable de decisión X y Variable de holgura Solución

n

s

h

n

2

1

1

0

0

18

s

2

3

0

1

0

42

h

3

1

0

0

1

24

Z

-3

-2

0

0

0

0

Encontrar la variable de decisión que entra en la base yla variable de holgura que sale de la base

Para escoger la variable de decisión que entra en la base, (FLECHA ROJA PARTE SUPERIOR), observamos la ultima fila, la cual muestra los coeficientes de la función objetivo y escogemos la variable con el coeficiente más negativo (en valor absoluto). En este caso, la variable x de coeficiente - 3. Si existiesen dos o más coeficientes iguales condiciónanterior, entonces se elige cualquiera de ellos. que cumplan la

Si en la última fila no existiese ningún coeficiente negativo, significa que se ha alcanzado la solución óptima. Por tanto, lo que va a determinar el final del proceso de aplicación del método del simplex, es que en la última fila no haya elementos negativos. La columna de la variable que entra en la base se llama (en colorazulado). columna pivote

Para encontrar la variable de holgura que tiene que salir de la base, (FLECHA ROJA COSTADO IZQUIERDO) se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos loselementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y no se puede seguir. El término de la columna pivote que en la división anterior dé lugar al menor cociente positivo, el 3, ya 8 es el menor, indica la fila de la variable de holgura que sale de la base, h. Esta fila se llama fila pivote (en color azulado).

Iteración No. 1 Base Variable de decisión Variable deholgura Solución Operación

x

y

n

s

h

n s h Z

2 2 3 -3

1 3 1 -2

1 0 0 0

0 1 0 0

0 0 1 0

18 42 24 0

18/2 = 9 42/2 = 21 24/3 = 8

Si al calcular los cocientes, dos o más son iguales, indica que cualquiera de las variables correspondientes pueden salir de la base.

En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3,este indica que la variable de decisión X entra y la variable de holgura h sale.

Encontrar los coeficientes para el nuevo tablero de simplex.

Los nuevos coeficientes de la fila pivote se obtienen dividiendo todos los coeficientes de la fila por el pivote operacional ³3´, ya que este se debe convertir en 1. A continuación mediante la reducción gaussiana hacemos ceros los restantes términos...