RT info:eu-repo/semantics/bachelorThesis
T1 Teoría poliédrica en programación lineal entera
A1 Alonso González, Rocío
A2 Universidad de Valladolid. Facultad de Ciencias
K1 Programación lineal entera
K1 Cortes de Gomory
K1 Planos de corte
AB La programación lineal entera es una rama importante de la programación linealen la que las variables toman valores enteros, lo que dificulta la búsqueda de lasolución óptima.Sin embargo, se emplea en diferentes ámbitos con el fin de optimizar una funciónobjetivo sujeta a una serie de restricciones.Este trabajo se centra en dar una descripción ideal de la envolvente convexa dela región factible y acercarnos lo más posible a la solución óptima del problemamediante la utilización de algoritmos de corte.En el primer capítulo se presentan definiciones y resultados fundamentales dela teoría poliédrica, además de la formulación de los diferentes tipos de problemasde programación entera (pura, mixta y binaria) y el Teorema de Meyer, resultadoprincipal de este capítulo.El Capítulo 2 se centra en la resolución efectiva de problemas de programación entera,debido a que se conoce la descripción completa de la envolvente convexa. Seestudian los conceptos de poliedro entero y matrices unimodulares y se analizan losproblemas de transporte y flujo de redes.En el tercer capítulo se profundiza en la descripción parcial de la envolvente convexamediante familias de desigualdades, se introducen los conceptos de desigualdadesválidas, relajaciones y cortes. Se detalla el algoritmo de planos de corte, como herramientapara aproximarse a la solución óptima de un problema de programaciónentera. Y finalmente se da una lista con una breve explicación de algunas familiasde desigualdades.Por último en el Capítulo 4 se tratan los cortes de Gomory, el algoritmo de cortesfraccionarios de Gomory tanto para el problema de programación entera puro comopara el mixto, y se estudia la efectividad de dicho algoritmo para llegar a una solución óptima en un número finito de iteraciones.
YR 2024
FD 2024
LK https://uvadoc.uva.es/handle/10324/71029
UL https://uvadoc.uva.es/handle/10324/71029
LA spa
NO Departamento de Estadística e Investigación Operativa
DS UVaDOC
RD 24-abr-2025