Investigación de Operaciones Temas desarrollados 1 y 2 para estudio. PDF

Preview

Summary

Temas desarrollados de las unidades 1 y 2 de la materia de investigacion de operaciones del semestre 1...

Description

NOMBRE LA ASIGNATURA: INVESTIGACION DE LAS OPERACIONES I HORA: 3-4 TEMA: TEMAS IO 1 Y IO2 TERCER SEMESTRE GRUPO: B

NOMBRE DEL DOCENTE: SANDRA LUZ CARREON YAÑEZ ALUMNO: URIEL LANDAVERDE VILLASANA

Definición de investigación de operaciones: El propósito de la Investigación de Operaciones consiste en preparar al profesional para decidir entre diferentes medios o métodos disponibles para alcanzar un objetivo propuesto, de modo que se alcance un resultado en relación a determinados criterios de optimización.

Temas de la investigación de operaciones 1: 1. Introducción a la Investigación de Operaciones. 1.1 Conceptos y definiciones de la investigación de operaciones. La Investigación de Operaciones se ocupa de la toma de decisiones óptima a partir del modelado y solución de sistemas determinísticos y probabilísticos que se originan en la vida real. Estas aplicaciones que ocurren en el gobierno, en los negocios, en las industrias, en la ingeniería económica y en las ciencias naturales y sociales se caracterizan en gran parte por la necesidad de asignar escasos recursos. En estas situaciones se puede obtener un conocimiento profundo del problema a partir del análisis científico que proporciona la Investigación de Operaciones. El enfoque de la Investigación de Operaciones proviene principalmente de la estructuración, el análisis y desarrollo. 1.2 Fases de estudio de la investigación de operaciones. Las fases de estudio de la I.O son las siguientes:  Definición del problema  Construcción del modelo  Solución del modelo  Validación del modelo  Implantación de los resultados finales 1.3 Principales aplicaciones de la investigación de operaciones. 1. Optimización de las operaciones de producción para cumplir con la finalidad de un costo mínimo. 2. La optimización del corte de árboles en productos de madera maximizando su producción.

3. Asignación optima de recursos hidráulicos térmicos en el sistema nacional de generación de energía. 4. Programación de turnos de trabajo en oficinas de reservaciones y aeropuertos para cumplir con las necesidades del cliente.

1.4 Formulación de modelos de programación lineal. El problema de la Wyndor Glass Co. se diseñó para ilustrar un problema común de programación lineal, en versión simplificada. Sin embargo, esta técnica es muy versátil como para describirla mediante un solo ejemplo. En esta sección se presentarán las características generales de los problemas de programación lineal y las distintas formas legítimas del modelo matemático. 2. El Método Simplex. 2.1. Método gráfico. El método grafico se utiliza para la solución de problemas de PL, representando geométricamente a las restricciones, condiciones técnicas y el objetivo. El modelo se puede resolver en forma geométrica si solo se tiene 2 variables. Para modelos con 3 o más variables el método grafico es impráctico o imposible. Cuando los ejes son relacionados con las variables del problema, el método es llamado método grafico en actividad.

2.2. Método simplex. El Método Simplex es un procedimiento iterativo el cual permite mejorar la solución a cada paso. Este proceso concluye cuando no es posible seguir mejorando la solución. Este método se puede considerar como un método algebraico para resolver problemas de programación lineal el cual involucra dos o más variables. El Método Simplex fue creado en el año de 1947. Su primera aplicación fue después del verano de 1947 cuando se resolvió un problema de programación de 9 restricciones y 27. 2.3. Procedimiento para resolver problemas con variables artificiales (M grande, doble fase). Este método es sencillo y laborioso y se usa ante la presencia de numerosas variables. En este método se considerará la primera fase de la siguiente forma: se reemplaza la función objetivo de la programación lineal por la minimización de las sumas de las variables artificiales encontradas y resolviéndose la minimización. En la segunda fase se inicia con una tabla terminando la primera fase y se retoma la

función objetivo en donde todas las variables artificiales se igualan a cero eliminando las restricciones de holgura. 2.4. Casos especiales de programación lineal. En la resolución de un modelo de Programación Lineal se pueden enfrentar ciertos casos especiales que merecen particular atención. Estos casos (infinitas soluciones óptimas, problema no acotado sin solución óptima, problema infectable, solución óptima degenerada) se pueden detectar a través de la aplicación del Método Simplex según hemos tratado previamente en el Blog. A continuación, un resumen de dichos escenarios:

