Apostila Pesquisa operacional

Universidade Federal de Viosa Departamento de Informtica

Prof. Mauro Nacif Rocha Prof. Luiz Aurlio Raggi

Prof. Heleno do Nascimento Santos

Fevereiro de 2005

INF-280 Pesquisa Operacional I

Contedo: Programao Linear

Programao em Redes

ii

ASPECTOS GERAIS DA PESQUISA OPERACIONAL ........................................................................................ 1 EXEMPLOS DE ALGUNS PROBLEMAS COMUNS DA P.O............................................................................................... 5

PARTE I PROGRAMAO LINEAR ................................................................................................................. 8 EXEMPLOS DE MODELOS PARA ALGUNS PROBLEMAS CLSSICOS DE PROGRAMAO LINEAR .................................. 13 PROBLEMAS PARA MODELAGEM ............................................................................................................................ 17 SOLUO DE UM PROBLEMA DE PROGRAMAO LINEAR INTERPRETAO GEOMTRICA ...................................... 19 CASOS ENCONTRADOS NA RESOLUO GRFICA ................................................................................................... 23

O MTODO SIMPLEX.......................................................................................................................................... 27 MODELO MATEMTICO E FORMA PADRO DE UM PPL............................................................................................. 27 DEFINIES BSICAS ............................................................................................................................................. 30 TEOREMAS FUNDAMENTAIS ................................................................................................................................... 35 O ALGORITMO SIMPLEX ........................................................................................................................................ 37 ALGORITMO SIMPLEX MTODO DAS DUAS FASES ................................................................................................ 47

ELEMENTOS DE PS-OTIMIZAO................................................................................................................ 53 MUDANA NO VETOR C.......................................................................................................................................... 55 MUDANA NO VETOR B.......................................................................................................................................... 56 DUALIDADE .......................................................................................................................................................... 57

PARTE II PROGRAMAO EM REDES......................................................................................................... 63 INTRODUO ........................................................................................................................................................ 63

INTRODUO TEORIA DE GRAFOS ............................................................................................................ 65 UMA BREVE HISTRIA DA TEORIA DOS GRAFOS ..................................................................................................... 65 CONCEITOS BSICOS DA TEORIA DE GRAFOS.......................................................................................................... 68

FLUXOS EM REDE ............................................................................................................................................... 74 FORMULAO GERAL (CLSSICA) PARA PROBLEMAS DE FLUXOS EM REDE ............................................................. 75 O PROBLEMA DE FLUXO DE CUSTO MNIMO (PFCM).............................................................................................. 79 O PROBLEMA DE TRANSPORTE (PT) ....................................................................................................................... 87 O PROBLEMA DE DESIGNAO (PD) ...................................................................................................................... 94 O PROBLEMA DO CAMINHO MAIS CURTO (PCMC) ............................................................................................... 100 O PROBLEMA DE FLUXO MXIMO (PFM) ............................................................................................................. 104 O PROBLEMA DA RVORE GERADORA MNIMA (AGM) ........................................................................................ 111 O PROBLEMA DE STEINER EM GRAFOS NO DIRECIONADOS .................................................................................. 115

REDES PERT / CPM............................................................................................................................................ 117 REDES PERT....................................................................................................................................................... 117 REDES PERT/CPM.............................................................................................................................................. 121

BIBLIOGRAFIA................................................................................................................................................... 125

1

Aspectos Gerais da Pesquisa Operacional

1. Introduo e Histrico

Durante a II Guerra Mundial, lderes militares da Inglaterra e dos Estados Unidos requisita-ram um grupo de cientistas de diversas reas de conhecimento para analisarem alguns problemas militares. Entre esses problemas citam-se: desenvolvimento, operao e localizao de radares, ge-renciamento e controle de navios de apoio, planejamento de ataques areos, lanamento de bombas contra submarinos, defesa das comunidades europias contra ataques areos inimigos, abastecimen-to de tropas com munies e alimentos, operaes de minerao, etc. A aplicao de mtodos ma-temticos e cientficos para ajudar as operaes militares foi chamada Operational Research ou Operations Research.

1759 (Quesney), 1874 (Walras)

Modelos primitivos de programao matemtica.

1873 (Jordan), 1896 (Minkowsky), 1903 (Farkas)

Bases matemticas para os modelos lineares.

1920 (Markov) Modelos dinmicos. 192* (peridicos de negcios e en-genharia industrial)

Sugestes inovadoras para controle econmico de esto-ques.

1920 (Erlang) Estudos pioneiros dos fenmenos das filas de espera. 1937 (Von Neumann), 1939 (Kan-torovich)

Modelos econmicos mais sofisticados.

1938 (RAF viabilidade dos siste-mas de radar)

Operational Research RESEARCH into (military) OPERATIONS

1940 (tomada da Frana pelos ale-mes)

Maior conquista da OR na II Guerra.

1947 (Dantzig) Primeira formulao abstrata de um problema de progra-mao linear.

a partir de 1947 Aplicaes na engenharia, economia, controle de estoque, anlise de trfego areo, agricultura, comunicao, plane-jamento rural e urbano, distribuio de energia e outros

Obs.: U.K. / Europa: Operational Research E.U.A.: Operations Research

2

2. Definio

Pesquisa Operacional o uso do mtodo cientfico com o objetivo de prover departamentos exe-cutivos de elementos quantitativos para a tomada de decises, com relao a operaes sob seu controle (Kittel, 1947).

A Pesquisa Operacional a aplicao do mtodo cientfico, por equipes multidisciplinares, a pro-blemas envolvendo o controle de sistemas organizados de forma a fornecer solues que melhor interessam a determinada organizao (Ackoff,1968).

Pesquisa Operacional uma metodologia de estruturar processos aparentemente no estruturados por meio da construo de modelos. Utiliza um conjunto de tcnicas quantitativas com o intuito de resolver os aspectos matemticos dos modelos (Ehrlich, 1991).

Hoje, o termo operations research, ou pesquisa operacional, significa um mtodo cientfico para tomada de deciso, que busca determinar como melhor planejar e operar um sistema, usual-mente sob condies que requerem alocao de recursos escassos.

3. A Metodologia da Pesquisa Operacional

Geralmente a atividade de uma equipe de P.O. envolve as seguintes fases:

identificao do problema; construo de um modelo; obteno da soluo; teste do modelo e avaliao da soluo; implantao e acompanhamento da soluo.

Deve-se salientar que tais fases no so distintas, superpondo-se e interagindo entre si, na tentativa de se obter uma melhor identificao entre o modelo e o real. Quando a pesquisa opera-cional usada para resolver um problema de uma organizao, o seguinte procedimento, poder ser seguido:

Passo 1 - Identificao e formulao do problema

Em primeiro lugar deve ser definido claramente o problema da organizao, incluindo a es-pecificao dos objetivos e as partes da organizao que devem ser estudadas antes que o problema possa ser resolvido.

Passo 2 - Observao do sistema

Dados devem ser coletados para estimar valores de parmetros que afetam o problema da organizao. Estes valores so usados para desenvolver e avaliar o modelo matemtico para o pro-blema.

Passo 3 - Formulao do modelo matemtico para o problema

Consiste no desenvolvimento do modelo matemtico para o problema. Geralmente, existem vrias tcnicas que podem ser aplicadas na soluo dos modelos matemticos. A tcnica adequada selecionada em funo das caractersticas do modelo representativo do problema. Algumas situa-es, no entanto, so to complexas que no existem modelos analticos tratveis que possam repre-

3

sent-las. Quando isso acontece possvel desenvolver modelos de simulao e usar a capacidade dos computadores para aproximar o comportamento desses sistemas