View
30.573
Download
0
Category
Preview:
Citation preview
Pesquisa Operacional 1
FACULDADE PITÁGORAS– Engenharia de Produção –
Disciplina: Pesquisa Operacional 1:
AULA2: Solução Gráfica de Problemas de PL
Prof. Msc. Joabe Silva
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
O método da solução gráfica.1
Exemplos.2
SUMÁRIOExercícios.3
2
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
3
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
4
Os problemas de Pesquisa Operacional, quando esboçam uma relação linear entre as variáveis de decisão, são chamados de Problemas de Programação Linear (PL).
Dentre as diversas possibilidades de problemas de PL, aqueles que são baseados em apenas 2 variáveis de decisão (x1 e x2), podem ser solucionados pelo Método Gráfico.
Este método caracteriza-se pela busca da solução ótima do problema de PL, dentro de uma região factível formada pela intersecção das retas geradas pelas inequações das restrições.
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
5
Como obter a solução gráfica?
1 º PASSO: Formulação do problema de pesquisa operacional.
DICAS:
Quando o problema citar que há um estoque para se utilizar, as restrições são do tipo (≤) pois não se pode consumir matéria-prima além do que se tem disponível no estoque. São as Restrições de Matéria-Prima;
Quando o problema citar que há um número existente de máquinas para produção, homens para trabalhar, veículos para transportar, dinheiro para investir e similares, as restrições são do tipo (≤) pois não se pode utilizar mais máquina para se produzir, além do que se tem. Não pode contar com mais operadores, além do que se tem. Não se pode transportar além da capacidade do caminhão. Enfim, todas Restrições de Capacidade de Produção;
Quando o problema citar quantidades necessárias para a produção ser aceitável (sucos, vitaminas, tintas, misturas em geral), as restrições são do tipo (≥) pois não se pode utilizar menos do que o exigido para se ter um produto de qualidade.
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
6
Como obter a solução gráfica?
2 º PASSO: Estabelecer os eixos do plano cartesiano xy.
Para trabalharmos com um padrão, o eixo vertical será a variável x2 (abscissas) e o eixo horizontal será a variável x1 (ordenadas).
Restrições obtidas no processo de formulação.
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
7
Como obter a solução gráfica?
3 º PASSO: Traçar as retas para cada restrição.
Restrições obtidas no processo de formulação.
Restrição 1Te
rmo
inde
pend
ente
O valor que não estiver associado a uma variável de decisão, é o ponto em que a reta intercepta o eixo vertical !
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
8
Como obter a solução gráfica?
3 º PASSO: Traçar as retas para cada restrição.
Restrições obtidas no processo de formulação.
Restrição 1
Para achar o ponto em que a reta intercepta o eixo horizontal, basta atribuir 0 (zero) para a variável na vertical (x2) , e obter o respectivo valor para x1.
3
6
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
9
Como obter a solução gráfica?
4 º PASSO: Esboçar o sentido da solução da inequação. Se for do tipo ≤ , a solução está para baixo ou para esquerda. Se for do tipo ≥ , a solução está para cima ou para a direita.
Restrição 1
3
6
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
10
Como obter a solução gráfica?
5 º PASSO: Repetir para todas as inequações.
Restrição 1
3
6
Restrição 2 6
4
Restrição 2
Restrição 1
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
11
Como obter a solução gráfica?
5 º PASSO: Repetir para todas as inequações.
Restrição 1
3
6
Restrição 2 6
4
Restrição 2
Restrição 1
Restrições de Negatividade
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
12
Como obter a solução gráfica?
6 º PASSO: Delimitar a região factível.
Restrição 1
Restrição 2
Restrições de Negatividade
Região Factível
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
13
Como obter a solução gráfica?
7 º PASSO: Traçar as retas da função objetivo.
Região Factível
Para isto, é necessário atribuir valores arbitrários para a função objetivo. Mas é claro que devem fazer sentido estes valores, caso contrário a reta ficará fora do gráfico. Para Z = 6
2
5
Como o objetivo é maximizar, esta reta demonstra que ainda se pode obter valores mais altos para as variáveis de decisão x1 e x2.
2
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
14
Como obter a solução gráfica?
7 º PASSO: Traçar as retas da função objetivo.
Região Factível
Para isto, é necessário atribuir valores arbitrários para a função objetivo. Mas é claro que devem fazer sentido estes valores, caso contrário a reta ficará fora do gráfico. Para Z = 9
5
Como o objetivo é maximizar, esta reta demonstra que ainda se pode obter valores mais altos para as variáveis de decisão x1 e x2.
3
2
2
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
15
Como obter a solução gráfica?
7 º PASSO: Traçar as retas da função objetivo.
Região Factível
Para isto, é necessário atribuir valores arbitrários para a função objetivo. Mas é claro que devem fazer sentido estes valores, caso contrário a reta ficará fora do gráfico. Para Z = 9
5
Observa-se que ao passo que se aumenta o valor da função objetivo as retas se deslocam para cima.
A seta em amarelo representa o vetor gradiente da função objetivo. Como a função é de maximização, o ponto ótimo está na direção que o vetor cresce, até o limite da região factível.
3
2
2
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
16
Como obter a solução gráfica?
7 º PASSO: Traçar as retas da função objetivo.
Região Factível
Para isto, é necessário atribuir valores arbitrários para a função objetivo. Mas é claro que devem fazer sentido estes valores, caso contrário a reta ficará fora do gráfico. Para Z = 9
5
Observa-se que ao passo que se aumenta o valor da função objetivo as retas se deslocam para cima.
A seta em amarelo representa o vetor gradiente da função objetivo. Como a função é de maximização, o ponto ótimo está na direção que o vetor cresce, até o limite da região factível.
x2*
x1*
PONTO ÓTIMO
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
17
Como obter a solução gráfica?
8 º PASSO: Encontrar os pontos ótimos.
Região Factível
Às vezes é fácil observar quais são os pontos ótimos de cara (em casos onde a restrição é uma reta sem inclinação). No caso deste exemplo, utiliza-se o método de geometria analítica para achar o ponto em que as duas retas se cruzam.
5
Observa-se que ao passo que se aumenta o valor da função objetivo as retas se deslocam para cima.
A seta em amarelo representa o vetor gradiente da função objetivo. Como a função é de maximização, o ponto ótimo está na direção que o vetor cresce, até o limite da região factível.
x2*
x1*
PONTO ÓTIMO
Sistema de equações formado pelas duas restrições
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
18
Região Factível
5
x2*
x1*
PONTO ÓTIMO
Sistema de equações formado pelas duas restrições
Pode-se ignorar as desigualdades.
Como obter a solução gráfica?
8 º PASSO: Encontrar os pontos ótimos.
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
19
Região Factível
5
x2*
x1*
PONTO ÓTIMO
Sistema de equações formado pelas duas restrições
Pode-se ignorar as desigualdades.
Como obter a solução gráfica?
8 º PASSO: Encontrar os pontos ótimos.
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
20
Região Factível
5
x2*
x1*
PONTO ÓTIMO
Sistema de equações formado pelas duas restrições
Pode-se ignorar as desigualdades.Toma-se uma das equações e substitui-se o primeiro valor ótimo encontrado.
Como obter a solução gráfica?
8 º PASSO: Encontrar os pontos ótimos.
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
21
Região Factível
5
PONTO ÓTIMO
Pontos Ótimos encontrados:
Para encontrar a solução do problema, basta substituir na equação da função objetivo:
Como obter a solução gráfica?
9 º PASSO: Encontrar a solução do problema (se for maximizar lucro, encontrar o lucro máximo, por exemplo).
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
22
Região Factível
5
PONTO ÓTIMO
Como obter a solução gráfica?
PASSO FUTURO: Encontrar a solução do problema pelo aplicativo Solver do Excel.
Microsoft Excel 12.0 Relatório de respostaPlanilha: [Solver_Exemplo_da_Aula.xlsx]Plan1Relatório criado: 28/02/2011 23:14:31
Célula de destino (Máx)Célula Nome Valor original Valor final$B$5 Z= x1 0 13,5
Células ajustáveisCélula Nome Valor original Valor final$B$4 Variáveis x1 0 3$C$4 Variáveis x2 0 1,5
RestriçõesCélula Nome Valor da célula Fórmula Status Transigência$D$10 LHS 24 $D$10<=$E$10 Agrupar 0$D$9 LHS 12 $D$9<=$E$9 Agrupar 0
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
23
EXEMPLO ADICIONAL:
Região Factível
PONTOS ÓTIMOS E RESULTADO:
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
24
EXEMPLO ADICIONAL: TENTE ENCONTRAR A MESMA SOLUÇÃO !!!
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
25
Quais são as situações possíveis em um problema de solução pelo método gráfico?
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
26
Quais são as situações possíveis em um problema de solução pelo método gráfico?
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
4. RESUMO
27
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
4. RESUMO
28
Nesta unidade você aprendeu a utilizar o método gráfico para resolver um problema de duas variáveis. Pelo método gráfico, cada restrição precisa ser representada em um gráfico formado pelos eixos das variáveis x1 e x2. A junção de todas as restrições forma o espaço de possíveis soluções.
Depois de encontrar o espaço de possíveis soluções é necessário assumir alguns valores para a função objetivo (z). Com esses valores, podemos traçar uma reta para cada valor de z e perceber para onde a função objetivo cresce. Conseqüentemente, é possível visualizar qual é a solução ótima graficamente. A solução ótima estará localizada em um dos vértices da região de possíveis soluções, ou seja, está localizada na interseção de duas retas. Para encontrar os valores de x1, x2 e conseqüentemente z, basta resolver um sistema de equações lineares com as duas retas que passam pelo ponto ótimo.
Na próxima aula você aprenderá a solucionar os problemas de Programação Linear por meio do aplicativo Solver do Excel. Tal ferramenta permitirá a solução de problemas mais complexos, com mais de 2 variáveis de decisão e com um número maior de restrições.
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
3. EXERCÍCIOS
29
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
1. O MÉTODO DA SOLUÇÃO GRÁFICA
30
EXEMPLOS ADICIONAIS: TENTE ENCONTRAR A SOLUÇÃO !!!
Inteligência Computacional Aplicada a Sistemas de Controle e Automação – Joabe Silva
Faculdade PitágorasEngenharia de Produção
Prof. Msc. Joabe Amaral
Pesquisa Operacional 1
FIM !!!
31
Recommended