apunte_n0_14_transporte

Vista previa del material en texto

Transporte, Página 1
METODOS DE OPTIMIZACION
APUNTE Nº 14
TRANSPORTE
Este problema consiste en la distribución de un cierto producto desde varias
fuentes a diversos destinos. Si suponemos que se dispone de m bodegas y n
mercados que demandan este tipo de bien, entonces, existirá un flujo desde m
hacia n según condiciones especificas de oferta y demanda.
Se designa como:
Ai : Cantidad disponible en cada uno de los i depósitos.
Cij : Costo unitario de transporte desde un deposito i hasta un mercado j
Bj : Demanda de cada uno de los j mercados
La formulación del problema:
MIN C = ΣΣ Cij Xij Costo Total del transporte
S/a
Σ Xij ≤ ai i=1,2,3...m Oferta del deposito
Σ Xij ≤ bj j=1,2,3...n Demanda del Mercado
Xij ≤ 0
Xij: Es la cantidad a transportar desde un deposito i hasta un mercado j.
En principio, es posible resolver el problema de transporte utilizando el algoritmo
SIMPLEX, pero dada la estructura especial de este (todos los coeficientes de las
variables en las restricciones con 0 ó 1) existen otros algoritmos mas simples.
El problema de transporte se expresa de la siguiente forma:
Suponemos un problema de 3 depósitos y 4 mercados:
Depositos\Mercados M1 M2 M3 M4 Oferta
D1
C11
X11
C12
X12
C13
X13
C14
X14 a1
D2
C21
X21
C22
X22
C23
X23
C24
X24 a2
D3
C31
X31
C32
X32
C33
X33
C34
X34 a3
Demanda b1 b2 b3 b4 Σb \ Σa
Transporte, Página 2
SOLUCION BASICA FACTIBLE
El problema estandar de transporte tiene (n + m) restricciones y (n*m) variables.
En general, el numero de variables esta dado por el numero de restricciones
independientes. En un problema de transporte, el numero de vatriables basicas
será (n + m – 1) debido a que existe una restriccion que es redundante.
METODOLOGIAS PARA ENCONTRAR UNA SOLUCION BASICA FACTIBLE
INICIAL
 ESQUINA NOR-OESTE: Consiste en satisfacer las ofertas a partir del casillero
localizado en la esquina nor oeste.
Ejemplo:
Depositos\Mercados M1 M2 M3 M4 Oferta
D1
2
3
2 2 1
3
D2
10
1
8
3
5
3
4
7
D3
7 6 6
1
8
4 5
Demanda 4 3 4 4 15 \ 15
Costo Total = 3*2+1*10+3*8+3*5+1*6+4*8 = 93
 COSTO MENOR: Consiste en asignar la mayor cantidad de bienes o productos
a aquellos casilleros donde el costo de transporte es menor.
Depositos\Mercados M1 M2 M3 M4 Oferta
D1
2 2 2 1
3 3
D2
10
2
8 5
4
4
1 7
D3
7
2
6
3
6 8
4 5
Demanda 4 3 4 4 15 \ 15
Costo Total = 2*10+2*7+3*6+4*5+3*1+1*4+4*8 = 79
Transporte, Página 3
 VOGEL: Esta basado en la idea de costo de oportunidad, consiste:
1. Sacar la diferencia entre los dos menores costos de cada fila y columna.
2. Se escoge la mayor diferencia
3. Se escoge el casillero con menor costo de transporte y se asigna la máxima
cantidad posible.
Depositos\Mercados M1 M2 M3 M4 Oferta
D1
2
3
2 2 1
3
D2
10 8 5
3
4
4 7
D3
7
1
6
3
6
1
8
5
Demanda 4 3 4 4 15 \ 15
Costo Total = 3*2+1*7+3*6+3*5+1*6+4*4 = 68
Tarea: Resolver por los tres métodos el siguiente ejercicio:
La compañía IMFC se dedica a fabricar lápices, esta compañía tiene sus plantas
en Rancagua, Talca y Concepción. Sus centros de consumo son: Curico y
Temuco, los cuales demandan mensualmente 4.600 y 2.800 unidades
respectivamente.
Las capacidades mensuales de producción de las plantas es de 3.000 para
Rancagua, 3.600 para Talca y 4.500 para Concepción.
Los costos de traslado desde las plantas a los centros de consumo se detallan en
la siguiente tabla:
Pesos por unidad Curico Temuco
Rancagua 16 43
Talca 20 22
Concepción 21 14
¿qué pasa con el ejercicio si la tabla anterior son ingresos por unidad? (resuelva el
ejercicio por los tres métodos)
Transporte, Página 4
 METODO OPTIMIZANTE: este método se basa en holguras complementarias
