5.1 DEFINICIÓN DEL 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.

El problema del transporte o distribución es un problema de redes especial en programación lineal que se funda en la necesidad de llevar unidades de un punto específico llamado fuente u Origen  hacia otro punto específico llamado Destino. Los principales objetivos de un modelo de transporte son la satisfacción de todos los requerimientos establecidos por los destinos y claro está la minimización de los costos relacionados con el plan determinado por las rutas escogidas.

El contexto en el que se aplica el modelo de transporte es amplio y puede generar soluciones atinentes al área de operaciones, inventario y asignación de elementos.

El procedimiento de resolución de un modelo de transporte se puede llevar a cabo mediante programación lineal común, sin embargo su estructura permite la creación de múltiples alternativas de solución tales como la estructura de asignación o los métodos más populares.

Los problemas de transporte o distribución son uno de los más aplicados en la economía actual, dejando como es de prever múltiples casos de éxito a escala global que estimulan la aprehensión de los mismos.

PROBLEMA DE TRANSPORTE MEDIANTE PROGRAMACIÓN LINEAL

Como se mencionó anteriormente la programación lineal puede ser utilizada para la resolución de modelos de transporte, aunque no sea sensato resolver los modelos mediante el Método Simplex si puede ser de gran utilidad la fase de modelización, la programación carece de la practicidad de los métodos de asignación, pero puede ser de gran importancia dependiendo de la complejidad de las restricciones adicionales que puede presentar un problema particular.

 5.2 METODO DE LA ESQUINA NOROESTE

El método de la esquina Noroeste es un algoritmo heurístico capaz de solucionar problemas de transporte o distribución mediante 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. 

Este método tiene como ventaja frente a sus similares la rapidez de su ejecución, y es utilizado con mayor frecuencia en ejercicios donde el número de fuentes y destinos sea muy elevado. 

Su nombre se debe al génesis del algoritmo, el cual inicia en la ruta, celda o esquina Noroeste. Es común encontrar gran variedad de métodos que se basen en la misma metodología de la esquina Noroeste, dada que podemos encontrar de igual manera el método e la esquina Noreste, Sureste o Suroeste.

Es uno de los métodos más fácil para determinar una solución básica factible inicial. Este también considerado por ser el menos probable para dar una buena solución de “bajo costo” porque ignora la magnitud relativa de los costos.
Pasos para desarrollar este método:

1. Seleccionar la celda de la esquina noroeste (esquina superior izquierda).
2. Haga el más grande envío como pueda en la esquina de la celda de la esquina noroeste, esta operación agotará completamente la disponibilidad de suministros en un origen a los requerimientos de demanda en un destino. A este procedimiento o paso se le llama con frecuencia saturar.
3. Corrija los números del suministro y requerimiento para reflejar lo que va quedando de suministro y vuelva al paso uno.

Reglas para el desarrollo del método esquina noroeste: 

1. Los envíos son indicadores dentro de cada celda.
2. Los suministros y requerimientos que quedan pueden ser registrados a la derecha de los números originales.
3. Las filas correspondientes a los orígenes pueden ser eliminadas o señaladas, después de que sus requerimientos estén completamente llenos.

Guzmán, L. (2010). Modulo Métodos Determinísticos. Lugar: UNAD. 

Costo Total = (400*2)+(100*3)+(600*1)+(200*5)+(1000*1)
Costo Total = 800+300+600+1000+1000
Costo Total = $ 3.700

Es improbable que este plan factible sea también el plan de envío factible del mínimo costo, ya que ignoramos la magnitud relativa de los costos unitarios en cada interacción.

En general para saber si la solución es óptima existe una regla la cual dice que

m+n-1

Debe ser igual al número de casillas ocupadas por cantidades en donde n = a las columnas y m = a las filas, esta es utilizada para determinar si la solución inicial es degenerada o no. En otras palabras, si tenemos como es el caso del ejemplo anterior tres filas y tres columnas tendremos en total 6 menos uno dará 5 casillas que deben estar ocupadas si el número es superior a este significa que admite procedimiento para disminuir número de casillas asignadas, y tendremos que con mayor obligación aplicar prueba de optimalidad, si por el contrario el número de casillas es inferior entonces estaremos muy cerca de encontrar el valor del costo de envío óptimo.

