Lineární programování

Lineární programování — je odvětví matematického programování a široce využívaná metoda výzkumu operací, věnovaná vývoji teorie a metod řešení úloh hledání extrému (maxima nebo minima) lineární funkce za přítomnosti lineárních omezení.

Lineární programování je jedním z nejsilnějších a nejčastěji používaných nástrojů pro řešení optimalizačních úloh v ekonomice, řízení, plánování, logistice a dalších oblastech.

Předmět a účel

Základní úloha lineárního programování — najít nejlepší (optimální) způsob rozdělení omezených zdrojů k dosažení určitého cíle, kdy jak cíl, tak omezení na využití zdrojů mohou být vyjádřeny lineárními závislostmi.

• Lineární programování umožňuje řešit praktické úlohy, jako jsou:
• Optimální plánování výroby.
• Optimalizace dopravních toků (dopravní úloha).
• Optimální rozdělení investic.
• Optimální dělení materiálů. Úloha o přiřazení.

Matematická formulace úlohy lineárního programování

Standardní úloha lineárního programování je formulována takto:

Je třeba najít hodnoty rozhodovacích proměnných, které maximalizují nebo minimalizují lineární účelovou funkci. Přitom jsou na rozhodovací proměnné kladena omezení v podobě soustavy lineárních rovností a/nebo lineárních nerovností. Zpravidla se přidává podmínka nezápornosti rozhodovacích proměnných (jejich hodnoty musí být větší nebo rovny nule), což je často dáno fyzickým nebo ekonomickým smyslem úlohy.

Matematicky to znamená práci s lineárními funkcemi a soustavami lineárních rovnic/nerovností.

Základní pojmy lineárního programování

• Rozhodovací proměnné (řízené proměnné): Veličiny, jejichž hodnoty je třeba určit v průběhu řešení úlohy (například objemy výroby různých produktů, množství zdrojů směřovaných k různým cílům).
• Účelová funkce: Lineární funkce rozhodovacích proměnných, jejíž hodnotu je třeba maximalizovat nebo minimalizovat. Kvantitativně vyjadřuje cíl úlohy (například celkový zisk, celkové náklady).
• Omezení: Soustava lineárních rovností a/nebo nerovností, které musí rozhodovací proměnné splňovat. Omezení odrážejí limity zdrojů, technologické požadavky, plánované úkoly a další podmínky úlohy.
• Oblast přípustných řešení (APŘ): Množina všech kombinací hodnot rozhodovacích proměnných, které splňují všechna omezení úlohy. Geometricky v mnohodimenzionálním prostoru představuje APŘ konvexní mnohostěn (polyedr), případně neomezený nebo prázdný.
• Přípustné řešení: Jakákoliv kombinace hodnot proměnných náležející APŘ.
• Optimální řešení: Přípustné řešení, při němž účelová funkce dosahuje svého extrémního (maximálního nebo minimálního) hodnoty. Pokud optimální řešení existuje, nachází se vždy na hranici APŘ, alespoň v jednom z vrcholů konvexního mnohostěnu APŘ (základní věta lineárního programování).

Metody řešení úloh lineárního programování

Existuje několik základních metod pro řešení úloh lineárního programování:

• Grafická metoda: Používá se pro úlohy se dvěma rozhodovacími proměnnými. Umožňuje názorně znázornit APŘ a účelovou funkci v rovině a najít optimální řešení analýzou vrcholů APŘ nebo posouváním vrstevnice účelové funkce.
• Simplexová metoda: Univerzální iterační algoritmus vyvinutý Georgem Dantzigem. Metoda postupně přechází z jednoho vrcholu APŘ do sousedního, přičemž na každém kroku zlepšuje hodnotu účelové funkce, dokud není nalezeno optimální řešení. Je to klasická a nejznámější metoda řešení úloh lineárního programování.
• Metody vnitřního bodu: Alternativní třída algoritmů, které se objevily později než simplexová metoda. Pohybují se k optimálnímu řešení uvnitř APŘ, nikoliv po jejích hranicích. Tyto metody jsou zvláště účinné při řešení úloh lineárního programování velmi velké dimenze.

Dualita v lineárním programování

Každé úloze lineárního programování (nazývané primární) lze přiřadit jinou úlohu lineárního programování, nazývanou duální. Primární a duální úloha jsou spolu úzce svázány:

Řešení jedné úlohy poskytuje informace o řešení druhé. Optimální hodnoty účelových funkcí v obou úlohách se shodují (pokud existují). Proměnné duální úlohy mají důležitou ekonomickou interpretaci — odpovídají stínovým cenám (nebo duálním odhadům) zdrojů a ukazují, o kolik se změní optimální hodnota účelové funkce primární úlohy při malé změně omezení příslušného zdroje.

Využití lineárního programování

Lineární programování nachází široké uplatnění v:

• Ekonomice a podnikání (plánování výroby, logistika, finance, marketing).
• Průmyslu (optimalizace technologických procesů, řízení zásob, dělení materiálů).
• Dopravě (optimalizace tras, jízdních řádů). Zemědělství (optimalizace osevních ploch, krmných dávek).
• Energetice (optimalizace zatížení výrobních kapacit).

Literatura

• Dantzig, G. Lineární programování, jeho aplikace a zobecnění. — M.: Progress, 1966.
• Judin, D. B., Goldštejn, J. G. Lineární programování (teorie, metody a aplikace). — M.: Nauka, 1969.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

Viz také

• Výzkum operací
• Optimalizace
• Účelová funkce
• Omezení
• Oblast přípustných řešení
• Optimální řešení