Combinando o método de Pontos Interiores com o método Simplex para a solução de problemas de programação linear

Resumo

Quando a matriz A de restrições de um problema de programação linear apresenta posto completo, no método Simplex é usada uma submatriznão singular de A para determinar uma solução básica. Neste contexto, no método de Pontos Interiores, quando são usados métodos iterativos precondicionados, também usa-se uma submatriz não singular de A para calcular o precondicionador Separador. O processo que calcula uma solução
básica factível para o método Simplex, a partir de um ponto do método de Pontos Interiores é chamado crossover. Neste trabalho combinam-se ambos os métodos para a solução de problemas de programação linear canalizados, mais precisamente usa-se uma base do precondicionador Separador para determinar se a solução básica associada a ela é factível primai, dual ou infactível no sentido do método Simplex. Resultados numéricos mostram que alguns problemas que não eram resolvidos usando apenas o método de Pontos Interiores, são resolvidos usando a estratégia do crossover. Também observam-se problemas que reduzem consideravelmente o número de iterações do método Simplex quando inicialmente usam o método de Pontos Interiores, isto é, combinam ambos os métodos.