Aula 02 - Metodo Grafico

Prévia do material em texto

Aula 2 – Método Gráfico 
Objetivos: 
Ao final desta aula, o estudante será capaz de: 
1. Encontrar a solução ótima de um modelo PL com duas variáveis via método 
gráfico. 
2. Classificar os modelos PL de acordo com o número de soluções. 
1.Introdução 
A Aula 1 mostrou que a modelagem via PL pode ser utilizada para modelar problemas de 
decisão relacionados a diversas áreas da Engenharia de Produção, como por exemplo 
planejamento da produção, logística e finanças. Nesta aula é apresentado o primeiro 
método de resolução de modelos PL, conhecido como método gráfico. Este método 
aplica-se apenas a modelos com duas variáveis de decisão. Apesar desta limitação, o 
método gráfico ajuda na compreensão do método Simplex, que é o método utilizado para 
resolução de modelos com mais variáveis e que será visto com detalhes em aulas 
posteriores. 
2.Tipos de solução em PL 
Antes da apresentação dos fundamentos do método gráfico, deve-se ter em mente os 
conceitos de solução viável, inviável e ótima. 
Uma solução de um modelo PL é dita solução inviável se não satisfaz pelo menos uma 
das restrições do problema. Já uma solução que satisfaz todas as restrições do problema, 
é dita ser uma solução viável. A solução viável que mais otimiza a função objetivo é dita 
ser uma solução ótima do problema. 
Estes conceitos são ilustrados voltando ao modelo PL do Exemplo 1.1 da Aula 1: 
 
𝑀𝑎𝑥 𝑧 = 20𝑥1 + 10𝑥2 
s.a.: 3𝑥1 + 2𝑥2 ≤ 90 
𝑥1 ≤ 25 
𝑥1 𝑥2 ≥ 0 
 
A solução 𝑥1 = 20 e 𝑥2 = 15 é uma solução viável para o problema, pois 
matematicamente satisfaz todas as restrições do problema: (3 × 20 + 2 × 15) ≤ 90,
20 ≤ 25,20 ≥ 0 e 15 ≥ 0. Já a solução 𝑥1 = 10 e 𝑥2 = 35 é inviável pois não 
satisfaz a primeira restrição do problema: 3 × 10 + 2 × 35 ≥ 90. 
A solução viável 𝑥1 = 20 e 𝑥2 = 15 gera o valor 𝑧 = 20 × 20 + 10 × 15 = 550 na 
função objetivo. Não podemos afirmar ainda se esta solução é ótima ou não pois não 
sabemos ainda se existe alguma outra solução viável que gere um maior valor para função 
objetivo. O método gráfico auxilia neste propósito, pois o mesmo encontra a solução 
ótima do problema. 
3. Aplicação do Método Gráfico 
A aplicação do método gráfico é feita em dois passos: 
1. Determinação da região de soluções viáveis. 
2. Obtenção da solução ótima. 
A descrição destes passos é feita com base no modelo do Exemplo 1.1 da Aula 1, já 
discutido nesta aula. 
Passo 1: determinação da região de soluções viáveis 
Neste passo, um plano cartesiano é desenhado em que a abscissa representa os possíveis 
valores para a variável 𝑥1 enquanto a ordenada representa os possíveis valores para a 
variável 𝑥2. O objetivo é encontrar no plano a região de soluções viáveis 𝐹 formada por 
todos os pares (𝑥1, 𝑥2) que satisfazem todas as restrições do modelo. 
Para encontrar a região 𝐹, obtém-se, para cada uma das restrições, a região no plano 
representada pelas soluções que satisfazem a restrição. Começando por exemplo pelas 
restrições de não negatividade 𝑥1 ≥ 0 e 𝑥2 ≥ 0. Estas duas restrições em conjunto sem 
considerar as demais, fazem com que a região de soluções viáveis 𝐹 seja todo o primeiro 
quadrante do plano, conforme mostra a Figura 2.1. 
 
