Modelling the shortest path problem by using linear programming approach. a case of Nkawie fire station
Loading...
Date
JUNE, 2015.
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
There has been a number of fire outbreak cases recorded in the Atwima
Nwabiagya District that has brought about loss of lives of inhabitants and loss
of properties. Some routes within the district can be reconstructed into bitumen
roads so that fire attackers can traverse through the district in order to prevent
fire incidents. The main objective in this study is finding the minimum travel
distances and shortest paths from the Nkawie Fire Station to all other towns in
the district of Atwima Nwabiagya district in the Ashanti Region of Ghana.
Shortest path algorithms of various variants have been discussed with examples
in this study as well as review of abstracts of other related books and articles.
The linear programming approach was the method used. The primal and dual
models have been explained and dual model in which we maximize the source
node minus the destination node subject to an inequality constraints, was the
appropriate model used to write the constraints of the problem.
It was found out that as a destination is used in the objective function, the dual
algorithm proceeds to obtaining minimum distances to every other destination.
The Lindo 6.1 software was used to solve the maximization problem and the
results are found in the appendices of this study. There was an optimal distances
from Nkawie (NK) to all the towns in the district. The distance from Nkawie (NK)
to Mfensi (MF) was found to be 14.3km, that of Akropong(AK) was 21.1km etc.
Description
A thesis submitted to the Department of Mathematics,
Kwame Nkrumah University of Science and Technology in
partial fulfillment of the requirement for the Degree
of Master of Science in Industrial Mathematics.