Η διάρθρωση της παρούσας διπλωματικής εργασίας είναι η παρακάτω.
Στο πρώτο κεφάλαιο γίνεται μια γενική παρουσίαση της Επιχειρησιακής Έρευνας και του Γραμμικού Προγραμματισμού. Ο Γραμμικός Προγραμματισμός έχει ως στόχο τη βελτιστοποίηση της απόδοσης ενός συστήματος. Η λήψη απόφασης για ένα πρόβλημα Γραμμικού Προγραμματισμού βασίζεται στην επιλογή της βέλτιστης λύσης. Το μαθηματικό μοντέλο ενός τέτοιου προβλήματος αποτελείται από μεταβλητές απόφασης, την αντικειμενική συνάρτηση και περιορισμούς.
Στο δεύτερο κεφάλαιο παρουσιάζεται η μέθοδος 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.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/7803 |
| Date | 10 June 2014 |
| Creators | Αγουρίδη, Γεωργία |
| Contributors | Τσάντας, Νικόλαος, Agouridi, Georgia, Γράψα, Θεοδούλα, Κωτσιαντής, Σωτήριος |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
| Relation | Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0149 seconds