Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

# Základy lineárního programování

Požadavky

- Simplexová metoda
- Věty o dualitě (bez důkazu)

Nejprve si udělejme malý výlet do geometrie. Polytop je zobecněním polygonu (mnohoúhelníku) do vyšších dimenzích. Pro dimenzi se ale používá ještě speciální název polyhedron a pro dimenzi polychoron. My se v dalším textu omezíme na konvexní polytopy, což jsou konvexní obaly konečně mnoha bodů. Vzhledem k tomu, že tyto konvexní polytopy jsou průnikem jistého množství poloprostorů, můžeme je popsat maticovou rovnicí tvaru

kde je matice řádu a je počet poloprostorů, jejichž průnikem je daný polytop, a je dimenze podprostoru, ve kterém polytop máme.

Simplex je -dimenzionální trojúhelník (průnik několika poloprostorů). Podle rostoucí dimenze je to tedy po řadě bod, úsečka, trojúhelník, čtyřstěn, pentachoron (viz obrázek 1) atd. Může být omezený i neomezený.

Obrázok: Pentachoron

Nyní přistupme k formální definici úlohy lineárního programování.

Terminologie

1. Vektoru říkáme cenový vektor, funkci pak účelová funkce.
2. Nerovnosti a jsou omezující podmínky, vektor je pravá strana úlohy.
3. Konkrétní zadání úlohy lineárního programování (tj. matice a vektory , ) je přípustné, pokud existuje nějaký bod splňující a . Jinak je zadání nepřípustné.
4. Úloha je neomezená, pokud můžeme účelovou funkcí dosáhnout na přípustných bodech libovolně veliké hodnoty. Jinak je omezená.

Věta

Pro přípustnou a omezenou úlohu lineárního programování1 existuje bod, ve kterém účelová funkce nabývá maxima. Těchto bodů obecně může být více a říkáme jim optimální řešení.

Subsections

- Simplexová metoda
- Duální úloha