Introducao a Pesquisa Operacional

Embed Size (px)

Text of Introducao a Pesquisa Operacional

INTRODUO PESQUISA OPERACIONAL

Prefaciais.indd 1

27/08/2011 21:57:49

Universidade Estadual Paulista Vice-Reitor no exerccio da Reitoria Julio Cezar Durigan Pr-Reitora de Graduao Sheila Zambello de Pinho Pr-Reitora de Ps-Graduao Marilza Vieira Cunha Rudge Pr-Reitora de Pesquisa Maria Jos Soares Mendes Giannini Pr-Reitora de Extenso Universitria Maria Amlia Mximo de Arajo Pr-Reitor de Administrao Ricardo Samih Georges Abi Rached Secretria Geral Maria Dalva Silva Pagotto Chefe de Gabinete Carlos Antonio Gamero

Prefaciais.indd 2

27/08/2011 21:57:50

Cultura Acadmica

Fernando Augusto Silva Marins

INTRODUO PESQUISA OPERACIONAL

So Paulo 2011

Prefaciais.indd 3

27/08/2011 21:57:51

Pr-Reitoria de Graduao, Universidade Estadual Paulista, 2011.

Ficha catalogrfica elaborada pela Coordenadoria Geral de Bibliotecas da Unesp M339i Marins, Fernando Augusto Silva Introduo Pesquisa Operacional / Fernando Augusto Silva Marins. So Paulo : Cultura Acadmica : Universidade Estadual Paulista, Pr-Reitoria de Graduao, 2011. 176 p. ISBN 978-85-7983-167-6 1. Pesquisa Operacional. I. Ttulo. CDD 658.05

equipe

Pr-reitora Sheila Zambello de Pinho Secretria Silvia Regina Caro Assessoria Elizabeth Berwerth Stucchi Jos Brs Barreto de Oliveira Klaus Schlnzen Junior (Coordenador Geral NEaD) Maria de Lourdes Spazziani Tcnica Bambina Maria Migliori Camila Gomes da Silva Ceclia Specian Eduardo Luis Campos Lima Flvia Maria Pavan Anderlini Gisleide Alves Anhesim Portes Ivonette de Mattos Jos Welington Gonalves Vieira Maria Emlia Arajo Gonalves Maria Selma Souza Santos Renata Sampaio Alves de Souza Sergio Henrique Carregari Vitor Monteiro dos Santos

Prefaciais.indd 4

31/08/2011 21:19:41

PROGRAMA DE APOIO PRODUO DE MATERIAL DIDTICO

Considerando a importncia da produo de material didtico-pedaggico dedicado ao ensino de graduao e de ps-graduao, a Reitoria da UNESP, por meio da Pr-Reitoria de Graduao (PROGRAD) e em parceria com a Fundao Editora UNESP (FEU), mantm o Programa de Apoio Produo de Material Didtico de Docentes da UNESP, que contempla textos de apoio s aulas, material audiovisual, homepages, softwares, material artstico e outras mdias, sob o selo CULTURA ACADMICA da Editora da UNESP, disponibilizando aos alunos material didtico de qualidade com baixo custo e editado sob demanda. Assim, com satisfao que colocamos disposio da comunidade acadmica mais esta obra, Introduo Pesquisa Operacional, de autoria do Prof. Dr. Fernando Augusto Silva Marins, da Faculdade de Engenharia do Cmpus de Guaratinguet, esperando que ela traga contribuio no apenas para estudantes da UNESP, mas para todos aqueles interessados no assunto abordado.

Prefaciais.indd 5

27/08/2011 21:57:51

Prefaciais.indd 6

27/08/2011 21:57:51

SUMRIO

Apresentao

9 11 11

1 pesquisa operacional: origens, definies e reas1.1. 1.2. 1.3. 1.4. 1.5.

A Pesquisa Operacional e o Processo de Tomada de Deciso O que a Pesquisa Operacional? Origens da Pesquisa Operacional Consideraes Importantes21 23 12 13

Fases da Resoluo de um Problema pela Pesquisa Operacional19

16

Referncias

2 programao linear2.1. 2.2. 2.3. 2.4. 2.5. 2.6. 2.7. 2.8. 2.9.

Introduo Modelagem Limitaes

23 24 38 40

Resoluo Grfica Forma Padro46

Definies e Teoremas Mtodo Simplex

49 54

Forma Cannica de um Sistema de Equaes Lineares56 72

Mtodo Simplex com Duas Fases80

Referncias

3 introduo teoria dos grafos e a otimizao em redes3.1. 3.2. 3.3.

81

Introduo Algoritmos102

81 84

Conceitos Bsicos90

Referncias

4 o modelo de transporte simples4.1. 4.2. 4.3.

103 103 108 115

Histrico e Formulao Matemtica Algoritmo do Stepping Stone Method

Resoluo pelo Mtodo Modificado (Modi)

Prefaciais.indd 7

27/08/2011 21:57:51

8

| INTRODUO PESQUISA OPERACIONAL 4.4.

Mtodos para Encontrar uma Soluo Bsica Vivel Inicial para o Stepping Stone Method 117 Ofertas e Demandas Desbalanceadas Degenerescncia121 126 120

4.5. 4.6. 4.7.

Condies Proibidas de Embarque ou Recepo127 129

Referncias

5 o modelo da designao5.1. 5.2. 5.3. 5.4.

Introduo

129 130 131

Definies e Notaes Modelo Matemtico Mtodo Hngaro150

131

Referncias

6 introduo teoria das filas: modelos markovianos6.1. 6.2. 6.3. 6.4. 6.5.

151

Introduo

