Το λήμμα δεν περιέχει πηγές ή αυτές που περιέχει δεν επαρκούν.Μπορείτε να βοηθήσετε προσθέτοντας την κατάλληλη τεκμηρίωση. Υλικό που είναι ατεκμηρίωτο μπορεί να αμφισβητηθεί καινα αφαιρεθεί. Η σήμανση τοποθετήθηκε στις 27/09/2016.
Ογραμμικός προγραμματισμός (Γ.Π., Linear Programming, L.P.) ή αλλιώς γραμμική βελτιστοποίηση, είναι μέθοδος γιατην επίτευξη του καλύτερου αποτελέσματος (για παράδειγμα: μέγιστο κέρδος ή ελάχιστο κόστος) σε ένα μαθηματικό υπόδειγμα, του οποίου οι προϋποθέσεις (περιορισμοί) είναι ένα σύνολο γραμμικών σχέσεων των μεταβλητών του.
Πιο αυστηρά, ο γραμμικός προγραμματισμός είναι μία τεχνική γιατην μαθηματική βελτιστοποίηση μιας γραμμικής συνάρτησης δεδομένων κάποιων περιορισμών γραμμικών ισοτήτων ή γραμμικών ανισοτήτων. Ο χώρος που ορίζεται από αυτούς τους περιορισμούς είναι ένα κυρτό πολύεδρο. Ένας αλγόριθμος επίλυσης προβλημάτων γραμμικού προγραμματισμού βρίσκει ένα σημείο του πολύεδρου όπου η συνάρτηση λαμβάνει τη βέλτιστη τιμή, εφόσον το σημείο αυτό υπάρχει.
Τα προβλήματα γραμμικού προγραμματισμού εκφράζονται στην κανονική μορφή ως εξής:
,όπου το συμβολίζει το διάνυσμα μεταβλητών (τις τιμές των οποίων αναζητούμε), τακαι είναι (γνωστά) διανύσματα σταθερών όρων, ο είναι (γνωστός) πίνακας σταθερών όρων, καιτο σύμβολο δηλώνει την αναστροφή ενός διανύσματος ή πίνακα. Η παράσταση προς βελτιστοποίηση στο προκείμενο παράδειγμα είναι η. Οι ανισότητες και είναι οι περιορισμοί που καθορίζουν το κυρτό πολύεδρο στο οποίο καλούμαστε να βελτιστοποιήσουμε τη δοθείσα παράσταση.
Ο γραμμικός προγραμματισμός μπορεί να εφαρμοσθεί σε πληθώρα πεδίων. Χρησιμοποιείται ευρέως στηνεπιχειρησιακή έρευνακαιστηνοικονομία, καθώς επίσης καισε κάποια προβλήματα μηχανικής. Κάποιες βιομηχανίες που χρησιμοποιούν υποδείγματα γραμμικού προγραμματισμού είναι αυτές των μεταφορών, της ενέργειας καιτων τηλεπικοινωνιών.
