HILLIER, Frederick S.; LIEBERMAN, Gerald J. - Introdução à Pesquisa Operacional PDF

Preview

Summary

1101025599 11111111111 ,...,, ' INTRODUÇAO A PESQUISA OPERACIONAL 8ª Edição FREDERICK S. HILLIER Stanford University GERALD J. LIEBERMAN Ex-Professor Titular da Stanford University Tradução CARO LEITOR NÃO ARIOVALDO GRIESI RISQut O LIVRO . Revisão Técnica JOÃO CHANG JUNIOR Doutor em Administraç...

Description

1101025599

11111111111 ,...,,

'

INTRODUÇAO A PESQUISA OPERACIONAL 8ª Edição

FREDERICK S. HILLIER Stanford University

GERALD

J.

LIEBERMAN

Ex-Professor Titular da Stanford University

Tradução ARIOVALDO GRIESI

CARO LEITOR NÃO RISQut O LIVRO .

Revisão Técnica JOÃO CHANG JUNIOR Doutor em Administração - FEA/USP Professor Titular do Programa de Mestrado da UNIP Professor Titular da FAAP

FACULDADE DE EIOEIHAiUA DE GUAR ATllGUETA

BIBLIOTECA Bangcoc Bogotá Beijing Caracas Cidade do México Cingapura Lisboa Londres Madri Milão Montreal Nova Delhi Toronto Santiago São Paulo Seul Sydney Taipé

2 55 99

Data: '' · 8ª Edição ISBN 85-86804-68-1

Valor:

Cl i 0r,

Kl, k-o, ,_,s;,

