INVESTIGACION DE INVESTIGACION DE OPERACIONES IOPERACIONES I

EDUARDO QUIROZ VERAEDUARDO QUIROZ VERA

EL METODO SIMPLEXEL METODO SIMPLEX

El método simplex prevee un sistema rápido y efectivo El método simplex prevee un sistema rápido y efectivo para resolver problemas de programación lineal. Es la para resolver problemas de programación lineal. Es la técnica empleada en las aplicaciones prácticas y permite técnica empleada en las aplicaciones prácticas y permite resolver una gran cantidad de problemas de real resolver una gran cantidad de problemas de real importancia industrial.importancia industrial.

Este método llega a la solución óptima por medio de Este método llega a la solución óptima por medio de iteraciones o pasos sucesivos, utilizando los conceptos iteraciones o pasos sucesivos, utilizando los conceptos básicos del álgebra matricial, para determinar la básicos del álgebra matricial, para determinar la intersección de dos o mas líneas hiperplanas. Comienza intersección de dos o mas líneas hiperplanas. Comienza con alguna solución factible, y sucesivamente obtiene con alguna solución factible, y sucesivamente obtiene soluciones en las intersecciones que ofrecen mejores soluciones en las intersecciones que ofrecen mejores funciones de la función objetivo.funciones de la función objetivo.

Finalmente, este método proporciona un indicador que Finalmente, este método proporciona un indicador que determina el punto en el cual se logra la solución óptima.determina el punto en el cual se logra la solución óptima.

CASO DE MAXIMIZACIONCASO DE MAXIMIZACION

Dado el siguiente programa lineal en forma general: Max (z) = c1x1 + c2x2 + .........+ cnxn s.a. a11x1 + a12x2 + .......+ a1nxn b1

a21x1 + a22x2 + .......+ a2nxn b2 ................................................. ................................................ am1x1 + am2x2 + .......+ amnxn bm

x j 0 (j=1,n)

Max (z) = c1x1 + c2x2 + .........+ cnxn + 0 x n+1 +0 x n+2+...+0 x n+m s.a.

a11x1 + a12x2 + .......+ a1nxn + x n+1 = b1 a21x1 + a22x2 + .......+ a2nxn + x n+2 = b2 ................................................. ................................................

am1x1 + am2x2 + .......+ amnxn + x n+m = bm

x j 0 (j=1,n+m)

Cabe indicar que las variables de Cabe indicar que las variables de holgura son no negativas. Además, holgura son no negativas. Además, en la función objetivo, los en la función objetivo, los coeficientes asociados a estas coeficientes asociados a estas variables tomas el valor cero, ya que variables tomas el valor cero, ya que no deben afectar el valor de la no deben afectar el valor de la función en caso de ser positivas. función en caso de ser positivas.

Así mismo en las restricciones Así mismo en las restricciones estructurales, los coeficientes de las estructurales, los coeficientes de las variables de holgura son 1 y positivo.variables de holgura son 1 y positivo.

PROBLEMA DE PLANEACION DE PRODUCCIONPROBLEMA DE PLANEACION DE PRODUCCION La Cia. ALFA fabrica artículos para el hogar y manufactura dos La Cia. ALFA fabrica artículos para el hogar y manufactura dos productos: A y B. Ambos sufren 3 procesos en el mismo orden que productos: A y B. Ambos sufren 3 procesos en el mismo orden que

son:son:

MaquinadoMaquinado ArmadoArmado MontajeMontaje

La disponibilidad de minutos diarios de cada proceso es: 160,120 yLa disponibilidad de minutos diarios de cada proceso es: 160,120 y280 minutos respectivamente.280 minutos respectivamente.

El producto A requiere 2, 1 y 4 minutos de maquinado, armado y El producto A requiere 2, 1 y 4 minutos de maquinado, armado y montaje respectivamente; mientras que el producto B, necesita 2, 2 montaje respectivamente; mientras que el producto B, necesita 2, 2

y 2 y 2 minutos de maquinado, armado y montaje respectivamente.minutos de maquinado, armado y montaje respectivamente.

El gerente de producción debe decidir que cantidad de cada El gerente de producción debe decidir que cantidad de cada producto producto

debe manufacturarse con el objeto de hacer el mejor empleo de losdebe manufacturarse con el objeto de hacer el mejor empleo de losmedios limitados de producción, sabiendo que la ganancia por cada medios limitados de producción, sabiendo que la ganancia por cada unidad del producto A es $10 y del producto B es de $15.unidad del producto A es $10 y del producto B es de $15.

