Programação linear
Em matemática, problemas de Programação Linear (PL) são problemas de optimização nos quais a função objetivo e as restrições são todas lineares.
Aqui está um exemplo de problema de programação linear. Suponha que um fazendeiro tem um pedaço de terra de digamos, A km2, para ser semeado com trigo ou cevada ou uma combinação de ambas. O fazendeiro tem uma quantidade limitada de fertilizante F permitido e de inseticida P permitido que podem ser usados, cada um deles sendo necessários em quantidades diferentes por unidade de área para o trigo (F1, P1) e para a cevada (F2, P2). Seja S1 o preço de venda do trigo, e S2 o da cevada. Se chamarmos a área plantada com trigo e cevada de x1 e x2 respectivamente, então o número ideal de km2 de plantação com trigo vs. cevada pode ser expresso como um problema de programação linear:
Geometricamente, as restrições lineares definem um poliedro convexo, que é chamado de conjunto dos pontos viáveis. Uma vez que a função objectivo é também linear, todo ótimo local é automaticamente um ótimo global. A função objetivo ser linear também implica que uma solução ótima pode apenas ocorrer em um ponto da fronteira do conjunto de pontos viáveis. Existem duas situações nas quais uma solução ótima não pode ser encontrada. Primeiro, se as restrições se contradizem (por exemplo, x ≥ 2 e x ≤ 1) logo, a região factível é vazia e não pode haver solução ótima, já que não pode haver solução nenhuma. Neste caso, o PL é dito inviável. Alternativamente, o poliedro pode ser ilimitado na direção da função objetivo (por exemplo: maximizar x1 + 3 x2 sujeito a x1 ≥ 0, x2 ≥ 0, x1 + x2 ≥ 10), neste caso não existe solução ótima uma vez que soluções arbitrariamente grandes da função objetivo podem ser construídas, e o problema é dito ilimitado.
O algoritmo simplex resolve problemas de PL construindo uma solução admissível no vértice do poliedro, e então percorre os vértices do poliedro que sucessivamente possuem valores mais altos da função objectivo até encontrar o máximo. Embora este algoritmo seja bastante eficiente na prática, e seja garantido de encontrar um óptimo global se certas condições para se evitar ciclos forem assumidas, ele é fraco no pior-caso: é possível construir um problema de programação linear prático para o qual o método simplex realiza uma quantidade exponencial de passos em relação ao tamanho do problema. Na verdade, por algum tempo não se soube se problemas de programação linear eram NP-completos ou tinham solução em tempo polinomial. O primeiro algoritmo de programação linear em tempo polinomial no pior caso foi proposto por Leonid Khachiyan em 1979. Foi baseado no [método do elipsóide] da nonlinear optimization de Naum Shor, que é uma generalização do método da elipsóide da [optimização convexa] de Arkadi Nemirovski, uma dos ganhadores do John von Neumann Theory Prize 2003, e D. Yudin.
Se todas as variáveis do problema pertencerem ao conjunto dos números inteiros, temos uma sub-classe da Programação Linear chamada Programação Inteira (PI) ou programação linear inteira. Ao contrário da PL que pode-se encontrar a solução óptima em um tempo razoável, muitos problemas de Programação Inteira são considerados NP-difícil. Se as variáveis forem binárias, ou seja, assumirem somente os valores 0 (zero) ou 1, temos um caso especial da PI, que também pode ser classificado como NP-difícil. Quando somente algumas das variáveis são inteiras e outras contínuas, temos a "Programação Inteira Mista" (PIM). Existem no entanto algumas classes de problemas que podem ser resolvidos na perfeição em tempo polinomial, estes têm uma estrutura matricial própria chamada Matrizes totalmente unimodulares. Alguns algoritmos aplicados com sucesso na PI são:
