Programação Linear Inteira (PLI)

Programação Linear Inteira (PLI)

São programações nas quais algumas ou todas variáveis estão restritas a valores inteiros (ou discretos). Há dois algoritmos proeminentes de PLI; branch-and-bound (B&B) e planos de corte. O qual o mais eficiente e utilizado é o B&B.

Uma desvantagem dos algoritmos de PLI é a sua falta de consistência na resolução de problemas com inteiros. Embora seja comprovado teoricamente que esses algoritmos convergem em um número finito de iterações, sua implantação em computador (com seu inerente erro de arredondamento) é uma experiência diferente.

Aplicações Ilustrativas:

De modo geral existem duas categorias nas aplicações de PLI: direta e transformada. Na direta , as variáveis são naturalmente inteiras e podem assumir valores binários ( 0 ou 1). Por exemplo, o problema pode envolver a determinação de se um projeto será ou não selecionado para execução (binário) ou achar o número ótimo de máquinas necessárias para executar uma tarefa (valor discreto geral). Na categoria transformada, o problema original, que pode ou não envolver quaisquer variáveis inteiras, é intratável analiticamente. Variáveis auxiliares inteiras (em geral binárias) são usadas para transformá-lo em tratável. Por exemplo, na determinação da sequência de tarefas, A e B, em uma única máquina, a tarefa A pode preceder a tarefa B, ou a tarefa B pode preceder a tarefa A. A natureza “ou” das restrições é que torna o problema analiticamente intratável porque todos os algoritmos matemáticos de programação matemática tratam apenas de restrições “e”. A situação remediada usando variáveis binárias auxiliares para transformar as restrições “ou” em restrições “e” equivalentes.

Por conveniência, um problema inteiro puro é definido como aquele que tem todas as variáveis inteiras. Caso contrário é um problema de programação inteira mista, se tratar de variáveis contínuas, bem como inteiras.

Orçamento de Capital (PLI)

Trata-se de decisões referentes a investir ou não em projetos individuais. A decisão é tomada sob consideração de orçamento limitado, bem como de prioridades na execução dos projetos.

Exemplo 1 (Seleção de projeto):

Cinco projetos estão sob avaliação dentro de uma projeção de planejamento de três anos. A tabela a seguir dá os retornos esperados para cada projeto e os desembolsos anuais associados.

	Desembolsos (milhões $) / ano
Projeto	1	2	3	Retornos (milhões $)
1	5	1	8	20
2	4	7	10	40
3	3	9	2	20
4	7	4	1	15
5	8	6	10	30
Fundos disponíveis (milhões $)	25	25	25

                        

                         Quais projetos devem ser selecionados na projeção de três anos?

O problema se reduz a uma decisão “sim-não” para cada projeto.

Defina-se a variável binária x_j como

 

X_{j =        1,  se o projeto j for selecionado}

           _{0, se o projeto j não for selecionado}

O problema de PLI é:

Maximizar z = 20 x1 + 40 x2 + 20 x3 + 15 x4 + 30 x5

Sujeito a

5x1 + 4x2 + 3x3 + 7x4 + 8x5 <= 25

1x1 + 7x2 + 9x3 + 4x4 +6x5 <= 25

8x1 + 10x2 +2x3 + 1x4 + 10x5 <= 25

x1,x2,x3,x4,x5=(0,1)

           A solução ótima (obtida pelo LPSolver) é x1=x2=x3=x4=1, x5=0, com z=95 (milhões $). A solução mostra que todos os projetos, com exceção do 5, devem ser selecionados.