Resumen

La programacin lineal se utiliza para resolver problemas de optimizacin. As, encontrar el camino ms corto en una malla es un buen objetivo para aplicar la programacin lineal. En este trabajo se estudian rejillas bipartitas especficas, la cuadrada y la cbica centrada en el cuerpo. La primera se representa como una rejilla cuadrada diagonal que tiene puntos con pares de coordenadas pares o pares de coordenadas impares (destacando la caracterstica bipartita). Por lo tanto, una generalizacin directa de la representacin describe la rejilla cbica centrada en el cuerpo en 3D. En estas rejillas utilizamos caminos y distancias chafln; por lo tanto, los pesos de los pasos entre los vecinos ms cercanos y los pasos entre los puntos del mismo tipo ms cercanos son fijos, y dependiendo de los pesos, varios caminos podran ser el ms corto. Los vectores de los distintos vecinos forman una base si son independientes, y su nmero es igual a la dimensin del espacio estudiado. Dependiendo de la relacin de los pesos, varias bases podran dar la solucin ptima y se utilizan varios pasos en los caminos ms cortos. Este enfoque de investigacin operativa determina los caminos ptimos como soluciones factibles bsicas de un problema de programacin lineal. Se proporciona un grafo dirigido que contiene las bases factibles como nodos y arcos con condiciones sobre los pesos utilizados, de forma que el mtodo simplex pueda pasar de una base factible a otra. As, se pueden determinar las bases ptimas, que se resumen en dos teoremas. Si la solucin ptima no es entera, se aplica el corte de Gomory y la solucin ptima entera se alcanza tras una sola iteracin de Gomory. Las distancias de chafln se utilizan con frecuencia en el tratamiento y anlisis de imgenes, as como en temas relacionados con los grficos. La rejilla cbica centrada en el cuerpo, muy conocida en fsica del estado slido, ciencia de los materiales y cristalografa, tiene diversas aplicaciones en imgenes y grficos, ya que se necesitan menos muestras para representar la seal con la misma calidad que en la rejilla cbica. Adems, la malla cbica centrada en el cuerpo tiene tambin una ventaja topolgica sobre la malla cbica, a saber, que las celdas de Voronoi vecinas comparten siempre una cara completa.

• Materias:Algoritmos (Matemáticas) Algebra Ingeniería Lógica matemática Matemáticas
• Subjects:Agorithms (Math) Algebra Engineering Mathematical logic mathematics
• Palabras claves:Programación lineal; Problemas de optimización; Rejillas; Trayectorias en chaflán; Pesos; Rejilla cúbica centrada en el cuerpo
• Keywords:Linear programming; Optimization problems; Grids; Chamfer paths; Weights; Body-centered cubic grid