Algoritmo del simplex

El algoritmo o método del simplex es un método genérico de solución de problemas lineales, desarrollado por George Dantzig en 1947.

Se trata de un modelo matemático utilizado para optimizar la gestión del subsistema productivo.

Introducción

A través de este método se desarrollará un procedimiento de cálculo que permita, de entre la variedad de productos que la empresa puede producir, seleccionar cuáles producir y cuánto producir, de tal forma que permita a la empresa alcanzar el óptimo de su función objetivo.

Es necesario tener en cuenta la existencia de todo tipo de restricciones (financieras, legales, tecnológicas, comerciales, de abastecimiento…) que en el mundo de la economía condicionarán a la empresa.

Debido a esta última consideración nos enfrentaremos a problemas de óptimos condicionados, donde buscaremos un máximo o un mínimo de la función objetivo, respetando unas determinadas condiciones.

Por tratarse de un modelo de programación lineal se ha de trabajar con funciones de tipo lineal, sometidos a restricciones también de carácter lineal. Suponer relaciones lineales entre las variables es admitir que, al variar la producción, varía linealmente (proporcionalmente) el beneficio, los ingresos y el coste. Esto implica que tanto el precio como los costes variables unitarios son constantes. Es necesario tener en cuenta que esta última hipótesis sólo puede mantenerse en el corto plazo, por lo que el modelo sólo es válido para planificar la producción a corto plazo.

Planteamiento del modelo matemático

Función objetivo

Expresión matemática de aquello que se pretende maximizar o minimizar.

X_j: Cantidad del producto “j” a fabricar. Son las denominadas variables de decisión.

C_j: Contribución a la función objetivo al utilizar el proceso productivo “j” a nivel unitario. Impacto sobre la función objetivo por cada unidad producida del producto “j”.

Restricciones

Expresión matemática de las limitaciones a las que se encuentra sometida la función objetivo.

a_ij: Coeficientes técnicos. Cantidad del recurso “i” necesario para producir una unidad del producto “j”

b_i: Cantidad del recurso “i” disponible.

Planteamiento

Función objetivo

OPTIMIZAR Z = C₁ X₁ + C₂ X₂ + … + C_j X_j + … + C_n X_n

Restricciones

Planteamiento matricial

Forma de la tabla para la resolución del problema

Las variables básicas en su intersección conforman la matriz identidad.

Las Tasas físicas de sustitución son coeficientes que colocados debajo de cada variable no básica en su intersección con las básicas indican:

• si la TFS es positiva indica en cuánto disminuye el valor de la variable básica por cada unidad de valor que tiene la variable no básica.
• si la TFS es negativa indica en cuánto aumente el valor de la variable básica por cada unidad de valor en la variable no básica.

Los rendimientos indirectos se calculan para todas las variables del problema y su valor se obtiene sumando el valor de la TFS del valor que se trate más los respectivos valores (C_j) de la variable básica.

Los rendimientos netos representan el impacto neto que se produce en la función objetivo, aumento o disminución de su valor, por un aumento de una unidad en el valor de cada variable.

Proceso de cálculo para problemas de maximización

Fase I. Preparar el modelo inicial para construir la tabla

1) Transformar los términos independientes en positivos (multiplicando por -1).

2) En las inecuaciones en las que encontramos ≤ introducimos una variable de holgura (H) sumando.

3) En las inecuaciones en las que encontramos ≥ introducimos una variable de holgura restando y además una variable de excedente (F) sumando para que en dicha restricción haya un proceso unitario positivo.

4) En las igualdades se introduce una variable de excedente (F) sumando si en la misma no existe una variable unitaria positiva.

5) En toda restricción debe haber una variable unitaria positiva.

6) Las variables de holgura (H), a la hora de introducirlas en la función objetivo lo haremos siempre con coeficiente cero, y las variables de excedente (F) se introducen con el coeficiente –m si estamos maximizando o m si estamos minimizando.

7) Igualar a cero la función objetivo

Fase II. Construir la tabla y resolver el algoritmo

Paso 1: Construir la tabla del método Simplex y rellenamos la tabla con los coeficientes. Comprobamos que las variables básicas tienen un coeficiente de 1 en la intersección de su renglón y columna correspondiente y cero en los demás renglones incluido la función objetivo.

Paso 2: La solución es óptima, si y sólo si todos los coeficientes del renglón C_j - Z_j son negativos o cero. De lo contrario se debe iterar.

Paso 3: Si comprobamos que hay coeficientes positivos en el renglón C_j - Z_j, marcamos el mayor en valor absoluto y esta será la variable no básica que entra a la base.

Para determinar la variable básica que sale de la base, marcamos la columna debajo del coeficiente de la variable que entra y se le da el nombre columna pivote.

Aplicamos la prueba del cociente mínimo para determinar cuál es la variable básica que sale.

• Elegimos los coeficientes de la columna pivote positivos

• Se divide cada coeficiente del lado derecho entre los coeficientes de la columna pivote

• Se identifica el renglón con la menor razón

La variable básica para este renglón es la que sale y se le da el nombre de renglón pivote. La intersección entre la columna pivote y el renglón pivote lo denominamos número pivote. El patrón de coeficientes en la columna de la variable que entra en la base, debe quedar como actualmente está el patrón de coeficientes de la variable que sale.

Paso 4: Calculamos los nuevos coeficientes de la matriz:

• Coeficientes del renglón de la variable que entra: Dividimos el renglón pivote entre el número pivote y el resultado serán los coeficientes del nuevo renglón de la variable que entra.

• Coeficientes de los demás renglones : Dividimos el nuevo renglón de la variable que entra por menos el coeficiente del de la variable que entra en el renglón que estamos calculando y al resultado, le sumamos el renglón que teníamos inicialmente

Paso 5: Construimos la tabla con los resultados.

Paso 6: En la nueva matriz, comprobamos los coeficientes del renglón C_j - Z_j, si todavía existen coeficientes positivos, se sigue iterando, de lo contrario hemos terminado y hallamos la solución óptima.

Proceso de cálculo para problemas de minimización

El proceso es idéntico al descrito anteriormente. Únicamente es necesario tener en cuenta que en este caso nos encontraremos ante una solución no óptima cuando en el renglón C_j - Z_j encontremos algún valor negativo y saldrá de la tabla aquel que presente un mayor valor negativo.