Vypracovane-zkouskove-otazky - teorie

např. Xb= (0;0;b1;0;b2;b3) nebo jako vektor obecného řešení např.

x1

x2

b1 – a11 – a12

X0= d2

B2 - a21 –a 22 - +d2

B3 – a31 – a32

Vidíme, že první dvě rozhodovací proměnné jsou nebazické, rovněž nebyl překročen požadavek ve druhé omezující podmínce (d2=0).

Obecné vyjádření obsahu simplexové tabulky

Výchozí tvar

A – Matice strukturních koeficientů

I – jednotková matice, která vznikla doplněním přídatných proměnných

-cT – matice cenových koeficientů v anulovaném tvaru (-1)

0T – nulový vektor pod přídatnými proměnnými

0 – hodnota účelové funkce zj se na začátku rovná nule.

7) Popište účel, princip a postup provedení testu optimality v simplexové tabulce.

Test optimality

• Účelem je zjistit, zda je řešení optimální, zda můžeme dané bazické řešení zlepšit nebo ne

• Existuje bazické řešení s lepší hodnotou ÚF?

• Vychází z Jordanovy eliminační metody

• Záměna proměnných v bázi

• Zj – Cj = Cb x Aj – Cj

• Cb= vektor cen bazických proměnných

• Aj= vektor matice soustavy pod testovanou proměnnou a

• Cj= cena testované proměnné

• Koeficient zj – cj

• Záporný: hodnota ÚF se zvyšuje;

• Kladný: hodnota ÚF se snižuje;

• Nulový: proměnná nemá vliv na hodnotu

• Řešení je optimální

• Minimalizace: zj – cj ≤ 0 pro všechna j

• Maximalizace: zj – cj ≥ 0 pro všechna j

• Klíčový sloupec: maximální hodnota |zj – cj| z těch, které porušují podmínku optimality

8) Popište účel, princip a postup provedení testu přípustnosti v simplexové tabulce.

Cílem je získat nové bázické řešení, které i nadále bude splňovat podmínky pro aplikaci simplexového algoritmu

Proměnná, která je nadepsána v záhlaví klíčového sloupce se stane v dalším kroku základní, tedy vstoupí do báze. Klíčový sloupec zvolíme tím, že se koukneme na kriteriální řádek Zj-Cj a vybereme nejvíc nevýhodnou hodnotu, tedy u maximalizace největší záporné číslo a u minimalizace největší kladné číslo.

Ten řádek, kde vyjde podíl nejnižší, označíme jako klíčový řádek. Proměnná v řádku, ke kterému přísluší nejnižší podíl z báze vystoupí. Úpravami musíme dostat do klíčového pole1 a nad a pod něj 0, pomocí Gauss-Jordanovy eliminační metody. Klíčový pole= Pivot> číslo které mi protne klíčový sloupec a řádek

Test přípustnosti

• I nové řešení musí splňovat podmínky SA

• Nezáporné složky vektoru b

• Známe klíčový sloupec (z testu optima)

• Určíme klíčový řádek podle podílů

kde k je index klíčového sloupce

• Podíl složek z vektoru pravých stran (b) a hodnot matice soustavy v klíčovém sloupci

• Pouze pro aij > 0, nesmím dělit nulou a záporným

• Minimum z těchto podílů určuje klíčový řádek, název proměnné, jejíž hodnota je ve sloupci Ω minimální vstupuje do báze. Průsečík klíčového řádku a klíčového sloupce se nazývá klíčové pole (pivot).

• Toho aby hodnota klíčového pole (pivotu) byla 1, dosáhneme tím, že vydělíme daný řádek hodnotou pivotu. Poté postupujeme dále pomocí Jordánovy eliminační metody, cílem je aby místo klíčového sloupce byl v nové simplexové tabulce jednotkový vektor.

• Řešení je optimální ve chvíli, kdy na kriteriálním řádku jsou správné hodnoty pro maximalizaci a minimalizaci a kdy v bázi nemáme pomocnou proměnnou a nemůžeme zavedením nějaké proměnné do báze účelovou funkci zlepšit.