Investigación de operaciones modelos y aplicaciones de programación lineal

I. LA INVESTIGACIÓN DE OPERACIONES, USO DE MODELOS Y METODOS DE OPTIMIZACION

I.1 INTRODUCCION A LA INVESTIGACIÓN DE OPERACIONES

1. Un poco de Historia

Se inicia desde la revolución industrial, en los libros se dice que fue a partir de la segunda Guerra Mundial. La investigación de operaciones se aplica a casi todos los problemas. En 1947, en EE.UU., George Datzing encuentra el método simplex para el problema de programación lineal. En la investigación de operaciones, las computadoras son la herramienta fundamental en la investigación de operaciones.

2. Definición

La Investigación de Operaciones, es la aplicación del método científico por un grupo multidisciplinario de personas a un problema, principalmente relacionado con la distribución eficaz de recursos limitados (dinero, materia prima, mano de obra, energía), que apoyados con el enfoque de sistemas (este enfoque, es aquel en el que un grupo de personas con distintas áreas de conocimiento, discuten sobre la manera de resolver un problema en grupo.). Puede considerarse tanto un arte como una ciencia. Como arte refleja los conceptos eficiente y limitado de un modelo matemático definido para una situación dada. Como ciencia comprende la deducción de métodos de cálculo para resolver los modelos.

2.1 Pasos del Método científico en IO

1. Definición del problema.- Desde el punto de vista de la Investigación de operaciones(IO),esto indica tres aspectos principales:(a)Una descripciónde la meta o el objetivo del estudio,(b)Una Identificación de las alternativas de decisión y (c) Un reconocimiento de las limitaciones, restricciones y requisitos del sistema

2. Construcción del Modelo. Dependiendo de la definición del problema, el equipo de investigación de operaciones deberá decidir sobre el modelo mas adecuado para representar el sistema (modelo matemático, modelo de simulación; combinación de modelos matemáticos, de simulación y heurísticos)

3. Solución del Modelo.- En modelos matemáticos esto se logra usando técnicas de optimización bien definidas y se dice que el modelo proporciona una solución optima. Si se usan los modelos de simulación o heurísticos el concepto de optimalidad no esta bien definido, y la solución en estos casos se emplea para obtener evaluaciones aproximadas de las medidas del sistema

4.Validación del Modelo.- Un modelo es valido si, independientemente de sus inexactitudes al representar el sistema, puede dar una predicción confiable del funcionamiento del sistema

5. Implantación de los resultados Finales.-La tarea de aplicar los resultados probados del sistema recae principalmente en los investigadores de operaciones. Esto básicamente implicaría la traducción de estos resultados en instrucciones de operación detallada, emitidas en una forma comprensible a los individuos que administraran y operaran el sistema después. La interacción del equipo de investigación de operaciones y el personalde operación llegara a su máximo en esta fase.

I.2 TIPOS DE MODELOS DE INVESTIGACION DE OPERACIONES

Un modelo es una representación ideal de un sistema y la forma en que este opera. El objetivo es analizar el comportamiento del sistema o bien predecir su comportamiento futuro. Obviamente los modelos no son tan complejos como el sistema mismo, de tal manera que se hacen las suposiciones y restricciones necesarias para representar las porciones más relevantes del mismo. Claramente no habría ventaja alguna de utilizar modelos si estos no simplificaran la situación real. En muchos casos podemos utilizar modelos matemáticos que, mediante letras, números y operaciones, representan variables, magnitudes y sus relaciones.



Fig.1.2: Representación de un modelo

1. Modelos Matemáticos

Un modelo es producto de una abstracción de un sistema real: eliminando las complejidades y haciendo suposiciones pertinentes, se aplica una técnicamatemática y se obtiene una representación simbólica del mismo. Un modelo matemático consta al menos de tres conjuntos básicos de elementos:


Variables de decisión y parámetros

Las variables de decisión son incógnitas que deben ser determinadas a partir de la solución del modelo. Los parámetros representan los valoresconocidos del sistema o bien que se pueden controlar.


