Programação Linear (2D)

A programação linear otimiza uma função objetivo linear sujeita a restrições lineares de igualdade e desigualdade. A região viável forma um poliedro convexo. O teorema fundamental estabelece que a solução ótima deve ocorrer num dos vértices do poliedro, resolvido de forma eficiente pelo algoritmo Simplex.

Em termos simples, você está equilibrando recursos limitados sob várias regras ao mesmo tempo, e cada desigualdade recorta uma parte do plano. Onde todas as regras se sobrepõem fica a região viável, e cada ponto dentro dela é um plano válido. Como uma função objetivo linear sempre melhora numa direção, a melhor solução cai num vértice onde as restrições se encontram. A lição: para otimizar você nunca testa todos os pontos, apenas o punhado de vértices.

Em 1945, o economista George Stigler estudou a dieta mais barata que cobrisse todas as necessidades nutricionais, um problema linear com 77 alimentos. Sem um algoritmo, fez uma estimativa astuta e chegou a cerca de $39.93 por ano (preços de 1939). Quando o método simplex de Dantzig o resolveu com exatidão em 1947, o mínimo real era $39.69 — a estimativa manual de Stigler errou por apenas cerca de 24 centavos ao ano. Assim, a economia árida virou um dos casos fundadores da programação linear.