Apostila pesquisa operacional

Apostila pesquisa operacional

(Parte 1 de 4)

Universidade Federal de Viçosa Departamento de Informática

Prof. Mauro Nacif Rocha Prof. Luiz Aurélio Raggi Prof. Heleno do Nascimento Santos

Fevereiro de 2005

INF-280 Pesquisa Operacional I

Conteúdo:

Programação Linear Programação em Redes

ASPECTOS GERAIS DA PESQUISA OPERACIONAL1
EXEMPLOS DE ALGUNS PROBLEMAS COMUNS DA P.O5
PARTE I – PROGRAMAÇÃO LINEAR8
EXEMPLOS DE MODELOS PARA ALGUNS PROBLEMAS CLÁSSICOS DE PROGRAMAÇÃO LINEAR13
PROBLEMAS PARA MODELAGEM17
SOLUÇÃO DE UM PROBLEMA DE PROGRAMAÇÃO LINEAR – INTERPRETAÇÃO GEOMÉTRICA19
CASOS ENCONTRADOS NA RESOLUÇÃO GRÁFICA23
O MÉTODO SIMPLEX27
MODELO MATEMÁTICO E FORMA PADRÃO DE UM PPL27
DEFINIÇÕES BÁSICAS30
TEOREMAS FUNDAMENTAIS35
O ALGORITMO SIMPLEX37
ALGORITMO SIMPLEX – MÉTODO DAS DUAS FASES47
ELEMENTOS DE PÓS-OTIMIZAÇÃO53
MUDANÇA NO VETOR C5
MUDANÇA NO VETOR B56
DUALIDADE57
PARTE I – PROGRAMAÇÃO EM REDES63
INTRODUÇÃO63
INTRODUÇÃO À TEORIA DE GRAFOS65
UMA BREVE HISTÓRIA DA TEORIA DOS GRAFOS65
CONCEITOS BÁSICOS DA TEORIA DE GRAFOS68
FLUXOS EM REDE74
FORMULAÇÃO GERAL (CLÁSSICA) PARA PROBLEMAS DE FLUXOS EM REDE75
O PROBLEMA DE FLUXO DE CUSTO MÍNIMO (PFCM)79
O PROBLEMA DE TRANSPORTE (PT)87
O PROBLEMA DE DESIGNAÇÃO (PD)94
O PROBLEMA DO CAMINHO MAIS CURTO (PCMC)100
O PROBLEMA DE FLUXO MÁXIMO (PFM)104
O PROBLEMA DA ÁRVORE GERADORA MÍNIMA (AGM)1
O PROBLEMA DE STEINER EM GRAFOS NÃO DIRECIONADOS115
REDES PERT / CPM117
REDES PERT117
REDES PERT/CPM121

Aspectos Gerais da Pesquisa Operacional

1. Introdução e Histórico

Durante a I Guerra Mundial, líderes militares da Inglaterra e dos Estados Unidos requisitaram um grupo de cientistas de diversas áreas de conhecimento para analisarem alguns problemas militares. Entre esses problemas citam-se: desenvolvimento, operação e localização de radares, gerenciamento e controle de navios de apoio, planejamento de ataques aéreos, lançamento de bombas contra submarinos, defesa das comunidades européias contra ataques aéreos inimigos, abastecimento de tropas com munições e alimentos, operações de mineração, etc. A aplicação de métodos matemáticos e científicos para ajudar as operações militares foi chamada “Operational Research” ou “Operations Research”.

1759 (Quesney), 1874 (Walras) Modelos primitivos de programação matemática.

1873 (Jordan), 1896 (Minkowsky), 1903 (Farkas) Bases matemáticas para os modelos lineares.

1920 (Markov) Modelos dinãmicos.

192* (periódicos de negócios e engenharia industrial)

Sugestões inovadoras para controle econômico de estoques.

1920 (Erlang) Estudos pioneiros dos fenômenos das filas de espera.

1937 (Von Neumann), 1939 (Kantorovich) Modelos econômicos mais sofisticados.

1938 (RAF – viabilidade dos sistemas de radar)

Operational Research – RESEARCH into (military) OPERATIONS

1940 (tomada da França pelos alemães) Maior conquista da OR na I Guerra.

1947 (Dantzig) Primeira formulação abstrata de um problema de programação linear.

a partir de 1947 Aplicações na engenharia, economia, controle de estoque, análise de tráfego aéreo, agricultura, comunicação, planejamento rural e urbano, distribuição de energia e outros

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

2. Definição

“Pesquisa Operacional é o uso do método científico com o objetivo de prover departamentos executivos de elementos quantitativos para a tomada de decisões, com relação a operações sob seu controle” (Kittel, 1947).

