Fundamentos matematicos

Los fundamentos matemáticos de los modelos lineales discretos se encuentran en la teoría de las desigualdades lineales desarrollada en el siglo pasado. Otros conceptos que son paralelos a los de la Programación Lineal fueron formulados por von Neumann en 1928, con la aplicación del teorema del minimax a los juegos de estrategia. Como un antecedente inmediato, se encuentra el planteamiento del problema de transporte, por F. L. Hitchcock [HIT41], en 1941 en los Estados Unidos. En el contexto de la planificación óptima de la asignación de obligaciones productivas, el mismo modelo había sido estudiado y resuelto por Kantorovich en la Unión Soviética en 1939, empleando lo que puede interpretarse como variables duales. También, en un contexto concreto, Stiegler planteó el problema lineal de obtener una dieta adecuada con coste mínimo a partir de setenta y siete alimentos y considerando nueve nutrientes, reconociéndose en él la estructura de optimizar una función lineal sujeta a restricciones lineales. Pero el proyecto de formulación y ataque al problema lineal de forma general, fue propuesto por el departamento del Ejército del Aire bajo el nombre de proyecto SCOOP en 1947. El resultado inmediato fue el algoritmo de resolución simplex, debido a George B. Dantzig, y su implementación en un ordenador UNIVAC para la resolución de modelos lineales de gran tamaño.

En el resto de los años cincuenta, la Programación Lineal quedó completamente establecida, con los trabajos de Charnes [CHA52A-54]sobre la degeneración, de Lemke sobre la dualidad, de Dantzig, Orden y Wolfe sobre la forma compacta y la descomposición de grandes programas. En estos mismos años, Ford y Fulkerson, también contratados por la RAND Corporation, establecen los resultados sobre flujos en grafos y el método primal-dual para los problemas de distribución. Sin embargo, la Programación Lineal Entera no recibe atención hasta finales de esta década, en que Gomory [GOM58-60C]obtiene la expresión general para aproximar la envoltura convexa del conjunto admisible empleando sola y exclusivamente planos secantes. A pesar de las esperanzas que el procedimiento generó, sigue siendo un campo con métodos limitados e insatisfactorios, donde la enumeración parcial e inteligente de posibles soluciones es el socorrido último recurso que se hace necesario en multitud de situaciones.

En los modelos no lineales, los resultados fundamentales proceden del desarrollo del cálculo matemático en el siglo XVIII, siendo el concepto básico el del Lagrangiano. La caracterización de las condiciones necesarias de optimalidad en problemas restringidos, se generaliza a partir de los resultados de Lagrange en el conocido teorema de Kuhn-Tucker [KUH51], que recopila y estructura un conjunto de investigaciones llevadas a cabo por numerosos autores en los años cuarenta, entre los que también ha de citarse a Dantzig, y Fritz John . La Programación no Lineal progresó durante los años sesenta y setenta, pudiendo atacarse la resolución de problemas de tamaño medio con varias decenas de restricciones y algunos cientos de variables. Sin embargo, la investigación en la búsqueda de algoritmos eficientes seguía siendo muy activa, pues los existentes no eran plenamente satisfactorios.

En cuanto a la Programación Dinámica, su inicio y desarrollo básico se debe a Richard Bellman al principio de los cincuenta. La trascendencia de esta metodología no se limita a la Investigación Operativa, sino que es también de gran importancia en la Teoría del Control Óptimo, en estrecha relación con el principio del máximo de Pontryagin . En lo que aquí nos concierne, el desarrollo de la Programación Dinámica se ha visto limitado en su aplicabilidad concreta debido a la complejidad computacional que le acompaña, tanto debido a la cardinalidad del espacio de estado como al número de períodos que intervienen. En este sentido, el trabajo de Larson ha colaborado a su tratamiento, pero muchos autores aún consideran a la Programación Dinámica como un punto de vista conceptual y un bagaje teórico para el análisis de problemas; y no como un método o conjunto de ellos, implantable en algoritmos de tipo general. En esta dirección, los trabajos de Denardo, identificando la estructura de los procesos de decisiones secuenciales, suponen un avance para establecerlos.

