Apostila de Pesquisa Operacional I - 57pg

Embed Size (px)

Text of Apostila de Pesquisa Operacional I - 57pg

  • APOSTILA DO CURSO

    PESQUISA OPERACIONAL

    Prof. 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 _________________________ 1 1.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____________________________________________ 3

    1.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 ______________________________________________ 5 2.1 Vetores ______________________________________________________________________ 5

    2.1.1 Soma e subtrao de vetores ______________________________________________________________5

    2.1.2 Vetores LD e LI________________________________________________________________________5

    2.2 Matrizes _____________________________________________________________________ 6

    2.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____________________________________________________ 9

    2.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________________________________________ 12 3.1 Definio____________________________________________________________________ 12

    3.2 Formulao de Modelos ________________________________________________________ 12

    3.3 Exemplo ____________________________________________________________________ 13

    3.4 Soluo Grfica_______________________________________________________________ 13

  • iii

    4. O MTODO SIMPLEX ___________________________________________ 15 4.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 _________________________________________________ 23

    4.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) _______________________________ 27 5.1 Definindo e Resolvendo um Problema______________________________________________ 27

    5.2 Instalando o Solver____________________________________________________________ 30

    6. O PROBLEMA DE TRANSPORTE__________________________________ 31 6.1 Um Exemplo de Problema de Transporte ___________________________________________ 31

    6.2 Problema Clssico de Transporte _________________________________________________ 32

    6.3 Mtodo de Stepping-Stone ______________________________________________________ 33

    6.3.1 Soluo inicial________________________________________________________________________ 33

    6.3.2 Processo iterativo______________________________________________________________________ 33

    6.4 Dificuldades do Problema de Transporte ___________________________________________ 35

    6.4.1 No balanceamento entre oferta e demanda __________________________________________________ 35

    6.4.2 Solues mltiplas _____________________________________________________________________ 35

    7. ANLISE DE REDES____________________________________________ 36 7.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____________________________________________ 44 8.1 Introduo __________________________________________________________________ 44

    8.2 Jogos de Dois Jogadores e Soma Zero______________________________________________ 45

    8.3 Estratgias Mistas _____________________________________________________________ 46

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

  • iv

    9.2 Critrios para Deciso sob Condies de Incerteza____________________________________ 48

    9.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

    Prof. Erico Lisboa 1 http://www.ericolisboa.eng.br

    CAPTULO 1

    INTRODUO PESQUISA OPERACIONAL 1

    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.

  • 1 - Introduo pesquisa operacional Pesquisa Operacional

    Prof. Erico Lisboa 2 http://www.ericolisboa.eng.br

    1.3 Estrut