Lineární programování

Jako lineární programování nebo též lineární optimalizace či LP se označuje subdisciplína matematického programování, která řeší problém nalezení minima nebo maxima lineární funkce určitého počtu proměnných na množině popsané soustavou lineárních nerovnic.

Na tento typ úlohy lze převést řadu praktických problémů. Pro řešení jsou známy spolehlivé algoritmy.

Úloha

Úlohou lineárního programování je následující optimalizační úloha

${\displaystyle \min _{x\in M}c^{T}x,}$

přičemž:

• ${\displaystyle c^{T}x}$ označuje skalární součin vektorů c, x.
• množina přípustných řešení M je popsána soustavou

${\displaystyle Ax=b,\quad x\geq 0,}$

kde A je matice rozměru m × n, b je m-rozměrný vektor a c, x jsou n-rozměrné vektory. Součin Ax označuje součin matic.

Poznámky

1. Množina M představuje geometricky konvexní mnohostěn.
2. Optimální řešení úlohy (pokud existuje) leží ve vrcholu, popř. celé stěně konvexního polyedru M.
3. Existují speciální úlohy v rámci lineárního programování, např. dopravní problém.
4. Duální úloha k původní (tzv. primární) úloze je ve tvaru

${\displaystyle \max _{y\in N}b^{T}y,\quad N=\{y\in \mathbb {R} ^{m}\mid A^{T}y\leq c\}}$

.

Metody řešení

Nejznámější algoritmus na řešení úlohy lineárního programování je tzv. simplexový algoritmus (původem od G. B. Dantziga z roku 1951). Existují ale i jiné, asymptoticky rychlejší algoritmy, např. elipsoidová metoda (od L. Khachiyana z roku 1979), metoda vnitřních bodů (od N. Karmarkara z roku 1984).

Odkazy

Literatura

• Ján Plesník, Jitka Dupačová, Milan Vlach: Lineárne programovanie, ALFA, Bratislava 1990, 1. vydání
• Libuše Grygarová: Úvod do lineárního programování, skripta, Státní pedagogické nakladatelství, Praha 1975, 1. vydání, skripta
• Jitka Dupačová: Lineární programování, Státní pedagogické nakladatelství, Praha 1982, 1. vydání, skripta
• prof. Ing. Josef Jablonský, CSc.: Operační výzkum, Kvantitativní modely pro ekonomické rozhodování, Professional Publishing, 2002
• doc. RNDr. Bohdan Linda, CSc.: Lineární programování, Univerzita Pardubice, Pardubice 2009, 3. vydání

Související články

• Matematické programování
• Nelineární programování

Externí odkazy

• Obrázky, zvuky či videa k tématu lineární programování na Wikimedia Commons
• https://web.archive.org/web/20070107041207/http://www1.osu.cz/studium/mopv2/matemprog/linprog.htm
• https://web.archive.org/web/20051230031416/http://home.eunet.cz/berka/o/matempro.htm

Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.