O problema de estratificação ótima está associado à área de amostragem probabilística. Nesse problema deve-se delimitar os estratos populacionais e definir a alocação da amostra, considerando um dos seguintes objetivos: (i) minimizar a variância de um estimador de total; (ii) minimizar o tamanho amostral. Em função de sua relevância prática e alta complexidade computacional, diversos métodos heurísticos têm sido propostos na literatura. Não obstante, boa parte desses métodos produz soluções de qualidade apenas razoável e com algumas limitações de aplicabilidade. Neste trabalho, foi proposto um algoritmo para resolução do problema de estratificação ótima univariado com o objetivo (ii) de minimizar o tamanho da amostra dado um nível de precisão fixado. Para problemas de menor complexidade o método ´ de enumeração exaustiva é aplicado, enquanto em problemas de maior complexidade o algoritmo é baseado nas metaheurísticas Variable Neighborhood Decomposition Search com Path Relinking. O método proposto foi aplicado em cem populações (sendo 25 já utilizadas na literatura e 75 da Pesquisa Anual do Comércio), com quatro diferentes números de estrato e comparado com dois métodos bem conhecidos da literatura. O método foi capaz de produzir a melhor solução para 97% dos casos considerados, e além disso, em 38% ainda foi capaz de garantir que a solução corresponde a um mínimo global. Destarte, apresenta-se como uma alternativa promissora aos métodos existentes na literatura, embora leve a um maior tempo computacional.