Passo-a-passo do Método Simplex.
O método Simplex é uma técnica amplamente utilizada em programação linear
para encontrar a solução ótima de problemas que envolvem maximizar ou
minimizar uma função linear sujeita a restrições lineares. Abaixo está um passo-
a-passo didático para resolver um problema de programação linear usando o
método Simplex:
Passo 1: Formule o Problema de Programação Linear
1. Identifique a função objetivo e as restrições.
Função Objetivo: Max 𝑍=𝑐1𝑥1+𝑐2𝑥2+⋯+𝑐𝑛𝑥𝑛Z=c1x1+c2x2+⋯+cnxn
Restrições:
{𝑎11𝑥1+𝑎12𝑥2+⋯+𝑎1𝑛𝑥𝑛≤𝑏1𝑎21𝑥1+𝑎22𝑥2+⋯
+𝑎2𝑛𝑥𝑛≤𝑏2⋮𝑎𝑚1𝑥1+𝑎𝑚2𝑥2+⋯+𝑎𝑚𝑛𝑥𝑛≤𝑏𝑚𝑥1,𝑥2,…,𝑥𝑛≥0⎩⎨⎧a11x1
+a12x2+⋯+a1nxn≤b1a21x1+a22x2+⋯+a2nxn≤b2⋮am1x1+am2x2+⋯+amnxn≤bm
x1,x2,…,xn≥0
Passo 2: Converta para Forma Padrão
1. Adicione variáveis de folga para transformar as desigualdades em igualdades.
𝑎11𝑥1+𝑎12𝑥2+⋯+𝑎1𝑛𝑥𝑛+𝑠1=𝑏1a11x1+a12x2+⋯+a1nxn+s1=b1
𝑎21𝑥1+𝑎22𝑥2+⋯+𝑎2𝑛𝑥𝑛+𝑠2=𝑏2a21x1+a22x2+⋯+a2nxn+s2=b2
⋮⋮
𝑎𝑚1𝑥1+𝑎𝑚2𝑥2+⋯+𝑎𝑚𝑛𝑥𝑛+𝑠𝑚=𝑏𝑚am1x1+am2x2+⋯+amnxn+sm=bm
Onde 𝑠1,𝑠2,…,𝑠𝑚≥0s1,s2,…,sm≥0.
Passo 3: Configure a Tabela Simplex Inicial
1. Monte a tabela Simplex com as variáveis básicas e não-básicas.
Colunas: 𝑥1,𝑥2,…,𝑥𝑛,𝑠1,𝑠2,…,𝑠𝑚,𝑍x1,x2,…,xn,s1,s2,…,sm,Z
Linhas: Cada uma das restrições, mais uma linha para a função objetivo.
Passo 4: Identifique a Variável de Entrada
1. Determine a variável de entrada (coluna) que mais aumenta 𝑍Z.
Procure a maior contribuição positiva na linha 𝑍Z (critério de maior coeficiente).
Passo 5: Identifique a Variável de Saída
1. Determine a variável de saída (linha).
Divida o valor da coluna do termo constante pelo coeficiente positivo da
variável de entrada em cada linha.
Escolha a linha com o menor quociente positivo (critério da razão mínima).
Passo 6: Realize a Operação de Pivotamento
1. Atualize a tabela Simplex fazendo o pivotamento.
Transforme o elemento chave (interseção da linha de saída e coluna de entrada)
em 1.
Ajuste as outras entradas na coluna para 0, realizando operações de linha
adequadas.
Passo 7: Repetição
1. Repita os passos 4 a 6 até que não haja coeficientes positivos na linha 𝑍Z.
Quando todos os coeficientes forem ≤ 0, a solução é ótima.
Passo 8: Interprete a Solução
1. Leia a solução ótima da tabela final.
As variáveis básicas (colunas com 1 e os demais valores 0) têm seus valores
diretamente da coluna dos termos constantes.
As variáveis não-básicas têm valor zero.