Ruta más corta

El problema de la ruta mas corta determina la distancia menor entre un punto de origen y un punto de destino.

Un problema de la ruta mas corta involucra una red conexa con un costo no negativo asociado a cada rama. A un nodo se le denomina fuente y a otro se le denomina destino. El objetivo es determinar una ruta que una a la fuente con el origen, de manera que la suma de los costos asociados con las ramas en la ruta sea la mínima.

DEFINICIÓN DEL PROBLEMA

• -Se tienen n nodos, partiendo del nodo inicial 1 y terminando en el nodo final n.
• -Arcos bidireccionales conectan los nodos i y j con distancias mayores que cero.
• -Se desea encontrar la ruta de mínima distancia que conecta el nodo 1 con el nodo n.

Por medio de la aplicación del algoritmo de este problema podemos conocer la menor distancia entre un nodo origen y un nodo destino.

Pasos a seguir:

1. Elaborar un cuadro con todos los nodos y los ramales que salen de él.
2. Partiendo del origen, debemos encontrar el nodo más cercano a él.
3. Anular todos los ramales que entren al nodo más cercano elegido.
4. Comenzando en el origen se debe encontrar el nodo más cercano a él, por intermedio del(los) nodo(s) ya elegido(s) y volver al tercer paso hasta llegar al destino.

 Problemas de Asignación

El Problema de la Asignación es un problema clásico de la Investigación de Operaciones y es un caso particular del Problema del Transporte.

Este problema se trata de asignar una serie de Recursos a una serie de tareas.

Tiene una limitante y es que a cada tarea se le puede asignar sólo un recurso, pueden sobrar recursos o podrían sobrar tareas pero no se le puede asignar dos recursos a una misma tarea, o más.

Los problemas de asignación de hicieron con el objetivo de reducir el tiempo de fabricación al mínimo para así aumentar la producción lo máximo posible organizar las máquinas y los trabajadores, Para así optimizar los recursos que posee la organización en cuestión

Para satisfacer la demanda que exige el día a día en las operaciones de la empresa sin estos métodos de asignación los precios de los productos se dispararían por las nubes, y las fábricas serian todo un caos, los recursos se desperdiciarían.

Métodos de solución

Método húngaro

Este método utiliza la propiedad de reducción de matrices para reducir la matriz original de costo, hasta que los costos C i j asociados con la asignación óptima, sean cero y todos los otros costos sean no negativos.

En cada iteración del método húngaro, se reduce la matriz de tal manera que haya al menos un cero en cada renglón y columna, comprobando con el teorema de König si se ha alcanzado la solución óptima. Si el número mínimo de renglones y/o columnas necesarios para cubrir todos los ceros es n, entonces existe una asignación óptima (no necesariamente única).

Problemas de Transporte

El problema general del transporte se refiere a la distribución de mercancía desde cualquier conjunto de centro de suministro, denominados orígenes (fuentes), hasta cualquier conjunto de centros de recepción, llamados destinos, de tal forma que se minimicen los costos totales de distribución. 

 Cada origen tiene que distribuir ciertas unidades a los destinos y cada destino tiene cierta demanda de unidades que deben recibir de los orígenes.

 Estructura

 

En los renglones se ubican los orígenes indicando en la columna de la derecha los recursos (oferta disponible). 

En las columnas se ubican los distintos destinos indicando en el último renglón los totales  demandados. 

En el pequeño recuadro ubicado en la margen superior derecha se indica el costo de distribuir una unidad desde el origen hasta ese destino y en la parte inferior de cada recuadro se registran las asignaciones Xi para cada variable. 

En los casos donde la sumatoria de los recursos y las demanda no sean las mismas, se agrega un origen o destino ficticio con la cantidad que permita cumplir la propiedad de soluciones factibles.

Como se puede observar cualquier modelo de transporte se compone de unidades de un bien a distribuir, m orígenes, n destinos, recursos en el origen, demandas en los destinos y costos de distribución por unidad. 

Adicionalmente, se tienen varios supuestos:

• Supuesto de requerimientos: cada origen tiene un suministro fijo de unidades que se deben distribuir por completo entre los destinos.
• Supuesto de costo: el costo de distribuir unidades de un origen a un destino cualquiera es directamente proporcional al número de unidades distribuidas.
• Propiedad de soluciones factibles: un problema de transporte tiene soluciones factible si y sólo si la sumatoria de recursos en lo m orígenes es igual a la sumatoria de demandas en los destinos.
• Propiedad de soluciones enteras: En los casos en los que tanto los recursos como las demandas toman un valor entero, todas las variables básicas (asignaciones), de cualquiera de las soluciones básicas factibles (inclusive la solución optima), asumen también valores enteros.

Después de planteado el modelo de transporte, el siguiente paso es obtener una solución básica factible, la cual se puede obtener a partir de cualquiera de los 3 criterios siguientes:

1. Regla de la esquina noroeste.

2. Método de la ruta preferente.

3. Método de aproximación de Vogel

ANALISIS DE REDES

 ANALISIS DE

 REDES

El análisis de redes es el área encargada de analizar las redes mediante la teoría de redes (conocida más genéricamente como teoría de grafos).

Las redes pueden ser de diversos tipos:

•  Social
•  Transporte
•  Eléctrica
•  Biológica
•  Internet
•  Información
•  Epidemiología

Cuando se habla de una red, se entiende como un grupo de individuos que, en forma agrupada o individual, se relacionan con otros con un fin especifico, caracterizado por la existencia de flujo de información. Las redes pueden tener muchos o pocos actores y una o mas clases de relaciones entre pares de actores.

Terminología de Redes

* Flujo: Corresponde a la cantidad que debe transportarse desde un nodo i a un nodo j a través de un arco que los conecta.  La siguiente notación es usada: Xij= cantidad de flujo Uij= cota mínima de flujo que se debe transportar Lij= cota maxíma de flujo que se puede transportar.

 * Arcos dirigidos /no dirigidos:  Cuando el flujo puede transportarse en una sola dirección se tiene un arco dirigido (la flecha indica la dirección).  Si el flujo puede transportarse en ambas direcciones existe un arco no dirigido (sin flecha).

* Nodos adyacentes: Un nodo j es adyacente con un nodo i si existe un arco que une el nodo j con el nodo i.

Rutas/Conexión entre nodos

*Ruta: Una colección de arcos formados por una serie de nodos adyacentes; los nodos están conectados si existe una ruta entre ellos.

 

Ciclos / Arboles /Arboles expandidos

* Ciclos : Un ciclo se produce cuando al partir de un nodo por un cierto camino se vuelve al mismo nodo por otra ruta.

 * Arbol : Una serie de nodos que no contienen ciclos.

 *Arbol expandido: Es un árbol que conecta todos lo nodos de la red (contiene n-1 arcos).