Método de planos de corte

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

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[editar | editar código-fonte]

Supondo o problema de maximização


z = \sum^n_{j=1} c_j x_j

sujeito as seguintes restrições

z = \sum^n_{j=1} a_{ij} x_j = b_i \qquad (i = 1, 2, ..., m)

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