Investigación de operaciones : una introducción /
Hamdy A. Taha.
- 6ta. [i.e. en inglés, 1ra. en español]
- México: Prentice Hall, 1997
- 916 p.
Incluye diskette, nº inv. RE0280
CONTENIDO CAPITULO 1: PERSPECTIVA GENERAL DE LA INVESTIGACION DE OPERACIONES 1 1.1 Modelos matemáticos de investigación de operaciones 1 1.2 Técnicas de investigación de operaciones 3 1.3 Modelado de simulación 4 1.4 El arte del modelado 5 1.5 Acerca de este libro 6 Bibliografía 7 Parte 1: Modelos determinísticos 9 CAPITULO 2: INTRODUCCION A LA PROGRAMACION 11 2.1 Introducción 11 2.2 Construcción del modelo de PL 11 2.3 Solución gráfica de PL 14 2.3.1 Solución de un modelo de maximización 15 2.3.2 Solución de un modelo de minimización 18 2.3.3 Variables de holgura, de superávit y no restringidas 20 2.4 Análisis gráfico de sensibilidad 22 2.4.1 Cambios en los coeficientes de la función objetivo 23 2.4.2 Valor unitario de un recurso 27 2.5 Solución por computadora de problemas de PL 33 2.6 Análisis de modelos seleccionados de PL 39 2.7 Resumen 62 Bibliografía 62 Problemas integrales 62 CAPITULO 3: EL METODO SIMPLEX 67 3.1 Introducción 67 3.2 Forma estándar de PL y sus soluciones básicas 67 3.2.1 Forma estándar de PL 67 3.2.2 Determinación de soluciones básicas 70 3.2.3 Variables no restringidas y soluciones básicas 72 3.3 El algoritmo símplex 74 3.4 Solución inicial artificial 86 3.4.1 El método de la M 86 3.4.2 El método de dos fases 92 3.5 Casos especiales en la aplicación del método símplex 97 3.5.1 Degeneración 97 3.5.2 Óptimos alternativos 101 3.5.3 Soluciones no acotadas 103 3.5.4 Solución no factible 106 3.6 Resumen 108 Bibliografía 108 Problemas integrales 108 CAPITULO 4: ANALISIS DE DUALIDAD Y DE SENSIBILIDAD 111 4.1 Introducción 111 4.2 Definición del problema dual 111 4.3 Relación entre las soluciones óptimas primal y dual 117 4.4 Interpretación económica de la dualidad 122 4.4.1 Interpretación económica de las variables duales 123 4.4.2 Interpretación económica de las restricciones duales 125 4.5 Método dual símplex 128 4.6 Cálculos primales-duales 135 4.7 Análisis postóptimo o de sensibilidad 143 4.7.1 Cambios que afectan la factibilidad 144 4.7.2 Cambios que afectan la optimalidad 155 4.8 Resumen 161 Bibliografía 161 Problemas integrales 162 CAPITULO 5: MODELO DE TRANSPORTE Y SUS VARIANTES 165 5.1 Definición del modelo de transporte 165 5.2 Modelos de transporte no tradicionales 174 5.3 El algoritmo de transporte 179 5.3.1 Determinación de la solución inicial 181 5.3.2 Cálculos iterativos del algoritmo 185 5.3.3 Explicación del método símplex sobre el método de multiplicadores 193 5.4 El modelo de asignación 194 5.4.1 El método húngaro 195 5.4.2 Explicación símplex del método húngaro 201 5.5 El modelo de transbordo 202 5.6 Resumen 207 Bibliografía 208 Problemas integrales 208 CAPITULO 6: MODELOS DE REDES 215 6.1 Alcance de las aplicaciones de redes 215 6.2 Definiciones de red 216 6.3 Algoritmo de árbol de expansión mínima 218 6.4 Problema de la ruta más corta 222 6.4.1 Ejemplos de aplicaciones de la ruta más corta 222 6.4.2 Algoritmos de la ruta más corta 227 6.5 Modelo del flujo máximo 237 6.5.1 Enumeración de cortes 238 6.5.2 Algoritmo del flujo máximo 239 6.6 Problema del flujo restringido de costo mínimo 248 6.6.1 Representación de la red 248 6.6.2 Formulación de programación lineal 250 6.6.3 Algoritmo símplex de redes restringidas 256 6.7 CPM y PERT 263 6.7.1 Representación de la red 263 6.7.2 Cálculo de la ruta crítica 270 6.7.3 Construcción del programa de tiempo 274 6.8 Resumen 278 Bibliografía 278 Problemas integrales 278 CAPITULO 7: PROGRAMACION LINEAL AVANZADA 281 7.1 Introducción 281 7.2 Vectores y bases 281 7.2.1 PL estándar en forma matricial 281 7.2.2 Representación vectorial de una base 284 7.2.3 Soluciones básicas 285 7.3 Pruebas de validez del método símplex 287 7.3.1 Definición de conjuntos convexos 287 7.3.2 Optimalidad del algoritmo símplex 288 7.4 Tabla símplex generalizada en forma matricial 291 7.5 Algoritmos de cálculo eficientes 297 7.5.1 Método símplex revisado 297 7.5.2 Algoritmo de variables acotadas 305 7.5.3 Algoritmo de descomposición 313 7.6 Dualidad 323 7.6.1 Definición matricial del problema dual 324 7.6.2 Solución óptima dual 324 7.7 Programación lineal paramétrica 329 7.7.1 Cambios paramétricos en C 330 7.7.2 Cambios paramétricos en b 333 7.8 Algoritmo de punto interior de Karmarkar 336 7.8.1 Idea básica del algoritmo de punto interior 336 7.8.2 Algoritmo de punto interior 338 7.9 Resumen 346 Bibliografía 346 Problemas integrales 346 CAPITULO 8: PROGRAMACION DE METAS 349 8.1 Objetivo individual versus metas múltiples 349 8.2 Una formulación de programación de metas 349 8.3 Algoritmos de programación de metas 354 8.3.1 El método de ponderación 355 8.3.2 El método por preferencias 356 8.4 Resumen 363 Bibliografía 363 Problemas integrales 363 CAPITULO 9: PROGRAMACION LINEAL ENTERA 367 9.1 Introducción 367 9.2 Aplicaciones ilustrativas 367 9.3 Algoritmos de solución de la programación entera 384 9.3.1 Algoritmo de ramificación y acotamiento (RyA) 385 9.3.2 Algoritmo de enumeración implícita cero-uno 391 9.3.3 Algoritmo del plano cortante 398 9.4 Resumen 404 Bibliografía 405 Problemas integrales 405 CAPITULO 10: PROGRAMACION DINAMICA DETERMINISTICA 409 10.1 Introducción 409 10.2 Naturaleza re cursiva de los cálculos en la PD 409 10.3 Recursión hacia adelante y hacia atrás 413 10.4 Aplicaciones selectas de PD 414 10.4.1 Modelo de volumen-carga 415 10.4.2 Modelo del número de empleados 421 10.4.3 Modelo de reemplazo de equipo 425 10.4.4 Modelo de inversión 429 10.4.5 Modelos de inventario 433 10.5 Problema de dimensionalidad 433 10.6 Resumen 436 Bibliografía 436 Problema integral 436 CAPITULO 11: MODELOS INVENTARIOS DETERMINISTICOS 439 11.1 Introducción 439 11.2 Modelo de inventario general 439 11.3 Modelos estáticos de lote económico (EOQ) 440 11.3.1 Modelo EOQ clásico 440 11.3.2 EOQ con descuentos por cantidad 445 11.3.3 EOQ de artículos múltiples con límite de almacenamiento 449 11.4 Modelos dinámicos de lote económico EOQ 452 11.4.1 Modelo sin costo de preparación 454 11.4.2 Modelo con costo de preparación 459 11.5 Resumen 471 Bibliografía 471 Problemas integrales 471 Parte II: Modelos probabilísticos 475 CAPITULO 12: REVISION DE PROBABILIDAD BASICA 477 12.1 Introducción 477 12.2 Leyes de probabilidad 477 12.2.1 Ley de suma de probabilidades 478 12.2.2 Ley de la probabilidad condicional 479 12.3 Variables aleatorias y distribuciones de probabilidad 481 12.4 Esperanza de una variable aleatoria 483 12.4.1 Media y varianza de una variable aleatoria 484 12.4.2 Media y varianza de variables aleatorias conjuntas 486 12.5 Cuatro distribuciones de probabilidad comunes 489 12.5.1 Distribución binomial 489 12.5.2 Distribución Poisson 491 12.5.3 Distribución exponencial negativa 492 12.5.4 Distribución normal 493 12.6 Distribuciones empíricas 496 12.7 Resumen 503 Bibliografía 503 CAPITULO 13: MODELOS DE PRONOSTICOS 505 13.1 Introducción 505 13.2 Técnica del promedio móvil 505 13.3 Suavización exponencial 510 13.4 Regresión 512 13.5 Resumen 517 Bibliografía 517 Problema integral 517 CAPITULO 14: ANALISIS DE DECISION Y JUEGOS 519 14.1 Ambientes de decisión 519 14.2 Toma de decisiones bajo una certidumbre 519 14.2.1 Método analítico de jerarquía 520 14.3 Toma de decisiones bajo riesgo 530 14.3.1 Criterio del valor esperado 531 14.3.2 Variaciones del criterio del valor esperado 539 14.4 Decisión bajo incertidumbre 548 14.5 Teoría de juegos 554 14.5.1 Solución óptima a juegos de suma cero entre dos personas 555 14.5.2 Solución de juegos de estrategias mezcladas 559 14.6 Resumen 567 Bibliografía 567 Problemas integrales 567 CAPITULO 15: PROGRAMACION DINAMICA PROBABILISTICA 571 15.1 Introducción 571 15.2 Juego de azar 571 15.3 Problema de inversión 575 15.4 Maximización del evento de lograr una meta 580 Bibliografía 584 Problemas integrales 584 CAPITULO 16: MODELOS DE INVENTARIAS PROBABILISTICOS 585 16.1 Introducción 585 16.2 Modelos de revisión continua 585 16.2.1 Modelo EOQ "probabilizado" 585 16.2.2 Modelo EOQ probabilístico 588 16.3 Modelos de un solo periodo 592 16.3.1 Modelo sin costo de preparación 593 16.3.2 Modelo con costo de preparación (política s-S) 597 16.4 Modelo de periodos múltiples 600 16.5 Resumen 603 Bibliografía 603 Problemas integrales 603 CAPITULO 17: SISTEMAS DE COLAS 607 17.1 ¿Por qué estudiar las colas? 607 17.2 Elementos de un modelo de colas 609 17.3 Papel de la distribución exponencial 610 17.3.1 Propiedad de olvido 611 17.3.2 Derivación de la distribución exponencial 612 17.4 Modelos de nacimiento y muerte puros (relación entre las distribuciones exponencial y de Poisson) 615 17.4.1 Modelo de nacimiento puro 615 17.4.2 Modelo de muerte pura 619 17.5 Modelo de colas de Poisson generalizado 621 17.6 Colas especializadas de Poisson 627 17.6.1 Medidas de rendimiento de estado estable 628 17.6.2 Modelos de un solo servidor 632 17.6.3 Modelos de servidores múltiples 642 17.6.4 Modelo de servicio de máquinas-(M/M/R):(GD/K/K) 652 17.7 (M/G/1):(GD/infinito/infinito) - Fórmula de Pollaczek Khintchine (P-K) 656 17.8 Otros modelos de colas 658 17.9 Modelos de decisión de colas 659 17.9.1 Modelos de costos 659 17.9.2 Modelo de nivel de aspiración 665 17.10 Resumen 667 Bibliografía 667 Problemas integrales 667 CAPITULO 18: MODELADOR POR SIMULACION 673 18.1 ¿Qué es la simulación? 673 18.2 Simulación Monte Carlo 674 18.3 Tipos de simulación 679 18.4 Elementos de simulación de eventos discretos 680 18.4.1 Definición genérica de eventos 680 18.4.2 Muestreo a partir de distribuciones de probabilidad 682 18.5 Generación de números aleatorios 692 18.6 Mecánica de la simulación discreta 693 18.7 Métodos para reunir observaciones estadísticas 699 18.7.1 Método del subintervalo 700 18.7.2 Método de replicación 702 18.7.3 Método (ciclo) regenerativo 702 18.8 Lenguajes de simulación 705 18.9 Resumen 709 Bibliografía 709 CAPITULO 19: PROCESO DE DECISION MARKOVIANO 711 19.1 Alcance del problema de decisión Markoviano: el ejemplo del jardinero 711 19.2 Modelo de programación dinámica de etapas finitas 713 19.3 Modelo de etapas infinitas 718 19.3.1 Método de enumeración exhaustiva 719 19.3.2 Método de iteración de política sin descuentos 722 19.3.3 Método de iteración de política con descuentos 726 19.4 Solución por programación lineal 729 19.5 Resumen 733 19.6 Apéndice: revisión de las cadenas Markov 733 19.6.1 Procesos de Markov 734 19.6.2 Cadenas de Markov 734 Bibliografía 741 Parte III: Modelos no lineales 743 CAPITULO 20: TEORIA DE OPTIMIZACION CLASICA 745 20.1 Introducción 745 20.2 Problemas no restringidos 745 20.2.1 Condiciones necesarias y suficientes 746 20.2.2 El método Newton-Raphson 751 20.3 Problemas con restricciones 753 20.3.1 Restricciones de igualdad 753 20.3.2 Restricciones de desigualdad 771 20.4 Resumen 779 Bibliografía 779 CAPITULO 21: ALGORITMOS DE PROGRAMACION NO LINEAL 781 21.1 Algoritmos sin restricciones 781 21.1.1 Método de búsqueda directa 781 21.1.2 Método del gradiente 783 21.2 Algoritmos con restricciones 787 21.2.1 Programación separable 787 21.2.2 Programación cuadrática 797 21.2.3 Programación geométrica 801 21.2.4 Programación estocástica 807 21.2.5 Método de combinaciones lineales 811 21.2.6 Algoritmo SUMT 813 21.3 Resumen 814 Bibliografía 814 APENDICE A: REVISION DE VECTORES Y MATRICES 815 A.1 Vectores 815 A.1.1. Definición de un vector 815 A.1.2 Suma (resta) de vectores 815 A.1.3 Multiplicación de vectores por escalares 816 A.1.4 Vectores linealmente independientes 816 A.2 Matrices 816 A.2.1 Definición de una matriz 816 A.2.2 Tipos de matrices 816 A.2.3 Operaciones aritméticas con matrices 817 A.2.4 Determinante de una matriz cuadrada 819 A.2.5 Matriz no singular 820 A.2.6 Inversa de una matriz 821 A.2.7 Métodos para calcular la inversa de una matriz 822 A.3 Formas cuadráticas 825 AA Funciones convexas y cóncavas 826 Bibliografía 826 Problemas 826 APENDICE B: INTRODUCCION A SIMNET II 829 B.1 Estructura del modelado 829 B.2 Representación de proposiciones 830 B.2.1 Nodo fuente 830 B.2.2 Nodo de la cola 832 B.2.3 Nodo de instalación 833 B.2.4 Nodo auxiliar 835 B.2.5 Reglas básicas para la operación de nodos 836 B.3 Expresiones matemáticas de SIMNET II 838 B.4 Ejemplo del modelo SIMNET II 840 B.5 Rutas de transacción en SIMNET II 842 B.5.1 Selección de ruta 843 B.5.2 Rutas GOTO (campo *T) 845 B.6 Ramas en SIMNET II 847 B.7 Variables estadísticas 853 B.8 Conmutadores lógicos 855 B.9 Comandos especiales 858 B.9.1 Activación y desactivación de una fuente 859 B.9.2 Recopilación de variables estadísticas 859 B.9.3 Comandos para la manipulación de archivos 860 B.10 Datos iniciales 865 B.10.1 Entradas del archivo inicial 865 B.10.2 Funciones de densidad continua, discretas y discretizadas 866 B.10.3 Funciones tipo tabla 867 B.10.4 Inicialización de elementos de arreglos 868 B.11 Resumen 870 Bibliografía 870