EMM_I_dlya_ustnoy

Zápis vektorem bázického řešení

• např. XB = (0,0,b1,0,b2,b3) , obsahuje všechny proměnné jak jdou za sebou od X1,X2,…Xn, přes d1,d2….dn až po p1, p2….pn, s tím že všechny nebázické proměnné zapisujeme s jejich nulovou hodnotou a bázické s hodnotou vektoru pravých stran b

Zápis vektorem obecného řešení

• pomocí něj přepisujeme výsledek do podoby parametrického řešení, jednotlivé proměnné (parametry) zapisujeme přímo nýzvy a bázické proměnné vyjadřujeme pomocí proměnných nebázických

1. Co je to dualita modelů lineárního programování? Uveďte alespoň jeden příklad, kdy nám teorie duality výrazně zjednodušuje řešení úlohy.

• dualita je vztah mezi dvěma vektorovými prostory. V případě úloh LP se dualita projevuje tak, že ke každému modelu LP se dá přiřadit jeho duální verze, která má tytéž parametry, jako původní model, ale s jinou interpretací.

• duality se využívá zejména při analýze výsledků, kdy tvz. duální ceny poskytují důležité informace pro rozhodování

• princip: otočení úhlu pohledu o 90°

matice koeficientu A v primárním modelu a matice AT v duálním (transponovaná matice- řádky jsou sloupce, sloupce řádky)

• vektor pravých stran b v primárním modelu a vektor cen b v duálním modelu

• vektor cen c v primárním modelu a vektor pravých stran c v duálním modelu

1. Popište vztahy mezi prvky duálně sdružených úloh.

• primární úloha má optimální řešení X0 právě tehdy, když má duální úloha optimální řešení Y0

• Pro dvojici duálně sdružených úloh platí buď:

1. obě úlohy mají přípustné řešení, pak mají i optimální řešení

2. jedna z úloh přípustné řešení nemá, pak druhá nemá optimální řešení (bud´ také nemá přípustné řešení nebo má neomezenou účelovou funkci)

7) Co říká základní věta o dualitě? Jaký je její význam?

Má-li jedna z dvojice sdružených úloh optimální řešení, má optimální řešení i úloha druhá a optimální hodnoty obou účelových funkcí jsou stejné. Může-li hodnota účelové funkce jednoho se sdružených problému růst nebo klesat neomezeně, pak druhý problém nemá přípustné řešení.

význam: v důsledku vět o dualitě stačí vyřešit pouze jednu z duálně sdružených úloh, protože řešení druhé úlohy lze z tohoto řešení odvodit

Téma 5 a 6: Postoptimalizační analýza, praktické aplikace

1. Uveďte postup stanovení nebázického řešení modelu LP. Jak určíte maximální hodnotu, kterou může nebázická proměnná nabýt? Co víte o optimálnosti nebázických řešení?

- hodnota nebázické proměnné v bázickém řešení je rovna nule, zajímá nás na jaké maximální úrovni můžeme nebázickou proměnnou do řešení zařadit, aby řešení zůstalo přípustné, to je aby všechny hodnoty vektoru pravých stran zůstaly nezáporné – mluvíme o intervalu přípustných hodnot nebázické proměnné