Otimização Mono Objetivo

...

- CONCLUSÕES

Levando em consideração os resultados obtidos, percebeu se que, o algoritmo híbrido sempre encontra a solução ótima, mesmo com a solução do algoritmo de pontos interiores apresentando um erro considerável, porém, para soluções abaixo de 8 dimensões, o algoritmo híbrido apresentou tempo de execução maior do que o algoritmo que usa apenas o método SIMPLEX, a partir de 9 dimensões o algoritmo híbrido se comportou melhor.

Já levando em consideração a quantidade de iterações, até 4 dimensões o algoritmo híbrido apresentou mais iterações que o algoritmo SIMPLEX, esse por sua vez apresentou resultados muito inferiores a partir de 5 dimensões.

- CONSIDERAÇÕES FINAIS

Algumas considerações foram levantadas pelo professor e então respondidas:

1 – Alguma sugestão de algoritmos para determinar o vértice mais próximo de um politopo definido por Ax

Ajustando as variáveis de Passo e Gap de dualidade é possível obter ótimos resultados para o algoritmo híbrido encontrar o ponto interior factível mais próximo, porém percebeu-se que, em todos os casos, mesmo com pontos interiores que expressavam erros acima de 99%, quando era realizado o método simplex, a partir do ponto interior factível obtido, esse encontrava o resultado em apenas 33% das iterações, no caso do método SIMPLEX partindo do ponto inicial, sendo assim, percebe-se que o algoritmo poderia melhorar, pois na maioria dos casos, a solução obtida pelos pontos interiores é muito próxima do vértice ótimo, levando a crer que, com a aplicação do método de Murty, o vértice mais próximo já seria o vértice solução, o que não acontece de fato.

2 – Quais as vantagens e desvantagens desse algoritmo?

Percebeu-se que, para até 4 dimensões, o algoritmo SIMPLEX é muito mais rápido que o híbrido, esse por sua vez é muito mais ágil com problemas maiores, encontrando a solução em tempo e quantidade de iterações mais satisfatórias, logo, o algoritmo podia ser melhorado para tomar decisão de usar o método simplex isoladamente em casos com este.

3 – Alguma sugestão para que este algoritmo melhore o desempenho?

Algumas sugestões como, decisão para usar o método simplex isoladamente em dimensões menores, visto que seu desempenho se mostrou superior, e ainda, tentar refinar a solução de Murty para encontrar outros vértices próximos da solução factível encontrada pelos pontos interiores, pois parece que o algoritmo sempre parte de um ponto que ainda faz o SIMPLEX passar em muitos vértices.

4 - O vértice do politopo de restrição para o algoritmo simplex, calculado como sendo o mais próximo da solução dos pontos interiores, é realmente o vértice mais próximo?

Verificando os resultados obtidos essa questão levanta dúvidas, pois o ponto encontrado pelo algoritmo de Murty (Murtyalgoritm.m) é o mesmo ponto encontrado pelo algoritmo dos pontos interiores e, em todos os casos, o vértice que é dado para o algoritmo SIMPLEX, como sendo o ponto inicial ou mais próximo do ponto factível, difere bastante do encontrado pelo algoritmo de pontos interiores.