7/23/2019 09_IND2209_Alumno_15

1/47

Investigacin

de

OperacionesIND2209

Profesor:Pamelalvarez M.

Facultad de Ingeniera

Departamento de Ciencias de la Ingeniera

Unidad N6

7/23/2019 09_IND2209_Alumno_15

2/47

Unidad6:Programacinenredes(20%)

DefinicionesGenerales

Problemasclsicos

Algoritmosymtodosderesolucin

2

Programacin en redes

IND2209. Prof.: Pamela lvarez M.

7/23/2019 09_IND2209_Alumno_15

3/47

Recordemoslaformulacin:

3

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

1

i

m

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

1

j

n

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

OF

ERTA

DEM

ANDA

ORGENES DESTINOS

ia jb

7/23/2019 09_IND2209_Alumno_15

4/47

Modelomatemtico:

4

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

1 1

m n

ij ij

i j

in z c x

1

1,...,m

ij j

i

x b j n

1

1,...,n

ij ij

x a i m

0 1,..., ; 1,...,ijx i m j n

. .s a

Minimizacostosdetransporte

CapacidaddeOferta

Demandasolicitada

Nonegatividad

7/23/2019 09_IND2209_Alumno_15

5/47

Observaciones:

Segnloquehemosvistoenelcurso,cmosepuederesolver?

CmoeslamatrizAdeesteproblema?

TrabajemosconunProblemadeTransporteequilibrado,esdecir:

Enestecaso,cmoquedanlasrestricciones?

Cmopasar

de

un

problema

desequilibrado

auno

equilibrado?

5

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

1 1

m n

i j

i j

a b

7/23/2019 09_IND2209_Alumno_15

6/47

Cmopasardeunproblemadesequilibradoaunoequilibrado?

6

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

1 1

m n

i j

i j

a b

1 1

OFERTA DEMANDA

m n

i j

i j

a b

1

2

3

1

2

3

1 35a

2 50a

3 40a

4

1 40b

2 20b

3 30b

4 30b

F5 5 5b 5 0,ic i

7/23/2019 09_IND2209_Alumno_15

7/47

Cmopasardeunproblemadesequilibradoaunoequilibrado?

Infactible

Incorporarunapenalizacinpordemandainsatisfecha

7

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

1 1

m n

i j

i j

a b

1 1

OFERTA DEMANDA

m n

i j

i j

a b

7/23/2019 09_IND2209_Alumno_15

8/47

Ejemplo ProblemadeTransporte:

Unaempresaforestaltiene3huertosqueproducensemillasdepino

paralaforestacin.Lassemillassecultivanenloshuertosyluegoson

trasplantadasalosbosques. Enelaoactual,lossitiosdeplantacin

hansidopreparadosgeogrficamente.

Cadabosquevaraentamao,calidadytipodesuelo,demodoque

cadaunorequiereunacantidaddiferentedesemillas.

8

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

7/23/2019 09_IND2209_Alumno_15

9/47

Ejemplo ProblemadeTransporte:

Los3huertosestnlocalizadosenreasdiferentesytienendiferentes

capacidadesparalaproduccindelassemillas.Elmayorcosto

asociadoconlaoperacin,eseltransportedesemillashacialos

bosques.Latablasiguientemuestralosrequerimientosdelas

semillasdecadabosque,elnmerodesemillasdisponiblesencada

huertoyladistanciadesdecadahuertoacadabosque.Seasumeque

todosloscaminoshansidoconstruidosporlosmismosestndaresde

modoqueloscostosdetransportesonproporcionalesaladistancia.

9

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

7/23/2019 09_IND2209_Alumno_15

10/47

Ejemplo ProblemadeTransporte:

Sepideencontrarelplanptimodetransportequeminimicelos

costosdetransportedelsistema.

10

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Bosques

Huertos 1 2 3 4

Semillas

disponibles

(millones)1 8 19 22 6 52 15 6 16 5 13 7 8 9 12 2

Semillas

requeridas(millones)

2 3 2 1

7/23/2019 09_IND2209_Alumno_15

11/47

Ejemplo ProblemadeTransporte:

11

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

1

2

3

1

2

4

HUERTOS BOSQUES

3

5

1

2

2

3

2

1