Es importante que usted tenga en cuenta que la prueba de optimalidad siempre se debe aplicar sea cual fuere la elección del método aplicado a un ejercicio o problema así se tenga la prueba de degeneramiento con menor valor, esta solo lo ubica en una posición de ventaja para entender que el proceso está muy cercano al óptimo.

5.1 DEFINICIÓN DEL PROBLEMA DE TRANSPORTE

5.1 DEFINICIÓN DEL 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.

El problema del transporte o distribución es un problema de redes especial en programación lineal que se funda en la necesidad de llevar unidades de un punto específico llamado fuente u Origen hacia otro punto específico llamado Destino. Los principales objetivos de un modelo de transporte son la satisfacción de todos los requerimientos establecidos por los destinos y claro está la minimización de los costos relacionados con el plan determinado por las rutas escogidas.

El contexto en el que se aplica el modelo de transporte es amplio y puede generar soluciones atinentes al área de operaciones, inventario y asignación de elementos.

El procedimiento de resolución de un modelo de transporte se puede llevar a cabo mediante programación lineal común, sin embargo su estructura permite la creación de múltiples alternativas de solución tales como la estructura de asignación o los métodos más populares.

Los problemas de transporte o distribución son uno de los más aplicados en la economía actual, dejando como es de prever múltiples casos de éxito a escala global que estimulan la aprehensión de los mismos.

PROBLEMA DE TRANSPORTE MEDIANTE PROGRAMACIÓN LINEAL

Como se mencionó anteriormente la programación lineal puede ser utilizada para la resolución de modelos de transporte, aunque no sea sensato resolver los modelos mediante el Método Simplex si puede ser de gran utilidad la fase de modelización, la programación carece de la practicidad de los métodos de asignación, pero puede ser de gran importancia dependiendo de la complejidad de las restricciones adicionales que puede presentar un problema particular.

ITTLaguna. (2014). METODOS PARA ENCONTAR UNA SOLUCION BASICA INICIAL.. 24/05/2016, de ITTLaguna Sitio web:

http://www.itlalaguna.edu.mx/academico/carreras/industrial/invoperaciones1/U5B.HTML

Guzmán, L.. (2010). Modulo Métodos Determinísticos. 24/05/2016, de UNAD Sitio web:

http://datateca.unad.edu.co/contenidos/102016/CONTENIDOS/Exe_nuevo/leccin_11_mtodo_de_la_esquina_noroeste.html

5.2 METODO DE LA ESQUINA NOROESTE

5.2 METODO DE LA ESQUINA NOROESTE

El método de la esquina Noroeste es un algoritmo heurístico capaz de solucionar problemas de transporte o distribución mediante 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.

Este método tiene como ventaja frente a sus similares la rapidez de su ejecución, y es utilizado con mayor frecuencia en ejercicios donde el número de fuentes y destinos sea muy elevado.

Es uno de los métodos más fácil para determinar una solución básica factible inicial. Este también considerado por ser el menos probable para dar una buena solución de “bajo costo” porque ignora la magnitud relativa de los costos.

Pasos para desarrollar este método:

1. Seleccionar la celda de la esquina noroeste (esquina superior izquierda).
2. Haga el más grande envío como pueda en la esquina de la celda de la esquina noroeste, esta operación agotará completamente la disponibilidad de suministros en un origen a los requerimientos de demanda en un destino. A este procedimiento o paso se le llama con frecuencia saturar.
3. Corrija los números del suministro y requerimiento para reflejar lo que va quedando de suministro y vuelva al paso uno.

Reglas para el desarrollo del método esquina noroeste: 

1. Los envíos son indicadores dentro de cada celda.
2. Los suministros y requerimientos que quedan pueden ser registrados a la derecha de los números originales.
3. Las filas correspondientes a los orígenes pueden ser eliminadas o señaladas, después de que sus requerimientos estén completamente llenos.

5.3 EL METODO DE APROXIMACION DE VOGEL

Aproximación de Vogel

En este apartado estudiaremos un poco sobre el método de vogel como un método de aplicación de la investigación de operaciones, que nos permitirá analizar los problemas y llegar a un resultado óptimo para la obtención de las máximas ganancias. es un método 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 numero 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

Este procedimiento trata de eliminar casi toda la tabla simplex además de los datos de entrada, para llegar a la única información necesaria que es la solución básica factible actual, los valores actuales y los valores resultantes de las variables no básicas. Es posible apreciar de manera global la gran diferencia en eficiencia y conveniencia entre los métodos simplex de transporte y simplex si ambos se aplican al mismo problema pequeño.

