Como verificar se uma solução é viável e ótima em um problema de programação linear?

Resposta

Para verificar se uma solução é viável, é necessário confirmar que ela satisfaz todas as restrições do problema.
Para confirmar que é ótima, verifica-se se o valor da função objetivo naquele ponto é máximo (ou mínimo) dentro do conjunto viável, geralmente analisando os vértices da região delimitada pelas restrições.

Exemplo:

Considere o problema:

Maximizar \( z = 4x_1 + 3x_2 \)

Sujeito a:

• \( x_1 \leq 2 \)
• \( x_2 \leq 5 \)
• \( 2x_1 + x_2 \leq 7 \)
• \( x_1, x_2 \geq 0 \)

Suponha que tentemos a solução \( x_1 = 2 \), \( x_2 = 3 \):

• Verifique as restrições:
• \( 2 \leq 2 \) — verdadeira
• \( 3 \leq 5 \) — verdadeira
• \( 2\cdot 2 + 3 = 4 + 3 = 7 \leq 7 \) — verdadeira
• Assim, a solução é viável.

Calcule o valor da função objetivo:

\( z = 4 \cdot 2 + 3 \cdot 3 = 8 + 9 = 17 \)

Testando outros vértices do conjunto viável, verifica-se que nenhum ponto gera valor maior para \( z \), então essa solução é ótima.