Please use this identifier to cite or link to this item: http://ri-ng.uaq.mx/handle/123456789/850
Title: Politopos convexos críticos y el teorema generalizado de doignon-bell-sacarf en dimensión 2
metadata.dc.creator: EDGAR GONZALEZ ARREOLA
Keywords: INGENIERÍA Y TECNOLOGÍA;CIENCIAS TECNOLÓGICAS
metadata.dc.date: Dec-2015
Description: Actualmente existe una enorme cantidad de variantes del Teorema de Helly, que han aparecido en diferentes áreas de la matemática, particularmente en Programación Lineal. El Teorema de Doignon, por ejemplo, es una de estas, y una de sus aplicaciones de importancia radica en que es fundamental para el algoritmo de Clarckson, el cuál permite determinar soluciones enteras óptimas de un programa lineal de una manera más eficiente en comparación con los algoritmos que utilizan los softwares comerciales hoy en día. La eficiencia del algoritmo de Clarckson depende en particular del mejoramiento de las cotas para el Teorema de Doignon Generalizado, cotas que están ligadas directamente a la caracterización de los politopos k-retícula. En este trabajo se exponen algunos resultados originales relacionados con caracterización de los polígonos k-retícula.
Nowadays there are many versions of Helly¿s theorem, these has been used in different areas of mathematics, particularly in linear programing. The Doignon Bell y Scarf theorem is one of them. Its importance, lies in the fact that is fundamental for Clarkson¿s algorithm, since allows to determine optimal integer solutions of a linear programing problems in a more efficient way in comparison with the algorithms used in commercial software. Clackson¿s algorithm efficiency depends on the bounds¿s improvement for the for the generalize Doignon theorem, which is related with the k-lattice polytope¿s caracterization. In this Thesis some original results are given related with the characterization of k-lattice polygons.
URI: http://ri-ng.uaq.mx/handle/123456789/850
Other Identifiers: Algoritmo
Clarkson Doignon Bell and Scarf Theorem
Clarkson¿s algorithm
K-lattice polygon
Polígono k-retícla
Teorema de Doignon Bell y Scarf
Appears in Collections:Tesis

Files in This Item:
File Description SizeFormat 
RI003333.pdf937.75 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.