Resolvendo problemas de programação linear usando o método simplex

A programação linear é uma forma de alcançar os melhores resultados em um modelo matemático. Este modelo é representado por relações lineares. O objetivo da programação linear é encontrar o valor máximo ou mínimo de uma quantidade específica, que pode ser expressa como uma equação em restrições específicas. O método simplex é um algoritmo popular usado para resolver problemas de programação linear.

O que é o método simplex?

O método simplex é um procedimento passo a passo para resolver problemas de programação linear. Ele é projetado para lidar com equações com mais de duas variáveis e restrições mais complexas. A beleza do método simplex é que ele transforma o problema em um processo sistemático usando uma forma tabular chamada tableau simplex.

Problema de programação linear

Antes de prosseguirmos com o método simplex, vamos entender como é um problema de programação linear. Um problema típico de programação linear terá o seguinte:

1. Uma função objetivo para maximizar ou minimizar.
2. Restrições na forma de desigualdades lineares.
3. Variáveis não-negativas.

Por exemplo:

Maximizar: Z = 3x + 2y
sujeito a:
2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24
x, y ≥ 0

Aqui, Z é a função objetivo que você deseja maximizar. As restrições são representadas por desigualdades. Ambas as variáveis x e y devem ser maiores ou iguais a zero.

Passos do método simplex

O método simplex envolve várias etapas principais:

Passo 1: Converter desigualdades em equações

Converter desigualdades em igualdades adicionando variáveis de folga. As variáveis de folga representam a diferença entre os lados esquerdo e direito da desigualdade.

Considere as restrições:

2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24

Adicione as variáveis de folga s1, s2 e s3 para mudá-las:

2x + y + s1 = 18
2x + 3y + s2 = 42
3x + y + s3 = 24

Agora, as equações lineares têm variáveis de folga que são inicialmente configuradas para zero.

Passo 2: Configurar o tableau simplex

Crie uma tabela inicial simplex a partir das equações que você transformou. A tabela se parece com isto:

| x | y | s1 | s2 | s3 | Solução |
, 2 | 1 | 1 | 0 | 0 | 18 |
, 2 | 3 | 0 | 1 | 0 | 42 |
, 3 | 1 | 0 | 0 | 1 | 24 |
, -3 | -2 | 0 | 0 | 0 | 0 |

Nota: A linha inferior é formada subtraindo os coeficientes da função objetivo. Esta linha ajuda a determinar a otimização.

Passo 3: Identificar o elemento pivô

Um elemento pivô é selecionado para alterar a solução de tal forma que leve a novas dimensões em direção à solução ótima. Os principais pontos neste processo incluem:

• Selecionar o número mais negativo na linha inferior da tabela. Este será a coluna pivô.
• Calcular a razão dos valores da solução para os coeficientes na coluna pivô (ignorando coeficientes zero e negativos). A menor razão positiva determinará a linha pivô.

Por exemplo:

Razão: (18/2) = 9, (42/2) = 21, (24/3) = 8

A menor razão é 8, que corresponde à linha pivô. E para este exemplo, como -3 é o mais negativo na linha inferior, a coluna pivô é aquela com 3.

Passo 4: Realizar operações de linha

Use operações de linha elementares para mudar o elemento pivô para 1 e ajustar os outros elementos na coluna para 0. Este passo garante a convergência em direção a uma solução ótima.

Passo 5: Iterar

Repita os passos 3 e 4 até que não haja mais números negativos na linha inferior. Quando esse ponto for alcançado, a solução viável original encontrada é ótima.

Um exemplo prático usando o método simplex

Crise

Maximize a função Z = 5x + 4y, sujeito a:

y + 2x ≤ 20 
2x + 3y ≤ 30 
2x + y ≤ 15 
x, y ≥ 0

Passo 1: Converter em equação com variável de folga

x + 2y + s1 = 20
2x + 3y + s2 = 30
2x + y + s3 = 15

Passo 2: Configurar o tableau simplex

| x | y | s1 | s2 | s3 | Solução |
, 1 | 2 | 1 | 0 | 0 | 20 |
, 2 | 3 | 0 | 1 | 0 | 30 |
, 2 | 1 | 0 | 0 | 1 | 15 |
| -5|-4 | 0 | 0 | 0 | 0 |

Passo 3: Identificar o elemento pivô

O elemento com -5 é a coluna pivô. Calculando a razão para a terceira coluna:

Razão: (20/1) = 20, (30/2) = 15, (15/2) = 7,5

O menor valor positivo é 7,5. O elemento em (Linha 3, Coluna 1) será o pivô.

Passo 4: Realizar operações de linha

Faça o elemento pivô igual a 1:

| x | y | s1 | s2 | s3 | Solução |
, 1 | 2 | 1 | 0 | 0 | 20 |
| 1 | 1,5| 0 | 0,5| 0 | 7,5 | <- linha pivô (elemento pivô 1 criado)
, 2 | 1 | 0 | 0 | 1 | 15 |
| -5|-4 | 0 | 0 | 0 | 0 |

Ajuste as operações de linha para tornar os outros elementos da coluna zero e repita o processo até não haver negativos na linha inferior.

Passo 5: Solução ótima

Através de sucessivas iterações, eventualmente:

| x | y | s1 | s2 | s3 | Solução |
, 1 | 0 | 1 | 1 | 0 | 5 |
| 0 | 1 | 0 | 1,5| 0 | 12,5 |
, 0 | 0 | -1 |-1,5| 1 | -7,5 |
| 0 | 0 | 0 |0,5 | 0 | 35 |

Os valores x = 5 e y = 12,5 maximizam a função objetivo Z até um valor de 35.

Conclusão

O método simplex é uma ferramenta poderosa de otimização para programação linear. Ele pode lidar com múltiplas variáveis de forma eficiente, guiando para um ponto ótimo delimitado por restrições. A natureza procedural permite uma análise aprofundada de cenários práticos onde os recursos são limitados, garantindo utilização ótima.

Comentários