C I D I T: G Ir:(;:V.,

Nenhuma parte desta publicação poderá ser reproduzida ou distribuída de qualquer forma ou por qualquer meio, ou armazenada em um banco de dados ou sistema de recuperação, sem o consentimento, por escrito, da Editora, incluindo, mas não limitado a, qualquer rede ou outro dispositivo eletrônico de armazenamento ou transmissão ou difusão para ensino a distância. Todos os direitos reservados.© 2006 de McGraw-Hill Interamericana do Brasil Ltda. Av. Engenheiro Luís Carlos Berrini, 1.253 - 10º andar 04571-010 - São Paulo - SP

Tradução do original em inglês Introduction operations research Copyright© 2005, 2001, 1995, 1990, 1986, 1980, 1974, 1967 de The McGraw-Hill Companies, Inc. ISBN da obra original: 0-07-252744-7 - Parte de 0-07-301779-5 (Acompanha CD)

Diretor-geral: Adilson Pereira Editora de Desenvolvimento: Ada Santos Seles Preparação de Texto: Mateus Potumati Capa e Ilustração: Lisa Gravunder Editoração Eletrônica: ERJ Composição Editorial e Artes Gráficas Ltda.

Dados Internacionais de Catalogação na Publicação (CIP) (Câmara Brasileira do Livro, SP, Brasil)

Hillier, Frederick S. Introdução à pesquisa operacional/ Frederick S. Hillier, Gerald J. Lieberman; tradução Ariovaldo Griesi; revisão técnica João Chang Junior. - São Paulo: McGraw-Hill, 2006. Título original: Introduction operations research 8. ed. norte-americana Inclui CD-ROM. ISBN 85-868046-81 1. Pesquisa operacional 1. Lieberman, Gerald J. II. Título. CDD-003

06-3483 Índices para catálogo sistemático: 1. Pesquisa operacional 003

Se você tem dúvidas, críticas ou sugestões, entre em contato pelo endereço eletrônico [email protected]. Em Portugal, use o endereço serviç[email protected].

li

ou

rin-

,ara

SOBRE OS AUTORES

Frederick S. Hillier nasceu e se criou em Aberdeen, Washington, onde foi ganhador de prêmios em concursos estaduais para o ensino médio em dissertações, matemática, debates e música. Ainda como estudante da Stanford University ganhou o primeiro lugar em sua turma de engenharia com mais de 300 alunos. Ganhou também o McKinsey Prize para redação técnica, conquistou o Prêmio de Debatedor Brilhante para universitários cursando o segundo ano de faculdade, tocava no Stanford Woodwind Quintet e também obteve o Hamilton Award por combinar excelência na engenharia com êxitos notáveis em ciências humanas e sociais. Logo após ter se formado em engenharia industrial, ganhou três bolsas de estudo de âmbito nacional (National Science Foundation, Tau Beta Pi e Danforth) para pós-graduação na Stanford com especialização em pesquisa operacional. Após receber seu título de Ph.D., associou-se ao quadro de professores da Stanford University e também como professor visitante na Comell University, Carnegie-Mellon University, Technical University of Denmark, University of Canterbury (Nova Zelândia) e University of Cambridge (Inglaterra). Após 35 anos no quadro de professores da Stanford, aposentou-se precocemente de suas responsabilidades como docente, em 1996, para poder se dedicar em tempo integral à redação de livros e hoje é Professor Emérito de Pesquisa Operacional na Stanford. A pesquisa do Dr. Hillier se estendeu para uma série de áreas, incluindo programação inteira, teoria das filas e sua aplicação, controle de qualidade estatístico e a aplicação da pesquisa operacional ao projeto de sistemas de produção e orçamento de capital. Ele tem inúmeras publicações e seus trabalhos de grande influência foram selecionados para republicação em livros com leituras selecionadas pelo menos dez vezes. Foi o ganhador do primeiro prêmio de um concurso de pesquisas sobre "Orçamento de Capital de Projetos Inter-relacionados", patrocinado pelo The Institute of Management Sciences (Tims) e pelo U.S. Office of Naval Research. Dr. Hillier e Dr. Lieberman também receberam menção honrosa na edição de 1995 do Lanchester Prize (melhor publicação em língua inglesa de qualquer campo da pesquisa operacional), que foi concedida pelo Institute of Operations Research and the Management Sciences (lnforms) para a 6ª edição deste livro. Dr. Hillier ocupou vários cargos de liderança em sociedades de profissionais em sua área. Por exemplo, foi tesoureiro da Operations Research Society of America (Orsa), vicepresidente para Reuniões da Tims, co-presidente geral da edição de 1989 da Reunião Internacional da Tims em Osaka, Japão, presidente do Comitê de Publicação da Tims, presidente do Comitê de Pesquisa para Editor de Operations Research da Orsa, presidente do Comitê de Planejamento de Recursos da Orsa, presidente do Comitê de Reuniões Conjuntas Orsaffims e presidente do Comitê de Seleção do John von Neumann Theory Prize da Informs. Atualmente, atua como editor de séries para a International Series in Operations Research and Management Science publicada pela Kluwer Academic Publishers. Além de Introduction to Operations Research e outros dois volumes complementares, Introduction to Mathematical Programming (2. ed., 1995) e Introduction to Stochastic Models in Operations Research (1990), suas obras são: The Evaluation of Risky Interrelated Investments (North-Holland, 1969), Queueing Tables and Graphs (North-Holland: Elsevier 1981, em co-autoria com O. S. Yu, além de D. M. Avis, L. D. Fossett, F. D. Lo e M. 1. Reiman) e Introduction to Management Science: A Modeling Studies Approach with Spreadsheets (2. ed., McGraw-Hill/lrwin, 2003, em co-autoria com M. S. Hillier). Gerald J. Lieberman infelizmente nos deixou em 1999, ano de sua morte. Foi Professor Emérito de Pesquisa Operacional e Estatística na Stanford University, onde exerceu o cargo de presidente-fundador do Departamento de Pesquisa Operacional. Engenheiromecânico pela Cooper Union e estatístico em pesquisa operacional, recebeu o título de

m. Ili

\

IV

SOBRE OS AUTORES

mestrado em estatística matemática da Columbia University e de Ph.D. em estatística pela Stanford University). Dr. Lieberman foi um dos líderes mais eminentes da Stanford em décadas recentes. Após presidir o Departamento de Pesquisa Operacional, atuou como diretor associado da Escola de Ciências Humanas, vice-diretor e decano de pesquisa, vice-diretor e decano de pós-graduação, presidente do conselho administrativo, membro do conselho consultivo da Universidade e presidente do Comitê de Celebração do Centenário. Também atuou como diretor ou diretor interino no mandato de três presidentes distintos da Stanford. Ao longo desses anos de liderança na Universidade, também permaneceu ativo profissionalmente. Sua pesquisa foi realizada nas áreas de estocástica da pesquisa operacional, normalmente na interface de estatística e probabilidade aplicada. Publicou extensivamente nas áreas de confiabilidade e controle de qualidade e na modelagem de sistemas complexos, inclusive seu projeto ótimo, quando os recursos são limitados. Altamente respeitado como experiente defensor do campo da pesquisa operacional, Dr. Lieberman atuou em inúmeros papéis de liderança, inclusive como presidente eleito do The Institute of Management Sciences. Entre suas honrarias profissionais estão: eleito para o National Academy of Engineering, agraciado com a Shewhart Medal da American Society for Quality Control e com o Cuthbertson Award por serviços excepcionais à Stanford University e por sua atuação como membro no Centro para Estudos Avançados nas Ciências Comportamentais. Além disso, o Institute of Operations Research and the Management Sciences (lnforms) o agraciou com o prêmio de menção honrosa na edição de 1995 do Lanchester Prize pela 6ª edição deste livro. Em 1996, o lnforms também o premiou com a prestigiosa Medalha Kimball por suas contribuições excepcionais ao campo da pesquisa operacional e administração. Além de Introduction to Operations Research e outros dois volumes complementares, Introduction to Mathematical Programming (2. ed., 1995) e Introduction to Stochastic Models in Operations Research (1990), suas obras são: Handbook of Industrial Statistics (PrenticeHall, 1955, com co-autoria de A. H. Bowker), Tables of the Non-Central t-Distribution (Stanford University Press, 1957, com co-autoria de G. J. Resnikofi), Tables of the Hypergeometric Probability Distribution (Stanford University Press, 1961, com co-autoria de D. Owen), Engineering Statistics, 2. ed. (Prentice-Hall, 1972, com co-autoria de A. H. Bowker) e Introduction to Management Science: A Modeling and Case Studies Approach. with Spreadsheets (McGraw-Hill/Irwin, 2000, com co-autoria de F. S. Hillier e M. S. Hillier).

