ejercicios asignacion transporte.ppt

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 1/40

Problemas de Transporte y AsignaciónProblemas de Transporte y Asignación

Problemas de Transporte y AsignaciónProblemas de Transporte y Asignación

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 2/40

Introducción 1..

  Los  problemas de transporte problemas de transporte sonproblemas especiales de programaciónlineal que reciben ese nombre debido a

que muchas de sus aplicacionesinvolucran determinar la manera óptimade transportar bienes.

  Los  problemas de asignación problemas de asignación incluyen

aplicaciones tales como asignar personasa tareas. Aunque sus aplicacionesparecen diferir de las del problema deltransporte, constituye un caso particular.

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 3/40

Introducción 2..

  Los problemas de transporte yasignación son casos particulares deun grupo más grande de problemas,llamados  problemas de fujo enredes.

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 4/40

Problemas de TransporteProblemas de Transporte

Problemas de TransporteProblemas de Transporte

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 5/40

Problema de la FosterProblema de la FosterGeneratorsGenerators 

Se transporta un producto desde 3

plantas hasta 4 centros de distribución

Origen PlantaCapacidad deProducción en 3

meses (unidades)1 Cleveland 5000

2 Bedford 60003 York 2500

Total 13 500

Destino  Centro de

Distribución

Pronóstico de la

demanda a 3

meses (unidades)

1 Boston 6000

2 Chicago 4000

3 St. Lois 2000

4 Le!igton 1500

Total 13 500

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 6/40

Problema de la FosterProblema de la FosterGenerators CostosGenerators Costos

Origen Boston Chicago St ouis e!igton ProducciónCle"eland   3 2 " 6 5000

Bed#ord   " 5 2 3 6000

 $or%   2 5 4 5 2500

Demanda   6000 4000 2000 1500

13500

13500

Costo por unidad distribuida

Destino

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 7/40

S!L

!ptimalcost "#3$%&& 'oston (hicago St Louis Le)igton

