Vypracovane-zkouskove-otazky - teorie

7) Uveďte, jak v prostoru požadavků určíte přípustné řešení modelu lineárního programování a jak vyberete řešení optimální. Dokumentujte rovněž graficky.

Pokud jde o MIN. nákladů

• Hledám 2 proměnné x, které mi protnou přímku b

• V grafu je více přípustných řešení, například x4, x1(podmínka protnutí přímky b je tu splněna), další přípustné řešení jsou znázorněny v grafu ->

• Jako přípustné řešení se nebere například x1,x3 (neprotínají přímku b)

• Pokud chci najít optimální řešení pro MIN., musím najít proměnné x, které jsou nejdále od 0 => v tomto grafu to je X2,X3

• Optimálním řešením může být ale také jen jedna z proměnných

Téma 3: Simplexový algoritmus

1) Uveďte dvě základní podmínky pro aplikovatelnost simplexového algoritmu. Jaký je jejich význam, proč je jejich splnění nutné?

• Nezápornost složek vektoru pravých stran

• Stačí zkontrolovat

• Pokud není splněna, lze příslušné omezující podmínky vynásobit hodnotou (-1)

• Matice soustavy v kanonickém tvaru

• Krok 1: rovnicový tvar

• Krok 2: kanonický tvar modelu- zavádí se pomocné proměnné do všech omezujících podmínek typu >= nebo typu určení „=“

2) Popište postup převodu modelu z nerovnicového do rovnicového tvaru. Proč tento krok při řešení modelu lineárního programování provádíme?

• Při řešení úlohy LP vždy nejprve získáme výchozí základní přípustné řešení. K tomu je potřeba mít omezující podmínky úlohy ve tvaru soustavy lineárních rovnic v kanonickém tvaru. Jelikož omezující podmínky v úloze LP bývají zpravidla ve tvaru nerovnic, je prvním krokem převod této soustavy lineárních nerovnic (SLN) na soustavu lineárních rovnic (SLR)

• Matice soustavy musí obsahovat jednotkovou submatici, kterou tvoří koeficienty základníchproměnných (kanonický tvar)

• Nerovnice vyrovnáme na rovnice

• K tomu potřebujeme: doplňkové proměnné

  • značíme d, indexujeme číslem omezující podmínky

  • přidáváme do rovnic ≥(-d),≤(+d)

  • v účelové funkci ohodnocujeme 0 sazbou

  • požadujeme jejich nezápornost

• Přidáváme do omezujících podmínek

  • kapacitních s kladným znaménkem (rezerva);

  • požadavkových se záporným znaménkem (překročení požadavku)

PŘ:

X1+x2+x3≤100

X1≤20

5x1+4x2+x3≤300

Z (max)= 8x1+6x2+x3

Převod:

X1+x2+x3+d1=100

X1+d2=20

5x1+4x2+x3+d3=300

Z(max)= 8x1+6x2+x3+0d1+0d2+0d3

3) Popište postup převodu modelu z rovnicového do kanonického tvaru. Proč tento krok při řešení modelu lineárního programování provádíme?

Provádíme, protože jednou z podmínek pro aplikaci simplexového algoritmu je, že matice soustavy musí být v kanonickém tvaru (tvoří koeficienty základních proměnných)-jednotkovou submatici, abychom mohli využít Jordanovu eliminační metodu.

Kanonický tvar

• Nerovnice vyrovnáme na rovnice (doplňkové proměnné)

• Zajistíme úplnou jednotkovou submatici

• Pomocí pomocných proměnných