tailieunhanh - A parametric visualization software for the assignment problem

In this paper we present a parametric visualization software used to assist the teaching of the Network Primal Simplex Algorithm for the assignment problem (AP). The assignment problem is a special case of the balanced transportation problem. The main functions of the algorithm and design techniques are also presented. Through this process, we aim to underline the importance and necessity of using such educational methods in order to improve the teaching of Computer Algorithms. | Yugoslav Journal of Operations Research 15 (2005), Number 1, 147-158 A PARAMETRIC VISUALIZATION SOFTWARE FOR THE ASSIGNMENT PROBLEM Charalampos PAPAMANTHOU, Konstantinos PAPARRIZOS, Nikolaos SAMARAS Department of Applied Informatics University of Macedonia, Thessaloniki, Greece it0067@, paparriz@, samaras@ Received: September 2003 / Accepted: September 2004 Abstract: In this paper we present a parametric visualization software used to assist the teaching of the Network Primal Simplex Algorithm for the assignment problem (AP). The assignment problem is a special case of the balanced transportation problem. The main functions of the algorithm and design techniques are also presented. Through this process, we aim to underline the importance and necessity of using such educational methods in order to improve the teaching of Computer Algorithms. Keywords: Assignment problem, network simplex algorithm, visualization, computer algorithms. 1. INTRODUCTION The AP is a complex combinatorial optimization problem. It is one of the most classic in the field of Computer Science and Operations Research. A lot of efficient algorithms have been and are constantly being developed for its solution [1], [2], [3], [4], [6], [9], [10], [11], [16], [19], [20] and [23]. The problem owes its name to the classic application of assigning a number of jobs to an equal number of persons at a minimal total cost, given the costs of the assignment of every job to every person. It is evident, that even if every person is capable of employing every job, the solution of the problem must assign only one job to each person. From a first point of view it looks really simple; one must just find all the possible combinations between the jobs and the persons, compare the respective costs, and choose the minimal one. However, taking into account that there are n! possible permutations of n discrete objects, the approach just mentioned is computationally prohibitive, considering that the