Modelling the shortest path problem by using linear programming approach. a case of Nkawie fire station

Thumbnail Image
JUNE, 2015.
Journal Title
Journal ISSN
Volume Title
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.
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.