Figura 2.1: Região de soluções viáveis 𝐹 considerando apenas as restrições de não negatividade 
A Figura 2.2 adiciona ao gráfico prévio a região associada a restrição 𝑥1 ≤ 25. 
Graficamente, traça-se uma reta vertical em 𝑥1 = 25 e, como o objetivo é pontos com 
abcissa menores ou iguais a 25, a região será formada por todos os pontos que estão sobre 
esta reta ou a esquerda da mesma. Durante o desenho desta região, deve-se lembrar de 
fazer uma interseção com a região determinada pelas restrições de não negatividade 
(Figura 2.1). 
 
 
Figura 2.2: Região de soluções viáveis 𝐹 considerando as restrições de não negatividade e 𝑥1 ≤ 25 
Finalmente, adiciona-se ao gráfico a região de soluções que falta, que é a região associada 
a restrição 3𝑥1 + 2𝑥2 ≤ 90. Para isso, inicialmente traça-se a reta 3𝑥1 + 2𝑥2 = 90. 
Esta reta passa pelos pontos (0,45) e (30,0). Esta reta também divide o plano em dois 
semiplanos e, os pontos de apenas um destes, satisfaz a desigualdade. Para saber qual é o 
semiplano viável, toma-se por exemplo o ponto (0,0) como ponto referência. Se este 
ponto satisfaz a desigualdade, então o semiplano em que ele pertence é o semiplano 
viável. Caso contrário, o viável é o outro lado. No exemplo, (0,0) satisfaz a restrição pois 
3 × 0 + 2 × 0 = 0, que é menor ou igual a 90. Logo, o semiplano viável é o que contém 
o ponto(0,0). É válido ressaltar que o ponto (0,0) foi escolhido arbitrariamente e, 
portanto, qualquer outro ponto poderia ter sido escolhido como ponto referência. Fazendo 
uma interseção com a região da Figura 2.2, tem-se a região de soluções viável final 𝐹. A 
Figura 2.3 mostra a região de soluções viáveis 𝐹 considerando todas as restrições do 
modelo. 
 
Figura 2.3: Região de soluções viáveis 𝐹 considerando todas as restrições 
A região de soluções viáveis 𝐹 é formada por todos os pontos internos e sobre as arestas 
do polígono com quatro lados cujos vértices são interseções de retas associadas a duas 
restrições dos problema. Tal polígono é destacado na Figura 2.4. 
 
