09_IND2209_Alumno_15
Transcript of 09_IND2209_Alumno_15
-
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.