Investigación Operativa - 2do Cuatrimestre 2019

¿Qué es la Investigación Operativa? Introducción a Programación Matemática. Metodología de Investigación Operativa. Definición del Problema. Elementos característicos de un Modelo Matemático. Construcción, resolución y validación del Modelo. Implementación y Control del Modelo. Clasificación de los Problemas de Optimización. Complejidad de Problemas y Algoritmos.

Tipo de soluciones de un Problema Lineal. Caracterización de Soluciones Óptimas. Puntos extremos, polítopos y poliedros. Cono característico. Técnicas para modelar problemas linealmente. Resolución gráfica de problemas de Programación Lineal en dos dimensiones. Introducción al lenguaje ZIMPL y al solver SCIP.

Forma estándar de un problema de Programación Lineal. Procedimiento del algoritmo SIMPLEX. Soluciones básicas factibles. Generación de Puntos Extremos. Criterio de Optimalidad. Comportamiento del algoritmo en problemas no acotados o con más de un óptimo. Soluciones básicas degeneradas. Regla de Bland. Método de diccionarios y método matricial para la resolución de problemas de Programación Lineal utilizando SIMPLEX. Fase I de SIMPLEX. Método de las dos fases y método Big-M. Complejidad del Algoritmo SIMPLEX. Problema Dual. Teorema Fundamental de Dualidad. Holgura Complementaria. Significado económico de las Variables Duales. Análisis de Sensibilidad.

Forma general de un modelo de Programación Lineal Entera. Problema de la Mochila. Problema de Asignación. El Problema del Vendedor Viajero. Problema de Localización de Plantas. Algoritmo de Branch & Bound. Programación Entera Binaria.

Definición de grafo. Vecindario y grado de un vértice. Vértice aislado y vértice universal. Grado máximo y mínimo de un grafo. Grafo regular. Complemento de un grafo. Subgrafo, subgrafo generador y subgrafo inducido. Grafos isomorfos. Grafos completos. Caminos, circuitos y ciclos. Distancia entre vértices. Grafos bipartitos. Grafos conexos. Puntos de corte, bloques y puentes.

Definición de árbol, hoja y bosque. Árboles dirigidos. Caracterización de un árbol. Árbol Generador Mínimo. Ejemplos de aplicación. Algoritmo de Kruskal. Algoritmo de Prim.

Introducción e historia del problema de coloreo. Coloreo de grafos. Clique, conjunto independiente y número cromático. Propiedades. Teorema de Brooks. Algoritmo de conexión-contracción. Polinomio cromático. Índice cromático. Variantes de problemas de coloreo.

Camino y Circuito Euleriano. Teorema de Euler. Camino y Circuito Hamiltoniano. El Problema del Viajante de Comercio.

Problemas de Camino Mínimo. Representación de grafos: matriz de adyacencia, matriz de incidencia, lista de aristas y lista de vecinos. Estructuras de datos: pila y cola. Recorrido BFS de un grafo, pseudocódigo y propiedades. Aplicación al reconocimiento de grafos bipartitos. Recorrido DFS, pseudocódigo y propiedades. Distancia en un grafo con aristas pesadas. Árbol de caminos mínimos. Algoritmo de Dijkstra & Moore. Algoritmo de Bellman & Ford. Algoritmo de Floyd-Warshall. Algoritmo de Dantzig.

Problema de flujo máximo. Definición de red de flujo, fuente y sumidero. Cortes en la red. Variantes de problema y aplicaciones. Algoritmo de Ford y Fulkerson.