Diferencias
Muestra las diferencias entre dos versiones de la página.
Ambos lados, revisión anteriorRevisión previaPróxima revisión | Revisión previa | ||
analisis [2010/10/20 07:39] – [algoritmo de Dijkstra] admin | analisis [2023/03/13 14:40] (actual) – editor externo 127.0.0.1 | ||
---|---|---|---|
Línea 1: | Línea 1: | ||
=====Análisis y casos==== | =====Análisis y casos==== | ||
- | {{ : | + | ~~NOTOC~~ |
+ | {{ : | ||
+ | |||
+ | ===¿cómo usar los algoritmos en Grafos? | ||
+ | En el modo de edición gráfico observará una barra de herramientas con los siguientes botones.{{: | ||
* Caminos | * Caminos | ||
* camino mínimo | * camino mínimo | ||
Línea 13: | Línea 17: | ||
* problema de transbordo | * problema de transbordo | ||
* problema de asignación | * problema de asignación | ||
+ | * localización a coste mínimo | ||
* Rutas | * Rutas | ||
+ | * circuito euleriano | ||
* problema de viajante de comercio | * problema de viajante de comercio | ||
* problema de //m// viajantes de comercio | * problema de //m// viajantes de comercio | ||
Línea 19: | Línea 25: | ||
* problema de rutas con vehículos capacitados (CVRP) | * problema de rutas con vehículos capacitados (CVRP) | ||
- | Prueba | + | Al desplegar cualquiera |
+ | {{ :grafos_activandoanalisis.png? | ||
+ | Recuerde que para activar un nodo origen (Nd1) debe hacer click sobre él con el botón izquierdo del ratón, el nodo destino (Nd2) se selecciona haciendo click el botón derecho del ratón. Conforme se encuentre el estado de la selección, observará que se activan o desactivan las opciones de menú. | ||
+ | En el caso de que Grafos requiera información adicional, se mostrará en pantalla una pequeña ventana con los datos de entrada. Grafos le da libertad para analizar un mismo grafo desde diferentes puntos de vista en cualquier momento, en caso de que la estructura del grafo no sea coherente con el algoritmo, de que falten datos asociados a los arcos, o de no factibilidad, | ||
- | + | Si todo es correcto, a continuación el algoritmo comenzará su proceso de cálculo. El tiempo requerido dependerá del tipo de heurística, | |
- | < | + | |
- | + | ||
- | + | ||
- | < | + | |
- | alt="" | + | |
- | + | ||
- | < | + | |
- | ====Algoritmos==== | + | Al finalizar el algoritmo, ocurrirán varias cosas: |
- | Seguidamente se describirán | + | * Se muestra una ventana con los Resultados del Análisis. Donde se muestra la solución obtenida |
+ | {{ : | ||
- | ===¿qué | + | Utilizar esta ventana |
- | Una posible definición de [[wpes> | + | {{ : |
- | ===algoritmo | + | * Se dibujará la solución sobre el grafo, subrayando los arcos y nodos de la solución. |
+ | {{ : | ||
- | **//camino mínimo - camino máximo//** | + | {{: |
- | **Lester Randolph Ford** es uno de los pioneros en el campo de la programación de flujos en grafos. Es el hijo de L.R. Ford Sr. (quién también es un matemático distinguido) y nació el 23 de septiembre de 1927. L. R. Ford Sr es elogiado por su ejemplar trabajo en matemáticas al inventar una interpretación geométrica absolutamente maravillosa de la serie de Farey. También le acredita su trabajo ' | + | {{ : |
- | Al continuar | + | Con todo esto, ya está preparado para aprender más sobre los diferentes algoritmos y su utilidad. |
+ | ====Algoritmos==== | ||
+ | Una posible definición de [[wpes> | ||
- | Mientras trabajó en RAND CORPORATION, | + | Seguidamente |
- | + | ||
- | La mayoría del trabajo de Ford lo hizo en la colaboración con Fulkerson, al parecer los dos hacían una buena asociación. Sin embargo, en 1956 presentó varios artículos firmados por él sólo. Ha sido el autor de diversos algoritmos que se han refinado con los años y que todavía se utilizan para solucionar la mayoría de problemas de grafos. | + | |
- | + | ||
- | **algoritmo de Bellman-Ford (camino mínimo)** | + | |
- | + | ||
- | Soluciona el problema de la ruta más corta o camino mínimo desde un nodo origen, de un modo más general que el Algoritmo de Dijkstra, ya que permite valores negativos en los arcos. | + | |
- | + | ||
- | El algoritmo devuelve un valor booleano si encuentra un circuito o lazo de peso negativo. En caso contrario calcula y devuelve el camino mínimo con su coste. Para cada vértice v perteneciente a V, se mantiene el atributo d[v] como cota superior o coste del camino mínimo desde el origen s al vértice v. A continuación se muestra el pseudocódigo del algoritmo: | + | |
- | < | + | |
- | Bellman-Ford (G,s) | + | |
- | + | ||
- | Inicializar | + | |
- | for cada v perteneciente a V[G] | + | |
- | do d[v] = infinito | + | |
- | p[v] = nulo | + | |
- | p[s] = 0 | + | |
- | + | ||
- | for i=1 to V[G]-1 | + | |
- | do for cada arco (u,v) perteneciente a A[G] | + | |
- | Relajación | + | |
- | if d[v] > d[u] + w(u,v) then | + | |
- | d[v] = d[u] + w(u,v) | + | |
- | p(v) = u | + | |
- | + | ||
- | for cada arco (u,v) chequea lazo de peso negativo | + | |
- | do if d[v] > d[u] + w(u,v) then | + | |
- | return FALSO 'el algoritmo no converge | + | |
- | return VERDADERO | + | |
- | </ | + | |
- | + | ||
- | **algoritmo de Bellman-Ford (camino máximo)** | + | |
- | + | ||
- | El problema de la ruta más larga puede ser transformado en el de ruta más corta cambiando el signo de los costes de los arcos. De manera alternativa se puede transformar también cambiando los procesos de inicialización y relajación. En este caso el problema es inconsistente para circuitos de peso positivo. | + | |
- | + | ||
- | < | + | |
- | Inicializar | + | |
- | for cada v perteneciente a V[G] | + | |
- | do d[v] = - infinito | + | |
- | p[v] = nulo | + | |
- | p[s] = 0 | + | |
- | Relajación | + | |
- | if d[v] < d[u] + w(u,v) then | + | |
- | d[v] = d[u] + w(u,v) | + | |
- | p(v) = u | + | |
- | </ | + | |
- | + | ||
- | Puede encontrar más información en: | + | |
- | * [[wp> | + | |
- | * [[http:// | + | |
- | * Bellman, R. E., On a routing problem, quarterly of //Applied Mathematics//, | + | |
- | * Ford, L. R.Jr., Network Flow Theory, Paper P-923, RAND Corporation, | + | |
- | + | ||
- | ===algoritmo de Floyd-Warshall=== | + | |
- | **//camino mínimo entre todos los pares de nodos//** | + | |
- | + | ||
- | {{ : | + | |
- | + | ||
- | Fue uno de los inventores del // | + | |
- | + | ||
- | **algoritmo de Floyd-Warshall (todos los caminos mínimos)** | + | |
- | + | ||
- | El problema que intenta resolver este algoritmo es el de encontrar el camino más corto entre todos los pares de nodos o vértices de un grafo. Esto es semejante a construir una tabla con todas las distancias mínimas entre pares de ciudades de un mapa, indicando además la ruta a seguir para ir de la primera ciudad a la segunda. Este es uno de los problemas más interesantes que se pueden resolver con algoritmos de grafos. | + | |
- | + | ||
- | Existen varias soluciones a este problema y los algoritmos a aplicar dependen también de la existencia de arcos con pesos o costes negativos en el grafo. En el caso de no existir pesos negativos, sería posible ejecutar V veces el algoritmo de Dijkstra para el cálculo del camino mínimo, donde V es el número de vértices o nodos del grafo. Esto conllevaría un tiempo de ejecución de O(V^3) (aunque se puede reducir). Si existen arcos con pesos negativos, se puede ejecutar también V veces el Algoritmo de Bellman-Ford, | + | |
- | + | ||
- | El algoritmo de Floyd-Warshall (' | + | |
- | + | ||
- | < | + | |
- | Floyd-Warshall (G) | + | |
- | + | ||
- | Inicializar | + | |
- | D = A ' matriz de distancias = matriz de arcos | + | |
- | + | ||
- | si i=j o Dij= infinito entonces Pi,j = nulo sino Pi,j=i ' | + | |
- | + | ||
- | for k = 1 to V | + | |
- | for i = 1 to V | + | |
- | for j = 1 to V | + | |
- | Di,j = min(Di,j , Di,k + Dk,j ) | + | |
- | si min = Di,k + Dk,j entonces | + | |
- | Pi,j = Pk,j | + | |
- | fin | + | |
- | </ | + | |
- | + | ||
- | Este algoritmo se puede aplicar a multitud de problemas, incluyendo el diseño de circuitos, el diseño de rutas de transporte, aproximaciones al problema del viajante de comercio, o como base de otros algoritmos más complejos. | + | |
- | * Robert W. Floyd, Algorithm 97 (Shortest Path). Communications of the ACM, 5(6):345, 1962. | + | |
- | * Stephan Warshall, A theorem on boolean matrices. //Journal of the ACM//, 9(1):11-12, 1962. | + | |
- | * C. H. Papadimitriou, | + | |
- | + | ||
- | ===algoritmo de Kruskal=== | + | |
- | + | ||
- | **//árbol de coste total mínimo/ | + | |
- | + | ||
- | {{ : | + | |
- | + | ||
- | El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos. | + | |
- | + | ||
- | Un árbol (spanning tree) de un grafo es un subgrafo que contiene todos sus vértices o nodos. Un grafo puede tener múltiples árboles. Por ejemplo, un grafo completo de cuatro nodos (todos relacionados con todos) tendría 16 árboles. | + | |
- | + | ||
- | La aplicación típica de este problema es el diseño de redes telefónicas. Una empresa con diferentes oficinas, trata de trazar líneas de teléfono para conectarlas unas con otras. La compañía telefónica le ofrece esta interconexión, | + | |
- | + | ||
- | La formulación del MST también ha sido aplicada para hallar soluciones en diversas áreas (diseño de redes de transporte, diseño de redes de telecomunicaciones - TV por cable, sistemas distribuidos, | + | |
- | + | ||
- | Otra aplicación menos obvia es que el árbol de coste total mínimo puede ser usado como solución aproximada al problema del viajante de comercio (traveling salesman problem), recuerde que encontrar la solución óptima a este problema es NP-Hard. La manera formal de definir este problema es encontrar la trayectoria más corta para visitar cada punto al menos una vez. Nótese que si se visitan todos los puntos exactamente una vez, lo que se tiene es un tipo especial de árbol. En el ejemplo anterior, 12 de los 16 árboles son trayectorias de este tipo. Si se tiene una trayectoria que visita algunos vértices o nodos más de una vez, siempre se puede soltar algunos nodos del árbol. En general el peso del árbol total mínimo es menor que el del viajante de comercio, debido a que su minimización se realiza sobre un conjunto estrictamente mayor. Existen diferentes algoritmos y maneras de usar el árbol de coste total mínimo para encontrar la solución al problema del viajante de comercio (con resultados cercanos al óptimo). | + | |
- | + | ||
- | **algoritmo de Kruskal (árbol de coste total mínimo)** | + | |
- | + | ||
- | Dado un grafo G con nodos conectados por arcos con peso (coste o longitud): el peso o coste total de un árbol será la suma de pesos de sus arcos. Obviamente, árboles diferentes tendrán un coste diferente. El problema es entonces ¿cómo encontrar el árbol de coste total mínimo? | + | |
- | + | ||
- | Una manera de encontrar la solución al problema del árbol de coste total mínimo, es la enumeración completa. Aunque esta forma de resolución es eficaz, no se puede considerar un algoritmo, y además no es nada eficiente. | + | |
- | + | ||
- | Este problema fue resuelto independientemente por Dijkstra (1959), Kruskal (1956) y Prim (1957) y la existencia de un algoritmo polinomial (que todos ellos demostraron) es una grata sorpresa, debido a que un grafo con N vértices puede llegar a contener NN-2 subárboles. A lo largo de la historia se ha hecho un gran esfuerzo para encontrar un algoritmo rápido para este problema. El algoritmo de Kruskal es uno de los más fáciles de entender y probablemente el mejor para resolver problemas a mano. | + | |
- | + | ||
- | El algoritmo se basa en una propiedad clave de los árboles que permite estar seguros de si un arco debe pertenecer al árbol o no, y usar esta propiedad para seleccionar cada arco. Nótese en el algoritmo, que siempre que se añade un arco (u,v), éste será siempre la conexión más corta (menor coste) alcanzable desde el nodo u al resto del grafo G. Así que por definición éste deberá ser parte del árbol. | + | |
- | + | ||
- | Este algoritmo es de tipo greedy, ya que a cada paso, éste selecciona el arco más barato y lo añade al subgrafo. Este tipo de algoritmos pueden no funcionar para resolver otro tipo de problemas, por ejemplo para encontrar la ruta más corta entre los nodos a y b. | + | |
- | + | ||
- | Para simplificar, | + | |
- | + | ||
- | A continuación se muestra el pseudocódigo del algoritmo: | + | |
- | < | + | |
- | Kruskal (G) | + | |
- | E(1)=0, E(2)= todos los Arcos del grafo G | + | |
- | Mientras E(1) contenga menos de n-1 arcos y E(2)=0 do | + | |
- | De los arcos de E(2) seleccionar el de menor coste -->e(ij) | + | |
- | E(2)= E(2) - {e(ij)} | + | |
- | Si V(i), V(j) no están en el mismo árbol entonces | + | |
- | | + | |
- | end Si | + | |
- | end do | + | |
- | Fin del algoritmo | + | |
- | </ | + | |
- | + | ||
- | Este problema puede ser resuelto por diferentes algoritmos, e incluso en la actualidad sigue siendo tema de interés en investigaciones. Es interesante la lectura de los siguientes algoritmos (que resuelven este problema para diferentes supuestos), aunque son bastante complejos y probablemente no requiera utilizarlos a no ser que trabaje con grafos de grandes dimensiones: | + | |
- | + | ||
- | * Karger, Klein, and Tarjan, A randomized linear-time algorithm to find minimum spanning trees, //J. ACM//, vol. 42, 1995, pp. 321-328. | + | |
- | * Fredman and Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, 31st IEEE Symp. Foundations of //Comp. Sci.//, 1990, pp. 719-725. | + | |
- | * Gabow, Galil, Spencer, and Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. // | + | |
- | + | ||
- | Puede encontrar más información en: | + | |
- | * [[http:// | + | |
- | * [[http:// | + | |
- | * J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. of the American Mathematical Society, 7:48-50, 1956. | + | |
- | ===algoritmo de Prim=== | + | |
- | + | ||
- | **//árbol de coste total mínimo/ | + | |
- | + | ||
- | **Robert Prim** en 1957 descubrió un algoritmo para la resolución del problema del Árbol de coste total mínimo (minimum spanning tree - MST). Este problema es un problema típico de optimización combinatoria, | + | |
- | + | ||
- | En los años 60 estos científicos del Math Center (Bell Labs) fueron los pioneros de la moderna teoría de secuenciación, | + | |
- | + | ||
- | El algoritmo de Prim encuentra un árbol de peso total mínimo conectando nodos o vértices con arcos de peso mínimo del grafo sin formar ciclos. | + | |
- | + | ||
- | Al igual que el algoritmo de Kruskal, el de Prim también ha sido aplicado para hallar soluciones en diversas áreas (diseño de redes de transporte, diseño de redes de telecomunicaciones - TV por cable, sistemas distribuidos, | + | |
- | + | ||
- | **algoritmo de Prim (árbol de coste total mínimo)** | + | |
- | + | ||
- | Consiste en dividir los nodos de un grafo en dos conjuntos: procesados y no procesados. Al principio, hay un nodo en el conjunto procesado que corresponde a el equipo central; en cada interacción se incrementa el grafo de procesados en un nodo (cuyo arco de conexión es mínimo) hasta llegar a establecer la conexión de todos los nodos del grafo a procesar. A continuación se muestra el pseudocódigo del algoritmo: | + | |
- | + | ||
- | < | + | |
- | Prim ( L [1..n , 1..n ]) : ' | + | |
- | + | ||
- | ' | + | |
- | + | ||
- | T =NULL 'T contendrá los arcos del árbol de extensión mínima Distmin[1]=-1 | + | |
- | + | ||
- | para i=2 hasta n hacer | + | |
- | más_próximo [ i ]=1 | + | |
- | distmin [ i ]=L [ i , 1] | + | |
- | + | ||
- | para i=1 hasta n -1 hacer | + | |
- | min=infinito | + | |
- | + | ||
- | para j=2 hasta n hacer | + | |
- | si 0 <= distmin [ j ] < min entonces | + | |
- | min=distmin [ j ] | + | |
- | k=j | + | |
- | + | ||
- | T=T union {{mas_próximo [ k ], k }} | + | |
- | | + | |
- | + | ||
- | para j=2 hasta n hacer | + | |
- | si L [ j , k ] < distmin [ j ] entonces | + | |
- | distmin [ j ]=L [ j , k ] | + | |
- | más_próximo [ j ]=k | + | |
- | + | ||
- | devolver T | + | |
- | </ | + | |
- | + | ||
- | Algunos trabajos han comparado la eficiencia entre los algoritmos de Kruskal y de Prim: | + | |
- | + | ||
- | Sea a es el número de arcos y n el número de nodos. El algoritmo de Kruskal requiere un tiempo que está en O(a log n). Para un grafo denso, a tiende a n(n-1)/2, por lo que el algoritmo requiere un tiempo que está en O(n2 log n), y el algoritmo de Prim puede ser mejor O(n2). En un grafo disperso, a tiende a n-1, por lo que el algoritmo de Kruskal requiere un tiempo que está en O(n log n) y el algoritmo de Prim es menos eficiente. Sin embargo, si el algoritmo de Prim se implementa con montículos, | + | |
- | + | ||
- | * Si a es aproximadamente igual a n (grafo con pocos arcos) conviene usar Kruskal | + | |
- | * Si a es aproximadamente igual a n2 (grafo denso) conviene usar Prim | + | |
- | + | ||
- | En cualquier caso, la complejidad del algoritmo de Kruskal depende de la técnica de ordenación empleada. El algoritmo de Prim requiere más memoria que el algoritmo de Kruskal. Ambos algoritmos son relativamente fáciles de paralelizar. Puede encontrar más información en: | + | |
- | * R.C. Prim, Shortest connection networks and some generalizations, | + | |
- | + | ||
- | + | ||
- | ===algoritmo de Ford-Fulkerson=== | + | |
- | **//flujo máximo// | + | |
- | + | ||
- | Se puede considerar un grafo como una red de flujo. Donde un nodo fuente produce o introduce en la red cierta cantidad de algún tipo de material, y un nodo sumidero lo consume. Cada arco, por tanto, puede considerarse como un conducto que tiene cierta capacidad de flujo. De igual modo que en redes eléctricas (Ley de Kirchhoff), la suma de flujos entrantes a un nodo, debe ser igual a la suma de los salientes (principio de conservación de energía), excepto para el nodo fuente y el nodo sumidero. | + | |
- | + | ||
- | Por tanto, el problema de flujo máximo se enuncia como: ¿cuál es la tasa a la cual se puede transportar el material desde el nodo fuente al nodo sumidero, sin violar las restricciones de capacidad?. Este algoritmo se puede usar para resolver modelos de: transporte de mercancías (logística de aprovisionamiento y distribución), | + | |
- | + | ||
- | Una red de flujo es un grafo dirigido G=(V,E) donde cada arco (u,v) perteneciente a E tiene una capacidad no negativa. Se distinguen dos nodos: la fuente o nodo s, y el sumidero o nodo t. Si existen múltiples fuentes y sumideros, el problema se puede simplificar añadiendo una fuente común y un sumidero común. Este algoritmo depende de tres conceptos | + | |
- | * Un camino de aumento, es una trayectoria desde el nodo fuente s al nodo sumidero t que puede conducir más flujo. | + | |
- | * La capacidad residual es la capacidad adicional de flujo que un arco puede llevar c_f (u,v) = c(u,v) - f(u,v) | + | |
- | * Teorema de Ford-Fulkerson (1962): En cualquier red, el flujo máximo que fluye de la fuente al destino es igual a la capacidad del corte mínimo que separa a la fuente del destino. | + | |
- | + | ||
- | El algoritmo es iterativo, se comienza con f(u,v)=0 para cada par de nodos y en cada iteración se incrementa el valor del flujo buscando un camino de aumento. El proceso se repite hasta no encontrar un camino de aumento. A continuación se muestra el pseudocódigo del algoritmo: | + | |
- | + | ||
- | < | + | |
- | Ford-Fulkerson (G,s,t) | + | |
- | + | ||
- | para cada arco (u,v) de E | + | |
- | + | ||
- | f(u,v) = 0 | + | |
- | f(v,u) = 0 | + | |
- | + | ||
- | mientras exista un camino p desde s a t en la red residual G_f | + | |
- | + | ||
- | c_f (p) = min {c_f (u,v) : (u,v) está sobre p} | + | |
- | + | ||
- | para cada arco (u,v) en p | + | |
- | + | ||
- | f(u,v) = f(u,v) + c_f (p) | + | |
- | f(u,v) = -f(u,v) | + | |
- | </ | + | |
- | + | ||
- | Una variación del algoritmo de Ford-Fulkerson es el algoritmo de Edmonds-Karp (J. Edmonds; R.M. Karp - 1972). En éste, el ' | + | |
- | + | ||
- | Puede encontrar más información en: | + | |
- | + | ||
- | * Ford, L. R. and Fulkerson, D. R. Flows in Networks. Princeton, NJ. Princeton University Press, 1962. | + | |
- | * Edmonds, J. and Karp, R. M. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. //J. ACM// 19, 248-264, 1972. | + | |
- | * Berge, C. Two Theorems in Graph Theory. Proc. Nat. Acad. Sci. USA 43, 842-844, 1957. | + | |
- | + | ||
- | + | ||
- | ===problema de transbordo / transporte=== | + | |
- | **//a coste mínimo// | + | |
- | + | ||
- | En este apartado se comentará la aplicación de la teoría de grafos para la resolución y optimización del flujo en una red. Concretamente se hablará de los Problemas de Suministro y Demanda. | + | |
- | + | ||
- | Dado un grafo G con vértices o nodos V conectados entre sí y clasificados en dos conjuntos X e Y. Los nodos x se considerarán como elementos de suministro (por ejemplo plantas productivas o proveedores), | + | |
- | + | ||
- | En la literatura, existen multitud de heurísticas y algoritmos | + | |
- | + | ||
- | En cualquier caso, este tipo de problemas es uno de los más interesantes de la teoría de grafos y de la investigación operativa. Su aplicación es visible y de gran importancia para la resolución de problemas reales en la Dirección de Operaciones y Logística. | + | |
- | + | ||
- | **problema del transbordo (coste mínimo)** | + | |
- | + | ||
- | Se puede considerar un grafo como una red de flujo. Donde los nodos proveedor producen o introducen en la red cierta cantidad de algún tipo de material, y los nodos cliente lo consumen. Cada arco, por tanto, puede considerarse como un conducto que tiene cierta capacidad de flujo (mínima y/o máxima) y un coste de transporte por unidad de material. | + | |
- | + | ||
- | Dado un grafo dirigido G=(V,E) con capacidades c (mínima y/o máxima) no negativas y también con coste de transporte no negativo (expresado por unidad de flujo) para los arcos E. | + | |
- | + | ||
- | Dado un conjunto de nodos X proveedores (con una capacidad b<0 de suministro), | + | |
- | + | ||
- | Además, se exige la condición de continuidad en los nodos. Esto es, la suma de flujos entrantes a un nodo menos la suma de los salientes, debe ser mayor o igual a la capacidad b del nodo. | + | |
- | + | ||
- | Por tanto, el problema de flujo máximo se enuncia como: ¿cuál es el flujo de transporte de cada arco con el cual se puede transportar el material desde los nodos proveedores a los nodos cliente, sin violar las restricciones de capacidad y continuidad y todo ello minimizando el coste total de transporte? | + | |
- | + | ||
- | MODELO MILP | + | |
- | + | ||
- | En el caso de Grafos, | + | |
- | + | ||
- | El problema de transbordo, se puede transformar en un problema clásico de flujo mínimo coste añadiendo un único nodo proveedor s y un único nodo de demanda t (ver Hitchcock-Koopmans, | + | |
- | + | ||
- | **problema del transporte (coste mínimo)** | + | |
- | + | ||
- | El problema del transporte es un problema de transbordo pero con un grafo dividido G=(S,T,E), con todos los nodos suministradores en S y los de demanda en T. Además, todos los arcos van dirigidos de S a T y no existen nodos de transbordo. | + | |
- | + | ||
- | El Problema de Asignación es un caso especial | + | |
- | + | ||
- | Puede encontrar más información en: | + | |
- | * Hitchcock, F. L.,The distribution of a Product from Several Sources to Numerous Localities, //J. Math. Phys.//, 20, no. 2 (April 1941), 224-30. | + | |
- | * Kuhn, H. W., The Hungarian Method for the Assignment Problem, //Naval Research Logistics Quaterly//, 2, nos. 1 and 2 (1955), 83-97. | + | |
- | * Ford, L. R. and Fulkerson, D. R. Flows in Networks. Princeton, NJ: Princeton University Press, 1962. | + | |
- | * Edmonds, J. and Karp, R. M. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. //J. ACM// 19, 248-264, 1972. | + | |
- | * Zadeh. N, A Bad Network Problem for the Simplex Method and other Minimum Cost Flow Algorithms, //Math. Prog.//, 5, no. 3 (December 1973), 255-66. | + | |
- | ===problema de asignación=== | + | |
- | **//a coste mínimo// | + | |
- | + | ||
- | El problema de asignación (Assignment Problem), es un problema de complejidad NP-completo. Esto es así, porque el número de posibles soluciones crece O(n^3). | + | |
- | + | ||
- | El problema de asignación debe su nombre a la aplicación | + | |
- | + | ||
- | La condición necesaria y suficiente para que este tipo de problemas tenga solución, es que se encuentre balanceado, es decir, que los recursos totales sean iguales a las demandas totales. Si hay más máquinas que trabajos se formula con desigualdades, | + | |
- | + | ||
- | Su aplicación es visible y de gran importancia para la resolución de problemas reales en la Dirección de Operaciones y Logística. Por ejemplo: vehículos a rutas, trabajadores, | + | |
- | + | ||
- | **problema de asignación (mínimo coste total)** | + | |
- | + | ||
- | Este problema es de especial interés ya que una de las preocupaciones de los gerentes de las empresas es la utilización más eficiente de sus recursos escasos. En este caso el problema tratará de asignar un conjunto de recursos limitados a un conjunto de actividades competitivas de la mejor manera posible (óptima). | + | |
- | + | ||
- | El modelo de asignación es un caso especial del modelo de transporte, en el que los recursos se asignan a las actividades en términos de uno a uno, haciendo notar que la matriz correspondiente debe ser cuadrada. Así entonces cada recurso debe asignarse, de modo único a una actividad particular o asignación. | + | |
- | + | ||
- | Este problema es fácil de enunciar. Se trata por ejemplo de un conjunto de //n// tareas que se deben asignar de la manera más eficiente posible a otro conjunto de m máquinas. Sea //x_ij// una variable binaria que indica si la tarea //i// se realizará con la máquina //j//. Mientras que //c_ij// representa el coste de dicha asignación, | + | |
- | + | ||
- | MODELO MILP | + | |
- | + | ||
- | El problema es lineal porque la función coste a optimizar así como las restricciones pueden ser expresadas como ecuaciones lineales. En el caso de Grafos, este problema se aborda a través del modelo anteriormente expuesto y su resolución mediante Programación Lineal Entera Mixta. El Algoritmo Húngaro de Kuhn (1955) es uno de los más utilizados para resolver este tipo de problemas. | + | |
- | + | ||
- | Otra estrategia para solucionar este problema además de la PLEM en la literatura existen multitud de estrategias de resolución para este problema: técnicas de aproximación, | + | |
- | Más información en: | + | * [[algoritmo_dijkstra|algoritmo de Dijkstra (camino mínimo)]] |
- | * Kuhn, H. W. (1955). The hungarian method for the assignment problem. //Naval Res. Logistic Quart.// 3, 253-258. | + | * [[algoritmo_bellman_ford|algoritmo de Bellman-Ford |
+ | * [[algoritmo_floyd_warshall|algoritmo de Floyd-Warshall (todos los caminos mínimos)]] | ||
+ | * [[algoritmo_kruskal|algoritmo de Kruskal (árbol de coste total mínimo)]] | ||
+ | * [[algoritmo_prim|algoritmo de Prim (árbol de coste total mínimo)]] | ||
+ | * [[algoritmo_ford_fulkerson|algoritmo de Ford-Fulkerson (flujo máximo)]] | ||
+ | * [[problema_transbordo_transporte|problema de transbordo/transporte (a coste mínimo)]] | ||
+ | * [[problema_asignacion|problema de asignación (a coste mínimo)]] | ||
+ | * problema de localización (a coste mínimo) | ||
+ | * [[algoritmo_hierholzer|circuito euleriano | ||
+ | * [[problema_tsp|problema del viajante de comercio TSP (distancia total mínima)]] | ||
+ | * [[problema_mtsp|problema de los m-viajantes de comercio m-TSP (distancia total mínima)]] | ||
+ | * problema de rutas (paso por nodos seleccionados a coste mínimo) | ||
+ | * [[problema_cvrp|problema de rutas con vehículos capacitados - CVRP (distancia total mínima)]] | ||
- | ===algoritmo=== | + | Como puede observar Grafos incorpora un buen conjunto de algoritmos, pero el desarrollo sigue. En el futuro se incorporarán más algoritmos de análisis, nuevas funciones de dibujado y edición. Gracias por utilizar Grafos. |
+ | ====librería de Grafos==== | ||
+ | :-? **DISCULPA LAS MOLESTIAS, EL SERVICIO DE LIBRERÍA DE GRAFOS NO ESTÁ DISPONIBLE** | ||
- | ===algoritmo=== | + | Desde la [[libreria|librería de Grafos]] podrá descargarse grafos de ejemplo para aprender a usar el programa, utilizar en sus clases, etc. Con la última versión de Grafos podrá subir a la nube y compartir con el resto sus mejores grafos. |
---- | ---- |