Metodo Simplex

Método simplex

Es un algoritmo que parte de una solución básica inicial y que va mejorando la solución a través de cada iteración hasta llegar a la óptima.

Procedimiento:
1. Formular el modelo de programación lineal.
2. Convertir el conjunto de restricciones en ecuaciones mediante la introducción de las variables de holgura, Hi; de excedente; Si, o artificial, Ai, que sean necesarias,según el criterio siguiente:
|Tipo de restricción |Tipo de variable |
|≤ |+ Hi |
|≥ |- Si + Ai |
|= |+ Ai |

3. Identificar si se configuro una matriz identidad (unidad) en el conjunto de restricciones. Si es así, se puede proceder aelaborar la primera tabla simplex.
4. Elaborar la primera tabla simplex, bajo el formato siguiente:
Cj Lado Razones
CB Base X1 X2 H1 H2 H3 derecho de prueba

Zj
Cj - Zj

donde:
✓ La base decolumna que contiene las variables que se encuentran en la diagonal principal de la matriz identidad formada en el cuerpo de restricciones. Cualquier variable que se encuentre en esta columna recibe el nombre de “variable básica”.
✓ Cj. Es el renglón que contiene los coeficientes de la variable de la función objetivo. Los coeficientes de las variables adicionales se incluyen según el criteriosiguiente:
Tipo de variable Coeficiente

H 0
S -1
A +M
✓ CB. Columna que contiene loscoeficientes que contienen las variables básicas en el renglón Cj.
✓ X1, X2, …, Xn, Hj, Sj, Aj. Columnas que contienen los coeficientes de esas variables en el conjunto de restricciones convertidas a ecuaciones.
✓ Lado derecho: Columna que contiene los términos independientes (valores del lado derecho) del conjunto de restricciones.
✓ Zj. Renglón que se forma se la suma de los productos delos elementos de la columna CB por los de cada columna Xj, Hj, Sj o Aj y lado derecho.
✓ Cj – Zj. Diferencia entre los elementos correspondientes de los renglones Cj y Zj.

5. Efectuar prueba de optimalidad. La solución es óptima cuando:
Caso de maximización: Todos los elementos del renglón Cj – Zj son negativos y/o cero.
Caso de minimización: Todos los elementos del renglón Cj – Zj sonpositivos y/o cero.
Si la solución es óptima se procede a determinarla, si no lo es, se continua con el algoritmo.
6. Determinar la variable que entra a la base:
Caso de maximización: La que tenga el mayor valor positivo en el renglón Cj – Zj.
Caso de minimización: La que tenga el valor más negativo en el renglón Cj – Zj.
7. Determinar la variable que sale de la base. Calcular en la columna”Razones de prueba” los cocientes resultantes de dividir los elementos de la columna “Lado derecho” entre los elementos correspondientes ubicados en la columna de la variable que entra, genéricamente llamada “columna pivote”. El menor cociente no negativo, diferente de cero, corresponde a la variable que sale de la base. El renglón de la variable que sale de la base recibe el nombre genérico de “renglónpivote”.
El elemento donde se cruzan la columna y el renglón pivotes recibe el nombre de “elemento pivote”.
8. Construir la siguiente tabla simplex calculando primero el renglón correspondiente a la variable que entra a la base. Se divide cada elemento del renglón pivote entre el elemento pivote. El renglón generado se llama “nuevo renglón pivote”.
Calcular los renglones restantes de las...