La programación lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de un sistema de inecuacioneslineales, optimizando la función objetivo, también lineal. Consiste en optimizar (minimizar o maximizar) una función lineal, denominada función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.
Os dejo un vídeo tutorial donde se explica la programación lineal y se avanzan las ideas básicas del método Simplex.
Existen páginas web, como PHPSimplex, donde puedes solucionar on-line problemas sencillos. También puede resolverse este tipo de problemas con las herramientas de MATLAB: Optimization Toolbox.
A continuación os dejo un vídeo donde se explica cómo resolver un problema de Programación Lineal mediante MS Excel 2007. Es importante que aprendáis a utilizar el Solver. Espero que os guste el vídeo.
¿Seríais capaces de resolver los siguientes problemas, donde el objetivo es maximizar el beneficio?:
Una empresa produce hormigón usando los ingredientes A y B. Cada kilo de ingrediente A cuesta 60 unidades monetarias y contiene 4 unidades de arena fina, 3 unidades de arena gruesa y 5 unidades de grava. Cada kilo de ingrediente B cuesta 100 unidades monetarias y contiene 3 unidades de arena fina, 6 unidades de arena gruesa y 2 unidades de grava. Cada amasada debe contener, por lo menos, 12 unidades de arena fina, 12 unidades de arena gruesa y 10 unidades de grava. Formule un modelo de programación lineal y resuélvalo gráficamente.
Una empresa especializada en la construcción de estructuras de edificios tiene patentes de tres tipos de forjados F1, F2 y F3. Los beneficios que consigue por metro cuadrado de forjado construido son 100, 90 y 120 unidades monetarias respectivamente. Por razones de almacenamiento y financiación, diariamente sólo se dispone de dos toneladas de acero, 200 m3 de hormigón y 8 m3 de madera para encofrados. Maximizar el beneficio a obtener. Las cantidades de acero, hormigón y madera que se necesitan por m2 en cada uno de los forjados son:
Si tuviésemos que hablar de la historia de la planificación y control de las obras, deberíamos referirnos a la primera de las construcciones realizadas por el hombre y perdida en el origen de nuestra especie. Construcciones como las pirámides de Egipto no pudieron construirse sin un plan previo y una compleja organización de recursos. No obstante, al emplear las técnicas de planificación actuales, podemos acortar nuestra retrospectiva a aproximadamente medio siglo atrás en Estados Unidos. Tanto en el ámbito militar como en el civil, de manera independiente, se establecieron los fundamentos de las técnicas basadas en el método del camino crítico (Critical Path Method, CPM) y en el método PERT (Program Evaluation and Review Technique). La planificación y programación de proyectos complejos, sobre todo grandes proyectos unitarios no repetitivos, comenzó a ser motivo de especial atención al final de la Segunda Guerra Mundial, donde el diagrama de barras de Henry Gantt era la única herramienta de planificación de la que se disponía, que fue un método innovador en su momento, pero muy limitado. Gannt publicó en 1916 “Work, Wages, and Profits”, un texto donde discutía estos aspectos de planificación y otros relacionados con la productividad. De todos modos, para ser más exactos, Gantt no fue el pionero en el uso de esta herramienta. Otros autores como Joseph Priestley en 1765 o William Playfair en 1786, ya había sugerido ideas precursoras, que el ingeniero Karol Adamiecki desarrolló en 1896 en lo que él llamó como “Harmonograma”. También deberíamos destacar aquí los primeros intentos desarrollados, entre 1955 y 1957, por la “Imperial Chemical Industries” y el “Central Electricity Generating Board”, en el Reino Unido, donde se desarrolló una técnica capaz de identificar la secuencia de estados más larga e irreductible para la ejecución de un trabajo, en línea con lo que después se llamaría CPM (Crítical Path Method). Estas empresas consiguieron ahorros de tiempo en torno al 40%, pero debido a que no se publicaron estas innovaciones, cayeron en la oscuridad, de la cual se despertó con los avances que se desarrollaron al otro lado del océano.
Si bien al principio PERT y CPM tenían algunas diferencias importantes, con el tiempo, ambas técnicas se han fusionado, de modo que hoy día se habla de estos procedimientos como PERT/CPM. El PERT supone que el tiempo para realizar cada una de las actividades es una variable aleatoria descrita por una distribución de probabilidad. El CPM, por otra parte, infiere que los tiempos de las actividades se conocen en forma determinística y se pueden variar cambiando el nivel de recursos utilizados. Ambos métodos aportaron los elementos necesarios para conformar el método del camino crítico actual, empleando el control de los tiempos de ejecución y los costes de operación, para ejecutar un proyecto en el menor tiempo y coste posible. PERT/CPM se basan en diagramas de redes capaces de identificar las interrelaciones entre las tareas y establecen el momento adecuado para su realización. Además, permiten preparar el calendario del proyecto y determinar los caminos críticos. El camino crítico es, en esencia, la ruta que representa el cuello de botella de un proyecto. La reducción del plazo total de ejecución será solo posible si se encuentra la forma de abreviar las actividades situadas en dicho camino, pues el tiempo necesario para ejecutar las actividades no críticas no incide en la duración total del proyecto. La principal diferencia entre PERT y CPM es la manera en que se realizan los estimados de tiempo. En artículos anteriores hemos explicado mediante sendos vídeos las mecánicas de cálculo de los diagramas de flechas y del propio PERT.
El origen del CPM se sitúa entre diciembre de 1956 y febrero de 1959. En aquellos momentos, la compañía norteamericana E.I. du Pont (DuPont) estaba buscando cómo utilizar uno de los primeros ordenadores comerciales, el “UNIVAC1”. Los gestores de DuPont se dieron cuenta de que planificar, estimar y programar parecía ser el mejor uso que la empresa podría darle a este ordenador. Este trabajo se asignó a Morgan Walker, de la Engineering Services Division de Du Pont, que junto con el matemático James E. Kelley, Jr, que trabajaba en Remington Rand, consiguieron poner a punto el método, con el objetivo de controlar el mantenimiento de los proyectos de plantas químicas de DuPont. A mediados de 1957, esta empresa estaba interesada en ampliar cerca de 300 fábricas, lo cual implicaba un gran número de actividades (por lo menos unas 30000) lo cual no se podía abordar con los diagramas de Gantt. El objetivo era controlar y optimizar los costos de operación de las actividades de un proyecto. En este método, cada una de las tareas tenía una duración exacta, conocida de antemano.
Ordenador digital UNIVAC1. https://museo.inf.upv.es/univac2/William Francis Raborn (1905-1990) Militar estadounidense.
El origen de los trabajos de la técnica PERT empezaron formalmente en enero de 1957, siendo paralelo al del CPM, pero su origen fue en el ámbito militar. Se desarrolló en la Oficina de Proyectos Especiales de la Armada de los EEUU, al reconocer el almirante William. F. Raborn que se necesitaba una planificación integrada y un sistema de control fiable para el programa de misiles balísticos Polaris. Con su apoyo se estableció un equipo de investigación para desarrollar el PERT o “Program Evaluation Research Task”. Así, la Oficina de Proyectos Especiales de la Marina de los Estados Unidos de América, en colaboración con la división de Sistemas de Misiles Lockheed (fabricantes de proyectiles balísticos) y la consultora Booz, Allen & Hamilton (ingenieros consultores), se plantean un nuevo método para solucionar el problema de planificación, programación y control del proyecto de construcción de submarinos atómicos armados con proyectiles «Polaris». Este proyecto involucra la coordinación y supervisión de 250 empresas, 9,000 subcontratistas y numerosas agencias gubernamentales a lo largo de cinco años. En julio de 1958 se publica el primer informe del programa al que denominan “Program Evaluation and Review Technique”, decidiendo su aplicación en octubre del mismo año y consiguiendo un adelanto de dos años sobre los cinco previstos. D. G. Malcolm, J. H. Roseboom, C. E. Clark y W. Fazar, todos del equipo de investigación patrocinado por la Armada, fueron los autores del primer documento publicado sobre el PERT (Malcolm et al., 1959). Este método se basa en la probabilidad de la duración de las actividades. Hoy día se sigue utilizando este método, si bien, tal y como apuntan algunos autores (ver Ahuja et al., 1995), la estimación calculada por PERT suele subestimar la duración real de los proyectos.
REFERENCIAS
AHUJA, H; DOZZI, S.P.; ABOURIZK, S.M. (1995). Project management techniques in planning and controlling construction projects. 2nd edition, Wiley, N.Y.
CLARK, C.E. (1962). The PERT model for the distribution of an activity time. Operations Research, 10(3):405-406.
MALCOLM, D.G.; ROSEBOOM, J.H.; CLARK, C.E.; FAZAR, W. (1959). Application of a technique for research and development program evaluation. Operations Research, 11(5):646-669.
YEPES, V.; PELLICER, E. (2008). Resources Management, in Pellicer, E. et al.: Construction Management. Construction Managers’ Library Leonardo da Vinci: PL/06/B/F/PP/174014. Ed. Warsaw University of Technology, pp. 165-188. ISBN: 83-89780-48-8.
PELLICER, E.; YEPES, V.; TEIXEIRA, J.C.; MOURA, H.P.; CATALÁ, J. (2014). Construction Management. Wiley Blackwell, 316 pp. ISBN: 978-1-118-53957-6.
Los problemas de optimización en los que las variables de decisión son enteras, es decir, donde el espacio de soluciones está formado por ordenaciones o subconjuntos de números naturales, reciben el nombre de problemas de optimización combinatoria. En este caso, se trata de hallar el mejor valor de entre un número finito o numerable de soluciones viables. Sin embargo la enumeración de este conjunto resulta prácticamente imposible, aún para problemas de tamaño moderado.
Las raíces históricas de la optimización combinatoria subyacen en ciertos problemas económicos: la planificación y gestión de operaciones y el uso eficiente de los recursos. Pronto comenzaron a modelizarse de esta manera aplicaciones más técnicas, y hoy vemos problemas de optimización discreta en diversas áreas: informática, gestión logística (rutas, almacenaje), telecomunicaciones, ingeniería, etc., así como para tareas variadas como el diseño de campañas de marketing, la planificación de inversiones, la división de áreas en distritos políticos, la secuenciación de genes, la clasificación de plantas y animales, el diseño de nuevas moléculas, el trazado de redes de comunicaciones, el posicionamiento de satélites, la determinación del tamaño de vehículos y las rutas de medios de transporte, la asignación de trabajadores a tareas, la construcción de códigos seguros, el diseño de circuitos electrónicos, etc. (Yepes, 2002). La trascendencia de estos modelos, además del elevado número de aplicaciones, estriba en el hecho de que “contiene los dos elementos que hacen atractivo un problema a los matemáticos: planteamiento sencillo y dificultad de resolución” (Garfinkel, 1985). En Grötschel y Lobas (1993) se enumeran otros campos en los cuales pueden utilizarse las técnicas de optimización combinatoria.
REFERENCIAS
GARFINKEL, R.S. (1985). Motivation and Modeling, in LAWLER, E.L.; LENSTRA, J.K.; RINNOOY KAN, A.H.G.; SHMOYS, D.B. (eds.) The Traveling Salesman Problem: A Guide Tour of Combinatorial Optimization. Wiley. Chichester.
GRÖTSCHEL, M.; LÓVASZ, L. (1993). Combinatorial Optimization: A Survey. Technical Report 93-29. DIMACS, May.
YEPES, V. (2002). Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW. Tesis Doctoral. Escuela Técnica Superior de Ingenieros de Caminos, Canales y Puertos. Universitat Politècnica de València. 352 pp. ISBN: 0-493-91360-2. (pdf)
La planificación y gestión de redes de distribución de baja demanda exige disponer de técnicas eficientes de optimización de rutas. El sistema de optimización de rutas disponible, no sólo afecta el desarrollo de operaciones sino, también las decisiones tácticas y estratégicas como el tamaño óptimo de flota, estimación de costes, políticas de publicidad y rotura de servicio, etc. Por ejemplo, es habitual la venta de paquetes turísticos que incluyen el transporte; los precios se fijan mucho antes de que la demanda de transporte sea conocida, siendo frecuentes las cancelaciones de última hora y la llegada de nuevos clientes. Si el número de pasajeros que debe ser transportado es pequeño, en comparación con la máxima capacidad de carga del vehículo óptimo a la distancia correspondiente, los beneficios o pérdidas generadas por el transporte dependen críticamente de la eficiencia del sistema de optimización de rutas. La Figura describe la influencia de la optimización de operaciones en la planificación y gestión de redes de distribución de baja demanda.
Planificación y Gestión de Redes de Distribución de Baja Demanda
George Bernard Dantzig (1914-2005), “padre de la programación lineal”
Optimizar significa buscar la mejor manera de realizar una actividad, y en términos matemáticos, hallar el máximo o mínimo de una cierta función, definida en algún dominio. La optimización constituye un proceso para encontrar la mejor solución de un problema donde “lo mejor” se concilia con criterios establecidos previamente.
La programación matemática constituye un campo amplio de estudio que se ocupa de la teoría, aplicaciones y métodos computacionales para resolver los problemas de optimización condicionada. En estos modelos se busca el extremo de una función objetivo sometida a un conjunto de restricciones que deben cumplirse necesariamente. Las situaciones que pueden afrontarse con la programación matemática se suelen presentar en ingeniería, empresas comerciales y en ciencias sociales y físicas.
Con carácter general, un programa matemático (ver Minoux, 1986) consiste en un problema de optimización sujeto a restricciones en de la forma:
Me ha parecido interesante rescatar una pequeña publicación, que ya tiene 10 años, donde se aplicaba un algoritmo de optimización heurística curioso: Old Bachelor Acceptance, o “algoritmo del solterón“. En este caso, aplicado a la optimización de redes de transporte con flotas heterogéneas. Resulta curioso ver cómo determinados comportamientos sociales (colonias de hormigas), principios naturales (teoría de la evolución) o recreaciones de nuestro cerebro (redes neuronales) son capaces de resolver problemas complejos de optimización.
Espero que os sea de interés.
GDE Error: Error al recuperar el fichero. Si es necesario, desactiva la comprobación de errores (404:Not Found)
Los problemas de decisión están presentes en todos los ámbitos del ser humano: finanzas, empresa, ingeniería, salud, etc. Una de las grandes dificultades al tomar una decisión ocurre cuando queremos conseguir varios objetivos distintos, muchos de ellos incompatibles o contradictorios. Por ejemplo, si queremos un vehículo que sea muy veloz, debería tener un perfil aerodinámico que a veces es incompatible con la comodidad de los usuarios; si queremos hacer un negocio con grandes beneficios, a veces tenemos que asumir ciertos riesgos, etc. Una herramienta que permite afrontar este tipo de problemas de decisión es el denominado “óptimo de Pareto“. A continuación os paso un vídeo explicativo de este tema. Espero que os guste.
Aspecto de diversas soluciones al problema de rutas
Los problemas de distribución física consisten básicamente en asignar una ruta a cada vehículo de una flota para repartir o recoger mercancías. Los clientes se localizan en puntos o arcos y a su vez pueden presentar horarios de servicio determinados; el problema consiste en establecer secuencias de clientes y programar los horarios de los vehículos de manera óptima. Los problemas reales de transporte son extraordinariamente variados. Yepes (2002) propone una clasificación que contiene un mínimo de 8,8·109 combinaciones posibles de modelos de distribución. Si alguien fuese capaz de describir en un segundo cada uno de ellos, tardaría cerca de 280 años en enunciarlos todos. La investigación científica se ha centrado, por tanto, en un grupo muy reducido de modelos teóricos que además tienden a simplificar excesivamente los problemas reales. Son típicos problemas de optimización matemática combinatoria. Continue reading “¿Por qué son tan complicados los problemas de distribución física?”→
La trascendencia económica del sector del transporte genera costos sociales y medioambientales de gran envergadura. Esta actividad supone aproximadamente un sexto del Producto Interno Bruto (PIB) de los países industrializados (ver Yepes, 2002). Un estudio del National Council of Physical Distribution (ver Ballou, 1991) estima que el transporte sumó un 15% del PIB de Estados Unidos en 1978, constituyendo más del 45% de todos los costos logísticos de las organizaciones. En España, según datos del Ministerio de Fomento (ver CTCICCP, 2001), la participación del sector en el valor añadido bruto del año 1997 se situó en un 4.6%. En cuanto al empleo, 613,400 personas se encontraban ocupadas en el año 1999 en el sector de transportes en España, lo cual representa el 3.69% de la población activa. La distribución física representa para las empresas entre la sexta y la cuarta parte de las ventas y entre uno y dos tercios del total de los costos logísticos (Ballou, 1991). Continue reading “Optimización económica de redes de transporte”→
¿Cómo se podrían optimizar en tiempos de cálculo razonable problemas complejos de redes de transporte, estructuras de hormigón (puentes, pórticos de edificación, túneles, etc.) y otro tipo de problemas de decisión empresarial cuando la dimensión del problema es de tal calibre que es imposible hacerlo con métodos matemáticos exactos? La respuesta son los métodos aproximados, también denominados heurísticas. Este artículo divulgativo trata de ampliar otros anteriores donde ya hablamos de los algoritmos, de la optimización combinatoria, de los modelos matemáticos y otros temas similares. Para más adelante explicaremos otros temas relacionados específicamente con aplicaciones a problemas reales. Aunque para los más curiosos, os paso en abierto, una publicación donde se han optimizado con éxito algunas estructuras de hormigón como muros, pórticos o marcos de carretera: (González et al, 2008).
Desde los primeros años de la década de los 80, la investigación de los problemas de optimización combinatoria se centra en el diseño de estrategias generales que sirvan para guiar a las heurísticas. Se les ha llamado metaheurísticas. Se trata de combinar inteligentemente diversas técnicas para explorar el espacio de soluciones. Osman y Kelly (1996) nos aportan la siguiente definición: “Los procedimientos metaheurísticos son una clase de métodos aproximados que están diseñados para resolver problemas difíciles de optimización combinatoria, en los que los heurísticos clásicos no son ni efectivos ni eficientes. Los metaheurísticos proporcionan un marco general para crear nuevos algoritmos híbridos combinando diferentes conceptos derivados de la inteligencia artificial, la evolución biológica y la mecánica estadística”.
Aunque existen diferencias apreciables entre los distintos métodos desarrollados hasta el momento, todos ellos tratan de conjugar en mayor o menor medida la intensificación en la búsqueda –seleccionando movimientos que mejoren la valoración de la función objetivo-, y la diversificación –aceptando aquellas otras soluciones que, aun siendo peores, permiten la evasión de los óptimos locales-.
Las metaheurísticas son susceptibles de agruparse de varias formas. Algunas clasificaciones recurren a cambios sucesivos de una solución a otra en la búsqueda del óptimo, mientras otras se sirven de los movimientos aplicados a toda una población de soluciones. El empleo, en su caso, de memoria que guíe de la exploración del espacio de elecciones posibles permite otro tipo de agrupamiento. En otras circunstancias se emplean perturbaciones de las opciones, de la topología del espacio de soluciones, o de la función objetivo. En la Figura se recoge una propuesta de clasificación de las heurísticas y metaheurísticas empleadas en la optimización combinatoria (Yepes, 2002), teniendo en común todas ellas la necesidad de contar con soluciones iniciales que permitan cambios para alcanzar otras mejores. Es evidente que existen en este momento muchas más técnicas de optimización, pero puede ser dicha clasificación un punto de partida para una mejor taxonomía de las mismas.
Figura. Taxonomía de estrategias empleadas en la resolución aproximada de problemas de optimización combinatoria sobre la base de soluciones iniciales (Yepes, 2002)
Las metaheurísticas empleadas en la optimización combinatoria en podrían clasificarse en tres grandes conjuntos. Las primeras generalizan la búsqueda secuencial por entornos de modo que, una vez se ha emprendido el proceso, se recorre una trayectoria de una solución a otra vecina hasta que éste concluye. En el segundo grupo se incluyen los procedimientos que actúan sobre poblaciones de soluciones, evolucionando hacia generaciones de mayor calidad. El tercero lo constituyen las redes neuronales artificiales. Esta clasificación sería insuficiente para aquellas metaheurísticas híbridas que emplean, en mayor o menor medida, estrategias de unos grupos y otros. Esta eventualidad genera un enriquecimiento deseable de posibilidades adaptables, en su caso, a los diferentes problemas de optimización combinatoria.
Referencias
GONZÁLEZ-VIDOSA-VIDOSA, F.; YEPES, V.; ALCALÁ, J.; CARRERA, M.; PEREA, C.; PAYÁ-ZAFORTEZA, I. (2008) Optimization of Reinforced Concrete Structures by Simulated Annealing. TAN, C.M. (ed): Simulated Annealing. I-Tech Education and Publishing, Vienna, pp. 307-320. (link)
YEPES, V. (2002). Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW. Tesis Doctoral. Escuela Técnica Superior de Ingenieros de Caminos, Canales y Puertos. Universitat Politècnica de València. 352 pp. ISBN: 0-493-91360-2. (pdf)
La programación lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de un sistema de inecuaciones lineales, optimizando la función objetivo, también lineal. Consiste en optimizar (minimizar o maximizar) una función lineal, denominada función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.
