Solver: Qual o método de resolução que devo escolher?

Como Escolher o Método de Resolução Com o Solver

O Solver do Microsoft Excel é uma ferramenta valiosa para resolver problemas de programação linear e não-linear, para encontrar soluções ótimas. A partir da versão 2010 do Excel, existem três algoritmos de resolução disponíveis na caixa "Select a Solving Method": o Método Simplex LP, o Método GRG Nonlinear e o Método Evolutionary Solver.

Então, qual dos métodos de resolução do Solver escolher?

Para fazer a escolha do método de resolução mais apropriado é necessário ter em atenção ao problema que se pretende resolver e ao tipo de funções que estão envolvidas nas células da função objetivo e nas células das restrições.

O Método Simplex LP

O Método Simplex LP é utilizado quando o objetivo e as restrições são funções lineares das variáveis de decisão. Ele é o algoritmo ideal para problemas de otimização linear. 

O método Simplex LP é um algoritmo de resolução de problemas utilizado no Solver do Microsoft Excel para encontrar soluções ótimas para problemas de programação linear. Ele é utilizado quando o objetivo e as restrições são funções lineares das variáveis de decisão, ou seja, quando o declive é constante. Este é o algoritmo padrão utilizado para problemas de otimização linear.

O Simplex LP é baseado no método Simplex, que é uma técnica de otimização que utiliza a análise de tabelas para encontrar a solução ótima de um problema de programação linear. Ele funciona iterando através de diferentes soluções possíveis, até encontrar a solução ótima. O método Simplex LP é o algoritmo de resolução mais amplamente utilizado para problemas de programação linear e é conhecido por ser muito eficiente em termos de tempo de processamento.

Uma das principais vantagens do Simplex LP é que ele é capaz de lidar com problemas lineares de forma eficiente e é capaz de encontrar soluções ótimas para problemas que possuem múltiplos pontos de ótimo. Além disso, ele é capaz de lidar com problemas que possuem restrições de igualdade e desigualdade.

No entanto, o Simplex LP tem suas desvantagens. Ele não é capaz de lidar com problemas não-lineares e não é capaz de lidar com problemas que possuem restrições de inteiro ou binário. Ele também pode ter dificuldade em encontrar soluções ótimas para problemas que possuem restrições muito complexas.

O Método GRG Nonlinear

O Método GRG Nonlinear é utilizado quando o objetivo e as restrições resultam de funções não lineares das variáveis de decisão, como operações matemáticas que envolvem potências, cálculo exponencial ou trigonométrico. 

O método Generalized Reduced Gradient (GRG) é um algoritmo de resolução de problemas utilizado no Solver do Microsoft Excel para encontrar soluções ótimas para problemas de programação não-linear. Ele é utilizado quando o objetivo e as restrições resultam de funções não lineares das variáveis de decisão.

O GRG é baseado no método de gradiente reduzido, que é uma técnica de otimização que utiliza a derivada da função objetivo para encontrar a direção de melhoria e, em seguida, atualiza as variáveis de decisão na direção de melhoria. O GRG foi desenvolvido para lidar com problemas não-lineares que não podem ser resolvidos pelo método Simplex LP, que é o algoritmo padrão utilizado para problemas lineares.

Uma das principais vantagens do GRG é que ele é capaz de lidar com problemas não-lineares que possuem restrições não-lineares e funções objetivo não-lineares. Ele também é capaz de lidar com problemas que possuem restrições de igualdade e desigualdade. Além disso, o GRG é capaz de encontrar soluções ótimas para problemas que possuem múltiplos pontos de ótimo.

No entanto, o GRG também tem suas desvantagens. Ele pode ser mais lento do que o método Simplex LP para problemas lineares e pode ter dificuldade em encontrar soluções ótimas para problemas não-lineares que possuem restrições muito complexas. Além disso, o GRG não é capaz de lidar com problemas que possuem restrições de inteiro ou binário.

O Método Evolutionary Solver