2.5. Método dual simplex. La solución de un problema dual permite obtener interesantes resultados, relativo al análisis de sensibilidad de los términos independientes. Más concretamente, para los rangos de los términos independientes para los que se mantiene la base óptima, la solución dual nos permite conocer el precio sombra de la restricción, que será la variación de la función objetivo por unidad incrementada del término independiente de la restricción. 2.6. Relaciones primal dual. El modelo dual de un problema de Programación Lineal consiste en una instancia alternativa de modelamiento matemático que nos permite rescatar la información del problema original conocido comúnmente como modelo primal. En consecuencia, es suficiente con resolver uno de ellos (primal o dual) para poder obtener la solución óptima y valor óptimo del problema equivalente (primal o dual según sea el caso). Para ello se puede utilizar, por ejemplo, las condiciones establecidas en el Teorema de Holguras Complementarias. 2.7. Análisis de sensibilidad e interpretación de resultados. El análisis de sensibilidad o postoptimal para los modelos de Programación Lineal, tiene por objetivo identificar el impacto que resulta en los resultados del problema original luego de determinadas variaciones en los parámetros, variables o restricciones del modelo, sin que esto pase por resolver el problema nuevamente. Es decir, ya sea si resolvemos nuestro modelo gráficamente o utilizando el Método Simplex, lo que se busca es que estas variaciones o sensibilidad hagan uso de la solución y valor óptimo actual, sin tener la necesidad de resolver para cada variación un nuevo problema. En especial nos concentraremos en el análisis de sensibilidad o postoptimal que hace uso de la tabla final del Método Simplex.

2.8. Uso de software. En la práctica, los algoritmos son ejecutados en paquetes de software comercial; por ello, es importante familiarizar al estudiante con la naturaleza de los programas que utilizará en la vida profesional. El OR Courseware incluye una gran cantidad de material para introducir los tres paquetes de mayor uso, descritos a continuación. Juntos, estos paquetes permiten resolver con gran eficiencia casi todos los modelos de IO que se presentan en este libro. Además, se agregan ciertas rutinas automáticas propias del OR Courseware sólo para algunos casos en los que estos paquetes no son aplicables. 3. Programación Entera. 3.1. Introducción y casos de aplicación. Sus pioneros fueron Wagner (1950) y Manne (1959). Tradicionalmente estos modelos se han considerado como subclases de la programación lineal, sin embargo, las variables de decisión que aparecen en ellos sólo toman valores enteros, por lo que realmente deben considerarse como problemas de programación entera. El número de modelos lineales enteros y sus métodos de solución es en la actualidad bastante extenso, lo que nos ha llevado a hacer una selección considerando aquellos que creemos más interesantes y que aparecen con mayor frecuencia en la realidad. No siempre es admisible que las variables de un PL tomen valores continuos, existen: • Decisiones dicotómicas (si-no) • Decisiones que deben tomarse en unidades discretas 3.2. Definición y modelos de programación entera. Un modelo de programación entera es aquel que contiene restricciones y una función objetivo idénticas a las formuladas en programación lineal, la única diferencia en que una o más variables de decisión deben tomar valor entero en la solución final. Los modelos de programación entera son una extensión de los modelos lineales en los que algunas variables toman valores enteros. Con frecuencia las variables enteras sólo toman valores en 0-1, ya que este tipo de variables permiten representar condiciones lógicas 3.3. Método gráfico de programación entera. El Método Gráfico (resolución gráfica) constituye una excelente alternativa de representación y resolución de modelos de Programación Lineal que tienen 2 variables de decisión. Para estos efectos existen herramientas computacionales que facilitan la aplicación del método gráfico como los softwares TORA, IORTutorial y Geogebra, los cuales se pueden consultar en detalle en Cómo Resolver Gráficamente un Modelo de Programación Lineal con

TORA, Cómo Resolver Gráficamente un Modelo de Programación Lineal con IORTutorial y Cómo Resolver Gráficamente un modelo de Programación Lineal con Geogebra, respectivamente. En este contexto a continuación presentamos un compendio de ejercicios de Programación Lineal resueltos a través del método gráfico. 3.4. Método de ramificación y acotación. Consiste en una enumeración en árbol en el cual el espacio de las variables enteras se divide de forma sucesiva dando lugar a problemas lineales que se resuelven en cada nodo del árbol. Estos problemas lineales se obtienen relajando las restricciones de integralidad y añadiendo restricciones adicionales. El procedimiento de ramificación y acotación establece inicialmente una cota inferior y una cota superior del valor óptimo de la función objetivo. El mecanismo de ramificación aumenta progresivamente el valor de la cota inferior y disminuye progresivamente el valor de la cota superior. La diferencia entre estas dos cotas es una medida de la proximidad del punto actual a la solución óptima, si ésta existe. 3.5. Método heurístico para problemas binarios. Se basa en la utilización de reglas empíricas para llegar a una solución. El método heurístico conocido como “IDEAL”, formulado por Bransford y Stein (1984), incluye cinco pasos: Identificar el problema; definir y presentar el problema; explorar las estrategias viables; avanzar en las estrategias; y lograr la solución y volver para evaluar los efectos de las actividades (Bransford & Stein, 1984). El matemático Polya (1957) también formuló un método heurístico para resolver problemas que se aproxima mucho al ciclo utilizado para programar computadores. A lo largo de este curso se utilizará este método propuesto por Polya. Según Polya (1957), cuando se resuelven problemas, intervienen cuatro operaciones mentales: 1. Entender el problema 2. Trazar un plan 3. Ejecutar el plan (resolver) 4. Revisar Numerosos autores de textos escolares de matemáticas hacen referencia a estas cuatro etapas planteadas por Polya. 4. Transporte y Asignación 4.1. Definición del problema de transporte. La manera más fácil de reconocer un problema de transporte es por su naturaleza o estructura "de - hacia": de un origen hacia un destino, de una fuente hacia un usuario, del presente hacia el futuro, de aquí hacia allá. Al enfrentar este tipo de problema, la intuición dice que debe haber una manera de obtener una solución. Se conocen las fuentes y los destinos, las capacidades y demandas y los costos

