Pesquisa Operacional

Pesquisa Operacional

(Parte 1 de 11)

Prof. Erico Fagundes Anicet Lisboa, M. Sc. erico@ericolisboa.eng.br

Versão digital disponível na internet http://www.ericolisboa.eng.br

RIO DE JANEIRO, RJ - BRASIL FEVEREIRO DE 2002

1. INTRODUÇÃO À PESQUISA OPERACIONAL1
1.1 O Desenvolvimento da Pesquisa Operacional1
1.2 Modelagem1
1.3 Estrutura de Modelos Matemáticos2
1.4 Técnicas Matemáticas em Pesquisa Operacional2
1.5 Fases do Estudo de Pesquisa Operacional3
1.5.1 Definição do problema3
1.5.2 Construção do modelo3
1.5.3 Solução do modelo3
1.5.4 Validação do modelo3
1.5.5 Implementação da solução4
2. ÁLGEBRA LINEAR5
2.1 Vetores5
2.1.1 Soma e subtração de vetores5
2.1.2 Vetores LD e LI5
2.2 Matrizes6
2.2.1 Soma e subtração de matrizes6
2.2.2 Produto de matrizes7
2.2.3 Matrizes especiais8
2.2.4 A inversa de uma matriz8
2.3 Sistemas de Equações Lineares9
2.3.1 Método algébrico por adição10
2.3.2 Método algébrico por substituição10
2.3.3 Método de Gauss -Jordan1
3. PROGRAMAÇÃO LINEAR12
3.1 Definição12
3.2 Formulação de Modelos12
3.3 Exemplo13
4. O MÉTODO SIMPLEX15
4.1 Exemplo de um Problema15
4.2 Desenvolvimento do Método Simplex18
4.3 Procedimento do Método Simplex (Problemas de Maximização)21
4.4 Outro Exemplo21
4.5 Aspectos Matemáticos Singulares23
4.5.1 Minimização de uma função23
4.5.2 Restrições de limite inferior (³)23
4.5.3 Restrições de igualdade23
4.5.4 Variável irrestrita em sinal23
4.5 Método Simplex em Duas Fases24
5. A FERRAMENTA SOLVER (EXCEL)27
5.1 Definindo e Resolvendo um Problema27
5.2 Instalando o Solver30
6. O PROBLEMA DE TRANSPORTE31
6.1 Um Exemplo de Problema de Transporte31
6.2 Problema Clássico de Transporte32
6.3.1 Solução inicial3
6.3.2 Processo iterativo3
6.4 Dificuldades do Problema de Transporte35
6.4.1 Não balanceamento entre oferta e demanda35
6.4.2 Soluções múltiplas35
7. ANÁLISE DE REDES36
7.1 Conceitos Básicos em Teoria dos Grafos36
7.2 Problema de Fluxo Máximo37
7.3 Problema de Caminho Mínimo39
8. TEORIA DOS JOGOS44
8.1 Introdução4
8.2 Jogos de Dois Jogadores e Soma Zero45
8.3 Estratégias Mistas46
9. RISCO E INCERTEZA48
9.2 Critérios para Decisão sob Condições de Incerteza48
9.2.1 Critério Maximin (ou Minimax)49
9.2.2 Critério Maximax (ou Minimin)50
9.2.3 Critério de Hurwicz50
9.2.4 Critério de Savage51
9.2.5 Comparação Final52

1 - Introdução à pesquisa operacional Pesquisa Operacional

Prof. Erico Lisboa 1 http://www.ericolisboa.eng.br

CAPÍTULO 1

INTRODUÇÃO À PESQUISA OPERACIONAL 1

1.1 O Desenvolvimento da Pesquisa Operacional

Durante a Segunda Guerra Mundial, um grupo de cientistas foi convocado na Inglaterra para estudar problemas de estratégia e de tática associados com a defesa do país. O objetivo era decidir sobre a utilização mais eficaz de recursos militares limitados. A convocação deste grupo marcou a primeira atividade formal de pesquisa operacional.

Os resultados positivos conseguidos pela equipe de pesquisa operacional inglesa motivaram os Estados

