Student's night out problem solved with Excel's Solver
Rigid model
The cells in green are to be changed by Solver.
The cells in yellow specify that each node can only have one path from it and one path to it. The first and the last nodes work a bit different. The first node cannot receive a path and the last node cannot have a path from it.
In this example it is convention that a path leading from a node gives that node a +1 while a path leading to a node gives that node a -1.
The nodes in between the first and last node have to equal 0.
The cells in blue indicate the constraint values of the cells in yellow.
The cells in yellow specify that each node can only have one path from it and one path to it. The first and the last nodes work a bit different. The first node cannot receive a path and the last node cannot have a path from it.
In this example it is convention that a path leading from a node gives that node a +1 while a path leading to a node gives that node a -1.
The nodes in between the first and last node have to equal 0.
The cells in blue indicate the constraint values of the cells in yellow.
transhipment_problem.xlsx | |
File Size: | 13 kb |
File Type: | xlsx |
flexible model
Objective function and coefficients
The path chosen to be taken is indicated with a 1 whereas the path that will not be taken is indicated with a 0.
This indication with a 1 or 0 will be that path's coefficient.
The objective function wants to minimize the distance between the Engineering building and Springboks by choosing each path's coefficient.
The total distance will be calculated by multiplying each path's coefficient with that paths distance and then summing that specific answer of every path.
By choosing the distances of the paths that do not exist to be large relative to the distances of the paths that do exist the model is in effect ordering the Solver to skip that path.
The constraints
Each node can only have one path to it and one path from it.
The horizontal constraints will be the "from" constraint and the vertical constraints will be the "to" constraints.
Forcing the sum of the "from" constraints to be equal to 1 will force the solver to choose only one path from each node.
Forcing the sum of the "to" constraints to be equal to 1 will force the solver to choose only one path to each node.
The path chosen to be taken is indicated with a 1 whereas the path that will not be taken is indicated with a 0.
This indication with a 1 or 0 will be that path's coefficient.
The objective function wants to minimize the distance between the Engineering building and Springboks by choosing each path's coefficient.
The total distance will be calculated by multiplying each path's coefficient with that paths distance and then summing that specific answer of every path.
By choosing the distances of the paths that do not exist to be large relative to the distances of the paths that do exist the model is in effect ordering the Solver to skip that path.
The constraints
Each node can only have one path to it and one path from it.
The horizontal constraints will be the "from" constraint and the vertical constraints will be the "to" constraints.
Forcing the sum of the "from" constraints to be equal to 1 will force the solver to choose only one path from each node.
Forcing the sum of the "to" constraints to be equal to 1 will force the solver to choose only one path to each node.
shortest_path_transportation.xlsx | |
File Size: | 19 kb |
File Type: | xlsx |