Interpretace výsledku, dualita Uveďte způsob, jak V simplexové tabulce identifikujete bazické a nebazické proměnné. Rovněž uveďte, jak určíte hodnoty všech proměnnách V daném bazickém řešení.
Bázické proměnné jsou proměnné, které tvoří jednotkou matici a v takovém případě musí být soustava převedena do kanonického tvaru. V simplexové tabulce je poznáme tak, že vektor který je napsán pod danou proměnou je tvořen ze samých nul a jedné jedničky. Bázické takto tvořeny nejsou..
Hodnoty všech proměnných v daném bazické řešení určíme tak, že hodnoty bazických proměnných položíme rovno nule a hodnoty nebazických proměnných položíme rovno příslušnému číslu ze sloupce pravých stran. (podívat se na simplexovou tabulku)
Co jsou duální ceny proměnných? Jak je určíme a interpretujeme?
Optimální hodnoty duálních proměnných (říká se jim duální nebo stínové ceny) udávají, o kolik se zvýší hodnota primární účelové funkce při maximalizaci (nebo o kolik klesne při minimalizaci). Interpretaci duálních cen si můžeme vysvětlit na příkladu výrobního programování (stanovení výrobního programu), kde jsou-li ceny výrobků stanoveny tak aby bylo dosaženo maximálního zhodnocení, pak jsou duální ceny relativním oceněním surovin. Buď je proměnná bázická, pak má nulovou duální hodnotu nebo je nebazická, pak je
nulová a její duální hodnota může být libovolná. Jsou-li nulové obě, pak
je to znakem existence více řešení.
Co jsou to matice báze a inverzní matice V modelech lineárního programování? Jak tyto matice určíme a jaký je jejich význam?
Označme si matici báze jako matici B která je tvořena nezávislými vektory z matice A..potom se matice B nazývá bází uvedené úlohy lineárního programování a každá báze určuje právě jedno bazické řešení. Sloupce matice B jsou tvořeny bazickými proměnými. Inverzní matice je matice, kde pro dvě matice platí vztah A*B=B*A=E – potom jsou tyto dvě matice vzájemně inverzní. Najdeme ji na místě jednotkové matice po použití jordanovy metody.
Určete obsah vektoru bazického a obecného řešení LP. Uveďte příklad.
Vektor bazického řešení je jednotkový, tedy, že je tvořen z nul a jedničky. Například e2=(0,1,0)
Prvky vektoru obecného řešení vyjadřují závislost jednotlivých, základních proměnných na nezákladních proměnných. Dosadíme-li do vektoru obecného řešení za nezákladní proměnné nuly tak obdržíme vektor základního řešení. Dosazením různých nenulových čísel za nezákladní proměnné dostaneme různá řešení dané soustavy.
Co je to dualita modelů lineárního programování? Uveďte alespoň jeden příklad, kdy nám teorie duality výrazně zjednoduší řešení úlohy
Dualita je vztah mezi dvěma vektorovými prostory. V případě úloh lineárního programováním dualita projevuje tak, že ke každé úloze LP lze přiřadit jinou, tedy duální úlohu LP. Obě tyto úlohy mají stejné parametry, ale s jinou ekonomickou interpretací. Dualita je přínosná například pro dobrou charakterizaci optimálních řešení úloh LP.
Popište vztahy mezi prvky duálně sdružených úloh
Hodnota účelové funkce primární a duální úlohy je stejná
Proměnná jedné úlohy odpovídá doplňkové proměnné druhé úlohy
Základní proměnné jedné úlohy odpovídají nezákladním proměnné druhé úlohy
Optimální řešení duální úlohy nalezneme v absolutní hodnotě v indexním řádku výsledné simplexové tabulky primární úlohy ve sloupcích doplňkových proměnných a naopak.
Duální hodnoty udávají přírůstek optimální hodnoty primární účelové funkce při jednotkové změně pravých stran soustavy vlastních omezení primární úlohy. Tj. například rozšíření požadavku o 3 jednotky ->klesne hodnota účelové funkce o 3.