PESQUISA OPERACIONAL Introdução

Professor Volmir Wilhelm Professora Mariana Kleina

PESQUISA OPERACIONAL Ementa

Revisão de Álgebra Linear. Modelos de Programação Linear. O Método Simplex. O Problema do Transporte. O Problema da Designação. Dualidade. Análise de Pós-Otimização.

Programa

Revisão de álgebra linear: Matrizes. Solução de sistemas de equações lineares. Espaços Vetoriais. Sistemas de inequações lineares. Convexidade. Modelos de programação linear: Modelos de Programação Linear. Solução gráfica. Teoremas fundamentais. Limitações da Programação Linear. Método Simplex: O Método Simplex. Forma padrão. Transformação de um problema geral para a forma padrão. Casos especiais. Método das duas fases. Problema do transporte: Exemplos de modelos de transporte. Obtenção da solução inicial. Obtenção da solução ótima. Casos especiais. Problema da designação: Exemplos de problemas de designação. Algoritmo da designação. Dualidade: Propriedades. Exemplos de formulação do dual. Teorema básico da dualidade. Teorema da folga complementar. Método Dual-Simplex. Interpretação econômica do problema dual. Análise de pós-otimização: Mudanças dos coeficientes de custos. Mudanças nos recursos. Mudanças nas restrições. Programação paramétrica.

Referências

Puccini, A.L., Pizzolato, N.D., Programação Linear, LTC, 1990

Wagner, H.M., Pesquisa Operacional, Prentice Hall do Brasil, 1986

Taha, Hamdy A., Pesquisa Operacional, 8a. Edição, São Paulo, Pearson, 2008

Lachtermarcher, Gerson. Pesquisa Operacional na Tomada de Decisões, 4a. Edição, São Paulo, Pearson, 2009

Griffin, Christopher, Linear Programming, 2009-2011

Sottinen, Tommi, Operations Research with GNU Linear Programming Kit, 2009

Software Livre

LpSolve - lp_solve_5.5.2.0_IDE_Setup.exe

2 2 Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina

A Pesquisa Operacional (PO) consiste no estudo de

métodos matemáticos, usualmente implementados

por programas de computador, que podem ser

utilizados para resolver problemas gerenciais

relacionados à tomada de decisão e controle de

sistemas.

PESQUISA OPERACIONAL

3 Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina

1) Problema de Designação: Decidir qual tarefa atribuir a cada máquina de modo a minimizar o

tempo total de execução.

2) Projeto de Rede: Decidir como ligar n cidades através de uma coleção de possíveis ligações de

forma a minimzar o custo total de interligação.

3) Agendamento de Pessoal: Determinar a programação da semana para o pessoal do hospital,

de modo a satisfazer as necessidades diárias, minimizando o número de pessoas envolvidas.

4) Teoria da decisão: Decidir qual laptop comprar considerando o preço, o peso e as

performances.

Problemas complexos de tomada de decisões que são abordados através de uma abordagem

