Investigacion De Operaciones

INVESTIGACION DE OPERACIONES

Conceptos

Explicar qué se entiende por investigación de operaciones y algunas de sus aplicaciones.

La investigación de operaciones es una rama de las matemáticas que consiste en el uso de modelos matemáticos, estadística y algoritmos con objeto de realizar un proceso de toma de decisiones. Frecuentemente trata del estudio de complejos sistemas reales, con la finalidad de mejorar (u optimizar) su funcionamiento. La investigación de operaciones permite el análisis de la toma de decisiones teniendo en cuenta la escasez de recursos, para determinar cómo se puede optimizar un objetivo definido, como la maximización de los beneficios o la minimización de costos.

Podríamos pues indicar que la investigación de operaciones sólo se aplicará a los problemas de mayor complejidad, sin olvidar que el simple uso de la Investigacion de operaciones trae un costo, que de superar el beneficio, no resultará económicamente práctico, algunos ejemplos prácticos donde usarla resulta útil son:

• En el dominio combinatorio, muchas veces la enumeración es imposible. Por ejemplo, si tenemos 200 trabajos por realizar, que toman tiempos distintos y solo cuatro personas que pueden hacerlos, enumerar cada una de las combinaciones podría ser ineficiente (aparte de desanimante). Luego los métodos de secuenciación serán los más apropiados para este tipo de problemas.

• De igual manera, es útil cuando en los fenómenos estudiados interviene el azar. La noción de esperanza matemática y la teoría de procesos estocásticos suministran la herramienta necesaria para construir el cuadro en el cual se optimizará la función económica. Dentro de este tipo de fenómenos se encuentran las líneas de espera y los inventarios con demanda probabilística.

• Con mayor motivo, la investigación de operaciones se muestra como un conjunto de instrumentos precioso cuando se presentan situaciones de concurrencia. La teoría de juegos no permite siempre resolverlos formalmente, pero aporta un marco de reflexión que ayude a la toma de decisiones.

• Cuando observamos que los métodos científicos resultan engorrosos para nuestro conjunto de datos, tenemos otra opción, simular tanto el comportamiento actual así como las propuestas y ver si hay mejoras sustanciales. Las simulaciones son experiencias artificiales.

Explicar qué es un modelo, tipos de modelos, los pasos necesarios para su formulación y su importancia como elemento básico en la investigación de operaciones.

Un modelo es una representación de la realidad, o mejor dicho, trata de representar parte de la realidad según y como lo perciban las personas o bien el modelador según su objetivo, para entender, cambiar, gestionar y controlar esa parte de la realidad.

Los modelos puedes ser de los siguientes tipos:

ICONICOS: Es una representación física de algunos objetos, ya sea en forma idealizada (bosquejos) o a escala distinta.

Ejemplo:

•Planos y mapas (dos dimensiones).

•Maquetas y prototipos (4 dimensiones).

ANALOGICOS: Puede representar situaciones dinámicas o cíclicas, son mas usuales y pueden representar las características y propiedades del acontecimiento que se estudia.

Ejemplo:

•Curvas de demanda.

•Curvas de distribución de frecuencia en las estadísticas y diagramas de flujo.

SIMBOLICOS O MATEMATICOS: Son representaciones de la realidad en forma de cifras, símbolos matemáticos y funciones, para representar

variables de decisión y relaciones que nos permiten describir y analizar el comportamiento del sistema

Los pasos para la resolución de modelos de investigación de operaciones se resumen en los siguientes aspectos:

1. Definición del problema de interés y recolección de los datos relevantes

2. Formulación de un modelo que represente el problema

3. Solución del modelo

4 . Prueba del modelo

5. Preparación para la aplicación del modelo

6. Puesta en marcha

Definición del problema y recolección de datos

La primera actividad que se debe realizar es el estudio del sistema relevante, esto incluye determinar los objetivos, las restricciones sobre lo que se puede hacer, los diferentes cursos de acción posibles las interrelaciones del área bajo estudio con otras áreas de la organización, los límites de tiempo para tomar una decisión . Este proceso de definir el problema es muy importante ya que afectará en forma significativa las conclusiones en estudio, lo cual hace imposible extraer una respuesta correcta de un problema equivocado.

