Problemas de Transporte Asignacion y Trasbordo
Transcript of Problemas de Transporte Asignacion y Trasbordo
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
1/46
Problemas de transporte,
asignacin y trasbordo
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
2/46
1. Plantear un problema de transporte
Tiene como objetivo encontrar el mejor plan de distribucin,
generalmente minimizando el coste.
Un problema est equilibradoo balanceado si la oferta es igual a
la demanda. En ese caso, en las restricciones se cumplirn lasigualdades correspondientes.
Para aplicar el simplex de transporte necesitamos que el problema
est equilibrado. Si no lo est, aadiremos una demanda ficticia
con costes nulos o una oferta ficticia con costes de penalizacin.
En una tabla representaremos el coste que supone transportar
cada unidad desde i hasta j.
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
3/46
1. Plantear un problema de transporte
Demandantes
Oferentes
Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 4Oferta
kWh (106)
Planta 1 8 6 10 9 35
Planta 2 9 12 13 7 50
Planta 3 14 9 16 5 40
Demanda 45 20 30 30
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
4/46
1. Plantear un problema de transporte
Modelo matemtico.
xijrepresenta la energa transportada desde la planta i hasta la ciudad j
Funcin a optimizar:
Min w = 8x11+6x12+10x13+9x14+9x21+12x22+13x23+7x24+14x31+ 9x32+16x33+5x34
Restricciones de demanda
x11+x21+x3145
x12+x22+x3220
x13+x23+x3330
x14+x24+x3430
Restricciones de oferta
x11+x12+x13+x1435
x21+x22+x23+x2450
x31+x32+x33+x3440
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
5/46
1. Plantear un problema de transporte
8
10
6
25
10 9
45
9 12
5
13 7
14
10
9 16 5
30
Las soluciones del problema las representamos en un Cuadro de Transporte:
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
6/46
2. El mtodo simplex para eltransporte
Para resolver un problema de transporte mediante el simplex,
debemos seguir los siguientes pasos:
Equilibrarel problema
Hallar una solucin inicial
Realizar las iteracioneso pivoteos necesarios hasta llegar a la
solucin final
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
7/46
Equilibrado del problema
Un problema est equilibrado si la demanda es igual a la oferta.
Si en un problema equilibrado todas las variables cumplen todas
las restricciones menos una, la restante tambin se cumple.
Circuito cerrado. Para que un circuito sea cerrado se debe cumplir
que:
La trazada sea cerrada
Dos celdas consecutivas siempre estn en la misma fila o
columna Tres celdas consecutivas no pueden estar en la misma fila o
columna
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
8/46
Clculo de una solucin inicial
Existen tres mtodos para calcular una solucin inicial:
Esquina Noroeste. Es el ms simple, pero proporciona unaprimera solucin no muy buena. No tiene en cuenta los costes.
Mnimo coste. La aproximacin es mejor que en el casoanterior.
Mtodo de Vogel. Proporciona la mejor solucin inicial, aunquees el ms tedioso y requiere calcular multas.
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
9/46
Clculo de una solucin inicial: esquina NO
Mtodo:
Empezando en la celda situada en la esquina superior izquierdaescribimos el nmero menor entre el correspondiente a la fila oa la columna.
Si hemos empleado el nmero de la fila, debemos tachar dichafila y restar dicho nmero del nmero correspondiente a lacolumna, y viceversa.
Nos volvemos a situar en la esquina superior izquierda yrepetimos el procedimiento.
Al finalizar, el nmero de celdas rellenadas debe ser igual alnumero de filas ms el nmero de columnas menos uno.
Nota: cuando solo quede una fila/columna podemos escribirdirectamente los nmeros.
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
10/46
Clculo de una solucin inicial: esquina NO
2 5
1
3
2 4 2 1
3
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
11/46
Clculo de una solucin inicial: esquina NO
2 3 3
1
3
2 4 2 1
1
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
12/46
Clculo de una solucin inicial: esquina NO
2 3 3
1 1
3
2 1 2 1
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
13/46
Clculo de una solucin inicial: esquina NO
2 3 3
1 1
0 2 1 3
2 1 2 1 f+c-1=6
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
14/46
Clculo de una solucin inicial:mnimo coste
Mtodo:
Nos situamos en la celda que tenga el mnimo coste.
Realizamos el mismo proceso que en el mtodo anterior de
escribir el nmero y tachar la fila o columna correspondiente.
Volvemos a colocarnos en la celda de mnimo coste ycontinuamos hasta llegar a la solucin.
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
15/46
Clculo de una solucin inicial:mnimo coste
8 6 10 935
9 12 13 7
50
14 9 16
30
540
45 20 30 30
10
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
16/46
Clculo de una solucin inicial:mnimo coste
8
20
6 10 935
9 12 13 7
50
14 9 16
30
510
45 20 30 30
15
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
17/46
Clculo de una solucin inicial:mnimo coste
15
8
20
6 10 915
9 12 13 7
50
14 9 16
30
510
45 20 30 3030
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
18/46
Clculo de una solucin inicial:mnimo coste
15
8
20
6 10 915
30
9 12 13 7
50
14 9 16
30
510
30 20 30 30
20
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
19/46
Clculo de una solucin inicial:mnimo coste
15
8
20
6 10 935
30
9 12
20
13 7
50
14 9
10
16
30
540
45 20 30 30 f+c-1=6
20
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
20/46
Clculo de una solucin inicial:mtodo de Vogel
Mtodo:
La multa de cada fila o columna es la diferencia entre los dosmenores costes de las celdas de dicha fila/columna.
Calculamos las multas de cada fila y de cada columna.
Escogemos la fila o columna de mayor multa.
Escogemos la columna o fila de menor coste.
Procedemos como en los casos anteriores.
Habr que recalcular las multas despus de tachar celdas.
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
21/46
Clculo de una solucin inicial:mtodo de Vogel
6 7 810 1
15 80 78
15 63
15 5 5
9 73 70
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
22/46
Clculo de una solucin inicial:mtodo de Vogel
65
7 810 1
15 80 78
15 63
15 5 5
9 73 70
5 2
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
23/46
Clculo de una solucin inicial:mtodo de Vogel
65
75
85 2
15 80 78
15 63
15 5 5
9 73 70
0
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
24/46
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
25/46
Resolucin iterativa del problema
Partiremos de una solucin inicial:
358 6 10 9
109
2012
2013 7
14 910
1630
5
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
26/46
Resolucin iterativa del problema
VB
c11=0=u1+v1-8
c21=0=u2+v1-9
c22=0=u2+v2-12c23=0=u2+v3-13
c33=0=u3+v3-16
c34=0=u3+v4-5
VNB
c12=u1+v2-6=5
c13=u1+v3-10=2
c14=u1+v4-9=-8c24=u2+v4-7=-5
c31=u3+v1-14=-2
c32=u3+v2-9=6
u1=0u2=1u3=4v1=8v2=11v3=12v4=1
Como estamos minimizando, la condicin deparada es que cij0
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
27/46
Resolucin iterativa del problema
Entra la VNB ms positiva (c32). Para hallar la nuevaiteracin seguiremos los siguientes pasos:
Hacemos un circuito cerrado con la variable que entra
Nombramos alternativamente par e impar a las celdas
Tomamos como valor de el de la celda impar ms pequea,
en este caso =10
Sumamos
a las celdas pares y restamos
de las impares
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
28/46
Resolucin iterativa del problema
20I
20P
-10 +10
10P
10I
+10 -10
3010
En caso de existir dos celdas de valor mnimo, unade ellas conservar el valor cero
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
29/46
Resolucin iterativa del problema
358 6 10 9
109
1012
3013 7
1410
9 1630
5
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
30/46
Resolucin iterativa del problema
VB
c11=0=u1+v1-8
c21=0=u2+v1-9
c22=0=u2+v2-12c23=0=u2+v3-13
c32=0=u3+v2-9
c34=0=u3+v4-5
VNB
c12=u1+v2-6=5
c13=u1+v3-10=2
c14=u1+v4-9=-2c24=u2+v4-7=1
c31=u3+v1-14=-8
c33=u3+v3-16=-6
u1=0u2=1u3=-2
v1=8v2=11v3=12v4=7
Entra la variable c12
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
31/46
Resolucin iterativa del problema
35
I
10
P
-10 +10
10
P
10
I
+10 -10
25
20
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
32/46
Resolucin iterativa del problema
258
106 10 9
209 12
3013 7
14
109 16
305
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
33/46
Resolucin iterativa del problema
VB
c11=0=u1+v1-8
c12=0=u1+v2-6
c21=0=u2+v1-9c23=0=u2+v3-13
c32=0=u3+v2-9
c34=0=u3+v4-5
VNB
c13=u1+v3-10=2
c14=u1+v4-9=-7
c22=u2+v2-12=-5c24=u2+v4-7=-4
c31=u3+v1-14=-3
c33=u3+v3-16=-1
u1=0u2=1u3=3
v1=8v2=6v3=12v4=2
Entra la variable c13
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
34/46
Resolucin iterativa del problema
25
I
10 25
P
-25 +25
20
P
30
I
+25 -25
En este caso las celdas escogidas para el circuito cerradono son contiguas. El circuito ser un rectngulo:
45 5
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
35/46
Resolucin iterativa del problema
Con lo que ya tenemos:
810
625
10 9
459 12
513 7
1410
9 1630
5
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
36/46
Resolucin iterativa del problema
Donde:
VB
c12=0=u1+v2-6
c13
=0=u2+v
1-10
c21=0=u2+v1-9
c23=0=u2+v3-13
c32=0=u3+v2-9
c34=0=u3+v4-5
u1=0u2=3
u3=3v1=6v2=6v3=10
v4=2
VNB
c11=u1+v1-8=-2
c14
=u1+v
4-9=-7
c22=u2+v2-12=-3
c24=u2+v4-7=-2
c31=u3+v1-14=-5
c33=u3+v3-16=-3
Dado que todas las cij0 hemos llegado a la solucin ptima
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
37/46
3. Problemas de asignacin
En este tipo de problemas cada trabajo se asocia por completo auna mquina. La variable xij toma los valores 1 si se asigna lamquina i al trabajo j y 0, en caso contrario.
Trabajo 1 Trabajo 2 Trabajo 3 Trabajo 4
Mquina 1 14 5 8 7
Mquina 2 2 12 6 5
Mquina 3 7 8 3 9
Mquina 4 2 4 6 10
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
38/46
3. Problemas de asignacin
Modelo matemtico
Funcin a optimizar:
Min w = 14x11+5x12+8x13+7x14+2x21+12x22+6x23+
5x24+7x31+8x32+3x33+9x34+2x41+4x42+6x43+10x44
Restricciones de la mquina:
x11+x12+x13+x14=1
x21+x22+x23+x24=1x31+x32+x33+x34=1
x41+x42+x43+x44=1
Restricciones del trabajo:
x11+x21+x31+x41=1
x12+x22+x32+x42=1x13+x23+x33+x43=1
x14+x24+x34+x44=1
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
39/46
3. Problemas de asignacin
Mtodo Hngaro.
En una matriz de costeshallamos el mnimo de cadafila
Se resta el mnimo de cadafila.
Repetimos el procedimientopara las columnas
14 5 8 7 5
2 12 6 5 2
7 8 3 9 3
2 4 6 10 2
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
40/46
3. Problemas de asignacin
9 0 3 2
0 10 4 3
4 5 0 6
0 2 4 8
0 0 0 2
9 0 3 0
0 10 4 1
4 5 0 4
0 2 4 6
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
41/46
3. Problemas de asignacin
Ahora debemos cubrir todos losceros con el mnimo nmeromposible de lneas.
Si n=dimensin de la matriz,
se termina el algoritmo
Si n
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
42/46
3. Problemas de asignacin
Al menor de los nmeros nocubiertos lo denominamos k(k=1).
Restamos k de los nmeros nocubiertos y lo sumamos a los queestn cubiertos por dos lneas, yrepito el paso anterior.
Como n=4=dimensin de la matrizfinaliza el algoritmo.
Ahora escojo 4 ceros de maneraque tenga un cero por fila ycolumna. Dichas celdascorresponden a las xij de valorunitario.
10 0 3 0
0 9 3 0
5 5 0 4
0 1 3 5
x12=x24=x33=x41=1
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
43/46
4. Problemas de trasbordo
En los problemas de trasbordo las unidades puedenpasar por lugares intermedios antes de llegar a sudestino.
Memphis
(150)
Denver(200)
NY
Chicago Boston(130)
LA
(130)
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
44/46
4. Problemas de trasbordo
Destino
Origen
Memphis Denver NY Chicago LA Boston
Memphis 0 - 8 13 25 28
Denver - 0 15 12 26 25
NY - - 0 6 16 17
Chicago - - 6 0 14 16
LA - - - - 0 -
Boston - - - - - 0
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
45/46
4. Problemas de trasbordo
Memphis y Denver son ciudades origen.
LA y Boston son ciudades destino.
NY y Chicago son ciudades de trasbordo: son tantoorigen como destino.
Como la oferta es superior a la demanda incluimos undemandante ficticio con costes nulos.
La mxima cantidad que puede pasar (entrar o salir)por cada punto de trasbordo es igual a la suma de lasofertas.
-
7/21/2019 Problemas de Transporte Asignacion y Trasbordo
46/46
4. Problemas de trasbordo
Destino
OrigenNY Chicago LA Boston
CiudadFicticia
Memphis
130
8 13 25 28
20
0
Denver15 12 26
130
25
70
0
NY 220
0 6
130
16 17 0
Chicago6
350
0
0
14 16 0