de modelagem matemática (modelos matemáticos, algoritmos e implementações de

computador) (http://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.php)

PESQUISA OPERACIONAL

4 Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina

1. Modelagem, Simulação e Otimização

2. Programação Matemática

3. Processos Decisórios

4. Processos Estocásticos

5. Teoria dos Jogos

6. Análise de Demanda

7. Inteligência Computacional

http://www.abepro.org.br

PESQUISA OPERACIONAL

5 Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina

Principais características de problemas de tomada de decisão

• número de tomadores de decisão (quem decide?)

• número de objetivos (com base em que critérios?)

• nível de incerteza nos parâmetros (com base em qual informação?)

Vários tomadores de decisão ⇒ Teoria dos Jogos Vários objetivos ⇒ Programação Multi-objetivo Nível de incerteza > 0 ⇒ Programação Estocástica

http://home.deib.polimi.it/amaldi/teaching-materialFOR-10-11.php

PESQUISA OPERACIONAL

6 Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina

Principais etapas

• definir o problema

• construir um modelo

• conceber ou selecionar um método adequado

• desenvolver ou utilizar uma implementação eficiente

• analisar os resultados

Um modelo é uma representação simplificada da realidade.

Para definir um modelo precisamos identificar os elementos fundamentais do problema e as principais relações entre eles.

PESQUISA OPERACIONAL

7 Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina

Programação Matemática

Um problema de programação matemática tem por objetivo encontrar os valores para as variáveis de decisão que otimizam (maximizam ou minimizam) uma função objetivo respeitando um conjunto de restrições.

Tipos de modelos de programação matemática:

• Programação linear

• Programação inteira

• Programação não linear

• Programação dinâmica

• Programação binária

• Outros

PESQUISA OPERACIONAL

8 Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina

Programação Linear

É uma técnica de otimização bastante utilizada na resolução de problemas que tenham seus modelos representado por expressões lineares. Pela sua simplicidade e a possibilidade de aplicação em uma considerável diversidade de problemas, tornou-se um recurso bastante difundido.

Tem sido usada com sucesso na solução de problemas relativos à alocação de pessoal, mistura de materiais, distribuição, transporte, carteira de investimento.

PESQUISA OPERACIONAL

9 Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina

Programação Linear

• Administração da produção:

o Alocação de recursos limitados;

• Análise de investimentos;

• Logística:

o Custo de transporte;

o Localização de rede de distribuição;

• Alocação de recursos em marketing

PESQUISA OPERACIONAL

10 Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina

Origens

• Pesquisa Operacional: II Guerra Mundial - formulação e solução de modelos de programação linear em problemas de planejamento de operações militares

• Dantzig (1947): descoberta do método Simplex para a solução de problemas de programação linear,

PROGRAMAÇÃO LINEAR

11 Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina

Origens

• Maximizar ou minimizar uma função linear

• Sujeito a um conjunto de restrições lineares (igualdades ou desigualdades)

• Variáveis reais que podem assumir “qualquer” valor

PROGRAMAÇÃO LINEAR

12

0,...0

...

......

...

...minmax

1

11

11111

11

n

mnmnm

nn

nn

xx

bxaxa

bxaxa

xcxcZ

Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina

Principais etapas

• Definição do problema

• Construção do modelo - modelagem

• Solução do modelo

• Validação do modelo

• Implementação da solução

• Avaliação final

PROGRAMAÇÃO LINEAR

13 Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina

Modelagem

• Variáveis de decisão

• Função objetivo

• Restrições

PROGRAMAÇÃO LINEAR

14 Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina

Exemplo 1

Num teatro o espectador pode adquirir ingressos que dão direito a assento em cadeira ao custo de R$ 8,00, ou em poltrona ao custo de R$ 15,00. Sabendo que Ana Carolina gastou R$ 121,00 com 9 ingressos, quantos assentos de cada tipo comprou?

PS.: sem função objetivo

PROGRAMAÇÃO LINEAR

15 Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina

Exemplo 1 - variante

Num teatro o espectador pode adquirir ingressos que dão direito a assento em cadeira ao custo de R$ 8,00, ou em poltrona ao custo de R$ 15,00. Considere que o conforto de cada tipo de assento pode ser mensurado: 5 para cadeira e 7 para poltrona. Sabendo que Ana Carolina pode gastar R$ 121,00 e precisa comprar 9 ingressos, quantos assentos de cada tipo comprou?

PROGRAMAÇÃO LINEAR

16 Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina

Exemplo 2

Num centro de convenções o espectador pode adquirir ingressos que dão direito a assento em cadeira ao custo de R$ 8,00, ou em poltrona ao custo de R$ 15,00. O espectador também pode comprar assento em camarote ao valor de R$ 100,00. Sabendo que Guilherme Henrique gastou R$ 1.200,00 com 40 ingressos, quantos assentos de cada tipo comprou?

PS.: sem função objetivo

PROGRAMAÇÃO LINEAR

17 Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina

Exemplo 2 - variante

Num centro de convenções o espectador pode adquirir ingressos que dão direito a assento em cadeira ao custo de R$ 8,00, ou em poltrona ao custo de R$ 15,00. O espectador também pode comprar assento em camarote ao valor de R$ 100,00. Considere que o conforto de cada tipo de assento é assim mensurado: 5 para cadeira, 7 para poltrona e 20 para camarote. Sabendo que Guilherme Henrique pode gastar até R$ 1.200,00 e deseja comprar no máximo 40 ingressos, quantos assentos de cada tipo comprou sabendo que deseja maximizar o conforto?

PROGRAMAÇÃO LINEAR

18 Prof. Volmir Eugênio Wilhelm – Professora Mariana Kleina