Lineárne programovanie, technika matematického modelovania, pri ktorej je lineárna funkcia maximalizovaná alebo minimalizovaná, ak je vystavená rôznym obmedzeniam. Táto technika bola užitočná pri usmerňovaní kvantitatívnych rozhodnutí v obchodnom plánovaní, v priemyselnom inžinierstve a - v menšej miere - v spoločenských a fyzikálnych vedách.
optimalizácia: lineárne programovanie
Aj keď sa v súčasnosti bežne používa na riešenie problémov každodenného rozhodovania, bolo pred rokom 1947 pomerne neznáme lineárne programovanie
Riešenie problému lineárneho programovania sa redukuje na nájdenie optimálnej hodnoty (najväčšej alebo najmenšej, v závislosti od problému) lineárneho výrazu (nazývaného objektívna funkcia).
s výhradou obmedzení vyjadrených ako nerovnosti:
A, b a c sú konštanty určené kapacitami, potrebami, nákladmi, ziskami a ďalšími požiadavkami a obmedzeniami problému. Základným predpokladom pri použití tejto metódy je to, že rôzne vzťahy medzi dopytom a dostupnosťou sú lineárne; to znamená, že žiadny z i nie je povýšený na inú mocninu ako 1. Na získanie riešenia tohto problému je potrebné nájsť riešenie systému lineárnych nerovností (to znamená množinu n hodnôt premennej x i, ktorá súčasne spĺňa všetky nerovnosti). Objektívna funkcia sa potom vyhodnotí nahradením hodnôt x i v rovnici, ktorá definuje f.
Aplikácie metódy lineárneho programovania sa prvýkrát vážne pokúsili na konci 30. rokov sovietsky matematik Leonid Kantorovič a americký ekonóm Wassily Leontief v oblasti výrobných harmonogramov a ekonómie, ich práca sa však desaťročia ignorovala. Počas druhej svetovej vojny sa lineárne programovanie vo veľkej miere používalo na riešenie dopravy, plánovania a prideľovania zdrojov podliehajúcich určitým obmedzeniam, ako sú náklady a dostupnosť. Tieto aplikácie urobili veľa pre preukázanie prijateľnosti tejto metódy, ktorá získala ďalší impulz v roku 1947 zavedením simplexnej metódy amerického matematika Georga Dantziga, ktorá výrazne zjednodušila riešenie problémov s lineárnym programovaním.
Keďže sa však pokúšali čoraz zložitejšie problémy týkajúce sa viacerých premenných, počet potrebných operácií exponenciálne vzrástol a prekročil výpočtovú kapacitu aj tých najvýkonnejších počítačov. Potom v roku 1979 ruský matematik Leonid Khachiyan objavil algoritmus polynomiálneho času - v ktorom počet výpočtových krokov narastá skôr ako sila množstva premenných ako exponenciálne - čím umožňuje riešenie doteraz nedostupných problémov. Khachiyanov algoritmus (nazývaný elipsoidná metóda) bol však pri praktickom použití pomalší ako simplexová metóda. V roku 1984 indický matematik Narendra Karmarkar objavil ďalší algoritmus polynomiálneho času, metódu vnútorného bodu, ktorá sa ukázala ako konkurenčná so simplexnou metódou.
