Υπολογιστικές βελτιώσεις και αποτελεσματική υλοποίηση περιστροφικών αλγορίθμων δύο δρόμων

Περίληψη

Ο Γραμμικός Προγραμματισμός ασχολείται με τη βελτιστοποίηση (ελαχιστοποίηση ή μεγιστοποίηση) μιας γραμμικής συνάρτησης κάτω από ορισμένους γραμμικούς (ισοτικούς ή ανισοτικούς) περιορισμούς. Από την ανακάλυψη του αλγορίθμου simplex, το 1947, από τον Dantzig μέχρι σήμερα έχει συντελεστεί μεγάλη πρόοδος στην επιστήμη του Μαθηματικού Προγραμματισμού. Από τη στιγμή που αποδείχτηκε ότι η πολυπλοκότητα χειρότερης του αλγορίθμου simplex είναι εκθετική, το ενδιαφέρον των ερευνητών στράφηκε στη δημιουργία αλγορίθμων πολυωνυμικού χρόνου και στην επίλυση γραμμικών προβλημάτων μεγάλης κλίμακας. Στις αρχές της δεκαετίας του ’90 εμφανίστηκε μια νέα κλάση αλγορίθμων τύπου simplex στη διεθνή βιβλιογραφία. Οι αλγόριθμοι αυτής της κλάσης ονομάζονται αλγόριθμοι εξωτερικών σημείων ή αλγόριθμοι δύο δρόμων. Η πρώτη επιστημονική εργασία στην οποία παρουσιάζεται ένας αλγόριθμος εξωτερικών σημείων δημοσιεύτηκε το 1991 από τον Paparrizos. Ο πρωτεύων αλγόριθμος εξωτερικών σημείων έχει δύο μεγάλα υπολογιστικά μειο ...
περισσότερα

Περίληψη σε άλλη γλώσσα

Linear Programming deals with the optimization (minimization or maximization) of an objective function under certain linear (equality or inequality) constraints. Great progress has been made in mathematical programming since the introduction of the simplex algorithm in 1947 by Dantzig. Researchers' interest turned to polynomial complexity algorithms in order to solve large-scale linear problems since the moment that the worst-case complexity of the simplex algorithm proved to be exponential. In the early 1990s, a new class of simplex type algorithms appeared in the international bibliography. The algorithms of this class are called exterior point or two-path algorithms. The first paper, in which an exterior point algorithm was presented, published in 1991 by Paparrizos. The primal exterior point algorithm has two main computational drawbacks: 1.It is difficult to construct "good moving directions". The two paths depend on the initial feasible direction and the initial feasible vertex. ...
περισσότερα

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/30472
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/30472
ND
30472
Εναλλακτικός τίτλος
Computational improvements and efficient implementation of two pathpivoting algorithms
Συγγραφέας
Σαμαράς, Νικόλαος του Ευστάθιος
Ημερομηνία
2001
Ίδρυμα
Πανεπιστήμιο Μακεδονίας Οικονομικών και Κοινωνικών Επιστημών. Τμήμα Εφαρμοσμένης Πληροφορικής
Εξεταστική επιτροπή
Παπαρρίζο Κωνσταντίνος
Πέκος Γεώργιος
Τσιότρας Γεώργιος
Κάτος Αναστάσιος
Παπαναστασίου Δημήτριος
Μανιτσάρης Αθανάσιος
Στεφανίδης Γεώργιος
Επιστημονικό πεδίο
Φυσικές ΕπιστήμεςΜαθηματικά
Φυσικές ΕπιστήμεςΕπιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
Λέξεις-κλειδιά
Γραμμικός προγραμματισμός; Αλγόριθμοι τύπου Simplex; Αλγόριθμοι εξωτερικών σημείων; Υπολογιστική μελέτη
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά
Άλλα στοιχεία
219 σ., πιν., σχημ.
Στατιστικά χρήσης
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Google Analytics.
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη.
Πηγή: Google Analytics.
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
ΧΡΗΣΤΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.