Considere o PPI a seguir:
Maximizar z=5 x1+x2
& sa -x1+x2 <= 4 & x1-x2 <= 1 & 4 x1+x2 <= 12
x 1, x2 são inteiros não negativos
Solucione o problema graficamente (avaliando cada solução viável);

Passo 1

Opa! Então o lance aqui é um problema de Programação Linear Inteira (PLI), onde a gente quer
maximizar
z = 5x1 + x2
sujeito a
-,x1 + x2 <= 4, x1 - x2 <= 1, 4x1 + x2 <= 12, x1,x2 >= 0 e inteiros
Conteúdo: programação linear inteira e região viável em 2D.
O que vamos precisar:
  1. Desenhar mentalmente (ou no papel) a região das restrições.
  2. Listar os pontos inteiros possíveis dentro dela.
  3. Avaliar a função objetivo em cada ponto.

Passo 2

Primeira ideia (teoria): em PLI com 2 variáveis dá pra “ver” a região como um polígono no plano e depois checar só os pontos inteiros dentro dele.
– As restrições formam uma área limitada.
– Como são inteiros, a gente pega cada possível e vê quais satisfazem as 3 desigualdades + .

Passo 3

Vamos enumerar (já que da 3 pra frente a restrição corta tudo):
Para cada :
  1. .
  2. .
  3. .
  4. .
Vamos aos casos:
  • :
    ,
    .
    Então .
  • :
    ,
    .
    Então .
  • :
    ,
    .
    Então .
  • :
    ,
    .
    Como , não há ponto viável.

Passo 4

Agora avalia a em cada par viável e anota o maior:
  • Para : melhor é , .
  • Para : melhor é , .
  • Para : melhor é , .
O maior que apareceu foi em .

Resposta

Solução ótima inteira:
boxedx1=2, x2=4, zmax=14

Exercícios relacionados