Semana 7.pptx

INVESTIGACIÓN OPERATIVA I

Formulación de Problemas de de transporte, transbordo y asignación

Objetivos

1. Elaborar MPL aplicado a casos de transporte, transbordo y asignación

Caso 2. Una empresa de microbuses (CUSTERS) desea asignar para sus rutas desde tres ciudades a dos centros comerciales. La cantidad de micros que deben salir de las ciudades a los centros de abastos, es:

CIUDAD 1 2 3

NUMERO DE MICROS 10 20 40

CENTRO COMERCIAL

1 2

DEMANDA

25 30

El costo de cada ruta es: CIUDAD C.COMERCIAL 1 2

1

2

3

24 8

21 16

37 17

Determinar la cantidad de micros que debe surtir cada centro de distribución desde las ciudades, de tal forma que el costo total de transporte sea el menor posible.

FORMULACIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL SOLUCION Relaciones entre almacén y centros de distribución: 10

20

A1

A2

X11 X12 X13 X21 X22 X23

D1

25

D2

30

D3

15

X31 40

1.

X32 A3

X33

VARIABLE DE DECISIÓN

Xij : Cantidad de micros asignados de la ciudad i al C. de abasto j

2.

FUNCIÓN OBJETIVO 

Minimizar los costos de transporte:

Min Z = 24 X11 + 8 X12 + 21 X21 + 16 X22 + 37 X31 + 17 X32

3.

RESTRICCIONES 

Del centro de oferta (Ciudad) X11 + X12 + X13 X21 + X22 + X23 X31 + X32 + X33



= = =

10 20 40

Del centro de demanda (Centro de abastos) X11 + X21 + X31 X12 + X22 + X32 X13 + X23 + X33

= = =

25 30 15

No Negatividad: Xij  0; ∀i=1, 2 y 3; ∀ j= 1, 2 y 3

FORMULACIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL 4. MODELO DE PROGRAMACIÓN LINEAL (MPL) Min Z = 24 X11 + 8 X12 + 21 X21 + 16 X22 + 37 X31 + 17 X32 sa. X11 + X12 + X13 X21 + X22 + X23 X31 + X32 + X33 X11 + X21 + X31 X12 + X22 + X32 X13 + X23 + X33

= = = = = =

10 20 40 25 30 15

Xij  0; ∀i=1, 2 y 3; ∀ j= 1, 2 y 3

Transbordo. El problema de transbordo es una extensión del modelo de transporte, al cual se agregan nodos intermedios denominados nodos de trasbordo. A través de estos nodos intermedios existe la posibilidad de hacer envíos a los nodos de destino (demanda).

Definiremos los puntos de oferta como aquellos puntos desde donde sólo se puede despachar unidades. Similarmente, un punto de demanda es un punto donde sólo se pueden recibir unidades. Un punto de transbordo es punto que puede recibir y enviar unidades a otros puntos.

Origen (n)

Destino (p)

Transbordo (m)

El MPL de Transbordo Sea Xij=número de unidades enviadas desde el punto de oferta i al punto de demanda j usando nodos intermedios k. Con la oferta y la demanda equilibradas: n

Min

sa

m

 c i 1 k 1 m

x

k 1 n m

ik

p

m

x  ckj xkj

ik ik

k 1 j 1

ui

i=1,…,n m

p

 x  x i 1 k 1 m

x k 1

fin

kj

ik

 vj

k 1 j 1

kj

0

k=1,…,m j=1,…,p

Caso 3. Enigma S.A. tiene plantas de producción en Lima y Tacna. Los productos fabricados en cualquiera de estas instalaciones pueden ser enviados a cualquiera de sus almacenes regionales en Ica y Arequipa. De los almacenes regionales, la empresa distribuye a detallistas al menudeo en Ayacucho, Huancayo, Cusco y Huánuco. En las siguientes tablas aparece el costo unitario de transporte de cada ruta de distribución.

Planta

Almacén

Cantidad ofrecida

Ica

Arequipa

Lima

2

3

600

Tacna

3

1

400

Almacén Ica Arequipa Cantidad demandada

Distribuidor al detalle Ayacucho Huancayo Cusco Huánuco 2 6 3 6 4 4 6 5 200 150 350 300

Elaborar la Red. Elaborar el MPL para determinar cuántos productos deben ser trasladados por cada ruta propuesta de tal manera que se cumpla con la cantidad demandada por cada distribuidor al menor costo posible.

Caso 4. Una fábrica posee dos plantas de manufactura, una en Sta Anita y otra en El Callao. La planta de Sta Anita produce 150 unidades al día, la de El Callao 200 unidades al día. Los productos son enviados por avión a Tacna y Puno. En ambas ciudades, se requieren 130 unidades diarias. Existe una posibilidad de reducir costos enviando algunos productos en primer lugar a Arequipa o a Ayacucho y luego a sus destinos finales.