Por fim, o Método Evolutionary Solver é utilizado quando a célula da função objetivo ou as células de restrições são determinados a partir de funções cujos resultados variam de forma abrupta. Isto acontece geralmente quando nas células da função objetivo ou nas células das restrições são usadas fórmulas do tipo condicional (IF, SUMIF, etc.) tal como acontece com se utilizam fundação contendo ABS, MIN ou MAX para calcular o valor da célula objetivo ou de restrições, nestes casos o declive da função objetivo varia radicalmente para pequenas variações das variáveis de decisão, assim como o resultado. Para resolver problemas deste tipo utiliza-se o algoritmo Evolutionary Solver.

O método Evolutionary Solver é um algoritmo de resolução de problemas utilizado no Solver do Microsoft Excel para encontrar soluções ótimas para problemas de programação não-linear. Ele é utilizado quando a célula objetivo e as células de restrições são determinadas a partir de funções cujos resultados variam de forma abrupta.

O Evolutionary Solver é baseado na técnica de algoritmos evolutivos, que é uma técnica de otimização inspirada na evolução biológica. Ele é projetado para lidar com problemas não-lineares e não-diferenciáveis que são difíceis de serem resolvidos por outros algoritmos. A técnica de algoritmos evolutivos é baseada em princípios da evolução biológica, como seleção natural, reprodução e mutação.

Uma das principais vantagens do Evolutionary Solver é que ele é capaz de lidar com problemas não-lineares e não-diferenciáveis que são difíceis de serem resolvidos por outros algoritmos. Ele também é capaz de encontrar soluções ótimas para problemas que possuem múltiplos pontos de ótimo. Além disso, o Evolutionary Solver é capaz de lidar com problemas que possuem restrições de inteiro ou binário.

No entanto, o Evolutionary Solver também tem suas desvantagens. Ele pode ser mais lento do que outros algoritmos para problemas não-lineares e não-diferenciáveis e pode ter dificuldade em encontrar soluções ótimas para problemas que possuem restrições muito complexas. Além disso, o Evolutionary Solver não é capaz de lidar bem com problemas que possuem restrições de igualdade e desigualdade.

Para a análise de problemas mais complexos, depois de selecionado o método de resolução, podem definir-se algumas opções a partir do botão “Options” de modo a facilitar a sua resolução.

O Definições Comuns aos Três Modelos

Ao clicar no botão é exibida uma nova caixa de diálogo com três separadores:

No primeiro separador, podem definir-se opções comuns aos três algoritmos de resolução. Estão disponíveis as seguintes opções:

• Constraint Precision: aqui define-se qual o nível de tolerância a aplicar às restrições. Por exemplo, com um nível de precisão definido como 0,00001 a restrição C2>=1 poderá aceitar como válido um valor de C2 igual a 0,99999.
• Use Automatic Scaling: quando esta opção está ativada o Solver terá mais facilidade em resolver problemas em que a escala da variável objetivo e restrições são muito diferentes. Por exemplo, num problema em que o resultado da função objetivo é medido em quilómetros e as restrições variam na ordem dos milimetros, ativar esta opção levará ao redimensionamento interno das variáveis de modo a torna-las mais proximas, o que irá facilitar os cálculos internos. E a melhores soluções, na maior parte dos casos.
• Show Iteration Results: com esta opção ativa, os resultados são apresentados a cada iteração realizada pelo Solver. No canto inferior esquerdo da janela da folha de cálculo aparece o número da interação e o resultado da célula objetivo. Para aceitar, clicar em “Stop” e para continuar para a próxima iteração, clicar em “Continue”.
• Ignore Integer Constraints: com esta opção ativa, o Solver irá ignorar as restrições com números inteiros, binários ou todos diferentes, sendo possível definir a percentagem de tolerância (que por defeito é igual a 1%) do desvio em relação à solução ótima. Naturalmente, quanto maior for o desvio aceitável em relação à solução ótima, mais rápida será a resolução do problema. Em alguns casos, permitir um desvio de 1% representa uma poupança significativa no tempo de resolução.

Definições do Modelo GRG Nonlinear

No segundo separador, podem ser definidas as opções para o método de resolução GRG:

