O Método das Duas Fases em Programação Linear (Guia Passo a Passo)
Aprenda a resolver problemas com variáveis artificiais utilizando o Método das Duas Fases, uma alternativa computacionalmente robusta ao Big-M.
Experimente a Calculadora Simplex e de Sensibilidade Passo a Passo
Insira sua função objetivo e restrições para visualizar cada quadro, elementos pivô e análise de sensibilidade em tempo real.
Por que utilizar o Método das Duas Fases?
Em problemas de programação linear com restrições do tipo $\ge$ ou $=$, o método Big-M utiliza uma constante arbitrária (veja nosso guia do Método Big-M) $M$ muito grande, o que pode causar erros graves de arredondamento em sistemas computacionais. O Método das Duas Fases resolve esse problema dividindo o processo em duas etapas bem condicionadas numericamente.
Formulaçao do Modelo na Forma Padrão
Considere o seguinte problema:
Maximizar Z = 2x₁ + 3x₂
Sujeito a:
x₁ + x₂ ≤ 4 (restrição 1)
x₁ + 2x₂ ≥ 6 (restrição 2)
x₁, x₂ ≥ 0
Na forma padrão com variáveis de folga, excesso e artificiais:
- Restrição 1 (≤): x₁ + x₂ + s₁ = 4
- Restrição 2 (≥): x₁ + 2x₂ − s₂ + a₁ = 6
Fase I: Determinação de uma Solução Básica Inicial Viável
Ignora-se temporariamente a função Z original e constrói-se uma função objetivo auxiliar que busca minimizar a soma das variáveis artificiais:
Minimizar W = a₁
Se o valor mínimo de $W$ for zero, todas as variáveis artificiais saíram da base e obtém-se uma Solução Básica Inicial Viável (SBIV) legítima para o modelo original.
Quadro Inicial da Fase I
| Base | x₁ | x₂ | s₁ | s₂ | a₁ | LD |
|---|---|---|---|---|---|---|
| W | 1 | 2 | 0 | −1 | 0 | 6 |
| s₁ | 1 | 1 | 1 | 0 | 0 | 4 |
| a₁ | 1 | 2 | 0 | −1 | 1 | 6 |
Iteração da Fase I
- Entra na base: Coluna x₂ com coeficiente 2.
- Razão mínima: Linha s₁: 4/1 = 4; Linha a₁: 6/2 = 3 (mínimo). A variável a₁ deixa a base.
- Pivô: Elemento 2 na linha a₁.
Quadro resultante:
| Base | x₁ | x₂ | s₁ | s₂ | a₁ | LD |
|---|---|---|---|---|---|---|
| W | 0 | 0 | 0 | 0 | −1 | 0 |
| s₁ | 1/2 | 0 | 1 | 1/2 | −1/2 | 1 |
| x₂ | 1/2 | 1 | 0 | −1/2 | 1/2 | 3 |
W = 0. As variáveis artificiais foram totalmente eliminadas da base. A Fase I está concluída com sucesso!
Fase II: Otimização da Função Objetivo Original
Elimina-se a coluna da variável artificial a₁. Restaura-se a função objetivo original $Z = 2x_1 + 3x_2$ expressa em função das variáveis não básicas atuais.
Quadro Final da Fase II
| Base | x₁ | x₂ | s₁ | s₂ | LD |
|---|---|---|---|---|---|
| Z | 2 | 0 | 3 | 0 | −12 |
| s₂ | 1 | 0 | 2 | 1 | 2 |
| x₂ | 1 | 1 | 1 | 0 | 4 |
Todos os coeficientes da linha Z são não negativos. Pratique este modelo em nossa Calculadora do Método Simplex. → solução ótima encontrada:
- x₁ = 0, x₂ = 4, Z = 12
- s₂ = 2 (a restrição 2 possui folga excedente de 2 unidades).
Comparativo: Duas Fases vs. Big-M
| Propriedade | Método das Duas Fases | Método Big-M |
|---|---|---|
| Estabilidade numérica | Alta (não utiliza constantes M grandes) | Menor (risco de erros de precisão) |
| Detecção de inviabilidade | W > 0 ao término da Fase I | Variável artificial positiva no quadro final |
| Preferência computacional | Padrão em solvers comerciais | Didático para cálculos manuais |
Pronto para resolver seu modelo de Programação Linear?
Obtenha soluções instantâneas passo a passo com análise completa de sensibilidade e preços sombra para qualquer modelo de PL.