de cada trayectoria. Debe haber una combinación óptima que minimice el costo (o maximice la ganancia). La dificultad estriba en el gran número de combinaciones posibles. 4.2. Algoritmo de transporte. El algoritmo de transporte organiza los cálculos en una forma más cómoda aprovechando la ventaja de la estructura especial del modelo de transporte. Pare esto sigue los mismos pasos que el método simplex, sin embargo, en lugar de usar la tabla simplex normal se aprovecha la ventaja de la estructura especial del modelo de transporte para organizar los cálculos en una forma más cómoda. Se debe agregar que el algoritmo especial de transporte fue desarrollado por primera vez cuando la norma eran los cálculos a mano y se necesitaba de soluciones con método abreviado. el algoritmo de transporte se basa en la hipótesis que el modelo esta balanceado y eso quiere decir que la demanda total es igual a la oferta total. Si el modelo está desbalanceado siempre se podrá aumentar con una fuente ficticia o destino ficticio para restaurar el equilibrio o balance. Los pasos del algoritmo de transporte son exactamente iguales a los del algoritmo simplex 4.3. Método de la Esquina Noroeste. Pasos a seguir para el desarrollo de este método: 1. Asignar a la tabla de costos oferta y demanda la asignación a cada una de las casillas desde la parte superior izquierda hacia la derecha y hacia debajo de dicha tabla. 2. Analizar cada una de las casillas desocupados hacia la derecha o hacia la izquierda asignando valores ±. 3. Este método terminará si todas las casillas desocupadas son con signo positivo. 4. Si existieran casillas con valores negativos se realizará una nueva tabla iniciando la asignación a la casilla más negativa. Esta asignación será el valor que se encuentre más cerca del origen.

4.4. Método de Costo Mínimo. El método del costo mínimo determina una mejor solución inicial al concentrarse en las rutas más económicas. Asigna lo más posible a la celda con el costo unitario mínimo (los empates se rompen arbitrariamente). Luego se tacha la fila o columna satisfecha y se ajustan las cantidades de oferta y demanda como corresponda. 4.5. Método de aproximación de Vogel. Este método es una versión mejorada del método del costo mínimo que por lo general, pero no siempre, produce mejores soluciones iniciales.

Paso 1. Para cada fila (columna) determine una medida de penalización restando el elemento de costo unitario mínimo en la fila (columna) del siguiente elemento de costo mínimo en la misma fila (columna). Paso 2. Identifique la fila o columna con la penalización máxima, que rompa los empates arbitrariamente. Asigne lo más posible a la variable con el costo unitario mínimo en la fila o columna seleccionada. Ajuste la oferta y la demanda, y tache la fila o columna satisfecha. Si una fila y una columna se satisfacen al mismo tiempo, sólo se tacha una de las dos, y a la fila restante (columna) se le asigna una oferta (demanda) cero. 4.6. Definición del problema de asignación. El problema de asignación es un tipo especial de problema de programación lineal en el que los asignados son recursos que se destinan 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.10 Sin embargo, los asignados no tienen que ser personas. También pueden ser máquinas, vehículos o plantas, o incluso periodos a los que se asignan tareas. 4.7. El método húngaro. El método húngaro es un algoritmo que permite minimizar los costos en un problema de optimización basado en la programación lineal. El objetivo del método húngaro es encontrar el coste mínimo de un conjunto de tareas que deben ser realizadas por las personas más adecuadas. Utiliza la programación lineal (PL) para realizar una serie de pasos que se pueden automatizar. Así, herramientas como el software estadístico R (entre otros) tiene varios paquetes de mucha utilidad para estos problemas de optimización.