Restricciones

Las restricciones son relaciones entre las variables de decisión y magnitudes que dan sentido a la solución del problema y las acotan a valores factibles. Por ejemplo si una de las variables de decisión representa el número de empleados de un taller, es evidente que el valor de esa variable no puede ser negativo.


Función Objetivo

La función objetivo es una relación matemática entre las variables de decisión, parámetros y una magnitud que representa el objetivo o producto del sistema. Por ejemplo si el objetivo del sistema es minimizar los costos de operación, la función objetivo debe expresar la relación entre el costo y las variables de decisión. La solución ÓPTIMA se obtiene cuando el valor del costo sea mínimo para un conjunto de valores factibles de las variables. Es decir hay que determinar las variables x1, x2,..., xn que optimicen el valor de Z = f(x1, x2,..., xn) sujeto a restricciones de la forma g(x1, x2,..., xn) ? b. Donde x1, x2,..., xn son las variables de decisión Z es la función objetivo, f es una función matemática.

EJEMPLO 1.2.1: Sean X1 y X2 la cantidad a producirse de dos productos 1 y 2, los parámetros son los costos de producción de ambos productos, $3 para el producto 1 y $5 para el producto 2. Si el tiempo total de producción esta restringido a 500 horas y el tiempo de producción es de 8 horas por unidad para el producto 1 y de 7 horas por unidad para el producto 2, entonces podemos representar el modelo como:

MinZ = 3X1 + 5X2 (Costo total de Producción)

Sujeto a (S.A):

8X1 + 7X2 ? 500 (Tiempo total de producción)

X1, X2>= 0 (Restricciones de no negatividad)

EJEMPLO 1.2.2: En una empresa se fabrican dos productos, cada producto debe pasar por una máquina de ensamblaje A y otra de terminado B,antes antes de salir a la venta.El producto 1 se vende a $60 y el otro a $50 por unidad. La siguiente tabla muestra el tiempo requerido por cada producto:


Producto

Maquina A

Maquina B


1

2 H

3 H


2

4 H

2 H


Total disponible

48 H

36 H


Para representar el modelo de este problema primero se debe determinar las variables de decisión: Sea Xi: La cantidad a fabricar del producto 1 y 2 (i=1,2), entonces X1: cantidad a fabricar del producto 1, X2: cantidad a fabricar del producto2, luego el modelo quedaría de la siguiente manera:

MaxZ = 60X1+ 50X2 (máximo ingreso por ventas)

S.A: 2X1+ 4X2 <= 48 (disponibilidad horas _maquina A)

3X1+ 2X2 <= 36 (disponibilidad horas _maquina B)

X1, X2 >= 0 (Restricciones de no negatividad)

2. Modelos de Simulación

La simulación es una técnica para crear modelos de sistemas grandes y complejos que incluyen incertidumbre. Se diseña un modelo para repetir el comportamiento del sistema. Este tipo de modelamiento se basa en la división del sistema en módulos básicos o elementales que se enlazan entre sí mediante relaciones lógicas bien definidas (de la forma SI / ENTONCES). El desarrollo de un modelo de simulación es muy costoso en tiempo y recursos.

Aplicaciones de la Investigación Operativa

La Investigación de Operaciones o Investigación Operativa es una herramienta metodológica cuantitativa que nos permite la asignación óptima de recursos escasos y en general apoyar de una forma eficiente el proceso de toma de decisiones. La Investigación de Operaciones hace uso de modelos matemáticos con el objetivo que las decisiones que éstos nos proveen sean significativamente mejores en comparación a aquellas decisiones que se toman con una base cualitativa.

Las aplicaciones de la Investigación de Operaciones crecen rápidamente, principalmente por un mejor conocimiento de estas metodología en las diferentes disciplinas, la creciente complejidad de los problemas que se desea resolver, la mayor disponibilidad de software y el desarrollo de nuevos y mejores algoritmos de solución. A continuación un listado de distintas aplicaciones de la Investigación Operativa y los beneficios asociados a su implementación:

Organización	Aplicación	Año	Ahorros anuales
The Netherlands Rijkswaterstaat	Desarrollo de la política nacional de administración del agua, incluyendo mezcla de nuevas instalaciones, procedimientos de operaciones y costeo	1985	$15 millones
Monsanto Corp.	Optimización de las operaciones de producción para cumplir metas con un costo mínimo	1985	$2 millones
Weyerhauser Co.	Optimización del corte de árboles en productos de madera para maximizar su producción	1986	$15 millones
Electrobas/CEPAL Brasil	Asignación óptima de recursos hidráulicos y térmicos en el sistema nacional de generación de energía	1986	$43 millones
United Airlines	Programación de turnos de trabajo en oficinas de reservaciones y aeropuertos para cumplir con las necesidades del cliente a un costo mínimo	1986	$6 millones
Citgo Petroleum Corp.	Optimización de las operaciones de refinación y de la oferta, distribución y comercialización de productos	1987	$70 millones
SANTOS, Ltd., Australia	Optimización de inversiones de capital para producir gas natural durante 25 años	1987	$3 millones
Electric Power Research Institute	Administración de inventarios de petróleo y carbón para el servicio eléctrico con el fin de equilibrar los costos de inventario y los riesgos de faltantes.	1989	$59 millones
San Francisco Police Department	Optimización de la programación y asignación de oficiales de patrulla con un sistema computerizado	1989	$11 millones
Texaco Inc.	Optimización de la mezcla de ingredientes disponibles para que los productos de gasolina cumplieran con los requerimientos de ventas y calidad	1989	$30 millones
IBM	Integración de una red nacional de inventario de refacciones para mejorar el apoyo al servicio	1990	$20 millones + $250 millones en menor inventario
U.S. Military Airlift Command	Rapidez en la coordinación de aviones, tripulación, carga y pasajeros para manejar la evacuación por aire en el proyecto "Tormenta del Desierto" en el Medio Oriente	1992	Victoria
American Airlines	Diseño de un sistema de estructura de precios, sobreventas y coordinación de vuelos para mejorar las utilidades	1992	$500 millones más de ingresos
Yellow Freight System, Inc.	Optimización del diseño de una red nacional de transporte y la programación de rutas de envío	1992	$17.3 millones
New Haven Health Dept.	Diseño de un programa efectivo de cambio de agujas para combatir el contagio del SIDA	1993	33% menos contagios
AT&T	Desarrollo de un sistema basado en PC para guiar a los clientes del negocio en el diseño del centro de llamadas	1993	$750 millones
Delta Airlines	Maximización de ganancias a partir de la asignación de los tipos de aviones en 2.500 vuelos nacionales	1994	$100 millones
Digital Equipment Corp.	Reestructuración de toda la cadena de proveedores entre proveedores, plantas, centros de distribución, sitios potenciales y áreas de mercado	1995	$800 millones
China	Selección y programación óptima de proyectos masivos para cumplir con las necesidades futuras de energía del país	1995	$425 millones
Cuerpo de defensa de Sudáfrica	Rediseño óptimo del tamaño y forma del cuerpo de defensa y su sistema de armas	1997	$1.100 millones
Procter and Gamble	Rediseño del sistema de producción y distribución norteamericano para reducir costos y mejorar la rapidez de llegada al mercado	1997	$200 millones
Taco Bell	Programación óptima de empleados para proporcionar el servicio a clientes deseado con un costo mínimo	1998	$13 millones
Hewlett-Packard	Rediseño de tamaño y localización de inventarios de seguridad en la línea de producción de impresoras para cumplir metas de producción	1998	$280 millones de ingreso adicional

Fuente: PHPSimplex

Investigación Operativa Modelamientos matemáticos

