Questão 751672

Em um problema de programação linear inteira-mista, a partir da tabela final SIMPLEX, cuja forma algébrica geral é dada a seguir, é possível propor tanto desigualdades válidas quanto restrições de ramificação (Branching), quando se busca computar soluções integrais para o problema via algoritmo Branch And Bound. Uma vez inseridas tais restrições qual seria, respectivamente, o estado do programa linear inteiro-misto no que tange à viabilidade primal, acerca da viabilidade dual e à otimalidade? Qual algoritmo, entre o Primal e o Dual SIMPLEX, seria mais indicado para continuar o processo de otimização?

\(\begin{aligned} & \text{Min } z = z_0 + \sum_{j \in N} \left( z_j^N - c_j^N \right) x_j^N \\ & \text{s.t. } x_i^B + \sum_{j \in N} a_{ij}^N x_j^N = b_i, \forall i \in I, \\ & x_j \ge 0, \forall j \in J. \end{aligned}\)

Fonte: Banca Examinadora, 2026.