PHPSimplex

Optimizando recursos con Programación Lineal



Historia de la Investigación Operativa

A lo largo de la historia es frecuente encontrar una estrecha colaboración entre científicos y militares con el fin de dictaminar la decisión óptima en la batalla e intentar obtener la victoria. Es por esto que muchos expertos en la materia consideran el inicio de la Investigación Operativa en el siglo III A.C., durante la II Guerra Púnica, con el análisis y solución que Arquímedes propuso para la defensa de la ciudad de Siracusa, sitiada por los romanos. Entre sus inventos se encontraban la catapulta, y un sistema de espejos con el que incendiaba las embarcaciones enemigas al enfocarlas con los rayos del sol.

En 1503, Leonardo da Vinci participó como ingeniero en la guerra contra Pisa ya que conocía técnicas para realizar bombardeos, construir barcos, vehículos acorazados, cañones, catapultas, y otras máquinas bélicas.

Lámina con inventos de Leonardo da Vinci

Otro antecedente de uso de la Investigación Operativa se produce durante la Primera Guerra Mundial en Inglaterra, con el estudio matemático de Frederick William Lanchester sobre la potencia balística de las fuerzas opositoras. Además desarrolló, a partir de un sistema de ecuaciones diferenciales, la Ley Cuadrática de Combate de Lanchester, con la que era posible determinar el desenlace de una batalla militar en función de la fuerza numérica relativa y la capacidad relativa de fuego de los combatientes.

Thomas Alva Edison también hizo uso de la Investigación Operativa, contribuyendo en la guerra antisubmarina, desarrollando técnicas para que los navíos pudiesen evadir y destruir los submarinos enemigos, dotándolos de una protección anti-torpedos.

Desde el punto de vista matemático, en los siglos XVII y XVIII, Newton, Leibnitz, Bernoulli y Lagrange, trabajaron en obtener máximos y mínimos condicionados de ciertas funciones. El matemático francés Jean Baptiste-Joseph Fourier esbozó métodos de la actual programación lineal. Y en los últimos años del siglo XVIII, Gaspar Monge asentó los precedentes del método Gráfico gracias a su desarrollo de la Geometría Descriptiva.

A finales del siglo XIX, Frederick Winslow Taylor realizó un estudio que permitió maximizar el rendimiento de los mineros, en el que se determinaba que la única variable realmente significativa era el peso combinado de la pala y su carga. De esta forma se diseñaron palas según los diferentes tipos de materiales con los que iban a utilizarse.

Janos Von Neumann publicó en 1928 su trabajo "Teoría de Juegos", que proporcionó fundamentos matemáticos a la Programación Lineal. Posteriormente, en 1947, visionó la similitud entre los problemas de programación lineal y la teoría de matrices que había desarrollado.

En 1939, el matemático ruso Leonid Vitálievich Kantoróvich y el holandés Tjalling Charles Koopmans, desarrollaron la teoría matemática llamada "Programación Lineal", por la que les fue concedido el Premio Nobel de Economía.

En 1945, George Joseph Stigler planteó el problema de la dieta, a raíz de la preocupación del ejército americano por asegurar unos requerimientos nutricionales básicos para sus tropas al menor coste posible. Se trataba de determinar la cantidad, entre 77 alimentos diferentes, que debería ingerir diariamente un hombre mediano de aproximadamente 70Kg de peso, de modo que las necesidades mínimas de nutrientes fuesen iguales a las recomendadas por el Consejo Nacional de Investigación norteamericano. El problema fue resuelto manualmente mediante un método heurístico con el cual se examinaron 510 diferentes posibilidades de combinación de alimentos, y cuya solución difería tan sólo unos céntimos de la solución aportada años más tarde por el método Simplex.

Durante los años 1941 y 1942, Kantorovich y Koopmans estudiaron de forma independiente el problema del transporte por primera vez, conociéndose este tipo de problemas como problema de Koopmans-Kantorovich. Para su solución, emplearon métodos geométricos que están relacionados con la teoría de convexidad de Minkowski.

Se cree que Charles Babbage es el padre de la Investigación Operativa, debido a sus investigaciones acerca de los costos de transporte y clasificación del correo realizada en la Uniform Penny Post de Inglaterra en 1840.

Sin embargo no se considera que ha nacido una nueva ciencia llamada Investigación Operativa o Investigación de Operaciones hasta la II Guerra Mundial, durante la batalla de Inglaterra. La Luftwaffe, Fuerza Aérea Alemana, estaba sometiendo a este país a un fuerte acoso aprovechando la reducida capacidad aérea británica debido a la política de desarme, aunque experimentada en el combate. El gobierno británico, buscando algún método para defender su país, convocó científicos de diversas disciplinas para tratar de resolver el problema y sacar el máximo beneficio de los radares de reciente invención de que disponían. Gracias a su trabajo determinando la localización óptima de las antenas y la mejor distribución de las señales consiguieron duplicar la efectividad del sistema de defensa aérea y evitar que la isla cayera en manos de la Alemania nazi.

