Vypracovane-zkouskove-otazky - teorie

• Značíme p, indexujeme číslem omezující podmínky;

• Přebírají jednotky omezující podmínky

• V účelové funkci ohodnocujeme nevýhodnou (prohibitivní) sazbou;

• Požadujeme jejich nezápornost

• Přidáváme je pouze do omezujících podmínek typu „požadavkové“ nebo typu určení „=“ pouze s kladnou hodnotou

Př. A1x1 + a2x2 >= b2 → a1x1 + a2x2 – d2 + p3 = b2

4) Uveďte a stručně popište typy proměnných v modelech lineárního programování. Ke každému typu proměnných uveďte příklad interpretace.

Strukturní proměnné (x)

• Udávají úroveň jednotlivých procesů modelu (objem výroby obou druhů směsí)

Doplňkové proměnné (d)

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

• Přebírají jednotky omezující podmínky;

• V účelové funkci ohodnocujeme nulovou sazbou;

• Požadujeme jejich nezápornost

• Interpretace: 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).

Pomocné proměnné (p)

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

• Požadavkových „<=“;

• Typu určení;

• Vždy s kladným znaménkem

• A do účelové funkce přidáváme prohibitivní sazbu, kterou volíme tak, aby byla alespoň o jeden řád vyšší než řád rozhodovacích proměnných. Do minimalizačních modelů s kladným znaménkem a do maximalizačních modelů se záporným znaménkem

• Interpretace

• Kolik jednotek zbývá do splnění omezení;

• Řešení s kladnou hodnotou pomocné proměnné je proto automaticky nepřípustné

5) Uveďte a stručně popište typy omezujících podmínek v modelech lineárního programování. Ke každému typu uveďte příklad použití.

Omezující podmínky

• Vymezují přípustné kombinace hodnot proměnných.

• Základní typy omezujících podmínek:

  • kapacitní „ ≤ “ - omezení maximální kapacity (skladu, materiálu, času,…)

  • požadavkové „ ≥ “ - omezení minimálních požadavků kladených na model (minimální množství výrobků, které je potřeba vyrobit)

  • určení „ = “ - Pěstuji pšenici, ječmen a žito, a chci aby celková rozloha byla právě 140 ha => x1+x2+x3=140

  • nezápornosti

6) Prezentujte obecnou simplexovou tabulku. Jaké informace simplexová tabulka poskytuje?

• Koeficienty strukturních a doplňkových proměnných zapíšeme do vstupní simplexové tabulky

• První sloupec tabulky obsahuje proměnné, které jsou v bázi (struktura báze). V bázi jsou proměnné, jejichž vektory tvoří jednotkovou matici. V prvním řádku tabulky se nacházejí ceny všech proměnných a ve druhém řádku názvy proměnných a sloupců. Obsah sloupců zleva doprava tvoří: vektor cen proměnných (Cb), které tvoří bázi, druhý sloupec obsahuje názvy těchto bazických proměnných (Xb), pak následuje matice koeficientů u proměnných a posledním sloupcem je sloupec pravých stran (b). Poslední řádek tabulky je vyhrazen pro test optimality (Zj-Cj) a poslední sloupec pro test přípustnosti (Ω )

• Při zápisu výchozí simplexové tabulky, nejprve musíme zjistit jaké proměnné jsou bazické, abychom je mohli zapsat do sloupce (Xb). Zjistíme to jednoduše, podle toho pod kterou proměnnou máme jednotkový vektor (tu zařadíme do báze).

• Hodnoty bazických proměnných zjistíme v posledním sloupci tabulky (b - vektor pravých stran).

• Poslední řádek tabulky (indexní řádek – označený písmenkem Z)obsahuje anulovanou rovnici účelové funkce. Účelovou funkci vypočítáme skalárním součinem vektoru cen bazických proměnných (Cb) a vektoru pravých stran (b).

• Z tabulky tedy můžeme zjistit, jaké jsou bazické a nebazické proměnné, jejich hodnoty a ceny…

• Řešení můžeme alternativně zapsat pomocí vektoru bazického řešení