7/23/2019 09_IND2209_Alumno_15

12/47

Ejemplo ProblemadeTransporte:

Modelo:

12

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

7/23/2019 09_IND2209_Alumno_15

13/47

Ejemplo ProblemadeTransporte:Tableau detransporte:

Filas orgenes

Columnas destinos

13

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

HuertosBosques

OFERTA1 2 3 4

1 8 19 22 6 5

2 15 6 16 5

1

3 7 8 9 12

2

DEMANDA 2 3 2 1 8/8

7/23/2019 09_IND2209_Alumno_15

14/47

Cmoresolverlo? Loprimeroquenecesitamoses

encontrarunaSolucinBsicaFactible(SBF).

14

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

SBFm+n1variablesbsicas

Degenerancia

HuertosBosques

OFERTA1 2 3 4

18 19 22 6

02 3

215 6 16 5

00 1

37 8 9 12

01 1

DEMANDA 0 0 0 0 8/8

7/23/2019 09_IND2209_Alumno_15

15/47

ExistenprocedimientosparaobtenerunaSBF:

Mtododelaesquinanoroeste

Mtododelcostomnimo

MtododeVogel

15

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

7/23/2019 09_IND2209_Alumno_15

16/47

Mtododelaesquinanoroeste:

Comenzarporlaceldaubicadaenlaesquinasuperiorizquierda.

Asignarlamayorcantidadposiblealavariablex11.

Continuarasignandohacialaderechaohaciaabajosegnsean

lasdemandas

yofertas

restantes.

16

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

7/23/2019 09_IND2209_Alumno_15

17/47

MtododelaesquinanoroesteEjemplo:

17

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Huertos Bosques OFERTA1 2 3 4

1 8 19 22 6

5

2 15 6 16 5

1

3 7 8 9 12

2

DEMANDA 2 3 2 1 8/8

7/23/2019 09_IND2209_Alumno_15

18/47

MtododelaesquinanoroesteEjemplo:

18

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

HuertosBosques

OFERTA1 2 3 4

1 8 19 22 6

52=32

2 15 6 16 5

1

3 7 8 9 12

2

DEMANDA 22=0 3 2 1 8/8

7/23/2019 09_IND2209_Alumno_15

19/47

MtododelaesquinanoroesteEjemplo:

19

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

HuertosBosques

OFERTA1 2 3 4

1 8 19 22 6

33=02 3

2 15 6 16 5

1

3 7 8 9 12

2

DEMANDA 0 33=0 2 1 8/8

7/23/2019 09_IND2209_Alumno_15

20/47

MtododelaesquinanoroesteEjemplo:

20

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

HuertosBosques

OFERTA1 2 3 4

1 8 19 22 6

02 3

2 15 6 16 5

11=01

3 7 8 9 12

2

DEMANDA 0 0 21=1 1 8/8

7/23/2019 09_IND2209_Alumno_15

21/47

MtododelaesquinanoroesteEjemplo:

21

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

HuertosBosques

OFERTA1 2 3 4

1 8 19 22 6

02 3

2 15 6 16 5

01

3 7 8 9 12

21=1

1DEMANDA 0 0 11=0 1 8/8

7/23/2019 09_IND2209_Alumno_15

22/47

MtododelaesquinanoroesteEjemplo:

22

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

HuertosBosques

OFERTA1 2 3 4

1 8 19 22 6

02 3

2 15 6 16 5

01

3 7 8 9 12

11=0

1 1DEMANDA 0 0 0 11=0 8/8

7/23/2019 09_IND2209_Alumno_15

23/47

MtododelaesquinanoroesteEjemplo:

23

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

HuertosBosques

OFERTA1 2 3 4

1 8 19 22 6

02 3

2 15 6 16 5

01

3 7 8 9 12

0

1 1DEMANDA 0 0 0 0 8/8

7/23/2019 09_IND2209_Alumno_15

24/47

MtododelaesquinanoroesteEjemplo:

24

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

HuertosBosques

OFERTA1 2 3 4

18 19 22 6

02 3

215 6 16 5

0

1

3

7 8 9 12 0

1 1

DEMANDA 0 0 0 0 8/8

11

12

13 14

21 22 24

23

31 32

33

34

2

3

0

