RT info:eu-repo/semantics/bachelorThesis
T1 El algoritmo Branch and Cut en programación lineal entera
A1 Noriega González, Carlos
A2 Universidad de Valladolid. Facultad de Ciencias
K1 Branch and Cut
K1 Programación entera
K1 Optimización
AB Los problemas de programación lineal entera aparecen en numerosas ocasiones modelandosituaciones del mundo real donde las variables de decisión deben tomar valores enteros.A  nales del siglo pasado se desarrolló el algoritmo de Branch and Cut combinando lasideas de dos métodos ya conocidos a mediados de siglo, como eran el algoritmo de Branchand Bound y el método de planos de corte. A lo largo de este trabajo presentaremos losdiferentes tipos de programación lineal, introduciremos brevemente los conceptos básicosde la teoría de poliedros y del método símplex; y abordaremos los métodos de Branch andBound y de planos de corte explicando los algoritmos y tratando todas sus particularidades.En el penúltimo capítulo llegaremos al objetivo central de este trabajo: entendercómo funciona el algoritmo de Branch and Cut y los diferentes procesos que se puedenllevar a cabo previamente para acelerar la búsqueda de la solución óptima utilizando estemétodo. Finalmente, pondremos en práctica todo lo expuesto en el trabajo planteandoun problema denominado Team Orienteering Problem. Resolveremos este problema utilizandodos implementaciones diferentes del Branch and Cut, comparando los resultadosobtenidos con ambos enfoques.
YR 2023
FD 2023
LK https://uvadoc.uva.es/handle/10324/63200
UL https://uvadoc.uva.es/handle/10324/63200
LA spa
NO Departamento de Estadística e Investigación Operativa
DS UVaDOC
RD 24-nov-2024