Programowanie liniowe, technika modelowania matematycznego, w której funkcja liniowa jest zmaksymalizowana lub zminimalizowana, gdy podlega różnym ograniczeniom. Technika ta była przydatna w podejmowaniu decyzji ilościowych w planowaniu biznesowym, inżynierii przemysłowej oraz - w mniejszym stopniu - w naukach społecznych i fizycznych.
optymalizacja: programowanie liniowe
Chociaż powszechnie stosowane obecnie do rozwiązywania codziennych problemów decyzyjnych, programowanie liniowe było stosunkowo nieznane przed 1947 r. Żadna praca nie miała żadnego znaczenia
Rozwiązanie problemu programowania liniowego sprowadza się do znalezienia optymalnej wartości (największej lub najmniejszej, w zależności od problemu) wyrażenia liniowego (zwanej funkcją celu)
z zastrzeżeniem zestawu ograniczeń wyrażonych jako nierówności:
Wartości a, b i c są stałymi wyznaczonymi przez możliwości, potrzeby, koszty, zyski oraz inne wymagania i ograniczenia problemu. Podstawowym założeniem przy stosowaniu tej metody jest to, że różne zależności między popytem a dostępnością są liniowe; to znaczy żaden z X i jest podniesione do potęgi drugiej niż 1. W celu uzyskania rozwiązania tego problemu, konieczne jest, aby znaleźć rozwiązanie układu nierówności liniowych (Oznacza to, że zbiór N Wartości zmienne x i, które jednocześnie spełniają wszystkie nierówności). Funkcja celu są następnie oceniane przez podstawienie wartości x i w równaniu definiuje C.
Zastosowania metody programowania liniowego po raz pierwszy poważnie próbowali pod koniec lat trzydziestych XX wieku sowiecki matematyk Leonid Kantorowicz i amerykański ekonomista Wassily Leontief, odpowiednio w obszarach harmonogramów produkcji i ekonomii, ale ich praca była ignorowana przez dziesięciolecia. Podczas II wojny światowej programowanie liniowe było szeroko stosowane do transportu, planowania i alokacji zasobów z zastrzeżeniem pewnych ograniczeń, takich jak koszty i dostępność. Aplikacje te zrobiły wiele, aby ustalić akceptowalność tej metody, która nabrała dalszego impetu w 1947 r. Dzięki wprowadzeniu metody simpleksowej amerykańskiego matematyka George'a Dantziga, co znacznie uprościło rozwiązanie problemów programowania liniowego.
Jednak w miarę jak podejmowano coraz bardziej złożone problemy dotyczące większej liczby zmiennych, liczba niezbędnych operacji rosła wykładniczo i przekraczała możliwości obliczeniowe nawet najbardziej wydajnych komputerów. Następnie w 1979 r. Rosyjski matematyk Leonid Chachiyan odkrył algorytm czasu wielomianowego - w którym liczba kroków obliczeniowych rośnie jako potęga liczby zmiennych, a nie wykładniczo - umożliwiając w ten sposób rozwiązanie dotychczas niedostępnych problemów. Jednak algorytm Khachiyana (zwany metodą elipsoidy) był wolniejszy niż metoda simpleks, gdy był praktycznie stosowany. W 1984 r. Indyjski matematyk Narendra Karmarkar odkrył inny algorytm wielomianowy, metodę punktu wewnętrznego, który okazał się konkurencyjny w stosunku do metody simpleks.
