Δύο σημαντικοί σταθμοί στην ιστορία του γραμμικού προγραμματισμού : Simplex and Karmarkar’ s Method
Ο Γραμμικός Προγραμματισμός διαδραματίζει ένα σημαντικό ρόλο στη ζωή μας. Λόγω των επαναστατικών εξελίξεων τόσο στην τεχνολογία των υπολογιστών όσο και στους αλ- γόριθμους για τη γραμμική βελτιστοποίηση, προβλήματα που δεν μπορούσαν να λυθούν πριν από χρόνια, λόγω ενός απαιτούμενου υπολογιστικού...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2020
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/13797 |
| id |
nemertes-10889-13797 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-137972022-09-06T05:14:32Z Δύο σημαντικοί σταθμοί στην ιστορία του γραμμικού προγραμματισμού : Simplex and Karmarkar’ s Method - Χαϊδοπούλου, Νίκη Τσάντας, Νικόλαος Chaidopoulou, Niki Δημητρίου, Ιωάννης Μακρή, Ευφροσύνη Πολυπλοκότητα Simplex Κarmarkar Ο Γραμμικός Προγραμματισμός διαδραματίζει ένα σημαντικό ρόλο στη ζωή μας. Λόγω των επαναστατικών εξελίξεων τόσο στην τεχνολογία των υπολογιστών όσο και στους αλ- γόριθμους για τη γραμμική βελτιστοποίηση, προβλήματα που δεν μπορούσαν να λυθούν πριν από χρόνια, λόγω ενός απαιτούμενου υπολογιστικού χρόνου, για παράδειγμα ενός έτους, μπορούν τώρα να λυθούν μέσα σε λίγα λεπτά. Μέχρι το 1984, η μέθοδος επίλυσης προ- βλημάτων γραμμικής βελτιστοποίησης ήταν η μέθοδος Simplex. Η ανάπτυξη της μεθόδου Simplex από τον George Dantzig είναι μία από τις πιο δημοφιλείς και πιο σημαντικές με- θόδους για την εύρεση λύσης στα προβλήματα γραμμικού προγραμματισμού. Από την αρχική διατύπωση της το 1947, η μέθοδος αυτή συνεχώς βελτιώνεται. Η μέθοδος Simplex προχωρά από μια κορυφή της εφικτής περιοχής που ορίζεται από τους περιορισμούς του προβλήμα- τος σε μια γειτονική κορυφή. Οι Klee και Minty έδειξαν ότι, στη χειρότερη περίπτωση, η μέθοδος Simplex έχει εκθετική πολυπλοκότητα. Το ερώτημα που τίθεται είναι αν υπάρχει άλλος αλγόριθμος για το γραμμικό προγραμματισμό που έχει πολυωνυμική πολυπλοκότη- τα. Αυτή η ερώτηση απαντήθηκε από τον Karmarkar το 1984. Ο Karmarkar παρουσίασε έναν αλγόριθμο με πολυωνυμικό χρόνο γνωστός ως προβολικός αλγόριθμος για το γραμμικό προγραμματισμό. Ο αλγόριθμος του Karmarkar χρησιμοποιεί εσωτερικά σημεία της εφικτής περιοχής για να προσεγγίσει τη βέλτιστη λύση. Η παρούσα εργασία λοιπόν, μελετά τη μέθοδο Simplex και τη μέθοδο εσωτερικού σημείου του Karmarkar, τη κύρια ιδέα πίσω από τις μεθόδους και τη θεωρία που χρησιμοποιείται για την ανάπτυξη της κάθε μεθόδου. Στο τέλος, παρουσιάζεται ένα πρόβλημα γραμμικού προγραμματισμού και λύνεται αρχικά με τον αλγόριθμο του Karmarkar και στη συνέχεια με τη μέθοδο Simplex. Linear programming plays an important role in our lives. Due to revolutionary developments both in computer technology and algorithms for linear optimization, pro- blems that could not be solved years ago, due to a required computational time of one year, say, can now be solved within some minutes. Until 1984, the method of choice for solving linear optimization problems was the Simplex Method. George Dantzig’s develop- ment of the Simplex method is one of the most popular and most important methods of finding the solution to the linear programming problems. Since the initial formulation in 1947, this method has been constantly improved. The Simplex method proceeds from one vertex of the feasible region defined by the constraints of problem to a neighboring ver- tex. Klee and Minty showed that, in the worst case, the Simplex method has exponential complexity in the size of the problem. The question that then arises is whether there is another algorithm for linear programming that has polynomial complexity. This question was answered by Karmarkar in 1984. He produced a polynomial-time algorithm called the projective algorithm for linear programming that ran in much better time. Karmarkar’s algorithm uses interior points of the feasible region to approximate the optimal solution. Consequently, this master thesis was aim to study Simplex method and the interior point method (Karmarkar Method), the principle idea behind the methods and the theory that is used in the development of the methods. In the end, the Karmarkar’s algorithm is compared to the simplex method by showing a solution to a linear programming problem obtained by the both two method. 2020-08-29T05:16:04Z 2020-08-29T05:16:04Z 2020-02-18 Thesis http://hdl.handle.net/10889/13797 gr 6 application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Πολυπλοκότητα Simplex Κarmarkar |
| spellingShingle |
Πολυπλοκότητα Simplex Κarmarkar Χαϊδοπούλου, Νίκη Δύο σημαντικοί σταθμοί στην ιστορία του γραμμικού προγραμματισμού : Simplex and Karmarkar’ s Method |
| description |
Ο Γραμμικός Προγραμματισμός διαδραματίζει ένα σημαντικό ρόλο στη ζωή μας. Λόγω
των επαναστατικών εξελίξεων τόσο στην τεχνολογία των υπολογιστών όσο και στους αλ-
γόριθμους για τη γραμμική βελτιστοποίηση, προβλήματα που δεν μπορούσαν να λυθούν πριν
από χρόνια, λόγω ενός απαιτούμενου υπολογιστικού χρόνου, για παράδειγμα ενός έτους,
μπορούν τώρα να λυθούν μέσα σε λίγα λεπτά. Μέχρι το 1984, η μέθοδος επίλυσης προ-
βλημάτων γραμμικής βελτιστοποίησης ήταν η μέθοδος Simplex. Η ανάπτυξη της μεθόδου
Simplex από τον George Dantzig είναι μία από τις πιο δημοφιλείς και πιο σημαντικές με-
θόδους για την εύρεση λύσης στα προβλήματα γραμμικού προγραμματισμού. Από την αρχική
διατύπωση της το 1947, η μέθοδος αυτή συνεχώς βελτιώνεται. Η μέθοδος Simplex προχωρά
από μια κορυφή της εφικτής περιοχής που ορίζεται από τους περιορισμούς του προβλήμα-
τος σε μια γειτονική κορυφή. Οι Klee και Minty έδειξαν ότι, στη χειρότερη περίπτωση, η
μέθοδος Simplex έχει εκθετική πολυπλοκότητα. Το ερώτημα που τίθεται είναι αν υπάρχει
άλλος αλγόριθμος για το γραμμικό προγραμματισμό που έχει πολυωνυμική πολυπλοκότη-
τα. Αυτή η ερώτηση απαντήθηκε από τον Karmarkar το 1984. Ο Karmarkar παρουσίασε
έναν αλγόριθμο με πολυωνυμικό χρόνο γνωστός ως προβολικός αλγόριθμος για το γραμμικό
προγραμματισμό. Ο αλγόριθμος του Karmarkar χρησιμοποιεί εσωτερικά σημεία της εφικτής
περιοχής για να προσεγγίσει τη βέλτιστη λύση.
Η παρούσα εργασία λοιπόν, μελετά τη μέθοδο Simplex και τη μέθοδο εσωτερικού σημείου
του Karmarkar, τη κύρια ιδέα πίσω από τις μεθόδους και τη θεωρία που χρησιμοποιείται
για την ανάπτυξη της κάθε μεθόδου. Στο τέλος, παρουσιάζεται ένα πρόβλημα γραμμικού
προγραμματισμού και λύνεται αρχικά με τον αλγόριθμο του Karmarkar και στη συνέχεια με
τη μέθοδο Simplex. |
| author2 |
Τσάντας, Νικόλαος |
| author_facet |
Τσάντας, Νικόλαος Χαϊδοπούλου, Νίκη |
| format |
Thesis |
| author |
Χαϊδοπούλου, Νίκη |
| author_sort |
Χαϊδοπούλου, Νίκη |
| title |
Δύο σημαντικοί σταθμοί στην ιστορία του γραμμικού προγραμματισμού : Simplex and Karmarkar’ s Method |
| title_short |
Δύο σημαντικοί σταθμοί στην ιστορία του γραμμικού προγραμματισμού : Simplex and Karmarkar’ s Method |
| title_full |
Δύο σημαντικοί σταθμοί στην ιστορία του γραμμικού προγραμματισμού : Simplex and Karmarkar’ s Method |
| title_fullStr |
Δύο σημαντικοί σταθμοί στην ιστορία του γραμμικού προγραμματισμού : Simplex and Karmarkar’ s Method |
| title_full_unstemmed |
Δύο σημαντικοί σταθμοί στην ιστορία του γραμμικού προγραμματισμού : Simplex and Karmarkar’ s Method |
| title_sort |
δύο σημαντικοί σταθμοί στην ιστορία του γραμμικού προγραμματισμού : simplex and karmarkar’ s method |
| publishDate |
2020 |
| url |
http://hdl.handle.net/10889/13797 |
| work_keys_str_mv |
AT chaïdopoulounikē dyosēmantikoistathmoistēnistoriatougrammikouprogrammatismousimplexandkarmarkarsmethod |
| _version_ |
1799945006222409728 |
