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

Ο γραμμικός προγραμματισμός (Γ.Π., Linear Programming, L.P.) ή αλλιώς γραμμική βελτιστοποίηση, είναι μέθοδος για την επίτευξη του καλύτερου αποτελέσματος (για παράδειγμα: μέγιστο κέρδος ή ελάχιστο κόστος) σε ένα μαθηματικό υπόδειγμα, του οποίου οι προϋποθέσεις (περιορισμοί) είναι ένα σύνολο γραμμικών σχέσεων των μεταβλητών του.

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

Τα προβλήματα γραμμικού προγραμματισμού εκφράζονται στην κανονική μορφή ως εξής:

${\begin{aligned}&{\text{Μεγιστοπο}}{\acute {\iota }}{\text{ησε το}}&&{\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}\\&{\acute {\epsilon }}{\text{τσι }}\ {\acute {\omega }}{\text{στε}}&&{\boldsymbol {A}}{\boldsymbol {x}}\leq {\boldsymbol {b}}\\&{\text{και}}&&{\boldsymbol {x}}\geq {\boldsymbol {0}}\end{aligned}}$

,όπου το $x$ συμβολίζει το διάνυσμα μεταβλητών (τις τιμές των οποίων αναζητούμε), τα $c$ και $b$ είναι (γνωστά) διανύσματα σταθερών όρων, ο $A$ είναι (γνωστός) πίνακας σταθερών όρων, και το σύμβολο $(\cdot )^{\mathrm {T} }$ δηλώνει την αναστροφή ενός διανύσματος ή πίνακα. Η παράσταση προς βελτιστοποίηση στο προκείμενο παράδειγμα είναι η $c^{\mathrm {T} }x$. Οι ανισότητες $Ax\leq b$ και $x\geq 0$ είναι οι περιορισμοί που καθορίζουν το κυρτό πολύεδρο στο οποίο καλούμαστε να βελτιστοποιήσουμε τη δοθείσα παράσταση.

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