A programação linear não é apenas matemática abstrata. É o motor por trás da logística, das cadeias de abastecimento e da gestão de recursos. Em sua essência está o método simplex. Esta técnica padrão encontra o melhor resultado possível em um sistema definido por restrições e uma função objetivo.
Pense desta forma. Você tem um objetivo. Talvez seja maximizar o lucro ou minimizar custos. Você também tem limites. Horas da máquina. Matérias-primas. Trabalho. O método simplex navega por esses limites para encontrar o pico. Não adivinha. Ele calcula.
Por que precisamos de uma abordagem sistemática
Você pode pensar que pode simplesmente representar graficamente duas variáveis e ver onde elas se cruzam. Isso funciona para problemas simples. Uma fábrica que fabrica dois produtos. Você desenha linhas. Você encontra o canto onde o lucro atinge o pico. É visual. É intuitivo.
Mas a realidade raramente é bidimensional. Problemas reais envolvem centenas de equações e milhares de variáveis. O número de soluções potenciais torna-se astronômico. Desenhar um gráfico para mil variáveis é impossível. Você precisaria de dimensões que não consegue perceber.
George Dantzig resolveu isso em 1947. Ele trabalhava como consultor matemático para a Força Aérea dos EUA. Os militares tiveram enormes problemas logísticos. Eles precisavam otimizar as rotas de abastecimento e a alocação de recursos. Dantzig desenvolveu o método simplex para eliminar o ruído.
O método restringe o número de pontos extremos que devem ser examinados. Transforma uma tarefa impossível em uma tarefa administrável. Continua sendo o algoritmo padrão em computadores hoje. Uma das ferramentas mais úteis já inventadas.
Como funciona o método Simplex passo a passo
O processo é sistemático. Ele passa de uma possibilidade para outra. Veja como isso se desenrola na prática.
Primeiro, pressupõe que você tenha um ponto de partida. Um ponto extremo. Se não tiver um, uma variante chamada Fase I encontra um ponto de partida viável ou determina que não existe solução.
A seguir, o método testa esse ponto. É ideal? A especificação algébrica do problema executa esta verificação. Se o teste falhar, o algoritmo move-se para um ponto extremo adjacente. Ele se move ao longo de uma borda. Ele escolhe a direção onde a função objetivo aumenta mais rapidamente.
Às vezes, a função aumenta sem limite. O procedimento para e identifica a aresta onde o valor vai para o infinito positivo. Você encontrou uma solução ilimitada.
Se isso não acontecer, você chegará a um novo ponto extremo. Este ponto tem um valor pelo menos tão alto quanto o anterior. A sequência se repete. Ele continua até encontrar um ponto ideal ou identificar a ilimitação.
Em teoria, as etapas poderiam crescer exponencialmente com o número de pontos extremos. Na prática, a convergência é rápida. Geralmente leva apenas um pequeno múltiplo do número de pontos extremos.
Um exemplo concreto: maximizando o lucro da fábrica
Vejamos um caso tangível. Uma fábrica produz dois produtos. Nós os chamamos de x1 e x2. O lucro do segundo tipo é o dobro do primeiro. O lucro total é representado pela equação:
x1 + 2×2
Esta é a sua função objetivo. Você quer maximizá-lo.
Naturalmente, você gostaria de ganhar apenas x2. Isso traz mais dinheiro por unidade. Mas existem restrições. Você não pode simplesmente produzir infinitamente.
Aqui estão os limites do mundo real:
- A matéria-prima para x2 limita a produção a cinco unidades por lote (x2 ≤ 5).
- A matéria-prima para x1 limita a produção a oito unidades por lote (x1 ≤ 8).
- O tempo de máquina permite um máximo de dez unidades totais (x1 + x2 ≤ 10).
- Você não pode produzir valores negativos (x1 ≥ 0 e x2 ≥ 0).
O método simplex encontra os valores de x1 e x2 que maximizam o lucro dentro desses limites. Qualquer solução é um par de números (x1, x2). Por exemplo, produzir três de x1 e seis de x2 é um ponto válido (3, 6).
Quando plotadas em um gráfico, essas restrições formam uma região poligonal. Este é o conjunto de soluções viáveis. Os pontos fora desta região violam uma ou mais restrições.
Para ver como o método simplex identifica o vértice ideal, considere a função objetivo x1 + 2×2 = k. Se você definir k como 4, obterá uma linha no gráfico. À medida que você aumenta k, você obtém linhas paralelas. O maior valor de k que ainda atinge a região viável é o lucro máximo possível.
Neste exemplo, a reta para k = 15 toca a região no ponto (5, 5). Se k for maior, a linha fica fora do conjunto viável. A solução ideal é produzir quantidades iguais de cada mercadoria.
Por que os vértices são importantes na programação linear
O resultado não é uma coincidência. Em problemas lineares, a solução ótima sempre ocorre em um vértice. Um ponto extremo.
Esta é uma propriedade fundamental da programação linear. A função é linear. As restrições são lineares. A forma é um polígono convexo (ou poliedro em dimensões superiores). O pico de uma função linear sobre um conjunto convexo está sempre em um vértice.
Você não precisa verificar todos os pontos da região viável. Você só precisa verificar os vértices. O método simplex faz exatamente isso. Ele salta de vértice em vértice. Ele sobe na superfície da região viável. Ele para quando não pode subir mais.
Às vezes, o ideal não é único. Uma aresta inteira pode produzir o mesmo valor máximo. Mas o método simplex ainda encontrará um desses pontos ideais. Isso lhe dá uma resposta concreta. Dados acionáveis.
Tanto para estudantes quanto para profissionais, compreender essa mecânica é fundamental. Não se trata apenas de resolver equações. Trata-se de saber navegar em sistemas complexos com recursos limitados. O método simplex fornece o caminho.
O método simplex não apenas adivinha respostas. Ele caminha pelas bordas de uma região viável, verificando os vértices até encontrar o melhor. Tudo começa limpando a matemática. Você pega essas desigualdades lineares confusas e as transforma em igualdades limpas. Você faz isso adicionando “variáveis de folga”.
Pense na folga como capacidade restante. Se você tiver uma restrição como $x_1 \le 8$, adicione uma variável $x_3$ tal que $x_1 + x_3 = 8$. E lembre-se, $x_3$ deve ser maior ou igual a zero. Você faz isso para cada restrição.
- $x_1 + x_3 = 8$ (com $x_3 \ge 0$)
- $x_2 + x_4 = 5$ (com $x_4 \ge 0$)
- $x_1 + x_2 + x_5 = 10$ (com $x_5 \ge 0$)
Você também precisa de uma variável para a própria função objetivo. Vamos chamá-lo de $x_0$. Se seu objetivo é maximizar $x_0 = x_1 + 2x_2$, você reescreve como $x_1 + 2x_2 – x_0 = 0$.
Agora o problema é mais simples. Encontre valores não negativos para $x_1$ até $x_5$. Faça $x_0$ o maior possível.
Começando pela Origem
Por onde você começa? O local mais fácil é a origem. Defina todas as variáveis de decisão como zero. $x_1 = 0$. $x_2 = 0$.
Esta é uma solução válida. É um ponto extremo. Na verdade, é a curva inicial. O valor objetivo $x_0$ também é zero. Não é ótimo, mas é uma medida legal.
Podemos fazer melhor? Sim. Se você aumentar uma das variáveis de zero enquanto mantém a outra em zero, $x_0$ sobe. A questão é qual variável oferece o maior retorno para seu investimento.
Observe a equação objetiva: $x_1 + 2x_2 – x_0 = 0$. Reorganizando para $x_0$, você obtém $x_0 = x_1 + 2x_2$.
Aumentar $x_1$ adiciona 1 ao total. Aumentar $x_2$ soma 2. $x_2$ é o vencedor claro. Produz o maior aumento em $x_0$ por mudança de unidade. Então, você escolhe $x_2$ e empurra para cima.
Atingindo a primeira restrição
Você não pode aumentar $x_2$ para sempre. As variáveis devem permanecer não negativas. Se você empurrar $x_2$ além de 5, algo quebra. Especificamente, observe a segunda restrição: $x_2 + x_4 = 5$.
Se $x_2 = 6$, então $x_4$ se torna -1. Isso não é permitido. O requisito de não negatividade atua como uma parada brusca. O limite é 5.
Então você define $x_2 = 5$. Como é a solução agora?
- $x_2 = 5$
- $x_1 = 0$ (ainda zero)
- $x_4 = 0$ (esta variável atingiu o limite, então agora é zero)
- $x_3 = 8$ (já que $0 + 8 = 8$)
*$
