Introducción
El inicio formal de la Investigación Operativa tuvo lugar en
Inglaterra a
finales de 1939, cuando la estación de investigación de Bawdsey, bajo la dirección de A. Rowe, fue encargada del
desarrollo de
políticas óptimas para el nuevo
sistema de
detección militar llamado radar. Poco después, se
presentó un estudio de las fases de las operaciones
nocturnas en lo que sería un modelo para
los estudios posteriores del mismo tipo.
Poco después, debido a las extremas necesidades
de personal que se
plantearon durante la guerra y a la
complejidad de los nuevos sistemas de
defensa y ataque que se introdujeron, pareció indicado el
empleo de
científicos en el estudio global de los problemas
planteados. La finalidad era conseguir la máxima eficiencia
posible. Así, en Agosto de 1940, el físico P.M.S.
Blackett de la Universidad de
Manchester fue responsabilizado de formar un grupo de
trabajo para estudiar el sistema de
defensa antiaérea gobernado por radar. Este grupo, estaba
constituido por tres psicólogos, dos físicos
matemáticos, un astrofísico, un oficial del
ejército, un topógrafo, un físico y dos
matemáticos. Fue jocosamente denominado el «circo de
Blackett», siendo generalmente admitido que en él se
daban todas las características de los grupos que
trabajan en Investigación Operativa:
Grupo de trabajo interdisciplinar
Empleo de
modelos
matemáticos
Punto de vista de análisis de sistemas
Uno de los primeros esfuerzos de este grupo fue dirigido
al estudio del ataque aéreo a los submarinos. Las bombas estaban
programadas para estallar a una profundidad de unos treinta
metros, pues se argumentaba que al divisar el submarino al
bombardero se sumergiría; y dado que desde el instante en
que fuera localizado el bombardero hasta el del lanzamiento de la
bomba, transcurrirían aproximadamente dos minutos, unos
treinta metros era, aproximadamente, la profundidad alcanzada por
el submarino en su precipitada inmersión. Pero aunque el
razonamiento era válido, los resultados obtenidos con esta
política
eran muy limitados. Cuando el grupo de Blackett fue encargado del
estudio, su primera decisión consistió en la
observación directa de la situación,
encaramándose en los bombarderos en sus misiones de ataque
a submarinos. Tras un elevado número de observaciones
llegaron a la conclusión, con el análisis de los datos de los
ataques, de que se producían las siguientes
circunstancias:
a) Debido a la falta de precisión del bombardeo,
muy pocas de las bombas explotaban
cerca de su objetivo, a
treinta metros de profundidad.
b) La precisión aumentaba cuando el submarino no
había tenido tiempo de
sumergirse, pero en ese caso las bombas estallaban a demasiada
profundidad y no producían grandes
daños.
En definitiva, la profundidad de treinta metros era
adecuada cuando el submarino divisaba con antelación al
bombardero, pero la falta de precisión impedía
obtener resultados. Y cuando la precisión era buena, la
profundidad a que estaba programada la explosión era
inadecuada, pues esto sólo ocurría cuando el
submarino se mantenía cercano a la superficie.
A la vista de los datos
estadísticos sobre la precisión del bombardeo y la
inmersión de los submarinos, se llegó a la
conclusión de que la alternativa más adecuada era
optar por causar daños cuando el submarino estuviera en la
superficie. Así se hizo y los resultados mejoraron
espectacularmente. En este trabajo ya estaban incluidos los
aspectos que caracterizan a los estudios de Investigación
Operativa:
1. Toma directa de datos.
2. Empleo de modelos
matemáticos para el análisis de la
situación, que en este caso era simplemente
estadístico.
3. Obtención de las políticas
óptimas que corresponden al modelo.
4. Modificación de dichas políticas de acuerdo con
factores reales no considerados en el modelo: en este caso se
emplearon espoletas que explotaban a diez metros de profundidad,
pues no se disponía de otras que lo hiciesen más
cerca de la superficie. Un resultado del estudio fue iniciar su
fabricación.
Como consecuencia de los resultados obtenidos, por
éste y otros estudios sobre problemas de
índole militar, el Almirantazgo Británico
creó el grupo funcional «Naval Operational
Research». El punto de vista empleado para el
análisis de los problemas por este grupo, y los que
inmediatamente le siguieron, fue denominado Operational Research.
Dicha acepción fue modificada en Estados Unidos
por Operations Research. Según narran autores ingleses,
como Sir Robert Watson-Watt, fue a sugerencia suya el que los
norteamericanos introdujeran también grupos de
científicos para el estudio de operaciones
militares tras el inicio de su participación en la
guerra. Para
el mes de abril de 1942, las Fuerzas Aéreas, el
Ejército y la Marina poseían grupos funcionales
conocidos como Operations Analysis, Operations Research y
Operations Evaluations, respectivamente. El último de
estos grupos era dirigido por Philp M. Morse [MOS55],
del Massachusetts Institute of Technology, que años
más tarde sería el primer presidente de la sociedad
norteamericana de Investigación Operativa (O.R.S.A.) y uno
de sus principales difusores.
Durante la guerra, otros países aliados como
Canadá y Francia,
también introdujeron grupos de Investigación
Operativa en sus respectivos ejércitos. Al finalizar la
guerra, las circunstancias en Gran Bretaña y Estados Unidos
fueron distintas para estos grupos. En Estados Unidos, los fondos
para la investigación en el campo militar se
incrementaron, por lo que la mayoría de los grupos se
consolidaron, aumentando su número y tamaño. Debido
a ello, la industria y la
administración norteamericanas
permanecieron indiferentes a la Investigación Operativa
durante el resto de la década. Uno de los primeros
establecimientos de investigación, dependiente del
ejército del aire y que tuvo
gran influencia en el posterior desarrollo de
esta disciplina,
fue la RAND Corporation fundada por Donald Douglas en 1946. En la
primera conferencia sobre
la Investigación Operativa en la Industria, que
tuvo lugar en el Case Institute of Technology de Cleveland en
1951, fue casi imposible encontrar aplicaciones industriales de
carácter no militar. Quizás las
causas de este lento desarrollo en Estados Unidos, sea necesario
buscarlas en la situación de la
Organización Industrial tradicional, que estaba
plenamente establecida, difundida y reputada. La
Investigación Operativa se percibía como un dudoso
competidor de aquélla, a lo que hay que añadir el
celoso secreto con el que se mantenían las limitadas
experiencias que se llevaban a cabo.
En cambio, en
Gran Bretaña, los componentes de los grupos que se
habían desarrollado en el medio militar pasaron a la
sociedad
civil. Los nuevos problemas que se le plantearon a la nueva
administración laborista inglesa, con la
nacionalización de importantes sectores de su economía y la
reconstrucción de gran parte de sus instalaciones
industriales, estimularon la implantación de la
Investigación Operativa. Sir Charles Ellis, responsable
durante la guerra del grupo de Investigación Operativa del
Ejército, fue nombrado asesor científico en el
Comité del Carbón, creando un grupo de
Investigación Operativa. Análogas circunstancias se
dieron en los sectores nacionalizados de la electricidad y el
transporte. En
el sector privado, la industria inglesa mantiene instituciones
cooperativas
de investigación, por lo que la difusión de nuevos
métodos
está menos mediatizada por el secreto industrial.
Quizás debido a ello, casi inmediatamente la industria del
acero y la textil
introdujeron grupos de Investigación Operativa. Otro
aspecto importante en este contexto es que el desarrollo de la
Organización Industrial tradicional en Gran
Bretaña había sido más limitado, y con la
excepción del Estudio del Trabajo, era todavía una
novedad en los círculos industriales. Por ello,
todavía ciertos campos como la gestión
de inventarios se
identifican con la
Organización de la Producción en Estados Unidos y con la
Investigación Operativa en Inglaterra.
Así, toda una serie de metodologías de
carácter cuantitativo se difundieron en la industria de
este último país bajo la denominación y con
el prestigio de la Investigación Operativa.
Simultáneamente, el desarrollo de los ordenadores
y su implantación en la industria, posibilitaron el
tratamiento y estudio de problemas de gran complejidad, por lo
cual a mediados de la década de los cincuenta, la
Investigación Operativa se encontraba ya afianzada en el
mundo industrial. Los primeros cursos sobre
Investigación Operativa se impartieron en el M.I.T. de
Boston en 1948, y un año después hubo un ciclo de
conferencias en el University College de Londres. Poco
después, ofrecían programas
específicos completos las Universidades Case Western
Reserve, Johns Hopkins y North-Werstern en U.S.A.; y en el
Imperial College y la London School of Economics en
Inglaterra.
El grupo de científicos ingleses que
procedían de los establecimientos militares formaron en
1948 el Operational Research Club, que daría lugar, en
1954, a la Operational Research Society. Unos años antes,
en 1950, se había fundado la Operations Research Society
of America. Ambas iniciaron inmediatamente la publicación
de revistas científicas monográficas para la
presentación pública de los resultados de las
investigaciones en curso y la difusión de
la disciplina.
Los primeros alumnos del programa de
graduados que obtuvieron el título de Doctores en
Investigación Operativa se graduaron en el Case Institute
of Technology en 1957, siendo responsables del programa los
profesores Russell Ackoff y West Churchman.
Con la Investigación Operativa ya firmemente
establecida, su rápida evolución arrastró consigo la de la
Organización de la Producción, de forma tal que existe una
correlación profunda y completa entre ambas materias. Para
destacar el solape se introduce ahora la reciente evolución de los Métodos
Cuantitativos hasta la situación en que se encuentran en
la actualidad.
Toda disciplina científica emerge de la
convergencia de un creciente interés en
alguna clase de problemas y del desarrollo de métodos,
técnicas e instrumentos científicos
adecuados para resolver esos problemas. La I.O. utiliza
resultados de muchas áreas científicas, aunque su
base fundamental se encuentra en la matemática, la economía y el
cálculo
de probabilidades y estadística. Desde un punto de vista
matemático se podrían establecer los
orígenes en diferentes trabajos sobre modelos lineales
debidos a Jordan, Minkowsky y Farkas a finales del siglo XIX. En
relación con la estadística, sus orígenes se
encuentran en los trabajos de Erlang sobre fenómenos de
espera en los años veinte del presente siglo. En
economía se deben a Quesnay (XVIII) y Walras (XIX), que
plantearon los primeros modelos de programación matemática, que fueron posteriormente
perfeccionados por autores como Von Neumann , Kantorovich y
Dantzig
Como puede observarse en los primeros estudios que se
etiquetaron como de Investigación Operativa, el aspecto
técnico más característico consistió en la
estructuración estadística de los datos y en el
empleo de modelos descriptivos de tipo probabilístico. Sin
embargo, el prestigio y difusión de la
Investigación Operativa está cimentado en la
Programación Lineal, aunque ello
corresponda a una simplificación de la
realidad.
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.
Autor:
Rafael Daguer