Las variables de decisión son:Las variables de decisión son:

xx11: número de unidades del producto A que se va : número de unidades del producto A que se va a producir/díaa producir/día

xx22: número de unidades del producto B que se va : número de unidades del producto B que se va a producir/díaa producir/día

El programa lineal es:El programa lineal es:

Max Z = 10 x Max Z = 10 x 11 + 15 x + 15 x 22

s.a.s.a. 2x 2x 11 + 2x + 2x 22 160 160

x x 11 + 2x + 2x 22 120 120 4x 4x 11 + 2x + 2x 2 2 280 280

x x 11, x , x 22 0 0

Max Z = 10 x Max Z = 10 x 11 + 15 x + 15 x 22 + 0 x + 0 x 33 + 0 x + 0 x 44 + 0 x + 0 x 55

s.a.s.a.

2x 2x 11 + 2x + 2x 22 + x + x 3 3 = 160 = 160

x x 11 + 2x + 2x 22 + x + x 4 4 = 120 = 120

4x 4x 11 + 2x + 2x 2 2 + x + x 55 = 280 = 280

x x 11, x , x 22, x , x 33, x , x 44 x x 55 0 0

Tablero Nº 1Tablero Nº 1c j 10 15 0 0 0 c i x k b i X 1 X 2 x 3 x 4 x 5 0 x 3 160 2 2 1 0 0 80 0 x 4 120 1 (2) 0 1 0 60 0 x 5 280 4 2 0 0 1 140

Z 0 0 0 0 0 0 c j – z j 10 15 0 0 0

Z = ci . bi el cual representa el valor de la función objetivo.

Z j = ci . a ij

Min = min (bi / a ij) donde a ij > 0

Tablero Nº 2Tablero Nº 2

c j 10 15 0 0 0 c i x k b i X 1 X 2 x 3 x 4 x 5 0 x 3 40 (1) 0 1 -1 0 40 15 x 2 60 1/2 1 0 ½ 0 120 0 x 5 160 3 0 0 -1 1 53.3

Z 900 7.5 15 0 7.5 0 c j – z j 2.5 0 0 -7.5 0

Tablero Nº 3Tablero Nº 3

c j

10 15 0 0 0

c i x k B i X 1 X 2 x 3 x 4 x 5 10 x 3 40 1 0 1 -1 0 15 x 2 40 0 1 -1/2 1 0 0 x 5 40 0 0 -3 2 1

Z 1000 10 15 2.5 5 0 c j – z j 0 0 -2.5 -5 0

CASO DE MINIMIZACIONCASO DE MINIMIZACION

Dos fabricas de papel producen 3 tipos diferentes de Dos fabricas de papel producen 3 tipos diferentes de papel papel

de bajo grado, medio grado y alto grado. Se tiene un de bajo grado, medio grado y alto grado. Se tiene un contrato de venta para proveer: 16 ton. de bajo grado, 5contrato de venta para proveer: 16 ton. de bajo grado, 5 ton. de medio grado y 20 ton. de alto grado.ton. de medio grado y 20 ton. de alto grado.La fabrica 1, produce 8 ton de bajo grado, 1 ton de medio La fabrica 1, produce 8 ton de bajo grado, 1 ton de medio grado y 2 ton de alto grado en un día de operación. La grado y 2 ton de alto grado en un día de operación. La fabrica 2 produce 2 ton de bajo grado, 1 ton de medio fabrica 2 produce 2 ton de bajo grado, 1 ton de medio grado y 7 ton de alto grado por día de operación.grado y 7 ton de alto grado por día de operación.

Los costos de operación son de $1000/día para la fabrica Los costos de operación son de $1000/día para la fabrica 1 1

y de $2000/día para la fabrica 2.y de $2000/día para la fabrica 2.¿Cuantos días debe trabajar cada fabrica a fin de cumplir ¿Cuantos días debe trabajar cada fabrica a fin de cumplir con el mencionado contrato de venta en la forma más con el mencionado contrato de venta en la forma más económica?económica?

Sean las variables de decisión:Sean las variables de decisión:

xx11 = número de días de trabajo de la fabrica 1 = número de días de trabajo de la fabrica 1

xx2 2 = número de días de trabajo de la fabrica 1= número de días de trabajo de la fabrica 1

Min (z) = 1x1 +2x2Min (z) = 1x1 +2x2

s.a.s.a.

