Θεωρία Βελτιστοποίησης – quiz

Ποιος είναι ο γενικός στόχος της μαθηματικής διαδικασίας βελτιστοποίησης;

Τα προβλήματα βελτιστοποίησης ονομάζονται και ως μαθηματικός προγραμματισμός.

Τι είναι «τοπικό ή σχετικό ελάχιστο» μιας συνάρτησης;

Τι είναι «καθολικό ή απόλυτο μέγιστο» μιας συνάρτησης;

5. Αν μια συνάρτηση f(x) έχει ακρότατο στη θέση x* (ελάχιστο ή μέγιστο) μεταξύ δύο τιμών της μεταβλητής x και υπάρχει η 1η παράγωγος της συνάρτησης στο σημείο x* τότε f’(x*)=0

Για να προσδιοριστεί εάν εκεί όπου μηδενίζεται η 1η παράγωγος είναι μέγιστο ή ελάχιστο χρειάζεται να ελεγχθεί η τιμή της 2ης ή ανώτερης παραγώγου στα κρίσιμα σημεία.

Ο υπολογισμός των ακρότατων βασίζεται στον υπολογισμό της κλίσης της αντικειμενικής συνάρτησης. Όμως η μηδενική κλίση δεν εξασφαλίζει την ύπαρξη ακρότατου.

Οι αναλυτικές μέθοδοι υπολογίζουν τη θέση των ακρότατων, τα οποία μπορεί να είναι καθολικά ή τοπικά. Όμως το καθολικό ακρότατο μπορεί να βρίσκεται στα συνοριακά σημεία ή σε σημεία που δεν υπάρχει η παράγωγος, άρα πρέπει να γίνεται έλεγχος και εκεί.

Τι είναι «γραμμικός προγραμματισμός»;

Τα χαρακτηριστικά ενός προβλήματος γραμμικού προγραμματισμού, το οποίο περιγράφεται στην κανονική μορφή (standard form) είναι:

Ένα πρόβλημα βελτιστοποίησης μπορεί να μετασχηματιστεί από πρόβλημα ελαχιστοποίησης σε πρόβλημα μεγιστοποίησης.

Μια μεταβλητή απόφασης που λαμβάνει οποιοδήποτε πρόσημο μπορεί να μετασχηματιστεί σε μη αρνητική:

Οι περιορισμοί με τη μορφή ανισοτήτων του τύπου «μικρότερο ή ίσο» ή «μεγαλύτερο ή ίσο» μπορούν να μετατραπούν σε ισότητες με την προσθήκη μιας νέας μη αρνητικής συμπληρωματικής (slack) ή πλεονασματικής (surplus) μεταβλητής αντίστοιχα (μεταβλητές απόκλισης).

Ένα τοπικό ελάχιστο που ανήκει σε ένα κυρτό σύνολο είναι και απόλυτο (καθολικό) ελάχιστο.

Το σύνολο εφικτών λύσεων ενός προβλήματος γραμμικού προγραμματισμού είναι κυρτό.

Ποιο είδος προβλημάτων βελτιστοποίησης μπορεί να επιλυθεί με γραφικό τρόπο.

Οι μέθοδοι απαλοιφής

Η μέθοδος Fibonacci στα προβλήματα βελτιστοποίησης

Η τετραγωνική μέθοδος παρεμβολής στα προβλήματα βελτιστοποίησης

Οι μέθοδοι άμεσης αναζήτησης (Direct search methods)

Οι μέθοδοι καθόδου ή κλίσης (descent ή gradient ή indirect methods)

Οι τεχνικές συναρτήσεων ποινής

Οι συναρτήσεις ποινής εξωτερικού σημείου

Οι συναρτήσεις ποινής εσωτερικού σημείου

Οι εξελικτικοί αλγόριθμοι

Ο ακέραιος προγραμματισμός

Η Weighted Sum Method

Το όριο Pareto