Unidos a iniciarem atividades semelhantes. Apesar de ser creditada à Inglaterra a origem da Pesquisa Operacional, sua propagação deve-se principalmente à equipe de cientistas liderada por George B.

Dantzig, dos Estados Unidos, convocada durante a Segunda Guerra Mundial. Ao resultado deste esforço de pesquisa, concluído em 1947, deu-se o nome de Método Simplex.

Com o fim da guerra, a utilização de técnicas de pesquisa operacional atraiu o interesse de diversas outras áreas. A natureza dos problemas encontrados é bastante abrangente e complexa, exigindo portanto uma abordagem que permita reconhecer os múltiplos aspectos envolvidos. Uma característica importante da pesquisa operacional e que facilita o processo de análise e de decisão é a utilização de modelos. Eles permitem a experimentação da solução proposta. Isto significa que uma decisão pode ser mais bem avaliada e testada antes de ser efetivamente implementada. A economia obtida e a experiência adquirida pela experimentação justificam a utilização da Pesquisa Operacional.

Com o aumento da velocidade de processamento e quantidade de memória dos computadores atuais, houve um grande progresso na Pesquisa Operacional. Este progresso é devido também à larga utilização de microcomputadores, que se tornaram unidades isoladas dentro de empresas. Isso faz com que os modelos desenvolvido pelos profissionais de Pesquisa Operacional sejam mais rápidos e versáteis, além de serem também interativos, possibilitando a participação do usuário ao longo do processo de cálculo.

1.2 Modelagem

Um modelo é uma representação de um sistema real, que pode já existir ou ser um projeto aguardando execução. No primeiro caso, o modelo pretende reproduzir o funcionamento do sistema, de modo a aumentar sua produtividade. No segundo caso, o modelo é utilizado para definir a estrutura ideal do sistema.

A confiabilidade da solução obtida através do modelo depende da validação do modelo na representação do sistema real. A validação do modelo é a confirmação de que ele realmente representa o sistema real. A diferença entre a solução real e a solução proposta pelo modelo depende diretamente da precisão do modelo em descrever o comportamento original do sistema.

Um problema simples pode ser representado por modelos também simples e de fácil solução. Já problemas mais complexos requerem modelos mais elaborados, cuja solução pode vir a ser bastante complicada.

1 - Introdução à pesquisa operacional Pesquisa Operacional

Prof. Erico Lisboa 2 http://www.ericolisboa.eng.br

1.3 Estrutura de Modelos Matemáticos Em um modelo matemático, são incluídos três conjuntos principais de elementos:

(1) variáveis de decisão e parâmetros: variáveis de decisão são as incógnitas a serem determinadas pela solução do modelo. Parâmetros são valores fixos no problema;

(2) restrições: de modo a levar em conta as limitações físicas do sistema, o modelo deve incluir restrições que limitam as variáveis de decisão a seus valores possíveis (ou viáveis);

(3) função objetivo: é uma função matemática que define a qualidade da solução em função das variáveis de decisão.

Para melhor ilustrar ao conjuntos acima, considere o seguinte exemplo:

"Uma empresa de comida canina produz dois tipos de rações: Tobi e Rex. Para a manufatura das rações são utilizados cereais e carne. Sabe-se que:

ü a ração Tobi utiliza 5 kg de cereais e 1 kg de carne, e a ração Rex utiliza 4 kg de carne e 2 kg de cereais; ü o pacote de ração Tobi custa $ 20 e o pacote de ração Rex custa $ 30; ü o kg de carne custa $ 4 e o kg de cereais custa $ 1; ü estão disponíveis por mês 10 0 kg de carne e 30 0 kg de cereais. Deseja-se saber qual a quantidade de cada ração a produzir de modo a maximizar o lucro."

Neste problema as variáveis de decisão são as quantidades de ração de cada tipo a serem produzidas. Os parâmetros fornecidos são os preços unitários de compra e venda, além das quantidades de carne e cereais utilizadas em cada tipo de ração. As restrições são os limites de carne e cereais e a função objetivo é uma função matemática que determine o lucro em função das variáveis de decisão e que deve ser maximizada.

