Programação Linear

Um programa linear é o problema de maximizar ou minimizar uma função linear c⊤x, a função objetivo, sujeita a restrições também lineares. As variáveis são reais e em geral não negativas.

Simplex e dual deste tópico reutilizam a mesma forma padrão Ax = b, x ≥ 0 e os mesmos vértices do poliedro factível.

As páginas se agrupam em três blocos. O primeiro escreve o modelo e o converte à forma padrão: folga soma numa ≤, excesso subtrai numa ≥; cada solução básica factível é um vértice.

O segundo desenha a região factível no plano: cada desigualdade corta um semiplano, e o ótimo finito ocorre num vértice — listam-se os cruzamentos factíveis e compara-se z.

O terceiro visita um vértice vizinho por iteração no tableau — entra a não básica, sai a menor razão positiva, pivoteia como Gauss — e monta o dual min b⊤y a partir do tipo de cada restrição primal.

Introdução à Programação Linear monta c⊤x, introduz folgas e excessos, e avalia z nos vértices do polígono. Método simplex executa o teste de entrada, o teste da razão e o pivô até a linha z não ter negativos.

Infactível ou ilimitado pelos semiplanos está em Introdução à Programação Linear. Coluna que entra sem entrada positiva, ou Fase I que não zera artificiais, está em Método simplex.

O dual de um primal misto — y livre numa igualdade, y ≥ 0 numa ≤, y ≤ 0 numa ≥, objetivo com b e restrições com c — está em Método simplex.