La Investigación de Operaciones o Investigación Operativa (en inglés ORu Operations Research) es una disciplina que consiste en la aplicación de métodos analíticos avanzados con el propósito de apoyar el proceso de toma de decisiones, identificando los mejores cursos de acción posibles.

En este contexto la Investigación de Operaciones utiliza técnicas de modelamiento matemático, análisis estadístico y optimización matemática, con el objetivo de alcanzar soluciones óptimas o cercanas a ellas cuando se enfrentan problemas de decisión complejos. Se espera que las decisiones alcanzadas mediante el uso de un modelo de investigación operativa sean significativamente mejores en comparación a aquellas decisiones que se podrían tomar haciendo uso de la simple intuición o experiencia del tomador de decisiones. Lo anterior es particularmente cierto en aquellos problemas de naturaleza real complejos, que consideran cientos, incluso miles de variables de decisión y restricciones.

La Investigación de Operaciones se complementa con otras disciplinas como la Ingeniería Industrial y la Gestión de Operaciones. En términos estrictos un modelo de optimización considera una función objetivo en una o varias variables que se desea maximizar (por ejemplo el ingreso o beneficio asociado a un plan de producción) o por el contrario minimizar (por ejemplo los costos de una firma, el riesgo asociado a una decisión, la pérdida de un alternativa, etc). Los valores que pueden adoptar las variables de decisión usualmente están restringidos por restricciones que adoptan la forma de ecuaciones y/o inecuaciones que buscan representar las limitantes asociadas a la problemática.

El enfoque de la Investigación de Operaciones es el modelaje. Un modelo es una herramienta analítica que nos sirve para lograr una visión bien estructurada de la realidad. Así, el propósito del modelo es proporcionar un medio para analizar el comportamiento de las componentes de un sistema con el fin de optimizar su desempeño (identificar el mejor curso de acción posible).

Una visión esquemática del proceso asociado a la construcción de un modelo de optimización se presenta a continuación:

1. Definición del problema: Se debe definir el problema para el cual se busca proponer un curso de acción. ¿Es un problema relevante? ¿es posible tomar una buena decisión sin la necesidad de resolver un modelo de optimización? ¿cuáles son sus alcances? ¿cuáles son los factores que influyen en el desempeño del sistema?, etc. La calidad del modelo de optimización dependerá en gran parte de la asertividad en la definición del problema de decisión.

2. Construcción de un modelo: Un modelo de optimización considera necesariamente una abstracción o simplificación de la realidad. Por un lado se busca que el modelo sea representativo del problema real que se busca representar pero que al mismo tiempo sea simple de modo de favorecer su resolución haciendo uso de un algoritmo ad-hoc. Alcanzar este equilibrio no es trivial. Por ello ante un mismo problema puede existir más de un modelo de optimización que lo represente con distintos niveles de detalle y abstracción.

3. Solución del modelo: Una vez construido el modelo de optimización se deben identificar las alternativas de resolución para el mismo. Para ello se puede hacer uso de programas computacionales que utilizan algoritmos de resolución específicos dependiendo de las características del modelo. Por ejemplo, para resolver un problema de Programación Lineal (las variables de decisión se representan como funciones lineales tanto en la función objetivo como restricciones) se puede utilizar el Método Simplex.

4. Validación: Se verifica que la solución alcanzada cumpla con las condiciones (restricciones) impuestas al problema.

5. Implementación y control de la solución: Una vez verificada la solución se procede a su implementación. Cabe destacar que esto puede lugar a actualizaciones del modelo de optimización tanto en términos del modelo como el valor de los parámetros estimados. Por ejemplo, si el modelo de optimización corresponde a un Plan Maestro de la Producción (PMP) y se genera un cambio en el valor de la hora hombre de los trabajadores será necesario actualizar el valor del parámetro que representa dicho costo para posteriores instancias de resolución.

En la actualidad el uso de modelos de optimización es cada vez más frecuente en la toma de decisiones. Este mayor uso se explica, principalmente, por un mejor conocimiento de estas metodología en las diferentes disciplinas, la creciente complejidad de los problemas que se desea resolver, la mayor disponibilidad de software y el desarrollo de nuevos y mejores algoritmos de solución.

