Lineární programování, technika matematického modelování, ve které je lineární funkce maximalizována nebo minimalizována, pokud je vystavena různým omezením. Tato technika byla užitečná pro vedení kvantitativních rozhodnutí v obchodním plánování, v průmyslovém inženýrství a - v menší míře - v sociálních a fyzikálních vědách.
optimalizace: Lineární programování
Přestože se dnes řešení problémů každodenního rozhodování široce používá, bylo před rokem 1947 poměrně neznámé lineární programování
Řešení problému lineárního programování se redukuje na nalezení optimální hodnoty (největší nebo nejmenší, v závislosti na problému) lineárního výrazu (nazývaného objektivní funkce).
s výhradou řady omezení vyjádřených jako nerovnosti:
A, b a c jsou konstanty určené kapacitami, potřebami, náklady, zisky a dalšími požadavky a omezeními problému. Základním předpokladem při použití této metody je to, že různé vztahy mezi poptávkou a dostupností jsou lineární; to znamená, že žádný z x i není povýšen na jinou mocninu než 1. Pro získání řešení tohoto problému je nutné najít řešení systému lineárních nerovností (tj. množinu n hodnot proměnné x i, které současně uspokojí všechny nerovnosti). Objektivní funkce je poté vyhodnocena nahrazením hodnot x i v rovnici, která definuje f.
Aplikace metody lineárního programování se poprvé vážně pokusil koncem třicátých let sovětským matematikem Leonidem Kantorovičem a americkým ekonomem Wassily Leontiefem v oblasti výrobních plánů a ekonomie, jejich práce však byla po celá desetiletí ignorována. Během druhé světové války bylo lineární programování široce využíváno k řešení dopravy, plánování a přidělování zdrojů podléhajících určitým omezením, jako jsou náklady a dostupnost. Tyto aplikace udělaly mnoho pro stanovení přijatelnosti této metody, která získala další impuls v roce 1947 zavedením americké matematiky George Dantzigovy simplexní metody, která výrazně zjednodušila řešení problémů lineárního programování.
Avšak jak se snažili o stále složitější problémy týkající se více proměnných, počet potřebných operací exponenciálně vzrostl a překročil výpočetní kapacitu i těch nejvýkonnějších počítačů. V roce 1979 pak ruský matematik Leonid Khachiyan objevil algoritmus polynomiálního času - ve kterém počet výpočetních kroků roste spíše jako síla řady proměnných než exponenciálně - což umožňuje řešení dosud nepřístupných problémů. Khachiyanův algoritmus (nazývaný elipsoidní metoda) byl však při použití prakticky pomalejší než simplexová metoda. V roce 1984 objevil indický matematik Narendra Karmarkar další algoritmus polynomiálního času, metodu vnitřního bodu, která se ukázala jako konkurenční se simplexní metodou.