Figura 2.4: Polígono que contorna a região de soluções viáveis 𝐹 
Pode-se encontrar as coordenadas de cada um destes vértices através da resolução de um 
sistema de equações do 1º grau. Por exemplo, o ponto 𝐶 é a interseção das retas associadas 
as restrições 3𝑥1 + 2𝑥2 ≤ 90 e 𝑥1 ≤ 25. Assim, as coordenadas de 𝐶 podem ser 
obtidas resolvendo o sistema: 
{
3𝑥1 + 2𝑥2 = 90
𝑥1 = 25 
 , 
cuja solução é 𝑥1 = 25 e 𝑥2 = 7,5. Todos os demais vértices são encontrados de maneira 
similar, obtendo 𝐴 = (0,0), 𝐵 = (25,0), 𝐶 = (25, 7,5) e 𝐷 = (0,45). 
 
 
De acordo com a definição 2.1, os pontos 𝐴, 𝐵, 𝐶, 𝐷 e (30,0) são pontos extremos do 
modelo. No entanto, o ponto (30,0) não está associado a uma solução viável do problema. 
Diz-se então que ele é um ponto extremo inviável, enquanto os demais pontos extremos 
são chamados de pontos extremos viáveis. 
Passo 2: obtenção da solução ótima 
A região de soluções viáveis 𝐹 obtida no passo anterior é composta de infinitos pontos. 
Assim, é necessário um método para encontrar qual destes pontos representa a solução 
ótima. 
Para encontrar a solução ótima, inicialmente é identificada a direção de crescimento da 
função objetivo 𝑧 = 20𝑥1 + 10𝑥2. Para isso, atribui-se valores para 𝑧 arbitrariamente e 
traça-se as retas associadas. Estas retas são chamadas de curvas de nível da função 
objetivo. Designando, por exemplo, 𝑧 = 200 e 𝑧 = 400, tem-se as retas 200 = 20𝑥1 +
10𝑥2 e 400 = 20𝑥1 + 10𝑥2. Tais retas estão desenhadas na Figura 2.5. 
Definição 2.1: os pontos que são interseção entre restrições de um modelo PL são 
chamados de pontos extremos. 
 
Figura 2.5: duas curvas de nível desenhadas 
Observa-se que as retas são paralelas e ambas tocam o conjunto de soluções. Assim, 
qualquer ponto pertencente ao conjunto de soluções viáveis 𝐹 e que ao mesmo tempo 
esteja sobre a reta 200 = 20𝑥1 + 10𝑥2 é uma solução viável com valor na função 
objetivo 𝑧 = 200. Raciocínio similar pode ser aplicado para a reta 400 = 20𝑥1 + 10𝑥2. 
Aumenta-se o valor de 𝑧 até a última reta que toca o conjunto de soluções viáveis ser 
encontrada. A Figura 2.6 mostra retas associadas a diversos valores de 𝑧, onde a reta com 
maior valor de 𝑧 e que toca o conjunto de soluções viáveis 𝐹 está destacada em negrito. 
 
Figura 2.6: Diversas curvas de nível do modelo 
A reta que toca o conjunto de soluções com maior valor de 𝑧 é a reta com 𝑧 = 575, ou 
seja é a reta 575 = 20𝑥1 + 10𝑥2. Tal reta toca o conjunto de soluções viáveis 𝐹 apenas 
no ponto extremo 𝐶 = (25, 7,5). Conclui-se que a solução ótima do problema é 𝑥1 = 25 
e 𝑥2 = 7,5, que gera umafunção objetivo 𝑧 = 575. 
Seguem agora os passos do método o gráfico para um novo exemplo. 
Exemplo 2.1 Considere o modelo: 
𝑀𝑖𝑛 𝑧 = 2𝑥1 + 𝑥2 
s.a.: −𝑥1 + 𝑥2 ≥ 3 
2,5𝑥1 + 𝑥2 ≥ 10 
𝑥2 ≤ 11 
𝑥1 , 𝑥2 ≥ 0 
 
Pede-se um gráfico com a região de soluções viáveis 𝐹, as coordenadas dos pontos 
extremos viáveis do modelo e a solução ótima do modelo via método gráfico. 
Solução: Primeiramente, é desenhado em um plano a região 𝐹 de soluções viáveis, ou 
seja, a região formada por todos os pontos (𝑥1, 𝑥2) que satisfazem todas as restrições do 
problema. Para isso, desenha-se a região de soluções viáveis de cada restrição, fazendo 
uma interseção entre estas. Para se desenhar a região associada a restrição 
2,5𝑥1 + 𝑥2 ≥ 10, por exemplo, desenha-se inicialmente a reta 2,5𝑥1 + 𝑥2 = 10. Esta 
reta é a que passa pelos pontos (𝑥1, 𝑥2) = (4,0) e (𝑥1, 𝑥2) = (0,10). Esta reta divide o 
plano em dois semiplanos e só um destes contém os pontos que satisfazem as restrições. 
Para saber qual o semiplano viável, toma-se um ponto como referência, por exemplo o 
ponto (𝑥1, 𝑥2) = (0,0). Como este ponto não satisfaz a restrição 2,5𝑥1 + 𝑥2 ≥ 10, 
temos que o semiplano viável é aquele que não contém o ponto (0,0). A região F completa 
encontra-se na Figura 2.7, onde a região associada a restrição 2,5𝑥1 + 𝑥2 ≥ 10 está 
destacada em amarelo. 
 
Figura 2.7: Região de soluções viáveis do Exemplo 2.1 
Na Figura 2.7 estão destacados também os pontos 𝐴, 𝐵, 𝐶 e 𝐷, que são os pontos extremos 
viáveis do modelo. É mostrado aqui como exemplo o cálculo das coordenadas do ponto 
𝐴. Tal ponto é interseção das restrições −𝑥1 + 𝑥2 ≥ 3 e 2,5𝑥1 + 𝑥2 ≥ 10. Assim, as 
coordenadas de 𝐴, satisfazem com igualdade estas duas restrições e, portanto, são obtidas 
resolvendo o sistema de equações: 
{
−𝑥1 + 𝑥2 = 3 
2,5𝑥1 + 𝑥2 = 10
 , 
que tem como solução 𝑥1 = 2 e 𝑥2 = 5. Os demais pontos extremos viáveis são 𝐵 =
(8,11), 𝐶 = (0,11) e 𝐷 = (0,10). 
𝐹 possui infinitas soluções. Para saber a solução ótima do modelo, ou seja, a solução em 
𝐹 que gera o menor valor para a função objetivo 𝑧 = 2𝑥1 + 𝑥2, alguns valores para 𝑧 são 
arbitrados e desenharmos as retas associadas. Para 𝑧 = 14 e 𝑧 = 12, por exemplo, tem-
se as retas14 = 2𝑥1 + 𝑥2 e 12 = 2𝑥1 + 𝑥2, conforme destaca a Figura 2.8. 
 
Figura 2.8: Duas curvas de nível para o Exemplo 2.1 
Ambas as retas tocam o conjunto de soluções viáveis. Assim, qualquer ponto que estiver 
sobre a reta 14 = 2𝑥1 + 𝑥2 e pertencer a 𝐹 é uma solução viável com função objetivo 
𝑧 = 14. Raciocínio similar pode ser aplicado para se obter soluções com 𝑧 = 12. 
Encontra-se então a reta com menor valor de 𝑧 e que toque o conjunto de soluções viáveis. 
A Figura 2.9 apresenta diversas retas, onde a reta procurada é destacada em negrito. 
 
Figura 2.9: Diversas curvas de nível para o Exemplo 2.1 
A reta destacada é a reta com 𝑧 = 9. Esta reta toca apenas no ponto extremo viável 𝐴 =
(2,5). Logo, este ponto representa a solução ótima do problema. 
4. Casos especiais 
Um modelo PL pode ser classificado como viável ou inviável. O modelo viável é aquele 
que possui pelo menos uma solução viável. Já o modelo inviável é aquele não possui 
nenhuma solução viável. 
 
 
Os dois modelos estudados nesta aula até o momento possuem uma única solução ótima. 
No entanto, alguns modelos podem ter múltiplas soluções ótimas ou ainda possuir solução 
ótima ilimitada. Para exemplificar o caso das múltiplas soluções ótimas, considere o 
seguinte modelo, que é semelhante ao do Exemplo 2.1, apenas com uma mudança na 
função objetivo: 
 
Os modelos PL viáveis podem possuir: uma única solução ótima, múltiplas soluções 
ótimas ou solução ilimitada. 
 
𝑀𝑖𝑛 𝑧 = 5𝑥1 + 2𝑥2 
s.a.: −𝑥1 + 𝑥2 ≥ 3; 
2,5𝑥1 + 𝑥2 ≥ 10; 
𝑥2 ≤ 11; 
𝑥1 , 𝑥2 ≥ 0; 
 
A Figura 2.10 ilustra a região de soluções viáveis 𝐹 e as curvas de nível para o novo 
modelo. 
 
Figura 2.10: Exemplo com múltiplas soluções ótimas 
Observe que agora a curva de nível com menor valor de 𝑧 e que toca o conjunto de 
soluções viáveis é a reta 20 = 5𝑥1 + 2𝑥2. Esta reta toca o conjunto de soluções em todo 
o segmento 𝐴𝐷̅̅ ̅̅ e não somente em um único ponto. Assim, o modelo possui infinitas 
soluções ótimas uma vez que qualquer ponto pertencente ao segmento 𝐴𝐷̅̅ ̅̅ (incluindo o 
próprio 𝐴 e o próprio 𝐷) é uma solução ótima do problema. Note que substituindo as 
coordenadas de 𝐴 ou 𝐷 na função objetivo, obtemos 𝑧 = 20. Uma condição para que um 
modelo PL tenha múltiplas soluções ótimas é que os coeficientes da função objetivo 
devem ser proporcionais aos coeficientes de uma das restrições, o que deixa as curvas de 
nível paralelas a esta restrição. 
Agora, vamos analisar um modelo com solução ilimitada. Para isso, considere o seguinte 
modelo: 
𝑀𝑎𝑥 𝑧 = 3𝑥1 + 𝑥2 
s.a.: −𝑥1 + 𝑥2 ≤ 0 
−
1
2
𝑥1 + 𝑥2 ≤ 3 
𝑥1 , 𝑥2 ≥ 0 
 
A Figura 2.11 mostra as curvas de nível associadas ao modelo prévio. 
 
Figura 2.11: Exemplo com solução ilimitada 
Observe que o valor de 𝑧 pode ser aumentado indefinidamente e a curva de nível 
associada continua tocando a região de soluções viáveis. Diz-se neste caso que a Solução 
é ilimitada ou que o modelo é ilimitado. 
5. Enumeração de pontos extremos viáveis 
Nesta aula foram vistos dois modelos que possuíam uma única solução ótima. Para 
ambos, esta solução estava associada a um ponto extremo viável. Esta observação de uma 
certa maneira também é válida para o exemplo com múltiplas soluções ótimas, uma vez 
que os pontos extremos viáveis 𝐴 e 𝐷 (Figura 2.10) são também solução ótima do modelo. 
O fato da solução ótima, quando esta existe, estar associada a um ou mais pontos extremos 
viáveis não é uma mera coincidência, pois esta é uma característica presente em qualquer 
modelo PL, independente se este for de maximização ou minimização. 
 
 
Com base na informação prévia, se um modelo PL é viável e não é ilimitado, pode-se 
então achar a solução ótima do mesmo enumerando todos os pontos extremos viáveis da 
região de soluções e retornando aquele que gera maior valor para função objetivo 
(problemas de maximização), ou aquele que gera menor valor para função objetivo 
(problemas de minimização). Volte agora ao primeiro modelo trabalhado nesta aula. Tal 
modelo não é um modelo ilimitado e possui os pontos extremos viáveis 𝐴 = (0,0), 𝐵 =
(25,0), 𝐶 = (25, 7,5) e 𝐷 = (0,45). Foi visto que a solução ótima era o ponto 𝐶, através 
do desenho das curvas de nível do modelo. Agora esta solução é encontrada enumerando 
os pontos extremos viáveis do modelo: 
Ponto extremo 
viável 
(𝑥1, 𝑥2) 𝑧 
𝐴 (0,0) 0 
𝐵 (25,0) 500 
𝐶 (25, 7,5) 575 
𝐷 (0,40) 400 
Importante: Em modelos PL viáveis não ilimitados, ao menos uma solução ótima é 
um ponto extremo viável do modelo PL. 
 
Como já era esperado, o ponto extremo 𝐶 = (25, 7,5) é aquele que gera maior valor de 
𝑧. 
6. Exercícios 
Exercício 2.1 Considere o PPL: 
𝑀𝑎𝑥 𝑧 = 3𝑥1 + 𝑥2 
s.a.: −2𝑥1 + 𝑥2 ≤ 3 
𝑥2 ≤ 10 
3𝑥1 + 2𝑥2 ≤ 14 
𝑥1 , 𝑥2 ≥ 0 
a) Encontre graficamente a região de soluções viáveis. 
b) Calcule as coordenadas de todos os pontos extremos viáveis. 
c) Desenhe as curvas de nível do modelo, destacando aquela que toca o conjunto de 
soluções viáveis e com maior valor de 𝑧. Qual a solução ótima? 
d) Classifique o PPL dado de acordo com o número de soluções ótimas do mesmo. 
e) Neste modelo, é possível se obter a solução ótima enumerando os pontos extremos 
viáveis? Se sim, encontre tal solução por este método. 
Solução comentada: 
 