Programación lineal

El problema de la resolución de un sistema lineal de inecuaciones se remonta, al menos, a Joseph Fourier, después de quien nace el método de eliminación de Fourier-Motzkin. La programación lineal se plantea como un modelo matemático desarrollado durante la Segunda Guerra Mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas industrias lo usaron en su planificación diaria.

Los fundadores de la técnica son George Dantzig, quien publicó el algoritmo simplex, en 1947, John von Neumann, que desarrolló la teoría de la dualidad en el mismo año, y Leonid Kantoróvich, un matemático de origen ruso, que utiliza técnicas similares en la economía antes de Dantzig y ganó el premio Nobel en economía en 1975. En 1979, otro matemático ruso, Leonid Khachiyan, diseñó el llamado Algoritmo del elipsoide, a través del cual demostró que el problema de la programación lineal es resoluble de manera eficiente, es decir, en tiempo polinomial.2​ Más tarde, en 1984, Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal, lo que constituiría un enorme avance en los principios teóricos y prácticos en el área.

El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70 personas a 70 puestos de trabajo es un ejemplo de la utilidad de la programación lineal. La potencia de computación necesaria para examinar todas las permutaciones a fin de seleccionar la mejor asignación es inmensa (factorial de 70, 70!) ; el número de posibles configuraciones excede al número de partículas en el universo. Sin embargo, toma sólo un momento encontrar la solución óptima mediante el planteamiento del problema como una programación lineal y la aplicación del algoritmo simplex. La teoría de la programación lineal reduce drásticamente el número de posibles soluciones factibles que deben ser revisadas.

El gurú en técnicas de investigación operativa

Revista Contacto No. 13 / 23 de mayo de 2017




Modelos matemáticos, probabilidad y estadística, teoría de juegos y ciencias de la decisión hacen parte del bagaje académico del investigador Rajan Batta, profesor de la Escuela de Ingeniería y Ciencias Aplicadas de la Universidad de Buffalo en Estados Unidos, quien ha centrado su trabajo en desarrollar nuevos modelos en técnicas de investigación operativa para resolver problemáticas urbanas relacionadas con el transporte y logística.




Este ingeniero mecánico, nacido en India, es uno de los invitados de lujo de la próxima Escuela Internacional de Verano que se desarrolla en el periodo intersemestral en Uniandes. Con el curso 'Applications of Opperations Research to Urban Problems' espera compartir las últimas novedades de este modelo con los ingenieros colombianos.


​


El profesor Batta conversó con CONTACTO sobre sus intereses académicos y sus expectativas con el curso. ​

​

CONTACTO: Su filosofía de investigación toma como base el problema a resolver y a partir de ahí la creación de modelos para encontrar la mejor solución. ¿Podría explicar este método?




Rajan Batta: Mi verdadera preferencia es trabajar en la solución de problemas en un entorno de aplicaciones. Un ejemplo es un problema de enrutamiento de autobuses escolares en el que trabajé para un distrito escolar local. El problema implicó el enrutamiento del vehículo con severas tasas de sobrecupo, ya que muchos estudiantes no toman el autobús a la escuela todos los días. Una vez examinamos el problema descubrimos que no había una investigación específica sobre esta situación y tuvimos que desarrollar un nuevo modelo y crear una nueva teoría para apoyarlo. Nuestros hallazgos y recomendaciones fueron publicados en la revista Transportation Science, y también fueron compartidos con la comunidad en una reunión de la junta escolar, después de la cual se llevó a cabo la implementación.




Estos problemas son difíciles de encontrar, por lo que también trabajo en los problemas que son de suma importancia para la sociedad y tratar de aprender sobre el dominio de la aplicación tanto como sea posible durante la realización de la investigación. Por lo general, también hacemos un estudio de caso para demostrar el potencial de aplicabilidad del modelo.