a pela

entes. do da DO de l\"O da como

>rofis:ional, mente ,lexos,

~.Dr.

loThe Jara o ociety mford ências ement 95 do com a '>quisa

11tares, Iodeis ~tice­

bution 'Jf the >ria de A. H. h with ).

SOBRE OS AUTORES DOS ESTUDOS DE CASO Karl Schmedders é professor-adjunto do Departamento de Economia Gerencial e Ciências da Decisão da Kellogg Graduate School of Management (Northwestem University), onde leciona métodos quantitativos para tomada de decisão gerencial. Entre seus interesses de pesquisa estão aplicações da pesquisa operacional à teoria econômica, teoria de equilíbrio geral com mercados incompletos, avaliação de ativos e economia computacional. Dr. Schmedders recebeu seu doutorado em pesquisa operacional da Stanford University, onde lecionou tanto em cursos de graduação como de pós-graduação em pesquisa operacional. Entre as aulas dadas destacam-se um curso de estudos de caso em pesquisa operacional e o convite subseqüente para se apresentar em uma conferência patrocinada pelo Institute of Operations Research and the Management Sciences (lnforms) sobre sua bem-sucedida experiência com esse curso. Recebeu várias premiações por sua atuação como professor na Stanford, inclusive o prestigioso Walter J. Gores Teaching Award da Universidade. Também foi nomeado L. G. Lavengood Professor of the Year na Kellogg School of Management. Após dar um curso na WHU Koblenz (uma escola de administração de empresas alemã de primeira linha) em 2003, recebeu o Prêmio de Melhor Professor dessa escola, bem como para aquele semestre. Molly Stephens é associada na unidade de Los Angeles da Quinn, Emanuel, Urquhart, Oliver & Hedges, LLP. Formou-se pela Stanford University em engenharia industrial e tem mestrado em pesquisa operacional por essa mesma Universidade. Stephens lecionou o curso de oratória na Escola de Engenharia de Stanford e atuou como professora-assistente para um curso de estudos de caso em pesquisa operacional. Como professora-assistente, ela analisou problemas de pesquisa operacional encontrados no mundo real e a transformação desses problemas em estudos de caso para sala de aula. Sua pesquisa foi premiada quando ganhou uma bolsa destinada à pesquisa para não-graduados da Stanford que lhe permitiu continuar seu trabalho e foi convidada para dar uma palestra em uma conferência da lnforms para apresentar suas conclusões referentes aos bem-sucedidos estudos de caso. Após sua formatura, Stephens trabalhou na Andersen Consulting como integradora de sistemas, vivenciando casos reais de perto, antes de retomar seus estudos para obter o título de Doutora em Direito (com honra ao mérito) da Escola de Direito da University of Texas em Austin.

V

,

DEDICATORIA

À memória de nossos pais e À memória do meu dileto mentor, Gerald J. Lieberman, que foi um dos verdadeiros gigantes de nosso campo

VI

,

SUMARIO

PREFÁCIO

XVIII

