A PLICACIONES

DE

AS:

EJEMPLOS

E LISA S CHAEFFER Programa de Posgrado en Ingenier´ıa de Sistemas (P ISIS ) [email protected]

´ I NVESTIGACI ON

DE

O PERACIONES

E JEMPLO : TRANSPORTE ´ ˜ produce a la Tenemos dos fabricas farmaceuticas. ´ La pequena ´ ´ capacidad maxima 300 unidades diarias y la grande 500 unidades diarias. Tres distribuidores venden el producto y tienen demandas m´ınimas diarias de 150, 350 y 300 unidades. Los ´ costos de transporte de fabrica a distribuidor ci,j por unidad son: cD,F

F1

F2

Demanda

D1

15

5

150

D2

7

10

350

D3

20

13

500

Capacidad

300

500

Todos los distribuidores pagan el mismo precio por unidad. Hay que minimizar el costo total del transporte y transportar por lo menos 50 unidades de F1 a D1 .

´ COMO UN PL E JEMPLO : FORMULACI ON

m´ın x

X i,j

ci,j xi,j s.a.

                            

r1 : x1,1 + x2,1 + x3,1

≤ 300

r2 : x1,2 + x2,2 + x3,2

≤ 500

r3 :

x1,1 + x1,2

= 150

r4 :

x2,1 + x2,2

= 350

r5 :

x3,1 + x3,2

= 300

r6 :

x1,1

≥ 50

∀i, j :

xi,j

≥ 0

´ E JEMPLO : SOLUCION OPTIMA

P =D x∗

= 7900 = (x1,1 , x1,2 , x2,1 , x2,2 , x3,1 , x3,2 ) = (50, 100, 250, 100, 0, 300)

y∗

= (2, 5, 0, 5, 8, 13)

´ DEL y? ¿I NTERPRETACI ON P = 7900 con f (x) = 15x1,1 + 5x1,2 + 7x2,1 + 10x2,2 + 20x3,1 + 13x3,2 . ¡Los precios sombre de igualdades y restricciones en la ´ “opuesta” no funcionan! direccion ri

bi

yi

∆P con bi ↑

∆P con bi ↓

Efecto

≤

300

2

−3

imposible

x2,2 ↓, x2,1 ↑

≤

500

5

0

imposible

ninguno

=

150

0

imposible

−5

x1,2 ↓

=

350

5

imposible

−10

x2,2 ↓

=

300

8

imposible

−13

x3,2 ↓

≥

50

13

+13

−13

varios

´ estamos modificando y Hay que ver que´ tipo de restriccion que´ consequencias tiene el cambio con las otras restricciones.

E JEMPLO : COSTO DE OPORTUNIDAD Estan considerando a poner pavimiento nuevo por la ruta de F1 a ´ deber´ıa ser el costo D3 para bajar el costo de transporte. ¿Cual de transporte por unidad por la ruta para que lo utilicen? ´ El optimo para el caso donde x3,1 = 1 es 7910. El costo de oportunidad es 7910 - 7900 = 10 y entonces el precio disparador de la ruta es 20 - 10 = 10.

E JEMPLO : ¿ ENTONCES ? Si realizamos tal cambio de c′3,1 = 10 y resolucionamos, ´ a las variables es P = P ′ = 7900 no cambia, pero la asignacion diferente: x∗ = (50, 100, 250, 100, 0, 300) x′

∗

= (50, 100, 0, 350, 250, 50)

´ grandes de c3,1 , incluso 11, no hay cambio en la Con valores mas ´ asignacion. ´ No es realmente necesario calcular el nuevo optimo: la ´ del dual que corresponde a variable de holgura de la restriccion x3,1 es exactamente el costo de oportunidad de la primer variable ´ en el optimo: y1 + y5 = 2 + 8 = 10 ≤ 20 ⇒ 10 es el costo que buscamos.

E JEMPLO : RECETA DE PAN ´ ´ optimizando el uso de los ingredientes En la fabrica de pan, estan para minimizar el costo de pan multigrano mientras se cumple ´ de la mezcla con algunos requisitos nutricionales: la composicion de harina tiene trigo blanco (H1 ), trigo integral (H2 ), avena (H3 ), y ´ linaza molida (H4 ). Los precios pi por kilogramo y los porcentajes ´ m´ınimos (bi ) y maximos (si ) son los siguientes: pi

bi

si

H1

1,0 40 90

H2

1,5

0 70

H3

1,7

7 30

H4

7,0

2

5

E JEMPLO : MODELO DE PL

m´ın x

4 X i=1

pi xi s.a.

     

r1 :

4 X

xi

= 100

i=1

 de r2 a r5 : ∀i : xi     de r6 a r9 : ∀i : xi

≤ si ≥ bi

−→

  x∗ P ≈ 117,4 con  y∗

= (90, 1, 7, 2), = (1 21 , 0, 0, 15 , 5 21 , 12 , 0, 0, 0)

El resultado sera´ entonces pan casi blanco, entonces. Es un resultado predecible: poner el m´ınimo de todo, continuar con ´ barato, despues ´ el todo lo que se puede del ingrediente mas ´ barato, etcetera. ´ segundo mas

E JEMPLO : PRECIOS SOMBRA El subgerente esta´ preocupado por el uso de avena, porque le ´ quiere saber cuanto ´ parece muy caro. El bajara´ el precio de la ´ mezcla por kilogramo si se exige solamente 4 % de avena en vez del 7 % que se exige por ahora. b′6 := 4 = b6 − 3 junto con precio sombra de avena y6 ≈ 15 nos da el resultado: baja en 3 unidades (o sea porcientos) esto da un ahorro de 0,6 por kilo: 117,4 − 0,6 = 116,8. No es mucho ahorro y deciden que no vale la pena.

E JEMPLO : RESTRICCIONES ADICIONALES Sin embargo, el gerente es un hombre educado y sabe que comer ´ exige que no se ponga pan blanco es muy malo para la salud. El ´ de harina de trigo blanco que de harina integral. mas

r ′ : x2 − x1 ≥ 0 =⇒ P ′ ≈ 139, 65 con x∗ = (45 12 , 45 21 , 7, 2) ¿Se puede predecir que esto va a pasar?

A LGORITMO S IMPLEX D UAL Como ya aprendimos, hay una manera de introducir ´ Con restricciones nuevas sin reiniciar el proceso de resolucion. el algoritmo Simplex Dual, se puede continuar directamente de la ˜ tabla final del algoritmo, anadiendo una fila nueva en la tabla ´ y iterando hasta llegar a la (primal) para representar la restriccion ´ optima. ´ solucion Si el gerente quisiera introducir centeno en la mezcla, la ´ para acomodar la variable nueva se podr´ıa hacer modificacion ´ con una continuando desde la tabla final de Simplex basico columna adicional.

´ ... A CONTINUACI ON Repaso para el examen parcial. ´ del repaso, continuamos en la segunda parte del curso Despues con problemas de redes y grafos, resolucionandolos con ´ entera. programacion