Programação linear

A programação linear (PL) otimiza uma função objetivo linear sobre uma região viável definida por restrições lineares de igualdade e desigualdade. É a base da pesquisa operacional e o problema que o método Simplex resolve. O insight geométrico-chave: a solução ótima sempre fica em um vértice do politopo viável.

Formulação padrão

Um programa linear em forma padrão:

em que \(x \in \mathbb{R}^n\) são as variáveis de decisão, \(\mathbf{c} \in \mathbb{R}^n\) são os coeficientes do objetivo, \(\mathbf{A} \in \mathbb{R}^{m \times n}\) é a matriz de restrições, e \(\mathbf{b} \in \mathbb{R}^m\) são os valores do lado direito.

Qualquer PL com restrições de desigualdade \(\mathbf{A}x \leq \mathbf{b}\) pode ser convertido para forma padrão introduzindo variáveis de folga \(s \geq 0\):

\[\mathbf{A}x + s = \mathbf{b}, \quad x \geq 0, \quad s \geq 0\]

Um problema de maximização \(\max \mathbf{c}^T x\) é convertido minimizando \(-\mathbf{c}^T x\).

Geometria: por que o ótimo está em um vértice

A região viável \(\mathcal{F} = \{x : \mathbf{A}x \leq \mathbf{b},\, x \geq 0\}\) é um politopo convexo: a interseção de um número finito de semiespaços. Como \(f(x) = \mathbf{c}^T x\) é linear (e, portanto, convexa), seu mínimo sobre um conjunto convexo é atingido em um ponto extremo, um vértice do politopo.

Esse é o fato-chave que torna a PL tratável: em vez de buscar em todo \(\mathcal{F}\) (infinitos pontos), só precisamos verificar os vértices (finitos). O método Simplex explora isso movendo-se de vértice em vértice ao longo das arestas, sempre melhorando o objetivo.

A região sombreada é o conjunto viável. Os contornos do objetivo (linhas de valor igual) são empurrados na direção de aumento de \(3x+2y\). O ótimo está no vértice \((3,1)\), onde \(3(3)+2(1)=11\): o último vértice tocado antes de sair da região viável.

Exemplo completo: planejamento de produção

Uma fábrica produz dois produtos, A e B. Cada unidade de A exige 1 hora de usinagem e 2 horas de montagem. Cada unidade de B exige 2 horas de usinagem e 1 hora de montagem. Disponível: 8 horas de usinagem, 10 horas de montagem por dia. Lucro: R$5 por unidade de A, R$4 por unidade de B.

Formulação:

\[\max\; 5x_A + 4x_B\]

\[\text{sujeito a:} \quad x_A + 2x_B \leq 8 \quad \text{(usinagem)}\]

\[2x_A + x_B \leq 10 \quad \text{(montagem)}\]

\[x_A, x_B \geq 0\]

Vértices da região viável:

A interseção das duas restrições ativas dá \((4, 2)\): resolva \(x_A + 2x_B = 8\) e \(2x_A + x_B = 10\) simultaneamente.

Solução ótima: produzir 4 unidades de A e 2 unidades de B para um lucro de R$28.

Casos especiais

Nem toda PL se comporta tão bem quanto o exemplo de planejamento de produção acima, e vale a pena saber como são as exceções:

Dualidade

Toda PL (o primal) tem um PL dual associado. Para o primal \(\min \mathbf{c}^T x\) s.a. \(\mathbf{A}x \geq \mathbf{b}\), \(x \geq 0\), o dual é:

\[\max \mathbf{b}^T y \quad \text{s.a.} \quad \mathbf{A}^T y \leq \mathbf{c},\quad y \geq 0\]

Dualidade forte: se o primal tem um valor ótimo finito, o dual também tem, e eles são iguais: \(\mathbf{c}^T x^* = \mathbf{b}^T y^*\). As variáveis duais \(y^*\) são os preços sombra: elas medem o quanto o objetivo ótimo melhora se a restrição correspondente for relaxada em uma unidade.

library(lpSolve)

# Production planning example: max 5*xA + 4*xB
obj  <- c(5, 4)
mat  <- matrix(c(1,2, 2,1), nrow=2, byrow=TRUE)
rhs  <- c(8, 10)
dir  <- c("<=", "<=")

sol  <- lp("max", obj, mat, dir, rhs)
sol$solution    # optimal x
sol$objval      # optimal value

# With the lpSolveAPI package for more complex problems
# With CVXR for convex optimization (LP, QP, SOCP)
library(CVXR)
x <- Variable(2, nonneg = TRUE)
prob <- Problem(Maximize(c(5,4) %*% x),
                list(c(1,2) %*% x <= 8,
                     c(2,1) %*% x <= 10))
solve(prob)