Unidad 4 Transporte Y Asignación

4.1 Definición Problema de Transporte

La manera más fácil de reconocer un problema de transporte es por su naturaleza o estructura "de - hacia": de un origen hacia un destino, de una fuente hacia un usuario, del presente hacia el futuro, de aquí hacia allá. Al enfrentar este tipo de problema, la intuición dice que debe haber una manera de obtener una solución. Se conocen las fuentes y los destinos, las capacidades y demandas y los costos de cada trayectoria. Debe haber una combinación óptima que minimice el costo (o maximice la ganancia). La dificultad estriba en el gran número de combinaciones posibles.

En general, los problemas de transporte se ocupan (en forma literal o imaginaría) de la distribución desde cualquier grupo de centros de suministro, llamados orígenes, a cualquier grupo de centros de recepción, llamados destinos de modo que se minimice el costo total de distribución.

Cada origen tiene ciertos recursos (oferta) para distribuir a los destinos y cada destino tiene cierta demanda de estos recursos que recibe de los orígenes. El modelo de un problema de transporte hace la siguiente suposición acerca de estos recursos (ofertas) y demandas.

Suposición de requerimientos. Cada origen tiene una cantidad fija de unidades (oferta), las cuales tienen que distribuirse entre los destinos. De manera similar, cada destino tiene una demanda fija de unidades, que tiene que ser satisfecha desde los orígenes.

Esta suposición significa que debe haber un equilibrio entre la oferta total de todos los orígenes y la demanda total de todos los destinos.

Suposición de costo. El costo de distribuir unidades de cualquier origen dado a cualquier destino dado es directamente proporcional al número de unidades distribuidas. Por lo tanto, este costo es justo el costo unitario de distribución por el número de unidades distribuidas.

Los únicos datos necesarios para el modelo del problema de transporte son los recursos (capacidades, existencias, oferta), las demandas y los costos unitarios.

Formulacion del problema

Supongamos que hay m centros de oferta (orígenes) y n centros de demanda (destinos) asimismo, supongamos que Ej es el número de unidades de mercancía disponibles en cada centro de oferta, y Dj el número requerido de unidades de mercancía en el centro de demanda. Si consideramos Cij como el costo unitario de transporte en la ruta de un centro de oferta a uno de demanda. El objetivo es determinar el número de unidades de mercancía que debe transportarse de las fuentes(i) a los destinos (j) de tal forma que se minimice el costo total del transporte. Si Xijes la cantidad transportada del centro de oferta (i) al centro de demanda (j)Entonces nuestro modelo será:

Una forma agradable de visualizar un problema de transporte en forma gráfica es usar su representación de red. Esta representación ignora la disposición geográfica de los orígenes y destinos. En su lugar, simplemente alinea todos los orígenes en una columna a la izquierda (donde E1 es el símbolo del origen 1, etc.)y todos los destinos en una columna a la derecha.

4.2 Metodo Aproximacion de Vogel

El método de aproximación de Vogel es un método heurístico de resolución de problemas de transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere de la realización de un número generalmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo produce mejores resultados iniciales que los mismos.

El método consiste en la realización de un algoritmo que consta de 3 pasos fundamentales y 1 más que asegura el ciclo hasta la culminación del método.

PASO 1

Determinar para cada fila y columna una medida de penalización restando los dos costos menores en filas y columnas.

PASO 2

Escoger la fila o columna con la mayor penalización, es decir que de la resta realizada en el "Paso 1" se debe escoger el número mayor. En caso de haber empate, se debe escoger arbitrariamente (a juicio personal).

PASO 3

De la fila o columna de mayor penalización determinada en el paso anterior debemos de escoger la celda con el menor costo, y en esta asignar la mayor cantidad posible de unidades. Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende se tachará la fila o columna, en caso de empate solo se tachará 1, la restante quedará con oferta o demanda igual a cero.

PASO 4: DE CICLO Y EXCEPCIONES

- Si queda sin tachar exactamente una fila o columna con cero oferta o demanda, detenerse.

- Si queda sin tachar una fila o columna con oferta o demanda positiva, determine las variables básicas en la fila o columna con el método de costos mínimos, detenerse.

- Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda, determine las variables básicas cero por el método del costo mínimo, detenerse.

- Si no se presenta ninguno de los casos anteriores vuelva al paso 1 hasta que las ofertas y las demandas se hayan agotado.

Una empresa está considerando satisfacer las necesidades de 4 clientes empleando los artículos que tiene disponibles en 3 almacenes. La cantidad de artículos que tiene en cada almacén son y es, 40 y 20 unidades respectivamente. Los clientes necesitan 12, 15, 30 y 20 unidades respectivamente. El costo unitario de embarque desde los almacenes hasta el cliente se encuentran en la siguiente tabla:

Encuentre la solución inicial del modelo de transporte utilizando el método de aproximación de vogel.

4.3 Metodo Modi

Este método reproduce exactamente las mismas iteraciones del método de banquillo. La principal diferencia ocurre en la forma en que las variables no básicas se evalúan en cada iteración. Asociados a cada renglón i de la tabla existen multiplicadores Ui similarmente se asocia un multiplicador Vj a cada columna de la tabla j. Para cada variable básica Xij de la solución actual, se escribe la ecuación Ui +Vj = Cij. Esas ecuaciones proporcionan m+n-1 relaciones con m+n incógnitas.

Los valores de los multiplicadores pueden ser determinados a partir de las ecuaciones suponiendo un valor arbitrario para cualquiera de los multiplicadores (usualmente se establece U1=0) y resolviendo el sistema de ecuaciones para encontrar los multiplicadores desconocidos. Una vez que se hace esto, la evaluación de cada variable no básica

...