Livro (Pesquisa Operacional)

Embed Size (px)

Text of Livro (Pesquisa Operacional)

APOSTILA DO CURSO

PESQUISA OPERACIONALProf. Erico Fagundes Anicet Lisboa, M. Sc. erico@ericolisboa.eng.br

Verso digital disponvel na internet http://www.ericolisboa.eng.br

RIO DE JANEIRO, RJ - BRASIL FEVEREIRO DE 2002

ii

NDICE

1. INTRODUO PESQUISA OPERACIONAL _________________________ 11.1 O Desenvolvimento da Pesquisa Operacional _________________________________________ 1 1.2 Modelagem ___________________________________________________________________ 1 1.3 Estrutura de Modelos Matemticos_________________________________________________ 2 1.4 Tcnicas Matemticas em Pesquisa Operacional_______________________________________ 2 1.5 Fases do Estudo de Pesquisa Operacional ____________________________________________ 31.5.1 Definio do problema ___________________________________________________________________ 3 1.5.2 Construo do modelo ___________________________________________________________________ 3 1.5.3 Soluo do modelo _____________________________________________________________________ 3 1.5.4 Validao do modelo ____________________________________________________________________ 3 1.5.5 Implementao da soluo________________________________________________________________ 4

2. LGEBRA LINEAR ______________________________________________ 52.1 Vetores ______________________________________________________________________ 52.1.1 Soma e subtrao de vetores ______________________________________________________________ 5 2.1.2 Vetores LD e LI________________________________________________________________________ 5

2.2 Matrizes _____________________________________________________________________ 62.2.1 Soma e subtrao de matrizes _____________________________________________________________ 6 2.2.2 Produto de matrizes _____________________________________________________________________ 7 2.2.3 Matrizes especiais ______________________________________________________________________ 8 2.2.4 A inversa de uma matriz _________________________________________________________________ 8

2.3 Sistemas de Equaes Lineares ____________________________________________________ 92.3.1 Mtodo algbrico por adio _____________________________________________________________ 10 2.3.2 Mtodo algbrico por substituio _________________________________________________________ 10 2.3.3 Mtodo de Gauss-Jordan ________________________________________________________________ 11

3. PROGRAMAO LINEAR________________________________________ 123.1 Definio____________________________________________________________________ 12 3.2 Formulao de Modelos ________________________________________________________ 12 3.3 Exemplo ____________________________________________________________________ 13 3.4 Soluo Grfica_______________________________________________________________ 13

iii

4. O MTODO SIMPLEX ___________________________________________ 154.1 Exemplo de um Problema _______________________________________________________ 15 4.2 Desenvolvimento do Mtodo Simplex ______________________________________________ 18 4.3 Procedimento do Mtodo Simplex (Problemas de Maximizao) _________________________ 21 4.4 Outro Exemplo _______________________________________________________________ 21 4.5 Aspectos Matemticos Singulares _________________________________________________ 234.5.1 Minimizao de uma funo _____________________________________________________________ 23 4.5.2 Restries de limite inferior () ___________________________________________________________ 23 4.5.3 Restries de igualdade _________________________________________________________________ 23 4.5.4 Varivel irrestrita em sinal_______________________________________________________________ 23

4.5 Mtodo Simplex em Duas Fases __________________________________________________ 24

5. A FERRAMENTA SOLVER (EXCEL) _______________________________ 275.1 Definindo e Resolvendo um Problema______________________________________________ 27 5.2 Instalando o Solver____________________________________________________________ 30

6. O PROBLEMA DE TRANSPORTE__________________________________ 316.1 Um Exemplo de Problema de Transporte ___________________________________________ 31 6.2 Problema Clssico de Transporte _________________________________________________ 32 6.3 Mtodo de Stepping-Stone ______________________________________________________ 336.3.1 Soluo inicial________________________________________________________________________ 33 6.3.2 Processo iterativo______________________________________________________________________ 33

6.4 Dificuldades do Problema de Transporte ___________________________________________ 356.4.1 No balanceamento entre oferta e demanda __________________________________________________ 35 6.4.2 Solues mltiplas _____________________________________________________________________ 35

7. ANLISE DE REDES____________________________________________ 367.1 Conceitos Bsicos em Teoria dos Grafos ____________________________________________ 36 7.2 Problema de Fluxo Mximo _____________________________________________________ 37 7.3 Problema de Caminho Mnimo ___________________________________________________ 39

