Resolución de Problemas Método Gráfico

Primer Semestre 2007

EII 405 – Clase 4

Conjunto convexo

Conjunto no convexo

Cuando el problema se transforma en un modelo matemático con 2 (ó 3) variables de decisión, entonces es posible resolver gráficamente el problema.

Si la región de soluciones factibles del problema es un conjunto convexo, existe a lo menos un óptimo global y se encuentra en una esquina.

Un conjunto es convexo si el segmento rectilíneo que une cualquier par de puntos del conjunto se encuentra completamente dentro de él.

Método Gráfico

Una empresa produce dos tipos de juguetes de plásticos: Space y Zapper. La empresa dispones de 40 horas semanales de producción y de 1200 kilos de plásticos para la construcción de ambos juguetes.

El Depto de Marketing ha determinado que la demanda conjunta no excederá de las 800 docenas y que el número de docenas de Space no puede exceder al número de docenas de Zapper por más de 450.

El Depto de Producción determinó que los Space requieren de 2 kilos de plástico y 3 minutos de producción por docena, mientras que los Zappers requieren de 1 kilo de plástico y 4 minutos de producción por docena.

Ejemplo

Método Gráfico

La utilidad que se obtendrá por los Space es de $8 por docena y $5 por docena de Zapper.

Determine la política óptima de producción para maximizar las ganancias

Definición de variables:

X: Docenas a producir de SpaceY: Docenas a producir de Zapper

F.O: Max Z = 8X + 5Y

S. a

2X + Y 1200 Plástico disponible

3X + 4Y 2400 Tiempo disponible

X + Y 800 Demanda máxima

X - Y 450 Producción en exceso

X, Y 0

Método Gráfico

600

600 800

1200

Región infactible

Región factible

2X + Y 1200

3X + 4Y 2400

X + Y 800

X - Y 450

Y

X

Método Gráfico

Hay 2 procedimientos para encontrar la solución factible óptima:

Evaluar la F.O. en cada una de las esquinas del área de soluciones factibles.

El problema es cuando hay un área con muchas esquinas lo que implica la solución de muchos sistemas de ecuaciones lineales.

Usar la F.O. para determinar la esquina del área de soluciones factibles que la optimiza.

El problema se produce cuando la F.O. es aproximadamente paralela a uno de los lados del área de soluciones factibles, originando una duda visual sobre la gráfica.

Método Gráfico

Y

X

P(0;600) Z= 3000

P(480;240) Z= 5040

P(550;100) Z= 4900

P(450,0) Z= 3600P(0,0)

Procedimiento 1

Óptimo

Política de ProducciónSpace = 480

Zapper = 240Utilidad = $5040

Política de ProducciónSpace = 480

Zapper = 240Utilidad = $5040

Método Gráfico

Procedimiento 2Política de Producción

Space = 480Zapper = 240

Utilidad = $5040

Política de ProducciónSpace = 480

Zapper = 240Utilidad = $5040

Utilidad = 80020003600 Utilidad = 5040 Utilidad = 5040

Método Gráfico

Ejemplo 2

Max Z = 2,5X1 + X2

S.a

3X1 + 5X2 15

5X1 + 2X2 10

Xi 0 con i = 1 y 2

X2

X1

3X1 + 5X2 15

5X1 + 2X2 10

3

5

52

Método Gráfico

3

2

X2

X1

P(20/19;45/19) Z= 5

P(2;0) Z= 5

Z = 3

Método Gráfico

Problema de múltiples soluciones

Problema de múltiples soluciones

Cuando existen múltiples soluciones óptimas implica que la función objetivo es una recta paralela a uno de los lados de la región factible.

En el ejemplo todos los puntos que pertenecen a la recta 5X1 + 2X2 = 10 entre los puntos (2;0) y (20/19;45/19) maximizan la F.O, es decir, existen múltiples soluciones con Z = 5

Múltiples soluciones óptimas

Método Gráfico

Ejemplo 3

Min Z = -X1 + X2

S.a

X1 X2

-0,5X1 + X2 1

Xi 0 con i = 1 y 2

X1 – X2 0

X2

X1

-0,5X1 + X2 1Región factible

infinitaRegión factible

infinita

Problema de soluciones

indeterminadas

Problema de soluciones

indeterminadas

Método Gráfico

Caso 4

Min Z = -X + Y

S.a

X Y

X + Y 6

-X + 2Y 6

X 0

Y 0

Y

X

X Y

X + Y 6

-X +2Y 6

Problema sin Solución

Problema sin Solución

Método Gráfico

Ejercicio:

Máx. Z = 2X + Y

S.a

2X – Y 8

X - Y 3

X + 2Y 14

X + 4Y 24

X 0

Y 0

Y

X

2X – Y 8

X + 2Y 14

X – 3