La Teoría de Colas se inicia con el trabajo del ingeniero danés A. K. Erlang en la industria telefónica de principios de siglo. El estudio en detalle de los modelos más usuales, en que tanto la distribución de llegadas al sistema como la del tiempo de servicio son conocidas, y pertenecen a categorías bien establecidas, está completamente caracterizado. Pero los recursos técnicos de carácter matemático que se requieren para llevar a cabo estos análisis hacen que sea la simulación el método habitual de estudio cuando los procesos de colas son de cierta complejidad. Debe resaltarse la existencia de multitud de lenguajes de simulación a disposición de los usuarios de computadores de las empresas de mayor importancia en el sector.

La Teoría de Juegos se inicia con los primeros resultados de von Neumann sobre el teorema del minimax en 1926. Sobre todo a partir de la publicación de su obra básica en unión de Morgenstern, asentando la teoría de juegos matriciales. Posteriormente, y como consecuencia de las aportaciones de la Teoría del Control Óptimo, se bifurca en los Juegos Diferenciales, que ahora no nos conciernen, y en el estudio de los juegos cooperativos. Dentro de estos últimos, el desarrollo se sustenta en el estudio de la teoría del núcleo, incluyendo el concepto de valor de Shapley y los resultados de Nash. En cualquier caso, la influencia de esta teoría sobre la Organización de la Producción ha sido muy limitada. En cuanto a la Teoría de la Decisión en condiciones de incertidumbre, toda ella se basa en la estadística bayesiana y la estimación subjetiva de las probabilidades de los sucesos. La estructuración de la teoría axiomática de la utilidad es más reciente, encontrándose en fase de pleno desarrollo, como muestran las publicaciones de Schlaifer y Raiffa . En la actualidad se la considera un instrumento válido para la estructuración de la toma de decisiones con incertidumbre cuando la información no es completa. La aplicabilidad a la Organización de la Producción es reducida debido a que en ella la situación es bastante estructurada, pudiendo accederse a una satisfactoria información sobre el contexto. Si acaso, en los planteamientos estratégicos que pueden darse en la fase de diseño en que la información es menor o incluso no existe, pueden emplearse estos métodos.

Desde su origen, la Investigación Operativa se encuentra encarada con problemas para los que no existe método analítico alguno que permita obtener, con seguridad y en un tiempo conveniente, el óptimo teórico. Éste es, por ejemplo, el caso de los problemas combinatorios en que el sentido común da por imposible la enumeración. Es más que normal que el tamaño y la naturaleza de ciertos problemas combinatorios nos prohibían abordarlos por la vía del sentido común. Nuestro buen sentido, educado por la ciencia, sabe distinguir particularmente los problemas NP completos, para los cuales no existe un algoritmo que en tiempo polinomial sea capaz de encontrar la solución (Garey and Johnson ). De siempre, la investigación de operaciones ha establecido, por tales razones, métodos denominados heurísticos, incapaces de proporcionar el óptimo formal, pero susceptibles de llegar a soluciones buenas, tanto más fiables en cuanto que permiten determinar al mismo tiempo una cota (superior o inferior) del óptimo teórico con el que se comparan. Con el auge de los microordenadores, hacia principios de los ochenta, estos métodos han ido ganando terreno, puesto que se iba haciendo, cada vez más, factible y fácil intentar diferentes heurísticas y juzgar su eficacia relativa.

Es de destacar también la gran difusión que ha sufrido el «software» de optimización debido al incremento en la potencia de cálculo de los ordenadores y al abaratamiento del coste de las aplicaciones y del «hardware». Entre algunas de ellas se pueden citar nombres de aplicaciones de programación matemática (para la resolución de modelos lineales, mixtos y no lineales) como GINO, MINOS, IMSL, XA, GPSS y CPLEX. También se pueden mencionar otras aplicaciones pre y postprocesadoras de las anteriores: ANALYZE, GAMS, AMPL, etc. que permiten de una forma amigable generar los modelos y analizar sus resultados.

Durante los últimos años han aparecido una serie de métodos, denominados metaheurísticas, cuya finalidad es la de encontrar buenas soluciones a problemas de optimización (lineal o no lineal y con o sin restricciones). Entre ellos se pueden enumerar los algoritmos genéticos, el recocido simulado, la búsqueda tabú y las redes neuronales. Su aplicación a los problemas de secuenciación de todo tipo es una finalidad típica y clásica. Es más, prácticamente todos ellos están basados en intentar resolver, de la mejor forma posible, problemas típicos de Organización de la Producción. Así, los problemas típicos de secuenciación de trabajos en máquinas, de equilibrado de líneas de montaje, de asignación de rutas, de planificación de la producción, etc. han sido, son y, casi con toda seguridad, serán el banco de pruebas de las más modernas técnicas de búsqueda de soluciones a problemas en los que, de entrada, se declina la posibilidad de encontrar la solución óptima.