Formulación del modelo

Una vez definido el problema la siguiente etapa consiste en reformularlo para su análisis, mediante la construcción de un modelo que represente la esencia del problema. Los modelos son representaciones idealizadas de la realidad. Los modelos tienen muchas ventajas sobre una descripción verbal del problema, una ventaja obvia es que el modelo describe un problema en forma mucho más concisa.

Obtención de una solución a parir del modelo

Una vez formulado el modelo para el problema bajo estudio, la siguiente etapa de un estudio consiste en desarrollar un procedimiento para derivar

en una solución al problema a partir de este modelo, según el tipo de modelo este puede hacerse en computadora.

Prueba del modelo

Sin duda que la primera versión de un modelo grande tenga muchas fallas, por lo tanto antes de usar el modelo debe probarse para identificar y corregir todas las fallas que se pueda, este proceso de prueba y mejoramiento se conoce como validación del modelo. Un modelo es válido si, independientemente de sus inexactitudes, puede dar una predicción confiable del funcionamiento del sistema. Un método común para probar

la validez de un modelo es comparar su funcionamiento con algunos datos pasados disponibles del sistema actual (se le llama también prueba retrospectiva).

Preparación para la aplicación del modelo

El siguiente paso es instalar un sistema bien documentado para aplicar el modelo. Este sistema incluirá el modelo y el procedimiento de solución (además del análisis postóptimo) y los procedimientos operativos para su implantación (este sistema casi siempre esta diseñado para computadora).

Implantación del modelo

Una vez desarrollado el sistema para aplicar el modelo, la última etapa consiste en la implantación de los resultados probados del modelo. 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 administrará y operarán al sistema.

Explicar el origen y naturaleza de la 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 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.

Formular y resolver, gráficamente, problemas mediante la utilización del modelo de programación lineal.

Explicar el concepto y la estructura de un algoritmo.

Un algoritmo es una secuencia lógica de operaciones ejecutadas en un determinado orden para resolver un problema. Generalmente se asocia a un programa informatico y esta definido por lenguajes de programación.

Debe ser confiable, indicado con un orden lógico a seguir y debe ser finito, o sea, debe terminar en un numero finito de pasos.

La estructura básica de todo algoritmo se basa en tres etapas básicas, debe tener un inicio y un fin, y como el cuerpo o parte del desarrollo del

algoritmo tenemos los procesos, lectura de datos, entradas y salidas, ciclos y condiciones.

Describir el planeamiento del método simplex.

El método Simplex es un método secuencial de optimización, es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.

Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.

Explicar el álgebra del método simplex.

En el algoritmo del Símplex, se parte de un programa base que estará formado por vectores unitarios (vector proceso unitario), realizando iteraciones sucesivas, de manera que en cada uno de ellos, la matriz de coeficientes asociada al programa base sea una matriz identidad.

Los pasos a seguir en el algoritmo del Símplex son:

1. Convertir desigualdades en igualdades, introduciendo para ello variables de holgura, que serán positivas en restricciones menores o iguales, y negativas en restricciones mayores o iguales.

2. Obtener el programa base: Esta es la pregunta inicial de la cual partimos para determinar la solución. Para encontrar el programa base, tomaremos un vector unitario de cada una de las restricciones del problema, de acuerdo con el siguiente esquema:

2.1. Escoger aquellas variables de holgura con el mismo signo que el término independiente y coeficiente unitario.

2.2. En su defecto, escoger aquellas variables Xi que aparezca en una única restricción, y tenga el mismo signo que el término independiente. Esta variable deberá tener coeficiente unitario.

2.3. En su defecto, introduciremos en aquellas restricciones de las cuales no hemos tocado aún, un vector unitario una variable artificial Kj afectada de un rendimiento –N si estamos maximizando, o de un rendimiento +N si estamos minimizando, y que tendrá un coeficiente unitario.

