Programação Linear — Método Simplex e Solução Gráfica

Programação linear é um método para encontrar o melhor valor de uma função objetivo linear, como lucro máximo ou custo mínimo, sujeito a restrições lineares. Em um problema com duas variáveis, a solução gráfica encontra a região viável e verifica seus pontos de canto. Em problemas maiores, o método simplex usa a mesma ideia dos pontos de canto de forma algébrica.

Use programação linear apenas quando a função objetivo e as restrições forem lineares. Se a relação tiver curvatura, formar curvas ou depender de produtos como $xy$, o modelo não é um problema de programação linear.

Definição de Programação Linear

$$\text{maximize or minimize } z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$

sujeito a restrições como

$$a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1$$

além de desigualdades lineares semelhantes, junto com condições como $x_i \ge 0$ quando valores negativos não fazem sentido.

O conjunto de todos os pontos que satisfazem todas as restrições é chamado de região viável. A programação linear pergunta: entre esses pontos viáveis, qual deles fornece o melhor valor da função objetivo?

Como Funciona o Método Gráfico

Se houver apenas duas variáveis de decisão, você pode desenhar cada restrição no plano $xy$. A interseção de todas as regiões permitidas é a região viável.

Cada ponto dessa região é uma solução válida. A função objetivo atribui um valor a cada um deles.

Em programação linear, um fato importante é o seguinte: se existir uma solução ótima, então pelo menos uma solução ótima ocorre em um ponto de canto da região viável. É por isso que o método gráfico se concentra nos vértices em vez de verificar todos os pontos da região sombreada.

Exemplo Resolvido: Resolver um Problema de Programação Linear Graficamente

Suponha que uma oficina produza dois produtos, $A$ e $B$.

• Lucro por unidade de $A$: $3$
• Lucro por unidade de $B$: $5$
• Limite de tempo de máquina: cada unidade de $A$ usa $1$ hora, cada unidade de $B$ usa $2$ horas, e há no máximo $8$ horas disponíveis
• Limite de montagem: cada unidade de $A$ usa $1$ hora, cada unidade de $B$ usa $1$ hora, e há no máximo $5$ horas disponíveis

Seja $x$ o número de unidades de $A$ e $y$ o número de unidades de $B$.

Maximizar

$$P = 3x + 5y$$

sujeito a

$$x + 2y \le 8$$ $$x + y \le 5$$ $$x \ge 0,\quad y \ge 0$$

Encontre os pontos de canto

A partir dos eixos e das retas das restrições, os pontos de canto viáveis são

• $(0,0)$
• $(5,0)$
• $(0,4)$
• $(2,3)$

O ponto $(2,3)$ vem da resolução das equações de fronteira

$$x + 2y = 8,\quad x + y = 5$$

Subtraindo, obtemos $y = 3$, e então $x = 2$.

Teste a função objetivo em cada canto

Calcule o lucro em cada ponto de canto:

• Em $(0,0)$, $P = 0$
• Em $(5,0)$, $P = 15$
• Em $(0,4)$, $P = 20$
• Em $(2,3)$, $P = 21$

Portanto, o lucro máximo é

$$P = 21$$

em

$$(x,y) = (2,3)$$

Esse é o método gráfico em uma frase: represente a região viável, encontre os pontos de canto e avalie a função objetivo neles.

Intuição do Método Simplex

O método gráfico é prático apenas quando há duas variáveis, e às vezes três, se você estiver disposto a imaginar uma região em 3D. Problemas reais de otimização costumam ter muitas variáveis, então desenhar a região viável deixa de ser realista.

O método simplex mantém a mesma lógica dos pontos de canto, mas faz isso de forma algébrica. Em termos gerais, ele passa de um ponto de canto viável para outro que melhora a função objetivo, e para quando nenhum movimento adjacente produz um valor melhor.

Então, um bom modelo mental é:

• Método gráfico: ver os pontos de canto
• Método simplex: percorrer os pontos de canto sem desenhá-los

Essa descrição é a intuição, não o algoritmo completo. O procedimento simplex real usa um tableau ou uma forma algébrica equivalente para decidir qual variável entra e qual sai em cada etapa.

Por Que os Pontos de Canto Importam

Funções objetivo lineares criam retas de nível como

$$3x + 5y = k$$

para diferentes valores de $k$. À medida que você desloca essa reta na direção de maior lucro, o último ponto em que ela ainda toca a região viável é onde o máximo ocorre.

Em muitos gráficos, esse último contato acontece em um único vértice. Se a reta da função objetivo for paralela a uma aresta da fronteira, vários pontos dessa aresta podem ser ótimos. Nesse caso, ainda existe pelo menos um ponto de canto ótimo.

Erros Comuns

Confundir viável com ótimo

Um ponto pode satisfazer todas as restrições e ainda assim não maximizar nem minimizar a função objetivo. Viável significa apenas permitido.

Esquecer as condições de não negatividade

Se $x$ e $y$ representam quantidades produzidas ou transportadas, valores negativos normalmente não fazem sentido. Omitir $x \ge 0$ ou $y \ge 0$ pode mudar o problema.

Supor que toda resposta deve ser um número inteiro

A programação linear comum permite valores fracionários. Se as variáveis precisarem ser números inteiros, como número de caminhões ou número de trabalhadores, você precisa de um modelo de programação inteira ou de uma condição extra de integralidade.

Supor que todo problema tem uma melhor resposta

Alguns problemas de programação linear são inviáveis, o que significa que nenhum ponto satisfaz todas as restrições. Outros são ilimitados, o que significa que a função objetivo pode melhorar sem limite. Você só obtém um ótimo finito quando as restrições realmente limitam o problema o suficiente.

Usar o método gráfico quando há variáveis demais

Quando há muitas variáveis, fazer o gráfico deixa de ser a ferramenta certa. É aí que o simplex ou outros métodos de otimização se tornam necessários.

Quando a Programação Linear É Usada

A programação linear é usada quando decisões competem por recursos limitados e tanto o objetivo quanto as restrições podem ser modelados linearmente. Exemplos típicos incluem planejamento de produção, transporte, alocação de pessoal, mistura, escalonamento e distribuição de orçamento.

O modelo é tão bom quanto suas hipóteses. Se a relação real não for aproximadamente linear, ou se as variáveis precisarem ser inteiras, um problema de programação linear simples pode ser apenas um ponto de partida.

Tente um Problema Parecido

Pegue um pequeno problema contextualizado com dois produtos, dois limites de recursos e uma função de lucro. Defina as variáveis, represente graficamente as restrições e teste você mesmo os pontos de canto. Quando essa ideia fizer sentido, o método simplex ficará muito mais fácil de entender, porque ele estende a mesma lógica para dimensões maiores.