Método Simplex

Método Simplex. Concepto: Uno de los Métodos de Solución de la Programación Lineal.

MétodoSimplex: se basa en un procedimiento algebraico y la explicación geométrica del mismo se puede interpretar a través del método gráfico.

Conceptos Básicos del Método Simplex

• La aplicación del método simplex presupone que se tiene un sistema de restricciones lineales formado sólo por ecuaciones lineales. Esta transformación puede ser llevada a cabo de una forma muy simple introduciendo algunas variables adicionales, las cuales se denominan variables de holgura. Estas variables se definen una para cada restricción y si la misma tiene el signo ≤ la variable de holgura se adiciona y el signo fuera ≥ la variable de holgura se restara.
• Luego que se tiene un problema de Programación Lineal estándar, es decir, todas las restricciones tienen signos de igualdad es necesario determinar la solución básica factible inicial (S.B.F.I).
• Dado un sistema de m ecuaciones lineales con n variables (AX=b) con m<n y rango r(A)=m. Si escogemos cualquier matriz no singular de orden mxm y si todas las (n-m) variables no asociadas con estas columnas de la matriz son iguales a cero, entonces la solución al sistema de ecuaciones resultante es llamada una solución básica. Como la matriz A consta de n columnas se puede definir la matriz B formada por m columnas linealmente independientes de A, esta matriz la llamaremos matriz básica. Con las (n-m) columnas restantes de A se puede construir otra matriz que se denominará matriz no básica y la denotaremos por W. Entonces puede escribirse la matriz A de la siguiente manera: A = (B, W).
• Las variables que forman parte de la matriz B se llaman variables básicas (XB) y las que forman parte de la matriz W se llaman variables no básica.( XW ), entonces el vector X está conformado por el conjunto de variables básicas y no básicas, es decir, X = (XB, XW).
• Entonces el sistema de restricciones del problema de Programación Lineal AX=b puede escribirse de la forma siguiente: AX=BXB + WXW = b. Si asumimos que las variables no básicas tomarán valor cero, la expresión anterior quedaría BXB =b. La expresión XB = B-1 b que se obtiene a partir de la anterior, permitiría calcular la solución básica factible inicial.

Para realizar la Tabla del Método Simplex

El método simplex se desarrolla en la tabla simplex. Cada iteración requiere de una tabla.

En la primera columna se escribirán los coeficientes de la función objetivo correspondiente a las variables básicas, escribiendo en la segunda columna dichas variables. La tercera columna indica los valores que toman las variables básicas en la solución que se está representando mediante la tabla simplex. El resto de la columnas representan los vectores Pj correspondientes a cada uno de los vectores aj de la matriz A (Pj es el vector coordenado de cada vector aj respecto a la base considerada). En la última fila de la tabla aparecen los valores Zj -Cj correspondiente a cada vector aj. Los coeficientes Zj se determinan utilizando la siguiente expresión: Zj =CBPj

Procedimiento computacional del Método Simplex

El procedimiento iterativo en que se basa el método simplex puede resumirse en los siguientes pasos:

• Paso1: Convertir las inecuaciones en ecuaciones con la utilización de las variables de holgura.
• Paso 2: Determinar la solución básica factible inicial XB*, los valores Z*, Pj y Zj - Cj y construir la tabla simplex que resuma toda la información sobre esta solución inicial. La solución básica inicial debe tener la característica de que la matriz básica debe ser unitaria. Esto facilita el cálculo de la matriz inversa.
• Paso 3: Examinar en la tabla simplex los valores de los coeficientes Zj – Cj.

Pueden presentarse las siguientes situaciones: Caso Máximo y Caso Mínimo.

Caso Máximo

• Todos los Zj – Cj ≥ 0. En este caso se ha alcanzado la solución óptima. (criterio de optimalidad)
• Uno o más Zj – Cj < 0.En este caso debe calcularse una nueva solución básica determinando el vector ak que entra en la base mediante la siguiente expresión:

ZK –CK = MIN (Zj – Cj) para todos los aj con Zj – Cj < 0 (1)

Si para uno o más vectores se obtienen ese valor mínimo puede escogerse cualquiera como vector entrante. Una vez escogido el vector ak pueden presentarse dos casos:

• Caso 1: Los valores Pik≤0 para cada i. Esto indica la existencia de una solución no acotada.
• Caso 2: Se tiene Pik > 0 para al menos una i. En este caso puede hallarse una nueva solución básica en la cual el valor de Z mejore o sea el óptimo.

Caso Mínimo

• Todos los Zj – Cj ≤ 0. En este caso se ha alcanzado la solución óptima. (Criterio de optimalidad)
• Uno o más Zj – Cj > 0.En este caso debe calcularse una nueva solución básica determinando el vector ak que entra en la base mediante la siguiente expresión (1).

Paso 4:Si se tiene que Pik > 0 para al menos una i, se determina el vector que sale mediante la expresión:

Θ = XBr / Prk = MIN {X*Bi/ Pik, Pik > 0}

Debe extraerse de la base el vector ar siendo reemplazado por el vector ak. Si para 2 o más vectores se obtienen el mismo valor de Θ puede escogerse cualquiera como vector saliente.

Paso 5: Se calculan los nuevos valores XB, Z, Pj y Zj- Cj insertando dichos valores en la nueva tabla simplex. Una vez concluido este paso, se retorna al paso 3 repitiendo el procedimiento hasta que se alcance la solución óptima.

Fuente

• Felipe Pilar y otros. Programación Matemática I. Pag. 40-68.
• .Portela Silva José M. Vladimir Kuzmich. Modelo Económico Matemático I, pág. 1-19.
• Gallagher,Charles A. Watson, Hugh J. Métodos Cuantitativos para la toma de decisiones. Pág. 156-166.
• Anderson David R., Dennis J. Sweeney, Thomas A. Willians. Introducción a los modelos cuantitativos para Administración. Pág.29.