MÉTODO DE VOGEL

Este método tiene como objetivo obtener una solución inicial BF[1]. Como todas las restricciones funcionales de los problemas de transporte son igualdades, el método simplex obtendría esta solución mediante la introducción de variables artificiales y su utilización como variables básicas iniciales. La solución básica que resulta sólo es factible para la versión revisada del problema, por lo que se necesita un buen número de iteraciones[2] para hacer que el valor de estas variables sea igual a cero y se obtengan las soluciones BF reales. Este procedimiento es más sencillo ya que construye de manera directa una solución BF real en la tabla simplex de transporte. (Introduccion a la Investigacion de Operaciones, pág. 297)

Tabla 1  8.15 Tomada de Introducción a la Investigación de operaciones pág. 296

Procedimiento general para construir una solución inicial BF.

Al inicio, todos los renglones de los orígenes y las columnas de destinos de la tabla simplex de transporte se toman en cuenta para proporcionar una variable básica (asignación).

1. Se selecciona la siguiente variable básica (asignación) entre los renglones y columnas en que todavía se puede hacer una asignación de acuerdo con algún criterio.

2. Se hace una asignación que sea tan grande como para que use el resto de los recursos en ese renglón o la demanda restante en esa columna (lo que resulte menor).

3. Se elimina ese renglón o columna —la que tenía la cantidad más pequeña de los recursos o demandas restantes— para las nuevas asignaciones. (Si el renglón y la columna tienen la misma cantidad de recursos y demanda restantes, de manera arbitraria se elimina el renglón. La columna se usará después para proporcionar una variable básica degenerada, es decir, una asignación con cero unidades encerradas en un círculo.)

4. Si sólo queda un renglón o una columna dentro de las posibilidades, entonces el procedimiento se termina eligiendo como básicas cada una de las variables restantes —es decir, las variables que no han sido elegidas ni eliminadas al quitar su renglón o columna— asociadas con ese renglón o columna que tiene la única asignación posible. De otra manera, se regresa al paso 1. (Introduccion a la Investigacion de Operaciones, pág. 299)

Se han propuesto varios criterios diferentes para elegir las variables básicas, uno de ellos es el Método de aproximación de Vogel que dice que 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 entre el costo más pequeño de los restantes de un renglón o columna, entonces la diferencia es 0.) En el renglón o columna que tiene la mayor diferencia, se elige la variable que tiene el menor costo unitario que queda. (Los empates en el caso de la mayor de estas diferencias se pueden romper de manera arbitraria.)

Ejemplo.

Ahora se aplicará el procedimiento general al problema del Metro Water District con el criterio del método de aproximación de Vogel para seleccionar la siguiente variable básica en el paso 1. En cada iteración, después de calcular y escribir las diferencias en 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 costo unitario menor en ese renglón o columna. La variable con este costo unitario menor se selecciona como la siguiente variable básica y su valor se indica en la esquina inferior derecha de la tabla actual, junto con el renglón o columna que se elimina (vea los pasos 2 y 3 del procedimiento general). La tabla de la siguiente iteración es la misma, pero se elimina este renglón o columna y se resta la cantidad asignada de la demanda o los recursos correspondientes (cualesquiera que sean los sobrantes).

La aplicación de este procedimiento al problema del Metro Water District resulta en la serie de tablas de parámetros que se muestran en la tabla 8.17, en donde la solución BF inicial consiste en las ocho variables básicas (asignaciones) dadas en la esquina inferior derecha de las tablas de parámetros respectivas.

Este ejemplo ilustra dos características sutiles del procedimiento general que merecen atención especial. Primero, observe que la iteración final elige tres variables (x31, x32 y x33) para entrar a la base, en lugar de una sola que se elige en las iteraciones anteriores. La razón es que en este punto queda sólo un renglón (el renglón 3) sin eliminar. Por tanto, el paso 4 del procedimiento general impone que se deben seleccionar como básicas todas las variables restantes asociadas con el renglón 3.

Segundo, observe que la asignación x23 5 20 en la penúltima iteración agota tanto los recursos restantes de ese renglón como la demanda que queda en esa columna. Sin embargo, en lugar de eliminar los dos, el paso 3 dispone que se elimine sólo el renglón y se deje la columna para que más tarde proporcione una variable básica degenerada. En realidad, la columna 3 se usa para este propósito en la iteración final cuando se selecciona x33 5 0 como una de las variables básicas. Vea en la tabla 8.16 otro ejemplo de este fenómeno, donde después de hacer la asignación x12 5 20 se elimina sólo el renglón 1, y la columna 2 se conserva para proporcionar la variable básica degenerada x22 5 0, en la siguiente iteración.