El método Simplex básico

El método Simplex, introducido en su forma original por Spendley; Hext y Himsworth, en 1962, no se basa en planeamientos factoriales y por eso requiere pocos experimentos para moverse, desplazándose en la dirección del óptimo. La aplicación del método Simplex en Química Analítica fue efectuada por la primera vez en 1969. El método Simplex original, a lo largo de estos años, há sufrido modificaciones que obligaron a la distinción del mismo dentro de las estrategias de optimización, así el método Simplex original pasó a ser llamado de Método Simplex Básico (MSB).

El procedimiento de optimización, en el método Simplex, comienza por la elección de la n+1 puntos donde será hecha la evaluación de la respuesta. Este resultado será evaluado contra las demás respuestas para que el proceso pueda continuar, siendo que este tipo de desarrollo convierte al simplex en un método del tipo secuencial.

El procedimiento es repetido sucesivamente, descartándose la peor respuesta. Por lo tanto, como vemos, el objetivo del método Simplex secuencial es forzar al simplex a moverse para la región de respuesta óptima.

Las decisiones requeridas para que eso sea posible constituyen las llamadas "reglas" del procedimiento simplex.

REGLAS PARA EL MOVIMIENTO DEL SIMPLEX BÁSICO

Regla nº 1: Después de determinar las respuestas de los n+1 experimentos necesarios para iniciar el proceso, con base en el conocimiento ya adquirido sobre el sistema, se debe clasificarlas en mejor

[B (the Best)], peor [W (the Worst)] y resultados intermediarios [N (Next to worst)], según el objetivo de la optimización.

Regla nº 2: El simplex es movido para un simplex adyacente, el cuál es determinado descartando la respuesta menos deseada. El vértice correspondiente a esta respuesta es sustituido por un nuevo vértice, generado por su reflexión a través del centroide de la hiperfase de los vértices restantes.

Matematicamente, sí los vértices de un simplex k-dimensional son representados por coordenadas vectoriales P1, P2, ...., Pj, ....Pk, .... Pk+1, la eliminación de la respuesta no deseada Pj resulta en la hiperfase formada por P1, P2, ...., Pj-1, Pj+1, ....Pk, .... Pk+1 con el centroide definido por:

Pc = 1/k (P1 + P2 + .... + Pj-1 + Pj+1 + .... + Pk + Pk+1)

Pc = centroide de la hiperfase K = número de dimensiones del simplexPj = vértice correspondiente a la peor respuesta.

El nuevo simplex es definido por esta fase y un nuevo vértice, P, que corresponde a la reflexión del vértice rechazado Pj, a través de la fase por el centroide Pc.

P = Pc + (Pc - Pj)

Regla nº 3: Sí el punto reflejado, P, tuviera la peor respuesta en el nuevo simplex, probablemente el desplazamiento no está sucediendo en dirección al óptimo. En este caso, se debe rechazar la 2ª peor respuesta de este simplex y continuar con la optimización.

Esta regla es necesaria, pues el simplex puede estar encima de una cresta y la aplicación directa de la Regla no 2 puede hacer con que el punto P sea reflejado de vuelta al punto anterior. En este caso el simplex oscila y se vuelve sin recurso (decimos, que se mantiene parado).

Esta situación sucede con frecuencia en la región del óptimo. Sí un punto es obtenido cercano a él, todos los otros nuevos puntos tienden a pasar más allá del tope de la curva de respuesta. Entonces, un cambio en la dirección es indicado. En la región del óptimo, normalmente ocurre el

simplex circular en vuelta de un óptimo temporáneo. Como se puede tratar de un resultado falso, el cual hace, con que el simplex se prenda a él, es necesario la siguiente excepción adicional a la Regla no 1.

