modelos cuantitativos 10.1-10.2

Modelos Modelos CuantitativosCuantitativos

Modelos Modelos CuantitativosCuantitativos

Capítulo 10Capítulo 10Problemas de Transporte y Asignación Problemas de Transporte y Asignación 10.1-10.210.1-10.2

Capítulo 10Capítulo 10Problemas de Transporte y Asignación Problemas de Transporte y Asignación 10.1-10.210.1-10.2

Introducción 1.. Los problemas de transporte problemas de transporte son

problemas especiales de programación lineal que reciben ese nombre debido a que muchas de sus aplicaciones involucran determinar la manera óptima de transportar bienes.

Los problemas de asignaciónproblemas de asignación incluyen aplicaciones tales como asignar personas a tareas. Aunque sus aplicaciones parecen diferir de las del problema del transporte, constituye un caso particular.

Introducción 2..

Los problemas de transporte y asignación son casos particulares de un grupo más grande de problemas, llamados problemas de flujo en redes.

Problemas de TransporteProblemas de TransporteProblemas de TransporteProblemas de Transporte

Problema de la Foster Problema de la Foster GeneratorsGenerators

Se transporta un producto desde 3 plantas hasta 4 centros de distribución:

Origen Planta Capacidad deProducción en 3meses (unidades)

1 Cleveland 50002 Bedford 60003 York 2500

Total 13 500

DestinoCentro deDistribución

Pronóstico de lademanda a 3meses (unidades)

1 Boston 60002 Chicago 40003 St. Louis 20004 Lexigton 1500

Total 13 500

Problema de la Foster Problema de la Foster Generators CostosGenerators Costos

Origen Boston Chicago St Louis Lexigton ProducciónCleveland 3 2 7 6 5000Bedford 7 5 2 3 6000

York 2 5 4 5 2500Demanda 6000 4000 2000 1500

13500

13500

Costo por unidad distribuidaDestino

Problema de la Foster Problema de la Foster Generators Representación en Generators Representación en RedRed

O1

[5000]

O2

[6000]

O3

[2500]

D1 [6000]

[4000]

[2000]

[1500]

D2

D3

D4

332277

66

7755

2233

22 554455

Plantas

Nodos de Origen

Centros de Dist.

Nodos de DestinoRutas de Distribución

Arcos

Planteamiento matemáticoPlanteamiento matemáticoSea Z Z el costo total de transporte y sea xxijij (i=1,2,3;j=1,2,3,4) el número de unidades transportadas de la enlatadora i al almacén j.

)4,3,2,1;3,2,1(0

1500

2000

4000

6000

2500

6000

5000

545232

576723

342414

332313

322212

312111

34333231

24232221

14131211

343332312423

222114131211

jix

xxx

xxx

xxx

xxx

xxxx

xxxx

xxxx

xxxxxx

xxxxxxZ

ij

nesrestriccio las a Sujeta

Max

)4,3,2,1;3,2,1(0

1500

2000

4000

6000

2500

6000

5000

545232

576723

342414

332313

322212

312111

34333231

24232221

14131211

343332312423

222114131211

jix

xxx

xxx

xxx

xxx

xxxx

xxxx

xxxx

xxxxxx

xxxxxxZ

ij


Max

Solución óptima para el Solución óptima para el problema del transporte de la problema del transporte de la FosterFoster


York 2500 0 0 0 2500Demanda 6000 4000 2000 1500 39500

Unidades que se envíanDestino


York 2500 0 0 0 2500Demanda 6000 4000 2000 1500 39500

Unidades que se envíanDestino

COSTOCOSTO

Problema GeneralProblema General Se refiere (en sentido literal o figurado) a la

distribución de cualquier bien desde cualquier grupo de centros de suministro, llamados orígenesorígenes a cualquier grupo de centros de distribución llamados destinosdestinos de manera que se minimicen los costos totales de distribuciónminimicen los costos totales de distribución.

Unidades de un bien, m orígenes, n destinos, si recursos en el origen i, demanda dj en el destino j, costo cij por unidad distribuida desde el origen i al destino j.

El modelo generalEl modelo general

1 2 … n Recursos1 c11 c12 … c1n s1

Origen 2 c21 c22 … c2n s2… … … … …

m cm1 cm2 … cmn smDemanda d1 d2 … dn

DestinoCosto por unidad distribuida

Representación de red para el problema generalRepresentación de red para el problema general

S1[s1]

S2[s2

]

Sm

[sm]

D1 [-d1]

D2 [-d2]

Dm [-dm]

c11

c12

c1nc21 c22

c2n

cm1cm2

cmn

Planteamiento matemático modelo generalPlanteamiento matemático modelo general

.y para,0

,,...,2,1 para

,,...,2,1 para

a sujeta

min

1

1

1 1

jix

njdx

misx

xcZ

ij

m

jjij

n

jjij

m

i

n

jijij

.y para,0

,,...,2,1 para

,,...,2,1 para

a sujeta

min

1

1

1 1

jix

njdx

misx

xcZ

ij

m

jjij

n

jjij

m

i

n

jijij

Variantes del Problema

1. La oferta total no es igual a la demanda total

2. Maximización en lugar de minimización

3. Capacidades en las rutas o mínimos en las rutas

4. Rutas inaceptables

¿Cómo resolver en Excel?

Plantear tabla de datos especificando orígenes y destinos (de forma general). Plantear tabla de soluciones usando funciones apropiadas para estos problemas. Opción de problema de Programación Lineal , opción de No negatividad.

Problemas de AsignaciónProblemas de AsignaciónProblemas de AsignaciónProblemas de Asignación

IntroducciónIntroducción

El problema de asignaciónproblema 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 Ej.

empleados a trabajo máquinas a tareas períodos a tareas

Supocisiones de un problema de Supocisiones de un problema de asignaciónasignación

1. El número de asignados es igual al número de tareas (se denota por n). (esto puede variar)

2. Cada asignado se asigna exactamente 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).

