PHPSimplex

Otimizar os recursos com Programação Linear



Caminho mínimo

Os problemas conhecidos como problemas do caminho mínimo ou do caminho mais curto, como sugere o nome, procuram encontrar a rota mínima ou o caminho mais curto entre dois pontos. Este mínimo pode ser a distância entre os pontos de origem e de destino, ou ainda, o tempo decorrido para se deslocar de um ponto a outro. É muito utilizado em problemas de redes de comunicações.

Esses problemas podem ser resolvidos por meio do método Simplex, no entanto, existem outros métodos mais eficientes, como por exemplo, o algoritmo de Dijkstra ou o de Bellman-Ford.

Exemplo

Uma pessoa tem que deslocar-se diariamente da cidade A à cidade G. E, está estudando qual é o trajeto mais curto, usando um mapa de estradas. As estradas e suas distâncias são representadas na figura seguinte:

Problema do caminho mínimo

 

Determinar as variáveis de decisão e expressá-las algebricamente. Neste caso:

Determinar as restrições e expressá-las como equações ou inequações dependentes das variáveis de decisão. Tais restrições são deduzidas do balanço entre os possíveis caminhos que partem de cada cidade e os caminhos que chegam até ela (ignorando as estradas que nos retornam ao ponto de partida e àquelas que vêm do destino):

Expressar todas as condições estabelecidas implicitamente pela natureza das variáveis: que não possam ser negativas, que sejam inteiras, que somente possam ter determinados valores, ... Neste caso, as restrições são, que as variáveis devem ser booleanas (0 não se deve tomar o caminho, 1 utilizar o caminho), e, portanto, não podem ser negativas:

Determinar a função objetivo:

Fazer uma mudança de variáveis com a seguinte correspondência:

XAB XAC XBE XBD XDB XEB XCD XCF XFC XDC XDE XED XEG XFG
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13 X14

Resolver com PHPSimplex.

Copyright ©2006-2017 PHPSimplex. Todos os direitos reservados. Termos e condições.
Siga-nos no Twitter
X

PHPSimplex
Versão 0.81

Copyright ©2006-2017. Todos os direitos reservados.

Desenvolvido por:
Daniel Izquierdo Granja
Juan José Ruiz Ruiz

Tradução para o Inglês por:
Luciano Miguel Tobaria

Tradução para o Francês por:
Ester Rute Ruiz

Tradução para o Português por:
Rosane Bujes