Περιεχόμενο
Ο γραμμικός προγραμματισμός είναι ένας κλάδος των μαθηματικών και των στατιστικών που επιτρέπει στους ερευνητές να καθορίζουν λύσεις σε προβλήματα βελτιστοποίησης. Τα προβλήματα γραμμικού προγραμματισμού διακρίνονται από το ότι είναι σαφώς καθορισμένα από την άποψη της αντικειμενικής λειτουργίας, των περιορισμών και της γραμμικότητας. Τα χαρακτηριστικά του γραμμικού προγραμματισμού το καθιστούν ένα εξαιρετικά χρήσιμο πεδίο που έχει βρει χρήση σε εφαρμοσμένα πεδία, από την εφοδιαστική μέχρι το βιομηχανικό σχεδιασμό.
Βελτιστοποίηση
Όλα τα προβλήματα γραμμικού προγραμματισμού είναι προβλήματα βελτιστοποίησης. Αυτό σημαίνει ότι ο πραγματικός σκοπός πίσω από την επίλυση ενός προβλήματος γραμμικού προγραμματισμού είναι να μεγιστοποιήσει ή να ελαχιστοποιήσει κάποια αξία. Έτσι, προβλήματα γραμμικού προγραμματισμού εντοπίζονται συχνά στα οικονομικά, στις επιχειρήσεις, στη διαφήμιση και σε πολλούς άλλους τομείς που εκτιμούν την αποτελεσματικότητα και τη διατήρηση των πόρων. Παραδείγματα στοιχείων που μπορούν να βελτιστοποιηθούν είναι το κέρδος, η απόκτηση πόρων, ο ελεύθερος χρόνος και η χρησιμότητα.
Γραμμικότητα
Όπως υποδηλώνει το όνομα, τα προβλήματα γραμμικού προγραμματισμού έχουν όλα το χαρακτηριστικό ότι είναι γραμμικά. Ωστόσο, αυτό το χαρακτηριστικό γραμμικότητας μπορεί να είναι παραπλανητικό, καθώς η γραμμικότητα αναφέρεται μόνο στις μεταβλητές που είναι στην πρώτη ισχύς (και επομένως εξαιρούνται οι λειτουργίες ισχύος, οι τετραγωνικές ρίζες και άλλες μη γραμμικές λειτουργίες). Η γραμμικότητα όμως δεν σημαίνει ότι οι λειτουργίες ενός προβλήματος γραμμικού προγραμματισμού είναι μόνο μιας μεταβλητής. Εν ολίγοις, η γραμμικότητα σε προβλήματα γραμμικού προγραμματισμού επιτρέπει στις μεταβλητές να συνδέονται μεταξύ τους ως συντεταγμένες σε μια γραμμή, εξαιρουμένων άλλων σχημάτων και καμπυλών.
Αντικειμενική λειτουργία
Όλα τα προβλήματα γραμμικού προγραμματισμού έχουν μια λειτουργία που ονομάζεται "αντικειμενική λειτουργία". Η αντικειμενική συνάρτηση είναι γραμμένη με βάση τις μεταβλητές που μπορούν να αλλάξουν κατά βούληση (π.χ. χρόνος που δαπανάται για μια εργασία, μονάδες που παράγονται κ.ο.κ.). Η αντικειμενική λειτουργία είναι αυτή που ο διαλυτής ενός προβλήματος γραμμικού προγραμματισμού επιθυμεί να μεγιστοποιήσει ή να ελαχιστοποιήσει. Το αποτέλεσμα ενός προβλήματος γραμμικού προγραμματισμού θα δοθεί από την άποψη της αντικειμενικής λειτουργίας. Η αντικειμενική λειτουργία γράφεται με το κεφαλαίο γράμμα "Z" στα περισσότερα γραμμικά προβλήματα προγραμματισμού.
Περιορισμοί
Όλα τα προβλήματα γραμμικού προγραμματισμού έχουν περιορισμούς στις μεταβλητές εντός της αντικειμενικής συνάρτησης. Αυτοί οι περιορισμοί έχουν τη μορφή ανισοτήτων (π.χ. "b <3" όπου το b μπορεί να αντιπροσωπεύει τις μονάδες βιβλίων που γράφει ένας συγγραφέας ανά μήνα). Αυτές οι ανισότητες καθορίζουν τον τρόπο με τον οποίο η αντικειμενική λειτουργία μπορεί να μεγιστοποιηθεί ή να ελαχιστοποιηθεί, καθώς μαζί καθορίζουν τον "τομέα" στον οποίο μια οργάνωση μπορεί να λαμβάνει αποφάσεις σχετικά με τους πόρους.