The Master's thesis consists of a theoretical research part and a practical part. In the first part, we address two very important problems that deal with the optimization of flows in networks. These are the minimum cost flow problem and its special, slightly simplified form, the so-called the transshipment problem. In the latter, we have one less constraint for determining the edge flow, while in both cases we aim to optimise the cost of transferring goods between nodes in the network. The solution for each of the two problems can be obtained using a network simplex algorithm. To understand these two optimization problems and how the algorithm itself works, we focus on mathematical concepts such as s-flow, spanning tree solution, feasible and strongly feasible pair of spanning tree T and root r, potential and reduced costs. We formulate and prove some propositions and theorems. One of the most important theorems provides a sufficient and necessary condition for when an s-flow associated with the spanning tree structure (T,r) is optimal. This result also plays a key part in the network simplex algorithm, the steps of which are given in this thesis. We then present each step of the algorithm in detail and prove that the algorithm works correctly. To this end, we ensure that we obtain an s-flow after each iteration of the algorithm, that after each iteration the price of the s-flow is reduced or unchanged, that after each iteration the new pair (T,r) is strongly feasible, that the algorithm always stops after a finite number of iterations, and that the s-flow associated with the last spanning tree structure (T,r) is indeed the optimal solution of the given transshipment problem.
The practical part of the Master's thesis comprises the development of an interactive application in the Unity environment. The application demonstrates each step of the network simplex algorithm and works with any network entered by the user and at the end provides an optimal solution for the transshipment problem. We decided to develop the application because the network simplex algorithm is quite complex and can therefore be difficult to understand. We incorporated the ideas of constructivist learning theory into the learning material we created, and gave the user the opportunity to actively engage in the process, as the application requires the user to complete certain tasks related to the execution of the algorithm in certain steps. By creating such an application, we would like to contribute to a better understanding of this algorithm for solving the transshipment problem, primarily for the students of the 4th year of the Faculty of Education, University of Ljubljana, first-cycle study programme Two-subject Teacher, major: Mathematics - Computer Science. They learn the above-mentioned subject content in the course Combinatorial Optimization. At the same time, we have provided the teachers of this course with a teaching tool that can help them in presenting this subject to their students. The application is available free of charge to anyone interested in this topic. In this master’s thesis, we present the origin of the idea of creating such an app and its purpose. We introduce the Unity programming environment and explain why we decided to create the application in this environment. It allows us to realise visual and interactive elements quite easily compared to some other tools. We also visualise the steps in the application using flowcharts and describe the appearance of the application's user interface. We then present the overall implementation of the application in detail both from the user’s point of view and from a technical or programming point of view.
|
