UNIDAD III

UNIDA III
TRANSPORTE Y ASIGNACIÓN
PROBLEMAS DE TRANSPORTE
Se refiere a la distribución de cualquier bien desde un grupo de centros de abastecimiento llamado orígenes, a un grupo de
centros de recepción llamados destinos, de tal manera que se minimicen los costos totales de distribución.
Así, por lo general, el origen i(i=1, 2, …m) dispone de Si unidades para distribuir a los destinos y el destinoj(j=1, 2, …n) tienen
una demanda dj unidades que recibe desde los orígenes.
Una suposición es que el costo de distribución de unidades desde el origen i al destino j, es directamente proporcional al
número de unidades y se denota por cij.
Planteamiento del problema de transporte
Este problema puede resolverse mediante programación lineal, que en forma generalizada es:
=

Sujeto a:



== 1, 2, …

=

= 1, 2, …

El cual se basa en dos condiciones:
1) Las variables deben de tomar valores enteros.
2) El problema debe estar balanceado, es decir:





≥



=

 En caso de que no se cumpla esta restricción se introduce un origen o destino ficticio, con costos 0.
 Si no se desea alguna asignación su costo es infinito y regularmente se le denota por M.
Algoritmo detransporte
El método simplex simplificado para el problema de transporte es:
Inicialización. Se construye una solución factible con cualquiera de los siguientes procedimientos:
1) Regla de la esquina noroeste.
2) Método de costo mínimo.
3) Método de aproximación de Vogel.
Debe verificarse que se tengan m + n – 1 asignaciones.
Depto. Ing. Industrial

1

Investigación de Operaciones

Regla deoptimalidad. Se obtiene ui y vj eligiendo el renglón con mayor número de asignaciones, estableciendo ui = 0, y
determinando el resto de las ui y vj, resolviendo el sistema de ecuaciones donde cij = ui + vj, para las variables básicas (son las
que tienen asignación). Si ui + vj – cij ≤ 0, para cada una de las variables no básicas, se encontró la solución óptima, de lo
contrario se itera nuevamente.Iteración.
1) Se determina la variable básica entrante, es aquella que tiene el coeficiente más positivo para u i + vj - cij.
2) Se determina la variable básica que sale identificando la reacción en cuadro que se necesita para conservar la
factibilidad cuando se aumenta el valor de la variable.
3) Se determina la nueva solución; se suma el valor de la variable que sale a las asignaciones de las celdasreceptoras y
se resta este valor a las asignaciones de las celdas donadoras.
Regla de la esquina noroeste
La primera elección es x11 (es decir, se comienza en la esquina noroeste de la tabla simplex de transporte). De ahí en
adelante, si xij fue la última variable básica seleccionada, la siguiente elección es xi,j+1 (es decir se mueve una columna a la
derecha) si quedan recursos en i. De otra manera,se elige xi+1,j (es decir, se mueve un renglón hacia abajo).
Si se continúa en esta misma forma, llegará el momento en que obtenga la solución inicial BF completa, en la que los
números al centro de la celda son los valores de las variables básicas, y todas las otras variables son no básicas igual a cero.
Se pueden agregar flechas para indicar el orden en que se eligieron las variables básicas(asignaciones).
Método de aproximación de Vogel
Para cada renglón y columna que queda bajo consideración, se calcula su diferencia, que se define como la diferencia
aritmética entre el costo unitario más pequeño (cij) y el que le sigue, de los que quedan en ese renglón o columna. (Si se
tiene un empate para el costo más de los restantes de un renglón o columna, entonces la diferencia es cero). En elrenglón
o columna que tiene la mayor diferencia se elige la variable que tiene el menor costo unitario que queda. (Los empates para
la mayor de estas diferencias se pueden romper arbitrariamente). En cada iteración, después de calcular y escribir las
diferencias para cada renglón y columna que quedan bajo consideración, se encierra en un círculo la mayor de ellas y se
enmarca en un cuadro el...