Linear programming — Γραμμικός Προγραμματισμός

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

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

Αντικείμενο και σκοπός

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

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

Μαθηματική διατύπωση του προβλήματος ΓΠ

Το τυπικό πρόβλημα γραμμικού προγραμματισμού διατυπώνεται ως εξής:

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

Μαθηματικά, αυτό σημαίνει εργασία με γραμμικές συναρτήσεις και συστήματα γραμμικών εξισώσεων/ανισοτήτων.

Βασικές έννοιες του ΓΠ

• Μεταβλητές απόφασης (Ελεγχόμενες μεταβλητές): Μεγέθη, των οποίων οι τιμές πρέπει να προσδιοριστούν κατά τη διαδικασία επίλυσης του προβλήματος (π.χ. όγκοι παραγωγής διαφόρων προϊόντων, ποσότητες πόρων που κατευθύνονται σε διαφορετικούς στόχους).
• Αντικειμενική συνάρτηση: Γραμμική συνάρτηση των μεταβλητών απόφασης, της οποίας η τιμή απαιτείται να μεγιστοποιηθεί ή να ελαχιστοποιηθεί. Εκφράζει ποσοτικά τον στόχο του προβλήματος (π.χ. συνολικό κέρδος, συνολικό κόστος).
• Περιορισμοί: Σύστημα γραμμικών ισοτήτων ή/και ανισοτήτων, τις οποίες πρέπει να ικανοποιούν οι μεταβλητές απόφασης. Οι περιορισμοί αντικατοπτρίζουν τα όρια πόρων, τεχνολογικές απαιτήσεις, προγραμματικά έργα και άλλες συνθήκες του προβλήματος.
• Περιοχή εφικτών λύσεων (ΠΕΛ): Το σύνολο όλων των συνόλων τιμών των μεταβλητών απόφασης που ικανοποιούν όλους τους περιορισμούς του προβλήματος. Γεωμετρικά, στον πολυδιάστατο χώρο η ΠΕΛ αποτελεί ένα κυρτό πολύεδρο, ενδεχομένως αφoριστό ή κενό.
• Εφικτή λύση: Οποιοδήποτε σύνολο τιμών μεταβλητών που ανήκει στην ΠΕΛ.
• Βέλτιστη λύση: Εφικτή λύση στην οποία η αντικειμενική συνάρτηση λαμβάνει την ακρότατη (μέγιστη ή ελάχιστη) τιμή της. Εάν υπάρχει βέλτιστη λύση, αυτή βρίσκεται πάντα στο όριο της ΠΕΛ, τουλάχιστον σε μία από τις κορυφές του κυρτού πολυέδρου της ΠΕΛ (θεμελιώδες θεώρημα ΓΠ).

Μέθοδοι επίλυσης προβλημάτων ΓΠ

Υπάρχουν αρκετές βασικές μέθοδοι για την επίλυση προβλημάτων γραμμικού προγραμματισμού:

• Γραφική μέθοδος: Εφαρμόζεται για προβλήματα με δύο μεταβλητές απόφασης. Επιτρέπει την οπτική απεικόνιση της ΠΕΛ και της αντικειμενικής συνάρτησης στο επίπεδο και την εύρεση της βέλτιστης λύσης μέσω ανάλυσης των κορυφών της ΠΕΛ ή μετατόπισης της ισοϋψούς γραμμής της αντικειμενικής συνάρτησης.
• Μέθοδος simplex: Καθολικός επαναληπτικός αλγόριθμος, ανεπτυγμένος από τον George Dantzig. Η μέθοδος μεταβαίνει διαδοχικά από μια κορυφή της ΠΕΛ στην γειτονική, βελτιώνοντας την τιμή της αντικειμενικής συνάρτησης σε κάθε βήμα, έως ότου βρεθεί η βέλτιστη λύση. Είναι η κλασική και πιο γνωστή μέθοδος επίλυσης προβλημάτων ΓΠ.
• Μέθοδοι εσωτερικού σημείου: Εναλλακτική κατηγορία αλγορίθμων, που εμφανίστηκαν αργότερα από τη μέθοδο simplex. Κινούνται προς τη βέλτιστη λύση στο εσωτερικό της ΠΕΛ και όχι κατά μήκος των ορίων της. Αυτές οι μέθοδοι είναι ιδιαίτερα αποτελεσματικές για την επίλυση προβλημάτων ΓΠ πολύ μεγάλης διάστασης.

Δυϊσμός στον γραμμικό προγραμματισμό

Σε κάθε πρόβλημα γραμμικού προγραμματισμού (που ονομάζεται πρωτεύον) μπορεί να αντιστοιχιστεί ένα άλλο πρόβλημα ΓΠ, που ονομάζεται δυϊκό. Το πρωτεύον και το δυϊκό πρόβλημα συνδέονται στενά μεταξύ τους:

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

Εφαρμογές του ΓΠ

Ο γραμμικός προγραμματισμός βρίσκει ευρεία εφαρμογή σε:

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

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

• Dantzig G. Γραμμικός προγραμματισμός, εφαρμογές και γενικεύσεις. — Μ.: Progress, 1966.
• Yudin D. B., Goldstein E. G. Γραμμικός προγραμματισμός (θεωρία, μέθοδοι και εφαρμογές). — Μ.: Nauka, 1969.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10η έκδ., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11η έκδ., 2021)

Δείτε επίσης

• Έρευνα επιχειρήσεων
• Βελτιστοποίηση
• Αντικειμενική συνάρτηση
• Περιορισμοί
• Περιοχή εφικτών λύσεων
• Βέλτιστη λύση