El método gráfico para resolver problemas de programación lineal tiene una particularidad, solo aplica para resolver problemas con dos variables de decisión. Sin embargo, los problemas cotidianos de programación lineal que se enfrentan regularmente los especialistas en IO, involucran un número mayor de variables y a veces compuestos de cientos de restricciones por lo que es necesario auxiliarse de programas computacionales, basados en el algoritmo Símplex, para la solución de los mismos.
Para la aplicación del algoritmo Símplex se transforma el modelo de programación original, formado por restricciones funcionales de desigualdad, en un modelo de forma estándar, integrado por restricciones de igualdad equivalentes. Esta conversión se logra con la introducción de variables de holguras y/o superávit.
Variables de holgura. Aplica para las restricciones del tipo (<=), donde el lado derecho de la desigualdad representa el limite sobre la disponibilidad de un recurso y el lado izquierdo representa la utilización de ese recurso limitado que hacen las variables del modelo. Esto quiere decir que una holgura representa la cantidad disponible del recurso que excede a la utilización que se le da. En la conversión de este tipo de desigualdad se añade una variable de ajuste (Xi o Hi) para convertirla en igualdad. Por ejemplo, tenemos la siguiente restricción: 3X1 + 2X2 <= 6, su equivalente seria, 3X1 + 2X2 + X3 = 6.
Variables de superávit. Aplica para las restricciones del tipo (>=), generalmente determinan los requerimientos mínimos de especificaciones. Es decir, un superávit representa el exceso minimo del lado izquierdo sobre el requerimiento mínimo de la restricción. En la conversión de este tipo de desigualdad se resta una variable de ajuste (Xi o Si) para convertirla en igualdad. Por ejemplo, tenemos la siguiente restricción: X1 + 3X2 >= 5, su equivalente seria, X1 + 3X2 - X3 = 5.
La solución del algoritmo Símplex se puede realizar de forma algebraica o de forma tabular. Para los fines de este apartado se explicará el desarrollo del algoritmo en su forma tabular. Antes de iniciar, se deben plantear algunos conceptos importantes: variables básicas, variables no básicas, solución básica factible, variable de entrada, variable de salida, iteración, condición de optimalidad (criterio de entrada) y condición de factibilidad (criterio de salida).
La forma estándar de un problema de programación lineal se compone de m ecuaciones lineales simultaneas en n incógnitas o variables, donde m es menor que n (m < n). Este conjunto de variables se puede segmentar en dos grupos: (1) m - n variables, a las cuales se le asigna un valor cero y (2) las restantes m variables, cuyos valores se determinan resolviendo las m ecuaciones resultantes. Si la m ecuaciones conducen a una única solución, estas variables se denominan variables básicas y las n - m restantes variables se les llaman variables no básicas.
En el inicio de un algoritmo Símplex, se consideran todas las variables de holguras y ficticias adicionadas en la forma estándar, con valores cero, procedimiento que se denomina solución básica factible inicial. Se denomina una solución básica factible si las m variables básicas son no negativas (>= 0). Si cualquiera de estas m variables es igual a cero se considera un solución BF degenerada. Después se trata de encontrar otra solución básica factible que mejorará el valor del objetivo, proceso denominado iteraciones. Para que una variable cero actual se convierta en positiva, debe eliminarse una de las variables basicas actuales, es decir, volver esta última no básica a nivel cero. Esto introduce dos conceptos, la variable cero seleccionada es la variable de entrada y la variable básica eliminada es la variable de salida.
Condición de optimalidad. La variable de entrada en un problema de maximización es la variable no basica que tiene el coeficiente más negativo en la fila Z o función objetivo. En el caso de minimización, la variable de entrada se define como la variable no básica que tiene que tiene el coeficiente más positivo en la fila Z.
Condición de factibilidad. Tanto para los problemas de maximización como de minimización, la variable de salida es la variable básica asociada con la razón no negativa más pequeña. En caso de empates se rompen arbitrariamente y se descartan las razones negativas o indefinidas. Cuando se refiere a razón se entiende por la división de los limites del lado derecho entre los coeficientes de la columna de la variable de entrada.
La solución de un problema de PL a través del algoritmo Símplex, en su forma tabular, consiste en cálculos para encontrar una nueva solución básica fundamentados en operaciones algebraicas de la metodología Gauss-Jordan para la solución de sistemas de ecuaciones simultaneas por matrices. Donde se tiene una columna pivote (columna de la variable de entrada) y un reglón o fila pivote (variable de salida). La intersección de estos dos constituyen el elemento pivote, que el la tabla se lleva a la unidad (valor 1).
Los cálculos del método Símplex son iterativos, es decir, se aplican condiciones y cálculos fijos a la tabla Símplex actual para producir la siguiente tabla. Por tanto, se denomina iteraciones a las tablas sucesivas.
Para la aplicación del algoritmo Símplex se transforma el modelo de programación original, formado por restricciones funcionales de desigualdad, en un modelo de forma estándar, integrado por restricciones de igualdad equivalentes. Esta conversión se logra con la introducción de variables de holguras y/o superávit.
Variables de holgura. Aplica para las restricciones del tipo (<=), donde el lado derecho de la desigualdad representa el limite sobre la disponibilidad de un recurso y el lado izquierdo representa la utilización de ese recurso limitado que hacen las variables del modelo. Esto quiere decir que una holgura representa la cantidad disponible del recurso que excede a la utilización que se le da. En la conversión de este tipo de desigualdad se añade una variable de ajuste (Xi o Hi) para convertirla en igualdad. Por ejemplo, tenemos la siguiente restricción: 3X1 + 2X2 <= 6, su equivalente seria, 3X1 + 2X2 + X3 = 6.
Variables de superávit. Aplica para las restricciones del tipo (>=), generalmente determinan los requerimientos mínimos de especificaciones. Es decir, un superávit representa el exceso minimo del lado izquierdo sobre el requerimiento mínimo de la restricción. En la conversión de este tipo de desigualdad se resta una variable de ajuste (Xi o Si) para convertirla en igualdad. Por ejemplo, tenemos la siguiente restricción: X1 + 3X2 >= 5, su equivalente seria, X1 + 3X2 - X3 = 5.
La solución del algoritmo Símplex se puede realizar de forma algebraica o de forma tabular. Para los fines de este apartado se explicará el desarrollo del algoritmo en su forma tabular. Antes de iniciar, se deben plantear algunos conceptos importantes: variables básicas, variables no básicas, solución básica factible, variable de entrada, variable de salida, iteración, condición de optimalidad (criterio de entrada) y condición de factibilidad (criterio de salida).
La forma estándar de un problema de programación lineal se compone de m ecuaciones lineales simultaneas en n incógnitas o variables, donde m es menor que n (m < n). Este conjunto de variables se puede segmentar en dos grupos: (1) m - n variables, a las cuales se le asigna un valor cero y (2) las restantes m variables, cuyos valores se determinan resolviendo las m ecuaciones resultantes. Si la m ecuaciones conducen a una única solución, estas variables se denominan variables básicas y las n - m restantes variables se les llaman variables no básicas.
En el inicio de un algoritmo Símplex, se consideran todas las variables de holguras y ficticias adicionadas en la forma estándar, con valores cero, procedimiento que se denomina solución básica factible inicial. Se denomina una solución básica factible si las m variables básicas son no negativas (>= 0). Si cualquiera de estas m variables es igual a cero se considera un solución BF degenerada. Después se trata de encontrar otra solución básica factible que mejorará el valor del objetivo, proceso denominado iteraciones. Para que una variable cero actual se convierta en positiva, debe eliminarse una de las variables basicas actuales, es decir, volver esta última no básica a nivel cero. Esto introduce dos conceptos, la variable cero seleccionada es la variable de entrada y la variable básica eliminada es la variable de salida.
Condición de optimalidad. La variable de entrada en un problema de maximización es la variable no basica que tiene el coeficiente más negativo en la fila Z o función objetivo. En el caso de minimización, la variable de entrada se define como la variable no básica que tiene que tiene el coeficiente más positivo en la fila Z.
Condición de factibilidad. Tanto para los problemas de maximización como de minimización, la variable de salida es la variable básica asociada con la razón no negativa más pequeña. En caso de empates se rompen arbitrariamente y se descartan las razones negativas o indefinidas. Cuando se refiere a razón se entiende por la división de los limites del lado derecho entre los coeficientes de la columna de la variable de entrada.
La solución de un problema de PL a través del algoritmo Símplex, en su forma tabular, consiste en cálculos para encontrar una nueva solución básica fundamentados en operaciones algebraicas de la metodología Gauss-Jordan para la solución de sistemas de ecuaciones simultaneas por matrices. Donde se tiene una columna pivote (columna de la variable de entrada) y un reglón o fila pivote (variable de salida). La intersección de estos dos constituyen el elemento pivote, que el la tabla se lleva a la unidad (valor 1).
Los cálculos del método Símplex son iterativos, es decir, se aplican condiciones y cálculos fijos a la tabla Símplex actual para producir la siguiente tabla. Por tanto, se denomina iteraciones a las tablas sucesivas.
Para ejemplificar el funcionamiento del algoritmo Símplex se selecciona el problema de maximización 5.3-4 del libro de texto ubicado en las páginas 176 y 177. Este problema se compone de 3 variables de decisión y 4 restricciones.
 |
