O que é programação linear inteira?

Problemas de programação linear inteira surgem ao tentar resolver sistemas lineares ao especificar que todas as variáveis ​​desconhecidas devem ser números inteiros ou inteiros. Sistemas lineares são conjuntos de equações que descrevem uma situação para a qual o programador está tentando encontrar uma solução. Eles geralmente consistem em uma equação que deve ser maximizada ou minimizada e uma ou mais equações restritivas que colocam limites em variáveis ​​desconhecidas. Para que o sistema seja linear, cada restrição deve ser uma equação linear; isto é, não deve conter instâncias da variável desconhecida com expoentes maiores que um.

Sistemas lineares regulares podem ser resolvidos facilmente usando um computador. O programa pode identificar uma solução encontrando a derivada e definindo-a como zero. Em seguida, ele pode verificar se o ponto é máximo ou mínimo, verificando sua vizinhança imediata na função. Desde que a derivada seja definida em cada ponto da função, o computador possui apenas um número limitado de soluções possíveis para verificar.

A programação linear torna-se programação linear inteira com a adição da restrição inteira. Isso significa que o problema permanece o mesmo, mas a resposta deve consistir em valores inteiros para os valores desconhecidos: eles devem ser números inteiros. Às vezes, isso significa que a solução será abaixo do ideal em comparação com o caso em que as frações são permitidas; é reflexo, no entanto, do mundo real, no qual itens geralmente vêm em unidades discretas e indivisíveis. Isso torna a programação linear inteira importante para aplicativos de negócios, pois as empresas desejam maximizar os lucros o máximo possível, mas não podem optar por vender uma fração de um produto.

Uma vez que as restrições de número inteiro estejam em vigor, o problema de resolver o sistema linear é NP-complete. Isso significa que o tempo necessário para um computador resolver o sistema é indeterminado. Com restrições de número inteiro, os computadores não podem usar a ferramenta da derivada porque não há garantia de que o ponto zero da derivada caia em um número inteiro. A solução será o número inteiro com o valor mais alto ou mais baixo dentre todos os números inteiros, para que o computador precise verificar todos eles - um processo que pode levar uma quantidade infinita de tempo.

Os programadores desenvolveram heurísticas, ou métodos de solução de problemas, para lidar com a complexidade desses problemas. Um método para resolver problemas de programação linear inteira é o algoritmo branch and bound, no qual o computador resolve uma série de problemas relacionados ao original para restringir o intervalo de valores disponível a uma solução. Para problemas complexos, no entanto, isso pode levar um longo tempo.