Aunque una asignación de cero puede parecer irrelevante, en realidad juega un papel importante, pues como se verá pronto, el método simplex de transporte debe conocer todas las m 1 n 2 1 variables básicas, incluso aquellas que tienen un valor de cero, que constituyen la solución BF actual. (Introduccion a la Investigacion de Operaciones, pág. 300)

 

Tabla 2 8.17 Tomada de Introducción a la Investigación de operaciones pág. 301

---

[1] Soluciones Básicas Factibles

[2] Iteración: acto de repetir un proceso con el objetivo de alcanzar una meta deseada, objetivo o resultado.

PRUEBA DE OPTIMALIDAD

 Se obtiene ui y vj al elegir el renglón con el mayor número de asignaciones y establecer su u1 = 0; después se resuelve el sistema de ecuaciones cij = ui + vj para cada (i, j) tal que xij es básica. Si cij - ui - vj ≥ 0 para toda (i, j) tal que xij es no básica, entonces la solución actual es óptima, por lo que el proceso se detiene. De lo contrario, se realiza una iteración. (Introduccion a la Investigacion de Operaciones, pág. 304/305)

Partiendo de una solución inicial factible (Vogel, Esquina Noroeste, etc.) es necesario probar la optimización de la asignación evaluando todas las celdas no asignadas (vacías) y determinando la conveniencia de asignar en ellas. En la evaluación de las celdas vacías para un posible mejoramiento, una ruta cerrada (ciclo) es seleccionada. La ruta tiene movimientos horizontales y verticales, considerando que las celdas asignadas y no asignadas pueden ser brincadas en el movimiento para localizar una celda adecuada.

La adición y la resta asegura que las restricciones de la unidad de capacidad y la unidad de requerimientos no serán violadas.

Para evaluar la celda vacía se realiza la sumatoria de los costos de cada una de las celdas en la ruta.

Si alguna de estas evaluaciones arrojará un signo negativo (para un problema de minimización), entonces se deberá asignar en aquella celda con la evaluación más negativa. Esto indicará que una reducción en el costo total puede lograrse transfiriendo tantas unidades como sea posible a esa celda.

El número de unidades posibles a ser transferido será igual a la mínima cantidad que se encuentra asignada en las celdas de la ruta con costo negativo. Al realizarse esta transferencia debe asegurarse que las restricciones de la capacidad y de requerimientos no sean violadas (esto se hace agregando las unidades encontradas a asignar en las celdas con signo positivo y restando estas unidades de las celdas con signo negativo).

Si las evoluciones de todas las celdas vacías arrojan valores positivos, entonces se dice que la asignación es óptima.

Iteración:

1. Se determina la variable básica entrante: se elige la variable no básica sij que tiene el valor más negativo —en términos absolutos— para cij - ui - vj.

2. Se determina la variable básica saliente: se identifica la reacción en cadena que se necesita para conservar la factibilidad cuando aumenta el valor de la variable básica entrante. Entre las celdas donadoras se selecciona la variable básica que tiene el menor valor.

3. Se determina la nueva solución BF: se suma el valor de la variable básica saliente a las asignaciones de las celdas receptoras y se resta a las asignaciones de las celdas donadoras. (Introduccion a la Investigacion de Operaciones, pág. 304)

A continuación te presentamos algunos mapas mentales y ejemplos que te ayudarán a entender mejor estos temas.

Referencias

•           Hillier, F. (s.f.). Introduccion a la Investigacion de Operaciones. México, D.F: Mc Graw Hill.
•           https://jorgesosasanchez.wordpress.com/unidad-2/2-1-problema-de-transporte-2/2-1-2-procedimiento-de-optimizacion/
•           http://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/m%C3%A9todo-de-aproximaci%C3%B3n-de-vogel/
•           http://yanerios.blogspot.mx/2013/10/metodo-de-aproximacion-de-vogel.html

5.5 DEFINICION DEL PROBLEMA DE ASIGNACION

Definición del problema de asignación.

Primero que nada, es importante empezar con el pie derecho al definir un tema importante como el que veremos a continuación.

