Pesquisa Operacional - 97pg

  • View
    1.833

  • Download
    26

Embed Size (px)

Text of Pesquisa Operacional - 97pg

SUMRIO ORIGEM DA PESQUISA OPERACIONAL MODELAGEM MATEMTICA 1.1- Introduo .................................................................................................................. 1.2- Metodologia da PO ................................................................................................... 1.3- O Modelo de Programao Linear............................................................................. 1.4- Exemplos de Formulao de Modelos....................................................................... 1.5- Problemas Propostos ................................................................................................. 1.6- Soluo Grfica ......................................................................................................... II FUNDAMENTOS MATEMTICOS 2.1- Matriz ......................................................................................................................... 2.2- Sistema de Equaes Lineares ................................................................................... 2.3- Vetores no Plano e no Espao ................................................................................... 2.4- Combinao Linear .................................................................................................... 2.5- Independncia Linear ................................................................................................ 2.6- Soluo Bsica Vivel ............................................................................................... 2.7- Combinao Convexa ................................................................................................ 2.8- Conjunto Convexo ..................................................................................................... III MTODO SIMPLEX 3.1- Introduo .................................................................................................................. 3.2- Teoremas Fundamentais do Mtodo Simplex ........................................................... 3.3- Reduo de Um Problema de Programao Linear Forma Padro ........................ 3.4- Forma Cannica de Um Sistema ............................................................................... 3.5- Conceitos Bsicos do Mtodo Simplex ..................................................................... 3.6- Desenvolvimento do Mtodo Simplex ...................................................................... 3.7- Procedimento do Mtodo Simplex ............................................................................ 3.8- Anlise das Solues ................................................................................................. 3.9- Anlise Econmica .................................................................................................... 3.10- Mtodo do M Grande............................................................................................... 3.11- Mtodo das Duas Fases ........................................................................................... IV DUALIDADE 4.1- Introduo .................................................................................................................. 4.2- Estudo da Dualidade .................................................................................................. 4.3- Relaes Entre Primal e Dual .................................................................................... 4.4- Resumo Para Transformao Primal-Dual ................................................................ V ANLISE DE SENSIBILIDADE 5.1- Introduo .................................................................................................................. 5.2- Variaes nos Coeficientes da FO ............................................................................. 5.3- Variaes nas Quantidades dos Recursos................................................................... 5.4- Acrscimo de Varivel .............................................................................................. 5.5- Acrscimo de Restrio.............................................................................................. VI PROBLEMAS DE TRANSPORTES 6.1- Introduo................................................................................................................... 6.2- Modelagem do Problema de Transportes .................................................................. 6.3- Algoritmo do Problema de Transporte ...................................................................... 6.3.1- Obteno da Soluo Bsica Inicial ................................................................ 6.3.2- Algoritmo da Stepping-Stone....................................................................... 6.3.3- Clculo da Soluo tima Atravs do Problema Dual.................................... VII PROGRAMAO INTEIRA 7.1- Introduo I 01 04 04 06 07 10 17 19 29 29 30 32 33 33 33 34 34 35 35 35 36 38 39 47 50 50 51 57 58 60 60 60 66 66 67 67 68 70 72 75 79 79 79 81 82 87 89 92 92

1

7.2- Algoritmo de Bifurcao e Limite 7.2.1- Limite 7.2.2- Consideraes 7.2.3- Diagrama Esquemtico ANEXO 1- ESTUDO DE CASO: COMPOSIO DE FERTILIZANTES ANEXO 2- RESOLUO POR COMPUTADOR

92 94 94 94 95 103

2