Regla nº 4: Sí un vértice fuera mantenido en k+1 simplex, antes de aplicar la Regla no 2, haga una nueva observación del vértice persistente. Sí el vértice está realmente cercano al óptimo, es probable que la evaluación repetida de la respuesta sea consistente y de esta forma el punto será mantenido. Sí la respuesta en el vértice fuera alta por causa de un error de observación, es improbable que con la nueva evaluación eso ocurra y por lo tanto, el vértice será consecuentemente eliminado.

Regla nº 5: Sí el nuevo vértice encontrarse fuera de los limites aceptables de las variables optimizadas, no se deben realizar observaciones experimentales con estos valores, al contrario se debe atribuir a este la respuesta más indeseable.

La aplicación posterior de las Reglas nos 2 e 3 obligará al simplex a regresar dentro de los límites permitidos y este continuará buscando por la respuesta óptima. Cuando un óptimo es localizado, las reglas del simplex lo fuerzan a circular.

Determinar situaciones en las que se pueda aplicar el método simple.

El metodo simplex se puede aplicar a problemas cotidianos relacionados con la mejora de sistemas en el transporte, suministros, productividad, abastecimiento e inventarios entre otros

3.1 Explicar la importancia de los problemas de programación lineal

La Investigación de operaciones o “Science managment”, conocida en nuestro medio como la Programación Lineal e Investigación Operativa ha evolucionado en su aplicación en los últimos años, pero aún no nos hemos dado cuenta de ello y eso hace que este tema no cobre la importancia que realmente merece. De esta forma la importancia de la Programación Lineal no solo radica en el procedimiento matemático, sino en la herramienta financiera que sirve de soporte para la toma de decisiones en cualquier organización. Adicionalmente, vale la pena resaltar que, para el Administrador de Empresas, el Economista, el

contador, el Gerente, el financiero, y para el empresario en general, es vital manejar adecuadamente esta herramienta que es aplicable a todas las áreas que componen una organización empresarial y que permiten la asignación eficiente de los recursos, además de la ayuda que presta para globalizar la información. La Programación Lineal busca la asignación eficiente de los recursos asignados, que permite maximizar las utilidades y minimizar los costos. Por lo tanto, Programación Lineal comprende la planificación de actividades, es decir un resultado que alcance la meta en la mejor forma teniendo en cuenta las restricciones propias de cada actividad. En definitiva, se llama Programación Lineal al conjunto de técnicas matemáticas que pretenden resolver la situación siguiente: optimizar (maximizar ó minimizar) una función objetivo, función lineal de varias variables sujeta a una serie de restricciones, expresada por inecuaciones lineales.

La programación lineal constituye un importante campo de la optimización por varias razones, muchos problemas prácticos de la investigación de operaciones pueden plantearse como problemas de programación lineal. Algunos casos especiales de programación lineal, tales como los problemas de flujo de redes y problemas de flujo de mercancías se consideraron en el desarrollo de las matemáticas lo suficientemente importantes como para generar por si mismos mucha investigación sobre algoritmos especializados en su solución. Una serie de algoritmos diseñados para resolver otros tipos de problemas de optimización constituyen casos particulares de la más amplia técnica de la programación lineal. Históricamente, las ideas de programación lineal han inspirado muchos de los conceptos centrales de la teoría de optimización tales como la dualidad, la descomposición y la importancia de la convexidad y sus generalizaciones. Del mismo modo, la programación lineal es muy usada en la microeconomía y la administración de empresas, ya sea para aumentar al máximo los ingresos o reducir al mínimo los costos de un sistema de producción. Algunos ejemplos son la mezcla de alimentos, la gestión de inventarios, la cartera y la gestión de las finanzas, la asignación de recursos humanos y recursos de máquinas, la planificación de campañas de publicidad, etc.

Otros son:

• Optimización de la combinación de cifras comerciales en una red lineal de distribución de agua.

• Aprovechamiento óptimo de los recursos de una cuenca hidrográfica, para un año con afluencias caracterizadas por corresponder a una determinada frecuencia.

• Soporte para toma de decisión en tiempo real, para operación de un sistema de obras hidráulicas;

• Solución de problemas de transporte.

Explicar la estructura básica del problema del transporte.

