LP_SOLVE

Lp_solve es un programa que resuelve problemas de programación lineal entera mixta (MLP).

Fue desarrollado originalmente por Michel Berkelaar en Eindhoven University of Technology. Jeroen Dirks hizo que la transición de la versión básica 1.5 a la versión completa 2.0 fuera posible. Él contribuyó la interfaz de procedimiento, un built-in lector MPS, y muchas correcciones y mejoras en el código.

lp_solve es una biblioteca que consta de un conjunto de rutinas, llamadas API que se puede llamar desde casi cualquier lenguaje de programación para resolver problemas MILP.

Hay varias formas de pasar los datos a la biblioteca:

·         A través de la API.

·         A través de los archivos de entrada.

·         A través de un IDE.

El API es un conjunto de rutinas que se pueden llamar desde un lenguaje de programación para construir el modelo en la memoria, resolver y devolver los resultados. Hay muchas rutinas de la API para realizar muchas tareas posibles y establecer varias opciones.

A través de los archivos de entrada, soporta varios tipos de archivos de entrada. El formato común conocido como MPS es un apoyo de la mayoría de resolver, pero no es muy legible para los seres humanos.

Otro formato es el formato lp que es más legible. lp_solve tiene la capacidad única de utilizar rutinas escritas por el usuario para introducir el modelo.

A través de un IDE gracias a Henri Gourvest, ahora hay también un programa llamado IDE LPSolve; IDE que utiliza la API para proporcionar una aplicación de Windows para resolver los modelos. Con este programa usted no tiene que saber nada de la API o de lenguajes de programación. Usted sólo puede proporcionar el modelo para el programa que va a resolver  y le dará el resultado.

Como ya se dijo, lp_solve puede ser llamado desde muchos lenguajes de programación. Entre ellos se encuentran en C, C + +, Pascal, Delphi, Java, VB, C #, VB.NET, Excel.

Ofrece diferentes métodos de escala para hacer el modelo numérico más estable; tiene la  capacidad de aumentar las restricciones, hacer el modelo más pequeño y más rápido para resolver.

Tiene una rutina base para determinar un punto de partida y permite el reinicio después de hacer cambios en el modelo y continúa desde la última solución encontrada.

lp_solve es un solver  libre  de  programación que resuelve los problemas basándome  en el método simplex modificado y el método Branch-and-bound para los enteros. Además este solver contiene código fuente completo, ejemplos y manuales.

lp_solve resuelve problemas de programcion lineal, (mixto) enteros / binarios, semi-continuo y conjuntos ordenados especiales (SOS) modelos.

A través del algoritmo Branch-and-bound, se puede manejar variables de tipo entero, las variables semi-continuo  y los conjuntos ordenados especiales .

Sacado de _http://lpsolve.sourceforge.net/5.5/

LA IO EN OPERACIONES MILITARES

En esta ocasión nos correspondió consultar sobre aplicaciones de las teorías de colas en las fuerzas militares,  no ha sido fácil encontrar información sobre lo que se no ha pedido, ya que como todos sabemos hemos visto aplicaciones de teorías de colas en filas de bancos, supermercados, etc. pero nos realizamos un gran cuestionamiento y es ¿Cómo aplicaríamos los conceptos sobre teoría de colas que hemos ido adquiriendo como futuros ingenieros industriales, para solucionar los problemas presentes en las fuerzas militares?

La IO surgió durante la segunda guerra mundial aproximadamente entre los años 1939 y 1945. En este tiempo había una gran necesidad de administrar los recursos ya que había un gran conflicto entre países.

La fuerza aérea Británica formo el primer grupo que desarrollaría métodos cuantitativos para resolver estos problemas operacionales y bautizo a sus esfuerzos como investigación operacional:

Poco después las fuerzas armadas estadounidenses formaron un grupo similar, compuesto por científicos, físicos e ingenieros.

Un tema bastante polémico que ha traído consigo a lo largo del tiempo  controversia, son las guerras y todo lo que tiene que ver con los conflictos armados. A medida que los años han transcurrido los problemas que giran alrededor de un país van aumentando, ya sea en los polito, económico, social, religión, etc.

Para cada problema hay una solución de acuerdo a la gravedad e intensidad de este, asi mismo se le tiene que encontrar una gran solución. Para acabar con las guerras nacieron las fuerzas militares, ¿Qué función cumplen las fuerzas militares?

 Las Fuerzas Militares son las instituciones castrenses de tierra, mar y aire, de una República; están bajo el planeamiento y dirección estratégica del Comando General de las Fuerzas Militares de cada país, están conformadas por Ejército, Armada y Fuerza Aérea.

