Download - TRANSPORTE_Y_ASIGNACION_138793.ppt
TRANSPORTE Y ASIGNACION
Algoritmo de TransporteMétodo Noroccidental - Método Vogel - Método Simplex
Algoritmo de AsignaciónMétodo Hungaro
ESTRUCTURA DE TRANSPORTE
• Se supone que “m” origen tienen que surtir a “n” centros de consumo con un cierto producto. La capacidad de oferta del origen i es ai con i = (1,....m) y la demanda en el centro de consumo j es bj con j = (1,......,n). Se supone que cij es el costo de enviar una unidad del producto del origen i al centro de consumo j.
PROBLEMA DE TRANSPORTEsi, centro de ofertadi, centro de demandaXij, flujo del centro de oferta i al centro de demanda j
P1
C1
P2
P3
C2
C3
C4
s1
s2
s3
d1
d2
d3
d4
C5 d5
• El problema de transporte se reduce a determinar cuántas unidades del producto deben enviarse del origen i al centro de consumo j, tal que se minimicen los costos totales de distribución, se satisfaga la demanda del centro de consumo j y no se exceda la capacidad de oferta del origen i.
• Sea Xij la variable de decisión, entonces la formulación del problema lineal es:
• Mín Z = cij Xij
• sujeto a Xij ai, i=(1,......,m)
• Xij bj, j=(1,......,n)
• con Xij 0, i=(1,....m)
• j=(1,....,n)
n
mj
i
n
i j
m
• Con la adición de las variables de holgura y superfluas el problema puede escrbirse como:
• Mín Z = cij Xij
• i j n
• sujeto a Xij = ai, i=(1,......,m)
•
• Xij = bj, j=(1,......,n)
• con Xij 0, i=(1,....m)
• j=(1,....,n)
m n
j
i
m
• Esta formulación lineal, PT, se denomina estructura de transporte.
• La restricción 1, indica que todo flujo del producto que emana del origen i y que se envía a todos los posibles m destinos, no puede excederse a la oferta del origen i ques ai. Existe una restricción de ese tipo por cada origen.
• La restricción 2, indica que todo flujo del producto que llega al centro de consumo j de todos los posibles n origen debe satisfacer la demanda del centro de consumo bj.
• Las restricciones de no negatividad indican que el sentido del flujo del producto es de los orígenes a los destino, unicamente.
ALGORITMO DE TRANSPORTE
• Mín Z = cij Xij
• • sujeto a Xij = ai, i=(1,......,m)• • Xij = bj, j=(1,......,n)
• con Xij 0, i=(1,....m)• j=(1,....,n)
m n
n
m
i j
j
i
• En el problema PT, ai y bj son número enteros positivos.
• Para construir el algoritmo se establecer dos matrices: una matriz de costos y una matriz de flujos.
• Cuando la oferta total sea mayor que la demanda total es decir: ai > bj, entonces se añade un centro de consumo artificial n + 1, cuya demanda bn+1 es
ai - bj, y cuyos costos unitarios c k,n+1, K=(1,...,m) son todos ceros.
MATRIZ DE COSTOSDestinos Oferta
1 2 ...........................n
Origenes
1
2
.
.
.
.m
Demanda b1 b2 .......................bn
a1
a2
.
.
am
Costos
c11 c12........................c1n
cm1 cm2......................cmn
c21 c22........................c2n
MATRIZ DE FLUJOSDestinos Oferta
1 2 ...................................n
Origenes
1
2
m
Demanda
X11 X12 ............................... .X1n
X21 X22 ............................... .X2n
Xm1 Xm2 ...............................Xmn
b1 b2 ............................... .. bn
a1
a2
am
• Si la demanda total excede a la oferta total, es decir, bj > ai, entonces se añade un centro de oferta artificial m+1, cuya capacidad de oferta a m+1 es bj - ai, y cuyos costos unitarios c m+1,k, son todos ceros.
• Una vez que el problema de transporte está balanceado, se requiere una solución inicial sea básica y factible.
• Los métodos aplicables son el Método del Extremo Noroccidental y Método de Vogel.
Destinos Oferta
1 2...................... n n+1
Origenes
12.....m
c11 c12........................c1n 0
c21 c22........................c2n 0
cm1 cm2........................cmn 0
Demanda b1 b2 ......................... bn ai - bj
m n
i j
a1
a2
.
.
am
Costos
Destinos Oferta1 2 ...................... n
12.....m
m + 1
c11 c12........................c1n a1
c21 c22........................c2n a2
cm1 cm2........................cmn am
0 0 ..........................0 bj - ai
n m
j ib1 b2 ......................... bnDemanda
Origenes
Costos
METODO DEL EXTREMONOROCCIDENTAL PARA GENERAR UNASOLUCIÓN INICIAL BÁSICA
• El punto de partida es una matriz con orígenes, destinos, ofertas y demandas de un problema balanceado.
• Para obtener una solución básica factible al problema, PT, se empieza a construir un matriz de flujos de la siguientes manera: ai bj
• Las variables Xij sólo pueden tomar el valor 0 ó 1. Toman el valor 1 si el origen i se hace corresponder con el destino j, y 0 en caso contrario
• Para resolver estos problemas se aplican algoritmos de asignación .
• Una condición necesaria y suficiente para que estos problemas tengan una solución es que estén balanceados, esto es, que la oferta total sea igual a la demanda total. Así si existen m orígenes y n destinos, se requiere que m y n sean iguales.
• Un algoritmo para resolver este tipo de problemas es el Método Húnguro
• O
rige
nes
1
2...n
Demanda b1 b2 ......................bn
a1
a2
.
.
.
.am
1 2 ...........................mOferta
Destinos
• PASO I. En la posición (1,1), que es el extremo noroccidental de la matriz asígnese el
• Mín (a1,b1) = X1,1. Réstese X1,1 de la oferta a1 y de la demanda b1. Alguna de estas cantidades se convertirá en cero
• PASO II. Si a1 se convierte en cero, pásese a la posición (2,1) y hágase
• X 2,1 = Mín (b1 - X 1,1, a2).
• Si por el otro lado es b1 el que se convierte en cero en el paso anterior, se pasa a la posición (1,2) y X 1,2 = Mín (a1 - X
1,2,, b2) • PASO III. Continuese con la misma lógica hata llegar a la
posición (m,n). La matriz de flujos que se obtenga será lfactible y básica para PT
METODO DE VOGEL
• PASO I: Este método comienza calculando, para cada reglón y columna, una “penalización” igual a la diferencia entre los dos costos más pequeños en el reglón (o columna).
• PASO II: encuentre el reglón o columna con la penalización más grande. Dentro de ese reglón o columna, fije la variable con costo más bajo, con el valor más alto posible y anule el resto de las variables del reglón o columna correspondiente.
• PASO III: Actualice las penalizaciones (esta vez no se consideran las variables ya fijadas) y vuelva a iterar hasta completar el tableau.
• PROBLEMAS DE ASIGNACION• La formulación de un problema es:
• Mín Z = cij Xij
• sujeto a Xij = 1, i = 1,......., m
• Xij = 1, j = 1,......., n
Xij 0
m n
i
j
ij
m
n
PASO I: METODO HUNGARO
• Dada una matriz de costos de un problema de asignación balanceado, reste en cada columna y en cada renglón el número más pequeño de esa columna ó renglón, del resto de los elementos en esa columna o renglón. En otras palabras:
• cij = cij - Mín cij, j = 1,.........,n
• cij = cij - Mín cij, i = 1,.........m
PASO II: METODO HUNGARO
• En la nueva matriz de costos seleccione un cero en cada renglón y columna. Elimine durante el proceso de selección la columna y el renglón al que pertenece el cero seleccionado. Si al finalizar este paso se ha hecho una asignación completa de ceros, es decir, cada origen tiene asignado un sólo destino y cada destino tiene asignado un sólo origen, se ha encontrado la asignación óptima. En caso contrario continúe con el PASO III.
PASO III: METODO HUNGARO
• En este paso encuentra la condición de Konig de que O(M) = D(M), siendo la Matriz de costos del PASO II. Este paso tiene 6 etapas:
• 3-1 Marque cada fila que no contiene un cero asignado• 3-2 Marque cada columna que contiene un cero (no
necesariamente asignado) en la fila marcada en el Paso 3-1
• 3-3 Marque cada fila que contiene un sero asignado en la columna marcada en el Paso 3-2
PASO III: METODO HUNGARO
• 3-4 Repita los pasos 3-2 y 3-3 hasta que no se puedan marcar más columnas o filas
• 3-5 Tache las filas no marcadas y las columnas marcadas• 3-6 Selecciónese al número más pequeño de los elementos
no cubiertos por una tachadur horizontal o vertical. Reste ese elemento del resto de los no tachados y sume ese elemento a los tachados en cruz, es decir, por una tachadura horizontal y vertical. Los elementos cruzados por una sola tachadura no cambian. Regrésese al PASO II