Compreendendo o Método do Big-M em Programação Linear (Exemplo Passo a Passo)
Domine o método do Big-M para restrições de >= e = em Programação Linear. Entenda variáveis de folga, excesso e artificiais com um exemplo resolvido passo a passo.
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 precisamos do Método Big-M?
O método Simplex padrão estabelece facilmente uma base viável inicial quando todas as restrições são do tipo ≤, pois as variáveis de folga formam uma matriz identidade na origem $(x=0)$. Contudo, quando há restrições ≥ ou =, a origem não é viável e não existe uma base óbvia. O Método do Big-M soluciona essa limitação aplicando penalidades massivas a variáveis artificiais em nossa Calculadora do Método Simplex.
Variáveis de Folga, Excesso e Artificiais
- Variáveis de Folga ($s_i ≥ 0$): Adicionadas a restrições ≤ ($+s_i$). Expressam capacidade de recurso ociosa.
- Variáveis de Excesso ($e_i ≥ 0$): Subtraídas de restrições ≥ ($-e_i$). Medem a superação do requisito mínimo. Em $x=0$, $-e_i = b_i ⇒ e_i = -b_i < 0$, violando a não negatividade.
- Variáveis Artificiais ($a_i ≥ 0$): Somadas ($+a_i$) a restrições ≥ e =. Não possuem significado físico no modelo: são artifícios matemáticos para dar partida no quadro Simplex.
A Penalidade do Big-M na Função Objetivo
- Em Maximização: Subtrai-se $M \times a_i$: $\max Z = \sum c_j x_j - M \sum a_i$.
- Em Minimização: Soma-se $M \times a_i$: $\min Z = \sum c_j x_j + M \sum a_i$.
Exemplo Prático Resolvido e Validado
Resolva este mesmo problema passo a passo em nossa Calculadora do Método Simplex:
Maximizar Z = 3x₁ + 5x₂
Sujeito a:
x₁ + x₂ ≥ 2 (Restrição 1: Demanda mínima)
2x₁ + 3x₂ ≤ 12 (Restrição 2: Limite de recurso)
x₁, x₂ ≥ 0
Passo 1: Forma Padrão
- Restrição 1 (≥): $x_1 + x_2 - e_1 + a_1 = 2$
- Restrição 2 (≤): $2x_1 + 3x_2 + s_2 = 12$
- Base inicial: ${a_1, s_2}$. Variáveis: $x_1, x_2, e_1, s_2, a_1 ≥ 0$.
Passo 2: Operação Prévia de Linha em Z
Linha Z com penalidade: $Z - 3x_1 - 5x_2 + M a_1 = 0$. Eliminamos $a_1$ subtraindo $M \times (\text{Linha } 1)$:
Nova Linha Z = [Z - 3x₁ - 5x₂ + M a₁] - M × [x₁ + x₂ - e₁ + a₁ = 2]
⇒ Z - (3 + M)x₁ - (5 + M)x₂ + M e₁ + 0s₂ + 0a₁ = -2M
Passo 3: Quadro Inicial (Iteração 0)
| Base | x₁ | x₂ | e₁ | s₂ | a₁ | LD | Razão Mínima |
|---|---|---|---|---|---|---|---|
| Z | -(3 + M) | -(5 + M) | M | 0 | 0 | -2M | — |
| a₁ | 1 | 1 | -1 | 0 | 1 | 2 | 2 / 1 = 2 (mín) ← Pivô |
| s₂ | 2 | 3 | 0 | 1 | 0 | 12 | 12 / 3 = 4 |
Passo 4: Iteração 1
Entra $x_2$ e sai $a_1$. O pivô é 1 na linha $a_1$. Gauss-Jordan zera a coluna de $x_2$ e elimina o termo $M$ do LD:
| Base | x₁ | x₂ | e₁ | s₂ | a₁ | LD | Razão Mínima |
|---|---|---|---|---|---|---|---|
| Z | 2 | 0 | -5 | 0 | 5 + M | 10 | — |
| x₂ | 1 | 1 | -1 | 0 | 1 | 2 | -1 ≤ 0 (ignorado) |
| s₂ | -1 | 0 | 3 | 1 | -3 | 6 | 6 / 3 = 2 ← Pivô |
Passo 5: Iteração 2 (Quadro Ótimo)
Entra $e_1$ e sai $s_2$. O pivô é 3 na linha $s_2$:
| Base | x₁ | x₂ | e₁ | s₂ | a₁ | LD |
|---|---|---|---|---|---|---|
| Z | 1/3 | 0 | 0 | 5/3 | M | 20 |
| x₂ | 2/3 | 1 | 0 | 1/3 | 0 | 4 |
| e₁ | -1/3 | 0 | 1 | 1/3 | -1 | 2 |
Interpretação da Solução Ótima
Todos os coeficientes da linha Z são não negativos ($1/3 ≥ 0, 5/3 ≥ 0, M ≥ 0$). A solução ótima foi alcançada:
- Variáveis de decisão: $x_1^* = 0$, $x_2^* = 4$.
- Variáveis de folga/excesso: $e_1 = 2$ (restrição 1 tem excedente de 2), $s_2 = 0$ (restrição 2 está totalmente consumida).
- Valor ótimo: $Z^* = 3(0) + 5(4) = 20$.
- Factibilidade: Variável artificial $a_1 = 0$ fora da base.
Visualize geometricamente em nossa Calculadora do Método Gráfico.
Big-M versus Método das Duas Fases
Para evitar erros de precisão numérica computacional com a constante $M$, softwares industriais preferem o Método das Duas Fases.
Erros Frequentes de Alunos
- Esquecer a eliminação prévia de $M$ na linha Z antes do primeiro pivoteamento.
- Trocar o sinal da penalidade ($-M$ em maximização e $+M$ em minimização).
- Calcular razão mínima com coeficientes negativos ou nulos.
- Aprofunde seus estudos sobre preços sombra e análise de sensibilidade.
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.