• Convergence: define o valor máximo de variação do resultado das últimas cinco iterações antes de o Solver terminar a resolução do problema. Quanto mais baixo for este valor maior será a precisão da solução e consequentemente maior será o tempo que levará até encontrar a uma solução.
• Derivatives: define o método de diferenciação utilizado no algoritmo. A opção “Forward” é a escolha por defeito, no entanto, a opção “Central” é a mais precisa embora seja necessário realizar o dobro dos cálculos a cada iteração.
• Multistart: com esta opção ativada, o método GRG Nonlinear é executado várias vezes testando diferentes valores iniciais para as variáveis de decisão. Esta opção permite chegar a resultados mais precisos, no entanto, requer mais tempo de processamento.
  1. Population Size: define-se o número de pontos de partida das variáveis de decisão. Pode variar entre 10 e 200,
  2. Random Seed: indica-se um número aleatório positivo e inteiro que define o gerador de pontos de partida das variáveis de decisão. Se nada for indicado o Solver utilizará pontos de partida diferentes a cada resolução,
  3. Require bounds on variables: ao selecionar está opção as variáveis de decisão serão restringidas entre um limite inferior e um limite superior. Neste caso, o método de resolução será mais eficaz.

Definições do Modelo Evolutionary Solver

Por fim, no terceiro separador permite definir diversas opções para o método Evolutionary:

• Convergence: define o valor máximo de variação percentual permitida,a cada iteração, para os valores da célula objetivo antes de terminar a resolução do problema. Tal como no método GRG, quanto mais baixo for este valor mais precisa será a solução encontrada e mais tempo será necessário para a convergência.
• Mutation Rate: define o valor da frequência relativa que qualquer uma das células das variáveis de decisão pode variar para gerar uma nova iteração. Este valor será definido entre 0 e 1 e quanto maior, maior será a probabilidade de encontrar uma solução ótima, do mesmo modo que mais lento será o processo de resolução do problema.
• Population Size: permite definir um valor entre 10 e 200 que determina o número de valores diferentes das variáveis de decisão usados a qualquer momento durante a resolução do problema,
• Random Seed: define- se um valor positivo e inteiro que define o valor dos pontos de partida das variáveis de decisão. Quando deixado em branco será usado um número aleatório diferente cada vez que se executa o Solver.
• Maximum Time without improvement: é o tempo máximo de execução permitido, medido em segundos, sem que a solução do problema apresente melhorias.
• Require Bounds on Variables: se está opção estiver ativada, no modelo as variáveis de decisão deverão estar restringidas por limites inferiores e limites superiores.

Além de escolher o algoritmo de resolução de problemas adequado, é importante definir algumas opções a partir do botão "Options" para facilitar a resolução do problema. Por exemplo, a opção Constraint Precision define o nível de tolerância aplicado às restrições, enquanto a opção Use Automatic Scaling facilita a resolução de problemas em que a escala da variável objetivo e restrições são muito diferentes. A opção Show Iteration Results permite ver os resultados de cada iteração realizada pelo Solver.

Em geral, é importante lembrar que escolher o algoritmo de resolução de problemas adequado e definir as opções corretas é apenas uma parte da solução para um problema de programação linear. A modelagem do problema, a análise de sensibilidade e o preço sombra também são importantes para garantir que a solução encontrada seja viável e aplicável para a situação real.

Conclusão

Em resumo, os algoritmos de resolução de problemas disponíveis no Solver do Excel incluem o Método Simplex LP, o Método GRG Nonlinear e o Método Evolutionary Solver. 

Cada um desses algoritmos tem suas próprias vantagens e desvantagens e é importante escolher o algoritmo adequado para o problema específico. Além disso, é importante lembrar de definir as opções corretas e considerar a modelagem do problema, a análise de sensibilidade e o preço sombra para garantir que a solução encontrada seja viável e aplicável.

Todos os dias centenas de pessoas pesquisam no Google sobre optimização e como usar o Excel Solver. 

E você, achou este artigo útil? foi fácil seguir o passo a passo? Então, por favor, compartilhe esta informação nas redes sociais abaixo para ajudar mais pessoas a encontrar uma resposta para aquilo que procuram sobre optimização com o Solver no Excel.