Η διάρθρωση της παρούσας διπλωματικής εργασίας είναι η παρακάτω. Στο πρώτο κεφάλαιο γίνεται μια γενική παρουσίαση της Επιχειρησιακής Έρευνας και του Γραμμικού Προγραμματισμού. Ο Γραμμικός Προγραμματισμός έχει ως στόχο τη βελτιστοποίηση της απόδοσης ενός συστήματος. Η λήψη απόφασης για ένα πρόβλημα Γραμμικού Προγραμματισμού βασίζεται στην επιλογή της βέλτιστης λύσης. Το μαθηματικό μοντέλο ενός τέτοιου προβλήματος αποτελείται από μεταβλητές απόφασης, την αντικειμενική συνάρτηση και περιορισμούς. Στο δεύτερο κεφάλαιο παρουσιάζεται η μέθοδος Simplex, που αναπτύχθηκε από τον G. B. Dantzig το 1947. Η μέθοδος Simplex αποτελεί ίσως την πιο αποδοτική και χρησιμοποιημένη μέθοδο για επίλυση προβλημάτων Γραμμικού Προγραμματισμού. Η μέθοδος Simplex είναι μια μέθοδος δυο φάσεων, όπου κάθε φάση χρησιμοποιεί τον αλγόριθμο Simplex. Στην πρώτη φάση στόχος είναι ο προσδιορισμός μιας εφικτής λύσης. Στη δεύτερη φάση στόχος είναι ο εντοπισμός της βέλτιστης λύσης, ξεκινώντας από την εφικτή λύση που έχει βρεθεί στην πρώτη φάση. Παράλληλα περιγράφεται η πινακοειδής μορφή της μεθόδου Simplex (tableau format). Στο τρίτο κεφάλαιο γίνεται παρουσίαση της μεθόδου δικτυωτής Simplex. Πρόκειται για μια μέθοδο που αποτελεί εξειδίκευση του αλγορίθμου Simplex για δίκτυα. Παρουσιάζονται διάφορες βασικές δομές δικτύων. Επιπλέον, αναλύεται το πρόβλημα ελάχιστου κόστους ροής σε ένα δίκτυο. Ακόμα γίνεται αναφορά σε προβλήματα γραμμικού προγραμματισμού που έχουν δομή δικτύου και μπορούν με τη μέθοδο δικτυωτής Simplex να επιλυθούν με πολύ πιο αποδοτικό τρόπο, παρόλο που μπορούν να λυθούν και με το βασικό αλγόριθμο Simplex. Στο τέταρτο κεφάλαιο παρουσιάζονται οι σημαντικότερες εφαρμογές του προβλήματος ελάχιστου κόστους ροής δικτύου. Οι ειδικές περιπτώσεις του προβλήματος ελάχιστου κόστους της ροής δικτύου είναι το πρόβλημα μεταφοράς, το πρόβλημα εκχώρησης, το πρόβλημα μέγιστης ροής και το πρόβλημα της συντομότερης διαδρομής. / The structure of this thesis is the following. In the first chapter Operational Research and Linear Programming are generally presented. Linear Programming aims to optimize the efficiency of a system. Decision making for a problem of Linear Programming is relevant to the choice of the optimal solution. The mathematical model of such a problem consists of decision variables, an objective function and constraints. In the second chapter Simplex method is presented, which was developed by G. B. Dantzig in 1947. The Simplex method is possibly the most efficient and used method for solving Linear Programming problems. The Simplex method is a two phase method, each phase of which uses the Simplex Algorithm. In the first phase, the goal is to determine a feasible solution. In the second phase, the goal is to determine an optimal solution, starting from a feasible solution that has been found in the first phase. Moreover the Simplex method is described in a tabular format (Simplex tableaux). In the third chapter Network Simplex Method is presented. This method is a specialization of the Simplex algorithm for networks. Various network structures are presented. Moreover, the minimum cost network flow problem is analyzed. Furthermore linear programming problems that have network structure can be solved more efficiently using network Simplex method, even though they can be solve using standard Simplex algorithm. In the fourth chapter the most significant applications of the minimum cost network flow problem are presented. These special cases of the minimum cost network flow problem are the transportation problem, the assignment problem, the maximal flow problem and the shortest path problem.

