Concepto
Es un procedimiento algebraico (aunque sus conceptos fundamentales son geométricos) utilizado para resolver problemas de programación lineal. Este procedimiento iterativo fue propuesto por el matemático norteamericano George Dantzing en 1947.
Planteamiento del problema
Para resolver un problema utilizando el método simplex es necesario que se maximice una función objetivo lineal sujeta a restricciones lineales que pueden ser de tipo igualdad o desigualdad. De forma matricial genérica del problema se podría plantear de la siguiente forma:
Maximizar CTX (función objetivo).
Sujeto a: AX ≤ b (restricciones).
X ≥ 0 (condiciones de no negatividad).
Donde CT es el vector de los coeficientes de las variables de la función objetivo, X son las variables de decisión del problema, A es la matriz de coeficientes de las variables de las restricciones y b es el vector de términos independientes de las restricciones.
Preparación del problema para el método simplex
Para poder utilizar el método simplex, lo primero que hay que hacer es convertir las restricciones de desigualdad en restricciones de igualdad equivalentes. Para ello es necesario añadir unas variables ficticias llamadas variables holgura. El modelo equivalente, que se obtiene al añadir las variables holgura en las restricciones, se llama forma aumentada del modelo.
Si en una solución, el valor de la variable holgura es cero, entonces, esta se encuentra en la frontera de la restricción, si la variable holgura es mayor que cero, entonces, la solución pertenece al conjunto factible y, si es menor que cero la solución se encuentra en el lado no factible de la frontera de restricción.
Una vez planteado el problema en su forma aumentada es necesario obtener la solución. Pero antes de desarrollar los pasos necesarios para la obtención de la solución es necesario definir los siguientes conceptos:
- a) Solución aumentada es una solución para las variables de decisión del problema junto con los valores de las variables de holgura.
- b) Solución básica es una solución en un vértice aumentada, es decir, es una solución que contiene valores de las variables de decisión del problema y de las variables holgura. Estas soluciones básicas pueden ser factibles o no dependiendo de si el vértice pertenece o no al conjunto factible (conjunto de puntos que cumplen todas las restricciones del problema). En un problema el número de variables básicas es igual al número de restricciones del problema (sin considerar las condiciones de no negatividad). El número de variables no básicas es igual a los grados de libertad del problema.
- c) Grados de libertad del problema es la diferencia que existe entre el número de variables y el número de ecuaciones.
Pasos para resolver un problema de optimización lineal utilizando el método simplex
Paso 1. Elegir las variables no básicas e igualarlas a cero para obtener la solución básica factible inicial. Se comprueba si, en esta solución, la función objetivo alcanza su valor máximo. La solución no será optima si al moverse en cualquier dirección o si al aumentar cualquier variable no básica el valor de la función objetivo aumenta. Por lo tanto, para obtener la solución óptima es necesario determinar cual es la dirección de movimiento de las variables no básicas.
Paso 2. Establecer cual es la dirección de movimiento de las variables no básicas. Se aumentará el valor de la variable no básica que proporcione un mayor valor de la función objetivo y se calculan los valores del resto de las variables para que se cumpla el sistema de ecuaciones. Esta variable se llama variable básica entrante y aumentará su valor dentro del conjunto factible hasta que la primera variable básica valga cero (no se pueden incumplir las restricciones de no negatividad de las variables). Con estos valores, que toman la variable básica entrante y la nueva variable básica, se resuelve el sistema de ecuaciones obteniendo una solución básica factible. Esta solución no será óptima si al aumentar el valor de una variable no básica el valor de la función objetivo aumenta.
Paso 3. Se repite el proceso hasta que al aumentar el valor de cualquier variable no básica el valor de la función objetivo disminuya.
Recuerde que...
- • Este procedimiento iterativo fue propuesto por el matemático norteamericano George Dantzing en 1947.
- • Para resolver un problema utilizando el método simplex es necesario que se maximice una función objetivo lineal sujeta a restricciones lineales que pueden ser de tipo igualdad o desigualdad.
- • Paso 1. Elegir las variables no básicas e igualarlas a cero para obtener la solución básica factible inicial.
- • Paso 2. Establecer cual es la dirección de movimiento de las variables no básicas.
- • Paso 3. Repetir el proceso hasta que al aumentar el valor de cualquier variable no básica el valor de la función objetivo disminuya.