151 152

Estrutura Bsica de um Sistema de Filas Processos de Nascimento e Morte Modelos de Filas Markovianas Comentrios Gerais172 176 169 156

160

Anexo

Referncias

Prefaciais.indd 8

27/08/2011 21:57:51

APRESENTAO

A Pesquisa Operacional (PO) uma rea da Engenharia de Produo que proporciona aos profissionais, que tm acesso ao seu escopo, um procedimento organizado e consistente que o auxiliar na difcil tarefa de gesto de recursos humanos, materiais e financeiros de uma organizao. De fato, a Pesquisa Operacional oferece um elenco interessante de reas, modelos e algoritmos que permitem ao gestor tomar deciso em problemas complexos, onde deve ser aplicada a tica cientfica. O material deste livro corresponde a um curso semestral introdutrio PO, abordando a Programao Linear, algoritmos para Modelos em Redes e modelos estocsticos da Teoria de Filas. O contedo vem sendo ministrado, h mais de 20 anos, no nvel de graduao para os cursos de Engenharia Mecnica e de Engenharia de Produo Mecnica da Faculdade de Engenharia do Campus de Guaratinguet (FEG) da Universidade Estadual Paulista (UNESP); e desde 2008, em cursos de ps-graduao, Lato Sensu e Stricto Sensu tem sido utilizado como apoio, principalmente pelos alunos que esto tendo acesso PO pela primeira vez. Entendendo a dificuldade dos professores em desenvolver o material didtico para suas aulas, ser disponibilizado, para os que adotarem o livro, na pgina na Internet do Autor (www.feg.unesp.br/~fmarins) os seguintes materiais de apoio: a) Conjunto de slides em PowerPoint com o contedo dos vrios captulos do livro; b) Arquivos com exerccios propostos sobre cada captulo do livro; c) Endereos na Internet para o download de verses livres de importantes e teis softwares (LINDO), e, ainda, o endereo para acesso de software livre desenvolvido em outra instituio (PROLIN Universidade Federal de Viosa UFV). Manuais de usurio do Solver do Excel e do LINDO desenvolvidos por professores de outra instituio (Universidade Federal de Ouro Preto UFOP).

Prefaciais.indd 9

27/08/2011 21:57:51

10

| INTRODUO PESQUISA OPERACIONAL

O autor agradece aos Professores Heleno do Nascimento Santos da UFV, Alosio de Castro Gomes Jnior e Marcone Jamilson Freitas Souza da UFOP, respectivamente, pela autorizao do uso do software PROLIN e dos manuais do Solver e do LINDO. Agradece, ainda, a aluna Monique de Medeiros Takenouchi do curso de Engenharia de Produo Mecnica da FEG UNESP pelo trabalho de adequao nos slides em PowerPoint, bem como ao mestrando Marco Aurlio Reis dos Santos pela reviso final do texto. Finalmente, o autor gostaria de agradecer ao revisor annimo, indicado pela Pr-Reitoria de Graduao da UNESP PROGRAD para avaliar o texto, pelas valiosas sugestes de melhoria, e a prpria PROGRAD, por meio do Programa de Apoio Produo de Material Didtico, ao viabilizar esta publicao.Guaratinguet, agosto de 2011.

Fernando Augusto Silva Marins

Prefaciais.indd 10

27/08/2011 21:57:51

1PESQUISA OPERACIONAL: ORIGENS, DEFINIES E REAS1.1. A PESQUISA OPERACIONAL E O PROCESSO DE TOMADA DE DECISO

Um profissional que assume uma funo em uma empresa logo se depara com situaes onde dever tomar algum tipo de deciso. medida que este profissional vai ascendendo na carreira, os problemas e as decises vo se tornando mais complexas e de maior responsabilidade. De fato, tomar decises uma tarefa bsica da gesto, nos seus vrios nveis, estratgico, gerencial (ttico) ou operacional, devendo ser entendido que o ato de decidir significa fazer uma opo entre alternativas de soluo que sejam viveis de serem aplicadas situao. Apesar de cada gestor ter o seu prprio procedimento de anlise e soluo de problemas, pode-se, em geral, estabelecer algumas etapas que, necessariamente, devem ser observadas, configurando o que se denomina de papel do decisor: a) Identificar o problema talvez seja a etapa mais difcil, pois, diferentemente dos livros, os problemas na prtica no esto, inicialmente, claros, definidos e delimitados. Aqui importante perceber quais so os demais sistemas que interagem com o sistema onde se insere o problema a ser tratado. fundamental se ter uma equipe de analistas multidisciplinar para o problema seja visto de prismas diferentes e isso seja incorporado na sua soluo; b) Formular objetivo(s) nesta etapa devem ser identificados e formulados (muitas vezes matematicamente) quais so os objetivos que devero ser atingidos quando da soluo do problema. Em alguns casos, podem-se ter vrios objetivos que podem ser qualitativos (por exemplo, satisfao do cliente), quantitativos (custo ou lucros) ou ainda conflitantes; c) Analisar limitaes na seqncia deve-se levantar quais so as restries que limitaro as solues a serem propostas. Comumente, essas limitaes dizem respeito ao atendimento de tempo/prazo, oramento,

Cap_1.indd 11

27/08/2011 21:51:26

12

| INTRODUO PESQUISA OPERACIONAL

demandas, capacidades (transporte, produo e armazenamento), tecnologia (equipamentos e processos), inventrios (matria-prima, subconjuntos, work in process e produtos acabados), entre outros; d) Avaliar alternativas aqui, o decisor, aps identificar quais so suas alternativas de ao, dever, utilizando algum pr