Programação Linear (Método do Gráfico)

Prévia do material em texto

Pesquisa Operacional
Instituto de Engenharia de Produção e Gestão 
Universidade Federal de Itajubá
Prof. Dr. José Arnaldo Barra Montevechi
Método Gráfico
Programação Linear (PL)
Solução do problema (método 
gráfico)
Possível para duas 
variáveis
Problema formulado para 
Giapetto
max Z = 3X1 + 2X2 
sujeito a:
2X1 + X2 ≤ 100 
X1 + X2 ≤ 80 
X1 ≤ 40 
X1 ≥ 0 
X2 ≥ 0 
Tempo de acabamento
Tempo de carpintaria
Demanda de soldados
Restrições:
Implicações implícitas da FO 
em PL
? A contribuição para a função objetivo 
de cada variável de decisão é 
proporcional ao valor da variável de 
decisão;
? A contribuição para a função objetivo 
para cada variável é independente dos 
valores de outras variáveis de decisão.
max Z = 3X1 + 2X2
Definição
?Região de solução para um problema de 
PL: é o conjunto de todos os pontos que 
satisfazem todas as restrições do 
problema.
Restrições:
2X1 + X2 ≤ 100 ok 2*40+20 ≤ 100
X1 + X2 ≤ 80 ok 40+20 ≤ 80
X1 ≤ 40 ok 40 ≤ 40
X1 ≥ 0 ok 40 ≥ 0
X2 ≥ 0 ok 20 ≥ 0
Giapetto: X1 = 40 X2 = 20 região de solução
Região de solução
Giapetto: X1 = 15 X2 = 70 não é região de solução
Restrições:
2X1 + X2 ≤ 100 ok 2*15+70 ≤ 100
X1 + X2 ≤ 80 não 15+70 > 80
X1 ≤ 40 ok 15 ≤ 40
X1 ≥ 0 ok 15 ≥ 0
X2 ≥ 0 ok 70 ≥ 0
Região de solução
região de solução
Pontos que atendem e onde será procurada
a solução ótima
Solução ótima
Ponto da região de solução, que leva ao maior
valor da função objetivo.
Região de solução
?A maioria dos problemas de PL, tem 
somente uma solução ótima;
?Alguns não tem solução ótima;
?Alguns tem infinitas soluções. 
Para o problema de Giapetto, solução ótima:
X1=20 e X2 = 60
Z = 3*20 +2*60 = 180
Solução ótima
Solução gráfica para o 
problema de 2 variáveis de 
decisão
?Um PL com 2 variáveis pode ser 
resolvido graficamente. 
?Nós sempre nomeamos as variáveis 
X1 e X2 e os eixos coordenados por 
X1 e X2.
Como plotar uma inequação
2X1+3X2 ≤ 6 (1)
3X2 ≤ 6 - 2X1
X2 ≤ 1/3*(6 - 2X1) = 2 - 2/3X1 (2)
O conjunto de pontos que 
satisfaz (1) e (2) cai sobre a 
reta ou abaixo dela
X2
X11
2
3
4
5
6
1 2 3 4 5 6
X2 = 2 - 2/3X1
Região onde:
2X1+3X2 ≤ 6
Região onde:
2X1+3X2 ≥ 6
Encontrando a região de solução 
do problema de Giapetto:
2X1 + X2 ≤ 100 
X1 + X2 ≤ 80 
X1 ≤ 40 
X1 ≥ 0 
X2 ≥ 0 
Para um 
ponto (X1, X2)
pertencer a região de
solução é preciso
satisfazer todas
estas inequações.
X1 e X2 ≥ 0, indicam o primeiro quadrante
X2
X120
40
60
80
100
120
20 40 60 80 100 120
(2)
(3)
(4)
A
B
C
D
E
F
G
H
Polígono DGFEH - região de solução
Região convexa simplex
Encontrando a solução 
ótima
?Após a identificação da região de solução, 
nós devemos procurar a solução ótima, que 
será o ponto da região que leva ao maior 
valor de:
Z = 3X1+2X2
?Para encontrar a solução ótima, nós 
precisamos desenhar uma linha sobre a 
qual todos os pontos levem ao mesmo valor 
de Z.
?Escolhe-se qualquer ponto da região de 
solução:
(20, 0): Z = 3X1+2X2 = 60
Assim (20, 0) cai sobre a reta:
Z = 3X1 + 2X2 = 60
X2 = 30 - 3/2X1
Encontrando a solução 
ótima
?3X1 + 2X2 = 60 
? tem coeficiente angular = -3/2
?Assim todas as retas 3X1+2X2 = constante 
terão o mesmo coeficiente angular.
Importante: uma vez desenhada a reta, 
podemos encontrar
todas as outras pelo movimento paralelo da reta
que desenhamos.
Encontrando a solução 
ótima
X2
X120
40
60
80
100
120
20 40 60 80 100 120
(4)(2)
(3)
A
B
C
D
E
F
G
H
X2 = 30 - 3/2 X1
Indica o ponto ótimo - G (20, 60)
Retas iso-lucro
Lucro de Giapetto 
?Z = 3*20 + 2*60 = 180
Quatro casos especiais em 
PL
?Sem solução (infeasibility);
?Sem fronteira (unboundedness);
?Redundância (redundancy);
?Múltiplas soluções (alternate optimal 
solutions).
X2
X1
20
40
60
80
100
120
20 40
0
60 80 100 120
CE
Sem solução
X1
X2
20
40
60
80
100
120
20 40 60 80 100 120
CE
Sem 
fronteira
X2
X1
20
40
60
80
100
120
20 40
0
60 80 100 120
CE
Redundância
X2
X1
20
40
60
80
100
120
20 40
0
60 80 100 120
CE
Múltiplas 
soluções
Resolva o exercício 1 do item 
4.4.1 pelo método gráfico
max Z = 5X1 + 2X2 
sujeito a:
X1≤ 3 
X2 ≤ 4 
X1 + 2X2 ≤ 9 
X1 ≥ 0 
X2 ≥ 0 
X2
X11
2
3
4
5
6
1 2 3 4 5 6
Método Gráfico
A B
C
D
E
Indicando ponto ótimo - C (3, 3)
Z = 21
Exercício
?Obter os gráficos dos problemas 
formulados anteriormente no item 4.3.2 
e o do problema 02 do item 4.4.1;
?Grupos de 2 participantes;
?Entregar o resultado para fazer parte da 
avaliação da disciplina.