Algoritmo De Ubicacion

Algoritmos de ubicación optima

Ing. Bladimir

Asignatura: Estructura de datos y algoritmos

Azarel O. Mejía 31241191

Para minimizar sus costos, una empresa que cuenta con una red de distribución debe asegurar que sus centros de distribución se ubiquen eficientemente.

Un programa computacional bien diseñado, junto con la información geográfica correcta, puede lograr este objetivo de una manera que requiera poco esfuerzo humano.

El problema planteado consiste en tener un número determinado de centros o puntos que demandan la entrega de un bien o su recolección. En base a la ubicación de todos estos centros se requiere encontrar la mejor localización de una planta industrial que sea capaz de satisfacer los requisitos de todos los otros centros. Este tipo de problema se denomina problema de localización óptima. Para resolver el problema planteado, en primer lugar, se presenta un estudio sobre algunos tipos de problemas de localización óptima y sus correspondientes algoritmos de solución.

Posteriormente, se realiza el diseño e implementación del prototipo en la herramienta para Sistemas de Información Geográfica (SIG) y en el lenguaje de programación elegidos, aplicando los algoritmos de solución a problemas de localización óptima estudiados, para finalmente realizar pruebas al prototipo evaluando su comportamiento en la ejecución. El análisis, diseño e implementación, fue aplicado a un problema de localización de canchas de acopio de madera, en parte de la superficie de plantaciones de una empresa forestal.

El algoritmo que se muestra a continuación nos da una idea del funcionamiento de un algoritmo voraz usado para ayudar a las empresas o multinacionales a ubicar óptimamente sus almacenes principales dependiendo de la ubicación de las ciudades destino y la cantidad de viajes que se deben hacer a cada una de esas ciudades.

Algoritmo voraz: (también conocido como ávido, devorador o goloso) es aquel que, para resolver un determinado problema, sigue una heurística consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución general óptima. Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento. Normalmente se aplica a los problemas de optimización.

Dado un conjunto finito de entradas , un algoritmo voraz devuelve un conjunto (seleccionados) tal que y que además cumple con las restricciones del problema inicial. A cada conjunto que satisfaga las restricciones se le suele denominar prometedor, y si este además logra que la función objetivo se minimice o maximice (según corresponda) diremos que es una solución óptima.

• El conjunto de candidatos, entradas del problema.

• Función solución. Comprueba, en cada paso, si el subconjunto actual de candidatos elegidos forma una solución (no importa si es óptima o no lo es).

• Función de selección. Informa de cuál es el elemento más prometedor para completar la solución. Éste no puede haber sido escogido con anterioridad. Cada elemento es considerado una sola vez. Luego, puede ser rechazado o aceptado y pertenecerá a .

• Función de factibilidad. Informa si a partir de un conjunto se puede llegar a una solución. Lo aplicaremos al conjunto de seleccionados unido con el elemento más prometedor.

• Función objetivo. Es aquella que queremos maximizar o minimizar, el núcleo del problema.

El algoritmo escoge en cada paso al mejor elemento posible, conocido como el elemento más prometedor. Se elimina ese elemento del conjunto de candidatos ( ) y, acto seguido, comprueba si la inclusión de este elemento en el conjunto de elementos seleccionados

...