1.4 Técnicas Matemáticas em Pesquisa Operacional

A formulação do modelo depende diretamente do sistema a ser representado. A função objetivo e as funções de restrições podem ser lineares ou não-lineares. As variáveis de decisão podem ser contínuas ou discretas (por exemplo, inteiras) e os parâmetros podem ser determinísticos ou probabilísticos.

O resultado dessa diversidade de representações de sistemas é o desenvolvimento de diversas técnicas de otimização, de modo a resolver cada tipo de modelo existente. Estas técnicas incluem, principalmente: programação linear, programação inteira, programação dinâmica, programação estocástica e programação não-linear. Programação linear é utilizada para analisar modelos onde as restrições e a função objetivo são lineares; programação inteira se aplica a modelos que possuem variáveis inteiras (ou discretas); programação dinâmica é utilizada em modelos onde o problema completo pode ser decomposto em subproblemas menores; programação estocástica é aplicada a uma classe especial de modelos onde os parâmetros são descritos por funções de probabilidade; finalmente, programação não-linear é utilizada em modelos contendo funções não-lineares.

Uma característica presente em quase todas as técnicas de programação matemática é que a solução ótima do problema não pode ser obtida em um único passo, devendo ser obtida iterativamente. É escolhida uma solução inicial (que geralmente não é a solução ótima). Um algoritmo é especificado para determinar, a partir desta, uma nova solução, que geralmente é superior à anterior. Este passo é repetido até que a solução ótima seja alcançada (supondo que ela existe).

1 - Introdução à pesquisa operacional Pesquisa Operacional

Prof. Erico Lisboa 3 http://www.ericolisboa.eng.br

1.5 Fases do Estudo de Pesquisa Operacional Um estudo de pesquisa operacional geralmente envolve as seguintes fases:

(1) definição do problema; (2) construção do modelo;

(3) solução do modelo; (4) validação do modelo; (5) implementação da solução.

Apesar da seqüência acima não ser rígida, ela indica as principais etapas a serem vencidas. A seguir, é apresentado um resumo da cada uma das fases.

1.5.1 Definição do problema A definição do problema baseia-se em três aspectos principais:

ü descrição exata dos objetivos do estudo; ü identificação das alternativas de decisão existentes; ü reconhecimento das limitações, restrições e exigências do sistema.

A descrição dos objetivos é uma das atividades mais importantes em todo o processo do estudo, pois a partir dela é que o modelo é concebido. Da mesma forma, é essencial que as alternativas de decisão e as limitações existentes sejam todas explicitadas, para que as soluções obtidas ao final do processo sejam válidas e aceitáveis.

1.5.2 Construção do modelo

A escolha apropriada do modelo é fundamental para a qualidade da solução fornecida. Se o modelo elaborado tem a forma de um modelo conhecido, a solução pode ser obtida através de métodos matemáticos convencionais. Por outro lado, se as relações matemáticas são muito complexas, talvez se faça necessária a utilização de combinações de metodologias.

1.5.3 Solução do modelo

O objetivo desta fase é encontrar uma solução para o modelo proposto. Ao contrário das outras fases, que não possuem regras fixas, a solução do modelo é baseada geralmente em técnicas matemáticas existentes.

No caso de um modelo matemático, a solução é obtida pelo algoritmo mais adequado, em termos de rapidez de processamento e precisão da resposta. Isto exige um conhecimento profundo das principais técnicas existentes. A solução obtido, neste caso, é dita "ótima".

1.5.4 Validação do modelo

Nessa altura do processo de solução do problema, é necessário verificar a validade do modelo. Um modelo é válido se, levando-se em conta sua inexatidão em representar o sistema, ele for capaz de fornecer uma previsão aceitável do comportamento do sistema.

Um método comum para testar a validade do sistema é analisar seu desempenho com dados passados do sistema e verificar se ele consegue reproduzir o comportamento que o sistema apresentou.

1 - Introdução à pesquisa operacional Pesquisa Operacional

(Parte 1 de 11)

Comentários