a) Primeiramente, o conjunto de soluções viáveis 𝐹 é desenhado: 
 
Observe que a restrição 𝑥2 ≤ 10 é redundante. Em outras palavras, se ela não existisse, o 
conjunto de soluções viáveis seria o mesmo. 
b) Pela região de soluções viáveis 𝐹 do item anterior, tem-se que a mesma determina 
quatro pontos extremosviáveis denotados por 𝐴, 𝐵, 𝐶 e 𝐷. Cada um destes pontos é 
interseção de duas retas associadas as restrições do modelo. Logo, as coordenadas 
destes pontos são encontradas resolvendo sistemas de equações do 1º grau: 
 
Ponto extremo 
viável 
Interseção das 
retas 
Coordenadas 
𝐴 𝑥1 = 0 e 𝑥2 = 0 (0,0) 
𝐵 𝑥2 = 0 e 
3𝑥1 + 2𝑥2 = 14 
(
14
3
, 0) 
𝐶 3𝑥1 + 2𝑥2 = 14 
e −2𝑥1 + 𝑥2 =
 3 
(
8
7
,
37
7
) 
𝐷 𝑥1 = 0 e −2𝑥1 +
𝑥2 = 3 
(0,3) 
 
c) Para obtenção das curvas de nível, arbitra-se valores para 𝑧 e as retas (curvas de nível) 
associadas são desenhadas. Por exemplo, arbitrando 𝑧 = 10, a reta associada é 3𝑥1 +
𝑥2 = 10. Aumenta-se, então, os valores de 𝑧 até que seja encontrada a última reta que 
toca o conjunto de soluções viáveis: 
 
 
Note que a curva de nível que toca a região de soluções viáveis 𝐹 com maior valor de 𝑧 é 
quando 𝑧 = 14. Esta reta toca apenas no ponto 𝐵 = (
14
3
, 0), indicando que este ponto 
representa a solução ótima do problema. 
d) O PPL fornecido é viável e possui uma única solução ótima. 
e) O PPL é viável e não é ilimitado. Logo, pelo menos uma solução ótima do problema é 
um dos pontos extremos viáveis. Assim, a solução ótima pode ser encontrada enumerando 
os pontos extremos viáveis ao invés de desenhar as curvas de nível: 
 
