MÉTODO ALGORITMO DE SIMPLEX- SOLUCIÓN DE MAXIMIZACIÓN Y MINIMIZACIÓN

MÉTODO ALGORITMO DE SIMPLEX- SOLUCIÓN DE MAXIMIZACIÓN Y MINIMIZACIÓN

El método simplex: es uno de los varios métodos que existen para el cálculo de los programas lineales y consiste e un simple proceso que sigue una serie de pasos a partir de un tablero original (que se plantea casi idénticamente como en inversión de matrices). Originando otros hasta haber determinado una solución que se llama solución óptima.

VARIABLES DE HOLGURA Y DE EXCESO: hay restricciones como las inecuaciones, donde siempre “sobra” o “falta” una cantidad que aún desconocemos pero que será necesario suponer (considerando como incógnita), para que compense el otro miembro d ela restricción. Dicha variable incógnita será calculada o no, según la optimización de la función objetiva, la requiere necesaria esta variable de Holgura, aquella que se le suma el miembro de la inecuación para compensar el otro miembro de la variable de exceso, aquella que se le resta a un miembro de la inecuación para compensar el otro.

Ejemplo:

[pic 1]        [pic 2]  variable holgura

[pic 3]        [pic 4]  variable exceso

VARIABLE ARTIFICIAL

Es necesario  formar una base (matriz unidad) y una ecuación con variable de exceso no nos permite formularla por el signo que tiene dicha variable, entonces se le agrega una variable artificial “Xi” siendo su valor cero.

[pic 5]        Si agregamos las nuevas variables Xn+1, si asociamos un costo implícito cero, si se trata de variable artificial cuyo valor s cero,  lo podremos asociar un costo “M” de magnitud muy grande que nos permitirá salvar alguna dificultad en el momento de la resolución del programa. De este modo Z se escribirá:

[pic 6]

Ejemplo 1. Zmax= x1 + x2 + 0x3 + 0x4                                variable holgura[pic 7]

[pic 8]

                x1 + 2x2 [pic 9] 4 → x1 + 2x2         + x3        = 4

                3x1+2x2 [pic 10] 2 → 3x1 + 2x2       + x4        = 6

Ejemplo 2. Zmin= 2x1 – x2 + 0x3 + 0x4 + M[pic 11]1 +  M[pic 12]2            v. exceso         v. artificial[pic 13][pic 14]

[pic 15][pic 16]

                2x1 + 4x2       5 → 2x1 + 4x2           -  x3                                = 5

                3x1 +   x2       2 → 3x1 +   x2           -  x4                                = 2

PROCEDIMIENTO DE CÁLCULO

Se tiene los siguientes pasos:

1. Se establece el sistema de ecuaciones donde se presente una base.
2. se disponen las variables sus coeficientes y sus costos, así como las magnitudes (bi) del segundo miembro de las ecuaciones, en un tablero original, en dicho tablero las variables y las magnitudes se ubicarán o dispondrán según un orden el cual nos permite el procedimiento de cálculo.
3. Dentro del tablero dispondremos las variables cuyos coeficientes permiten formar la base en un cuadro.
4. Tal como se hizo en el cálculo de la matriz inversa de una determinada matriz, determinamos el elemento PIVOTE; partiendo del cálculo previo de la fila Zj – Cj para la variable que entra en la solución según sea el caso: menor valor negativo si se trata de maximización y mayor valor positivo si se trata de minimización.
5. determinamos el menos coeficiente positivo para la variable que sale al dividir cada valor bi con el correspondiente elemento de la columna de la variable que entra que antes se halló, entonces la intersección de la variable que entra y sale se determina el pivote.
6. Una vez determinada el pivote y lo semi-pivotes, en el siguiente tablero se determinan cada uno de los elementos o coeficientes como se hacia en el proceso de inversión de la matriz.
7. los pasos restantes son similares hasta encontrar la solución óptima, es decir, cuando en la fila Zj – Cj, no haya ningún negativo para la maximización y si se trata de minimización en la fila Zj – Cj no exista un valor positivo.

EJEMPLO 1:

Sea el siguiente programa de programación lineal solución por algoritmo de simples.

Zmax = x1 + 2x2

S.A.         2x1 + x2 [pic 17]   4

          X1 – x2  [pic 18]  6                  

1er paso

        Se establece el sistema de ecuaciones donde se presenta una base.                                                                                                                                                                                                                                                        

        2x1 + x2 + x3                = 4

          x1 -  x2 + x4                = 6

        Zmax=x1 + 2x2 + 0x3 + 0x4

        Aquí la base formará inicialmente x3 y x4 variables de holgura.

2do paso

        Se dispone  las variables y sus coeficientes y sus costos o utilidades, así como las magnitudes del segundo miembro en un tablero original como sigue:

...