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



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.



Introducción 2..

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



Problemas de TransporteProblemas de Transporte

Problemas de TransporteProblemas de Transporte



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



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



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 %&& %&&&



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



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


Max



"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#"$#



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 .



'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



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



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

≥

==

==

=

∑

∑

∑ ∑

=

=

= =



(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



)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.



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



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



"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.



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)



!ptimalcost "

# (liente * (liente (liente 3

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

@oberto Assign *4 3



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



Iariables de decisión

=así esnosi

clientealproyectode jefeelasignasesi

0

1 ji x

ij

Pl i ! iPl t i t t !ti



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


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


Max



"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



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



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

≥

==

==

=

∑

∑

∑∑

=

=

= =



./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



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.



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



/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&&



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)



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



Origen

)11

Capacidad

21



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



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



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



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.



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



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



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



!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 %&



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

[email protected] 7in6

Tiempo de ?ado

*26*

Documents

ejercicios asignacion transporte.ppt