Skip to main content
18 julho 2017
Follow Us

Solver: Qual o método de resolução de problemas a escolher?

Agora, teremos de escolher um método de resolução do problema a partir da caixa “Select a Solving Method”, além da indicação de objetivos, variáveis e restrições.

Nem sempre é fácil compreender o que faz cada um dos três métodos disponíveis (existem três algoritmos apenas a partir da versão 2010 do Excel) e como se chega a uma solução.

Em geral, escolhemos:

  • O método Simplex LP, se o objetivo e restrições são funções lineares das variáveis de decisão, ou seja, quando o declive é constante. Este é o algoritmo a usar para problemas de otimização linear;
  • O método GRG Nonlinear, se o nosso objetivo e restrições resultam de funções não lineares das variáveis de decisão. Usamos este método quando a célula objetivo e as células de restrições são calculadas a partir de uma operação matemática que envolve potências, cálculo exponencial ou trigonométrico sobre as variáveis de decisão;
  • O método Evolutionary Solver, se a célula objetivo e as células de restrições são determinados a partir de funções cujos resultados variam de forma abrupta.

Por exemplo, quando usamos fórmulas do tipo condicional (IF, SUMIF, etc.) assim como ABS, MIN ou MAX para calcular o valor da célula objetivo ou de restrições, o declive varia radicalmente a pequenas variações das variáveis de decisão, assim como o resultado. Para este tipo de problemas recorrermos ao algoritmo Evolutionary Solver que ilustraremos mais à frente.

Quando o problema em causa é complexo, podemos definir algumas opções a partir do botão “Options” que poderão facilitar um pouco a sua resolução.

Ao clicar no botão é exibida a seguinte caixa:

BusinessModelling3

No primeiro separador, podemos definir opções para todos os algoritmos. Vejamos de que opções dispomos:

  • Constraint Precision: nesta caixa define-se o nível de tolerância a aplicar às restrições. Por exemplo, a restrição B2>=1 aceitaria um valor de B2 igual a 0,999999 com o nível de precisão definido para 0,000001
  • Use Automatic Scaling: quando esta caixa de verificação está marcada, o Solver terá mais facilidade em resolver problemas em que a escala da variável objetivo e restrições são muito díspares. Por exemplo, num problema em que a taxa de inflação é medida percentualmente e o Valor Atualizado Líquido é medido em milhões de euros, marcar esta opção levará ao redimensionamento interno das variáveis no sentido da sua aproximação, o que facilitará os cálculos internos. Tal conduz a melhores soluções, na maior parte dos casos.
  • Show Iteration Results: marcada esta caixa de verificação, uma caixa será apresentada a cada iteração realizada pelo Solver. No canto inferior esquerdo poderemos ver o número da interação e o resultado da célula objetivo. Para aceitar, clicamos em “Stop” e para continuar para a próxima iteração, clicamos em “Continue”. Também é possível guardar cenários que poderão ser posteriormente analisados no Gestor de Cenários do Excel.
  • Ignore Integer Constraints: com esta opção selecionada, o Solver ignorará as restrições com números inteiros, binários ou todos diferentes. Na caixa ao lado é possível definir a percentagem de tolerância (que por defeito é igual a 1%) do desvio em relação à solução ótima. Quanto maior o desvio tolerado em relação à solução ótima, mais rápida será a resolução do problema. Por vezes, aceitar um desvio de 1% representa uma poupança significativa de tempo de resolução.
  • Nas caixas seguintes é possível determinar limites à resolução de problemas em função do tempo, medido em segundos, do número de iterações e do número máximo de subproblemas e de soluções viáveis (aplicável apenas a problemas com restrições com números inteiros, binários e todos diferentes assim como ao algoritmo Evolutionary).

No segundo separador, definimos as opções para o método GRG Nonlinear:

BusinessModelling4

  • Convergence: define o valor máximo de variação 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 o tempo até chegar a uma solução,
  • Derivatives: escolhe o método de diferenciação. A opção “Forward” é a escolha por defeito mas a opção “Central” é a mais precisa embora requeira o dobro dos cálculos a cada iteração,
  • Multistart: com esta caixa de verificação marcada, o método GRG Nonlinear é executado repetidas vezes testando diferentes valores iniciais para as variáveis de decisão. Esta opção permite alcançar resultados mais precisos mas consome mais tempo de processamento.
    1. Population Size: determina o número de pontos de partida das variáveis de decisão. Pode variar entre 10 e 200,
    2. Random Seed: é um número aleatório positivo e inteiro que define o gerador de pontos de partida das variáveis de decisão. Se deixado vazio, o Solver irá utilizar pontos de partida diferentes a cada resolução,
    3. Require bounds on variables: se esta opção estiver selecionada, as variáveis de decisão terão que ser restringidas entre um limite inferior e superior. O método de resolução será mais eficaz neste caso.

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

BusinessModelling5

  • Convergence: define o valor máximo de variação percentual permitida para os valores da célula objetivo antes de terminar a resolução do problema. Tal como no método anterior, quanto mais baixo for este valor mais precisa será a solução e mais tempo será necessário para a encontrar,
  • Mutation Rate: é o valor da frequência relativa que alguma célula das variáveis de decisão pode variar para criar uma nova iteração. Este valor terá de se situar entre 0 e 1 e quanto maior, maior a probabilidade de encontrar uma solução ótima mas simultaneamente mais lento será o processo de resolução do problema,
  • Population Size: é 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: é um valor positivo e inteiro que define o valor de pontos de partida das variáveis de decisão. Se deixado em branco, será usado um número aleatório diferente de cada vez que se executa o Solver,
  • Maximum Time without improvement: é o tempo máximo de execução, medido em segundos, que deve ser mantido sem que a solução melhore,
  • Require Bounds on Variables: se esta caixa de verificação estiver marcada, as variáveis de decisão deverão estar restringidas por limites inferiores e superiores.

Pronto para a ação? No próximo artigo, veremos como resolver um problema de otimização da gestão de inventários.

Ficheiros em anexo


Assine a nossa newsletter e receba o nosso conteúdo diretamente no seu email