Vistenos en:www.pearsoneducacion.net
ISBN 978-607-32-0796-6
HAMDY A. TAHA
40
Novena edicin
HAMDY A. TAHA
Novena edicin
INVESTIGACINDE OPERACIONES
Novenaedicin
Co
n AMP
L, S
olver,
Exce
l,
e im
pleme
ntacio
nes T
ORA
TAHA
Esta novena edicin del reconocido libro de Taha contiene, de manera ms concisa que las anteriores, tanto el texto como el software de apoyo, con el fin de que el lector se enfoque de lleno en la puesta en ejecucin algortmica y prctica de las tcnicas de investigacin de operaciones.
El libro recalca que, si bien el modelado matemtico es la piedra angular de la IO, en la decisin final se deben tomar en cuenta factores incuantificables, como el comportamiento humano; asimismo, hace hincapi en que la definicin correcta de los problemas es la fase ms importante y ms difcil de la IO. Por ltimo, la obra presenta varias aplicaciones que utilizan ejemplos resueltos y problemas especficos.
Novedades en esta edicin: La nueva seccin 3.7 ofrece un marco de trabajo (sin necesidad de utilizar matemticas) sobre cmo
implementar los diferentes algoritmos de programacin lineal (simplex, simplex dual, simplex revisado y de punto interior) en cdigos comerciales, con el fin de incrementar la velocidad de cmputo y la precisin necesarias para resolver problemas muy grandes.
El nuevo captulo 10 cubre la heurstica y la metaheurstica diseadas para obtener buenas soluciones aproximadas a problemas de programacin entera y combinatoria.
El nuevo captulo 11, dedicado al importante problema del agente viajero, incluye varias aplicaciones y el desarrollo de algoritmos de solucin heursticos y exactos.
Todos los algoritmos de los captulos 10 y 11 se codificaron en Excel para una agradable experimen-tacin interactiva con los modelos.
En todos los captulos se agregaron numerosos problemas nuevos.
Tambin se actualiz el software TORA.
Para mayor informacin, visite:pearsoneducacion.net/taha
INVESTIGACINDE OPERACIONESINV
ESTIGA
CIN
DE O
PERACIO
NES
ANIVERSARIO
www.FreeLibros.com
www.FreeLibros.com
Investigacinde operaciones
www.FreeLibros.com
www.FreeLibros.com
Investigacinde operaciones
Novena edicin
Hamdy A. TahaUniversity of Arkansas, Fayetteville
TRADUCCINRodolfo Navarro Salas
Ingeniero MecnicoUniversidad Nacional Autnoma de Mxico
REVISIN TCNICA
MXICOAlicia Nandeli Mercado Zepeda
Humberto Oviedo GaldeanoFrancisco Garca Mora
Academia de Investigacin de OperacionesUnidad Profesional Interdisciplinaria de Ingeniera
y Ciencias Sociales y Administrativas (UPIICSA)Instituto Politcnico Nacional
Mario lvarez GarcaDepartamento de Ingeniera Industrial
Instituto Tecnolgico Superior del Occidente del Estado de HidalgoUlises Mercado Valenzuela
Unidad de Estudios de Posgrado e InvestigacinInstituto Tecnolgico de Estudios Superiores de Coacalco
ARGENTINAOsvaldo Facundo Martnez
Departamento de Ingeniera IndustrialUniversidad Tecnolgica Nacional
Facultad Regional Crdoba
www.FreeLibros.com
Authorized translation from the English language edition, entitled Operations Research: An Introduction,9th Edition, by Hamdy A. Taha, published by Pearson Education, Inc., publishing as Prentice Hall,Copyright 2011. All rights reserved.ISBN 9780132555937
Traduccin autorizada de la edicin en idioma ingls, titulada Operations Research: An Introduction, 9a.edicin, por Hamdy A. Taha, publicada por Pearson Education, Inc., publicada como Prentice Hall,Copyright 2011. Todos los derechos reservados.
Esta edicin en espaol es la nica autorizada.
Edicin en espaolEditora: Gabriela Lpez Ballesteros
e-mail: [email protected] Editor de desarrollo: Bernardino Gutirrez Hernndez Supervisor de produccin: Rodrigo Romero Villalobos
NOVENA EDICIN, 2012
D.R. 2012 por Pearson Educacin de Mxico, S.A. de C.V.Atlacomulco 500-5o. pisoCol. Industrial Atoto53519, Naucalpan de Jurez, Estado de Mxico
Cmara Nacional de la Industria Editorial Mexicana. Reg. nm. 1031.
Reservados todos los derechos. Ni la totalidad ni parte de esta publicacin pueden reproducirse, registrarseo transmitirse, por un sistema de recuperacin de informacin, en ninguna forma ni por ningn medio, seaelectrnico, mecnico, fotoqumico, magntico o electroptico, por fotocopia, grabacin o cualquier otro,sin permiso previo por escrito del editor.
El prstamo, alquiler o cualquier otra forma de cesin de uso de este ejemplar requerir tambin laautorizacin del editor o de sus representantes.
ISBN VERSIN IMPRESA: 978-607-32-0796-6ISBN VERSIN E-BOOK: 978-607-32-0797-3ISBN E-CHAPTER: 978-607-32-0798-0
PRIMERA IMPRESINImpreso en Mxico/Printed in Mexico.1 2 3 4 5 6 7 8 9 0 - 14 13 12 11
Datos de catalogacin bibliogrfica
TAHA, HAMDY A.
Investigacin de operaciones Novena edicin
PEARSON EDUCACIN, Mxico, 2012
ISBN: 978-607-32-0796-6
rea: Matemticas
Formato: 18.5 3 23.5 cm Pginas: 824
www.FreeLibros.com
A Karen
Los ros no llevan agua,el sol las fuentes sec
Yo s donde hay una fuenteque no ha de secar el sol!La fuente que no se agota
es mi propio corazn
V. Ruiz Aguilera (1862)
www.FreeLibros.com
www.FreeLibros.com
Contenido
Lo nuevo en esta edicin xxvAgradecimientos xxviReconocimientos xxxAcerca del autor xxxiMarcas registradas xxxiii
Captulo 1 Qu es la investigacin de operaciones 1
1.1 Introduccin 11.2 Modelos de investigacin de operaciones 11.3 Solucin del modelo de IO 51.4 Modelos de colas y simulacin 61.5 El arte del modelado 61.6 Ms que slo matemticas 71.7 Fases de un estudio de IO 91.8 Acerca de este libro 10
Bibliografa 11
Captulo 2 Modelado con programacin lineal 13
2.1 Modelo de PL con dos variables 132.2 Solucin grfica de la PL 16
2.2.1 Solucin de un modelo de maximizacin 162.2.2 Solucin de un modelo de minimizacin 24
2.3 Solucin con computadora, aplicando Solver y AMPL 272.3.1 Solucin de PL con Excel Solver 272.3.2 Solucin de PL con AMPL 31
2.4 Aplicaciones de programacin lineal 352.4.1 Inversin 352.4.2 Planificacin de la produccin y control de inventario 402.4.3 Planificacin de la mano de obra 482.4.4 Planificacin de desarrollo urbano 522.4.5 Mezcla y refinacin 572.4.6 Aplicaciones de PL adicionales 63Bibliografa 68
Captulo 3 Mtodo simplex y anlisis de sensibilidad 69
3.1 Modelo de PL en forma de ecuacin 693.2 Transicin de la solucin grfica a la algebraica 72
vii
www.FreeLibros.com
viii Contenido
3.3 Mtodo simplex 763.3.1 Naturaleza iterativa del mtodo simplex 773.3.2 Detalles de clculo del algoritmo simplex 793.3.3 Resumen del mtodo simplex 85
3.4 Solucin artificial inicial 893.4.1 Mtodo M 893.4.2 Mtodo de dos fases 94
3.5 Casos especiales en el mtodo simplex 993.5.1 Degeneracin 993.5.2 ptimos alternativos 1023.5.3 Solucin no acotada 1043.5.4 Solucin no factible 106
3.6 Anlisis de sensibilidad 1083.6.1 Anlisis de sensibilidad grfica 1083.6.2 Anlisis de sensibilidad algebraica. Cambios
en el lado derecho 1143.6.3 Anlisis de sensibilidad algebraica.
Funcin objetivo 1233.6.4 Anlisis de sensibilidad con Tora, Solver,
y AMPL 1293.7 Temas de clculo en la programacin lineal 131
Bibliografa 136
Captulo 4 Dualidad y anlisis postptimo 137
4.1 Definicin del problema dual 1374.2 Relaciones primal-dual 141
4.2.1 Repaso de operaciones con matrices simples 1414.2.2 Diseo de la tabla simplex 1424.2.3 Solucin dual ptima 1434.2.4 Clculos con la tabla simplex 150
4.3 Interpretacin econmica de la dualidad 1534.3.1 Interpretacin econmica de las variables duales 1544.3.2 Interpretacin econmica de las restricciones
duales 1564.4 Algoritmos simplex adicionales 158
4.4.1 Algoritmo simplex dual 1594.4.2 Algoritmo simplex generalizado 164
4.5 Anlisis postptimo 1654.5.1 Cambios que afectan la factibilidad 1664.5.2 Cambios que afectan la optimalidad 171Bibliografa 174
www.FreeLibros.com
Contenido ix
Captulo 5 Modelo de transporte y sus variantes 175
5.1 Definicin del modelo de transporte 1755.2 Modelos de transporte no tradicionales 1825.3 Algoritmo de transporte 187
5.3.1 Determinacin de la solucin de inicio 1885.3.2 Clculos iterativos del algoritmo de transporte 1915.3.3 Explicacin del mtodo de los multiplicadores
con el mtodo simplex 1995.4 Modelo de asignacin 200
5.4.1 Mtodo hngaro 2015.4.2 Explicacin del mtodo hngaro con simplex 206Bibliografa 208
Captulo 6 Modelo de redes 209
6.1 Alcance y definicin de modelos de redes 2096.2 Algoritmo del rbol de mnima expansin 2126.3 Problema de la ruta ms corta 217
6.3.1 Ejemplos de aplicaciones de la ruta ms corta 2176.3.2 Algoritmos de la ruta ms corta 2216.3.3 Formulacin de programacin lineal del problema
de la ruta ms corta 2306.4 Modelo de flujo mximo 234
6.4.1 Enumeracin de cortes 2356.4.2 Algoritmo de flujo mximo 2366.4.3 Formulacin de programacin lineal en el modo
de flujo mximo 2446.5 CPM y PERT 247
6.5.1 Representacin en forma de red 2476.5.2 Clculos del mtodo de la ruta crtica (CPM) 2526.5.3 Construccin del cronograma 2556.5.4 Formulacin de programacin lineal de CPM 2616.5.5 Redes PERT 262Bibliografa 265
Captulo 7 Programacin lineal avanzada 267
7.1 Fundamentos del mtodo simplex 2677.1.1 Desde los puntos extremos hasta las soluciones
bsicas 2697.1.2 Tabla simplex generalizada en forma
matricial 272
www.FreeLibros.c