Feasible region — Περιοχή Επιτρεπτών Λύσεων

Περιοχή επιτρεπτών λύσεων (ΠΕΛ) (επίσης σύνολο επιτρεπτών λύσεων, αγγλ. Feasible region, feasible set) — στην έρευνα επιχειρήσεων, στη βελτιστοποίηση και στη μαθηματική μοντελοποίηση, είναι το σύνολο όλων των δυνατών λύσεων (συνόλων τιμών μεταβλητών) που ικανοποιούν όλους τους περιορισμούς που έχουν επιβληθεί στο πρόβλημα.

Η ΠΕΛ αποτελεί έναν υποχώρο εντός του οποίου αναζητείται η βέλτιστη λύση. Οποιαδήποτε λύση βρίσκεται εκτός αυτής της περιοχής θεωρείται μη επιτρεπτή.

Ορισμός και Διαμόρφωση

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

• Ανισοτήτων: Καθορίζουν ανώτατα ή κατώτατα όρια για τις τιμές των μεταβλητών ή των συνδυασμών τους (π.χ. «η κατανάλωση πόρου Α δεν πρέπει να υπερβαίνει τις 100 μονάδες», «η ποσότητα παραγόμενου προϊόντος πρέπει να είναι τουλάχιστον 50 τεμάχια»).
• Ισοτήτων: Απαιτούν την ακριβή εκπλήρωση μιας συνθήκης (π.χ. «ο συνολικός όγκος μεταφορών πρέπει να ισούται με 1000 τόνους», «η ισορροπία εισερχόμενων και εξερχόμενων ροών ισούται με μηδέν»).
• Συνθηκών πρόσημου μεταβλητών: Συχνά οι μεταβλητές πρέπει να είναι μη αρνητικές, ακέραιες ή να ανήκουν σε ένα συγκεκριμένο διακριτό σύνολο.

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

Γεωμετρική Ερμηνεία

Η ΠΕΛ έχει συχνά παραστατική γεωμετρική ερμηνεία, ιδιαίτερα σε προβλήματα με μικρό αριθμό μεταβλητών:

• Στον δισδιάστατο χώρο (2 μεταβλητές): Κάθε γραμμικός περιορισμός-ανισότητα ορίζει ένα ημιεπίπεδο. Η ΠΕΛ αποτελεί την τομή αυτών των ημιεπιπέδων — ένα κυρτό πολύγωνο (ενδεχομένως αφόριστο ή κενό).
• Στον τρισδιάστατο χώρο (3 μεταβλητές): Κάθε γραμμικός περιορισμός-ανισότητα ορίζει έναν ημιχώρο. Η ΠΕΛ είναι η τομή αυτών των ημιχώρων — ένα κυρτό πολύεδρο.
• Στον πολυδιάστατο χώρο: Η ΠΕΛ που ορίζεται από γραμμικούς περιορισμούς είναι ένα κυρτό πολύτοπο.

Στην περίπτωση μη γραμμικών περιορισμών, η ΠΕΛ μπορεί να έχει πιο σύνθετη μορφή και να μην είναι κυρτή.

Ρόλος στη Βελτιστοποίηση

Η περιοχή επιτρεπτών λύσεων διαδραματίζει θεμελιώδη ρόλο στη βελτιστοποίηση:

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

Ιδιότητες της ΠΕΛ (σε προβλήματα γραμμικού προγραμματισμού)

Σε προβλήματα γραμμικού προγραμματισμού (ΓΠ), όπου όλοι οι περιορισμοί και η αντικειμενική συνάρτηση είναι γραμμικά, η ΠΕΛ διαθέτει σημαντικές ιδιότητες:

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

Η ΠΕΛ μπορεί να είναι:

• Φραγμένη: Έχει πεπερασμένες διαστάσεις.
• Αφόριστη: Εκτείνεται απεριόριστα προς μία ή περισσότερες κατευθύνσεις.
• Κενή: Δεν περιέχει κανένα σημείο.

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

• Ventzel E. S. Έρευνα επιχειρήσεων: προβλήματα, αρχές, μεθοδολογία. — Μόσχα: Nauka, 1988.
• Ackoff R., Sasieni M. Βασικές αρχές έρευνας επιχειρήσεων. — Μόσχα: Mir, 1971.
• 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)

Δείτε επίσης

• Έρευνα επιχειρήσεων
• Βελτιστοποίηση
• Μαθηματικό μοντέλο
• Περιορισμοί
• Επιτρεπτή λύση
• Βέλτιστη λύση
• Αντικειμενική συνάρτηση
• Γραμμικός προγραμματισμός
• Κυρτό σύνολο