Introdução
A programação Linear Inteira Mista tem uma grande vantagem em relação a Programação Inteira que é permitir que sejam incluídos na análise os custos fixos, bem como diferentes níveis de custos variáveis para as instalações. Estes problemas possuem soluções mais complexa em relação aqueles que utilizam a Programação Linear. Contudo na Programação Linear, existem condições necessárias e suficientes de otimização teoricamente provadas que podem ser utilizadas para testar eficientemente se uma dada solução viável é uma solução ótima ou não.
A Programação Linear está preocupada com a maximização ou minimização de uma equação sobre certos critérios ou restrições. Abaixo temos um exemplo:
Exemplo:
Este problema pode ser resolvido pelo Método Simplex ou Simplex duas Fases. A solução ótima se encontra abaixo:
`x = (x_1,x_2,x_3) = (0.5,0,1.5)`
Problemas como estes são utilizados em todas as empresas para minimizar o desperdício, maximizar lucro, ou otimizar a outros aspectos do negócio . No entanto, algumas partes da solução pode ser limitada a números inteiros, `x in Z^+`
Programação linear inteira mista é uma PL(Programação Linear) que existe alguma ou todas as variáveis não inteiras. Portanto precisamos de encontrar uma nova solução ótima para evitarmos casos de números parciais. Simplesmente com o arredondamento, a solução muitas vezes pode sair da região viável, comprometendo a otimalidade.
Resolvendo PLIM Usando Branch-Bound
O problema com a resolução de PLIMs usando o método Simplex é que ele frequentemente retorna partes de ` x = (x_1,x_2,x_3)` que não estão em forma de número inteiro.
Para resolver usando o Branch and Bound, primeiro resolvemos o problema usando o Relaxamento, o que significa resolvê-lo pelo Simplex Revisado como se não houvesse restriçőes inteiras. Assim, obtemos: ` z = cx`.
Como o exemplo usado envolve um problema de maximização que engloba todas as soluçőes inteiras, então esse é um limite superior da PLIM. Em seguida, escolhe-se uma variável não inteira. Comumente, escolhe-se a variável mais fracionada, que esteja mais próxima do valor mediano ou mais distante de um número inteiro.
Por exemplo, em ` x = (1.25, 3.45, 2.75, 5)`, escolhe-se ramificar em `x_2`, pois `0.45` está mais próximo de `0.5` do que as outras fraçőes. A partir disso, criamos dois subproblemas ou dois nodos de nossa árvore. Em um nó adicionamos a restrição `x_2 <=3`, na outra adicionamos `x_2>=4`. Seja `S` o conjunto solução viável do relaxamento: `S = {x: Ax <=b\ e\ x>=0}`, temos que:
` S_1 = S \cap{x:x_j <=\ lfloor\hat{x}_j\rfloor\} ` ` S_1=S \cap{x:x_j>= \ceil{hat{x}_j}} `
Então, cada um dos nós devem ser resolvidos com suas novas restriçőes pelo método Dual Simplex. Caso o problema seja inviável, então o nó é cortado por inviabilidade. A solução ótima é encontrada quando todos os nós fracionários são cortados.