También en 1942, la U-Bootswaffe alemana con su flota de submarinos U-Boot inició un bloqueo a Gran Bretaña atacando convoyes de barcos cargados de suministros procedentes de Estados Unidos e impidiendo que alcanzaran su destino. El Grupo de Investigación de Operaciones de Guerra Antisubmarina de Estados Unidos (ASWORG, Anti-Submarine Warfare Operations Research Group en inglés) realizó representaciones matemáticas de dichos convoyes, teniendo en cuenta una serie de restricciones y condiciones impuestas por la realidad, tales como la velocidad máxima a la que podían desplazarse los navíos, la cantidad de suministros que debían transportar, y el combustible necesario para alcanzar su destino. Aplicaron estos modelos también sobre los U-Boots: el tamaño de su flota, el alcance de los submarinos, sus torpedos, etc. Con base a esta información fueron capaces de modelar la guerra naval, y determinar si era mejor una estrategia basada en convoyes formados por un gran grupo de navíos de carga escoltados por muchos destructores, o por el contrario pequeños grupos más difíciles de localizar para el enemigo, e incluso la manera de causar un mayor daño a los submarinos U-Boot. Cuando la armada de los Estados Unidos de América puso en práctica esta estrategia, disminuyó de forma considerable la cantidad de barcos hundidos mientras se incrementaba la destrucción de submarinos alemanes (pasando del hundimiento de apenas una treintena al año a rondar los 250 anuales en 1943 y 1944).

Convoy de provisiones con destino Gran Bretaña

Tras apreciar el alcance de ésta nueva disciplina, Inglaterra creó otros grupos de la misma índole para obtener resultados óptimos en la contienda. De la misma forma, Estados Unidos (EEUU) al unirse a la Guerra en 1942, creó el proyecto SCOOP (Scientific Computation Of Optimum Programs). En dicho proyecto se encontraba trabajando George Bernard Dantzig, quien desarrolló en 1947 el algoritmo del método Simplex.

Durante la Guerra Fría, la antigua Unión Soviética (URSS), excluida del Plan Marshall, quiso controlar las comunicaciones terrestres, incluyendo rutas fluviales, de Berlín. Para evitar la rendición de la ciudad, y su sumisión a formar parte de la zona comunista alemana, Inglaterra y Estados Unidos decidieron abastecer la ciudad, o bien mediante convoyes escoltados (lo que podría dar lugar a nuevos enfrentamientos) o mediante puente aéreo, rompiendo o evadiendo en cualquier caso el bloqueo de Berlín. Se optó por ésta segunda opción, iniciando la Luftbrücke (puente aéreo) el 25 de junio de 1948. Éste fue otro de los problemas en los que participó el grupo SCOOP, en diciembre de ese mismo año se conseguía abastecer con 4500 toneladas diarias, y tras estudios de Investigación Operativa se optimizó el abastecimiento hasta llegar a las 8000 ó 9000 toneladas diarias en marzo de 1949. Ésta cifra era la misma que se hubiera transportado por medios terrestres, por lo que los soviéticos decidieron levantar el bloqueo el 12 de mayo de 1949.

Tras la Segunda Guerra Mundial, se estimó oportuno realizar la organización de los recursos de Estados Unidos (energía, armamento, y todo tipo de suministros) mediante modelos de optimización, resueltos mediante la Programación Lineal.

Al mismo tiempo que la doctrina de la Investigación Operativa, se desarrollaron también las técnicas de computación, las cuales permitieron una importante reducción del tiempo de resolución de los problemas.

El primer resultado de estas técnicas se obtuvo en el año 1952, utilizando un ordenador SEAC del National Bureau of Standars para obtener la solución de un problema. El éxito en el tiempo de resolución fue tan alentador que de inmediato se usó para todo tipo de problemas militares tales como la gestión de fondos monetarios para logística y armamento, determinar la altura óptima a la que deberían volar los aviones para localizar los submarinos enemigos, e incluso la profundidad a la que se debían enviar las cargas para alcanzar los submarinos enemigos de forma que causara el mayor número de bajas. Todo esto se tradujo en un aumento de hasta cinco veces en la eficacia de la fuerza aérea.

Durante las décadas de los 50 y 60, creció el interés y el desarrollo de la Investigación Operativa, debido a su aplicación en el ámbito del comercio y la industria. Un ejemplo de esto es el problema del cálculo del plan óptimo de transporte de arena de construcción a las obras de edificación de la ciudad de Moscú, donde existían 10 puntos de origen y 230 de destino. Para resolverlo se utilizó un ordenador Strena en el mes de junio de 1958, y después de 10 días de cálculos produjo una solución que aportó una reducción del 11% de los gastos respecto a los costes originales previstos.

Anteriormente ya se habían planteado estos problemas en una disciplina conocida como Investigación de Empresas o Análisis de Empresas, que no disponían de métodos tan efectivos como los desarrollados durante la Segunda Guerra Mundial (por ejemplo el método Simplex). Las aplicaciones no bélicas de la Investigación Operativa se extienden a todos los ámbitos, con problemas que van desde la alimentación, ganadería, distribución de campos de cultivo en agricultura, transporte de mercancías, localización, distribución de personal, problemas de redes, colas, grafos, etc.

A modo de ejemplo se pueden observar los siguientes casos reales de uso de Investigación Operativa y los beneficios reportados.

Copyright ©2006-2014 PHPSimplex. Todos los derechos reservados. Términos y condiciones.
Síguenos en Twitter
X

PHPSimplex
Versión 0.9

Copyright ©2006-2014. Todos los derechos reservados.

Desarrollado por:
Daniel Izquierdo Granja
Juan José Ruiz Ruiz

Traducción a inglés por:
Luciano Miguel Tobaria

Traducción a francés por:
Ester Rute Ruiz