Los algoritmos genéticos («genetic algorithms») fueron introducidos por Holland para imitar algunos de los mecanismos que se observan en la evolución de las especies. Los mecanismos no son conocidos en profundidad pero sí algunas de sus características: la evolución ocurre en los cromosomas; un ser vivo da vida a otro mediante la decodificación de los cromosomas de sus progenitores, el cruce de los mismos, y la codificación de los nuevos cromosomas formando los descendientes; las mejores características de los progenitores se trasladan a los descendientes, mejorando progresivamente las generaciones.
Basándose en estas características, Holland creó un algoritmo que genera nuevas soluciones a partir de la unión de soluciones progenitoras utilizando operadores similares a los de la reproducción, sin necesidad de conocer el tipo de problema a resolver.

Los algoritmos de recocido simulado («simulated annealing») fueron introducidos por Cerny y Kirkpatrick et al. para la optimización de problemas combinatorios con mínimos locales. Utilizan técnicas de optimización no determinista: no buscan la mejor solución en el entorno de la solución actual sino que generan aleatoriamente una solución cercana y la aceptan como la mejor si tiene menor coste, o en caso contrario con una cierta probabilidad p; esta probabilidad de aceptación irá disminuyendo con el número de iteraciones y está relacionada con el empeoramiento del coste.

Estos algoritmos derivan de la analogía termodinámica con el proceso metalúrgico del recocido: cuando se enfría un metal fundido suficientemente despacio, tiende a solidificar en una estructura de mínima energía (equilibrio térmico); a medida que disminuye la temperatura, las moléculas tienen menos probabilidad de moverse de su nivel energético; la probabilidad de movimiento se ajusta a la función de Boltzmann.

Entre los distintos métodos y técnicas heurísticas de resolución de problemas combinatorios surge, en un intento de dotar de “inteligencia” a los algoritmos de búsqueda local, el algoritmo de búsqueda tabú («tabu search»),Glover .

La búsqueda tabú, a diferencia de otros algoritmos basados en técnicas aleatorias de búsqueda de soluciones cercanas, se caracteriza porque utiliza una estrategia basada en el uso de estructuras de memoria para escapar de los óptimos locales, en los que se puede caer al “moverse” de una solución a otra por el espacio de soluciones. Al igual que en la búsqueda local, la búsqueda tabú selecciona de modo agresivo el mejor de los movimientos posibles en cada paso. Al contrario que sucede en la búsqueda local, se permiten movimientos a soluciones del entorno aunque se produzca un empeoramiento de la función objetivo, de manera que sea posible escapar de los óptimos locales y continuar estratégicamente la búsqueda de mejores soluciones.

Las redes neuronales (<neural networks>) son modelos analógicos que tienen como objetivo reproducir en la medida de lo posible las características y la capacidad de procesamiento de información del conjunto de neuronas presentes en el cerebro de los seres vivos. Las características principales de estos modelos son su robustez, tolerancia a fallos, capacidad de adaptación y aprendizaje y la capacidad de procesar información defectuosa.

Los modelos de redes neuronales intentan conseguir unos buenos resultados basándose en una densa interconexión de unos sencillos nodos computacionales llamados neuronas. Aleksander y Morton definen una red neuronal como un “Procesador distribuido paralelo que posee una propensión natural para el almacenamiento de conocimiento experimental haciéndolo disponible para su uso. Recuerda al cerebro humano en dos aspectos: el conocimiento se adquiere mediante un proceso de aprendizaje, y la conexión interneuronal se utiliza para el almacenamiento del conocimiento.

Una ventaja importante que presentan las heurísticas frente a las técnicas que buscan soluciones exactas es que, por lo general, permiten una mayor flexibilidad para el manejo de las características del problema. No suele ser complejo utilizar algoritmos heurísticos que en lugar de funciones lineales utilicen no linealidades. Habitualmente las heurísticas proponen un conjunto de soluciones, ampliando de esta forma las posibilidades de elección del decisor, especialmente cuando existen factores no cuantificables que no han podido ser reflejados en el modelo pero deben ser tenidos en cuenta.

En resumen, podría decirse que el uso de estas técnicas supone la posibilidad de resolver, de forma práctica, problemas de gran complejidad que resultaban intratables mediante técnicas exactas.