CAPÍTULO 1 Introdução 1 1. 1 As Origens da Pesquisa Operacional 1.2 A Natureza da Pesquisa Operacional 2 1.3 O Impacto da Pesquisa Operacional 3 1.4 Algoritmos e/ou Courseware 5 Referências Selecionadas 6 Problemas 7

CAPÍTULO 2 Visão Geral da Abordagem de Modelagem da Pesquisa Operacional

8

2. 1 Definição do Problema e Coleta de Dados 8 2.2 Formulando um Modelo Matemático 11 2.3 Derivando Soluções a Partir do Modelo 15 2.4 Testando o Modelo 17 2.5 Preparando-se para Aplicar o Modelo 19 2.6 Implementação 20 2.7 Conclusões 22 Referências Selecionadas 22 Problemas 23

CAPÍTULO 3 Introdução à Programação Linear

25

3.1 Exemplo de Protótipo 26 3.2 O Modelo de Programação Linear 31 3.3 Hipóteses da Programação Linear 36 3.4 Exemplos Adicionais 43 3.5 Alguns Estudos de Caso Clássicos 58 3.6 Formulando e Solucionando Modelos de Programação Linear em uma Planilha 3. 7 Formulando Modelos de Programação Linear de Grandes Dimensões 7 1 3.8 Conclusões 78 Apêndice 3.1 A Linguagem de Modelagem Lingo 78 Referências Selecionadas 88 Ferramentas de Aprendizado para este Capítulo Incluídas no CD-ROM 88 Problemas 88 Caso 3.1 Montagem de Automóveis 98 Apresentação Prévia dos Casos Adicionais no CD-ROM 99 Caso 3.2 Cortando Custos na Lanchonete 99 Caso 3.3 Dotando uma Central de Atendimento de Pessoal 99 Caso 3.4 Promovendo um Cereal Matinal 100

64

VII

VIII

SUMÁRIO CAPÍTULO 4 Solucionando Problemas de Programação Linear: O Método Simplex 4. 1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9

A Essência do Método Simplex 1O1 Configurando o Método Simplex 106 A Álgebra do Método Simplex 109 O Método Simplex em Forma Tabular 114 Desempate no Método Simplex 118 Adaptando a Outras Formas de Modelo 122 Análise de Pós-otimalidade 139 Implementação Via Computador 146 Sistemática do Ponto Interno na Resolução de Problemas de Programação

Linear 149 4.1 O Conclusões 154 Apêndice 4.1 Uma Introdução para Emprego do Lindo

154

Referências Selecionadas 157 Ferramentas de Aprendizado para este Capítulo Incluídas no CD-ROM Problemas 158 Caso 4.1 Tecidos e Moda Outono-inverno 166 Apresentação Prévia dos Casos Adicionais no CD-ROM Caso 4.2 Novas Fronteiras 168 Caso 4.3 Distribuindo Alunos em Escolas 168 CAPÍTULO 5 Teoria do Método Simplex

168

1 69

5.1 Fundamentos do Método Simplex 169 5.2 Método Simplex Revisado 180 5.3 Um lnsight Fundamental 188 5.4 Conclusões 195 Referências Selecionadas 196 Ferramentas de Aprendizado para este Capítulo Incluídas no CD-ROM Problemas

196

197

CAPÍTULO 6 Teoria da Dualidade e Análise de Sensibilidade 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8

157

203

A Essência da Teoria da Dualidade 203 Interpretação Econômica da Dualidade 211 Relações Primai-Dual 214 Adaptando para outras Formas Primais 218 O Papel da Teoria da Dualidade na Análise de Sensibilidade A Essência da Análise de Sensibilidade 224 Aplicando a Análise de Sensibilidade 232 Efetuando Análise de Sensibilidade em uma Planilha 251

222

6. 9 Conclusões 264 Referências Selecionadas 265 Ferramentas de Aprendizado para este Capítulo Incluídas no CD-ROM Problemas 266 Caso 6.1 Controlando a Poluição do Ar 279 Apresentação Prévia dos Casos Adicionais no CD-ROM 280 Caso 6.2 Administração de uma Propriedade Rural 280 Caso 6.3 Redistribuição de Alunos por Escolas, Revisitada Caso 6.4 Redigindo um Memorando Não-técnico 280

280

265

1 O1

IX

SUMÁRIO CAPÍTULO 7 Outros Algoritmos para Programação Linear

281

7. 1 O Método Simplex Dual 281 7.2 Programação Linear Paramétrica 284 7.3 A Técnica do Limite Superior 289 7.4 Um Algoritmo de Ponto Interno 292 7.5 Conclusões 302 Referências Selecionadas 303 Ferramentas de Aprendizado para este Capítulo Incluídas no CD-ROM Problemas 304