Este es un caso curioso, con solo 6 variables (un caso real de problema de transporte puede tener fácilmente más de 1.000 variables) en el cual se aprecia la utilidad de este procedimiento de cálculo.

Existen tres minas de carbón cuya producción diaria es:

• La mina "a" produce 40 toneladas de carbón por día;

• La mina "b" produce 40 t/día; y,

• La mina "c" produce 20 t/día.

En la zona hay dos centrales termoeléctricas que consumen:

• La central "d" consume 40 t/día de carbón; y,

• La central "e" consume 60 t/día

Los costos de mercado, de transporte por tonelada son:

• De "a" a "d" = 2 monedas

• De "a" a "e" = 11 monedas

• De "b" a "d" = 12 monedas

• De "b" a "e" = 24 monedas

• De "c" a "d" = 13 monedas

• De "c" a "e" = 18 monedas

Si se preguntase a los pobladores de la zona cómo organizar el transporte, tal vez la mayoría opinaría que debe aprovecharse el precio ofrecido por el transportista que va de "a" a "d", porque es más conveniente que los otros, debido a que es el de más bajo precio.

En este caso, el costo total del transporte es:

• Transporte de 40 t de "a" a "d" = 80 monedas

• Transporte de 20 t de "c" a "e" = 360 monedas

• Transporte de 40 t de "b" a "e" = 960 monedas

• Total 1.400 monedas.

Sin embargo, formulando el problema para ser resuelto por la programación lineal se tienen las siguientes ecuaciones:

• Restricciones de la producción:

• Restricciones del consumo:

• La función objetivo será:

La solución de costo mínimo de transporte diario resulta ser:

• Xb-d = 40 resultando un costo de 12 x 40 = 480 monedas

• Xa-e = 40 resultando un costo de 11 x 40 = 440 monedas

• Xc-e = 20 resultando un costo de 18 x 20 = 360 monedas

• Total 1.280 monedas.

120 monedas menos que antes.

Determinar, en la práctica, en cuáles situaciones se debe aplicar el modelo de transporte.

Dos tipos particularmente importantes (y relacionados) de problemas de programación lineal, son el problema de transporte y el problema de asignación.

El problema de transporte recibe este nombre debido a que muchas de sus aplicaciones involucran determinar la manera óptima de transportar bienes. Sin embargo, algunas de aplicaciones importantes (como la programación de la producción), de hecho no tienen nada que ver con el transporte.

El segundo tipo, llamado problema de asignación, incluye aplicaciones tales como asignar personas a tareas. Aunque sus aplicaciones parecen diferir del problema de transporte, se vera que este problema es un acaso especial del problema de transporte.

Modelo del problema de transporte.

El problema general de transporte se refiere a la distribución de cualquier bien desde cualquier grupo de centros de suministro, llamados orígenes, a cualquier grupo de centros de recepción, llamados destinos, de tal manera que se minimicen los costos totales de distribución.

Determinar, en la práctica, en las cuáles situaciones se debe de aplicar el modelo de asignación.

PROBLEMA DE ASIGNACION.

El problema de asignación es un tipo especial de problema de programación lineal en el que los asignados son recursos destinados a la realización de tareas. Por ejemplo, los asignados pueden ser empleados a quienes se tiene que dar trabajo. La asignación de personas a trabajos es una aplicación común del problema de asignación. Sin embargo, los asignados no tienen que ser personas. También, pueden ser maquinas, vehículos, plantas a los que se asignan tareas. Para que un problema se ajuste a la definición de problema de transporte se deben cumplir las siguientes suposiciones:

1) El número de asignados es igual al número de tareas. (este numero se denota por n).

2) Cada asignado se asigna a una tarea.

3) Cada tarea debe realizarla exactamente un asignado.

4) Existe un costo cij asociado con el asignado i ( i = 1,2...,n) que realiza la tarea j (j = 1,2...n).

5) El objetivo es determinar como deben hacerse las n asignaciones para minimizar los costos totales.

...