The problems known like minimal road's problem or shorter road problem, treat as its name shows to find the minimal or shorter route among two points. This minimum can be the distance among origin and destination points or else the elapsed time to go the route between that two points. It's usually used in communications networks problems.
This kind of problems can be solved by the Simplex Method, however exist another more efficient methods for example Dijkstra algorithm or other case can be Bellman-Ford algorithm.
A person must go every day from village A to village G. He is studying with a roads map wich way is the shortest. The roads and its distances are shows in the following figure:
Determining decision variables and expressing them algebraically. In this case:
Determining the restrictions and expressing them as equations or inequalities in function of the decision variables. Such restrictions can be obteined from the balance among the possible ways that takes from each village and that wich arrive it (obviating the roads that take back to the starting point and the ones that come from the destination point):
Expressing all implicit conditions established by the origin of variables: negativeness, integer, only a few allowed values... . In this case, the restrictions are that the variables must be boolean (0 the way isn't taken, 1 yes), and so, can't be negatives:
Determining objective function:
Perform a change of variable with the following correspondence:
Copyright ©2006-2016. All rights reserved.
Daniel Izquierdo Granja
Juan José Ruiz Ruiz
English translation by:
Luciano Miguel Tobaria
French translation by:
Ester Rute Ruiz