Toquemos el tema de las fuerzas militares de Colombia estas tienen como misión Defender la soberanía, la independencia, la integridad del territorio nacional y el orden constitucional, para proteger la vida, honra, bienes, creencias y demás derechos y libertades, asegurando el cumplimiento de los deberes sociales del Estado y de los particulares.

Las fuerzas militares de Colombia también tienen una visión y es ser una organización sólida, estructurada y altamente capacitada para conducir con eficacia operaciones conjuntas prolongadas en cualquier parte del territorio nacional, tendientes a mantener la soberanía, independencia, la vigencia de la Constitución, el ejercicio la ley, el funcionamiento de las instituciones y a garantizar la protección de la población y sus recursos así como para participar con fuerzas de otros países en operaciones combinadas de mantenimiento de la paz internacional.

A partir de  la segunda guerra mundial surge la investigación de operaciones por la necesidad de utilizar un sistema de diseño y utilización óptima de un nuevo sistema de detección y advertencia prematura denominado radiofrecuencia por parte de los militares para comunicarse con sus subalternos y superiores; poco después este avance sirvió para el análisis de todas las fases de las operaciones nocturnas, y el estudio se constituyó en un modelo de los estudios de investigación de operaciones que siguieron; el surgimiento de esta rama ha sido el desarrollo de múltiples teorías, pues esta ha sido fundamental en el desarrollo de diversos problemas organizacionales y empresariales; hoy día es utilizada por grandes compañías mediante la utilización de software, mecanismos para la planificación de producción, control de inventarios, etc.

Una de las teorías más importante que ha desarrollado la investigación de operaciones en el transcurso de los años ha sido la teoría de colas, pues esta tiene múltiples aplicaciones donde podemos resaltar las siguientes: solución de problemas referentes al congestionamiento del tránsito, el servicio de máquinas sujetas a imperfectos, la determinación del nivel de la mano de obra, la programación del tráfico aéreo, el diseño de empresas, la programación de la producción y la administración de hospitales. En este artículo trataremos la teoría de  colas y las aplicaciones de esta en el ámbito de las operaciones militares.

Por medio de la investigación de operaciones, utilizamos la teoría de colas con fin de crear modelos que permitan la organización y buen funcionamiento de las bases aéreas, con el fin de controlar el tráfico aéreo para realizar el debido control aéreo para la defensa de operaciones militares.

Entrevista al Ingeniero de ecopetrol William Bendeck

En esta ocasión tuvimos la placentera  oportunidad de entrevistar al ingeniero William Bendek, el cual es ex alumno de la Universidad Tecnológica de Bolívar, lugar donde nos estamos formando nosotros como ingenieros.

En esta entrevista nos cuenta como ha sido su trayectoria como profesional  y  como lo ha ayudado la investigación de operaciones en el desarrollo de su experiencia laboral; también nos cuenta  lo que tuvo que enfrentar al salir de la universidad y no contar con software especializado  y vivir la escasa  presencia de los computadores.

Por tanto los invitamos a que vean nuestra entrevista y se enteren como pudo sobrepasar todas estas limitaciones el ingeniero William Bendek.

GRID en Optimización

La tecnología actual, y principalmente la informática, ha contribuido de forma única a la resolución de millones de problemas en diferentes ámbitos y disciplinas, constituyendo hoy en día el motor de procesamiento y fuente de recursos absolutamente imprescindible.

Desde sus orígenes, la informática ha visto la luz de su evolución en las actividades científicas, más precisamente en sus necesidades de almacenamiento y procesamiento de datos. Y si bien en la mayoría de los casos la ciencia y otra variedad de disciplinas han visto satisfechos sus requerimientos, aún quedan desafíos abordables que esperan a ser atendidos. Un claro ejemplo es la capacidad de procesamiento requerida en ambiciosos proyectos de investigación científica, simulaciones a gran escala, toma de decisiones a partir de grandes volúmenes de información y cientos de casos imaginables que no encuentran una solución, o quizá parte de ella, en las herramientas disponibles en la tecnología actual.

Este artículo está basado en la  “computación grid” (En castellano: rejilla, tramado, entrelazado, enrejado). Varios conceptos similares coexisten acerca de qué es un grid. Uno de ellos, elaborado por el Grid Computing Information Centre, una de las asociaciones dedicada exclusivamente al desarrollo de esta tecnología, llama grid a un “tipo de sistema paralelo y distribuido que permite compartir, seleccionar y reunir recursos ‘autónomos’ geográficamente distribuidos en forma dinámica y en tiempo de ejecución, dependiendo de su disponibilidad, capacidad, desempeño, costo y calidad de servicio requerida por sus usuarios”. Según esta definición, se busca aprovechar la sinergia que surge de la cooperación entre recursos computacionales y proveerlos como servicios.

