ejercicio de transporte

Ejercicio de método simplex

ejercicio del método gráfico

Problema de Transporte

Problema de Transporte: (Referencia: Hitchcock, 1941; Kantorovich, 1942; Koopmans 1947).

El problema consiste en decidir cuántas unidades trasladar desde ciertos puntos de origen (platas, ciudades, etc) a ciertos puntos de destino (centros de distribución, ciudades, etc) de modo de minimizar los costos de transporte, dada la oferta y demanda en dichos puntos. Se suponen conocidos los costos unitarios de transporte, los requerimientos de demanda y la oferta disponible.

Por ejemplo, suponga que una empresa posee dos plantas que elaboran un determinado producto en cantidades de 250 y 400 unidades diarias, respectivamente. Dichas unidades deben ser trasladadas a tres centros de distribución con demandas diarias de 200, 200 y 250 unidades, respectivamente. Los costos de transporte (en $/unidad) son:

	C.Dist. 1	C.Dist.2	C.Dist.3
Planta 1	21	25	15
Planta 2	28	13	19

Se requiere formular un modelo de Programación Lineal que permita satisfacer los requerimientos de demanda al mínimo costo.

Solución:

Variables de Decisión: Xij : Unidades transportadas desde la planta i (i=1, 2) hasta el centro de distribución j (j=1, 2, 3)

Función Objetivo: Minimizar el costo de transporte dado por la función: 21X11 + 25X12 + 15X13 + 28X21 + 13X22 + 19X23

Restricciones:

Satisfacer los requerimientos de Demanda:

X11+ X21 = 200

X12 + X22 = 200

X13 + X23 = 250

Sujeto a la Oferta de las plantas::

X11+ X12 + X13 = 250

X21 + X22+ X23 = 400

No Negatividad: Xij >= 0

El siguiente diagrama permite una visualización de la situación anterior:

Resolución utilizando el complemento Solver de Microsoft Excel:

1. Abrir una Planilla de Cálculo de Excel. Asegurese de tener instalado el complemento Solver (OpciónHerramientas - Complementos)

Luego construya una planilla como la de la imagen de referencia. Se han marcado con amarillo las celdas cambiantes (variables de decisión) y función objetivo. Para facilitar el seguimiento se ha escrito en rojo las fórmulas asociadas a cada celda.

2. Ingrese la función objetivo, celdas cambiantes y restricciones en la ventana de "Parámetros de Solver". Si utiliza la mismas celdas de la imagen anterior, usted debería obtener lo siguiente:

3. Ingrese a "Opciones". Luego selecione "Adoptar modelo lineal" y "Asumir no negativos". Finalmente presione "Aceptar". Luego de esto usted volverá a la pantalla principal (Parámetros de Solver)

4. Seleccione "Resolver". Obtendrá la solución al problema y podrá requerir los Informes de Solver. Finalmente presione "Aceptar".

5. Se actualizarán los valores en la Planilla de Cálculo en las celdas marcadas en amarillo desplegando la solución óptima y valor óptimo. Adicionalmente se verifica el cumplimiento de las restricciones del problema.

6. Finalmente, se obtienen los informes de sensibilidad los cuales entregan información relevante en cuanto a los precios sombra asociados a las restricciones, intervalos de variación de garantizan la validez del precio sombra, intervalo de variación para los coeficientes de la función objetivo, etc.

método húngaro

EL METODO HUNGARO

Este algoritmo se usa para resolver problemas de minimización, ya que es más eficaz que el empleado para resolver el problema del transporte por el alto grado de degeneración que pueden presentar los problemas de asignación. Las fases para la aplicación del método Húngaro son:

Paso 1: Encontrar primero el elemento más pequeño en cada fila de la matriz de costos m*m; se debe construir una nueva matriz al restar de cada costo el costo mínimo de cada fila; encontrar para esta nueva matriz, el costo mínimo en cada columna. A continuación se debe construir una nueva matriz (denominada matriz de costos reducidos) al restar de cada costo el costo mínimo de su columna.

Paso 2: (En algunos pocos textos este paso se atribuye a Flood). Consiste en trazar el número mínimo de líneas (horizontales o verticales o ambas únicamente de esas maneras) que se requieren para cubrir todos los ceros en la matriz de costos reducidos; si se necesitan m líneas para cubrir todos los ceros, se tiene una solución óptima entre los ceros cubiertos de la matriz. Si se requieren menos de m líneas para cubrir todos los ceros, se debe continuar con el paso 3. El número de líneas para cubrir los ceros es igual a la cantidad de asignaciones que hasta ese momento se pueden realizar.

Paso 3: Encontrar el menor elemento diferente de cero (llamado k) en la matriz de costos reducidos, que no está cubierto por las líneas dibujadas en el paso 2; a continuación se debe restar k de cada elemento no cubierto de la matriz de costos reducidos y sumar k a cada elemento de la matriz de costos reducidos cubierto por dos líneas (intersecciones). Por último se debe regresar al paso 2.

Notas:

1. Para resolver un problema de asignación en el cual la meta es maximizar la función objetivo, se debe multiplicar la matriz de ganancias por menos uno (−1) y resolver el problema como uno de minimización.

2. Si el número de filas y de columnas en la matriz de costos son diferentes, el problema de asignación está desbalanceado. El método Húngaro puede proporcionar una solución incorrecta si el problema no está balanceado; debido a lo anterior, se debe balancear primero cualquier problema de asignación (añadiendo filas o columnas ficticias) antes de resolverlo mediante el método Húngaro.

3. En un problema grande, puede resultar difícil obtener el mínimo número de filas necesarias para cubrir todos los ceros en la matriz de costos actual. Se puede demostrar que si se necesitan j líneas para cubrir todos los ceros, entonces se pueden asignar solamente j trabajos a un costo cero en la matriz actual; esto explica porqué termina cuando se necesitan m líneas.

Características de los problemas de transporte

Características de los problemas de transporte

En general los problemas de transporte se ocupan (en forma literal o imaginaria) 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. 


Suposición de requerimientos: cada origen tiene un suministro fijo de unidades, donde este suministro completo tiene que distribuirse entre los destinos. De manera similar, cada destino tiene una demanda fija de unidades, donde esta demanda completa tiene que recibirse desde los orígenes. 


Propiedades de soluciones factibles: un problema de transporte tendrá soluciones factibles si y sólo la suma de sus recursos es igual a la suma de sus demandas (equilibrio entre suministro total de todos los orígenes y la demanda total de todos los destinos).En algunos problemas reales, los recursos en realidad representan cantidades máximas(y no cantidades fijas) para distribuir. 


Suposición de costo :  el costo de distribuir unidades de cualquier origen 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.

El modelo: cualquier problema (involucre o no transporte) se ajusta al modelo de un problema de transporte  si se puede describir por completo en términos de una tabla de parámetros (origen-destino: costos, recursos, demanda) y satisface tanto la suposición de requerimientos como la suposición de costo. El objetivo es minimizar el costo total de distribuir las unidades. Todos los parámetros del modelo están incluidos en la tabla de parámetros.

¡ Se requiere solo llenar una tabla de parámetros para formular el problema de transporte. !