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.

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]. As variáveis binárias são muito úteis para exprimirem situações dicotómicas (sim ou não, fazer ou não fazer, etc.),

  • Integridade total:Todas as variáveis de decisão são do tipo inteiro,como mostra o exemplos abaixo.
33ju7w5.jpg

Exemplo 2

MaxZ = 3 X1 + 2 X2
X1 + X2 <= 6
X1, X2 >= 0
X1, X2 INT
  • Integridade parcial
MaxZ = 3 X1 + 2 X2
X1 + X2 <= 6
X1, X2 >= 0
X1 INT
  • O caso binário
MaxZ = X1 - X2
X1 + X2 <= 2
2 X1 - X2 <= 1
X1, X2 BIN

RESOLUÇÃO DE PROGRAMAÇÃO NO EXCEL

ALGUNS PROBLEMAS TÍPICOS DE PROGRAMAÇÃO INTEIRA

* PROBLEMA DE AFETAÇÃO

O Problema de Afetação (em inglês, Assignment Problem) é conhecido por este nome por ser a representação de inúmeras situações em que é necessário afetar pessoas a lugares, a tarefas ou a zonas de trabalho, máquinas a tarefas, etc. Aparece muitas vezes como se tratasse de um problema de PL mas, como veremos, as suas variáveis de decisão são binárias.

Suponhas que se pretende afetar n indivíduos a n tarefas, sabendo que a medida de eficiência de afetar o indivíduo i à tarefa j é cij (que tanto pode representar um lucro como um custo). Pretende-se determinar a afetação dos indivíduos às tarefas de modo a otimizar a eficiência total.
As variáveis de decisão são as seguintes:

Xij=1, se o indivíduo i for afetado à tarefa j
0, se o indivíduo i não for afetado à tarefa j
i=1, .., n j= 1,.., n
**

O modelo de Programação Linear Inteira segue o modelo:

 MIN ou MAX  otimizar a eficiência total

s.a

1. cada indivíduo só pode estar afetado a uma tarefa:

2. cada tarefa só deve ser desempenhada por um indivíduo:

Trata-se, como se pode ver, de um modelo muito simples e cujo sistema de restrições tem uma estrutura particular com certas propriedades. Situações em que o número de indivíduos é diferente do número de tarefas podem também ser representadas.
Um problema que seja representado por um modelo com esta estrutura chama-se problema de afetação, independentemente da situação que estiver a ser considerada.
Os problemas de afetação dispõem de um método de resolução próprio graças à sua estrutura especial.

Playlist: Videoaulas complementares

Exercício de programação linear inteira usando Solver do Excel

Modelagem e Otimização de Modelos de Programação Inteira

Salvo indicação em contrário, o conteúdo desta página é licenciado sob Creative Commons Attribution-ShareAlike 3.0 License