X + Y 24

P(6,4) Z = 16P(6,4) Z = 16

Método Gráfico

¿En qué intervalo puedo variar los coeficientes de la F.O. (Cj) sin que cambie la actual solución óptima?

¿Cuánto varía el óptimo si se cambia el parámetro “del lado derecho” (bi) de una restricción ?

¿Qué recurso tiene mayor impacto en la F.O. y en el valor óptimo?

Análisis de Sensibilidad

Supongamos el siguiente ejemplo:

Max Z = 15X + 20YS.a X + 2Y 6 2X + 2Y 8 X, Y 0

4 6

4

3

X

Y

P(2;2) Z = 70P(2;2) Z = 70

Análisis de Sensibilidad

4 6

4

3

X

Y

P(2;2) Z = 70P(2;2) Z = 70

Se analizan las pendientes de las restricciones activas y la de la F.O.

Entonces, el actual vértice (2,2) seguirá siendo la solución óptima mientras:

La pendiente de la FO se encuentra entre las pendientes de las restricciones activas

La pendiente de la FO se encuentra entre las pendientes de las restricciones activas

Variación de los Cj

Max Z = C1X + C2Y Pendiente: -C1/C2

S.a X + 2Y 6 Pendiente: -1/2 2X + 2Y 8 Pendiente: -1 X, Y 0

La pendiente de la FO se encuentra entre las pendientes de las restricciones activas

La pendiente de la FO se encuentra entre las pendientes de las restricciones activas

Matemáticamente:

-C1/C2 [-1,-1/2]

Es decir:

-1 -C1/C2 -1/2

C2 C1

2C1 C2

C2 C1

2C1 C2

Variación de los Cj

Variación de C1 con C2 constante:

-1 - C1 /20 -1/2

C1 20 y C1 10

10 C1 20

Variación de C1 con C2 constante:

-1 - C1 /20 -1/2

C1 20 y C1 10

10 C1 20

También se puede estudiar el intervalo de variación de un solo coeficiente, dejando el resto de los parámetros fijos:

Variación de C2 con C1 constante:

-1 - 15/C2 -1/2 C2 15 y C2 30

15 C2 30

Variación de C2 con C1 constante:

-1 - 15/C2 -1/2 C2 15 y C2 30

15 C2 30

Variación de los Cj

En este caso interesa hallar la mínima y máxima variación del bi que conserve la actual geometría del problema, es decir, que conserve las actuales restricciones activas. De esta manera, la solución óptima cambia, pero se obtiene a partir de las mismas restricciones activas.

En el ejemplo, para la 1ª restricción: X + 2Y = b1, la mayor variación se obtiene en b1= 8, en tanto que la menor se obtiene en b1= 4.

En el ejemplo, para la 1ª restricción: X + 2Y = b1, la mayor variación se obtiene en b1= 8, en tanto que la menor se obtiene en b1= 4.

X + 2Y = 8

X + 2Y = 4

Variación de los bj

Ahora es posible calcular la tasa de cambio de la F.O. al variar b1:

54

20

48

6080)0,4()4,0(

11

1

bb

zz 54

20

48

6080)0,4()4,0(

11

1

bb

zz

Lo anterior significa que que si dispongo de 1 unidad más del recurso, entonces la utilidad va a aumentar en 5 unidades. Lo anterior es válido dentro del rango, porque fuera de él las restricciones activas cambian.

Variación de los bj

Con los precios sombra se puede ver cuál recurso es el que más afecta a la F.O.

Toda restricción que no esté activa tiene precio sombra cero.

Con los precios sombra se puede ver cuál recurso es el que más afecta a la F.O.

Toda restricción que no esté activa tiene precio sombra cero.

La tasa de cambio es una para cada restricción. También se le llama “Precio sombra” pues representa el valor máximo que estoy dispuesto a pagar por una unidad de ese recurso.

La tasa de cambio es una para cada restricción. También se le llama “Precio sombra” pues representa el valor máximo que estoy dispuesto a pagar por una unidad de ese recurso.

Variación de los bj

Para la 2ª restricción: 2X + 2Y = b2

2X + 2Y = 12

2X + 2Y = 6

56

30

6126090

bb)3,0(z)0,6(z

222

56

30

6126090

bb)3,0(z)0,6(z

222

Variación de los bj

En este ejemplo ambos recursos presentan igual tasa de cambio, o precio sombra, por lo que ambos aportan el mismo beneficio a la F.O. Entonces la elección depende de los precios de compra de cada recurso. Se elige el más barato.

En general, si se dispone de dinero, se elige el recurso que entregue mayor tasa de cambio, descontado el precio de compra

del recurso.

En general, si se dispone de dinero, se elige el recurso que entregue mayor tasa de cambio, descontado el precio de compra

del recurso.

Variación de los bj