Considere o seguinte conjunto de restrições:
X1+2 X2+2 X3+4 X4 <= 40
2 X1-X2+X3+2 X4 <= 8
4 X1-2 X2+X3-X4 <= 10
X1 ; X2 ; X3 ; X4 >= 0
Max z=2 X1+X2-3 X3+5 X4

Passo 1

Beleza, o enunciado é um problema de Programação Linear (PL):
Maximizar
z = 2X1 + X2 - 3X3 + 5X4
sujeito a
X1 + 2X2 + 2X3 + 4X4 <= 40, 2X1 - X2 + X3 + 2X4 <= 8, 4X1 - 2X2 + X3 - X4 <= 10, X1,X2,X3,X4 >= 0
Matéria: otimização linear. Vamos usar a ideia de ponto extremo (vértice do poliedro viável) e a teoria de que, num problema de maximização, se uma variável tem coeficiente negativo no (aqui tem ), a melhor escolha é pôr essa variável em zero. A partir daí reduzimos o número de variáveis e achamos as interseções das retas (duas restrições de cada vez) para testar quem dá maior .

Passo 2

Por que podemos definir max z = 2X1 + X2 + 5X4 ?
– Teoria rápida: em maximização, se X1 + 2X2 + 4X4 <= 40, 2X1 - X2 + 2X4 <= 8, 4X1 - 2X2 - X4 <= 10, X1,X2,X4>=0 tem termo , quanto mais alto for menor fica . Como , a melhor é tomar .
Então o problema vira
sujeito a

Passo 3

Agora vamos achar os candidatos a vértice: pegamos pares de restrições (3 restrições dão X1 + 2X2 = 40, 2X1 - X2 = 8 combinações), resolvemos como sistema de duas equações em três variáveis, impondo que a terceira vale zero ou fica livre mas depois checamos viabilidade. Os pares são: (1,2), (1,3) e (2,3).
  1. Interseção de (1) e (2) com 2X1 - X2 + 2X4 = 8, 4X1 - 2X2 - X4 = 10 :
X4 = 65, X2 = 2X1 - 5.6, (com (X1) livre)
Solução: X4=1.2, X2=12.96 , . Mas aí, checando a restrição (3):
,
portanto esse ponto não é viável.
  1. Interseção de (2) e (3) tomando as duas iguais e eliminando em função de . Sem pular etapas, você resolveria:
Isso leva à família de soluções
Ao impor todas as restrições e não-negatividade, chega-se que varia de a . O valor de cresce com , logo o máximo nessa aresta ocorre em . Aí
Esse ponto ainda precisa satisfazer (1), o que de fato satisfaz como igualdade:
.
  1. Interseção de (1) e (3) (o procedimento é similar ao de cima) também leva ao mesmo ponto ótimo .

Passo 4

Entre todas as soluções viáveis, a que maximiza
z=2X1 + X2 + 5X4
é justamente
X1 = 9.28,; X2 = 12.96,; X4 = 1.20,; X3 = 0,
e aí
zmax = 2cdot9.28 + 12.96 + 5cdot1.20 = 37.52

Resposta

, com .

Exercícios relacionados