Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/2627
Title: Ανάλυση και υπολογιστική πολυπλοκότητα τεχνικών επίλυσης προβλημάτων γραμμικού προγραμματισμού
Authors: Κατσίκης, Αναστάσιος
Issue Date: 2010-02-08T11:04:20Z
Keywords: Επιχειρησιακή έρευνα
Γραμμικός προγραμματισμός
Σίμπλεξ
Keywords (translated): Operational research
Linear programming
Simplex
Abstract: Το πρώτο κεφάλαιο περιλαμβάνει μια ιστορική αναδρομή σχετικά με τη γέννηση και την ανάπτυξη της Επιχειρησιακής Έρευνας και του Γραμμικού Προγραμματισμού. Επίσης παρουσιάζεται το χρονικό των μεγαλυτέρων ανακαλύψεων: ο αλγόριθμος Simplex (Dantzig-1949), ο ελλειψοειδής αλγόριθμος (Khachian-1979) και ο αλγόριθμος εσωτερικών σημείων (Karmarkar-1983). Στη συνέχεια - δεύτερο κεφάλαιο - γίνεται η θεωρητική θεμελίωση της μεθόδου Simplex, συμπεριλαμβάνοντας τόσο την γεωμετρική-εποπτική παρουσίαση της μεθόδου, όσο και την αυστηρή αλγεβρική τεκμηρίωσή της μέσω θεωρημάτων. Το τρίτο κεφάλαιο αφιερώθηκε στον αλγόριθμο των ελλειψοειδών, στη μέθοδο δηλαδή που ουσιαστικά απέδειξε ότι τα προβλήματα του γραμμικού προγραμματισμού μπορούν να λυθούν σε πολυωνυμικό χρόνο. Στο τέταρτο κεφάλαιο παρουσιάζεται η πιο σύγχρονη τάση στον τομέα επίλυσης προβλημάτων γραμμικού προγραμματισμού: οι μέθοδοι εσωτερικού σημείου. Συγκεκριμένα αναπτύσσεται ο αλγόριθμος του Karmakar, η κατηγορία των μεθόδων ομοπαραλληλικής αλλαγής κλίμακας και ο πρωτεύοντας-δυϊκός αλγόριθμος εσωτερικού σημείου. Τέλος, στο πέμπτο κεφάλαιο περιλαμβάνεται η παρουσίαση της έννοιας της υπολογιστικής πολυπλοκότητας αλγορίθμων, η πλήρης ανάλυση της πολυπλοκότητας των αλγορίθμων Simplex και εσωτερικού σημείου του Karmakar, καθώς και η σύγκριση των δύο αλγορίθμων.
Abstract (translated): 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.
Appears in Collections:Τμήμα Μαθηματικών (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
Nimertis_Katsikis(ma).pdf613.29 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.