Problemas de otimização com grafos - resolução com o Solver do Excel

Jorge Paulo Jesus Santos

Os problemas de otimização com grafos surgem em variadíssimas situações, desde aplicações mais diretas como a determinação do percurso mais rápido quando se pretende ir de um local para outro (GPS), ou em aplicações não tão diretas como a afetação de serviços a zonas geográficas ou a funcionários e árvores de decisão.

Muitos problemas envolvendo grafos podem ser modelados em termos de otimização linear. Nesta sessão irão ser analisados alguns dos problemas mais simples que normalmente são tratados quando se aborda pela primeira vez esta temática (problema de transportes, problema do caminho mais curto e problema do fluxo máximo). A abordagem de cada problema segue a seguinte sequência:

• apresentação de um exemplo; • modelação em otimização linear; • organização dos dados numa folha cálculo do Microsoft Office Excel; • resolução com o suplemento Solver; • representação e interpretação da solução.