Optimización. Programación lineal y aplicaciones

Optimización es, según el Diccionario de la Real Academia de la Lengua Española, ?acción y efecto de optimizar?; es decir ?acción y efecto de buscar la mejor manera de realizar una actividad?. En contextos científicos se impone la necesidad de optimizar. De ahí que la Investigación Operativa, cuyo objetivo fundamental es el de ?ayudar a decidir científicamente?, cuente con la Optimización como una de sus partes fundamentales. En una relación amplia de campos de trabajo, las soluciones a los problemas, modelizados matemáticamente, deben tener atributos de optimalidad. Y la garantía de dichos atributos será la consecuencia de utilizar las adecuadas herramientas matemáticas y computacionales. De lo anterior se deduce que la Optimización o, lo que es lo mismo, la Programación Matemática, es materia de interés en ciencias, ingenierías, economía, gestión y organización?, donde son habituales problemas que deben ser resueltos óptimamente. El caso lineal presenta las características de gran relevancia práctica y de disposición de propiedades matemáticas y herramientas computacionales que posibilitan su resolución eficiente. Este trabajo pretende ser un estudio de los problemas de Programación Lineal, haciendo énfasis en los fundamentos matemáticos que soportan el desarrollo del Método Simplex y sus variantes. El esfuerzo realizado se proyecta a determinadas aplicaciones. En el Tema 0 se hace una introducción los aspectos históricos y metodológicos de la Optimización como parte fundamental de la Investigación Operativa. En el Tema 1 se estudian distintos problemas de Programación Matemática. Se formula el problema general de Programación Lineal, identificando los distintos elementos que lo componen. Se introduce la forma estándar de dicho problema y se establecen las pautas para convertir cualquier caso al correspondiente estándar. Se finaliza con la resolución gráfica en el caso bidimensional. En el Tema 2 se hace un recorrido por los conceptos y propiedades matemáticas que sirven de fundamentos para el estudio y la resolución de problemas de Programación Lineal. Se estudian las propiedades básicas de los conjuntos afines prestando especial atención a los hiperplanos. Entre los conjuntos convexos interesan los poliedros y su caracterización en términos de puntos extremos y direcciones extremas. Este estudio es clave para el desarrollo posterior del Método Simplex. En el Tema 3 se desarrolla el Método Simplex, un algoritmo que resuelve cualquier problema de Programación Lineal. Se exponen y justifican las operaciones que realiza este procedimiento, atendiendo a los detalles que hacen posible su aplicación global. En el Tema 4, se presenta el Método Simplex Revisado, es decir, la versión matricial adaptada al manejo computacional del método que sólo usa los elementos imprescindibles para su implementación eficiente. Como herramienta de apoyo docente, se introducen unas nuevas tablas, denominadas tablas inversas, que hacen posible la generación de la información correspondiente a cada iteración a partir de los datos iniciales del problema. En el Tema 5 se introduce el importante concepto de dualidad en Programación Lineal. Como consecuencia, aparece el problema dual asociado a cualquier problema de Programación Lineal (ahora, problema primal) y se establecen los resultados fundamentales que relacionan ambos problemas. Usando convenientemente las nuevas ideas, se desarrolla el Método Simplex Dual y otros importantes como el Método Primal- Dual y el Método Autodual Paramétrico. Los problemas de Programación Lineal en los que costos o recursos dependen linealmente de un parámetro se estudian en el Tema 6. Este estudio, realizado en principio de forma separada, puede hacerse simultáneamente y extenderse a los coeficientes tecnológicos. Las herramientas necesarias para llevarlo a cabo se concretan en el uso del Método Simplex Primal y del Método Simplex Dual. En el Tema 7 se analiza la influencia que pueden tener, en la optimalidad previamente detectada, algunos cambios en los elementos definidores del problema. Concretamente, nos referimos a la adición de restricciones o de variables, cambios en los costos, en los recursos o en los coeficientes tecnológicos. En todos los casos, la resolución del problema modificado se realiza a partir de la situación de optimalidad de partida. En el Tema 8 se contempla la ?novedad? de que, en la práctica, los niveles de las actividades tienen cotas inferiores y superiores. Esto supone algunas modificaciones del Método Simplex que, sustancialmente, se reducen a un manejo conveniente de las restricciones de cotas; implícito, como sucedió en el desarrollo previo con las restricciones de no negatividad. En este tema también se presenta un estudio adaptado de la dualidad y la versión correspondiente del Método Simplex Dual. En muchos problemas de Optimización es necesario que los niveles de las distintas actividades tengan valores enteros. En el Tema 9 se formalizan distintos modelos de Programación Lineal Entera. Se hace énfasis en la ingente cantidad de casos en los que se pueden utilizar modelos de este tipo. En el Tema 10 se estudian métodos generales de resolución de problemas de Programación Entera aplicando la Programación Lineal. Dentro del grupo de Métodos Enumerativos, estudiaremos un esquema general de los Métodos de Ramificación y Acotación (Branch and Bound). Como exponente de los Métodos No Enumerativos, veremos casos de Métodos de Hiperplanos de Corte (Cutting Planes). Todos los temas contienen ejemplos que ilustran los casos descritos o soportan aplicaciones de propiedades o procedimientos introducidos previamente. También, al final de cada tema, aparecen ejercicios propuestos (de dificultad similar a los ejemplos resueltos) para que el lector pueda aplicar los conocimientos adquiridos. El trabajo se completa con una breve relación de referencias bibliográficas