Lineární programování

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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.

Úloha[editovat | editovat zdroj]

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

\min_{x\in M} c^Tx,

přičemž:

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[editovat | editovat zdroj]

  1. Množina M představuje geometricky konvexní polyedr (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 tvaru
\max_{y\in N} b^Ty,\quad N=\{y\in\mathbb{R}^m \mid A^Ty\leq c\}

.

Metody řešení[editovat | editovat zdroj]

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).

Reference[editovat | editovat zdroj]

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

Externí odkazy[editovat | editovat zdroj]

http://www1.osu.cz/studium/mopv2/matemprog/linprog.htm
http://home.eunet.cz/berka/o/matempro.htm
http://www.scribd.com/renepuchinger/d/98032672-Cviceni-z-Linearniho-programovani-FJFI