0

1

0

1

1

x

x

x x

x x x

x

x x

x

x

SBFm+n1variablesbsicas

Ejemplo (3+41)=6

7/23/2019 09_IND2209_Alumno_15

25/47

Mtododelcostomnimo:

Elmtodoanteriornoconsideracostos,porlotantopuede

entregarSBFdealtocosto.

Estemtodoalconsiderarelcostobuscatratardereducirla

cantidad

de

iteraciones.

25

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

7/23/2019 09_IND2209_Alumno_15

26/47

Mtododelcostomnimo:

Enlaceldaquetienemenorcosto,asignarelmayorvalor

posible.Estoharquelafilaocolumnasesatisfaga

completamenteylaotraquedeconunsaldomayoroiguala

cero.

Eliminarlafilaocolumnaquequedsatisfecha.

Enlatablarestante,asignarelmayorvalorposiblealaceldade

menorcosto

Continuarhastaquequedeunasolafilaocolumna.

26

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

7/23/2019 09_IND2209_Alumno_15

27/47

Mtododelcostomnimo:

Nota:

Siemprelosempatesseresuelvenenformaarbitraria

Cuandounafilaounacolumnasesatisfaga

simultneamente,se

debe

eliminar

la

fila

ola

columna

en

formaarbitrariaylaotrapermanececonsaldocero.

27

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

7/23/2019 09_IND2209_Alumno_15

28/47

MtododelcostomnimoEjemplo:

28

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Huertos Bosques OFERTA1 2 3 4

1 8 19 22 6

5

2 15 6 16 5

1

3 7 8 9 12

2

DEMANDA 2 3 2 1 8/8

7/23/2019 09_IND2209_Alumno_15

29/47

MtododelcostomnimoEjemplo:

29

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Huertos Bosques OFERTA1 2 3 4

1 8 19 22 6

5

2 15 6 16 5

11=01

3 7 8 9 12

2

DEMANDA 2 3 2 11=0 8/8

7/23/2019 09_IND2209_Alumno_15

30/47

MtododelcostomnimoEjemplo:

30

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Huertos Bosques OFERTA1 2 3 4

1 8 19 22 6

5

2 15 6 16 5

11=00 1

3 7 8 9 12

2

DEMANDA 2 3 2 11=0 8/8

7/23/2019 09_IND2209_Alumno_15

31/47

MtododelcostomnimoEjemplo:

31

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Huertos Bosques OFERTA1 2 3 4

1 8 19 22 6

5

2 15 6 16 5

11=00 1

3 7 8 9 12

22=0

2DEMANDA 22=0 3 2 11=0 8/8

7/23/2019 09_IND2209_Alumno_15

32/47

MtododelcostomnimoEjemplo:

32

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Huertos Bosques OFERTA1 2 3 4

1 8 19 22 6

5

2 15 6 16 5

11=00 1

3 7 8 9 12

22=0

2 0DEMANDA 22=0 3 2 11=0 8/8

7/23/2019 09_IND2209_Alumno_15

33/47

MtododelcostomnimoEjemplo:

33

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Huertos Bosques OFERTA1 2 3 4

1 8 19 22 6

53=23

2 15 6 16 5

11=00 1

3 7 8 9 12

22=0

2 0DEMANDA 22=0 33=0 2 11=0 8/8

7/23/2019 09_IND2209_Alumno_15

34/47

MtododelcostomnimoEjemplo:

34

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Huertos Bosques OFERTA1 2 3 4

1 8 19 22 6 53=2

2=03 2

2 15 6 16 5

11=00 1

3 7 8 9 12

22=02 0

DEMANDA 22=0 33=0 22=0 11=0 8/8

7/23/2019 09_IND2209_Alumno_15

35/47

MtododelcostomnimoEjemplo:

35

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Huertos Bosques OFERTA1 2 3 4

1 8 19 22 6 53=2

22=03 2

2 15 6 16 5

11=00 1

3 7 8 9 12

22=02 0

DEMANDA 22=0 33=0 22=0 11=0 8/8

7/23/2019 09_IND2209_Alumno_15

36/47

MtododelcostomnimoEjemplo:

36

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Huertos Bosques OFERTA1 2 3 4

1 8 19 22 6 53=2

