Vypracovane-zkouskove-otazky - teorie

31x1 + 32x2+ 33x3 = 30 13y1 + 23y2 + 33y3 + 43y4 <= 300

41x1 + 42x2 + 43x3 = 40

Z = 100x1 + 200x2 + 300x3 → MAX Z=10y1 + 20y2 + 30y3 + 40y4 →MIN

x1>= 0 x2….s.l. x3<=0 y1 >= 0, y2 <= 0, y3….s.l.

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

Věta o dualitě

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 bazický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 účeovou 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í nebazické proměnné do řešení bude mít vliv na hodnoty bazický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 nebazickou rozhodovací proměnnou → přidáváme aktivitu do výsledného řešení