del problema de transporte original y su dual. De esta forma se deberá
determinar números ui para los depósitos y vj para los mercados, tal que:
Cij = Cij –ui – vj
Cij = 0 Para toda variable básica (lo mismo que en el simplex)
Si todos los Cij son positivos, significa que el cuadro es la solución optima, en
caso contrario, existirá una variable no básica candidata tal que para esa variable
su costo reducido es el mínimo Cij.
Para comenzar el método optrimizante es necesario escoger la columna o fila con
menor cantidad de soluciones y asignar ui ó vj igual a cero.
Se tiene la siguiente solución ( por vogel), determinar si es la mas optima, si no lo
es, determinarla.
Depositos\Mercados M1 M2 M3 M4 Oferta ui
D1
2 2 2 1
3 3 -3
D2
10
2
8 5
4
4
1 7 0
D3
7
2
6
3
6 8
4 5 -3
Demanda 4 3 4 4 15 \ 15
vj 10 9 5 4
Considerando U2=0, se tiene:
C21´= C21-U2-V1=0 Por lo tanto V1=10
C23´= C23-U2-V3=0 Por lo tanto V3=5
C24´= C24-U2-V4=0 Por lo tanto V4=4
C14´= C14-U1-V4=0 Por lo tanto U1=-3
C31´= C31-U3-V1=0 Por lo tanto U3=-3
C32´= C32-U3-V2=0 Por lo tanto U3=-3
Transporte, Página 5
Con esto determinamos los costos reducidos:
C11´= C11-U1-V1= -5 Esta puede entrar a la base , θ =2
C12´= C12-U1-V2= -4
C13´= C13-U1-V3= 0
C22´= C22-U2-V2= -1
C33´= C33-U3-V3= 4
C34´= C34-U3-V4= 7
Depositos\Mercados M1 M2 M3 M4 Oferta ui
D1
-5 2
θ
-4 2 0 2 0 1
3- θ 3 -3
D2
0 10
2- θ
-1 8 0 5
4
0 4
1+ θ 7 0
D3
0 7
2
0 6
3
4 6 7 8
4 5 -3
Demanda 4 3 4 4 15 \ 15
vj 10 9 5 4
Ahora la nueva solución:
Depositos\Mercados M1 M2 M3 M4 Oferta
D1
 2
2
2 2 1
1 3
D2
10
0
8 5
4
4
3 7
D3
7
2
6
3
6 8
4 5
Demanda 4 3 4 4 15 \ 15
El nuevo costo total es 2*2+2*7+3*6+4*5+1*1+3*4=69
Ahora es necesario verificar si existe otra solución mas optima, efectuando
nuevamente el método optimizante.
Transporte, Página 6
Depositos\Mercados M1 M2 M3 M4 Oferta ui
D1
0 2
2+ θ
1 2 0 2 0 1
1- θ 3 2
D2
5 10 4 8 0 5
4
0 4
3+ θ 7 5
D3
0 7
2- θ
0 6
3
-1 6
θ
2 8
4 5 7
Demanda 4 3 4 4 15 \ 15
vj 0 -1 0 -1
Depositos\Mercados M1 M2 M3 M4 Oferta ui
D1
0 2
3
1 2 0 2 0 1
0 3 2
D2
5 10 4 8 0 5
4
0 4
4 7 5
D3
0 7
1
0 6
3
-1 6
1
2 8
4 5 7
Demanda 4 3 4 4 15 \ 15
vj 0 -1 0 -1
El nuevo costo total es 3*2+1*7+3*6+4*5+1*6+4*4+4*8=68
Ahora se vuelve analizar por medio del método optimizante.
	D1
	C11
	C12
	X12
	
	
	
	
	
	
	C13
	C14
	C21
	C22
	C23
	C24
	C31
	C32
	C33
	C34
	Demanda
	SOLUCION BASICA FACTIBLE
	
	
	
	
	
	
	D1
	2
	2
	2
	1
	10
	8
	5
	4
	7
	6
	6
	8
	Demanda
	D1
	2
	2
	2
	1
	10
	8
	5
	4
	7
	6
	6
	8
	Demanda
	D1
	2
	2
	2
	1
	10
	8
	5
	4
	7
	6
	6
	8
	Demanda
	D1
	2
	2
	2
	1
	10
	8
	5
	4
	7
	6
	6
	8
	Demanda
	vj
	D1
	-5 2
	-4 2
	0 2
	0 1
	0 10
	-1 8
	0 5
	0 4
	0 7
	0 6
	4 6
	7 8
	Demanda
	vj
	D1
	2
	2
	2
	1
	10
	8
	5
	4
	7
	6
	6
	8
	Demanda
	D1
	0 2
	1 2
	0 2
	0 1
	5 10
	4 8
	0 5
	0 4
	0 7
	0 6
	-1 6
	2 8
	Demanda
	vj
	D1
	0 2
	1 2
	0 2
	0 1
	5 10
	4 8
	0 5
	0 4
	0 7
	0 6
	-1 6
	2 8
	Demanda
	vj