Sub-optimální řešení je bázické i nebázické řešení problému s dostatečně dobrou hodnotou kritéria, které se odvozuje z výsledné simplexové tabulky. Toto řešení musí být přípustné (tj splňující omezující podmínky), dostatečně dobré a musí být blízké optimálnímu řešení. Hodnota účelové funkce se blíží optimální.
Suboptimálním řešením rozumíme takový vektor řešení, který dostaneme z vektoru obecného řešení volbou určitého kladného čísla za alespoň jednu nezákladní strukturní proměnnou. Hodnota účelové funkce se oproti původní optimální vždy zhorší, tj. při maximalizaci se zmenší, při minimalizaci se zvětší.
Alternativní řešeni je každé další bázické i nebázické optimální řešení, které lze odvodit z výsledné simplexové tabulky a přináší stejnou hodnotu účelové funkce jako řešení optimální. Jedná se tedy o jiné optimální řešení. Alternativní řešení je indikováno tím, že alespoň jeden koeficient u nezákladní proměnné (proměnné která není v bázi) je roven nule. Platí pro něj stejné podmínky jako pro řešení optimální (poskytuje nejlepší hodnotu účelové funkce, přípustné...).
Alternativní řešení má tedy na rozdíl od řešení sub-optimálního stejnou hodnotu účelové funkce jako řešení optimální.
Při pohledu na výslednou optimální simplexovou tabulku rozpoznáme alternativní řešení tak, že v testu optima, ať již jde o maximalizační či minimalizační úlohu, hledáme nulovou hodnotu, která se nevztahuje k bazické proměnné. Nebazická proměnná jenž má v testu optima hodnotu rovnou nule, značí existenci alternativního řešení. Tato proměnná vstoupí do báze a bude tvořit další optimální (alternativní) řešení se stejnou hodnotou účelové funkce jakou mělo optimální řešení.
Rozpoznání sub-optimálního řešení při pohledu na optimální simplexovou tabulku je následovné:
Pokud se jedná o maximalizační úlohu, tak při pohledu na test optima hledáme kladnou hodnotu nejblíže k nule. Tato hodnota určuje o kolik se zhorší hodnota účelové funkce, zařazením jedné jednotky dané proměnné. Takovou to hodnotu tedy vybereme a zařadíme do báze a dopočítáme tabulku, dle simplexového algoritmu. Nově vzniklé řešení (tabulka) je sub-optimální řešení původního optimálního řešení, s horší u maximalizační úlohy tedy menší hodnotou účelové funkce.
Jedná-li se o minimalizační úlohy, nebo-li naším cílem je dosáhnout nejnižší možné hodnoty účelové funkce, hledáme zápornou hodnotu v optimální simplexové tabulce, která je nejblíže nule, vyjadřující to, o kolik se hodnota účelové funkce zhorší, v tomto případě tedy o kolik se hodnot účelové funkce zvýší. Sub-optimálním řešením u minimalizační úlohy simplexového algoritmu tedy bude tabulka, která bude obsahovat proměnnou vybranou z optimálního řešení na základě záporné hodnoty,která bude nalezena v řádku testu optimality, a která je nejblíže nule a to u proměnné nebazické.
2. červen 2018
3 677×
411 slov
