ESTUDO E IMPLEMENTAÇÃO DE UM ALGORITMO COM BASE NO MÉTODO DE PONTOS INTERIORES PARA PROGRAMAÇÃO LINEAR

Resumo

Karmarkar (1984) revolucionou a área de programação linear ao propor um algoritmo de complexidade polinomial para problemas de programação linear, essa pesquisa deu origem ao novo campo chamado método de pontos interiores. Os métodos de pontos interiores têm como principal característica a de realizar a busca por soluções no interior da região viável do problema. Em teoria, os métodos de pontos interiores são melhores que o método simplex. Na prática ambos métodos concorrem ate hoje.Neste trabalho foi realizado um estudo do método de pontos interiores, especificamente, foi estudado o algoritmo primal-dual de passos curtos. O método necessita de um ponto interior da região de solução viável. A partir daí, gera-se novos pontos interiores em uma vizinhança gerando uma trajetória central até atingir uma solução aproximada com certo grau de tolerância para uma solução ótima. O método estudado resolve de maneira eficiente um conjunto de sistemas de equações lineares a cada iteração, para isso faz uso de conceitos de álgebra matricial juntamente com o método de Newton estendido e fatoração de Cholesky. O algoritmo foi testado usando o Excell e implementado no software Scilab.Neste trabalho foi estudado o algoritmo de trajetória central de passos curtos, o algoritmo foi testado utilizando o Excell e implementado no software Scilab, em ambos os testes o método obteve o resultado ótimo. Nesta implementação preliminar, o ponto inicial interior à região de solução viável foi dado e não foi utilizada fatoração de cholesky, o sistema foi resolvido pelo calculo direto da matriz inversa, pois o Scilab possui funções que realizam o calculo dessa matriz, mas em futuras implementações do método na linguagem de programação C++ será incorporada a fatoração de cholesky para resolver o sistema de maneira mais eficiente.Nos testes realizados foi observado que o método tem uma convergência lenta ao se aproximar da solução ótima, porém o resultado é satisfatório. O desempenho do algoritmo em problemas pequenos é caro se comparado ao método simplex, espera-se melhor desempenho em problemas de maior porte.