Introdução à Pesquisa Operacional

Introdução à Engenharia de Produção

Nomes:

DATA

PESQUISA OPERACIONAL

Sumário PESQUISA OPERACIONAL INTRODUÇÃO .......................................................................................................................................... 3 HISTÓRIA ................................................................................................................................................. 3 O IMPACTO DA PESQUISA OPERACIONAL ............................................................................................... 3 MÉTODO DA PESQUISA OPERACIONAL ................................................................................................... 5 PROGRAMAÇÃO LINEAR.......................................................................................................................... 6 EXEMPLO DE PROGRAMAÇÃO LINEAR / FORMAÇÃO DE UM MODELO ................................................. 7 BIBLIOGRAFIA .......................................................................................................................................... 8

Página 2

PESQUISA OPERACIONAL

INTRODUÇÃO A Pesquisa Operacional é uma ciência aplicada voltada para a resolução de problemas reais. Tendo como foco a tomada de decisões, aplica conceitos e métodos de várias áreas científicas na concepção, planejamento ou operação de sistemas. A Pesquisa Operacional é usada para avaliar linhas de ação alternativas e encontrar as soluções que melhor servem aos objetivos dos indivíduos ou organizações. Através de desenvolvimentos de base quantitativa, a Pesquisa Operacional visa também introduzir elementos de objetividade e racionalidade nos processos de tomada de decisão, sem descuidar, no entanto, dos elementos subjetivos e de enquadramento organizacional que caracterizam os problemas.

HISTÓRIA A Pesquisa Operacional surgiu durante a Segunda Guerra Mundial, da necessidade de lidar com problemas de natureza logistica, tática e de estratégia militar de grande dimensão e complexidade. Para apoiar os comandos operacionais na resolução desses problemas, foram então criados grupos multidisciplinares de matemáticos, físicos e engenheiros e cientistas sociais. Esses cientistas não fizeram mais do que aplicar o método cientfico, que tão bem conheciam, aos problemas que lhes foram sendo colocados. Desenvolveram então a ideia de criar modelos matemáticos, apoiados em dados e fatos, que lhes permitissem perceber os problemas em estudo e simular e avaliar o resultado hipotético de estratégias ou decisões alternativas. O sucesso e credibilidade ganhos durante a guerra foram tão grandes que, terminado o conflito, esses grupos de cientistas e a sua nova metodologia de abordagem dos problemas se transferiram para as empresas que, com o "boom" econômico que se seguiu, se viram também confrontadas com problemas de decisão de grande complexidade. Em alguns países, em que prevaleceu a preocupação com os fundamentos teóricos, a Pesquisa Operacional se desenvolveu sob o nome de Ciência da Gestão ou Ciência da Decisão e em outros, em que predominou a ênfase nas aplicações, com o nome de Engenharia Industrial ou Engenharia de Produção.

O IMPACTO DA PESQUISA OPERACIONAL A Pesquisa Operacional tem tido um grande impacto crescente na administração de empresas nos anos recentes. Tanto o número quanto a variedade de suas aplicações continuam a crescer rapidamente. Algumas de suas técnicas envolvem idéias sofisticadas em ciências políticas, matemática, economia, teoria da probabilidade e estatística. Como também sendo usada

Página 3

PESQUISA OPERACIONAL

amplamente em outros tipos de organizações, inclusive negócios e indústria. Muitas indústrias, inclusive a de aviação e mísseis, automóveis, comunicações, computadores, energia elétrica, eletrônica, alimentos, metalúrgica, mineração, papel, petróleo e transporte, têm feito uso extensivo da pesquisa operacional. Mesmo instituições financeiras, agências governamentais e hospitais têm aumentado rapidamente o uso que fazem da pesquisa operacional. Alguns dos problemas que têm sido resolvidos por técnicas particulares de pesquisa operacional: •

•

•

•

•

• • •

