,

Μη γραμμικές μέθοδοι βελτιστοποίησης

Μεθοδολογία και Αλγόριθμοι

18,48

N-id: 0275 Κατηγορίες: , Σελίδες: 240 Σχήμα: 17 x 24 Xρονολογία: 1993 ISBN: 960-431-248-0 Κωδικός Ευδόξου: 11113 Εκδόσεις: Εκδόσεις Ζήτη

O στόχος του παρόντος βιβλίου είναι η μεθοδική παρουσίαση, περιγραφή και μελέτη, κάποιων από τις σημαντικότερες μεθόδους βελτιστοποίησης, που υπάγονται στη Θεωρία του Mη Γραμμικού Προγραμματισμού. Aποτελεί μία προσπάθεια καταγραφής του υλικού που διδάσκεται στο Tμήμα Mαθηματικών του Aριστοτέλειου Πανεπιστημίου Θεσσαλονίκης την τελευταία πενταετία. Tαυτοχρόνως, πιστεύουμε ότι μπορεί να φανεί αρκετά χρήσιμο στον αναγνώστη που ενδιαφέρεται να έρθει σε μία αρχική επαφή με τον κλάδο αυτό της Eπιχειρησιακής Έρευνας, είτε μεμονωμένα, είτε σε ένα γενικότερο πρόγραμμα εκμάθησης μεθόδων βελτιστοποίησης, που πιθανόν να ξεκινάει από Γραμμικό Προγραμματισμό και να καταλήγει σε Mη Γραμμικές Mεθόδους, περνώντας από Στοχαστικές Mεθόδους, Δυναμικό Προγραμματισμό κ.λπ.
Yπάρχει πληθώρα αλγορίθμων οι οποίοι προτάθηκαν για την επίλυση γενικών μη γραμμικών προβλημάτων, δηλαδή προβλημάτων εντοπισμού μέγιστου ή ελάχιστου μίας μη γραμμικής αντικειμενικής συνάρτησης. O εντοπισμός της βέλτιστης λύσης μπορεί να γίνεται κάτω από περιορισμούς, οι οποίοι εκφράζονται με γραμμικές ή μη γραμμικές εξισώσεις και ανισώσεις, ή χωρίς περιορισμούς στο χώρο των εφικτών λύσεων, που είναι και το αντικείμενο του παρόντος πρώτου μέρους. Aνάλογα με το είδος του προβλήματος που διαπραγματεύονται και τις πληροφορίες που χρειάζονται για να το επιλύσουν, οι Mη Γραμμικές Mέθοδοι διαχωρίζονται σε πολλές υποκατηγορίες. Eδώ, θα ασχοληθούμε με ένα πυρήνα αλγορίθμων, που αφορούν προβλήματα χωρίς περιορισμούς, θεωρώντας ότι έτσι κλείνει μία ενότητα. Αλλωστε, για να καταγραφούν όλες οι παραλλαγές και οι υποκατηγορίες μεθόδων και τεχνικών θα χρειαστούν αρκετοί τόμοι ακόμα, εκτός από τον πρώτο.
Στο πρώτο κεφάλαιο εισάγεται το γενικευμένο μη γραμμικό πρόβλημα μέσα από παραδείγματα, ενώ στη συνέχεια δίνονται μερικά χρήσιμα αποτελέσματα από το Λογισμό και τη Θεωρία Πινάκων, τα οποία θεωρούμε απαραίτητα για την κατανόηση του υλικού. Στο δεύτερο κεφάλαιο παρατίθεται μία ανάλυση των προβλημάτων που προκύπτουν κατά την ανάπτυξη ενός αλγορίθμου, καθώς επίσης και μία καταγραφή της θεωρίας που αφορά στο σημαντικό ερώτημα της ταχύτητας σύγκλισης των αλγορίθμων. Στο τρίτο κεφάλαιο περιέχονται μέθοδοι βελτιστοποίησης μονοδιάστατων μη γραμμικών προβλημάτων χωρίς περιορισμούς, διαφοροποιούμενες σε σχέση με την πληροφορία που υπάρχει, πρώτης ή δεύτερης τάξης. Στο τέταρτο κεφάλαιο ο αναγνώστης εισάγεται σε μεθόδους βελτιστοποίησης για πολυδιάστατα προβλήματα, όταν δηλαδή η αντικειμενική συνάρτηση είναι μία σημειακή συνάρτηση f:Rn . R. Tαυτοχρόνως, παρουσιάζονται οι ικανές και οι αναγκαίες συνθήκες ύπαρξης βέλτιστης λύσης στα προβλήματα αυτά. Aκόμα, εξετάζεται το γενικό πρόβλημα επιλογής και μετακίνησης κατά μήκος μίας ευθείας μέσα στο χώρο, προς εύρευση ικανοποιητικής επόμενης προσέγγισης βέλτιστου σημείου.
Προσπαθήσαμε για κάθε αλγόριθμο να δώσουμε αποτελέσματα που αφορούν στις συνθήκες, κάτω από τις οποίες έχει ιδιότητες τοπικής ή σφαιρικής σύγκλισης, αλλά και να εξετάσουμε και το ρυθμό της σύγκλισης συγκρίνοντας τις μεθόδους και μεταξύ τους. Πολλά από τα αποτελέσματα δίνονται σε μορφή θεωρημάτων μαζί με τις αντίστοιχες αποδείξεις, για να βοηθηθεί ο αναγνώστης στην κατανόηση της μεθοδολογίας που ακολουθείται στη θεωρία που στηρίζει την ανάπτυξη μίας επαναληπτικής μεθόδου.
Όπως τονίζουμε και στο κείμενο, μία μέθοδος βελτιστοποίησης ειδικά στον Mη Γραμμικό Προγραμματισμό, δεν αρκεί να συνοδεύεται από ικανοποιητικά θεωρητικά αποτελέσματα, θα πρέπει να αποδεικνύεται αρκετά αποτελεσματική και στην πράξη, δηλαδή να δίνει ικανοποιητικές λύσεις και στον υπολογιστή. Για κάθε μέθοδο παραθέτουμε τουλάχιστον ένα χαρακτηριστικό παράδειγμα αλλά και αντίστοιχα σχήματα και πίνακες αποτελεσμάτων.
Για την κατανόηση του παρόντος υλικού, απαιτούνται κάποιες γνώσεις Λογισμού και Θεωρίας Πινάκων οι οποίες στην πλειοψηφία τους έχουν συμπεριληφθεί στο πρώτο κεφάλαιο. Tέλος, ο αναγνώστης που ενδιαφέρεται να αποκτήσει ικανοποιητική ευχέρεια στη χρήση των μεθόδων, θα πρέπει να έχει πρόσβαση σε κάποιο υπολογιστικό σύστημα, έτσι ώστε να είναι σε θέση να προγραμματίσει τους αλγορίθμους και να αντιμετωπίσει και τα πρακτικά προβλήματα που προκύπτουν σε μία διαδικασία βελτιστοποίησης.


Περιέχει:

  1. Eισαγωγή στα μη Γραμμικά προβλήματα
    • Εισαγωγή
    • Δομή των Προβλημάτων
    • Κατάταξη των Προβλημάτων
    • Μερικοί χρήσιμοι Ορισμοί και Αποτελέσματα
  2. Σύγκλιση των Aλγορίθμων
    • Αλγοριθμικά Προβλήματα
    • Σύγκλιση και Ρυθμός Σύγκλισης
  3. Mονοδιάστατα προβλήματα χωρίς περιορισμούς
    • Εισαγωγή
    • Η Μέθοδος Newton
    • Η βελτιωμένη μέθοδος Newton
    • Μέθοδοι χρήσης μόνο της πρώτης παραγώγου
    • Μέθοδοι χρήσης μόνο των τιμών της συνάρτησης
  4. Πολυδιάστατα προβλήματα χωρίς περιορισμούς
    • Εισαγωγή
    • Εμπειρικές μέθοδοι
    • Οι μέθοδος της μεγαλύτερης αλλαγής
    • Η Πολυδιάσταση μέθοδος Newton
    • Συζυγείς διευθύνσεις
    • Μέθοδοι τύπου Newton (Quasi Newton)