Buscar

Programação Linear 04

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 29 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 29 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 29 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

ENP153 –Programação Linear
Aula 04 – Resolução gráfica de PPL
INTRODUÇÃO
 Um problema de programação linear consiste em
determinar valores não negativos para variáveis de
decisão, satisfazendo as restrições impostas de forma a
otimizar (maximizar ou minimizar) uma função, que é
linear
INTRODUÇÃO
 Para problemas que apresentam duas variáveis de
decisão, a solução ótima pode ser encontrada
graficamente
 Um problema com três variáveis também pode ser
resolvido graficamente, mas na maioria das vezes,
torna-se uma tarefa árdua
 A partir de quatro variáveis a resolução somente será
possível algebricamente
PASSOS PARA RESOLVER UM PPL
1° passo
•Definir o 
modelo de 
programação 
linear
2º passo
3º passo
4º passo
PASSOS PARA RESOLVER UM PPL
1° passo
•Definir o 
modelo de 
programação 
linear
2º passo
•Definir as 
curvas de 
restrições
3º passo
4º passo
PASSOS PARA RESOLVER UM PPL
1° passo
•Definir o 
modelo de 
programação 
linear
2º passo
•Definir as 
curvas de 
restrições
3º passo •Definir a curva de objetivo
4º passo
PASSOS PARA RESOLVER UM PPL
1° passo
•Definir o 
modelo de 
programação 
linear
2º passo
•Definir as 
curvas de 
restrições
3º passo •Definir a curva de objetivo
4º passo •Resolver o PPL
PASSOS PARA RESOLVER UM PPL
1° passo
•Definir o 
modelo de 
programação 
linear
2º passo
•Definir as 
curvas de 
restrições
3º passo •Definir a curva de objetivo
4º passo •Resolver o PPL
PASSO 1
𝜑 = max 𝑓 𝑥1, 𝑥2 = 200𝑥1 + 300𝑥2
𝑠. 𝑡.
R1: 2𝑥1 + 𝑥2 ≤ 20
R2: 4𝑥1 ≤ 32
R3: 𝑥2 ≤ 10
R4: 𝑥1, 𝑥2 ≥ 0
PASSOS PARA RESOLVER UM PPL
1° passo
•Definir o 
modelo de 
programação 
linear
2º passo
•Definir as 
curvas de 
restrições
3º passo •Definir a curva de objetivo
4º passo •Resolver o PPL
PASSO 2
 Inicialmente, determina-se o conjunto de pontos
𝑥1, 𝑥2 que satisfaçam as restrições
 Para isso, determinam-se os pontos no plano
cartesiano que satisfaçam cada uma das inequações
das restrições
 R1: 2𝑥1 + 𝑥2 ≤ 20
 Ao se atribuir valores para 𝑥1 e 𝑥2, a equação 2𝑥1 + 𝑥2
não pode resultar em valor superior a 20
 Deste modo, para se criar a curva de atendimento a
restrição, cria-se os pontos extremos da curva:
𝑝𝑎𝑟𝑎 𝑥1 = 0, 𝑥2 = 20
𝑝𝑎𝑟𝑎 𝑥2 = 0, 𝑥1 = 10
PASSO 2
PASSO 2
 R1: 2𝑥1 + 𝑥2 ≤ 20
 Ao se atribuir valores para 𝑥1 e 𝑥2, a equação 2𝑥1 + 𝑥2
não pode resultar em valor superior a 20
 Deste modo, para se criar a curva de atendimento a
restrição, cria-se os pontos extremos da curva:
𝑝𝑎𝑟𝑎 𝑥1 = 0, 𝑥2 = 20
𝑝𝑎𝑟𝑎 𝑥2 = 0, 𝑥1 = 10
PASSO 2
 O mesmo processo deve ser efetuado para R2, R3 e R4
 R2: 𝑥1 = 8
 R3: 𝑥2 = 10
 R4: 𝑥1 = 0, 𝑥2 = 0
PASSO 2
 Os pontos que satisfazem todas as restrições estão na
intersecção das regiões encontradas por R1, R2, R3 e
R4
 O conjunto de pontos que satisfazem todas as
restrições é chamado de região viável, ou zona de
viabilidade
PASSOS PARA RESOLVER UM PPL
1° passo
•Definir o 
modelo de 
programação 
linear
2º passo
•Definir as 
curvas de 
restrições
3º passo •Definir a curva de objetivo
4º passo •Resolver o PPL
PASSO 3
 Para se determinar, caso exista, um ponto 𝑥1
∗, 𝑥2
∗ que
pertence ao conjunto de pontos viáveis, de forma que a
função objetivo assuma o maior valor possível, deve-se
plotar as curvas de nível para 𝑓 𝑥1, 𝑥2
 Para se obter as curvas de nível, primeiro precisa-se
obter o vetor gradiente
PASSO 3
 O vetor gradiente de 𝑓 𝑥1, 𝑥2 é dado por:
𝛻𝑓 𝑥1, 𝑥2 =
𝜕𝑓
𝜕𝑥1
,
𝜕𝑓
𝜕𝑥2
 𝛻𝑓 𝑥1, 𝑥2 = 200, 300
PASSO 3
 As curvas de nível são criadas a partir da multiplicação
do vetor gradiente por valores escalares, de modo a
criar curvas paralelas ao 𝛻𝑓
𝐶𝑁 𝑘 = 𝑘 × 𝛻𝑓, 𝑜𝑛𝑑𝑒 𝑘 ∈ 𝑅
 𝐶𝑁 0.01 = 2, 3
 𝐶𝑁 0.02 = 4, 6
 ...
PASSO 3
PASSOS PARA RESOLVER UM PPL
1° passo
•Definir o 
modelo de 
programação 
linear
2º passo
•Definir as 
curvas de 
restrições
3º passo •Definir a curva de objetivo
4º passo •Resolver o PPL
PASSO 4
PASSO 4
último ponto a ser tocado 
pelas curvas de nível
SOLUÇÃO ÓTIMA
MÚLTIPLAS SOLUÇÕES ÓTIMAS
INFINITAS SOLUÇÕES ÓTIMAS
SOLUÇÃO ÓTIMA INFINITA
NÃO EXISTE SOLUÇÃO (INVIABILIDADE)
EXEMPLO
𝜑 = min𝑓 𝑥1, 𝑥2 = 30𝑥1 + 20𝑥2
𝑠. 𝑡.
R1: 4𝑥1 + 𝑥2 ≥ 20
R2: 𝑥1 + 2𝑥2 ≥ 10
R3: 𝑥1 ≥ 2
R4: 𝑥1, 𝑥2 ≥ 0

Outros materiais