Ponto extremo viável Valor de 𝑧 
𝐴 = (0,0) 3 × (0) + 0 = 0 
𝑩 = (
𝟏𝟒
𝟑
, 𝟎) 𝟑 × (
𝟏𝟒
𝟑
) + 𝟎 = 𝟏𝟒 
𝐶 = (
8
7
,
37
7
) 3 × (
8
7
) +
37
7
=
61
7
 
𝐷 = (0,3) 3 × (0) + 3 = 3 
 
Observe que o ponto 𝐵 é realmente aquele que gera o maior valor de 𝑧. 
 
Exercício 2.2 Considere o PPL: 
 
𝑀𝑖𝑛 𝑧 = 2𝑥1 + 3𝑥2 
s.a.: 𝑥1 + 𝑥2 = 9 
−2𝑥1 + 𝑥2 ≤ 6 
−𝑥1 + 𝑥2 ≥ 2 
𝑥1 , 𝑥2 ≥ 0 
 
a) Encontre graficamente a região de soluções viáveis. 
b) Calcule as coordenadas de todos os pontos extremos viáveis. 
c) Desenhe as curvas de nível do modelo, destacando aquela que toca o conjunto de 
soluções viáveis e com maior valor de 𝑧. Qual a solução ótima? 
d) Classifique o PPL dado de acordo com o número de soluções. 
e) Neste modelo, é possível se obter a solução ótima enumerando os pontos extremos 
viáveis? Se sim, encontre tal solução por este método. 
Solução comentada 
a) Desenha-se inicialmente que o conjunto de soluções viáveis 𝐹. 
 
