deOPERACIONES7 a. e d i c i n

INVESTIGACIN

7 a. e d i c i n

deOPERA

CION

ESIN

VESTIG

AC

IN

HAMDY A. TAHATA

HA

Vistenos en:www.pearsoneducacion.net

Vistenos en:www.pearsoneducacion.net

La sptima edicin de esta reconocida obra ofrece una cobertura equilibrada

de la teora, las aplicaciones y el clculo en la investigacin de operaciones,

e incluye situaciones prcticas completamente analizadas. Cada captulo

contiene ejemplos y aplicaciones tomadas de estudios de casos ya publicados.

Para destacar la efectividad de la investigacin de operaciones para la toma de

decisiones, esta edicin hace nfasis en las herramientas de clculo modernas

los programas de cmputo. Prcticamente cada algoritmo es respaldado y

explicado por medio de una herramienta de software apropiada, lo que facilita

considerablemente la comprensin de los conceptos.

La obra incluye los siguientes apoyos tecnolgicos:

Poderoso software TORA, con caractersticas tutoriales nuevas y nicas.

Las plantillas Excel, diseadas para resolver problemas generales

cambiando simplemente en una plantilla los datos de entrada.

Excel Solver para resolver problemas de transportacin, de red y de programacin lineal y no lineal.

Investigacin deoperaciones

Investigacin deoperaciones

Sptima edicin

Hamdy A. TahaUniversity of Arkansas, Fayetteville

TRADUCCIN:Virgilio Gonzlez PozoIngeniero QumicoUniversidad Nacional Autnoma de Mxico

REVISIN TCNICA:M. en C. Guillermo Martnez del Campo VarelaUniversidad Iberoamericana

Bonifacio Romn TapiaIngeniero Mecnico ElectricistaUniversidad Nacional Autnoma de Mxico

Heriberto Garca ReyesDirector Asociado del Departamento de Ingeniera Industrial y de SistemasInstituto Tecnolgico y de Estudios Superiores de MonterreyCampus Monterrey

Datos de catalogacin bibliogrfica

TAHA, HAMDY A.

Investigacin de operaciones, 7a. edicin

PEARSON EDUCACIN, Mxico, 2004

ISBN: 970-26-0498-2 rea: Universitarios

Formato: 18.5 23.5 cm Pginas: 848

Authorized translation from the English language edition, entitled Operations Research: An Introduction, SeventhEdition, by Hamdy A. Taha, published by Pearson Education, Inc., publishing as PRENTICE HALL, INC., Copyright 2003. All rights reserved.ISBN 0-13-032374-8

Traduccin autorizada de la edicin en idioma ingls, titulada Operations Research: An Introduction, Seventh Edition,por Hamdy A. Taha, publicada por Pearson Education, Inc., publicada como PRENTICE HALL, INC., Copyright 2003. Todos los derechos reservados.

Esta edicin en espaol es la nica autorizada.

Edicin en espaolEditor: Guillermo Trujano Mendoza

e-mail: guillermo.trujano@pearsoned.com Supervisor de desarrollo: Jorge Bonilla Talavera Supervisor de produccin: Enrique Trejo Hernndez

Edicin en inglsEditor-in-Chief: Denise J. Clinton Vice President and Editorial Director, ECS: Marcia J.

HortonAcquisitions Editor: Dorothy MarreroEditorial Assistant: Erin KatchmarVice President and Director of Production andManufacturing, ESM: David W. RiccardiExecutive Managing Editor: Vince OBrienManaging Editor: David A. George

Production Editor: Ann ImhofDirector of Creative Services: Paul BelfantiCreative Director: Carole AnsonArt Director: Jayne ConteCover Designer: Bruce KenselaarArt Editor: Greg DullesManufacturing Manager: Trudy PisciottiManufacturing Buyer: Lynda CastilloMarketing Manager: Holly Stark

SPTIMA EDICIN, 2004

D.R. 2004 por Pearson Educacin de Mxico, S.A. de C.V.Atlacomulco No. 500-5 piso Col. Industrial Atoto 53519, Naucalpan de Jurez, Edo. de MxicoE-mail: editorial.universidades@pearsoned.com

Cmara Nacional de la Industria Editorial Mexicana. Reg. Nm. 1031.

Prentice Hall es una marca registrada de Pearson Educacin de Mxico, S.A. de C.V.

Reservados todos los derechos. Ni la totalidad ni parte de esta publicacin pueden reproducirse, registrarse o transmitirse,por un sistema de recuperacin de informacin, en ninguna forma ni por ningn medio, sea electrnico, 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 la autorizacin deleditor o de sus representantes.

ISBN 970-26-0498-2

Impreso en Mxico. Printed in Mexico.1 2 3 4 5 6 7 8 9 0 - 05 04 03 02

A Karen

Los ros no llevan agua,el sol las fuentes sec

Yo s dnde hay una fuente que no ha de secar el sol! La fuente que no se agota

es mi propio corazn

V. Ruiz Aguilera (1862)

vi

Contenido abreviado

Prefacio xv

Acerca del autor xvii

Captulo 1 Qu es la investigacin de operaciones? 1

Captulo 2 Introduccin a la programacin lineal 11

Captulo 3 El mtodo smplex 71

Captulo 4 Anlisis de dualidad y sensibilidad 115

Captulo 5 Modelo de transporte y sus variantes 165

Captulo 6 Modelos de redes 213

