Otimização Mono Objetivo

Primeiro Trabalho – Algoritmo De Pontos Interiores E Simplex

Aluno: Francirley Resendes Borges Costa

1. METODOLOGIA DE TESTE

Várias execuções do foram realizadas para determinar os impactos das variáveis que controlam a dimensão do espaço, o passo e o gap de dualidade, além do chaveamento entre o algoritmo de pontos interiores e SIMPLEX. Primeiramente foram definidos os valores que seriam testados para cada uma das variáveis de impacto do algoritmo, log definiu-se:

• Número de dimensões: Variando entre 3 até 20, visto que acima de 20 dimensões o algoritmo demorava bastante tempo para resolver o simplex, levando a crer que era desnecessário testá-lo acima de 20 dimensões.
• Passo: Variando entre os valores 0.25, 0.50, 0.75 e 0.99.
• GAP de dualidade: variando entre , ,  e  [pic 1][pic 2][pic 3][pic 4]

Foram realizadas  execuções do algoritmo, totalizando 288 iterações, e para testar o seu desempenho, usaram-se os valores de: Quantidade de iterações e tempo de convergência ou execução. Além disso foi definido que o máximo de iterações possíveis seriam 200. [pic 5]

1. RESULTADOS

Variável Dimensão: Percebeu-se que variando a dimensão do problema, quanto maior era seu valor, mais iterações eram necessárias para convergência do algoritmo, percebeu-se que seu custo computacional aumentava exponencialmente, tanto em tempo de execução quanto em quantidade de iterações.

Variável GAP de Dualidade: Visto que o GAP de dualidade é a menor diferença aceitável entre o valor da função objetivo do problema primal e o do problema dual, a variável que controla o GAP atingiu o algoritmo de maneira que, quanto menor é seu valor, mais iterações o algoritmo fez para convergir em uma solução ótima e mais próxima do vértice ótimo o foi o resultado.

Variável PASSO: Determina o tamanho da distância percorrida na direção da solução ótima pelo algoritmo de pontos interiores (seu valor varia de “0 < passo < 1”), a variável que controla o passo atingiu o funcionamento do algoritmo de forma que, quanto mais próximo de 1 é o foi o seu valor, menor foi a quantidade de iterações que o algoritmo fez e vice-versa, essa valor também atingiu a precisão do algoritmo, visto que ele, definido com passo mais conservador, não convergiu devido ao fato do critério de parada pela quantidade de iterações.

Fase dos Pontos interiores: É sabido que, quanto maior o espaço dimensional “n”, maior é a complexidade do algoritmo, ou seja, maior é o custo computacional para resolver o problema. Verificando o comportamento do algoritmo, ainda na fase dos pontos interiores, percebe-se que quanto menor o valor de passo, mais iterações ou custo computacional serão feitas. Também foi verificado que quanto menor é o valor do Gap de dualidade, menor é o erro, ou seja, mais preciso é o resultado em relação ao vértice ótimo, além disso, alterar o valor do Gap também aumenta o custo computacional, fazendo com que o algoritmo faça mais iterações.

Fase simplex: Encontrado o valor ótimo definido pelo algoritmo de pontos interiores, o resultado (Xsol_pi) é passado para um algoritmo que implementa o método de Murty (MurtyAlgoritm) esse por sua vez tenta encontrar um vértice próximo ao ponto interior encontrado, feito isso, o algoritmo passa para a solução através do método SIMPLEX, que resolve o problema, encontrando o vértice ótimo.

Com os testes efetuados, os resultados encontrados mostraram que o algoritmo de pontos interiores normalmente encontra uma solução bem próxima do vértice ótimo, quase sempre, com taxas de erro abaixo de 0,01%, levando-se em consideração os valores ideais de Passo e Gap, e em casos isolados, alguns erros consideráveis, acima de 99%, esses principalmente quando era atingido o número máximo de iterações. Com os testes efetuados, e considerando os testes com erros isolados e sem ajustes de Passo e Gap de dualidade ideais para o problema, em média o algoritmo de pontos interiores gastou 25 iterações (variando de 5 até 200) e erro de 6% (variando entre  até 99%).[pic 6]

Com o ponto factível encontrado pelo algoritmo dos pontos interiores, é então calculado um vértice factível para ser usado como ponto inicial no algoritmo SIMPLEX. O que foi percebido é que, em todos os casos, o SIMPLEX, partindo do ponto factível, resolveu o problema do hipercubo de Klee-Minty em apenas 33% das iterações que seriam necessárias, se o algoritmo partisse do ponto inicial. Também é calculado o erro porcentual da solução ótima encontrada pelo SIMPLEX, que sempre apresenta 0% de erro, indicando que o valor encontrado é de fato a solução ótima esperada.

1. 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.