Beleza, o enunciado é um problema de Programação Linear (PL):
Maximizar
sujeito a
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).
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.
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: .
Interseção de (1) e (3) (o procedimento é similar ao de cima) também leva ao mesmo ponto ótimo .