Método Simplex

Método Simplex

El método del simplex fue creado en 1947 por el matemático George Dantzig. El método del simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables.

El álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la base del método simplex.

Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.

Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.

El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.

Función Objetivo

Es una expresión matemática lineal que representa el objetivo del problema. Es la expresión que tendremos que maximizar o minimizar una función lineal, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.

La función objetivo puede ser:

o

Donde:

 = coeficientes son relativamente iguales a cero.

Variable de holgura

Variables de holgura o excedente. Son variables que se agregan a la restricción para que la relación de la restricción sea de igualdad (representa el valor que le hace falta al lado izquierdo para ser igual al lado derecho). Ambos tipos de variables tienen que cumplir con la restricción de no negatividad, se suma al lado izquierdo de la restricción del tipo ≤.

Ejemplo:

6 x1+4 x2 ≤ 24 6 x1+4 x2 + h = 24

Noción de la dualidad en la programación lineal

Tiene unas importantes relaciones y propiedades respecto al problema primal que pueden ser de gran beneficio para la toma de decisiones. A continuación se muestran algunas características de la noción dual:

El número de variables que presenta el problema dual se ve determinado por el número de restricciones que presenta el problema primal.

- El número de restricciones que presenta el problema dual se ve determinado por el número de variables que presenta el problema primal.

- Los coeficientes de la función objetivo en el problema dual corresponden a los términos independientes de las restricciones (RHS), que se ubican del otro lado de las variables.

- Los términos

...