Note que a região de soluções viáveis é apenas o segmento 𝐴𝐵̅̅ ̅̅ . Isto aconteceu porque o 
problema possui a restrição de igualdade 𝑥1 + 𝑥2 = 9. 
b) 
 
Ponto extremo 
viável 
Interseção das 
retas 
Coordenadas 
𝐴 𝑥1 + 𝑥2 = 9 e 
−2𝑥1 + 𝑥2 = 6 
(1,8) 
𝐵 𝑥1 + 𝑥2 = 9 e 
−𝑥1 + 𝑥2 = 2 
(
7
2
,
11
2
) 
c) 
 
 
Note que a curva de nível que toca a região de soluções viáveis 𝐹 com menor valor de 
𝑧 acontece quando 𝑧 = 23,5 e toca apenas o ponto 𝐵 = (
7
2
,
11
2
), indicando que este ponto 
representa a solução ótima do problema. 
Observação: O vetor destacado na figura é uma representação do vetor (2,3) 
(coeficientes da função objetivo). Na figura, tal vetor não tem relação com a direção de 
decrescimento de 𝑧, servindo apenas para mostrar que as curvas de nível são paralelas, 
pois este vetor é ortogonal a elas. 
 
d) O PPL fornecido é viável e possui uma única solução ótima. 
e) O modelo é viável e não é ilimitado. Logo, pelo menos uma solução ótima do 
problema é um dos pontos extremos viáveis. Assim, a solução ótima pode ser 
encontrada enumerando os pontos extremos viáveis ao invés de desenhar as curvas de 
nível: 
 
