Teoria lineas de espera gy danchcz85 110R6pR I S, 2011 242 pagcs INVESTIGACIÓN OPERATIVA. Teoría, Ejercicios y Prácticas con Ordenador Rosa Rodríguez Huertas Antonio Gámez Mellado 10 de Septiembre de 2002 2 Indice General Introducción or242 to View nut*ge TEORÍA 13 13 14 16 16 17 18 19 20 25 26 28 32 33 33 38 394348 51 55 57 62 64 66 57 68 72 76 77 1 Introducción a la teoría de optimización 1 . 1 Orígenes y . 1. 1 Orígenes de la Investigación desarrollo .. operativa 1 . 1. 2 La Teoría de Juegos . 1. 3 La Programación Lineal . . 1. 1. 4 La Investigación . 1. 2 Modelización de un problema de P. L Operativa 1. 2. Formulación de los modelos . 1. 3 Modelización de diversos problemas de 1. 0.. 1. 4 Modelos de programación matemática 1. 5 El método geométrico 1. 5. 1 lineal . 2. 2 Nociones . 2. 3 Definiciones previas . sobre las soluciones de un problema . . 2. 4 Algunos resultados sobre las soluciones 2. 5 El algoritmo del Simplex . 2. 6 Algoritmo del Simplex en forma de tabla (max) . . 2. 7 Algoritmo del Simplex en forma de tabla (min) . . . 2. 8 Búsqueda de soluciones iniciales . 2. 8. 1 Método de las Penalizaciones . . 2. 9 Algoritmo del . 2. 9. 1 Método del Simplex en forma matricial Simplex en forma matricial (caso maximizante) . 2. 0 Adaptación algebraica del algoritmo del Simplex . 2. 10. 1 Algoritmo del Simplex (enfoque algebraico) . 2. 10. 2 Método del Simplex en forma de tabla (Usando zj —cj en la última fila) . 2. 11 Otros algoritmos de programación lineal 2. 11. 1 Método de las dos fases 4 ÍNDICE GENERAL 2. 11. 2 Algoritmo revisado del Simplex (Caso maximizante) 79 85 85 85 88 91 92 94 105 107 111 111 112 112 114116 116 117 118 119 119 124 127 127 128 129 129 129 130 132 134 137 137 141 143 144 14 242 112 112 114116 116 117 118 119 119 124 127 127 128 129 129 29 130 132 134 137 137 141 143 144 146 146 147 149 150 3 Dualidad en programación lineal 3. Formas de la . 3. 1 . 1 Forma canónica maximizante dualidad de la dualidad 3. 1 . 2 Forma estándar maximizante de la dualidad 3. 1. 3 Reglas para escribir el problema dual . . 3. 1. 4 Forma canónica minimizante de la dualidad 3. 2 Propiedades de la relación de dualidad . . 3. 3 Interpretación económica de la dualidad . . 3. 4 Algoritmo Dual del Simplex. (Caso 4 Análisis de sensibilidad 4. 1 Introducción gráfica . 4. 2 Cambios discretos . riación en un coste de una variable no básica n un coste de una coeficientes de coste .. 4. 5. Parametrización de los recursos 5 El problema de transporte 5. 1 Introducción.. 5. 2 planteamiento como un problema de programación lineal 5. 3 Problema no equilibrado . 5. 4 Propiedades del problema de transporte 5. 5 Determinación de una solución inicial . 5. 5. 1 Método de la esquina Noroeste 5. 5. 2 Método de costo mínimo . 5. 5. 3 Método de Vogel . 5. 6 Definición de Ciclo 5. 7 Algoritmo de transporte (forma minimizante) . . 5. 8 Soluciones degeneradas . 5. 9 Otras variaciones del problema de transporte . 5. 10 El problema e transbordo 5. 1 El problema de asignación . 5. 11. 1 El algoritmo Húngaro (Forma minimiza 2 Ejemplo de 4 242 aplicación del algoritmo H 2 Problema de . 5. 13 Problema de planificación de la producción ÍNDICE GENERAL 6 Modelos de Redes 6. 1 Redes. conceptos básicos . 6. 2 Caminos de longitud mínima 6. 3 Algoritmos de ordenación y de etiquetación 6. 4 Algoritmo de . 6. 5 Problema del flujo máximo Dijkstra . 6. 6 Algoritmo de Ford-Fulkerson , . 6. 6. 1 Flujo de un . 6. 6. 2 Algoritmo de Ford-Fulkerson .. 6. 7 CPM corte . 6. 7. 1 Algoritmo CPM Y PERT 6. 7. 2 El mét0d0 PERT . 55 155 157 158 161 163 165 165 166 169 171 173 177 177 178 178 179 180 181 183 185 185 188 189 242 7 Programación Entera 7. 1 Introducción . 7. 2 Algunos problemas de programación entera . 7. 2. 1 El problema de la mochila . 7. 2. 2 Problema del viajante 7. 2. 3 Problema de costo fijo . . 7. 3 El algoritmo de ramificación y acotación . 7. 3. 1 Resumen 7. 3. 2 Programación entera mixta 7. 4 Algoritmo de corte o de Gomory . 7. 4. 1 Resumen del algoritmo de Gomory . 7. 5 Programación 0-1 . Algoritmo de enumeración 8 Teoría de colas 195 8. 1 Introducción . 195 8. 1. 1 Costos de los sistemas de colas 97 8. . 2 Estructuras típicas. — 198 8. 2 Terminología 198 8. 2. 1 Características físicas .. . 198 8. 2. 2 Características de funcionalidad . 200 8. 2. 3 Parámetros de los sistemas de colas . . 201 8. 3 Modelos de llegadas y de tiempo de servicio . . 201 8. 3 Modelos de llegadas y de tiempo de .. 201 8. 3. 1 Relación entre la distribución servicio.. . de Poisson y la exponencial .. 203 8. 3. 2 Otra distribución de las llegadas. La distribución de Erlang . 204 8. 3. 3 Modelos de duración de los servicios . .. 205 8. 4 La notación de Kendall . 205 8. 5 Estudio de una cola WM/I . . 206 8. . 1 probabilidad de que el sistema esté en cierto estado . 206 8. 5. 2 Número medio de elementos en el sistema . . 209 8. 5. 3 Número medio de elementos en cola . . 209 8. 6 Teorema de Little . . 209 8. 7 Sistemas con capacidad limitada . 210 8. 8 Modelo con S semdores . 213 8. 8. 1 Cálculo de la probabilidad de los diferentes estados del sistema 213 6 8. 8. 2 8. 8. 3 8. 84 ÍNDICE GENERAL Cálculo de po Cálculo de los parámetros . . Sistemas de colas de tipo Expresiones para el caso de s servidores . . 8. 9 El coste de un sistema de colas … 214215215216219219220223 24 225 226 226 226 . 214215215216219219220223 224 225 226 226 226 229 229 230 233 240 9 Introducción a la Simulaclón 9. 1 Simulación. Generalidades . 9. 2 Un ejemplo muy sencillo 9. 3 Método Montecarlo…. ….. ….. ….. ….. .. . 9. 4 Notas históricas sobre el Método Montecarlo . 9. 5 Generación de números aleatorios . . 9. 5. 1 Propiedades de un buen generador de números aleatorios . 9. 5. 2 Método del centro del cuadrado. . 9. 5. 3 Método de las congruencias . . 9. 6 Método de la transformación inversa 9. 6. 1 Método de la transformación inversa aplicado a la distribución xponencial 9. Simulación de una cola M/M/I . . 9. 7. 1 Programa FORTRAN . 9. 8 Integración Montecarlo. Método de éxito-fracaso . 9. 9 Ejemplos de programas de simulación EJERCICIOS 249 1 Introducción a la optimización 251 1. 1 Ejercicios Resueltos . . 251 1. 2 Ejercicios Propuestos 8 242 2511 . 2 Ejercicios 266 1. 3 Soluciones de . 275 2 Programación los Ejercicios Propuestos lineal 283 2. 1 Ejercicios Resueltos . 283 2. 2 Ejercicios Propuestos . 305 2. 3 Soluciones de los Ejercicios Propuestos . 310 3 Dualidad en programación lineal 315 3. 1 Ejercicios Resueltos 315 3. Ejercicios Propuestos . 30 3. 3 Soluciones de los Ejercicios Propuestos . 332 4 Análisis de sensibilidad 335 4. 1 Ejercicios Resueltos. . . 335 4. 2 Ejercicios . 362 4. 3 Soluciones de propuestos los Ejercicios Propuestos . 367 ÍNDICE GENERAL 7 5 El Problema de transporte 371 5. 1 Ejercicios . 371 5. 2 Ejercicios . 383 5. 3 Soluciones de los Ejercicios Propuestos • .. 388 6 Problemas de redes 391 6. 1 Ejercicios Resueltos g 242 . 388 6 Problemas de redes 391 6. 1 Ejercicios 391 6. 2 EjerciCi0S . 396 6. 3 Soluclones de los Ejercicios propuestos 401 7 Programación entera 403 7. Ejercicios . 03 7. 2 Ejercicios .. 414 7. 3 soluciones de los Ejercicios Propuestos . . . 4168 Teoría de colas 419 8. 1 Ejercicios Resueltos…. ….. ….. ….. ….. .. 419 8. 2 Ejercicios Propuestos . 424 8. 3 Soluciones de los Ejercicios Propuestos . 426 9 Introducción a la Simulación 427 9. 1 Ejercicios resueltos . . 427 9. 2 .. 428 PRÁCTICAS CON ORDENADOR 431 1 Programación lineal 1 433 1. 1 problema de programación . 433 1. 2 Análisis de lineal con LINGO sensibilidad con LINGO . 436 1. 3 Otros problemas . . 437 2 Programación lineal II 2. 1 Comandos de salida de ficheros .