(leveland 3%&& *%&&'edford %&& &&& *%&&

 -or %&&

/rom 0o Shipment(ost perunit

Shipmentcost

(leveland 'oston 3%&& 3 *&%&&

(leveland (hicago *%&& 3&&&

'edford (hicago %&& % *%&&'edford St Louis &&& 4&&&

'edford Le)igton *%&& 3 4%&&

 -or 'oston %&& %&&&

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 8/40

Problema de la FosterProblema de la FosterGenerators Representación enGenerators Representación enRedRed

!*1%&&&2

!

1&&&2

!3

1%&&2

* 1&&&2

14&&&2

1&&&2

1*%&&2

3

4

 3 3

22

7 7 6  6  

 7 7 5 5

223 3 

  2  2  5 54455

Plantas

Nodos de Origen

Centros de ist.Nodos de Destino

Rutas deistribución

 Arcos

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 9/40

Planteamiento matem!ticoPlanteamiento matem!ticoSea Z Z el costo total de transporte y sea  x  x 

ijij 5i"*,,36 j"*,,3,47

el n8mero de unidades transportadas de la enlatadora i alalmac9n j.

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

1500

2000

4000

6000

2500

60005000

545232

576723

342414

332313

322212

312111

34333231

24232221

14131211

343332312423

222114131211

==≥

=++

=++

=++

=++

=+++

=+++

=+++

+++++

++++++=

  ji x

 x x x

 x x x

 x x x

 x x x

 x x x x

 x x x x x x x x

 x x x x x x

 x x x x x x Z 

ij

nesrestricciolasaSujeta

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

==≥

=++

=++

=++

=++

=+++

=+++

=+++

+++++

++++++=

  ji x

 x x x

 x x x

 x x x

 x x x

 x x x x

 x x x x x x x x

 x x x x x x

 x x x x x x Z 

ij

nesrestricciolasaSujeta

Max

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 10/40

"olución óptima para el"olución óptima para elproblema del transporte de laproblema del transporte de la

FosterFoster

Origen Boston Chicago St ouis e!igton Producción

Cle"eland   3500 1500 0 0 5000

Bed#ord   0 2500 2000 1500 6000

 $or%   2500 0 0 0 2500

Demanda   6000 4000 2000 1500 3#500

&nidades 'ue se en"(an

DestinoOrigen Boston Chicago St ouis e!igton Producción

Cle"eland   3500 1500 0 0 5000

Bed#ord   0 2500 2000 1500 6000

 $or%   2500 0 0 0 2500

Demanda   6000 4000 2000 1500 3#500

&nidades 'ue se en"(an

Destino

C#"$#C#"$#

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 11/40

Problema GeneralProblema General

  Se re:ere 5en sentido literal o :gurado7 a ladistribución de cualquier bien desde cualquiergrupo de centros de suministro, llamadosor%&enesor%&enes  a cualquier grupo de centros de

distribución llamados destinosdestinos de manera que seminimicen los costos totales de distribuciónminimicen los costos totales de distribución.

;nidades de un bien, m or<genes, n destinos, si   recursos en el origen  i  , de$anda  d  j   en el

destino  j , costo  cij  %or nidad  distri&ida desde el

origen i al destino  j .

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 12/40

'l modelo &eneral'l modelo &eneral

) * + n ,ecursos

)   c11 c12 ' c1n s1

Origen *   c21 c22 ' c2n s2

' ' ' ' '

m  c$1 c$2 ' c$n s$

Demanda   d1 d2 ' dn

Destino

Costo por unidad distribuida

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 13/40

Representación de red para el problema &eneralRepresentación de red para el problema &eneral

S*1s*2

S1s

2

S

m

1sm2

* 1=d*2

1=d2

m 1=dm2

c**

c*

c*nc*c

cn

cm*c

m

cmn

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 14/40

Planteamiento matem!tico modelo &eneralPlanteamiento matem!tico modelo &eneral

.y para,0

,,...,2,1 para

,,...,2,1 para

asujeta

min

1

1

1 1

  ji x

n  jd  x

mi s x

 xc Z 

ij

m

  j

  jij

n

  j

  jij

m

i

n

  j

ijij

≥

==

==

=

∑

∑

∑ ∑

=

=

= =

.y para,0

,,...,2,1 para

,,...,2,1 para

asujeta

min

1

1

1 1

  ji x

n  jd  x

mi s x

 xc Z 

ij

m

  j

  jij

n

  j

  jij

m

i

n

  j

ijij

≥

==

==

=

∑

∑

∑ ∑

=

=

= =

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 15/40

(ariantes del Problema

*. La oferta total no es igual a lademanda total

. >a)imi?ación en lugar deminimi?ación

3. (apacidades en las rutas om<nimos en las rutas

4. @utas inaceptables

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 16/40

)Cómo resol*er en '+cel,

  lantear tabla de datos especi:candoor<genes y destinos 5de forma general7.

  lantear tabla de soluciones usandofunciones apropiadas para estosproblemas.

  !pción de problema de rogramaciónLineal , opción de Bo negatividad.

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 17/40

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

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 18/40

IntroducciónIntroducción

 Cl problema de asi&naciónproblema de asi&nación es untipo especial de problema deprogramación lineal en el que los

asignados son recursos destinados ala reali?ación de tareas

 CD.

  empleados a trabaDo  máquinas a tareas

  per<odos a tareas

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 19/40

"upocisiones de un problema de"upocisiones de un problema deasi&naciónasi&nación

*. Cl n8mero de asignados es igual al n8merode tareas 5se denota por n7. 5esto puedevariar7

. (ada asignado se asigna e)actamente auna tarea.

3. (ada tarea debe reali?arla e)actamente un asignado.

4. C)iste un costo cij asociado con el asignadoi 5i"*,,E,n7.

%. Cl obDetivo es determinar cómo debenhacerse las asignaciones para minimi?ar los

costos totales.

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 20/40

Caso Fo-le ar/etin& Researc0Caso Fo-le ar/etin& Researc0

* 3

1. Terr( 10 15 #

2. Carla # 1) 5

3. *o&erto 6 14 3

-e#e deProyecto

Cliente

Tiempos estimados de terminación del

proyecto (das)

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 21/40

!ptimalcost "

# (liente * (liente (liente 3

 0erry *& Assign *% $Farla $ *G Assign %

@oberto Assign *4 3

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 22/40

Problema de la Fo-leProblema de la Fo-leRepresentación en RedRepresentación en Red

 H*1*2

 H1*2

 H31*2

(* 1*2

1*2

1*2

(

(3

111515

2 2 

 2 2

11

5 5 

  6  6  1 4 1 433

 ees de Pro6ecto

Nodos de Origen

Clientes

Nodos deDestino

7si&nacionesPosibles

 Arcos

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 23/40

Iariables de decisión

=así esnosi

 clientealproyectode jefeelasignasesi

0

1  ji x

ij

Pl i ! iPl t i t t !ti

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 24/40

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

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

1

1

1

1

11

3146518991510

332313

322212

312111

333231

232221

131211

333231232221131211

==≥

=++

=++

=++

=++

=++

=++

++++++++=

  ji x

 x x x

 x x x

 x x x

 x x x

 x x x x x x

 x x x x x x x x x Z 

ij

nesrestricciolasaSujeta

Max

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

11

1

1

1

1

3146518991510

332313

322212

312111

333231

232221

131211

333231232221131211

==≥

=++

=++

=++

=++

=++

=++

++++++++=

  ji x

 x x x

 x x x

 x x x

 x x x

 x x x

 x x x

 x x x x x x x x x Z 

ij

nesrestricciolasaSujeta

Max

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 25/40

"olución '+cel"olución '+cel

) * 31. Terr( 0 1 0 1 + 1

2. Carla 0 0 1 1 + 1

3. *o&erto 1 0 0 1 + 1

1 1 1+ + + Costo 26

1 1 1

Asignaciones

-e#e de

Proyecto

Cliente

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 26/40

Representación de red para el problema &eneralRepresentación de red para el problema &eneral

S*1*2

S

1*2

S

m

1*2

* 1*2

1*2

m 1*2

c**

c*

c*n

c* c

cn

cm* cm

cmn

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 27/40

Planteamiento matem!tico modelo &eneralPlanteamiento matem!tico modelo &eneral

).ytoda para binarias, (y para,0

,,...,2,1 para1

,,...,2,1 para1

asujeta

min

1

1

1 1

 ji x ji x

n j x

mi x

 xc Z 

ijij

m

 j

ij

n

 j

ij

ij

m

i

n

 j

ij

≥

==

==

=

∑

∑

∑∑

=

=

= =

).ytoda para binarias, (y para,0

,,...,2,1 para1

,,...,2,1 para1

asujeta

min

1

1

1 1

 ji x ji x

n j x

mi x

 xc Z 

ijij

m

 j

ij

n

 j

ij

ij

m

i

n

 j

ij

≥

==

==

=

∑

∑

∑∑

=

=

= =

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 28/40

./emplos de Problemas de./emplos de Problemas de

Transporte y AsignaciónTransporte y Asignación

./emplos de Problemas de./emplos de Problemas de

Transporte y AsignaciónTransporte y Asignación

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 29/40

Problema (ersatec0Problema (ersatec08$ransporte98$ransporte9La corporación Iersatech producirá tres productos nuevos. Cn

este momento, cinco de sus plantas tienen e)ceso de capacidad

de producción. Cl costo unitario respectivo de fabricación delprimer producto será de #3*, #$, #3, #G y #$, en las plantas*, , 3, 4 y %. Cl costo unitario respectivo de fabricación delsegundo producto será de #4%, #4*, #4, #4 y #43 en lasplantas respectivas *, , 3, 4 y %6 y para el tercer producto será

de #3G, #3% y #4& en las plantas respectivas *, y 3, pero lasplantas 4 y % no pueden fabricar este producto. Los pronósticosde ventas indican que la producción diaria debe ser &&, *&&& yG&& unidades de los productos *, y 3, respectivamente. Lasplantas *, , 3, 4 y % tienen capacidades para producir 4&&, &&,

4&&, && y *&&& unidades diarias6 sin importar el producto ocombinación de productos. Suponga que cualquier planta quetiene capacidad y posibilidad de fabricarlos podrá producircualquiere combinación de productos en cualquier cantidad.

:a &erencia desea asi&nar los nue*os productos a las:a &erencia desea asi&nar los nue*os productos a las

plantas con el m%nimo costo total de abricación.plantas con el m%nimo costo total de abricación.

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 30/40

Problema (ersatec08$ransporte9

atos

1 2 3,lanta 1 -31 -45 -3) 011

,lanta 2 -2# -41 -35 211

,lanta 3 -32 -46 -40 011

,lanta 4 -2) -42 211

,lanta 5 -2# -43 111Pr Diaria 211 111 11

3111

Capacidad

*011

Origen

Tipo de Producto

Tabla de Costos

Destino

1 2 3,lanta 1 -31 -45 -3) 011

,lanta 2 -2# -41 -35 211

,lanta 3 -32 -46 -40 011

,lanta 4 -2) -42 211

,lanta 5 -2# -43 111Pr Diaria 211 111 11

3111

Capacidad

*011

Origen

Tipo de Producto

Tabla de Costos

Destino

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 31/40

/rom 0o Shipment(ost per

unitShipment

cost

Lanta * rod 3 && 3G J&&

Lanta * ummy && & &

Lanta rod & 4* &

Lanta rod 3 && 3% *&&&

Lanta 3 ummy 4&& & &Lanta 4 rod * && G *G&&

Lanta % rod * & $ &

Lanta % rod *&&& 43 43&&&

Knterp. La planta * produce del producto tres && unidades a un costo de 3G cutotal SJ&&

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 32/40

Problema (ersatec08$ransporte9 "olución '+cel

1 2 3

,lanta 1 0 0 200   *11   /+   011,lanta 2 0 0 600   211   /+   211

,lanta 3 0 0 0   1   /+   011

,lanta 4 600 0   1 211   /+   211

,lanta 5 0 1000   1 111   /+   111

Pr Diaria 211 111 11   45011611+ + +

211 111 11

Costo 7nimo

Destino

Origen

CapacidadTipo de Producto

Tabla Cantidades (asignaciones a cada planta)

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 33/40

Problema o*e;It 8$ransporte9 IProblema o*e;It 8$ransporte9 I

  La compaM<a >ove=Kt tiene dos plantas que

producen montacargas que se mandan a trescentros de distribución. Los costos de producciónunitarios son los mismos para las dos plantas y loscostos de transporte 5en cientos de dólares7 por

unidad para todas las combinaciones de planta ycentro de distribución son los siguientes

1 2 3

,lanta -)00 -"00 -400 81

,lanta B -600 -)00 -500 81

Dist6 Sem6 9 9 9

Suma

Destino

Centro de Distribución

Tabla de Costos de Transporte

Origen

)11

Capacidad

21

1 2 3

,lanta -)00 -"00 -400 81

,lanta B -600 -)00 -500 81

Dist6 Sem6 9 9 9

Suma

Destino

Centro de Distribución

Tabla de Costos de Transporte

Origen

)11

