Metodo Simplex

Método del 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.

El método del simplex nos facilitara la obtención de la solución optima mediante la elaboración de un criterio que nos permitirá saber si una solución básica es o no la optima y, en caso contrario, nos dará un procedimiento de aproximación a dicho optimo.

Supongamos el problema de programación lineal:

Z = C1X1 + C2X2 + ......+ CnXn =  Ci Xi

s.a.

C11X1 + C12X2 +.........+ C1nXn <= b1

C21X2 + C22X2 +...... ..+ C2Nxn <= b2

.

.

Cm1X1 + Cm2X2 +..........+ CmnXn <= bm

Partiremos de una solución factible básica inicial (vértice) de la que pasaremos a otra solución básica (vértice contiguo) en la que el valor de la función objetivo sea mayor que la anterior, y asi sucesivamente hasta llegar a una solución básica (vértice) en la que el valor de Z sea máximo (solución optima).

En algunos casos, las “Variables de Holgura” nos sirven para determinar la solución inicial, tomando: x= bi, i=1,...,m siempre que las componentes del vector de disponibilidades de recursos sean no negativas, esto es bi 0. En caso que alguna de las restricciones fuera de igualdad o algún bi < 0 las variables de holgura no nos sirven, por lo que se agregan “Variables Artificiales”.

Ejemplo del método Simplex

Vamos a resolver mediante el método simplex el siguiente problema:

Maximizar Z = f (x,y) = 3x+2y

Sujeto a :

2 X + Y <= 18

2 X + 3Y <= 42

3 X + Y <= 24

Siempre que X  0, Y 0

Se consideran las siguientes fases:

CONVERTIR LAS DESIGUALDADES EN IGUALDADES

Se introducen variables de holgura ( h1, h2 ,h3) por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:

2x + y + h1 = 18

2x +3y + h2 = 42

3x + y + h3 = 24

• IGUALAR LA FUNCIÓN OBJETIVO A CERO

- 3x –2y + z = 0

Nota: 1- Las Variables de Holgura se agregan -como se menciono anteriormente- para partir del supuesto que x=0 e y = 0 y cumplir con la condición inicial para aplicar el método Simplex.

2- La función objetivo puede ser igualada con

– z+2y + 3x = 0, eso es indistinto.

• ESCRIBIR LA TABLA INICIAL SIMPLEX

En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes de las igualdades obtenidas, una fila para cada restricción y la ultima fila con los coeficientes de la función objetivo:

• ENCONTRAR LA VARIABLE DE DECISION QUE ENTRA EN LA BASE Y LA VARIABLE DE HOLGURA QUE SALE DE LA BASE.

Para escoger la variable de decisión que entra en la base, nos fijamos en la ultima fila, la de los coeficientes de la función objeto y escogemos la variable con el coeficiente negativo mayor (en valor absoluto).

En nuestro caso, la variable x de coeficiente –3.

Si existiesen dos o mas coeficientes iguales que cumplan la condición anterior, entonces se elige uno cualquiera de ellos.

Si en la ultima fila no existiese ningún coeficiente negativo, significa que se ha alcanzado la solución optima. por tanto, lo que va ha determinar el final del proceso de aplicación del método simplex, es que en la ultima fila no haya elementos negativos.

La columna de la variable que entra en la base se llama columna pivote.

Para encontrar la variable de holgura que tiene que salir de la base, se divide cada termino de la ultima columna (valores solución) por el termino correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero, en nuestro caso:

18/2=9 , 42/2=21 , 24/3=8

Si hubiese algún elemento menor o igual que cero no se hace dicho cociente .en el caso de que todos los elementos fuesen menores

...