Método de planos de corte

Em Pesquisa Operacional, o método de planos de corte é um método exato para Programação linear que busca iterativamente refinar um conjunto viável ou função objetivo por meio de inequações lineares, chamadas cortes. Tais procedimentos são utilizados para encontrar soluções inteiras para problemas de Programação Linear Inteira (PLI), bem como para resolver problemas gerais de otimização convexa. O uso de planos de corte para resolver PLI foi introduzido por Ralph Gomory.

Algoritmo de planos de corte

Iniciamos a resolução do problema a partir de uma solução de um problema de Programação linear. A cada iteração, o algoritmo adiciona uma restrição linear que é satisfeita por uma solução inteira do problema original., eliminando as partes fracionárias da solução não-inteira. O algoritmo chega ao seu fim quando uma solução inteira é obtida.

Problema Inicial

Supondo o problema de maximização

$z=\sum _{j=1}^{n}c_{j}x_{j}$

sujeito as seguintes restrições

$z=\sum _{j=1}^{n}a_{ij}x_{j}=b_{i}\qquad (i=1,2,...,m)$

$x_{j}\in Z^{+}\qquad \qquad \qquad (j=1,2,...,n)$