[pt] Este trabalho busca desenvolver o método Simplex para Redes na solução de problemas de Fluxo de Custo Mínimo. Este método consiste em uma adaptação do método Simplex primal em que são exploradas as características específicas da rede subjacente ao problema ao se buscar a solução ótima em um número finito de árvores geradoras. A árvore geradora ótima será obtida iterativamente através de sucessivas melhorias na estrutura de cada árvore formada. A maior eficiência do Simplex para Redes se dá tanto no menor número de iterações necessárias para se atingir o ótimo, quanto na maior velocidade destas iterações, trata-se, portanto, de um método bastante poderoso na resolução de problemas de Fluxo de Custo Mínimo. Serão, também, abordados aspectos práticos da implementação do algoritmo além da aplicação deste algoritmo implementado em VBA (Visual Basic for Applications) em um problema prático a título de exemplificação. / [en] The current work intends to develop a Network Simplex Method for solving Minimum Cost Flow problems. Such method consists of a primal Simplex Method adaptation in which specific characteristics of the network underlying the problem are investigated by searching for the optimal solution within a finite number of spanning trees. The optimal spanning tree is iteratively obtained through successive structure improvements in each formed tree. The higher efficiency of Network Simplex lies both in fewer iterations necessary to achieve the optimum and in the higher speed of these iterations. Therefore, it is a powerful method for solving Minimum Cost Flow Problems. Practical aspects of implementing the algorithm will be discussed, as well as the algorithm´s implementation in VBA (Visual Basic for Applications) through a practical instance.

<p>Traffic planning in a modern congested society is an important and time consuming procedure. Finding fast algorithms for solving traffic problems is therefore of great interest for traffic planners allover the world. </p><p>This thesis concerns solving the fixed demand traffic assignment problem (TAP) on a number of different transportation test networks. TAP is solved using the Frank-Wolfe algorithm and the shortest path problems that arise as subproblems to the Frank-Wolfe algorithm are solved using the network simplex algorithm. We evaluate how a number of existing pricing strategies to the network simplex algorithm performs with TAP. We also construct a new efficient pricing strategy, the Bucket Pricing Strategy, inspired by the heap implementation of Dijkstra's method for shortest path problems. This pricing strategy is, together with the actual use of the network simplex algorithm, the main result of the thesis and the pricing strategy is designed to take advantage of the special structure of TAP. In addition to performing tests on the conventional Frank-Wolfe algorithm, we also test how the different pricing strategies perform on Frank-Wolfe algorithms using conjugate and bi-conjugate search directions. </p><p>These test results show that the updating shortest path calculations obtained by using the network simplex outperforms the non-updating Frank-Wolfe algorithms. Comparisons with Bar-Gera's OBA show that our implementation, especially together with the bucket pricing strategy, also outperforms this algorithm for relative gaps down to 10E-6.</p>

Traffic planning in a modern congested society is an important and time consuming procedure. Finding fast algorithms for solving traffic problems is therefore of great interest for traffic planners allover the world. This thesis concerns solving the fixed demand traffic assignment problem (TAP) on a number of different transportation test networks. TAP is solved using the Frank-Wolfe algorithm and the shortest path problems that arise as subproblems to the Frank-Wolfe algorithm are solved using the network simplex algorithm. We evaluate how a number of existing pricing strategies to the network simplex algorithm performs with TAP. We also construct a new efficient pricing strategy, the Bucket Pricing Strategy, inspired by the heap implementation of Dijkstra's method for shortest path problems. This pricing strategy is, together with the actual use of the network simplex algorithm, the main result of the thesis and the pricing strategy is designed to take advantage of the special structure of TAP. In addition to performing tests on the conventional Frank-Wolfe algorithm, we also test how the different pricing strategies perform on Frank-Wolfe algorithms using conjugate and bi-conjugate search directions. These test results show that the updating shortest path calculations obtained by using the network simplex outperforms the non-updating Frank-Wolfe algorithms. Comparisons with Bar-Gera's OBA show that our implementation, especially together with the bucket pricing strategy, also outperforms this algorithm for relative gaps down to 10E-6.