Questão de Estatística — Programação Linear — CESPE / CEBRASPE 2025

Programação linear: método simplex e variáveis inteiras

❌ ERRADO. O método simplex, em sua forma clássica, resolve problemas de programação linear contínua — ou seja, em que as variáveis podem assumir qualquer valor real dentro da região viável. Quando o problema exige que as variáveis sejam inteiras (programação linear inteira), o simplex puro não é suficiente: é necessário um método adicional, como o branch and bound ou o método de planos de corte (cortantes), para garantir a integralidade da solução. Portanto, a afirmação de que o simplex pode ser usado diretamente em problemas com variáveis inteiras, sem métodos adicionais, está errada.

O método simplex foi desenvolvido por George Dantzig em 1947 para resolver problemas de programação linear contínua. Ele percorre os vértices da região viável (um poliedro convexo) até encontrar o vértice que otimiza a função objetivo. A teoria que sustenta o método — o teorema fundamental da programação linear — garante que, se existe uma solução ótima, ela ocorre em um vértice do poliedro. Esse teorema vale para variáveis contínuas, mas não para variáveis inteiras: a solução ótima inteira pode não estar em um vértice do poliedro contínuo, e o simplex, ao encontrar um vértice ótimo contínuo, pode retornar valores fracionários (ex.: 2,5 unidades de um produto), o que é inviável em problemas que exigem quantidades inteiras (ex.: número de aviões, número de funcionários).

Para lidar com a integralidade, existem duas grandes famílias de métodos:

• Branch and bound (ramificação e limite): divide o problema em subproblemas, fixando valores inteiros para as variáveis fracionárias, e usa limites (bounds) para podar ramos que não podem conter a solução ótima inteira.

• Planos de corte (cutting planes): adiciona restrições lineares (cortes) que eliminam partes da região viável contínua que não contêm soluções inteiras, aproximando o poliedro até que o vértice ótimo seja inteiro.

Esses métodos são frequentemente combinados (branch-and-cut) em softwares de otimização. O simplex, por sua vez, é usado como sub-rotina dentro desses métodos para resolver os problemas contínuos relaxados (sem a restrição de integralidade).

A pegadinha da banca está em afirmar que o simplex resolve diretamente problemas inteiros, quando na verdade ele resolve apenas a relaxação contínua — e é justamente por isso que métodos adicionais são necessários.

❌ ERRADO. O item afirma que o método simplex pode ser utilizado diretamente em problemas com variáveis inteiras, sem métodos adicionais. Isso é falso: o simplex resolve problemas contínuos; para problemas inteiros, são necessários métodos como branch and bound ou planos de corte. Gabarito: ERRADO.