PHPSimplex

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:

 

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

• Xij: ação de deslocar-se da cidade i à cidade j (0 indica que não há deslocamento e 1 que há deslocamento)

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):

• Balanço de caminhos da cidade A: XAB + XAC = 1
• Balanço de caminhos da cidade B: XBD + XBE - XAB - XDB - XEB = 0
• Balanço de caminhos da cidade C: XCD + XCF - XAC - XDC - XFC = 0
• Balanço de caminhos da cidade D: XDB + XDC + XDE - XBD - XCD - XED = 0
• Balanço de caminhos da cidade E: XEB + XED + XEG - XBE - XDE = 0
• Balanço de caminhos da cidade F: XFC + XFG - XCF = 0
• Balanço de caminhos da cidade G: - XEG - XFG = -1

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:

• Xij ≥ 0
• Xij são booleanos

Determinar a função objetivo:

• Minimizar Z = 12·XAB + 4·XAC + 5·XBD + 3·XBE + 2·XCD + 10·XCF + 5·XDB + 2·XDC + 10·XDE + 3·XEB + 10·XED + 2·XEG + 10·XFC + 4·XFG

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.