El problema de asignación se puede definir fácilmente como “Asignar la mejor persona para el puesto”.

Pero veremos que este tipo de problema no se dedicara solamente a la asignación de personas así que daremos una definición más formal para el problema de asignación:

El problema de asignación es un tipo especial de problema de programación lineal en el que los asignados son recursos que se destinan a la realización de tareas.

Ejemplos

Múltiples son los casos en los que como ingenieros industriales podemos hacer uso del problema de asignación para resolver diversas situaciones, entre los que cabe mencionar se encuentran la asignación de personal a máquinas, asignados que pueden ser empleados a quienes se tiene que dar trabajo, herramientas a puestos de trabajos, horarios a maestros, candidatos a vacantes, huéspedes a habitaciones, comensales a mesas, vendedores a zonas territoriales etc.

Como observamos en algunos ejemplos los asignados no tienen que ser personas. También pueden ser máquinas, vehículos o plantas, o incluso periodos a los que se asignan tareas.

En el modelo de asignación la idea fundamental de resolución es ¿qué fuente satisface mejor el destino?, y dado que hemos asociado el modelo a una gran diversidad de circunstancias esta pregunta puede plantearse en múltiples contextos, como ¿qué candidato es el idóneo para la vacante?, o ¿qué personal es el indicado para la línea productiva?, o ¿qué personal es el mejor para ejecutar determinada tarea?

Supuestos que debe de cumplir un problema de asignación.

Para que se ajuste a la definición de un problema de asignación, es necesario que este tipo de aplicaciones se formule de manera tal que se cumplan los siguientes supuestos.

1.    El número de asignados es igual al número de tareas. (Este número se denota por n.)

2.    A cada asignado se le asigna sólo una tarea.

3.    Cada tarea debe realizarla sólo un asignado.

4.    Existe un costo c_ij asociado con el asignado i (i= 1, 2, . . ., n) que realiza la tarea j (j= 1,2, . . ., n).

5.    El objetivo es determinar cómo deben hacerse las n asignaciones para minimizar los costos totales.

Es importante mencionar que muchas aplicaciones potenciales no se adaptan por completo al problema de asignación. Con frecuencia es posible reformular el problema para hacerlo que se ajuste. Por ejemplo, muchas veces se pueden usar asignados ficticios o tareas ficticias con este fin.

Formas de representar el modelo y restricciones.

El modelo general de asignación con n trabajadores y n puestos se representa en la tabla siguiente:

El elemento cij representa el costo de asignar al trabajador i al puesto j (i, j = 1, 2, .., n).

El modelo matemático para manejar el problema de asignación utiliza las siguientes variables de decisión:

para i = 1, 2, . . . , n y j = 1, 2, . . . , n.  Entonces, cada xij es una variable binaria que toma valores 0 o 1. Las variables binarias son importantes en investigación de operaciones para representar las decisiones de sí o no.

En este caso, las decisiones de sí o no son: ¿debe el asignado i realizar la tarea j ? Si Z es el costo total, el modelo del problema de asignación es:

sujeta a:

y

El primer conjunto de restricciones funcionales especifica que cada asignado realice sólo una asignación, mientras que el segundo conjunto requiere que cada asignación sea realizada sólo por un asignado.

Las restricciones funcionales del modelo de asignación evitan que las variables sean mayores que 1, y las restricciones de no negatividad impiden que existan valores menores que cero. Por tanto, si se elimina la restricción binaria para poder resolver el problema de asignación como un problema de programación lineal, las soluciones que se obtienen (incluso la solución óptima final) satisfacerán en forma automática la restricción binaria.

El problema de asignación puede describirse de manera similar, como se ve en la figura que se muestra abajo. En este caso la primera columna enumera los n asignados y la segunda las n tareas. Los números entre corchetes indican el número de asignados que se proporcionan en ese lugar de la red, por lo cual los valores de la izquierda son 1 de manera automática, mientras que los valores de -1 de la derecha indican que cada tarea utiliza un asignado.

 

Representación de red del problema de asignación

 Referencias

Lieberman, G., & Hillier, F. (2010). Problema de asignación. En G. J. Frederick S. Hillier, Introducción a la Investigación de operaciones (Novena ed., pp. 309-312). México: Mc Graw Hill.

Taha, H. (2004). El Modelo de asignación. En H. A. Taha, Investigación de operaciones (Séptima ed., p. 196). México: Pearson.