Programação Inteira

A programação inteira é a classe de problemas que podem ser expressos como a otimização de um sujeito de função linear para um conjunto de restrições lineares sobre variáveis de número inteiro. Na realidade, trata-se de um problema NP completo. Talvez o mais importante seja o fato de que os programas de número inteiro que podem ser resolvidos para otimização comprovável em um tempo razoável são muito menores em tamanho do que seus equivalentes de programação linear.
Na programação inteira, uma ou mais variáveis de decisão devem assumir valor inteiro e não negativo. Geralmente os softwares permitem transformar problemas de PL em PI, através da inclusão de restrições de integridade.

Modelo genérico

(1)

\begin{align} max: \sum_{i=1}^{N} \sum_{k=1}^{M} D_{ik}X_{ik} \end{align}

(2)

\begin{equation} S.a. \end{equation}

(3)

\begin{align} \sum_{i=1}^{N} X_{ik} \geq R_i \end{align}

(4)

\begin{equation} INT X_{ik} \end{equation}

Tipos de programação inteira

• Puros: todas as variáveis de decisão são inteiras
• Mistos: algumas variáveis de decisão são inteiras
• Booleanos: variáveis de decisão só apresentam valores inteiros no intervalo [0, 1]
• Integridade total: todas as variáveis de decisão são do tipo inteiro