6.0 Técnicas para análise pelo método gráfico

Prévia do material em texto

Pesquisa Operacional Aplicada a 
Engenharia
Conteúdo da Seção
• Conceitos Fundamentais
– Otimização
– Soluções
• Soluções Viáveis e Inviáveis
• Soluções Ótimas
• Análise pelo Método Gráfico
– Variando o sinal da restrição
– Problema de Minimização
Problemas de Otimização
• Otimizar = maximizar ou minimizar
– Veja que o esforço de atingir exatamente um determinado
valor pode ser modelado como minimizar o quadrado da
diferença para este valor.
• Em problemas de otimização, busca-se maximizar ou
minimizar uma função, chamada de objetivo, que
depende de um número finito de variáveis de entrada.
• As variáveis de entrada podem ser:
– independentes uma das outras;
– relacionadas uma com as outras por meio de uma ou mais
restrições.
Programação Matemática
• Um problema de programação matemática é um
problema de otimização no qual o objetivo e as
restrições são expressos como funções
matemáticas e relações funcionais...








=








=
nnn
n
n
n
b
b
b
xxxg
xxxg
xxxg
xxxfz
:
),...,,(
:
),...,,(
),...,,(
 :a Sujeito
),...,,( :Otimizar
2
1
21
212
211
21
Variáveis de Decisão
• x1 , x2 , ... ,xn , são chamadas de Variáveis de Decisão.
• As variáveis de decisão representam valores e quantidades
relativas a itens que estão no centro do problema, e que
podemos escolher (decidir) livremente.
• As variáveis de decisão representam as opções que um
administrador têm para atingir um objetivo:
– Quanto produzir para maximizar o lucro?
– Quanto comprar de uma ação para minimizar o risco da carteira?
– Como distribuir bônus ou participação nos lucros aos funcionários
para maximizar a satisfação e o comprometimento do time?
Programação Linear
• Um problema de programação matemática é
linear se a função-objetivo e cada uma das
funções que representam as restrições forem
lineares, isto é, na forma abaixo:
𝑓 𝑥1, 𝑥2, … , 𝑥𝑛 = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑛𝑥𝑛
E
𝑔𝑖 𝑥1, 𝑥2, … , 𝑥𝑛 = 𝑎𝑖1𝑥1 + 𝑎𝑖2𝑥2 +⋯+ 𝑎𝑖𝑛𝑥𝑛
Quebrando a Linearidade
• Qualquer expressão que não seja na forma citada 
anteriormente é não linear, como por exemplo:
ൠ
log𝑎 𝑥1
𝑎𝑥1
para qualquer valor de 𝑎!
𝑥1
𝑛 para 𝑛 ≠ 1
Programação Linear
Exemplos
1 2
1 2
1 2
1 2
. .
3 4 26
18 10 60
, 0
Max Z x x
s r
x x
x x
x x
= +
+ 
+ 

1 2
1 2
1 2
1 2
2
s.r.
2 3 30
200 20 500
, 0
Min Z x x
x x
x x
x x
= +
+ 
+ =

Programação Linear
Terminologia
• Solução
– No campo de Programação Linear é qualquer
especificação de valores para as variáveis de decisão,
não importando se essa especificação se trata de uma
escolha desejável ou permissível.
x1 = 2 ; x2 = 2 (2,2)S =
x1 = 3 ; x2 = 4 (3,4)S =
1 2
1 2
1 2
1 2
s.r.
3 4 26
18 10 60
, 0
Max Z x x
x x
x x
x x
= +
+ 
+ 

Classificação das Soluções
• Solução Inviável
– É uma solução em que 
alguma das restrições 
ou as condições de não-
negatividade não são 
atendidas.
• Solução Viável
– É uma solução em 
que todas as 
restrições são 
satisfeitas.
x1 = 2 ; x2 = 2
(2,2)S =
x1 = 3 ; x2 = 4
(3,4)S =
1 2
1 2
1 2
1 2
s.r.
3 4 26
18 10 60
, 0
Max Z x x
x x
x x
x x
= +
+ 
+ 

Solução Viável
Solução Inviável
Valor da Função-Objetivo
• É especialmente importante verificar como fica o 
valor da função-objetivo (Z) nas soluções viáveis 
que podemos determinar: (1,1)S = 2Z = (2,1)S = 3Z = (3,2)S =5Z =
1 2
1 2
1 2
1 2
s.r.
3 4 26
18 10 60
, 0
Max Z x x
x x
x x
x x
= +
+ 
+ 

A Solução Ótima
• A Solução Ótima é uma solução viável especial.
• Dentre todas as soluções viáveis, aquela(s) que
produzir(em) o valor da função-objetivo otimizado é
chamada de ótima.
• Existem diversas maneiras de determinar a solução ótima.
Em geral, para problemas lineares de pequeno porte como
todos que serão vistos neste curso, é usado o método
Simplex, em sua forma gráfica ou tabular.
• O método simplex está implementado em diversos
softwares, inclusive no Excel!
Programação Linear 
Solução Gráfica
• Quando o problema envolve apenas duas variáveis de
decisão, a solução ótima de um problema de programação
linear pode ser encontrada graficamente.
• Considere buscar a solução ótima para o problema abaixo:
1 2
1
2
1 2
1
2
4 2
. . 5
4
7
0
0
Max Z x x
s r x
x
x x
x
x
= +


+ 


Solução Gráfica – passos 
Primeiro Passo
• Antes de considerar 
qualquer restrição, todo o 
plano cartesiano é solução 
viável.
• Quando colocamos uma 
restrição recortamos uma 
parte do plano cartesiano: 
a parte que não atende à 
restrição.
1 0x 
Solução Gráfica – passos 1 0x 
Segundo Passo
▪ Considerando uma nova 
restrição, haverá um novo 
corte, reduzindo ainda 
mais o conjunto de 
soluções viáveis.
2 0x 
Solução Gráfica – passos 
1 5x 
1 0x 
Este conjunto que está se 
formando é chamado de 
região viável.
Observação
▪ As duas restrições de não 
negatividade definem, 
juntas, que a região viável 
está no primeiro 
quadrante.
▪ Como são condições 
comuns, geralmente a 
análise se concentra no 
primeiro quadrante.
Terceiro Passo
▪ Colocar a terceira 
restrição.
2 0x 
Solução Gráfica – passos 
1 5x 
1 0x 
Quarto Passo
▪ A última restrição que se 
refere a somente uma 
variável.
▪ Observe que a região 
viável não depende da 
ordem em que as 
restrições são analisadas.
2 0x 
2 4x 
Solução Gráfica – passos 
1 5x 
1 0x 
1 2 7x x+ 
2 0x 
2 4x 
Quinto Passo
▪ A última restrição 
relaciona as duas variáveis 
simultaneamente.
▪ Devemos primeiro 
representar a reta de 
suporte desta restrição:
▪ Depois escolher qual lado 
é viável ou não. Para 
tanto, escolha um ponto 
qualquer e substitua na 
restrição.
▪ Por exemplo, (0,0) 
pertence à região viável, 
pois 0 + 0 ≤ 7.
1 2 7x x+ =
Solução Gráfica – passos 
1 5x 
2 4x 
1 0x 
2 0x 
1 2 7x x+ 
▪ A região viável está 
totalmente definida
Quinto Passo
▪ Estudar a função objetivo 
dentro da região viável:
▪ Para um ponto qualquer, Z
é uma constante, e a sua 
expressão pode ser escrita 
como uma equação geral 
de reta:
1 24 2Z x x= +
2 12
2
Z
x x= −
Solução Gráfica – passos 
▪ Assim, para qualquer 
ponto, há um dado valor 
de Z, e 
Para cada valor de Z há 
uma reta que representa 
todos os pontos com este 
valor de Z
▪ No Ponto (0 , 0):
▪ E a reta é:
1 24 2
4 0 2 0
0
Z x x= +
=  + 
=
2 1
2 1
2
2
2
Z
x x
x x
= −
= −
Z = 0
Solução Gráfica – passos 
▪ Variando o valor de Z 
vemos como ela se 
desloca em função desta 
variação
▪ No Ponto (0 , 4):
▪ E a reta é:
1 24 2
4 0 2 4
8
Z x x= +
=  + 
=
2 1
2 1
2
2
4 2
Z
x x
x x
= −
= −
Z = 0 Z = 8
Solução Gráfica – passos 
▪ O valor de Z deve ser 
projetado na direção que 
otimiza (maximiza), de 
maneira a ainda estar em 
algum ponto da região 
viável
▪ Assim, no ponto (5 , 2) a 
função objetivo foi 
deslocada o máximo 
possível na direção em 
que é ótima.
▪ x1 = 5 e x2 = 2 é a solução 
ótima. E o valor da função 
objetivo é Z = 24
(máximo).Z = 0 Z = 8 Z = 20
Z = 24
(3 , 4)
(5 , 2)
Programação Linear 
Solução Gráfica - Exercício
• Considere o seguinte o problema de LP
• Encontrar a solução ótima usando o método 
gráfico
1 2
1 2
1 2
1 2
 =4 2
. . 2 3 143 2 12
 , 0
Max Z x x
s r x x
x x
x x
+
+ 
+ 

Solução Gráfica - Exercício
▪ Como o problema possui 
as condições de não 
negatividade, podemos já 
partir do primeiro 
quadrante
Solução Gráfica - Exercício
1 23 2 12x x+ 
Solução Gráfica - Exercício
▪ A interseção das duas 
retas suporte das 
restrições é o ponto
1 23 2 12x x+ 
1 22 3 14x x+ 
( )1,6;3,6
(1,6 , 3,6)
Solução Gráfica - Exercício
Z = 0
Z = 4,7
Z = 13,6
Z = 16
(1,6 , 3,6)
(4 , 0)
▪ Deslocando a função 
objetivo no sentido da 
maximização...
▪ Chegamos à solução 
ótima:
x1 = 4
x2 = 0
Z = 16
Variando o sinal da restrição
• Examinar a região viável e a solução ótima dos 
seguintes problemas:
1 2
1
2
1 2
1 2
 3
. . 8
 4
 2 8
 , 0
Max x x
s r x
x
x x
x x
+


+ 

1 2
1
2
1 2
1 2
 3
. . 8
 4
 2 8
 , 0
Max x x
s r x
x
x x
x x
+


+ 

O que a mudança em apenas um sinal de uma das 
restrições pode provocar?
Análise Gráfica
• Primeiro Passo: já considerando as restrições de não 
negatividade é possível partir de todo o primeiro 
quadrante do plano cartesiano. Neste plano, fazer os cortes 
das duas primeiras restrições, que são mais óbvias:
x1
x2
1 8x 
2 4x 
Análise Gráfica
• Segundo Passo: para a restrição que envolve simultaneamente 
as duas variáveis, deve-se começar determinando a reta 
suporte
– A reta suporte vai dividir a região viável em duas partes, uma delas 
deixará de fazer parte da região viável.
x1
1 22 8x x+ =
Reta Suporte da 3ª 
restrição (em 
ambos modelos):Região 2
Região 1
x2
Análise Gráfica
• Terceiro Passo: escolher a região em função do sinal da 
restrição. Para tanto, testa-se algum ponto de uma das 
regiões para verificar se ele está dentro ou fora da 
restrição.
x1
1 22 8x x+ 
Substituindo no 
ponto mais 
simples, x1 = 0 e
x2 = 0, verifica-se 
que a região viável 
é a Região 1Região 1
Primeiro
Modelo:x2
Análise Gráfica
• Terceiro Passo segundo modelo
x1
x2
Região 2
1 22 8x x+ 
Substituindo no 
ponto mais 
simples, x1 = 0 e
x2 = 0, verifica-se 
que a região viável 
é a Região 2
Segundo 
Modelo:
Análise Gráfica
• Quarto Passo: a inclinação da região viável e verificar 
em que ponto ela assume valor máximo
x1
No ponto (0,4):
Região Viável
Primeiro Modelo
x2
1 23 3 0 4 4Z x x= + =  + =
1 2 1 23 4 3Z x x x x= +  = +
Z=4
No ponto (8,0): 1 23 3 8 0 24Z x x= + =  + =
1 2 1 23 24 3Z x x x x= +  = +
Z=24
Análise Gráfica
• Quarto Passo
x1
x2
Região Viável
Segundo Modelo
No ponto (8,0): 1 23 3 8 0 24Z x x= + =  + =
1 2 1 23 24 3Z x x x x= +  = +
Z=24
No ponto (0,4): 1 23 3 0 4 4Z x x= + =  + =
1 2 1 23 4 3Z x x x x= +  = +
Z=4
No ponto (8,4): 1 23 3 8 4 28Z x x= + =  + =
1 2 1 23 28 3Z x x x x= +  = +
Z=28
Variando o sinal da restrição
• A mudança em apenas um sinal de apenas uma das restrições provocou:
– Alteração da região viável
– Alteração da solução ótima
• Para um determinado tipo de restrição (redundantes – definições no fim desta 
seção) que estas consequências nem sempre ocorrem
1 2
1
2
1 2
1 2
 3
. . 8
 4
 2 8
 , 0
Max x x
s r x
x
x x
x x
+


+ 

1 2
1
2
1 2
1 2
 3
. . 8
 4
 2 8
 , 0
Max x x
s r x
x
x x
x x
+


+ 

Modelo 1 Modelo 2
Solução ótima:
x1 = 8, x2 = 0, Z = 24
Solução ótima:
x1 = 8, x2 = 4, Z = 28
Variando o sinal da restrição
• Uma restrição também pode ser modelada com o 
sinal de igualdade;
– Neste caso, a região viável se resume a um segmento de 
reta.
1 2
1
2
1 2
1 2
 3
. . 8
 4
 2 8
 , 0
Max x x
s r x
x
x x
x x
+


+ =

x1
x2
1 8x 
2 4x 
Exemplo
Receita de Xarope
• Um farmacêutico fabrica um medicamento a partir de dois 
ingredientes naturais: xarope de alcachofra e xarope de 
boldo. Estes insumos são dados em unidades de 100ml que 
são combinadas com água para formar o medicamento 
final.
– Cada unidade do xarope de alcachofra tem 2 gramas de 
vitamina e 3 gramas de cinarina (composto de gosto amargo)
– Cada unidade do xarope de boldo tem 4 gramas de vitamina e 
1,5 grama de cinarina
• O medicamento precisa conter pelo menos 14 gramas de 
vitamina e não mais do que 12 gramas de cinarina
• Se cada unidade do extrato de alcachofra custa $4 e o de 
cinarina custa $3, e descartando o custo da água, como o 
medicamento pode ser feito com o menor custo total?
Receita de Xarope
• Quem decide?
• O que o decisor deve decidir?
• Com que objetivo ele deve tomar a decisão?
• Com que restrições a decisão será tomada?
– O farmacêutico
– Quantas unidades de cada xarope incluir no medicamento
– Chamemos de x1 e x2 o total de unidades de xarope de alcachofra e boldo,
respectivamente, que irão compor o medicamento.
–Minimizar o custo total
– Quantidade mínima de vitamina
– Quantidade máxima de cinarina
O Modelo para a 
Receita do Xarope
• Função-objetivo
– Minimizar o custo total
• Restrições
– Mínimo de Vitamina
– Máximo de Cinarina
– Não Negatividade
1 0x 2 0x 
e
1 2 4 3Min x x+
1 22 4 14x x+ 
1 23 1,5 12x x+ 
Problemas de Minimização
• O processo de resolução gráfica de um problema 
de minimização é análogo ao de maximização, 
isto é:
1. Utiliza as restrições para determinar a região viável 
(o conjunto de soluções viáveis).
2. Utiliza a função-objetivo para determinar qual dos 
vértices da região viável é solução ótima.
• A diferença é que a solução ótima levará a 
função-objetivo ao menor valor possível.
Problema de Minimização Solução Gráfica
Z = 24Z = 18Z = 10,5
1 23 1,5 12x x+ 
1 22 4 14x x+ 
(0 ; 3,5)
(0 ; 8)
(3 ; 2)
A opção mais barata é usar 
somente 3,5 unidades do 
xarope de boldo.
O custo total será de 
R$10,5.