FACULTAD DE INGENIERÍA
INGENIERÍA INDUSTRIAL
IND – 543
INVESTIGACIÓN DE OPERACIONES I
MODELOS DE TRANSPORTE
El modelo de transporte es un problema de optimización de
redes donde debe determinarse como hacer llegar los
productos desde los puntos de existencia hasta los puntos de
demanda, minimizando los costos de envió.
El modelo busca determinar un plan de transporte de una
mercancía de varias fuentes a varios destinos. Entre los datos
del modelo se cuenta:
• El problema del transporte,
también conocido como
problema de Hitchcock, fue
formulado y resuelto por
primera vez en el año 1941
por Frank L. Hitchcock (1875 -
1957).
El modelo busca determinar un plan de transporte de una
mercancía de varias fuentes a varios destinos. Entre los
datos del modelo se cuenta:
1.- Nivel de oferta en cada fuente u origen y la cantidad de
demanda en cada destino.
2.- El costo de transporte unitario de la mercancía de cada
fuente a cada destino.
El modelo se utiliza para realizar actividades como: control
de inventarios, programación del empleo, asignación de
personal, flujo de efectivo, programación de niveles de
reservas en prensas entre otras.
El objetivo de los modelos de transporte es encontrar la
solución a un costo mínimo para la realización de planes
de envió, transporte distribución, desde cualquier centro
de abastecimiento llamado orígenes, a cualquier grupo de
centros de recepción llamados destinos
Modelo General del Problema del Transporte
Es un caso especial de problema de programación Lineal, en el que todos los
coeficientes de las variables en las restricciones tienen coeficiente uno (1), esto
es:
ai,j = 1 ; para todo i , para todo j Expresado en forma general queda:
Gráficamente:
para j = 1, 2, 3, ..., n
es la cantidad de recursos (x) asignados al destino ( j )
con su costo unitario (i).
Matemáticamente:
Minimizar Z = C1,1X1,1 +...+ C1,jX1,j +...+ C1,nX1,n +...+ Ci,1Xi,1 +...+ Ci,jXi,j +...+ Ci,nXi,n +...+
Cm,1Xm,1 +...+ Cm,jXm,j +...+ Cm,nXm,n
Xi,j= Unidades a enviar desde la fuente i-ésima (i=1,...,m) al destino j-
ésimo (j=1,...,n)
Ci,j= Costo de enviar una unidad desde la fuente i-ésima (i=1,...,m) al
destino
j-ésimo (j=1,...,n)
ai = Disponibilidad (oferta) en unidades, de la fuente i-ésima (i=1,...,m)
bj = Requerimiento (demanda) en unidades, del destino j-ésimo (j=1,...,n)
tabla de costos y requerimientos
Costo por unidad distribuida
Destino
1 2 ... n Recursos
1 c11 c12 ... c1n a1
Origen 2 c21 c22 ... c2n a2
. . . . .
. . . . . . . .
. . . . .
m cm1 cm2 ... cmn am
Demanda d1 d2 ... dn
Sea Z el costo total de distribución y xij (i = 1, 2, ..., m; j = 1, 2,..., n) el número
de unidades que se distribuyen del origen i al destino j, la formulación de
programación lineal para este problema es:
m n
Minimizar Z = ci 1 j 1
ij xij
n
sujeta a
x
j 1
ij ai para i = 1, 2, ..., m
x
i 1
ij dj para j = 1, 2, ..., n
xij 0, para toda i y
j
ALGORITMO DE TRANSPORTE
El método general de resolución del problema de transporte consta de
4 pasos que conforman el denominado algoritmo de transporte.
Paso 1. Escribir el problema de transporte en la forma matricial. Si el
problema es no equilibrado, transformarle en equilibrado.. Ir al paso 2
Paso 2. Determinar una solución básica factible inicial. Ir al paso 3.
Paso 3. Si las solución obtenida en el paso 2 es optima, detener el
proceso., en otro caso , ir al paso 4.
Paso 4. Obtener una nueva solución que sea mejor que la anterior
Teoremas
Teorema 1. Para que el problema de transporte tenga solución es
condición necesaria y suficiente que la oferta total sea igual a la
demanda total.
m n
ai b j
Oferta total i 1 j 1 Demanda total
Teorema 2. El problema de transporte equilibrado tiene una solución
factible.
Teorema 3. Todo problema de transporte equilibrado tiene una solución
básica factible. Esta solución tiene como máximo m + n -1 variables no
negativas
En nuestro estudio utilizaremos los siguientes modelos de transporte:
1. Método de la Esquina Nor Oeste
2. Método de Costo Minimo
RESOLUCIÓN DEL MODELO DE TRANSPORTE
Matriz de costos
MATRIZ DE FLUJOS
Costo por unidad
distribuida DESTINO
Destino ORIGEN 1 2 3 ... OFERTA
1 2 ... n Recursos
1 c11 c12 ... c1n a1
Orig 2 c21 c22 ... c2n a2
en
. . . . .
. . . . . . . .
. . . . .
m cm1 cm2 ... cmn am
Dem b1 b2 ... bn DEMANDA
anda
Modelo de programación lineal Sistema de redes
Minimizar Z = C1,1X1,1 +...+ C1,jX1,j +...+ C1,nX1,n +...+ Ci,1Xi,1 +...+ Ci,jXi,j
+...+ Ci,nXi,n +...+ Cm,1Xm,1 +...+ Cm,jXm,j +...+ Cm,nXm,n
X11 +…+ X1j +…+ X1n = a1
Xi1 +…+ Xij +…+ Xin = ai
Xm1 +…+ Xmj +…+ Xmn = am X11 +…+ Xij +…+ Xmn = b1
X1j +…+ Xij +…+ Xmj = bj
Xm1 +…+ Xmj +…+ Xmn = bn
Para el caso en que la oferta total sea mayor que la demanda total
Si el caso es que se dispone de mayor producción de la que se
demanda, entonces para balancear el problema se agrega un
destino imaginario o artificial (llamado también destino ficticio) el
cual tendrá como demanda dicha sobreproducción. En cuanto a
los costos asociados a este nuevo destino los estableceremos a
cero (¿por qué?). El siguiente dibujo muestra lo que se debe
hacer:
donde
bn+1 =
m n
ai bj
i 1 j 1
y
0 ci,n+1 = 0, para i =
1, 2, ..., m
0
0
Para el caso en que la demanda es mayor que la oferta
Si el caso es que se tiene mayor demanda de lo que se produce, entonces para
balancear el problema se agrega un origen imaginario o artificial (llamado
también origen ficticio) el cual tendrá como recursos (producirá) dicha
sobredemanda. En cuanto a los costos asociados a este nuevo origen los
estableceremos a cero (¿por qué?). El siguiente dibujo muestra lo que se debe
hacer:
donde
sm+1 =
n m
dj ai
j 1 i 1
y
cm+1j = 0 para
j = 1, 2, ..., n
0 0 0
Teorema 1.-
Para que el problema de transporte tenga solución es condición necesaria y
suficiente que la oferta total sea igual a la demanda total
Teorema 2.-
El problema de transporte equilibrado o balanceado tiene una solución
factible
Teorema 3.-
Todo problema de transporte equilibrado tiene una solución básica factible.
Esta solución tiene como máximo m+n-1 variables no negativas
Solución básica factible no degenerada
Es una solución factible básica con exactamente m + n – 1 variables básicas
Solución básica factible degenerada.-
Es una S.B.F., con menos m + n – 1 variables básicas
METODO DE LA ESQUINA NOR OESTE.
Es un algoritmo heurístico útil para resolver problemas de transporte o
distribución por medio la consecución de una solución básica inicial que
satisfaga todas las restricciones existentes sin que esto implique que se
alcance el costo óptimo total.
Pasos para desarrollar este método:
Paso 1. Seleccionar la celda de la esquina noroeste (esquina superior
izquierda).
Paso 2: asignar el máximo posible Xij = min (ai, bj) o la menor entre la
oferta y la demanda.
Paso 3: Actualizar la oferta y la demanda
Xij = min (ai, bj) si ai< bj b*j = bi – ai (se elimina la fila i)
si bj < ai a*i = ai – bj (se elimina la columna j)
Si ai = bj eliminamos la fila i o columna j.
Paso 4: Muévase a la derecha o hacia debajo de xij a Xij+1, según halla
quedado disponibilidad para asignar. En otro caso ir, al paso 1.
Este método trata de localizar una mejor solución inicial al modelo
de transporte , utilizando las rutas menos costosas.
Si existe costos iguales, se selecciona arbitrariamente uno de ellos.
ALGORITMO DEL MÉTODO DE COSTO MÍNIMO:
Paso1. Localizar la celda que tenga el menor costo y asignarle la mayor
cantidad posible de flujo. Si hay empate en el mínimo coste. Elegir la
celda a la que pueda asignarle una mayor cantidad de flujo
Paso 2.- Se procede actualizar o ajustar la oferta y demanda de la fila y
columna, restándole la cantidad asignada a la celda. Luego se procede a
eliminar la fila o columna. Para continuar asignando valores en las
siguientes filas o columna, se deja de considerar la fila o columna que ya
ha quedado saturada.
Paso 3. Si se han agotado todas las ofertas o demandas, igualad a cero las
Xij que no tienen valor asignado, y ya tenemos la solución básica factible
inicial. En caso contario volver al paso 1
Nota: se exceptúa los costos de las celdas de costo ficticio
EJEMPLO
Una empresa energética Boliviana dispone de cuatro plantas de generación para satisfacer la
demanda diaria eléctrica en cuatro ciudades, Santa Cruz, Cochabamba, La Paz y Chuquisaca.
Las plantas 1, 2, 3 y 4 pueden satisfacer de 80, 30, 60 y 45 millones de KW al día
respectivamente. Las necesidades de las ciudades de Santa Cruz, Cochabamba, La Paz y
Chuquisaca son de 70, 40, 70 y 35 millones de KW al día respectivamente. Los costos asociados
del envío de suministro energético por cada millón de KW entre cada planta y cada ciudad son
los registrados en la siguiente tabla.
Encuentre la solución inicial.
TAREA
Considere el problema de transporte que se originan debido a un accidente. Existen tres
ambulancias con distintas capacidades de 3, 7 y 5 heridos, para trasladar heridos hacia cuatro
servicios de urgencias que pueden atender a 4, 3, 4 y 4 heridos. Los costos generados por el
transporte se muestran en la tabla siguiente:
Encuentre la solución inicial.