CAPÍTULO 8 Os Problemas de Transporte e da Designação

303

308

8. 1 O Problema de Transporte 309 8.2 Um Método Simplex Aperfeiçoado para o Problema de Transporte 322 8.3 O Problema da Designação 337 8.4 Algoritmo Especial para o Problema da Designação 344 8.5 Conclusões 349 Referências Selecionadas 349 Ferramentas de Aprendizado para este Capítulo Incluídas no CD-ROM 350 Problemas 350 Caso 8.1 Entregando Madeira para o Mercado 358 Apresentação Prévia dos Casos Adicionais no CD-ROM 359 Caso 8.2 Continuação do Estudo de Caso da Texago 359 Caso 8.3 Escolha de Projetos 359

CAPÍTULO 9 Modelo de Otimização de Redes

360

9.1 Exemplo-Protótipo 361 9.2 A Terminologia das Redes 362 9.3 O Problema do Caminho Mais Curto 366 9.4 O Problema da Árvore de Expansão Mínima 370 9.5 O Problema do Fluxo Máximo 374 9.6 O Problema do Fluxo de Custo Mínimo 382 9.7 O Método Simplex de Rede 390 9.8 Modelo de Rede para Otimizar a Relação Conflitante Tempo-custo 399 9. 9 Conclusões 4 1O Referências Selecionadas 4 12 Ferramentas de Aprendizado para este Capítulo Incluídas no CD-ROM 4 12 Problemas 4 12 Caso 9.1 Dinheiro em Movimento 421 Apresentação Prévia dos Casos Adicionais no CD-ROM 423 Caso 9.2 Ajudando os Aliados 423 Caso 9.3 Passos para o Sucesso 423 CAPÍTULO 10 Programação Dinâmica

424

1O.1 Exemplo-Protótipo para Programação Dinâmica 424 10.2 Características dos Problemas de Programação Dinâmica 10.3 Programação Dinâmica Determinística 431

429

X

SUMÁRIO 10.4 Programação Dinâmica Probabilística 450 10.5 Conclusões 455 Referências Selecionadas 455 Ferramentas de Aprendizado para este Capítulo Incluídas no CD-ROM Problemas

CAPÍTULO 11 Programação Inteira 1 1. 1 11.2 1 1.3 11.4 1 1. 5

456

456

462

Exemplo-Protótipo 463 Algumas Aplicações de PIB 466 Usos Inovadores das Variáveis Binárias na Formulação de Modelos 4 7 1 Alguns Exemplos de Formulação 477 Algumas Considerações Sobre a Resolução de Problemas de Programação

Inteira 484 11.6 A Técnica da Ramificação e Avaliação Progressiva e sua Aplicação à Programação Inteira Binária 488 11 .7 Algoritmo de Ramificação e Avaliação Progressiva para Programação Inteira Mista 498 11 .8 Metodologia da Ramificação e Corte para Solucionar Problemas de PIB 1 1.9 Incorporação da Programação de Restrições 5 1O 1 1. 1O Conclusões 5 16 Referências Selecionadas 5 16 Ferramentas de Aprendizado para este Capítulo Incluídas no CD-ROM 5 17

504

Problemas 5 17 Caso 11 . 1 Preocupações com Capacidade 526 Apresentação Prévia dos Casos Adicionais no CD-ROM 528 Caso 11.2 Designação de Obras de Arte 528 Caso 11 .3 Estocando Conjuntos 529 Caso 11.4 Redistribuindo Estudantes em Escolas, Retornando ao Caso mais uma vez

529

CAPÍTULO 12 Programação Não-Linear 12. 1 12.2 12.3 12.4 12.5 12.6

530

Exemplos de Aplicações 531 Representação Gráfica de Problemas de Programação Não-linear 535 llpos de Problemas de Programação Não-linear 539 Otimização Irrestrita com Uma Variável 544 Otimização Irrestrita com Variáveis Múltiplas 550 As Condições de Karush-Kuhn-Tucker (Kkt) para Otimização Restrita 555

12.7 Programação Quadrática 559 12.8 Programação Separável 565 12.9 Programação Convexa 572 12.1 O Programação Não-convexa (com Planilhas) 580 12. 11 Conclusões 584 Referências Selecionadas 585 Ferramentas de Aprendizado para este Capítulo Incluídas no CD-ROM Problemas 586 Caso 12.1 Seleção Pragmática de Ações 597 Apresentação...