Capacidad

21

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 34/40

Problema o*e;It 8$ransporte9 IIProblema o*e;It 8$ransporte9 II

  Se debe producir y mandar un total de &

unidades por semana. (ada planta puedeproducir y mandar cualquier cantidad hastaun má)imo de %& unidades a la semana, demanera que hay una gran Ne)ibilidad paradividir la producción total entra las dosplantas y reducir los costos de transporte.

'l ob<eti*o de la &erencia es determinar'l ob<eti*o de la &erencia es determinar

cu!nto se debe producir en cada plantacu!nto se debe producir en cada planta6 despu=s> cu!l debe ser el patrón de6 despu=s> cu!l debe ser el patrón deembar?ue de manera ?ue se minimiceembar?ue de manera ?ue se minimice

el costo total de transporteel costo total de transporte

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 35/40

Problema o*e I$atos 6 "ol. '+cel

1 2 3

,lanta -)00 -"00 -400 81

,lanta B -600 -)00 -500 81

Dist6 Sem6 9 9 9

Suma

Destino

Centro de Distribución

Tabla de Costos de Transporte

Origen

)11

Capacidad

21

1 2 3,lanta 0 0 50 81 :; 81

,lanta B 0 0 10 )1 :; 81

Dist6 Sem6 1 1 21 4*8511161

