Lineární programování
Z Wikipedie, otevřené encyklopedie
Lineární programování (dříve lineární optimalizace) je odvětví optimalizace. Řeší problém nalezení minima (resp. maxima) lineární funkce n proměnných na množině, popsané soustavou lineárních nerovností.
Na tento typ úlohy lze převést řadu praktických problémů. Pro řešení jsou známy spolehlivé algoritmy.
Obsah |
[editovat] Úloha
Úlohou lineárního programování je následující optimalizační úloha
![\min_{x\in M} c^Tx,](../../../math/8/1/b/81b7239ad817de22e3e54fc715b9806a.png)
přičemž:
- cTx označuje skalární součin vektorů c, x.
- množina přípustných řešení M je popsána soustavou
![Ax=b,\quad x\geq 0,](../../../math/b/3/a/b3a6ff6fcbe9707b49e45fc899008c40.png)
- 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.
[editovat] Poznámky
- Množina M představuje geometricky konvexní polyedr (mnohostěn).
- Optimální řešení úlohy (pokud existuje) leží ve vrcholu, popř. celé stěně konvexního polyedru M.
- Existují speciální úlohy v rámci lineárního programování, např. dopravní problém.
- Duální úloha k původní (tzv. primární) úloze je tvaru
![\max_{y\in N} b^Ty,\quad N=\{y\in\mathbb{R}^m \mid A^Ty\leq c\}](../../../math/f/7/5/f7591db20c4f29caaab8e9fd69530e54.png)
.
- V literatuře jsou často zaměněny definice primární a duální úlohy. To však ničemu nevadí.
- Mezi primární a duální úlohou platí zajímavé vztahy.
[editovat] 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, 1951). Existují ale i jiné, asymptoticky rychlejší algoritmy, např. elipsoidová metoda (L. Khachiyan 1979), metoda vnitřních bodů (N. Karmarkar 1984).
[editovat] Reference
- 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. vyádní, skripta
- Jitka Dupačová: Lineární programování, Státní pedagogické nakladatelství, Praha 1982, 1. vydání, skripta