PROGRAMAÇÃO LINEAR: tem sido usada com sucesso na solução de problemas relativos à alocação de pessoal, mistura de materiais, distribuição, transporte, carteira de investimento, avaliação da eficiência; PROGRAMAÇÃO DINÂMICA: tem sido aplicada também com sucesso a áreas como planejamento de despesas de publicidade, distribuição do esforço de vendas e programação de produção; TEORIA DAS FILAS: tem tido aplicação na solução de problemas relativos a congestionamento de tráfego, máquinas de serviços sujeitas à quebra, determinação do nível de uma força de serviço, programação do tráfego aéreo, projetos de represas, programação de produção e operação de hospitais; PROGRAMAÇÃO INTEIRA: que é uma forma de programação linear onde as variáveis podem apenas apresentar números inteiros. Tem sido utilizada na resolução de problemas de investimento dentre outros; PROGRAMAÇÃO MISTA: que é uma forma de programação linear onde as variáveis podem assumir valores binários, inteiros e contínuos, este modelo também é definido como otimização combinatória, enquadrando-se em problemas de dificuldades não polinomiais NP-HARD; PROGRAMAÇÃO NÃO LINEAR: modelo matemático onde a função objetivo, as restrições ou ambas, apresentam não linearidade em seus coeficientes. PROGRAMAÇÃO MULTIOBJETIVO: é uma forma de programação linear e não linear onde se analisa múltiplas funções objetivos; GOAL PROGRAMMING: que é uma extensão dos modelos de programação multiobjetivo, contendo vários modelos específicos para cada problema de decisão; contendo vários modelos específicos para cada problema de decisão;

Outras técnicas de pesquisa operacional, tais como teoria de estoque, teoria dos jogos, teoria dos grafos e simulação, também tem sido aplicadas com sucesso a(em) diversos contextos.

Página 4

PESQUISA OPERACIONAL

MÉTODO DA PESQUISA OPERACIONAL Dois eventos motivaram o rápido desenvolvimento da PO. O primeiro foi o desenvolvimento de um algoritmo simples para solucionar problemas de programação linear (isto é, problemas determinísticos de PO), denominado algoritmo simplex e proposto por George Dantzig em 1947. Tal algoritmo permitiu a resolução manual de diversos problemas de PO, especialmente aqueles de baixa complexidade. O segundo foi a proliferação dos microcomputadores e o rápido aumento em sua velocidade de processamento. Problemas de PO são usualmente modelados na forma de uma função objetivo (por exemplo, maximizar o lucro da empresa) e diversas restrições (associadas, por exemplo, à disponibilidade de matérias-primas, mão-deobra, etc.). A chave do algoritmo simplex está no formato da região limitada pelas restrições, comum a todos os problemas de PO, conforme verificado por Dantzig; tal região é denominada simplex. Quaisquer dois pontos selecionados no contorno de um simplex, quando unidos por uma linha, resultam em uma linha inteiramente contida dentro do simplex. A partir dessa constatação, a busca pela solução ótima em problemas de PO passou a ser limitada a pontos extremos da região simplex, o que permitiu o desenvolvimento de um algoritmo de baixa complexidade computacional por Dantzig. Os problemas determinísticos de PO podem ser classificados em duas categorias genéricas: problemas de programação (i) linear e (ii) não-linear. Somente os problemas de programação linear podem ser resolvidos pelo algoritmo simplex. Um problema qualquer de programação linear é um problema de otimização (isto é, busca pela melhor dentre várias situações, utilizando um critério pré-estabelecido de otimalidade), com as seguintes características (Bronson & Naadimuthu, 1997): o problema possui um conjunto de variáveis manipuláveis no procedimento de busca pelo ótimo; essas são as variáveis de decisão do problema. uma função objetivo compõe o critério de otimalidade, sendo escrita em termos das variáveis de decisão do problema. A função objetivo é uma função linear das variáveis de decisão, devendo ser maximizada ou minimizada. os valores assumidos pelas variáveis de decisão devem satisfazer um conjunto de restrições, que compõem a região de soluções viáveis do problema. as variáveis de decisão podem assumir valores pré-estabelecidos no domínio dos números reais (isto é, valores positivos, negativos ou ambos). Assim, simplifica-se a pesquisa operacional em algumas etapas:

1. 2. 3. 4. 5.

Formulação do problema; Construção do modelo; Obtenção da solução; Teste do modelo e avaliação da solução; Implantação e acompanhamento da solução(manutenção).

Página 5

PESQUISA OPERACIONAL