ORIGEM E APLICAES DA PESQUISA OPERACIONALA Pesquisa Operacional (PO) uma cincia aplicada, formada por um conjunto de tcnicas que visa a determinao das melhores condies de aproveitamento dos recursos em uma situao na qual estejam sob restries, como a econmica, a material, a humana e a temporal. Sob o ponto de vista histrico, seu nome relativamente novo, de origem militar, sendo usado pela primeira vez na Gr-Bretanha, durante a Segunda Guerra Mundial. No comeo desse conflito, os organismos responsveis pela defesa daquele pas utilizaram o concurso de especialistas tais como fsicos, bilogos, matemticos para assessorar e contribuir no estudo e soluo de certos problemas que, geralmente, se consideravam de atribuies estritamente militar. Basicamente, as razes disto eram fundadas nos fatos da existncia de armamentos relativamente novos, mas sem o suficiente uso que permitisse medir a eficincia mxima dos mesmos e na necessidade urgente de alocar recursos escassos s vrias operaes militares e s atividades dentro de cada operao, de modo eficaz. Aplicando uma abordagem cientfica no tratamento de problemas estratgicos e tticos, foram resolvidos, com sucesso, problemas como a determinao do nmero mnimo de avies ingleses a serem mantidos em condies de fazer frente aos ataques alemes, a distribuio e localizao dos meios de defesa antiarea ao longo da ilha, a determinao da melhor profundidade para explodir as bombas lanadas dos avies contra os submarinos inimigos, entre outros. Os cientistas chamados para fazer pesquisa em operaes militares (da o nome Pesquisa Operacional), aps a guerra desenvolveram diversas outras aplicaes. Depois de 1950, a PO invadiu a rea industrial e encontrou seu aliado natural: o Computador. Depois do computador, a PO se expandiu de uma maneira extraordinria e problemas cada vez mais complexos e com grande nmero de variveis e equaes puderam ser solucionados. Na dcada de sessenta tinha a mesma divulgao e fascnio tambm obtidos por outras tcnicas, tal como a Gesto pela qualidade Total os tem obtido nas dcadas de oitenta e noventa. Hoje, o campo de atuao da PO bastante amplo, se estendendo desde o setor industrial, na produo de matrias-primas e bens de consumo, at o setor de servios e s aplicaes de interesse social como as relacionadas sade e educao. Existem diversas reas em que a PO vem sendo aplicada com sucesso para racionalizar recursos, reduzir custos e aumentar lucros. Dentre elas temos: Dosagem (ou Mistura) Investimentos Financeiros o Alimentao Anlise de Riscos de Crdito o Formulao de Raes Projeto de Investimentos, etc. o Fbrica de Adubos Alocao de Recursos o Ligas Metlicas Fbricas o Petrleo Fazendas (agropecuria), etc. o Minrios, etc. Localizao Transporte Localizao Industrial o Tamanho da Frota Localizao de Centrais Telefnicas o Roteamento, etc Localizao de Escolas, etc. Estoques, etc. 3

Os problemas de Misturas tem em comum o objetivo de se minimizar o custo do produto obtido pela mistura de diversas matrias-primas com diferentes custos e diferentes composies (qumica ou nutricional). As restries se referem participao dos componentes (ou nutrientes) no produto final. Este problema aplicado na pecuria para formular dietas de ruminantes a um custo mnimo atendendo exigncias de protenas e minerais e utilizando animais e alimentos disponveis em uma determinada regio. Assim como aplicado em dietas de animais, aplicado tambm na alimentao de pessoas utilizando alimentos disponveis e um pblico especfico, como por exemplo em hospitais, spas, escolas (merenda infantil), etc. Na indstria de fertilizantes a PO tem sido utilizada para formular diferentes tipos de composio a fim de otimizar o uso do nitrognio, fsforo e potssio que variam conforme as necessidades de cada cultura (algumas culturas absorvem determinados elementos da prpria natureza, outras necessitam receb-las ). Ver estudo de caso no Anexo I. Na indstria siderrgica aplicada a PO, por exemplo, para determinar quais minrios devem ser carregados no alto-forno de modo a se produzir, ao menor custo, uma liga de ao dentro de determinadas especificaes de elementos qumicos. J na indstria petrolfera, pode-se querer definir qual deve ser a mistura de petrleo a ser enviada para uma torre de craqueamento para produzir seus derivados (gasolina, leo, etc.) a um custo mnimo e considerando que os petrleos so de diversas procedncias e possuem composies diferentes. Na manufatura pode-se querer definir qual deve ser a composio de produtos a serem fabricados por uma empresa de modo que se atinja o lucro mximo, sendo respeitadas as limitaes ou exigncias do mercado comprador e a capacidade de produo da fbrica. Os problemas de transporte tm em comum o objetivo de minimizar o custo de todo o volume de transporte,