8. TEORIA DOS JOGOS____________________________________________ 448.1 Introduo __________________________________________________________________ 44 8.2 Jogos de Dois Jogadores e Soma Zero ______________________________________________ 45 8.3 Estratgias Mistas _____________________________________________________________ 46

9. RISCO E INCERTEZA ___________________________________________ 489.1 Conceito de Risco _____________________________________________________________ 48

iv

9.2 Critrios para Deciso sob Condies de Incerteza ____________________________________ 489.2.1 Critrio Maximin (ou Minimax) ___________________________________________________________ 49 9.2.2 Critrio Maximax (ou Minimin)___________________________________________________________ 50 9.2.3 Critrio de Hurwicz____________________________________________________________________ 50 9.2.4 Critrio de Savage _____________________________________________________________________ 51 9.2.5 Comparao Final _____________________________________________________________________ 52

BIBLIOGRAFIA__________________________________________________ 53

1 - Introduo pesquisa operacional

Pesquisa Operacional

CAPTULO 1INTRODUO PESQUISA OPERACIONAL1

1.1 O Desenvolvimento da Pesquisa Operacional Durante a Segunda Guerra Mundial, um grupo de cientistas foi convocado na Inglaterra para estudar problemas de estratgia e de ttica associados com a defesa do pas. O objetivo era decidir sobre a utilizao mais eficaz de recursos militares limitados. A convocao deste grupo marcou a primeira atividade formal de pesquisa operacional. Os resultados positivos conseguidos pela equipe de pesquisa operacional inglesa motivaram os Estados Unidos a iniciarem atividades semelhantes. Apesar de ser creditada Inglaterra a origem da Pesquisa Operacional, sua propagao deve-se principalmente equipe de cientistas liderada por George B. Dantzig, dos Estados Unidos, convocada durante a Segunda Guerra Mundial. Ao resultado deste esforo de pesquisa, concludo em 1947, deu-se o nome de Mtodo Simplex. Com o fim da guerra, a utilizao de tcnicas de pesquisa operacional atraiu o interesse de diversas outras reas. A natureza dos problemas encontrados bastante abrangente e complexa, exigindo portanto uma abordagem que permita reconhecer os mltiplos aspectos envolvidos. Uma caracterstica importante da pesquisa operacional e que facilita o processo de anlise e de deciso a utilizao de modelos. Eles permitem a experimentao da soluo proposta. Isto significa que uma deciso pode ser mais bem avaliada e testada antes de ser efetivamente implementada. A economia obtida e a experincia adquirida pela experimentao justificam a utilizao da Pesquisa Operacional. Com o aumento da velocidade de processamento e quantidade de memria dos computadores atuais, houve um grande progresso na Pesquisa Operacional. Este progresso devido tambm larga utilizao de microcomputadores, que se tornaram unidades isoladas dentro de empresas. Isso faz com que os modelos desenvolvido pelos profissionais de Pesquisa Operacional sejam mais rpidos e versteis, alm de serem tambm interativos, possibilitando a participao do usurio ao longo do processo de clculo. 1.2 Modelagem Um modelo uma representao de um sistema real, que pode j existir ou ser um projeto aguardando execuo. No primeiro caso, o modelo pretende reproduzir o funcionamento do sistema, de modo a aumentar sua produtividade. No segundo caso, o modelo utilizado para definir a estrutura ideal do sistema. A confiabilidade da soluo obtida atravs do modelo depende da validao do modelo na representao do sistema real. A validao do modelo a confirmao de que ele realmente representa o sistema real. A diferena entre a soluo real e a soluo proposta pelo modelo depende diretamente da preciso do modelo em descrever o comportamento original do sistema. Um problema simples pode ser representado por modelos tambm simples e de fcil soluo. J problemas mais complexos requerem modelos mais elaborados, cuja soluo pode vir a ser bastante complicada.

Prof. Erico Lisboa

1

http://www.ericolisboa.eng.br

1 - Introduo pesquisa operacional

Pesquisa Operacional

1.3 Estrutura de Modelos Matemticos Em um modelo matemtico, so includos trs conjuntos principais de elementos: (1) variveis de deciso e parmetros: variveis de deciso so as incgnitas a serem determinadas pela soluo do modelo. Parmetros so valores fixos no problema; (2) restries: de modo a levar em conta as limitaes fsicas do sistema, o modelo deve incluir restries que limitam as variveis de deciso a seus valores possveis (ou viveis); (3) funo objetivo: uma fun