As vantagens e desvantagens da utilização de modelos foram assim definidas: Vantagens • Emerge sob a forma gráfica, para representar a realidade aprendida em determinado momento; • Simplifica a visualização da amplitude das variáveis sem alterar a essência; • Ajuda a identificar várias relações possíveis entre os elementos da realidade; • Possibilita compreender relações complexas; • Serve como base para estabelecer e aprimorar parâmetros. Desvantagens • Limitações na identificação de todas as variáveis relevantes que influenciam em determinada situação; • Problemas na definição das propriedades a serem mensuradas e na especificação de procedimentos para tal; • Dificuldades no entendimento entre os provedores e os usuários da informação.

" A representação simplificada de um problema prático por meio de um modelo matemático permite que, sobre ele, se aplique técnicas e métodos que facilitam a obtenção de uma solução."

PROGRAMAÇÃO LINEAR Problemas de programação são modelados tal que o melhor uso de recursos escassos possa ser determinado, conhecidos os objetivos e necessidades do analista. Problemas de programação linear compõem uma sub-classe de problemas nos quais a modelagem é inteiramente expressa em termos de equações lineares. Parece intuitivo que para ser possível a solução de um dado problema através da programação linear, o problema deve ser, inicialmente, formulado em termos matemáticos, seguindo os passos a seguir: 1) Identifique as variáveis desconhecidas a serem determinadas (elas são denominadas variáveis de decisão) e represente-as através de símbolos algébricos (por exemplo, x e y ou e ). 2) Liste todas as restrições do problema e expresse-as como equações (=) ou inequações (≤, ≥) lineares em termos das variáveis de decisão definidas no passo anterior. 3) Identifique o objetivo ou critério de otimização do problema, representando-o como uma função linear das variáveis de decisão. O objetivo pode ser do tipo maximizar ou minimizar.

Página 6

PESQUISA OPERACIONAL

EXEMPLO DE PROGRAMAÇÃO LINEAR / FORMAÇÃO DE UM MODELO Suponha que uma empresa produza quatro modelos diferentes de brinquedos. Cada um deles gera uma quantidade de lucro diferente ao ser vendida. O brinquedo 1 gera ger R $10 de lucro, o 2 gera R$8, o 3 gera R$9 e o 4 gera R$7.. A função que determina o lucro da empresa é:

Assumindo que as variáveis são a quantidade de cada brinquedo que é vendida. Esta é uma função linear,, pois cada um dos termos da equação que a forma é uma constante ou um produto entre uma constante e um valor variável. Suponha agora que nós estamos interessados em descobrir qual é o maior lucro possível para esta empresa assumindo que o número máximo de vendas do brinquedo 1 é 100, do brinquedo 2 é 60, do brinquedo 3 é 40 e do brinquedo 4 é 70. Podemos então expressar este problema da seguinte forma: Máx

(Função Objetivo) (Restrição 1) (Restrição 2) (Restrição 3) (Restrição 4) (As variáveis de decisão são não-negativas) não

O que temos acima é um modelo de Programação Linear. Ele é formado sempre por uma função linear (que é a função objetivo) tivo) e por um conjunto de inequações inequações lineares (restrições do problema). No exemplo acima, desejamos obter o maior lucro possível (maior valor de Z). O objetivo da programação linear é justamente fornecer fornecer ferramentas para resolver o desafio de encontrar o maior ou o menor valor possível em uma função linear cujas variáveis possuem restrições. Assim, o problema geral de programação linear pode ser definido por: Maximizar (ou minimizar) a função objetivo; objeti

Sujeita as restrições;

a...

Página 7

PESQUISA OPERACIONAL

Considerando onsiderando que as variáveis de decisão assumem valores positivos. positivos

BIBLIOGRAFIA • http://www.sobrapo.org.br/o_que_e_po.php • http://www.dt.fee.unicamp.br/~valente/capt1_044.pdf • http://pt.wikipedia.org/wiki/Pesquisa_operacional • http://www.producao.ufrgs.br/arquivos/disciplinas/382_po_apostila_completa_mais_livro.pdf • http://pt.wikibooks.org/wiki/Pesquisa_operacional/Introdu%C3%A7%C3%A3o_%C3%A0_Program a%C3%A7%C3%A3o_Linear

Página 8