Vypracovane-zkouskove-otazky - teorie

Jak se bázické řešení reprezentuje graficky v prostoru požadavků?

• Před zakreslením je dobré zjistit ocenění jednotlivých proměnných v účelové funkci, tedy všechny koeficienty vydělíme jejich cenou. Avšak doplňkové proměnné nemůžeme dělit nulovou sazbou, ale dělíme je limitně (nějakou velmi malou hodnotou blížící se nule). V omezujících podmínkách tedy vyjde výsledek podílů +nekonečno nebo – nekonečno podle typu podmínky, a v omezující podmínce určení se nevyskytuje, tudíž podíl je 0. V podstatě jde o to, že nesmíme, zapomenou znázornit doplňkové proměnné jak do plus nekonečna tak do minus nekonečna a pak řešit kde d protla vektor b

• Bázi přípustného řešení zde tvoří dvojice proměnných, pomocí jejichž nezáporné lineární kombinace dokážeme vyjádřit vektor požadavků (pokud spojnice koncových vektorů ai a aj protne vektor požadavků v prvním kvadrantu, proměnné xi a xj(dvojice těch co se protnuly) tvoří přípustnou bázi úlohy)

• V grafu vedeme rovnoběžky od rozhodovacích proměnných do +nekonečna a –nekonečna (pokud je v rovnici +d do + nekonečna, -d do – nekonečna), řešením je taková rovnoběžka doplňkových proměnných, která protne vektor požadavků nejdále od počátku (minimalizace) a nejblíže od počátku (maximalizace). Tím zjistíme, která dvojice proměnných tvoří optimální bázi úlohy. Abychom zjistili hodnotu těchto proměnných musíme se vrátit k rovnicovému tvaru. V němž nebazické položíme rovny nule a tím zjistíme hodnoty bazických proměnných. Dosazením do účelové funkce zjistíme její hodnotu.

4) Co je to degenerované řešení modelu lineárního programování? Jak se degenerované řešení reprezentuje graficky?

5) K čemu slouží „základní věty lineárního programování“? Jaké mají důsledky pro hledání optimálního řešení modelu LP?

Základní věty LP

• Optimální řešení úlohy LP leží vždy na hranici množiny přípustných řešení

• Má-li úloha LP přípustné řešení, má i přípustné bazické řešení

• Má-li úloha LP optimální řešení, má i optimální bazické řešení

• Má-li úloha LP více než jedno optimální bazické řešení, je optimálním řešením i jejich lineární konvexní kombinace

6) Uveďte 4 možné výsledky řešení modelů lineárního programování a znázorněte je graficky v prostoru požadavků

1. Model nemá přípustné řešení (MINIMALIZAČNÍ ÚLOHA)→neexistuje kombinace proměnných jejíž spojnice protne vektor požadavků v prvním kvadrantu

2. Model má právě jedno optimální řešení (MINIMALIZAČNÍ ÚLOHA)

3. Alternativní optimální řešení (MINIMALIZAČNÍ ÚLOHA)→vidíme, že první omezující podmínka byla kapacitního typu, protože je zde doplňková proměnná s kladnou hodnotou(do +nekonečna). Existuje alternativní řešení, jelikož spojnice vektorů a2-a4 protíná vektor požadavků ve stejném bodě jako spojnice vektorů a2-d1. Hodnota účelové funkce bude v obou případech stejná.

4. Model má přípustné řešení, ale hodnota účelové funkce může neomezeně růst nebo klesat (MAXIMALIZAČNÍ ÚLOHA)→průsečík spojnic a2-a3 s vektorem požadavků se nachází v počátku souřadnic. Pokud by byla úloha minimalizační, optimálním řešením by byla kombinace vektorů a1-a4.