O algoritmo simplex resolve problemas de PL construindo uma solução admissível no vértice do poliedro, e então percorre os vértices do poliedro que sucessivamente possuem valores mais altos da função objectivo até encontrar o máximo. Embora este algoritmo seja bastante eficiente na prática, e seja garantido de encontrar um óptimo global se certas condições para se evitar ciclos forem assumidas, ele é fraco no pior-caso: é possível construir um problema de programação linear prático para o qual o método simplex realiza uma quantidade exponencial de passos em relação ao tamanho do problema. Na verdade, por algum tempo não se soube se problemas de programação linear eram NP-completos ou tinham solução em tempo polinomial.
O primeiro algoritmo de programação linear em tempo polinomial no pior caso foi proposto por Leonid Khachiyan em 1979. Foi baseado no [método do elipsóide] da nonlinear optimization de Naum Shor, que é uma generalização do método da elipsóide da [optimização convexa] de Arkadi Nemirovski, uma dos ganhadores do John von Neumann Theory Prize 2003, e D. Yudin.
Entretanto, a performance prática do algoritmo de Khachiyan é desapontante: geralmente, o método simplex é mais eficiente. Sua grande importância é que ele encoraja a pesquisa dos métodos de pontos interiores. Ao contrário de algoritmo simplex, que apenas evolui ao longo de pontos na fronteira da região factível, métodos de ponto interior podem se mover pelo interior da região factível.
Em 1984, Narendra Karmarkar propôs seu método projetivo, que tornou-se o primeiro algoritmo a apresentar um bom desempenho tanto na teoria como na prática: seu pior caso de complexidade é polinomial e os problemas práticos de experiência mostram que ele é razoavelmente eficiente em comparação com o algoritmo simplex. Desde o método de Karmarkar, muitos outros métodos de pontos interiores têm sido propostos e analisados. Um método bastante popular é o Método Preditor-corretor de Mehrotra, cuja atuação possui bom desempenho na prática, ainda que pouco se saiba sobre ele na teoria.
A opinião mais recente entre os estudiosos é que a eficiência das boas implementações dos métodos baseados em simplex e dos pontos interiores são similares para a aplicação de rotina no programa linear.
As soluções do programa linear estão em uso generalizado de otimização de diversos problemas na indústria, como a otimização de fluxo de transporte, que pode ser transformada em problemas de programação linear sem muitas dificuldades.
O primeiro algoritmo de programação linear em tempo polinomial no pior caso foi proposto por Leonid Khachiyan em 1979. Foi baseado no [método do elipsóide] da nonlinear optimization de Naum Shor, que é uma generalização do método da elipsóide da [optimização convexa] de Arkadi Nemirovski, uma dos ganhadores do John von Neumann Theory Prize 2003, e D. Yudin.
Entretanto, a performance prática do algoritmo de Khachiyan é desapontante: geralmente, o método simplex é mais eficiente. Sua grande importância é que ele encoraja a pesquisa dos métodos de pontos interiores. Ao contrário de algoritmo simplex, que apenas evolui ao longo de pontos na fronteira da região factível, métodos de ponto interior podem se mover pelo interior da região factível.
Em 1984, Narendra Karmarkar propôs seu método projetivo, que tornou-se o primeiro algoritmo a apresentar um bom desempenho tanto na teoria como na prática: seu pior caso de complexidade é polinomial e os problemas práticos de experiência mostram que ele é razoavelmente eficiente em comparação com o algoritmo simplex. Desde o método de Karmarkar, muitos outros métodos de pontos interiores têm sido propostos e analisados. Um método bastante popular é o Método Preditor-corretor de Mehrotra, cuja atuação possui bom desempenho na prática, ainda que pouco se saiba sobre ele na teoria.
A opinião mais recente entre os estudiosos é que a eficiência das boas implementações dos métodos baseados em simplex e dos pontos interiores são similares para a aplicação de rotina no programa linear.
As soluções do programa linear estão em uso generalizado de otimização de diversos problemas na indústria, como a otimização de fluxo de transporte, que pode ser transformada em problemas de programação linear sem muitas dificuldades.
Comentários
Postar um comentário