Ponto extremo viável Valor de 𝑧 
𝐴 = (1,8) 2 × 1 + 3 × 8 = 26 
𝐵 = (
7
2
,
11
2
) 2 ×
7
2
+ 3 ×
11
2
= 23,5 
 
Observe que o ponto 𝐵 é realmente aquele que gera o menor valor de 𝑧. 
Exercício 2.3: Considere um modelo PL similar ao do exercício 2.1, cuja única diferença 
é a não consideração da restrição 3𝑥1 + 2𝑥2 ≤ 14. O que pode ser afirmado sobre a 
solução ótima deste novo modelo? 
Solução comentada: O conjunto de soluções viáveis e as curvas de nível do novo modelo 
são inicialmente desenhadas: 
 
Note que podemos aumentar o valor de 𝑧 indefinidamente e ainda assim as curvas de 
nível continuam tocando a região de soluções viáveis. Logo, o modelo agora passa a ser 
ilimitado. Além disso, o fato do modelo ser ilimitado faz com que não seja possível mais 
usar o método de enumeração dos pontos extremos. 
Exercício 2.4: Considere um modelo PL similar ao do exercício 2.1, cuja única diferença 
é a função objetivo, que agora é 𝑧 = 9𝑥1 + 6𝑥2. O que pode ser afirmado sobre a solução 
ótima deste novo modelo? 
Solução comentada: O conjunto de soluções viáveis e as curvas de nível do novo modelo 
são inicialmente desenhadas: 
 
Note que a curva de nível que toca a região de soluções viáveis 𝐹 com maior valor de 𝑧 
toca a região no segmento 𝐵𝐶̅̅ ̅̅ , indicando que qualquer ponto deste segmento (incluindo 
os extremos) representa uma solução ótima do problema. Assim, pode-se dizer que o 
modelo agora tem múltiplas soluções ótimas. 
7. Conclusão 
Nesta aula, o primeiro método de resolução de PPLs foi apresentado, conhecido como 
método gráfico. Este método é divido em duas partes: construção da região de soluções 
viáveis e obtenção da solução ótima. Foi visto ainda que o método gráfico nos permite 
classificar um PPL de acordo com o número de soluções. 
Resumo 
No início da aula, foram definidos os conceitos de solução viável e inviável. Uma solução 
é dita viável se satisfaz todas as restrições do problema. Já a solução inviável não satisfaz 
pelo menos uma das restrições do problema. Definiu-se ainda que uma solução é chamada 
de ótima quando é viável e é a que mais otimiza a função objetivo do problema. 
Foi visto nesta aula o chamado método gráfico, que permite a obtenção da solução ótima 
de um PPL com duas variáveis em duas etapas: 
• Construção do conjunto de soluções viáveis: a região de todos os pontos que 
satisfazem as restrições é desenhada em um plano cartesiano. 
• Obtenção da solução ótima: nesta etapa identifica-se a direção de otimização da 
função objetivo, desenhando as curvas de nível do modelo. A última curva que 
tocar o conjunto de soluções viáveis está associada a solução ótima. 
O método gráfico permite ainda identificar se o modelo possui ou não solução viável. 
Quando possui, o método permite ainda classificar o modelo em uma das três opções: 
• com uma única solução ótima. 
• com múltiplas soluções ótimas. 
• com solução ilimitada. 
Informações sobre a próxima aula 
Na próxima aula, será visto os conceitos de forma padrão e canônica de um modelo PL. 
Estes conceitos são extremamente importantes para entendimento do algoritmo 
responsável pela resolução de modelos PL com diversas variáveis, conhecido como 
método Simplex. 
Referências 
Taha, H. A. (2008). Pesquisa operacional. Pearson Educación. 
Hillier, F. S., & Lieberman, G. J. (2013). Introdução à pesquisa operacional. McGraw 
Hill Brasil.