La aplicación de Grid en la que vamos a profundizar es en la optimización. Al optimizar procesos cuyo comportamiento no está determinado a priori, es necesario considerar la incertidumbre asociada a la predicción de dicho comportamiento. Esto conlleva la construcción de modelos de gran tamaño que tengan en cuenta esa incertidumbre y ofrezcan resultados que sean óptimos frente al abanico de situaciones posibles. Ejemplos de este tipo de problemas  son la planificación y operación de sistemas eléctricos, la planificación de la producción, la logística del transporte, la gestión de carteras de valores… Como consecuencia de su gran tamaño, en muchas ocasiones es necesario descomponer los problemas de optimización estocástica para poder resolverlos. Las posibilidades que ofrecen los grid para resolver estos problemas son muy importantes, las cuales son entornos de cálculo distribuido que reúnen gran cantidad de recursos de cálculo.

Los entornos grid son sistemas de cálculo distribuido formados por gran cantidad de equipos que se emplean como un gran ordenador virtual. Las características que definen un grid son:

• Está compuesto por una gran cantidad de equipos que pueden tener características muy diferentes en cuanto a prestaciones hardware y de la plataforma sobre la que se ejecutan.
• Estos equipos pueden estar dispersos geográficamente en las distintas organizaciones que participen en ese grid, lo que complica su gestión y coordinación.
• Los equipos están disponibles de forma dinámica, porque como medio de comunicación se emplea habitualmente Internet, que no fue diseñado para mantener unos requisitos de fiabilidad. Además, ni el número de equipos ni su estado de carga es conocido a priori por el usuario cuando lanza trabajos al grid.
• Es un sistema que debe ser escalable, es decir, debe estar pensado para poder crecer de tamaño con facilidad, ya que su objetivo es agrupar la mayor cantidad posible de recursos.

Por encima de los componentes físicos del grid (ordenadores, red de comunicaciones y otros recursos disponibles) se encuentra un middleware que es el software encargado de su gestión. La estructura de este software de gestión puede tener distintos grados de complejidad en función de las necesidades y dimensiones del grid en el que se ejecute, pero por lo general consta de al menos estos componentes.

ü  Un gestor que mantiene una lista de los recursos disponibles en el grid y que los asigna a las peticiones que reciba.

ü  Un componente que ejecuta los trabajos en cada uno de los equipos de cálculo.

ü  Otro componente que permite el acceso de las aplicaciones al grid, teniendo en cuenta la política de seguridad del sistema.

El método por el cual se utilizan los entornos grid para resolver problemas de optimización, consiste en la descomposición por escenarios completos, esto permite resolver el subproblema de cada escenario de forma independiente y asignar cada subproblema a un equipo diferente. En la resolución de cada subproblema se realizan dos tipos de cálculos:

•  En primer lugar, se resuelve el subproblema de cada escenario completo.
• En segundo lugar, se procede a calcular las consecuencias de las desiciones propuestas por los demás subproblemas, como si el propio subproblema fuese en esta ocasión el problema esclavo de los demás. Para esto se modifica el subproblema, eliminando los nodos comunes con nada uno de los demás escenarios, y se resuelve el problema resultante para las propuestas de los subproblemas de esos escenarios.

Con este algoritmo de solución se combinan varias resoluciones tradicionales simultáneas. El segundo punto conlleva un coste computacional adicional que no tiene sentido si este procedimiento no puede ser resuelto en paralelo. Sin embargo, por medio del cálculo paralelo se distribuye esa carga computacional y puede obtenerse mejoras en el tiempo total de ejecución, como se mostrara en el apartado de resultados. Para conseguir esta paralelización, se envía cada subproblema a un equipo, que se encarga de ejecutar las dos fases del cálculo que se han comentado para su subproblema: primero se calcula una nueva propuesta de decisiones propuestas por los demás escenarios en la iteración anterior. Este proceso iterativo continúa hasta que se alcanza una precisión suficiente en los valores de las soluciones de los subproblemas, que significa que se ha conseguido un acuerdo suficiente en los valores de las variables comunes a los diferentes escenarios.

REFERENCIAS BIBLIOGRÁFICAS

• www.icai.es/publicaciones/anales_get.php?id=1537. Optimización bajo incertidumbre. Técninas de descomposición y aplicación en Grid.