22=03 2

2 15 6 16 5

11=00 1

3 7 8 9 12

22=02 0

DEMANDA 22=0 33=0 22=0 11=0 8/8

2 * 7 3*19 0 * 6 0 *8 2 * 22 1*5 120z

7/23/2019 09_IND2209_Alumno_15

37/47

Mtododelcostomnimo:

Nonecesariamentegarantizaqueselogrencostosbajos

37

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

7/23/2019 09_IND2209_Alumno_15

38/47

MtododeVogel:

Calcularparacadacolumnayfilaunapenalizacin.

Penalizacin diferencia

entre

los

2costos

menores

en

la

columnaofilaquecorresponda.

Encontrarlamayorpenalizacin.

ElegircomoVBlademenorcostodeesafilaocolumna.

Asignarlamayorcantidaddeflujoposible.

Descartarfilaocolumna,

Recalcularofertasydemandas.

Repetirprocedimiento.

38

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

P i d P bl d T

7/23/2019 09_IND2209_Alumno_15

39/47

MtododeVogelEjemplo:

39

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Origen Destino OFERTA1 2 3

16 7 8

10

215 80 78

15

DEMANDA 15 5 5 25/25

P i d P bl d T t

7/23/2019 09_IND2209_Alumno_15

40/47

MtododeVogelEjemplo:

40

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Origen Destino OFERTA Penalizacin1 2 3

16 7 8

10 76=1

215 80 78

15 7815 =63

DEMANDA 15 5 5 25/25

Penalizacin 156=9 807=73 788=70

P i d P bl d T t

7/23/2019 09_IND2209_Alumno_15

41/47

MtododeVogelEjemplo:

41

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Origen Destino OFERTA Penalizacin1 2 3

16 7 8

10 76=1

215 80 78

15 7815 =63

DEMANDA 15 5 5 25/25

Penalizacin 156=9 807=73 788=70

P i d P bl d T t

7/23/2019 09_IND2209_Alumno_15

42/47

MtododeVogelEjemplo:

42

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Origen Destino OFERTA Penalizacin1 2 3

16 7 8 10 5

=5 86=2

5

215 80 78

15 7815 =63

DEMANDA 15 55=0 5 25/25

Penalizacin 156=9 788=70

Programacin en redes Problema de Transporte

7/23/2019 09_IND2209_Alumno_15

43/47

MtododeVogelEjemplo:

43

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Origen Destino OFERTA Penalizacin1 2 3

16 7 8 10 5

=5 86=2

5

215 80 78

15 7815 =63

DEMANDA 15 55=0 5 25/25

Penalizacin 156=9 788=70

Programacin en redes Problema de Transporte

7/23/2019 09_IND2209_Alumno_15

44/47

MtododeVogelEjemplo:

44

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Origen Destino OFERTA Penalizacin1 2 3

16 7 8

55 =0 5 5

215 80 78

15

DEMANDA 15 55=0 5 5=0 25/25

Penalizacin 156=9

Programacin en redes Problema de Transporte

7/23/2019 09_IND2209_Alumno_15

45/47

MtododeVogelEjemplo:

45

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Origen Destino OFERTA Penalizacin1 2 3

16 7 8

55 =0 0 5 5

215 80 78

15

DEMANDA 15 0=15 55=0 5 5=0 25/25

Penalizacin

Programacin en redes Problema de Transporte

7/23/2019 09_IND2209_Alumno_15

46/47

MtododeVogelEjemplo:

46

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.

Origen Destino OFERTA Penalizacin1 2 3

16 7 8

55 =0 0 5 5

215 80 78 15

15=0

15

DEMANDA 15 15=0 55=0 5 5=0 25/25

Penalizacin

Programacin en redes Problema de Transporte

7/23/2019 09_IND2209_Alumno_15

47/47

Enloscasosvistos,elproblemaoriginaldetransporteesde

minimizar

Paraproblemasdemaximizacin:

Mtododelaesquinanoroeste igual.

Mtodo

del

costo

mnimo

Asignar

a

los

mayores

beneficios. MtododeVogel lapenalizacinsecalculaconlos2mayores

beneficios

47

Programacin en redes Problema de Transporte

IND2209. Prof.: Pamela lvarez M.