Metodo simplex

Método Simplex

Capítulo 5 Método Simplex

Cj V.B. b 5 X1 13/9 3 X3 14/9 -2 X2 1/3 Zj - Cj 101/9

5 X1 1 0 0 0

-2 X2 0 0 1 0

3 0 -M 0 0 b/a X3 X4 X5 X6 X7 0 -4/15 4/15 7/45 4/45 NO 1/15 1 -1/15 2/45 14/45 70/3 0 -3/15 3/15 -2/15 1/15 NO 0 -11/15 M+11/15 53/45 56/45

Introducción El método algebraico es muy dispendioso, en razón a que trabaja con todos los datos de las ecuaciones,para mejorar éste aspecto se creó el método simplex cuya gran virtud es su sencillez, método muy práctico, ya que solo trabaja con los coeficientes de la función objetivo y de las restricciones. Ilustraremos su funcionamiento mediante un ejemplo, pero previamente mostraremos las reglas de decisión para determinar la variable que entra, la que sale, la gran M, y cómo determinar que estamos en elóptimo; Todas éstas reglas de decisión fueron deducidas del método algebraico, solamente que aquí se han acomodado para ser usadas en el tipo de tablero simplex que se usará. Criterio de decisión Gran M en la función objetivo Variable que entra Variable que sale Solución óptima Maximizar - MXj Minimizar +MXj

La más negativa de los Zj - Cj La más positiva de los Zj - Cj La menos positiva de los b/a ,La menos positiva de los b/a , Siendo a > 0 , de lo contrario Siendo a > 0 , de lo contrario no restringe no restringe a la variable que entra Cuando todos los Zj – Cj > 0 Cuando todos los Zj – Cj < 0

Adicionalmente se presentan las siguientes notas a tener en cuanta:

83

Método Simplex • Si en el tablero simplex de la solución óptima queda al menos una variable de Super avit óartificial dentro de las variables básicas, con un valor > 0 , el problema no tiene solución, esto quiere decir que al menos existen dos restricciones excluyentes, por lo tanto no existe área de soluciones factible y menos una solución , en éste caso se debe revisar la formulación del problema. Si al escoger la variable que sale, ninguna de las variables básicas restringe el crecimiento de la variable nobásica escogida para entrar, el problema tiene solución indeterminada y se debe revisar la formulación en busca de una nueva restricción que no se tuvo en cuenta en la formulación inicial. Si en el tablero simplex del óptimo, al menos una de las variables no básicas tiene coeficiente cero (0) en la función objetivo, esto es su Zj – Cj = 0, el problema tiene múltiples soluciones y se nos estáofreciendo una de ellas.

•

•

Ejemplo 1 Maximizar Z = X1 + X2 C.S.R. 5X1 + 3X2 < 15 3X1 + 5X2 < 15 Xj > 0 ; j = 1, 2 Todo problema de programación lineal que se formule de la forma Maximice, con todas sus restricciones < y con la condición de no negatividad, se le llama Forma Estándar ó Forma Normal

Aquí, al igual que en el método algebraico, debemos conseguir una solución básica factible,empleando las variables de holgura y/o artificiales, quedando el sistema de ecuaciones así: Maximizar Z = X1 + X2 C.S.R. 5X1 + 3X2 + X3 = 15 3X1 + 5X2 + X4 = 15 Xj > 0 ; j = 1,2,3,4 Las variables básicas son X3 y X4 y por su puesto en la función objetivo Z. Este ejercicio es el ejemplo 1 del capitulo de método algebraico. Compare los resultados entre los dos métodos.

A continuación construimos lasiguiente tabla: Cj → 1 1 0 0 b/a ↓ V.B. b X1 X2 X3 X4 0 X3 15 5 3 1 0 0 X4 15 3 5 0 1 Zj - Cj 0 -1 -1 0 0

El valor de la función objetiva Z, se encuentra frente a la casilla de Zj – Cj , en éste caso vale cero (0) y se calcula multiplicando el vector fila (en la tabla es la columna inmediatamente anterior a la de las variables básica V.B.) que contiene los coeficientes de 84

Método Simplexlas variables básicas en la función objetiva original por el vector columna de los términos independientes b CXB = Vector fila de los coeficientes en la función objetivo original de las variables básicas actuales, sus valores se encuentran en la primera columna del tablero. b = Vector columna de los términos independientes de las restricciones, que al mismo tiempo son los valores de las...