Por favor, use este identificador para citar o enlazar este ítem: https://ri-ng.uaq.mx/handle/123456789/850
Título : Politopos convexos críticos y el teorema generalizado de doignon-bell-sacarf en dimensión 2
Autor(es): Edgar Gonzalez Arreola
Palabras clave: Algoritmo
Clarkson Doignon Bell and Scarf Theorem
Clarkson¿s algorithm
K-lattice polygon
Polígono k-retícla
Teorema de Doignon Bell y Scarf
Área: INGENIERÍA Y TECNOLOGÍA
Fecha de publicación : dic-2015
Facultad: Facultad de Ingeniería
Programa académico: Maestría en Ciencias (Ingeniería Matemática)
Resumen: 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
Aparece en: Maestría en Ciencias (Ingeniería Matemática)

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
RI003957.pdf937.75 kBAdobe PDFPortada
Visualizar/Abrir


Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.