8x8x11 +2x +2x22 16 16

1x1x11 +1x +1x22 5 5

2x2x11 +7x +7x22 20 20

xx11, x, x22 0 0

Se sustraen 3 variables de exceso:Se sustraen 3 variables de exceso:

Min (z) = 1xMin (z) = 1x11 +2x +2x22 + 0x + 0x33 + 0x + 0x44 + 0x + 0x55

s.a.s.a.

8x8x11 +2x +2x22 - x - x33 = 16 = 16

1x1x11 +1x +1x2 2 - x - x44 = 5 = 5

2x2x11 +7x +7x2 2 - x - x55 = 20 = 20

xx11, x, x22, x, x33, x, x44, x, x55 0 0

Para el caso de minimización, se Para el caso de minimización, se propone una modificación a partir de propone una modificación a partir de esta etapa del simplex. Esta consiste esta etapa del simplex. Esta consiste en hacer que las variables en hacer que las variables estructurales puedan tomar un valor estructurales puedan tomar un valor nulo en las ecuaciones precedentes, nulo en las ecuaciones precedentes, en forma tal que las variables de en forma tal que las variables de exceso, permaneciendo positivas, exceso, permaneciendo positivas, satisfagan dichas ecuaciones. Esto se satisfagan dichas ecuaciones. Esto se logra introduciendo además de las logra introduciendo además de las variables de exceso, las llamadas variables de exceso, las llamadas “variables artificiales” (“variables artificiales” (λλjj))

Min (z) = 1xMin (z) = 1x11 +2x +2x22 + 0x + 0x33 + 0x + 0x4 4 + 0x+ 0x55 + M + M11 +M +M 22 +M +M33

s.a.s.a.

8x8x11 + 2x + 2x22 - x - x3 3 + +11 = 16 = 16

1x1x11 + 1x + 1x22 - x - x44 + +22 = 5 = 5

2x2x11 + 7x + 7x2 2 - x - x55 + +33 = 20 = 20

xx11, x, x22, x, x33,x,x44 ,x ,x55, , 11 , , 22, , 33 0 0

Tablero 1Tablero 1

cj 1 2 0 0 0 M M M ci xk bi X1 X2 X3 X4 X5 1 2 3 M 1 16 (8) 2 -1 0 0 1 0 0 2 M 2 5 1 1 0 -1 0 0 1 0 5 M 3 20 2 7 0 0 -1 0 0 1 10

Z 41M 11M 10M -M -M -M M M M cj - zj 1-

11M 2-

10M M M M 0 0 0

Tablero 2Tablero 2

cj 1 2 0 0 0 M M M ci xk bi X1 X2 X3 X4 X5 1 2 3 1 X1 2 1 2/8 -1/8 0 0 1/8 0 0 8 M 2 3 0 6/8 1/8 -1 0 -1/8 1 0 4 M 3 16 0 (52/8

) 2/8 0 -1 -2/8 0 1 2.26

Z 2+19M

1 2/8+ 58/8

M

1/8+ 3/8M

-M -M 1/8- 3/8M

M M

cj - zj 0 6/8 - 58/8

M

-1/8 +

3/8M

M M -1/8 +

11/8M

0 0

Tablero 3Tablero 3

cj 1 2 0 0 0 M M M ci xk bi X1 X2 X3 X4 X5 1 2 3 1 X1 72/52 1 0 -7/52 0 2/52 7/52 0 -2/52 36 M 2 60/52 0 0 5/52 -1 (6/52

) -5/52 1 -6/52 10

2 X2 32/13 0 1 2/52 0 -8/52 -2/52 0 8/52

Z 328/52

+60M/52

1 2 -3/52 +

5M/52

-M -14/5

2 +6M/

52

3/52 - 57M/5

2

0 14/52 - 58M/52

cj - zj 0 0 3/52 -

5M/52

M 14/52 -

6M/52

-3/52 +

57M/52

0 -14/52+ 58M/52

Tablero 4Tablero 4

cj 1 2 0 0 0 M M M ci xk bi X1 X2 X3 X4 X5 1 2 3

1 X1 3 1 0 -8/6 -1/6 0 8/6 1/6 0 0 X5 12 0 0 5/6 -1/6 1 -5/6 1/6 -1 2 X2 2 0 1 2/6 1/6 0 -2/6 -1/6 0

Z 7 1 2 -4/6 -1/6 0 4/6 1/6 0 cj - zj 0 0 4/6 1/6 0 M-

4/6 M-1/6

M