Em programação linear, quando a solução ótima é múltipla?

Quando a reta da função objetivo é paralela a uma restrição ativa no ótimo.

Explicação:
A função objetivo \(Z=c_1x_1+c_2x_2=c\) tem declive \(-\tfrac{c_1}{c_2}\) pois \(x_2=\tfrac{c}{c_2}-\tfrac{c_1}{c_2}x_1\).
Uma restrição \(a x_1+b x_2=d\) tem declive \(-\tfrac{a}{b}\).
Se \(-\tfrac{c_1}{c_2}=-\tfrac{a}{b}\) (paralelismo) e essa restrição é ativa na fronteira ótima, então toda a aresta correspondente é ótima → infinitas soluções.

exemplo:
Problema:
Maximizar \(Z=3x_1+6x_2\) sujeito a
\(x_1\ge0,\;x_2\ge0,\;x_1+2x_2\le4,\;x_1\le1\).

O declive da objetivo é \(-\tfrac{3}{6}=-\tfrac{1}{2}\).
A restrição \(x_1+2x_2=4\) tem declive \(-\tfrac{1}{2}\) (paralela).
A aresta dessa restrição dentro da região viável vai de \((0,2)\) a \((1,1.5)\).
Calcule \(Z\): \(Z(0,2)=3\cdot0+6\cdot2=12\) e \(Z(1,1.5)=3\cdot1+6\cdot1.5=12\).
Portanto todos os pontos entre \((0,2)\) e \((1,1.5)\) têm \(Z=12\) ⇒ infinitas soluções ótimas.