Γραμμικός προγραμματισμός, τεχνική μαθηματικής μοντελοποίησης στην οποία μια γραμμική συνάρτηση μεγιστοποιείται ή ελαχιστοποιείται όταν υπόκειται σε διάφορους περιορισμούς. Αυτή η τεχνική ήταν χρήσιμη για την καθοδήγηση ποσοτικών αποφάσεων στον επιχειρηματικό σχεδιασμό, στη βιομηχανική μηχανική και - σε μικρότερο βαθμό - στις κοινωνικές και φυσικές επιστήμες.
βελτιστοποίηση: Γραμμικός προγραμματισμός
Αν και χρησιμοποιείται ευρέως τώρα για την επίλυση προβλημάτων καθημερινών αποφάσεων, ο γραμμικός προγραμματισμός ήταν συγκριτικά άγνωστος πριν από το 1947. Δεν υπήρχε καμία εργασία
Η λύση ενός προβλήματος γραμμικού προγραμματισμού μειώνεται στην εύρεση της βέλτιστης τιμής (μεγαλύτερη ή μικρότερη, ανάλογα με το πρόβλημα) της γραμμικής έκφρασης (που ονομάζεται αντικειμενική συνάρτηση)
υπόκειται σε ένα σύνολο περιορισμών που εκφράζονται ως ανισότητες:
Τα a, b και c είναι σταθερές που καθορίζονται από τις ικανότητες, τις ανάγκες, το κόστος, τα κέρδη και άλλες απαιτήσεις και περιορισμούς του προβλήματος. Η βασική υπόθεση στην εφαρμογή αυτής της μεθόδου είναι ότι οι διάφορες σχέσεις μεταξύ ζήτησης και διαθεσιμότητας είναι γραμμικές. Δηλαδή, κανένα από τα x i δεν αυξάνεται σε ισχύ διαφορετική από 1. Για να επιτευχθεί η λύση σε αυτό το πρόβλημα, είναι απαραίτητο να βρεθεί η λύση του συστήματος γραμμικών ανισοτήτων (δηλαδή, το σύνολο τιμών n οι μεταβλητές x i που ταυτόχρονα ικανοποιούν όλες τις ανισότητες). Η αντικειμενική συνάρτηση στη συνέχεια αξιολογείται αντικαθιστώντας τις τιμές του x i στην εξίσωση που ορίζει f.
Εφαρμογές της μεθόδου γραμμικού προγραμματισμού επιχειρήθηκαν για πρώτη φορά σοβαρά στα τέλη της δεκαετίας του 1930 από τον σοβιετικό μαθηματικό Leonid Kantorovich και από τον Αμερικανό οικονομολόγο Wassily Leontief στους τομείς των χρονοδιαγραμμάτων κατασκευής και των οικονομικών, αντίστοιχα, αλλά το έργο τους αγνοήθηκε για δεκαετίες. Κατά τη διάρκεια του Β 'Παγκοσμίου Πολέμου, ο γραμμικός προγραμματισμός χρησιμοποιήθηκε εκτενώς για την αντιμετώπιση της μεταφοράς, του προγραμματισμού και της κατανομής των πόρων που υπόκεινται σε ορισμένους περιορισμούς όπως το κόστος και η διαθεσιμότητα. Αυτές οι εφαρμογές έκαναν πολλά για να αποδείξουν την αποδοχή αυτής της μεθόδου, η οποία κέρδισε περαιτέρω ώθηση το 1947 με την εισαγωγή της απλής μεθόδου του Αμερικανού μαθηματικού George Dantzig, η οποία απλοποίησε σημαντικά τη λύση των προβλημάτων γραμμικού προγραμματισμού.
Ωστόσο, καθώς επιχειρήθηκαν όλο και πιο περίπλοκα προβλήματα που αφορούσαν περισσότερες μεταβλητές, ο αριθμός των απαραίτητων λειτουργιών επεκτάθηκε εκθετικά και υπερέβαινε την υπολογιστική ικανότητα ακόμη και των πιο ισχυρών υπολογιστών. Στη συνέχεια, το 1979, ο Ρώσος μαθηματικός Leonid Khachiyan ανακάλυψε έναν αλγόριθμο πολυώνυμου χρόνου - στον οποίο ο αριθμός των υπολογιστικών βημάτων αυξάνεται ως δύναμη του αριθμού των μεταβλητών και όχι εκθετικά - επιτρέποντας έτσι τη λύση των μέχρι τώρα απρόσιτων προβλημάτων. Ωστόσο, ο αλγόριθμος του Khachiyan (που ονομάζεται μέθοδος ελλειψοειδούς) ήταν πιο αργός από τη μέθοδο simplex όταν εφαρμόστηκε πρακτικά. Το 1984 ο Ινδός μαθηματικός Narendra Karmarkar ανακάλυψε έναν άλλο αλγόριθμο πολυωνύμου χρόνου, τη μέθοδο εσωτερικού σημείου, που αποδείχθηκε ανταγωνιστικός με τη μέθοδο simplex.
