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.