Suma COSTO 7in6

+

21

21

OrigenDestino

CapacidadCentro de Distribución

Cantidades por planta

Problema o*e It 8$ransporte9Problema o*e;It 8$ransporte9

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 36/40

Problema o*e;It 8$ransporte9Problema o*e;It 8$ransporte9odi@cadoodi@cado

 @esolver el problema de >ove=Kt

si cualquier centro dedistribución puede recibircualquier cantidad entre *& y 3&montacargas por semana parareducir más el costo total de

env<o, siempre que el env<o totala los tres centros sea igual a &montacargas por semana.

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 37/40

Problema o*e I$ 8$ransporte9odi@cado atos 6 "ol. '+cel

1 2 3

,lanta -)00 -"00 -400 81

,lanta B -600 -)00 -500 81

Dist6 Sem6 )1<31 )1<31 )1<31

Suma

Destino

Centro de Distribución

Tabla de Costos de Transporte

Origen

)11

Capacidad

21

1 2 3

,lanta 0 10 30 01 :; 81,lanta B 20 0 0 *1 :; 81

Dist6 Sem6 *1 )1 31 43)511161

=;)1 =;)1 =;)1 COSTO 7in6

:;31 :;31 :;31

Suma

+

21

21

OrigenDestino

CapacidadCentro de Distribución

