La Programación Lineal
A menudo los problemas de optimización de recursos pueden plantearse como la maximización de una función lineal sujeta a restricciones lineales.
Max Z = ∑i Xi
Xi ≥ 0
Para todo j, ∑j AijXi ≤Bj
La Programación Lineal es un procedimiento hoy muy conocido para resolver problemas de optimización lineal de gran tamaño (con centenares de miles o millones de variables y restricciones). Su origen se remonta a los trabajos del matemático Fourier y culmina con George Dantzig y su desarrollo del método Simplex en los años 40.
Desde entonces, favorecido por la llegada de plataformas de cálculo cada vez más potentes, este procedimiento ha sido objeto de numerosas investigaciones y sus resultados pueden verse hoy en los solver comerciales reconocidos a nivel mundial (ILOG-CPLEX, FICO-XPRESS-MP, GUROBI), así como, y cada vez más, en los software libres tales como COIN, GLPK o LP-Solve.
La Programación Lineal tiene numerosas aplicaciones en los sectores industriales como en el petrolero, el agroalimentario, en la industria pesada y manufacturera, o en los sectores de servicios, transporte y en el mundo de las finanzas y de los seguros.
Para resolver los problemas de optimización de recursos que requieren utilizar valores enteros para las variables (variables que representan opciones o números enteros), se ha creado un procedimiento que combina el Simplex junto con un método de investigación con estructura de árbol llamado Ramificación y Poda (Branch and Bound). Normalmente este método viene acompañado de funciones de reducción del espacio de soluciones basadas en las técnicas de Programación por Restricciones o de generación automática de cortes (cutting plane). El objetivo consiste en reducir el dominio de investigación de tal forma que la solución lineal coincida con la solución entera. Los productos líderes del mercado de solver lineales incluyen hoy todos estos desarrollos.
Para garantizar la estabilidad y la eficiencia de los algoritmos hoy disponibles, los equipos de trabajo encargados del diseño de software basados en la Programación Lineal deben resolver los problemas complejos implementando técnicas de descomposición, con el fin de que su resolución sea compatible con la memoria disponible de los ordenadores y que los tiempos de computación sean aceptables para los usuarios. Por ejemplo la Generación de Columnas (Column Generation) que, al no tratar todas las variables de un problema lineal de forma explícita, permite abordar problemas cuyo tamaño podría ser potencialmente casi indeterminado.
EURODECISION utiliza la tecnología de la Programación Lineal y sus desarrollos desde sus inicios, lo que le convierte hoy en un centro de referencia en este ámbito. Con esta base hemos desarrollado numerosos proyectos para nuestros clientes, y su papel es clave en el diseño de nuestra plataforma de desarrollo, así como en la mayoría de nuestros componentes. Nuestra plataforma de desarrollo LP-Toolkit/LP-Colgen permite generar de forma rápida nuestras soluciones basadas en la Programación Matemática y realizar interfaces con cualquiera de los solver existentes, como por ejemplo:
- CPLEX (ILOG/IBM)
- XPRESS-MP (FICO)
- GUROBI
- COIN
- GLPK
- LP-SOLVE
Nuestros equipos de trabajo mantienen en todo momento una vigilia tecnológica de los diferentes solver del mercado y así conocen en detalle su eficacia relativa.