“A Pesquisa Operacional é a aplicação do método científico, por equipes multidisciplinares, a problemas envolvendo o controle de sistemas organizados de forma a fornecer soluções que melhor interessam a determinada organização” (Ackoff,1968).

“Pesquisa Operacional é uma metodologia de estruturar processos aparentemente não estruturados por meio da construção de modelos. Utiliza um conjunto de técnicas quantitativas com o intuito de resolver os aspectos matemáticos dos modelos” (Ehrlich, 1991).

Hoje, o termo operations research, ou pesquisa operacional, significa “um método científico para tomada de decisão, que busca determinar como melhor planejar e operar um sistema, usualmente sob condições que requerem alocação de recursos escassos”.

3. A Metodologia da Pesquisa Operacional Geralmente a atividade de uma equipe de P.O. envolve as seguintes fases:

• identificação do problema; • construção de um modelo;

• obtenção da solução;

• teste do modelo e avaliação da solução;

• implantação e acompanhamento da solução.

Deve-se salientar que tais fases não são distintas, superpondo-se e interagindo entre si, na tentativa de se obter uma melhor identificação entre o modelo e o real. Quando a pesquisa operacional é usada para resolver um problema de uma organização, o seguinte procedimento, poderá ser seguido:

Passo 1 - Identificação e formulação do problema

Em primeiro lugar deve ser definido claramente o problema da organização, incluindo a especificação dos objetivos e as partes da organização que devem ser estudadas antes que o problema possa ser resolvido.

Passo 2 - Observação do sistema

Dados devem ser coletados para estimar valores de parãmetros que afetam o problema da organização. Estes valores são usados para desenvolver e avaliar o modelo matemático para o problema.

Passo 3 - Formulação do modelo matemático para o problema

Consiste no desenvolvimento do modelo matemático para o problema. Geralmente, existem várias técnicas que podem ser aplicadas na solução dos modelos matemáticos. A técnica adequada é selecionada em função das características do modelo representativo do problema. Algumas situações, no entanto, são tão complexas que não existem modelos analíticos tratáveis que possam repre- sentá-las. Quando isso acontece é possível desenvolver modelos de simulação e usar a capacidade dos computadores para aproximar o comportamento desses sistemas.

Passo 4 - Verificação do modelo e uso do modelo para predição

Verifica-se se o modelo matemático proposto para o problema é uma representação fidedigna da realidade. Os dados coletados durante a observação do problema podem ser usados para a validação do modelo na situação corrente.

Passo 5 - Selecionar uma alternativa aceitável

Dado o modelo do problema e um conjunto de alternativas (soluções viáveis) deve-se escolher aquela (se existir) que melhor atende aos objetivos da organização. Em alguns casos, a seleção da melhor alternativa possível é um problema de difícil solução e, nesses casos, aceita-se uma “boa” alternativa.

Passo 6 - Apresentação dos resultados e conclusões

A partir da definição do modelo e das alternativas determinadas para o problema são feitas as recomendações para os gerentes das organizações para que eles possam tomar as decisões que melhor atendem os objetivos buscados.

Passo 7 - Implementação e avaliação das recomendações

Se a organização aceita o estudo realizado e as recomendações feitas, parte-se para a fase de implementação da solução, a qual deve ser constantemente monitorada, e atualizada dinamicamente, fazendo-se mudanças quando necessárias.

4. Áreas de aplicação

Segundo trabalhos apresentados em reuniões da Sociedade Brasileira de Pesquisa Operacional (SOBRAPO), citam-se abaixo algumas áreas onde a P.O. foi aplicada com algum sucesso e onde se observa a grande variedade dessas aplicações:

• administração • agropecuária

• economia e planejamento econômico

• educação e saúde

• energia

• engenharia

• forças armadas

• investimentos e finanças

• localização-armazenamento-distribuição

• planejamento e controle da produção

• planejamento urbano e regional

• recursos hídricos

• siderurgia

• telecomunicações

• transporte

5. Técnicas aplicadas

Os trabalhos de PO desenvolvidos e submetidos para apresentação em congressos e para publicação revistas científicas envolvem a utilização das seguintes técnicas:

• Análise e previsão de séries temporais • Controle e qualidade

• Estatística

• Teoria dos grafos

• Otimização

• Programação matemática

• Processos estocásticos e teorias das filas

• Simulação

• Teoria da decisão e teoria dos jogos

Estas técnicas permitem que se resolva uma variedade enorme de problemas, dentre os quais são típicos:

• Alocação de recursos • Localização e distribuição da produção

• Estoque

• Substituição e reposição de equipamentos

• Seqüenciamento e coordenação de tarefas

• Determinação de caminhos em rede

• Situações de competição (teoria dos jogos)

• Busca de informação

• Roteamento de veículos

• Fluxos em rede

