Metodo simplex

METODO SIMPLEX

1.DEFINICION:

Es un procedimiento general para encontrar la solución óptima a problemas de Programación Lineal. Este método logra la solución óptima en un número finito de pasos, la demostración de esto es lo que se pretende realizar.

        (Notas del Método Simplex -Investigación de Operaciones I, pag.3)

2.DESCRIPCION GENERAL:

Existen muchas variantes del método simplex, aunque todas ellas se basan en

la misma idea central. En este capítulo se describe una de tales versiones.

El método simplex se aplica a un PPL en el formato estándar siguiente.

Minimizar

f(x) = cT x (6.3)[pic 1]

3.DEFINICIONES IMPORTANTES.[pic 2][pic 3][pic 4][pic 5]

(Notas del Método Simplex -Investigación de Operaciones I, pag.3)

3.EJEMPLO ILUSTRATIVO DEL METODO SIMPLEX

Considérese el siguiente PPL en forma estándar. Minimizar

Z = −11 + x2 + 6x3 + 2x4 − x9

El método simplex sujeto a:

[pic 6]

(FUNCION OBJETIVO 1)

Como se tienen 6 restricciones de igualdad, se pueden despejar 6 variables, por ejemplo, x1, x2, x5, x6, x7, y x8, como función del resto de variables:

[pic 7]

(SISTEMA DE ECUACIONES)

Esto supone dividir el conjunto de variables {x1, x2, x3, x4, x5, x6, x7, x8, x9} en dos conjuntos {x1, x2, x5, x6, x7, x8} y {x3, x4, x9}, que se conocen como variables básicas y no básicas, respectivamente.

A continuación, se sustituyen las variables básicas (6.2) en la función objetivo (FUNCION OBJETIVO 1), en función de las variables no básicas, para obtener

Z = −7 + x9 + 3x3 + 2x4.

De este modo, el PPL inicial es equivalente a un PPL en el que se minimiza

Z = −7 + x9 + 3x3 + 2x4

[pic 8]

(Formulación y Resolución de Modelos de Programación Matemática en Ingeniería y Ciencia- Enrique Castillo, Antonio J. Conejo, Pablo Pedregal, Ricardo García y Natalia Alguacil, pag.121)

...