Δύο σημαντικοί σταθμοί στην ιστορία του γραμμικού προγραμματισμού : 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