O que é programação linear inteira?

Problemas inteiros de programação linear surgem ao tentar resolver sistemas lineares, especificando que todas as variáveis ​​desconhecidas devem ser inteiros ou números inteiros. Os 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; Ou seja, ele 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 o derivado e configurando -o igual a zero. Em seguida, pode verificar se o ponto é um máximo ou mínimo, verificando seu bairro imediato na função. Enquanto o derivado for definido em cada ponto ao longo da função, o computador possui apenas um número limitado de possiblose soluções para verificar.

A programação linear se torna 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; É reflexivo, no entanto, do mundo real, no qual os itens geralmente vêm em unidades discretas e individuais. 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 pode optar por vender uma fração de um produto.

Depois que as restrições inteiras estão em vigor, o problema de resolver o sistema linear é o NP-completo. Isso significa que o tempo necessário para um computador resolver o sistema é indeterminado. Com restrições inteiras, computadorS não pode usar a ferramenta da derivada, porque não há garantia de que o ponto zero da derivado cairá sobre um número inteiro. A solução será o número inteiro com o valor mais alto ou mais baixo de todos os números inteiros, para que o computador teria que verificar todos eles - um processo que poderia 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 de resolver problemas de programação linear inteira é o algoritmo de ramificação e ligado, no qual o computador resolve uma série de problemas relacionados ao original para restringir a faixa de valores disponíveis para uma solução. Para problemas complexos, no entanto, isso pode levar muito tempo.