2026-04-26T08:16:52Zhttps://uvadoc.uva.es/oai/requestoai:uvadoc.uva.es:10324/710292024-10-29T20:03:58Zcom_10324_38col_10324_852
Alonso González, Rocío
2024-10-29T14:33:18Z
2024-10-29T14:33:18Z
2024
https://uvadoc.uva.es/handle/10324/71029
La programación lineal entera es una rama importante de la programación lineal
en la que las variables toman valores enteros, lo que dificulta la búsqueda de la
solución óptima.
Sin embargo, se emplea en diferentes ámbitos con el fin de optimizar una función
objetivo sujeta a una serie de restricciones.
Este trabajo se centra en dar una descripción ideal de la envolvente convexa de
la región factible y acercarnos lo más posible a la solución óptima del problema
mediante la utilización de algoritmos de corte.
En el primer capítulo se presentan definiciones y resultados fundamentales de
la teoría poliédrica, además de la formulación de los diferentes tipos de problemas
de programación entera (pura, mixta y binaria) y el Teorema de Meyer, resultado
principal 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. Se
estudian los conceptos de poliedro entero y matrices unimodulares y se analizan los
problemas de transporte y flujo de redes.
En el tercer capítulo se profundiza en la descripción parcial de la envolvente convexa
mediante familias de desigualdades, se introducen los conceptos de desigualdades
válidas, relajaciones y cortes. Se detalla el algoritmo de planos de corte, como herramienta
para aproximarse a la solución óptima de un problema de programación
entera. Y finalmente se da una lista con una breve explicación de algunas familias
de desigualdades.
Por último en el Capítulo 4 se tratan los cortes de Gomory, el algoritmo de cortes
fraccionarios de Gomory tanto para el problema de programación entera puro como
para el mixto, y se estudia la efectividad de dicho algoritmo para llegar a una solución óptima en un número finito de iteraciones.
Integer linear programming is an important branch of linear programming in
which variables take on integer values, making it difficult to find the optimal solution.
However, it is used in different areas in order to optimize an objective function
subject to a series of constraints.
This work focuses on giving an ideal description of the convex envelope and getting
as close as possible to the optimal solution of the problem by using cutting
algorithms.
In the first chapter, definitions and fundamental results of polyhedral theory are
presented, as well as the formulation of the different types of integer programming
problems (pure, mixed and binary) and Meyer’s Theorem, the main result of this
chapter, is presented.
Chapter 2 focuses on the effective resolution of integer programming problems, as
the complete description of the convex envelope is known. The concepts of integer
polyhedron and unimodular matrices are studied and the problems of transport and
network flow are analyzed.
In the third chapter, the partial description of the convex envelope is deepened by
means of families of inequalities, the concepts of valid inequalities, relaxations and
cuts are introduced. The cutting plane algorithm is detailed as a tool to approximate
the optimal solution of an entire programming problem. And finally a list is given
with a brief explanation of some families of inequalities.
Finally, Chapter 4 deals with Gomory cuts, Gomory’s fractional cut algorithm for
both the pure and mixed integer programming problem, and studies the effectiveness
of this algorithm to arrive at an optimal solution in a finite number of iterations.
spa
info:eu-repo/semantics/openAccess
http://creativecommons.org/licenses/by-nc-nd/4.0/
Attribution-NonCommercial-NoDerivatives 4.0 Internacional
Teoría poliédrica en programación lineal entera
info:eu-repo/semantics/bachelorThesis