5. El objetivo es determinar cómo deben hacerse las asignaciones para minimizar los costos totales.

Caso Fowle Marketing ResearchCaso Fowle Marketing Research

1 2 31. Terry 10 15 92. Carla 9 18 53. Roberto 6 14 3

Jefe deProyecto

Cliente

Tiempos estimados de terminación delproyecto (días)

Problema de la Fowle Problema de la Fowle Representación en RedRepresentación en Red

J1[1]

J2[1]

J3[1]

C1 [1]

[1]

[1]

C2

C3

10101515

99

991818

55

66 141433

Jefes de Proyecto

Nodos de Origen

Clientes

Nodos de Destino

Asignaciones Posibles

Arcos

Variables de decisión

así es no si

cliente al proyecto de jefe el asigna se si

0

1 jixij

Planteamiento matemáticoPlanteamiento matemáticoSea Z Z teimpo total de terminación

)4,3,2,1;3,2,1(0

1

1

1

1

1

1

3146518991510

332313

322212

312111

333231

232221

131211

333231232221131211

jix

xxx

xxx

xxx

xxx

xxx

xxx

xxxxxxxxxZ

ij


Max

)4,3,2,1;3,2,1(0

1

1

1

1

1

1

3146518991510

332313

322212

312111

333231

232221

131211

333231232221131211

jix

xxx

xxx

xxx

xxx

xxx

xxx

xxxxxxxxxZ

ij


Max

Solución ExcelSolución Excel

1 2 31. Terry 0 1 0 1 = 12. Carla 0 0 1 1 = 13. Roberto 1 0 0 1 = 1

1 1 1= = = Costo 261 1 1

AsignacionesJefe deProyecto

Cliente

Representación de red para el problema generalRepresentación de red para el problema general

S1[1]

S2[1]

Sm

[1]

D1 [1]

D2[1]

Dm [1]

c11c12

c1nc21 c22

c2n

cm1 cm2

cmn

Planteamiento matemático modelo generalPlanteamiento matemático modelo general

).y todapara binarias, (y para,0

,,...,2,1 para1

,,...,2,1 para1

a sujeta

min

1

1

1 1

jixjix

njx

mix

xcZ

ijij

m

jij

n

jij

ij

m

i

n

jij

).y todapara binarias, (y para,0

,,...,2,1 para1

,,...,2,1 para1

a sujeta

min

1

1

1 1

jixjix

njx

mix

xcZ

ijij

m

jij

n

jij

ij

m

i

n

jij

Ejemplos de Problemas de Ejemplos de Problemas de Transporte y AsignaciónTransporte y Asignación

Ejemplos de Problemas de Ejemplos de Problemas de Transporte y AsignaciónTransporte y Asignación

Problema Versatech Problema Versatech (Transporte)(Transporte)

La corporación Versatech producirá tres productos nuevos. En este momento, cinco de sus plantas tienen exceso de capacidad de producción. El costo unitario respectivo de fabricación del primer producto será de $31, $29, $32, $28 y $29, en las plantas 1, 2, 3, 4 y 5. El costo unitario respectivo de fabricación del segundo producto será de $45, $41, $46, $42 y $43 en las plantas respectivas 1, 2, 3, 4 y 5; y para el tercer producto será de $38, $35 y $40 en las plantas respectivas 1, 2 y 3, pero las plantas 4 y 5 no pueden fabricar este producto. Los pronósticos de ventas indican que la producción diaria debe ser 600, 1000 y 800 unidades de los productos 1, 2 y 3, respectivamente. Las plantas 1, 2, 3, 4 y 5 tienen capacidades para producir 400, 600, 400, 600 y 1000 unidades diarias; sin importar el producto o combinación de productos. Suponga que cualquier planta que tiene capacidad y posibilidad de fabricarlos podrá producir cualquiere combinación de productos en cualquier cantidad.

La gerencia desea asignar los nuevos productos a las La gerencia desea asignar los nuevos productos a las plantas con el mínimo costo total de fabricación.plantas con el mínimo costo total de fabricación.

Problema Versatech (Transporte)Datos

1 2 3Planta 1 $31 $45 $38 400Planta 2 $29 $41 $35 600Planta 3 $32 $46 $40 400Planta 4 $28 $42 - 600Planta 5 $29 $43 - 1000

Pr Diaria 600 1000 800

3000

Capacidad

2400

OrigenTipo de Producto

Tabla de Costos

Destino1 2 3

Planta 1 $31 $45 $38 400Planta 2 $29 $41 $35 600Planta 3 $32 $46 $40 400Planta 4 $28 $42 - 600Planta 5 $29 $43 - 1000

Pr Diaria 600 1000 800

3000

Capacidad

2400

OrigenTipo de Producto

Tabla de Costos

Destino

Problema Versatech (Transporte) Solución Excel

1 2 3Planta 1 0 0 200 200 <= 400Planta 2 0 0 600 600 <= 600Planta 3 0 0 0 0 <= 400Planta 4 600 0 0 600 <= 600Planta 5 0 1000 0 1000 <= 1000

Pr Diaria 600 1000 800 $88,400.00= = =

600 1000 800

Costo Mínimo

DestinoOrigen

CapacidadTipo de Producto

Tabla Cantidades (asignaciones a cada planta)

Problema Move-It (Transporte) IProblema Move-It (Transporte) I La compañía Move-It tiene dos plantas que producen montacargas que se mandan a tres centros de distribución. Los costos de producción unitarios son los mismos para las dos plantas y los costos de transporte (en cientos de dólares) por unidad para todas las combinaciones de planta y centro de distribución son los siguientes

1 2 3Planta A $800 $700 $400 50Planta B $600 $800 $500 50

Dist. Sem. ? ? ?Suma

DestinoCentro de Distribución

Tabla de Costos de Transporte

Origen

100

Capacidad

60

1 2 3Planta A $800 $700 $400 50Planta B $600 $800 $500 50




Origen

100

Capacidad

60

Problema Move-It (Transporte) IIProblema Move-It (Transporte) II

Se debe producir y mandar un total de 60 unidades por semana. Cada planta puede producir y mandar cualquier cantidad hasta un máximo de 50 unidades a la semana, de manera que hay una gran flexibilidad para dividir la producción total entra las dos plantas y reducir los costos de transporte.

El objetivo de la gerencia es determinar El objetivo de la gerencia es determinar cuánto se debe producir en cada planta cuánto se debe producir en cada planta y después, cuál debe ser el patrón de y después, cuál debe ser el patrón de embarque de manera que se minimice embarque de manera que se minimice el costo total de transporteel costo total de transporte

Problema Move IT Datos y Sol. Excel

1 2 3Planta A $800 $700 $400 50Planta B $600 $800 $500 50




Origen

100

Capacidad

60

1 2 3Planta A 0 0 50 50 <= 50Planta B 0 0 10 10 <= 50

Dist. Sem. 0 0 60 $25,000.0Suma COSTO Min.

=60

60

OrigenDestino

CapacidadCentro de Distribución

Cantidades por planta

Problema Move-It (Transporte) Problema Move-It (Transporte) ModificadoModificado

Resolver el problema de Move-It si cualquier centro de distribución puede recibir cualquier cantidad entre 10 y 30 montacargas por semana para reducir más el costo total de envío, siempre que el envío total a los tres centros sea igual a 60 montacargas por semana.

Problema Move IT (Transporte) Modificado Datos y Sol. Excel

1 2 3Planta A $800 $700 $400 50Planta B $600 $800 $500 50

Dist. Sem. 10-30 10-30 10-30Suma



Origen

100

Capacidad

60

1 2 3Planta A 0 10 30 40 <= 50Planta B 20 0 0 20 <= 50

Dist. Sem. 20 10 30 $31,000.0>=10 >=10 >=10 COSTO Min.<=30 <=30 <=30

Suma=60

60

OrigenDestino

CapacidadCentro de Distribución

Cantidades por planta

El entrenador de un equipo de natación debe asignar competidores para la prueba de 200 metros de relevo combinado que irán a las Olimpiadas Juveniles. Como muchos de sus mejores nadadores son rápidos en más de un estilo, no es fácil decidir qué nadador asignar cada uno de los cuatro estilos. Los cinco mejores nadadores y sus mejores tiempos (en segundos) en cada estilo son los siguientes.

Problema Natación (Asignación)Problema Natación (Asignación)

Carlos Cristy David Antony JoséDorso 37.7 32.9 33.8 37 35.4Pecho 43.4 33.1 42.2 34.7 41.8Mariposa 33.3 28.5 38.9 30.4 33.6Libre 29.2 26.4 29.6 28.5 31.1

Tiempo de Nado

Problema Natación (asignación) Problema Natación (asignación) SoluciónSolución

Carlos Cristy David Antony JoséDorso 0 0 1 0 0 1 = 1Pecho 0 0 0 1 0 1 = 1Mariposa 0 1 0 0 0 1 = 1Libre 1 0 0 0 0 1 = 1

1 1 1 1 0<= <= <= <= <=1 1 1 1 1

TIEMPO Min.

Tiempo de Nado

126.2

modelos cuantitativos 10.1-10.2

Documents