Los costos unitarios de cada tramo factible se ilustran en la siguiente tabla:

Hacia Desde

Sta Anita

Callao

Arequipa

Ayacucho

Tacna

Puno

Sta Anita

0

-

8

13

25

28

Callao

-

0

15

12

26

25

Arequipa

-

-

0

6

16

17

Ayacucho

-

-

6

0

14

16

Tacna

-

-

-

-

0

-

Puno

-

-

-

-

-

0

La fábrica desea satisfacer la demanda minimizando el costo total de envío. En este problema, Sta Anita y Callao son puntos de oferta con 150 y 200 unidades respectivamente. Arequipa y Ayacucho son puntos de transbordo. Tacna y Puno son puntos de demanda de 130 unidades cada uno.

Esquemáticamente, la situación es la siguiente:

Sta Anita

Tacna Arequipa

Ayacucho Callao

a) ¿Se tendría que modificar el esquema? b) Elaborar el MPL

Puno

Asignación. El problema de asignación es un tipo especial de problema de programación lineal en el que los asignados son recursos destinados a la realización de tareas. Por ejemplo, los asignados pueden ser empleados a quienes se tiene que dar trabajo. La asignación de personas a trabajos es una aplicación común del problema de asignación. Sin embargo, los asignados no necesariamente tienen que ser personas. También, pueden ser maquinas, vehículos, plantas a los que se asignan tareas.

Para que un problema se ajuste a la definición de problema de transporte se deben cumplir las siguientes suposiciones: 1) El número de asignados es igual al número de tareas. (este numero se denota por n). 2) Cada asignado se asigna a una tarea. 3) Cada tarea debe realizarla exactamente un asignado. 4) Existe un costo cij asociado con el asignado i ( i = 1,2...,n) que realiza la tarea j (j = 1,2...n). 5) El objetivo es determinar como deben hacerse las n asignaciones para minimizar los costos totales.

Modelo del problema de asignación El modelo matemático para el problema asignación usa las variables de decisión:

de

xij = 1, si el asignado i realiza la asignación j xij = 0, en caso contrario,

Para i = 1,2..., n y j = 1,2...n. Entonces, cada xij es una variable binaria (toma valores 0 o 1). Estas variables representan decisiones de si o no: ¿Debe el asignado i realizar la tarea j?. Sea Z el costo total, el modelo del problema de asignación es:

Modelo del problema de asignación 𝑛

𝑛

𝑀𝑖𝑛𝑍 = ෍ ෍ 𝑐𝑖𝑗 𝑥𝑖𝑗 𝑖=1 𝑗=1

Sujeto a: 𝑛

෍ 𝑥𝑖𝑗 = 1; ∀𝑖 = 1, … , 𝑛 𝑗=1 𝑛

෍ 𝑥𝑖𝑗 = 1; ∀𝑗 = 1, … , 𝑛 𝑖=1

Observe que la estructura es similar al modelo de transporte. De hecho, el problema de asignación es solo un caso especial de los problemas de transporte, en donde los orígenes son ahora los asignados, y los destinos son las asignaciones o tareas y donde: Numero de orígenes (m) = numero de destinos (n). Cada recurso ui = 1 Cada demanda vj = 1.

Modelo del problema de asignación Tabla de parámetros para el problema de asignación formulado como un problema de transporte.

Caso 5. Asociar un trabajo a cada máquina de manera tal que minimice presentan en la tabla:

los

costos

que

se

FORMULACIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL SOLUCION 1.

DEFINICIÓN DE LAS VARIABLES DE DECISIÓN

xij = 1, si se le asigna la maquina i al trabajo j xij = 0, en caso contrario, 2.

FUNCIÓN OBJETIVO

Minimizar los costos de asignación: Min Z = 14x11+5x12+8x13+7x14+2x21+12x22+6x23+ 5x24+7x31+8x32 +3x33+9x34+2x41+4x42+6x43+10x44

3.

RESTRICCIONES 

De la máquina X11 X21 X31 X41



X12 X22 X32 X42

+ + + +

X13 X23 X33 X43

+ + + +

X14 X24 X34 X44

= = = =

1 1 1 1

+ + + +

X41 X42 X43 X44

= = = =

1 1 1 1

Del trabajo

X11 X12 X13 X14 

+ + + +

+ + + +

X21 X22 X23 X24

+ + + +

X31 X32 X33 X34

De asignación: Xij = 1 o 0; ∀ i=1, 2, 3 y 4; ∀ j= 1, 2, 3 y 4

GRACIAS

“Si cuidamos el Medio Ambiente, cuidamos nuestro futuro”