| Modelo PL Inicial Problema 5.3-4 |
 |
| Solución básica factible inicial |
 |
| Iteración 1: variable de entrada X1 y variable de salida X4 |
 |
| Iteración 2: variable de entrada X2 y variable de salida X5 |
 |
| Iteración 3: variable de entrada X3 y variable de salida X7 |
La última tabla muestra en el reglón Z que todos los coeficientes son ceros o con valores positivos. Se aplica la condición de optimalidad, encontrándose que no hay variable de entrada por lo que la solución expresada es óptima para este modelo. Con un valor objetivo Z= 525, X1 = 55/4 = 13.75, X2 = 15, X3 = 20 y una holgura con X6 = 2.5.
A modo general, el método Símplex consta de los pasos siguientes:
- Determinar una solución básica factible inicial.
- Definir una variable de entrada empleando la condición de factibilidad. El algoritmo se detiene cuando ya no hay una variable de entrada.
- Seleccionar una variable de salida empleando la condición de factibilidad.
- Determinar las nuevas soluciones básicas factibles aplicando los cálculos apropiados a través de la metodología Gauss-Jordan.
Otras variantes del método Símplex son el método de la M grande y el método de las dos fases. Ambos se aplican cuando se incorporan restricciones del tipo (<=) que implica agregar una variable ficticia para completar la matriz de identidad de las variables básicas requeridas por el algoritmo Símplex para iniciar las iteraciones.
En el método de la M grande se incorpora a la o las variables ficticias una penalidad denota por "M" cuyo valor es bastante grande (dígase >1000) en la función objetivo, luego se obliga que su valor sea cero en la solución final.
En el caso del método de la dos fases como su nombre lo indica resuelve los problemas de programación lineal en dos fases. La fase I trata de encontrar un solución inicial factible básica, de ser posible, minimizando la suma de las variables artificiales. En la fase II se utiliza la solución anterior para resolver el problema original, ya con las variables artificiales eliminadas del modelo de programación lineal.
En el método de la M grande se incorpora a la o las variables ficticias una penalidad denota por "M" cuyo valor es bastante grande (dígase >1000) en la función objetivo, luego se obliga que su valor sea cero en la solución final.
En el caso del método de la dos fases como su nombre lo indica resuelve los problemas de programación lineal en dos fases. La fase I trata de encontrar un solución inicial factible básica, de ser posible, minimizando la suma de las variables artificiales. En la fase II se utiliza la solución anterior para resolver el problema original, ya con las variables artificiales eliminadas del modelo de programación lineal.
