Teorie-emm ke zkoušce

• matice koeficientů A v primárním modelu a matice AT v duálním

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

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

• největší problém: typ omezení a podmínky nezápornosti proměnných

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

• má-li primární úloha řešení, má ho i úloha duální, optimální hodnoty se sobě rovnají (MAX jedné úlohy = MIN druhé úlohy)

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

• navíc platí cTxo = bTyo.

• 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?

Věta o dualitě

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

• obě úlohy mají přípustná řešení, pak mají i optimální řešení > hodnoty obou účelových funkcí se sobě rovnají

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

• 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Í = řešení, ve kterém některá z bazických proměnných nabývá nulové hodnoty

DUALITA = vztah, který vzniká 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í (primární) mode, ale s jinou interpretací

• využití:

  • při zkoumání vlastností úloh LP

  • při důkazech

  • při odvozování algoritmů

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

téma 5 – 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í?

V případě nebazické proměnné přičtu hodnotu z testu optimality

O optimálnosti nebazických řešení víme to že jedna hodnota vždy musí jít do +- nekonečna.

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

Např. x1 = 10 > sloupec b – x1 x a1 ….a1 = sloupec x1

3) Po provedené optimalizaci modelu LP došlo je 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).

Podle vzorce….musim udelat rozdil

4) K čemu slouží analýza stability báze vzhledem ke složkám vektoru pravých stran? Popište rámcově způsob jejího provedení.