• Problemas de características híbridas

6. Surgimento e desenvolvimento da PO no Brasil

O início da P.O. no Brasil se deu aproximadamente uma década após sua implantação na

Grã-Bretanha e nos Estados Unidos. Assim, já nos meados da década de 50, professores com formação em Engenharia, Matemática e/ou Estatística, entusiasmados com as novas técnicas relacionadas a P.O. que aqui chegavam pela difusão natural do conhecimento humano, começaram a formar equipes de P.O. nas universidades e instituições de ensino (ITA, PUC, COPPE-UFRJ, UFPB, UNICAMP, UFSC, UFMG, UFV, etc.), reproduzindo-se e induzindo a formação de equipes em conjunto com as empresas (PETROBRÁS, ELETROBRÁS, USIMINAS, CSN, EMBRAPA, SOUZA CRUZ, TELEBRÁS, etc.), bem como a formação de consultorias nas grandes cidades.

Atualmente, vê-se com certo otimismo as perspectivas da P.O. no Brasil e, em particular, na Agricultura, Sistemas de Produção e Engenharia de Alimentos, baseando-se nos seguintes fatores:

• A crise como elemento propulsor (escassez de recursos);

• A explosão da informática;

• Massa crítica existente de analistas de P.O.;

• Integração universidade × empresa;

• Seminários de P.O. aplicada à agropecuária;

• Existência de cursos de P.O. nas universidades brasileiras;

• Cursos e pesquisas em andamento na COPPE, UNICAMP, UFPb, UFSc, EMBRAPA, etc.

Exemplos de Alguns Problemas Comuns da P.O. Problema do Caminho Mínimo (PCM)

Objetivos: determinar a rota de menor caminho (distância, tempo ou custo) existente entre um ponto de origem (cidade, endereço, computador, objeto etc.) e um ponto de destino.

Problemas de Localização de Facilidades

Objetivos: determinar a localização e capacidade das facilidades (restaurantes, depósitos, antenas de rádio etc.) de forma a suprir a demanda da região toda com um custo mínimo e/ou lucro máximo (considerando um determinado período). Cada facilidade possui normalmente um custo fixo de instalação e custos variáveis de operação.

Problema da Mochila

Rolando Caio da Rocha, um exuberante alpinista, está se preparando para uma longa escalada nos Alpes. Ele consegue levar até W quilos em sua mochila. Ele tem N diferentes tipos de itens que po- de incluir em seu fardo, e cada unidade de item j pesa wj quilos. Para cada item j, ele calculou um valor numérico Rj representando o valor de sobrevivência de cada unidade do item. Como exemplo, se ele levar cinco unidades do item 3 e sete unidades do item 9, o “valor” para ele desta seleção na mochila é 5R3 + 7R9. O problema do Rolando é escolher o número de cada tipo para incluir em sua mochila.

Escolha da Mistura para Rações

Grão 1 Grão 2 Grão 3 Necessidades mínimas

Nutriente A 2 3 7 1250

Nutriente B 1 1 0 250

Nutriente C 5 3 0 900

Nutriente D 0,6 0,25 1 232,5

$/peso 41 35 96

Objetivos: formular uma ração formada a partir da mistura dos grãos que atenda às necessidades mínimas e máximas de nutrientes e tenha um custo mínimo.

Bin-packing / Cutting Stock

Barra (bin) = 4100mm

Demanda (m) 3100 1930 1850 850 850 795 639

Fornecimento de Produtos através de uma Rede de Transportes

Fornecimentos disponíveis Necessidades de demanda

Usinas Depósitos

Sm Dn

Objetivos: determinar a quantidade do produto que cada fornecedor deve enviar para cada depósito, de forma que o custo total do transporte seja mínimo, que cada depósito tenha sua demanda atendida, e que nenhum depósito estoure sua capacidade de fornecimento.

Objetivos: determinar a quantidade mínima possível de barras para que sejam cortados todos os pedaços neces- sários para suprir a demanda.

Problemas de Produção

INSUMOSPRODUTOS

Recursos Especificações Atividades

Máquinas Ferramentas

Capital

Matéria prima Mão-de-obra

Decisões ⇔

Produto 1 Produto 2 . . Produto n

CUSTOSRECEITA

Objetivos: determinar as atividades que devem ser realizadas ou produzidas de forma a maximizar o lucro ou minimizar o custo de produção, levando-se em conta a quantidade máxima disponível para cada insumo.

O Problema de Designação (caso particular do problema de transporte)

Indivíduos ou máqui- nas (n)

Custos cij Tarefas a serem executadas (n)

11
22
33

Objetivos: minimizar o custo total para executar um conjunto de tarefas, onde cada tarefa deve ser executada por uma única máquina, e cada máquina executa uma única tarefa.

