Ανάλυση και υπολογιστική πολυπλοκότητα τεχνικών επίλυσης προβλημάτων γραμμικού προγραμματισμού

Το πρώτο κεφάλαιο περιλαμβάνει μια ιστορική αναδρομή σχετικά με τη γέννηση και την ανάπτυξη της Επιχειρησιακής Έρευνας και του Γραμμικού Προγραμματισμού. Επίσης παρουσιάζεται το χρονικό των μεγαλυτέρων ανακαλύψεων: ο αλγόριθμος Simplex (Dantzig-1949), ο ελλειψοειδής αλγόριθμος (Khachian-1979) και ο...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής
Κύριος συγγραφέας: Κατσίκης, Αναστάσιος
Άλλοι συγγραφείς: Τσάντας, Νικόλαος
Μορφή: Thesis
Γλώσσα:Greek
Έκδοση: 2010
Θέματα:
Διαθέσιμο Online:http://nemertes.lis.upatras.gr/jspui/handle/10889/2627
id nemertes-10889-2627
record_format dspace
spelling nemertes-10889-26272022-09-05T05:00:30Z Ανάλυση και υπολογιστική πολυπλοκότητα τεχνικών επίλυσης προβλημάτων γραμμικού προγραμματισμού Κατσίκης, Αναστάσιος Τσάντας, Νικόλαος Τσάντας, Νικόλαος Πιπερίγκου, Βιολέτα Αλεβίζος, Παναγιώτης Katsikis, Anastasios Επιχειρησιακή έρευνα Γραμμικός προγραμματισμός Σίμπλεξ Operational research Linear programming Simplex 519.72 Το πρώτο κεφάλαιο περιλαμβάνει μια ιστορική αναδρομή σχετικά με τη γέννηση και την ανάπτυξη της Επιχειρησιακής Έρευνας και του Γραμμικού Προγραμματισμού. Επίσης παρουσιάζεται το χρονικό των μεγαλυτέρων ανακαλύψεων: ο αλγόριθμος Simplex (Dantzig-1949), ο ελλειψοειδής αλγόριθμος (Khachian-1979) και ο αλγόριθμος εσωτερικών σημείων (Karmarkar-1983). Στη συνέχεια - δεύτερο κεφάλαιο - γίνεται η θεωρητική θεμελίωση της μεθόδου Simplex, συμπεριλαμβάνοντας τόσο την γεωμετρική-εποπτική παρουσίαση της μεθόδου, όσο και την αυστηρή αλγεβρική τεκμηρίωσή της μέσω θεωρημάτων. Το τρίτο κεφάλαιο αφιερώθηκε στον αλγόριθμο των ελλειψοειδών, στη μέθοδο δηλαδή που ουσιαστικά απέδειξε ότι τα προβλήματα του γραμμικού προγραμματισμού μπορούν να λυθούν σε πολυωνυμικό χρόνο. Στο τέταρτο κεφάλαιο παρουσιάζεται η πιο σύγχρονη τάση στον τομέα επίλυσης προβλημάτων γραμμικού προγραμματισμού: οι μέθοδοι εσωτερικού σημείου. Συγκεκριμένα αναπτύσσεται ο αλγόριθμος του Karmakar, η κατηγορία των μεθόδων ομοπαραλληλικής αλλαγής κλίμακας και ο πρωτεύοντας-δυϊκός αλγόριθμος εσωτερικού σημείου. Τέλος, στο πέμπτο κεφάλαιο περιλαμβάνεται η παρουσίαση της έννοιας της υπολογιστικής πολυπλοκότητας αλγορίθμων, η πλήρης ανάλυση της πολυπλοκότητας των αλγορίθμων Simplex και εσωτερικού σημείου του Karmakar, καθώς και η σύγκριση των δύο αλγορίθμων. The first chapter includes a historical retrospection in respect of the birth and growth of Operational Research and Linear Programming. Furthermore, the chronicle of the biggest discoveries is presented: the Simplex algorithm (Dantzig-1949), the ellipsoid algorithm (Khachian-1979) and the interior point algorithm (Karmarkar-1983). Thereafter -in the second chapter- the theoretical foundation of Simplex method is presented, including both the geometric- supervisory presentation and the strict algebraic documentation of the method via theorems. The third chapter refers to the ellipsoid algorithm, namely the method that proved that the problems of linear programming can be solved in polynomial time. In the fourth chapter, the most contemporary tendency in the field of solving problems of linear programming, is presented: the methods of interior point. Particularly, the algorithm of Karmakar and the primal-dual algorithm of interior point are expounded. Finally, the fifth chapter includes the presentation of the concept of computational complexity of algorithms, the complete analysis of complexity of algorithms Simplex and interior point of Karmakar, as well as the comparison of the two algorithms. 2010-02-08T11:04:20Z 2010-02-08T11:04:20Z 2009-10-29 2010-02-08T11:04:20Z Thesis http://nemertes.lis.upatras.gr/jspui/handle/10889/2627 gr Η ΒKΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. 0 application/pdf
institution UPatras
collection Nemertes
language Greek
topic Επιχειρησιακή έρευνα
Γραμμικός προγραμματισμός
Σίμπλεξ
Operational research
Linear programming
Simplex
519.72
spellingShingle Επιχειρησιακή έρευνα
Γραμμικός προγραμματισμός
Σίμπλεξ
Operational research
Linear programming
Simplex
519.72
Κατσίκης, Αναστάσιος
Ανάλυση και υπολογιστική πολυπλοκότητα τεχνικών επίλυσης προβλημάτων γραμμικού προγραμματισμού
description Το πρώτο κεφάλαιο περιλαμβάνει μια ιστορική αναδρομή σχετικά με τη γέννηση και την ανάπτυξη της Επιχειρησιακής Έρευνας και του Γραμμικού Προγραμματισμού. Επίσης παρουσιάζεται το χρονικό των μεγαλυτέρων ανακαλύψεων: ο αλγόριθμος Simplex (Dantzig-1949), ο ελλειψοειδής αλγόριθμος (Khachian-1979) και ο αλγόριθμος εσωτερικών σημείων (Karmarkar-1983). Στη συνέχεια - δεύτερο κεφάλαιο - γίνεται η θεωρητική θεμελίωση της μεθόδου Simplex, συμπεριλαμβάνοντας τόσο την γεωμετρική-εποπτική παρουσίαση της μεθόδου, όσο και την αυστηρή αλγεβρική τεκμηρίωσή της μέσω θεωρημάτων. Το τρίτο κεφάλαιο αφιερώθηκε στον αλγόριθμο των ελλειψοειδών, στη μέθοδο δηλαδή που ουσιαστικά απέδειξε ότι τα προβλήματα του γραμμικού προγραμματισμού μπορούν να λυθούν σε πολυωνυμικό χρόνο. Στο τέταρτο κεφάλαιο παρουσιάζεται η πιο σύγχρονη τάση στον τομέα επίλυσης προβλημάτων γραμμικού προγραμματισμού: οι μέθοδοι εσωτερικού σημείου. Συγκεκριμένα αναπτύσσεται ο αλγόριθμος του Karmakar, η κατηγορία των μεθόδων ομοπαραλληλικής αλλαγής κλίμακας και ο πρωτεύοντας-δυϊκός αλγόριθμος εσωτερικού σημείου. Τέλος, στο πέμπτο κεφάλαιο περιλαμβάνεται η παρουσίαση της έννοιας της υπολογιστικής πολυπλοκότητας αλγορίθμων, η πλήρης ανάλυση της πολυπλοκότητας των αλγορίθμων Simplex και εσωτερικού σημείου του Karmakar, καθώς και η σύγκριση των δύο αλγορίθμων.
author2 Τσάντας, Νικόλαος
author_facet Τσάντας, Νικόλαος
Κατσίκης, Αναστάσιος
format Thesis
author Κατσίκης, Αναστάσιος
author_sort Κατσίκης, Αναστάσιος
title Ανάλυση και υπολογιστική πολυπλοκότητα τεχνικών επίλυσης προβλημάτων γραμμικού προγραμματισμού
title_short Ανάλυση και υπολογιστική πολυπλοκότητα τεχνικών επίλυσης προβλημάτων γραμμικού προγραμματισμού
title_full Ανάλυση και υπολογιστική πολυπλοκότητα τεχνικών επίλυσης προβλημάτων γραμμικού προγραμματισμού
title_fullStr Ανάλυση και υπολογιστική πολυπλοκότητα τεχνικών επίλυσης προβλημάτων γραμμικού προγραμματισμού
title_full_unstemmed Ανάλυση και υπολογιστική πολυπλοκότητα τεχνικών επίλυσης προβλημάτων γραμμικού προγραμματισμού
title_sort ανάλυση και υπολογιστική πολυπλοκότητα τεχνικών επίλυσης προβλημάτων γραμμικού προγραμματισμού
publishDate 2010
url http://nemertes.lis.upatras.gr/jspui/handle/10889/2627
work_keys_str_mv AT katsikēsanastasios analysēkaiypologistikēpolyplokotētatechnikōnepilysēsproblēmatōngrammikouprogrammatismou
_version_ 1771297129802760192