Liniowe programowanie jest metodą matematyczną, która służy do określenia najlepszego możliwego wyniku lub rozwiązania z danego zestawu parametrów lub listy wymagań, które są reprezentowane w postaci zależności liniowych. Jest najczęściej używany w modelowaniu lub symulacji komputerowej w celu znalezienia najlepszego rozwiązania w przydzielaniu ograniczonych zasobów, takich jak pieniądze, energia, siła robocza, zasoby maszynowe, czas, przestrzeń i wiele innych zmiennych. W większości przypadków „najlepszy wynik” potrzebny do programowania liniowego, to maksymalny zysk lub najniższy koszt.
Programowanie liniowe jest procesem podejmowania różnych liniowych nierówności w odniesieniu do pewnej sytuacji i znajdowania najlepszej wartości możliwej do uzyskania w danych warunkach. Typowym przykładem byłoby przyjęcie ograniczeń dotyczących materiałów i robocizny, a następnie określenie najodpowiedniejszych poziomów produkcji dla maksymalnych zysków w tych warunkach. W prawdziwym życiu, programowanie to jest częścią bardzo ważnej dziedziny matematyki zwanej „technikami optymalizacji”. Ta dziedzina studiów (lub przynajmniej jej stosowane wyniki) są wykorzystywane codziennie w organizacji i przydziale zasobów.
Te „rzeczywiste” systemy mogą mieć dziesiątki lub setki zmiennych, a nawet znacznie więcej. W algebrze pracuje jednak tylko z prostą (i graficzną), dwuwymiarową liniową obudową. Ogólnym procesem rozwiązywania zadań programowania liniowego jest wykreślenie nierówności (zwanych „ograniczeniami”) w celu utworzenia „otoczonego murami” obszaru na płaszczyźnie x i y (nazywanej „regionem wykonalności”). Następnie oblicza sie współrzędne rogów tego obszaru wykonalności (czyli znajduje się punkty przecięcia różnych par linii) i testuje się te punkty narożne we wzorze (zwanym „równaniem optymalizacji”), dla którego próbuje się znaleźć najwyższą lub najniższą wartość. Liniowe programowanie służy jako metoda matematyczna do określania i planowania najlepszych wyników i zostało opracowane podczas II wojny światowej przez Leonida Kantorowicza.
Była to metoda używana do planowania wydatków i zwrotów w sposób, który zmniejsza koszty dla wojska i ewentualnie spowoduje niebezpieczeństwo dla wroga. To programowanie jest częścią ważnej dziedziny matematyki zwanej technikami optymalizacji, ponieważ jest ona dosłownie używana do znalezienia najbardziej zoptymalizowanego rozwiązania danego problemu. Bardzo podstawowym przykładem zastosowania optymalizacji liniowej jest logistyka lub metoda efektywnego przenoszenia rzeczy. Załóżmy na przykład, że istnieje 1000 pudełek o tej samej wielkości po 1 metrze sześciennym; 3 ciężarówki, które są w stanie przewieźć odpowiednio 100 skrzyń, 70 skrzyń i 40 skrzyń; kilka możliwych tras; i 48 godzin na dostarczenie we wskazane miejsce wszystkich tych pudeł.
Liniowe programowanie zapewnia wykonanie równań matematycznych w celu określenia optymalnego obciążenia ciężarówek i trasy, które należy podjąć, aby spełnić wymóg przetransportowania wszystkich skrzyń z punktu A do punktu B, z najmniejszą liczbą przejeżdżania tam i z powrotem oraz, oczywiście, najniższymi możliwymi kosztami w tej sytuacji i w najszybszym możliwym czasie.
Podstawowymi elementami programowania liniowego są elementy takie jak zmienne decyzyjne – są to ilości do ustalenia każdorazowo; funkcja celu – określa ona, w jaki sposób każda zmienna decyzyjna wpłynie na koszt, lub po prostu wartość, którą należy zoptymalizować; ograniczenia – reprezentujące sposób, w jaki każda zmienna decyzyjna wykorzystywałaby ograniczoną ilość zasobów oraz dane – określające ilościowo relacje między funkcją celu a ograniczeniami.
Ze względu na swój charakter, liniowe programowanie jest również nazywane optymalizacją liniową. Problemy z optymalizacją są wszechobecne w matematycznym modelowaniu systemów rzeczywistych i obejmują szeroki zakres zastosowań. Aplikacje te pojawiają się we wszystkich gałęziach ekonomii, finansów, chemii, inżynierii materiałowej, astronomii, fizyki, biologii strukturalnej i molekularnej, inżynierii, informatyce, a także i w medycynie. Modelowanie optymalizacji wymaga odpowiedniego czasu.
Ogólna procedura, którą można zastosować w cyklu procesu modelowania, polega na, po pierwsze, opisaniu problemu, następnie przepisaniu rozwiązania i ostatecznie, na kontrolowaniu problemu poprzez ciągłą ocenę/aktualizację optymalnego rozwiązania przy zmianie parametrów i struktury problemu. Oczywiście, wśród tych ogólnych kroków zawsze występują sprzężenia zwrotne.
