Teorie-emm ke žkoušce EMM
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
-
matice koeficientů A v primárním modelu a matice AT v duálním =transponovaná
6) Popište vztahy mezi prvky duálně sdružených úloh.
primární úloha má optimální řešení x
o právě tehdy, když má duální úloha optimální řešení yo
navíc platí cTx
o = b
Ty
o
nechť má primární úloha přípustné řešení x a duální úloha přípustné
řešení y, pro která platí cTx = bTy, pak jsou tato řešení optimálními řešeními obou úloh
7) Co říká věta o dualitě? Jaký je její význam? Má-li jeden ze sdružených modelů LP optimální řešení s konečnou hodnotou účelové funkce, 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 ze sdružených problému růst nebo klesat neomezeně, pak druhý
problém nemá přípustné řešení.
Má-li jeden z duálně sdružených modelů alternativní optimální řešení, řešení druhého modelu je
degenerované. Degenerované řešení je řešení, ve kterým některá z bázických proměnných nabývá
nulové hodnoty.
Pro dvojici duálně sdružených úloh platí buď:
obě úlohy mají přípustná řešení, pak mají i optimální řešení
nebo
jedna z úloh přípustné řešení nemá, pak druhá nemá optimální řešení (buď také nemá přípustné
řešení nebo má neomezenou účelovou funkci)
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
V duálním modelu je třeba do omezujících podmínek přidat pomocné proměnné, aby matice
soustavy byla v kanonickém tvaru. V optimálním řešení jsou pomocné proměnné mimo bázi.
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é
- dolní mez tohoto intervalu je kvůli podmínkám nezápornosti rovna nule, abychom zjistili horní mez
využijeme testu přípustnosti, při zařazování výhodné proměnné do báze tento test určuje
maximální přípustnou hodnotu této proměnné. Test přípustnosti nám zjistí maximální přípustnou
hodnotu této proměnné. Zařazení nebázické proměnné do řešení bude mít vliv na hodnoty
bázických proměnných a na hodnotu účelové funkce
- vyčíslení vlivu této proměnné: vynásobíme hodnotou zařazované proměnné příslušný sloupec v
simplexové tabulce a výslednou hodnotou opravíme hodnoty bázických proměnných
- změnu hodnoty účelové funkce určíme jako záporný součin hodnoty zařazované proměnné a její
duální ceny
- pokud zařadíme do báze nebázickou rozhodovací proměnnou → přidáváme aktivitu do výsledného
řešení
- kdybychom zařazovali nebázickou doplňkovou proměnnou – měníme jeden z původních parametrů
modelu (sloupec b), maximální hodnota této proměnné je minimum z podílu sloupce proměnné a
vektoru b
- zhoršují hodnotu účelové funkce
2) Bylo rozhodnuto zařadit do optimálního řešení nový proces (nebázickou
strukturní proměnnou). Popište postup, jak určíte vliv této změny na další
parametry modelu (hodnoty bázických proměnných a účelové funkce). - přidáme další aktivitu do výsledného řešení a rozšíříme si spektrum realizovaných aktivit
- určíme maximální hodnotu zařazované proměnné, tak že provedeme test přípustnosti pro příslušný
sloupec – z těchto podílů vybereme minimum –to je maximální hodnota proměnné, kterou
můžeme do báze zařadit, aby zůstala daná báze přípustná
- vyčíslení vlivu této proměnné: vynásobíme hodnotou zařazované proměnné příslušný sloupec v
simplexové tabulce a výslednou hodnotou opravíme hodnoty bázických proměnných
- změnu hodnoty účelové funkce určíme jako záporný součin hodnoty zařazované proměnné a její
duální ceny
3) Po provedené optimalizaci modelu LP došlo ke změně kapacity jednoho zdroje.
Popište postup, jak určíte vliv této změny na další parametry modelu (hodnoty
bázických proměnných a účelové funkce).
Postoptimalizační úvahy