View
219
Download
4
Embed Size (px)
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