Os problemas de optimización en redes: algúns problemas clásicos de optimización en redes e a súa resolución

Abstract

Neste esencial imos facer un pequeno percorrido polas versións máis sinxelas dalgúns dos problemas clásicos de optimización en redes. Debido a que gran cantidade dos asuntos que nos rodean se organizan en redes, esta clase de problemas ten infinidade de aplicacións, entre outras, as seguintes: • deseño de rutas de vehículos ou de autoestradas, que minimicen a distancia entre dous vértices dados, • o deseño de redes de comunicacións, coma o trazado de redes de fibra óptica de maneira que se cubran os vértices da maneira máis económica posible, • determinar a cantidade máxima de enerxía que se pode enviar a través dunha rede eléctrica. Matematicamente, para a modelización deste tipo de situacións é preciso introducir o concepto de grafo. Un grafo queda determinado por un conxunto de vértices ou nodos, que denotaremos por N, que están conectados mediante os arcos ou arestas (no caso de grafos non dirixidos) ou as conexións (no caso de seren dirixidos) no conxunto M. Neste contexto, denomínase fluxo a calquera ben que circule polas conexións ou arcos do grafo.