Parte I – Programação Linear

1. O significado da expressão “PROGRAMAÇÃO” ⇒ alocação de itens ou entidades “LINEAR” ⇒ relativo a funções, equações ou inequações lineares

2. O problema geral

Recursos escassos devem ser repartidos entre deman- das competitivas ⇔

Decisões são interligadas na tomada de decisão ⇔

Demandas competem entre si na procura dos recursos escassos

Objetivos:

• Otimizar a distribuição dos recursos limitados no atendimento às demandas competitivas; • Maximizar lucros ou o uso dos recursos;

• Minimizar custos, sobras, tempos ou distâncias.

3. Fases na solução de um problema de pesquisa operacional FLUXOGRAMA

4. Modelagem de problemas MODELOS SÃO REPRESENTAÇÕES DA REALIDADE

5. Modelos matemáticos

Os modelos matemáticos são modelos simbólicos - o sistema real é representado por EQUAÇÕES E EXPRESSÕES MATEMÁTICAS que descrevem suas propriedades relevantes.

n DECISÕES QUE SÃO QUANTIFICÁVEIS E INTERRELACIONADAS n VARIÁVEIS DE DECISÃO (x1, x2, … , xn)

FUNÇÃO OBJETIVO Z = f(x1, x2, … , xn)

6. Expressão matemática de um modelo de programação linear OBJETIVO

Determinar os valores das variáveis x1, x2, … , xn que otimizam (maximizam ou minimizam) a função linear

Z = c1 x1 + c2 x2 + … + cn xn, obedecendo às seguintes RESTRIÇÕES:

e de forma que as variáveis sejam NÃO NEGATIVAS, ou seja:

Temos que cj, aij e bi são constantes conhecidas, para todo i e todo j. Os parãmetros e variáveis do modelo são:

Z - Medida de eficiência do sistema (chamada de Função Objetivo ou F.O.); xj - Nível da atividade j (variável de decisão); cj - Taxa de contribuição unitária da atividade j; bi - Disponibilidade do recurso i; aij - Coeficiente tecnológico (quantidade i / consumido por j) n - Número de atividades no modelo; m - Número de restrições no modelo.

7. Construção de um modelo de programação linear ETAPAS A SEGUIR PARA CONSTRUIR UM MODELO DE PL 1. Definição das atividades

Definir as atividades (xj) e escolher uma unidade de medida para o seu nível. 2. Definição dos recursos

Determinar os recursos consumidos e escolher a unidade de medida conveniente.

3. Determinação das condições externas

Determinar a quantidade de recurso disponível (bi). 4. Cálculo dos coeficientes insumo/produção

Determinar a relação entre atividades e recursos (aij).

5. Construção do modelo

Associar x1, x2, … , xn às n atividades; Escrever as equações de balanceamento por recurso;

Indicar o uso dos recursos; Estabelecer a função objetivo como medida de eficiência.

Exemplos de Modelos para Alguns Problemas Clássicos de Programação Linear

Escolha da Mistura para Rações

Grão 1 Grão 2 Grão 3 Necessidades mínimas

Nutriente A 2 3 7 1250 Nutriente B 1 1 0 250 Nutriente C 5 3 0 900 Nutriente D 0,6 0,25 1 232,5 $/kg 41 35 96

Seja: x1 = qtde. (kg) do Grão 1 usada na ração x2 = qtde. (kg) do Grão 2 usada na ração x3 = qtde. (kg) do Grão 3 usada na ração

Custo total da ração: 41x1 + 35x2 + 96x3 Para atender às necessidades mínimas para cada nutriente, devemos ter:

1250,0 (Nutriente A)

250,0 (Nutriente B)

900,0 (Nutriente C)

232,5 (Nutriente D)

Queremos obter uma ração que tenha um custo mínimo. Portanto, o modelo completo fica assim:

Sujeito a:(Restrições)

Minimizar 41x1 + 35x2 + 96x3 (Função Objetivo ou F.O.)

1250,0 (Nutriente A)

250,0 (Nutriente B)

900,0 (Nutriente C)

232,5 (Nutriente D)

Problema de Produção

A empresa Nova Linha produz artigos de vidro de alta qualidade: janelas e portas, em três seções de produção:

Seção de Serralharia: para produzir as estruturas de alumínio Seção de Carpintaria: para produzir as estruturas de madeira Seção de Vidro e Montagem: para produzir vidro e montar as portas e janelas

Devido à diminuição dos lucros, o gerente geral decidiu reorganizar a produção, e propõe produzir só 2 produtos que têm uma melhor aceitação entre os clientes. Estes produtos são:

Produto 1: uma porta de vidro com estrutura de alumínio Produto 2: uma janela grande com estrutura de madeira

(Parte 1 de 4)

Comentários