Solucao grafica

Prévia do material em texto

Solução gráfica
Um problema de programação linear consiste em determinar valores 
não negativos para as variáveis de decisão, satisfazendo as restrições 
impostas de forma a otimizar (maximizar ou minimizar) a função linear. 
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. 
Porque somente até duas variaveis?Porque somente até duas variaveis?
No espaço de 2 dimensões uma igualdade representa
uma reta.
É importante perceber que cada desigualdade
representa uma área.
No espaço de 2 dimensões uma igualdade representa
uma reta.
É importante perceber que cada desigualdade
representa uma área.
Solução gráfica
As restrições de não negatividade x1 > 0 e x2 > 0 representam o 
primeiro quadrante do gráfico de soluções.
Solução gráfica
• Escolher qualquer solução (x,y) viável.
• Traçar o hiperplano definido pela função objetivo passando pelo 
ponto (x,y).
• Determinar o gradiente da função objetivo (Z) no ponto x.
• Caminhar no sentido e direção do gradiente da função objetivo ate 
tangenciar a região viável.
Exemplo – inequação
Representar graficamente a inequação: x1 + 2x2 > 10
1) Construir a reta correspondente à equação: x1 + 2x2 = 10 
Para traçarmos a reta, precisamos de dois pontos. :
2) Fazendo x1 = 0, teremos: 0 + 2x2 = 10 (substituímos x1 por 0), Assim, x2 = 5
Um dos pontos da reta será: x1 = 0 e x2 = 5, ou seja, o ponto (0, 5).
3) Agora fazendo x2 = 0. Então teremos: x1 + 2.0 = 10, x1 + 0 = 10, Assim, x1 = 10
O outro ponto da reta será: x1 = 10 e x2 = 0, ou seja, o ponto (10, 0).
4) A reta é então traçada. Podemos observar que há uma região 
sombreada no gráfico, que corresponde à região viável limitada pela 
inequação x1 + 2x2 > 10. A região viável, então, é aquela que se 
encontra na região superior da reta, pois a inequação define que 
x1 + 2x2 deve ser maior ou igual a 10.
Exemplo – inequação
5) Testar a inequação: x1 + 2x2 > 10
Consideremos o ponto x1 = 10 e x2 = 5. Substituindo na inequação (x1 + 2x2 > 10), 
teremos: 10 + 2.5 > 10 ou 20 > 10, o que é verdadeiro. Portanto, a região das 
soluções da inequação é aquela que contém o ponto testado.
6) Vamos ainda testar um ponto que não esteja na região sombreada, como o 
ponto de origem, ou seja, x1 = 0 e x2 = 0. Substituindo na inequação (x1 + 2x2 > 10), 
teremos: 0 + 2.0 > 10 ou 0 > 10, o que NÃO é verdadeiro. Portanto, este ponto e os 
outros que se encontram abaixo da reta não pertencem à região das soluções.
Solução gráfica
• Representação gráfica da inequação : x1+2x2≥10
• x1, x2 = x, y
• Transformando a inequação em equação :
• x1+2x2=10 -> Representando uma reta no plano cartesiano
• Para se ter uma reta são necessário dois pontos A (__,__) e 
B (__,__).
• Para A atribuir x1=0 e para B atribuir x2=0 -> A(0,__) e B(__,0).
• Substituir na equação x1+2x2=10, no ponto A, x1=0.
• 0+2x2=10 -> x2=5 -> A(0,5).
• Substituir na equação x1+2x2=10, no ponto B, x2=0.
• x1+0=10 -> x1=10 -> B(10,0).
Z x1 x2
Plano cartesiano x y
A 0 5
B 10 0
Solução gráfica
Porém, a reta representa a equação x1+2x2=10.
• Na inequação x1+2x2≥10 a solução ótima 
pode estar acima ou abaixo da linha no 
gráfico.
Dessa forma, temos que adotar um novo ponto para
testarmos onde está a solução ótima da inequação.
• Chamaremos esse ponto de E (1,1).
A (0,5)
B (10,0)
Solução gráfica
A (0,5)
B (10,0)
E (1,1)
Substituir as coordenadas de E ,a inequação
X1+2x2≥10.
Se a afirmação for verdadeira, quer dizer que a solução está da reta 
para baixo (para próximo ao ponto E).
O ponto E pertence a solução. Se a afirmação for falsa, quer dizer 
que o ponto não pertence a solução E a solução está acima da reta.
E (1,1), Substituindo na inequação x1+2x2≥10 teremos :
1+2 ≥10 -> 3 ≥10 FALSO
O ponto E não faz parte da inequação x1+2x2≥10.
• Logo a solução está acima da 
reta, na área rasurada.
• O conjunto solução está da 
reta, incluindo a reta, para 
cima.
Solução gráfica
Exercício 11
Representar graficamente a solução do sistema :
X1+3x2≤12
2x1+x2≥16
x1 ≥0
x2 ≥0
• Transformar as inequações em equações :
X1+3x2=12 -> A(0,__) e B(__,0)
2x1+x2=16 -> C(0,__) e D(__,0)
• Reta ①
X1+3x2=12 -> A(0,__) e B(__,0)
• 0+3x2=12 -> x2=4
• X1+0=12 -> x1=12
• Reta ②
2x1+x2=16 -> C(0,__) e D(__,0)
• 0+x2=16 -> x2=16
• 2x1+0=16 -> x1=8
Exercício 11
A(0,4) e B(12,0)
C(0,16) e B(8,0)
Exercício 11
Qual o conjunto solução das inequações?
• Adotar a coordenada E(1,1)
• Substituir as coordenadas de E nas inequações :
X1+3x2=12 
2x1+x2=16
• Se a afirmação for verdadeira, quer dizer que a solução está na reta para 
baixo (para próximo ao ponto E). O ponto E pertence a solução.
• Se a afirmação for falsa, quer dizer que o ponto não pertence a solução e a 
solução está acima da reta.
• Fazer esse procedimento para as duas inequações para encontrar o 
conjunto solução.
Exercício 11
Exercício 11
Reta ① :
X1+3x2 ≤12, E(1,1) -> 1+3.1 ≤12 - > 4 ≤12 VERDADEIRO
Reta ② : 
2x1+x2≥16, E(1,1) -> 2.1+1 ≥16 -> 3 ≥16 FALSO
Todos os pontos dentro do triangulo
verde pertencem ao conjunto Solução.
Seja o seguinte problema de programação linear: 
Função objetivo Zmax = 200x1 + 300x2
Restrições :
2x1+x2≤20
4x1 ≤32
x2 ≤10
x1≥0
x2 ≥0
Exercício 12
Variáveis de decisão :
X1 = quantidade de produto A1 a ser produzido
X2 = quantidade de produto A2 a ser produzido
Determina-se o conjunto de pontos (x 1, x 2) que satisfaçam as restrições. 
• 2x1+x2≤20
• 4x1 ≤32
• x2 ≤10
Os pontos que satisfazem todas as restrições estão na intersecção das 
regiões encontradas e é chamado de região viável ou conjunto dos pontos 
viáveis. .
Exercício 12
Estabelece-se alguns valores para a função Z e obtêm-se as suas curvas de nível. 
Por exemplo: 
200x1+300x2=600
200x1+300x2=1200
200x1+300x2=2400
200x1+300x2=3600
Substituindo o ponto (5,10) em
Zmax=200x1+300x2, valor que a função pode 
assume é 4000 (valor ótimo).
Exercício 12
Solução ótima 
(5,10) = (x1,x2)
Represente graficamente e determine, se existir, a solução ótima dos 
seguinte problema :
Função Objetivo Zmin = 30x1+20x2
Restrições :
4x1+x2≥20
X1+2x2 ≥10
x1 ≥2
x1 ≥0
x2 ≥0
Exercício 13
Resolva graficamente o modelo abaixo: Z (MAX) = 3x1 + 5x2
Restrições :
①x1 ≤ 4
②2x2 ≤ 12
③3x1 + 2x2 ≤ 18
④x1 ≥ 0
⑤x2 ≥ 0
Indique o espaço solução, o ponto ótimo e as restrições.
Exercício 13
①x1 ≤ 4 -> (0,0);(4,0)
②2x2 ≤ 12 -> (0,6);(0,0)
③3x1 + 2x2 ≤ 18 -> (0,9);(6,0)
④x1 ≥ 0
⑤x2 ≥ 0
E (1,1)
①x1 ≤ 4 -> 1 ≤4 OK
②2x2 ≤ 12 -> 2 ≤12 OK
③3x1 + 2x2 ≤ 18 -> 5 ≤18 OK
Exercício 13
①
②
③
Zmax=3x1+5x2
MMC (3,5)
15=3x1+5x2 -> (0,3);(5,0)
25=3x1+5x2 -> (0,5);(8,3,0)
30=3x1+5x2 -> (0,6);(10,0)
Ponto ótimo : (2,6)
Z=18+10=28
Exercício 13
Exercício 14
• Avaliar o desempenho da função objetivo :
Max Z=2x1+5x2
x1 ≥0 e x2 ≥0
Escolher um valor para o
lucro Z dentro da
área das restrições.
Exercício 14
Maximizar a função Z=2x1+5x2
Tenho que encontrar uma reta para a função objetivo.
Qual o MMC?
2x1+5x2=10 ;
2x1+5x2=20
2x1+5x2=10
A (0, _) e B ( _,0)
2x1+5x2=20
C (0,_) e D( _,0)
2x1+5x2=10 
A (0, 2) e B ( 5,0)
2x1+5x2=20
C (0,4) e D( 10,0)
Exercício 15
Resolva graficamente o modelo abaixo: (MAX) Z = −2x1 − 2x2
Restrições :
① 3x1 − 4x2 ≤ 18 -> (0,-18/4); (6,0)
② 8x1 − 3x2 ≤ −24 -> (0,8);(-3,0)
③ 6x1 + 8x2 ≤ 24 -> (0,3);(4,0)
④ 3x1 + 5x2 ≤ 21 -> (0,21/5);(7,0)
⑤ x1 ≤ 3 -> (3,0);(0,0)
⑥ x2 ≥ 0
Indique o espaço solução e o ponto ótimo.
Exercício 15Zmax = −2x1 − 2x2
MMC :
2=-2x1-2x2 -> (0,-1);(-1,0)
4=-2x1-2x2 -> (0,-2);(-2,0)
6=-2x1-2x2 -> (0,-3);(-3,0)
Ponto ótimo -> (-14,12,5)
Zmax= -2(-14)-2(12,5) =28-25=3 
Resolva graficamente o modelo abaixo: (MAX) Z = 2x1 + x2
Restrições :
① x2 ≤ 10 
②2x1 + 5x2 ≤ 60 
③x1 + x2 ≤ 18 
④3x1 + x2 ≤ 44 
⑤x1 ≥ 0 
⑥x2 ≥ 0 
Indique o espaço solução, o ponto ótimo e as restrições redundantes.
Exercício 16
① x2 ≤ 10 -> (0,10);(0,0)
②2x1 + 5x2 ≤ 60 -> (0,12);(30,0)
③x1 + x2 ≤ 18 -> (0,18);(18,0)
④3x1 + x2 ≤ 44 -> (0,44);(14,7)
Exercício 16
①
②
③
④
Z = 2x1 + x2
6=2x1+x2 -> (0,6);(3,0)
16= 2x1+x2 -> (0,8);(16/12)
31=2x1+x2 -> (13,5) (Ponto ótimo) 
Exercício 16
Exercício 17
Certa empresa de alimentos congelados processa batatas em embalagens de batatinha 
frita, picadinho de batata e flocos para purê. As batatas podem ser compradas de duas 
fontes, cada uma fornecendo lucros distintos. A empresa necessita determinar a 
quantidade de batata a ser comprada de cada fonte (x1 e x2), de forma a obter o maior 
lucro. Embora uma das fontes apresente o maior lucro, o aproveitamento das batatas de 
cada fonte se dá de forma diversa. Além disso, a empresa deve considerar o seu potencial 
de vendas, para cada um dos produtos.
O problema de programação linear a ser resolvido é: Maximizar Z = 5x1 + 6x2
Restrições :
2x1 + 3x2 < 18 (restrição para batatinha frita)
2x1 + x2 < 12 (restrição para picadinho)
3x1 + 3x2 < 24 (restrição para flocos)
x1 > 0, x2 > 0 (restrições de não-negatividade)
Batatinha frita:
2x1 + 3x2 = 18 -> (0,6); (9,0)
Menor igual a 18
Picadinho:
2x1 + x2 = 12 ->(0,12);(6,0)
Exercício 17
Menor igual a 12
Flocos:
3x1 + 3x2 = 24 -> (0,8);(8,0)
Exercício 17
Menor igual a 24
Determinar a região viável, ou seja, que contém todas as possíveis soluções para o sistema e onde todas as 
restrições (batatinha frita, picadinho, flocos) são respeitadas. Pode ser definida como a região comum a todas 
as restrições. 
Podemos observar que a restrição referente 
aos flocos não influencia a região de soluções. 
Esta região ficou delimitada pelas restrições da 
batatinha frita e do picadinho.
Pelo gráfico podemos constatar que a região viável é 
delimitada por quatro linhas que se encontram em 
quatro pontos. Três destes pontos podem ser facilmente 
verificados, e são: (0, 0), (6, 0) e (0, 6). 
O quarto ponto é aquele em que as retas correspondentes 
às restrições, da batatinha frita e do picadinho, se encontram. 
Sendo este ponto comum às duas retas, ele pode ser determinado 
resolvendo o sistema correspondente às duas retas.
2x1 + 3x2 = 18 (restrição para batatinha frita)
2x1+x2=12 (restrição para picadinho)
Se subtrairmos uma reta da outra, podemos eliminar uma das 
variáveis das equações, e então determinar a outra.
Exercício 17
Assim:
2x1 + 3x2 = 18
- (2x1 + x2 = 12)
0.x1 + 2x2 = 6 -> x2 = 6/2 -> x2 = 3
Substituindo x2 = 3 em qualquer uma das equações acima, obtemos x1.
2x1 + 3 . 3 = 18 -> 2x1 + 9 = 18 -> 2x1 = 18 – 9 -> 2x1 = 9 -> x1 = 9/2 -> x1 = 4,5
O ponto ÓTIMO é x1 = 4,5 e x2 = 3.
Exercício 17
Calcular o valor da função objetivo para cada um dos pontos da região 
viável.
A partir dos pontos da região viável, definidos anteriormente, podemos 
calcular o valor da função objetivo para cada ponto.
A função objetivo é dada pela equação Z = 5x1 + 6x2
(0, 0) ; (0, 0) = 5 . 0 + 6 . 0 = 0
(6, 0) ; (6, 0) = 5 . 6 + 6 . 0 = 30 + 0 = 30
(0, 6) ; (0, 6) = 5 . 0 + 6 . 6 = 0 + 36 = 36
(4,5, 3) ; (4,5 , 3) = 5 . 4,5 + 6 . 3 = 22,5 + 18 = 40,5 ( ponto ótimo )
Exercício 17
Portanto, a fim de obter o maior lucro, a quantidade de batata a ser 
comprada pela empresa de cada fonte é 4,5 e 3 (em unidades de peso). 
Exercício 17
Uma empresa fabrica 2 produtos. Na fabricação destes produtos, 2 insumos são
críticos,: as quantidades de matéria prima e a mão de obra disponíveis.
Produto 1 Produto 2 Disponibilidade
Matéria Prima A 70 kg/unidade 70 kg/unidade 4900 kg
Matéria Prima B 90 kg/unidade 50 kg/unidade 4500 kg
Mão de Obra Especializada P1 2 H-h/unidade 80 H-h
Mão de Obra Especializada P2 3 H-h/unidade 180 H-h
Lucro 20 R$/unidade 60 R$/unidade
Dada a grande procura, estima-se que todas as unidades a serem produzidas, dos 2
produtos, poderão ser vendidas. O objetivo da empresa é obter o maior lucro
possível com a produção e a venda das unidades dos produtos 1 e 2.
Exercício 18
Exercício 18
Exercício 18
Exercício 18
Exercício 18
Exercício 18
Exercício 18
Como todas as restrições foram traçadas temos o chamado Espaço Solução que é o conjunto de
todos os pontos candidatos a serem o ponto ótimo, ou seja, todos os pontos que “obedecem” a
todas as restrições do modelo.
Exercício 18
Exercício 18
Exercício 18
Exercício 18
(0,0)  Z=0
(40,0)  Z=800
(40,18)  Z=1880
(25,45)  Z=3200
(10,60)  Z=3800
(0,60)  Z=3600
O ponto ótimo é sempre um dos vértices do espaço solução ...... a não ser quando temos
múltiplas (infinitas) soluções ótimas, pois neste caso, os pontos ótimos são todos os
pertencentes a um dos lados do espaço solução.
Exercício 18
Z=4500
(x1*,x2*)
Exercício 18
400
60
(10,60)
(40,18)
(25,45)
(0,0)  Z=0
(40,0)  Z=800
(40,18)  Z=1880
(25,45)  Z=3200
(10,60)  Z=3800
(0,60)  Z=3600
Exercício 18
Ao resolver um problema de PL pode ocorrer uma das seguintes situações:
O problema tem uma 
única solução ótima
(2,6)=Z*
Exercício 18
Método Gráfico 
O problema tem 
múltiplas soluções 
(uma infinidade)
(2,6)=Z*
(4,3)=Z*
Exercício 18
O problema não 
tem ótimo finito
Exercício 18
Exercício 18
Considere o problema e resolva graficamente.
ZMax = 3x1 + 2x2
2x1 + x2 ≤ 100
x1 + x2 ≤ 80
x1 ≤ 40
x1≥ 0
x2 ≥ 0
Exercício 19
• ZMax = 3x1 + 2x2
• 60= 3x1 + 2x2 -> (0,30);(20,0)
• 120= x1 + 2x2 -> (0,60);(40,0)
• Ponto ótimo (20,60)
• Zmax= 3(20) + 2(60) ->180
Exercício 19
Z=60
Z=100
Considere o problema e resolva graficamente.
ZMax = 2x1 - x2
x1 - x2 ≤ 1 -> (0,-1);(1,0)
2x1 + x2 ≥ 6 -> (0,6);(3,0)
x1 ≥ 0
x2 ≥ 0
Exercício 20
• ZMax = 2x1 - x2
• 4=
Exercício 20
Para conseguir fundo para a festa de formatura, Jose, Roberto e João 
vão produzir 2 tipos brinquedos (A e B), cujos lucros por unidade são 
R$ 300,00 e R$ 400,00 respectivamente. Na linha de produção cada 
brinquedo passa por 3 etapas: Modelagem, Pintura e Acabamento. 
Jose , encarregado da modelagem , dispõe de 20 horas por semana , 
Roberto encarregado a pintura dispõe de 30 horas por semana e JOão
encarregado do acabamento dispõe de 16 horas semanais. Use os 
dados da tabela para determinar o lucro Maximo.
Exercício 20
x1 = n° de brinquedos do tipo A na semana
x2 =n° de brinquedos do tipo B na semana
Z max = 300x1+400x2
Restrições :
Modelagem : 2x1+1x2≤20
Pintura : 3x1+3x2 ≤30
Acabamento : 1x1+2x2 ≤16
Exercício 20
Modelagem : 2x1+1x2≤20 -> (0,20);(8,0)
Pintura : 3x1+3x2 ≤30 -> (0,10);(10,0)
Acabamento : 1x1+2x2 ≤16 -> (0,8);(16,0)
Exercício 20
3x1+3x2=30
1x1+2x2=16
Portanto :
X1= 4 e x2=6
Exercício 20
Zmax=2x1+3x2
4x1+6x2≤60
X1+x2≥12
x1≥0
x2≥0
Exercício 21
Zmax=2x1+3x2
6=2x1+3x2 -> (0,2);(3,0)
12=2x1+3x2 -> (0,4);(6,0)
24=2x1+3x2 -> (0,8);(12,0)
(7,7)->Zmax=2x1+3x2 
2(7)+3(7)=35
Exercício 21
ZMax = −2x1 − 2x2
3x1 − 4x2 ≤ 18
8x1 − 3x2 ≤ −24
6x1 + 8x2 ≤ 24 
3x1 + 5x2 ≤ 21 
x1 ≤ 3 
x2 ≥ 0 
Exercício 22
• ZMax = −2x1 − 2x2
• 4=−2x1 − 2x2 -> (0,-2);(-2,0)
• 6=−2x1 − 2x2 -> (0,-3);(-3,0)
• Ponto Ótimo (-8,9)
• Zmax=-2(-8)-2(9)=2
Exercício 22