Captulo 7 Programacin lineal avanzada 289

Captulo 8 Programacin de metas 347

Captulo 9 Programacin lineal entera 361

Captulo 10 Programacin dinmica determinstica 401

Captulo 11 Modelos determinsticos de inventarios 429

Captulo 12 Repaso de probabilidad bsica 463

Captulo 13 Modelos de pronsticos 491

Captulo 14 Anlisis de decisiones y juegos 503

Captulo 15 Programacin dinmica probabilstica 547

Captulo 16 Modelos probabilsticos de inventario 559

Captulo 17 Sistemas de colas 579

Captulo 18 Modelado de simulacin 639

Captulo 19 Proceso de decisin markoviana 675

Captulo 20 Teora clsica de la optimizacin 701

Captulo 21 Algoritmos de programacin no lineal 731

Apndice A Repaso de vectores y matrices 765

Apndice B Introduccin a TORA 779

Apndice C Tablas estadsticas 785

Apndice D Respuestas parciales de problemas seleccionados 789

ndice 825

vii

Contenido

Prefacio xv

Acerca del autor xvii

Captulo 1 Qu es la investigacin de operaciones? 1

1.1 Modelos de investigacin de operaciones 11.2 Solucin del modelo de investigacin de operaciones 41.3 Modelos de colas y simulacin 51.4 El arte del modelado 51.5 Ms que slo matemticas 61.6 Fases de un estudio de investigacin de operaciones 81.7 Acerca de este libro 9

Captulo 2 Introduccin a la programacin lineal 11

2.1 Modelo de programacin lineal con dos variables 112.2 Solucin grfica de la programacin lineal 14

2.2.1 Solucin de un modelo de maximizacin 152.2.2 Solucin de un modelo de minimizacin 182.2.3 Solucin grfica con TORA 20

2.3 Anlisis grfico de sensibilidad 232.3.1 Cambios en los coeficientes de la funcin objetivo 242.3.2 Cambio en disponibilidad de recursos 272.3.3 Valor por unidad de un recurso 28

2.4 Soluciones de problemas de programacin lineal en computadora 332.4.1 Solucin de programacin lineal con TORA 332.4.2 Solucin de programacin lineal con Solver de Excel 362.4.3 Solucin de programacin lineal con LINGO

y AMPL 382.5 Anlisis de modelos seleccionados de programacin lineal 47

Referencias seleccionadas 66Problemas integrales 67

Captulo 3 El mtodo smplex 71

3.1 Espacio de soluciones en forma de ecuacin 713.1.1 Conversin de desigualdades a ecuaciones 713.1.2 Manejo de variables no restringidas 73

3.2 Transicin de solucin grfica a solucin algebraica 753.3 El mtodo smplex 80

3.3.1 Naturaleza iterativa del mtodo smplex 803.3.2 Detalles de clculo del algoritmo smplex 833.3.3 Iteraciones smplex con TORA 92

3.4 Solucin artificial de inicio 943.4.1 Mtodo M 943.4.2 Mtodo de dos fases 98

3.5 Casos especiales de aplicacin del mtodo smplex 1033.5.1 Degeneracin 1033.5.2 ptimos alternativos 1063.5.3 Solucin no acotada 1093.5.4 Solucin no factible 110Referencias seleccionadas 112Problemas integrales 112

Captulo 4 Anlisis de dualidad y sensibilidad 115

4.1 Definicin del problema dual 1154.2 Relaciones primal-dual 120

4.2.1 Repaso de operaciones matriciales sencillas 1204.2.2 Planteamiento de la tabla smplex 1224.2.3 Solucin dual ptima 1224.2.4 Clculos con la tabla smplex 1264.2.5 Valor objetivo primal y dual 130

4.3 Interpretacin econmica de la dualidad 1324.3.1 Interpretacin econmica de las variables duales 1324.3.2 Interpretacin econmica de las restricciones

duales 1354.4 Otros algoritmos smplex para programacin lineal 137

4.4.1 Mtodo dual smplex 1374.4.2 Algoritmo smplex generalizado 143

4.5 Anlisis postptimo o de sensibilidad 1444.5.1 Cambios que afectan la factibilidad 1454.5.2 Cambios que afectan la optimalidad 155Referencias seleccionadas 161Problemas integrales 162

Captulo 5 Modelo de transporte y sus variantes 165

5.1 Definicin del modelo de transporte 1655.2 Modelos no tradicionales de transporte 1725.3 El algoritmo de transporte 177

5.3.1 Determinacin de la solucin de inicio 1785.3.2 Clculos iterativos del algoritmo de transporte 1825.3.3 Solucin del modelo de transporte con TORA 1875.3.4 Explicacin del mtodo de los multiplicadores

con el mtodo smplex 1955.4 El modelo de asignacin 196

5.4.1 El mtodo hngaro 1975.4.2 Explicacin del mtodo hngaro con el mtodo

smplex 202

viii Contenido

5.5 El modelo de transbordo 203Referencias seleccionadas 208Problemas integrales 208

Captulo 6 Modelos de redes 213

6.1 Definiciones para redes 2146.2 Algoritmo de rbol de expansin mnima 2156.3 Problema de la ruta ms corta 220

6.3.1 Ejemplos de aplicaciones de ruta ms corta 2206.3.2 Algoritmos de ruta ms corta 2246.3.3 Formulacin del problema de la ruta ms c