Temas de la investigación de operaciones 2: 1. Programación por metas. 1.1 Definición y conceptos generales. La Programación de Metas o Programación por objetivos es un enfoque que permite abordar problemas de decisión general respecto a las metas que se deseen alcanzar en algún ámbito de la vida cotidiana. Estas metas pueden ser complementarias, pero frecuentemente conflictivas. Por ello, una forma de arreglar esta inconmensurabilidad se basa en una estructura prioritaria por parte de la administración. 1.2 Modelo general de metas. Es un enfoque para tratar problemas de decisión gerencial que comprenden metas múltiples o ilimitadas, de acuerdo a la importancia que se les asigne a estas metas. El tomador de decisiones debe ser capaz de establecer al menos una importancia ordinal, para clasificar estas metas. META: Valor objetivo numérico específico establecido para un fin en un programa de metas. PROGRAMACIÓN DE METAS: Planteamiento utilizado para resolver un problema de optimización de objetivos múltiples. 1.3 Diferencias entre modelo lineal y modelo metas. Modelo de programación meta-lineal Las suposiciones básicas que caracterizan el modelo de programación lineal se aplican igualmente al modelo de programación meta. La diferencia principal en la estructura es que la programación meta no intenta minimizar o maximizar la función objetivo como lo hace el modelo de programación lineal, en vez busca minimizar las desviaciones entre las metas deseadas y los resultados reales de acuerdo a las prioridades asignadas. 1.4 Modelos de una sola meta. Modelos de una sola meta. - Es similar al modelo de Programación Lineal. El Primer paso es definir las variables de decisión, después se deben de especificar todas las metas gerenciales en orden de prioridad. Una característica de la Programación de Meta es que proporciona solución para los problemas que tengan metas múltiples y conflictivas arregladas de acuerdo con la estructura prioritaria de la administración.

1.5 Modelos de metas múltiples. La Programación por Metas (Goal Programming) fue inicialmente introducida por Charnes y Cooper en los años 50. Desarrollada en los años 70 por Ljiri, Lee, Ignizio y Romero, es actualmente uno de los enfoques multicriterio que más se utilizan. En principio fue dirigida a resolver problemas industriales, sin embargo, posteriormente se ha extendido a muchos otros campos como la economía, agricultura, recursos ambientales, recursos pesqueros, etc. Resulta de gran interés, sobre todo, en problemas complejos de gran tamaño. 1.6 Modelos de sub metas dentro de una meta. Es un modelo que optimiza ya sean determinísticos, inductivos o deductivos, considerando una sola función objetivo y un solo propósito es decir una sola meta. Dado que este modelo es de una sola meta, se puede minimizar costos, tiempos o también maximizar utilidades. Dependiendo del problema y la meta en sí, se podrá tener interés en minimizar la deviación positiva, la negativa o ambas. 2. Optimización de redes. 2.1. Terminología. La mayor parte de los modelos de optimización de redes son casos particulares de modelos de programación lineal y pueden ser formalizados a partir del modelo de Flujo de Costo Mínimo, estos modelos se aplican en la administración de problemas de transporte, logística, comunicación y seguimiento de proyectos de finanzas, recursos humanos o mercadeo. En algunos problemas de optimización puede ser útil representar el problema a través de una gráfica, para entender los modelos de redes se utiliza una terminología apropiada que se muestra a continuación, esta terminología no está estandarizada ni lo estará pues un concepto se puede describir de diferentes maneras 2.2. Problema de la ruta más corta. Los problemas conocidos como problemas del camino mínimo o camino más corto, tratan como su nombre indica de hallar la ruta mínima o más corta entre dos puntos. Este mínimo puede ser la distancia entre los puntos origen y destino o bien el tiempo transcurrido para trasladarse desde un punto a otro. Se aplica mucho para problemas de redes de comunicaciones.

Este tipo de problemas pueden ser resueltos por el método del Simplex, sin embargo, existen otros métodos más eficientes como por ejemplo el algoritmo de Dijkstra o el de Bellman-Ford.

2.3. Problema de árbol de mínima expansión. Árbol: Es un grafo en el que existe un único nodo desde el que se puede acceder a todos los demás y cada nodo tiene un único predecesor, excepto el primero, que no tiene ninguno. También podemos definir un árbol como: 

  

Un grafo conexo y sin ciclos. -Un grafo sin ciclos y con n-1 aristas, siendo n el número de vértices. -Grado de un nodo en un árbol es el número de subárboles de aquel nodo (en el ejemplo, el grado de v1 es 2 y de v2 1). Denominamos hojas en un árbol a los nodos finales (v3, v5 y v6). Un árbol de máximo alcance es aquel que ...