Cantidades por planta

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 38/40

Cl entrenador de un equipo de natación debe

asignar competidores para la prueba de &&metros de relevo combinado que irán a las!limpiadas Huveniles. (omo muchos de sus meDoresnadadores son rápidos en más de un estilo, no esfácil decidir qu9 nadador asignar cada uno de loscuatro estilos. Los cinco meDores nadadores y susmeDores tiempos 5en segundos7 en cada estilo sonlos siguientes.

Problema Aatación 87si&nación9Problema Aatación 87si&nación9

Carlos Cristy Da"id Antony -os>Dorso 3"." 32.# 33.) 3" 35.4

Pecho   43.4 33.1 42.2 34." 41.)

7ariposa   33.3 2).5 3).# 30.4 33.6

ibre   2#.2 26.4 2#.6 2).5 31.1

Tiempo de ?ado

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 39/40

!ptimalcost "#*J. (arlos (risty avid Antony Hos9

orso 3J.J 3.$Assign33.G 3J 3%.4

echo 43.4 33.* 4.Assign34.J 4*.G

>ariposa 33.3AssignG.% 3G.$ 3&.4 33.

LibreAssign$. .4 $. G.% 3*.*

) %& %& %& %& Assign %&

7/23/2019 ejercicios asignacion transporte.ppt

http://slidepdf.com/reader/full/ejercicios-asignacion-transporteppt 40/40

Problema Aatación 8asi&nación9Problema Aatación 8asi&nación9"olución"olución

Carlos Cristy Da"id Antony -os>

Dorso 0 0 1 0 0 1 + 1Pecho   0 0 0 1 0 1 + 1

7ariposa   0 1 0 0 0 1 + 1

ibre   1 0 0 0 0 1 + 1

1 1 1 1 0

/+ /+ /+ /+ /+

1 1 1 1 1

T@.7PO 7in6

Tiempo de ?ado

*26*