Investigue sobre el método del ponderador (o método de la gran M) para inicializar problemas de optimización

1. Investigue sobre el método del ponderador (o método de la gran M) para inicializar problemas de optimización. Describa brevemente su funcionamiento.

METODO DE LA GRAN M

Para la resolución de problemas a través del método simplex en ocasiones no es inmediata la obtención de una solución básica factible inicial, en las variables originales del modelo.  Por esto existen otros métodos como el de la gran M, que consiste en modificar el problema inicial, agregando unas variables A denominadas artificiales que se penalizan con mediante un costo “M” que se refiere a valores muy grandes positivos.

FUNCIONAMIENTO

1. Pasar a la forma estándar, pasando a igualdad mediante la adición de las holguras S las inecuaciones de las restricciones iniciales.
2. Agregar variables artificiales en las ecuaciones que no tienen variables de holgura.
3. Se penalizan a las variables artificiales en la función objetivo asignándoles coeficientes positivos muy grandes al que se le asigna la letra M  un número muy grande. (en los modelos de Minimización la penalización para cada variable se suma y en los modelos de Maximización se restan).
4. Con la solución inicial artificial se aplica el método simplex de la forma acostumbrada, generando las tablas necesarias para llegar a una solución.

Cuadro de signos

[pic 1]

2. Resuelva a través del método Simplex el problema de Sunco Oil visto en clase. Para inicializar el problema utilice el método de las dos fases. Presente cada una de las iteraciones en MS-Excel con las conclusiones respectivas en cada etapa del método.

Min Z= 20X1+15X2

s.a

0.3X1 + 0.4X2 >= 2000

0.4X1 + 0.2X2 >= 1500

0.2X1 + 0.3X2 >= 500

X1 >= 9000

X2 >= 6000

X1, X2 ≥ 0

0.3 X1 + 0.4 X2 - S1                              + A1                 = 2000

0.4 X1 + 0.2 X2       - S2                                 + A2                = 1500

0.2 X1 + 0.3 X2             - S3                                   + A3          = 500

X1                                           + S4                                 = 9000

X2                                                   + S5                         = 6000

METODO 2 FASES

TABLA 1

[pic 2]

Variable que entra: X2

Variable que sale: A3

[pic 3]

TABLA 2

[pic 4]

Variable que entra: S3

Variable que sale: A1

[pic 5]

TABLA 3

[pic 6]

Variable que entra: S1

Variable que sale: S5

[pic 7]

TABLA 4

[pic 8]

Variable que entra: X1

Variable que sale: A2

[pic 9]

TABLA 5

[pic 10]

La función objetivo es igual a 0 (cero), las variables artificiales con el método Cj-Zj son iguales a 1 y las demás variables 0 (cero), entonces procedo aplicar método simplex eliminando las variables artificiales

METODO SIMPLEX

TABLA 6

[pic 11]

Variable que entra: S5

Variable que sale: S1

[pic 12]

TABLA 7

[pic 13]

La solución óptima es Z = 92500

X1 = 2000

X2 = 3500

S1 = 0

S2 = 0

S3 = 950

S4 = 7000

S5 = 2500

A1 = 0

A2 = 0

A3 = 0

Procedimiento

• En la parte superior de las tablas ingresamos las variables, las holguras, las artificiales y los resultados de las inecuaciones. Para las variables y holguras  tomamos los coeficientes  como cero y las artificiales como 1.
• En la primera columna ingresamos las artificiales y aquellas holguras positivas.
• La fila Zj es la suma producto de la primera columna con cada una de las columnas.
• Para iniciar el procedimiento de la fila Cj-Zj escojo el menor negativo.
• Luego divido la columna b en la columna que se seleccionó en el numeral anterior.
• De la división anterior, donde obtengo el número menor positivo, escojo esa fila.
• Y Ahora:  

Variable que entra: X2

Variable que sale: A3

Sale la fila y entra la columna.

• En esta intersección mediante reducción de Gauss-Jordan debo colocar un pivote 1 y todos los números por encima y por debajo deben ser ceros mediante operaciones elementales.
•  Vuelvo a mirar la fila Cj- Zj y escojo una vez más el menor negativo, repitiendo el proceso anterior.
• El proceso de la fase 1 termina cuando en la fila Cj-Zj, las celadas correspondientes a  las artificiales son iguales a 1 y el resto de celdas son cero, esto indica que existe una solución factible aquí finaliza la fase 1.
• Luego continuamos con la fase 2 a partir de la solución factible obtenida en el punto anterior con esta nueva tabla  resolvemos mediante el método simplex común, sin considerar las artificiales (Tabla 6 y 7).

Conclusiones

aaaaaaaaaaaaaa

MS-EXCEL SOLVER

[pic 14]

3. Resuelva a través del método Simplex el siguiente problema. Para inicializar el problema utilice el método del ponderador. Muestre las conclusiones respectivas en cada etapa del método.

Max Z= 50X1 + 45X2

s.a

7X1+2X2 >= 30

8X1+5X2 >= 60

X2 >= 5

X1, X2 >=0

Max Z =        50X1+45X2+0S1+0S2+0S3-MA1-MA2

Sujeto a:

7X1+2X2-1S1                  +1A1                  =30

8X1+5X2        -1S2                      +1A2      =60

X2                          +1S3                             =5

...