Optimal solution (optimization) — Βέλτιστη λύση

Βέλτιστη λύση — στην έρευνα επιχειρήσεων, τη βελτιστοποίηση και τη θεωρία λήψης αποφάσεων, είναι μια αποδεκτή λύση (δηλαδή που ικανοποιεί όλους τους περιορισμούς του προβλήματος), η οποία εξασφαλίζει την ακραία (μέγιστη ή ελάχιστη, ανάλογα με τη διατύπωση του προβλήματος) τιμή της αντικειμενικής συνάρτησης.

Η αναζήτηση της βέλτιστης λύσης αποτελεί τον κύριο στόχο της επίλυσης των περισσότερων προβλημάτων βελτιστοποίησης.

Ουσία και χαρακτηριστικά

Η βέλτιστη λύση διαθέτει δύο βασικά χαρακτηριστικά:

1. Αποδεκτότητα: Πρέπει να ικανοποιεί όλους τους περιορισμούς που έχουν επιβληθεί στις μεταβλητές του μοντέλου. Με άλλα λόγια, η βέλτιστη λύση ανήκει πάντα στην περιοχή αποδεκτών λύσεων (ΠΑΛ). 2. Ακραιότητα ως προς την αντικειμενική συνάρτηση: Μεταξύ όλων των αποδεκτών λύσεων, εξασφαλίζει την καλύτερη (μέγιστη ή ελάχιστη) τιμή της αντικειμενικής συνάρτησης, η οποία τυποποιεί το κριτήριο βελτιστότητας.

Δεν είναι κάθε αποδεκτή λύση βέλτιστη, αλλά κάθε βέλτιστη λύση πρέπει απαραιτήτως να είναι αποδεκτή.

Σχέση με την περιοχή αποδεκτών λύσεων

Η περιοχή αποδεκτών λύσεων (ΠΑΛ) αποτελεί το σύνολο όλων των εναλλακτικών (συνόλων τιμών μεταβλητών) που ικανοποιούν τους περιορισμούς του προβλήματος. Η βέλτιστη λύση είναι το σημείο (ή τα σημεία) σε αυτήν την περιοχή όπου η αντικειμενική συνάρτηση επιτυγχάνει το ακρότατό της. Εάν η ΠΑΛ είναι κενή, τότε το πρόβλημα δεν έχει ούτε αποδεκτές, ούτε, κατά συνέπεια, βέλτιστες λύσεις.

Ρόλος της αντικειμενικής συνάρτησης και των περιορισμών

• Οι περιορισμοί ορίζουν το σύνολο των εφικτών λύσεων (ΠΑΛ).
• Η αντικειμενική συνάρτηση καθορίζει ποια από αυτές τις εφικτές λύσεις είναι η καλύτερη (βέλτιστη).

Χωρίς αντικειμενική συνάρτηση είναι αδύνατο να προσδιοριστεί ποια από τις αποδεκτές λύσεις είναι βέλτιστη. Χωρίς περιορισμούς, το πρόβλημα μπορεί να είναι τετριμμένο ή να μην έχει πεπερασμένη βέλτιστη λύση (για παράδειγμα, μεγιστοποίηση γραμμικής συνάρτησης χωρίς περιορισμούς).

Μοναδικότητα της βέλτιστης λύσης

Η βέλτιστη λύση δεν είναι πάντα μοναδική. Σε ορισμένα προβλήματα (για παράδειγμα, στον γραμμικό προγραμματισμό, εάν η αντικειμενική συνάρτηση είναι παράλληλη προς έναν από τους ενεργούς περιορισμούς) μπορεί να υπάρχει άπειρο πλήθος βέλτιστων λύσεων με την ίδια τιμή αντικειμενικής συνάρτησης. Ωστόσο, η τιμή της αντικειμενικής συνάρτησης στο σημείο (ή τα σημεία) του βέλτιστου είναι πάντα μοναδική (εάν το βέλτιστο υπάρχει).

Μέθοδοι εύρεσης

Για την αναζήτηση βέλτιστων λύσεων στην έρευνα επιχειρήσεων χρησιμοποιούνται διάφορες μαθηματικές μέθοδοι, ανάλογα με τον τύπο του μοντέλου:

• Μέθοδος simplex (για γραμμικό προγραμματισμό)
• Μέθοδοι gradient descent και άλλες αριθμητικές μέθοδοι (για μη γραμμικό προγραμματισμό)
• Μέθοδος διακλάδωσης και ορίων, μέθοδοι αποκοπών (για ακέραιο προγραμματισμό)
• Μέθοδοι δυναμικού προγραμματισμού

Εξάρτηση από το μοντέλο

Είναι σημαντικό να κατανοηθεί ότι μια λύση είναι βέλτιστη μόνο στο πλαίσιο του υιοθετημένου μαθηματικού μοντέλου. Εάν το μοντέλο δεν αντικατοπτρίζει επαρκώς την πραγματική κατάσταση (εσφαλμένα επιλεγμένη αντικειμενική συνάρτηση, μη συμπερίληψη σημαντικών περιορισμών ή εξαρτήσεων), τότε η τυπικά ευρεθείσα βέλτιστη λύση μπορεί να αποδειχθεί αναποτελεσματική ή ακόμη και εσφαλμένη στην πράξη.

Βελτιστότητα σε πολυκριτηριακά προβλήματα

Σε προβλήματα με πολλαπλές αντικειμενικές συναρτήσεις (Πολυκριτηριακή βελτιστοποίηση) η έννοια της μοναδικής βέλτιστης λύσης αντικαθίσταται συχνά από την έννοια της βελτιστότητας κατά Pareto. Μια λύση βέλτιστη κατά Pareto είναι μια αποδεκτή λύση για την οποία είναι αδύνατο να βελτιωθεί η τιμή μιας αντικειμενικής συνάρτησης χωρίς να επιδεινωθεί η τιμή τουλάχιστον μιας άλλης.

Βιβλιογραφία

• Вентцель Е. С. Исследование операций: задачи, принципы, методология. — М.: Наука, 1988.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

Δείτε επίσης

• Έρευνα επιχειρήσεων
• Βελτιστοποίηση
• Μαθηματικό μοντέλο
• Αντικειμενική συνάρτηση
• Περιορισμοί
• Περιοχή αποδεκτών λύσεων
• Αποδεκτή λύση
• Κριτήριο
• Θεωρία λήψης αποφάσεων
• Πολυκριτηριακή βελτιστοποίηση
• Βελτιστότητα κατά Pareto
• Ακρότατο