Teorie-emm ke zkoušce

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?

• do omezujících podmínek typu nerovnice přidáme doplňkové proměnné

• doplňkové proměnné značíme d s indexem omezující podmínky (zjištění ke které omezující podmínce se doplňková proměnná vztahuje)

• pravidla

  • pokud se jedná o kapacitní proměnnou <= přičteme d

  • pokud se jedná o požadavkovou proměnnou >= odečteme d

• doplňková proměnná = „rezerva“

<= +d zbytek do vyčerpání

>= -d překročení požadavku chceme je nezáporné, mají nulovou sazbu

= p (pomocná proměnná)

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?

• přidání pomocných proměnných (p)

• děláme to proto, abychom měli jednotkovou submatici

• pomocné proměnné

  • označíme prohibitivní sazbou (nejvíc nevýhodná)

  • požadujeme nezápornost

• přidáme do

  • požadavkových podmínek

  • typu určení

  • vždy kladné

• udává, kolik jednotek zbývá do splnění omezení

• pokud má v řešení + hodnotu je to nepřípustné

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.

x……………………… strukturní – hodnota

d…………………….. doplňkové – interpret. – rezerva, která zbývá do vyčerpání omezujících podmínek <=,

překročení požadavku >=

p…………………….. pomocné – interpret. – kolik jednotek zbývá do splnění omezení > řešení s kladnou

hodnotou p je 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í.

1. kapacitní <=

   1. mám určitou kapacitu a tu nesmím překročit

   2. př.: místo ve skladu

2. požadavkové >=

   1. mám požadavek, že minimálně musím vyrobit tolik a tolik

   2. př.: každá plodina výsevu na min ha

3. určení =

   1. mám právě tolik a tolik jednotek

   2. př.: mám tolik tun zrn a víc ani ťuk

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

XB = výpis bazických proměnných

CB = cena bazických proměnných

C1, 2 = ceny proměnných

b = sloupec pravých stran

omega = test přípustnosti

zj – cj = test optima

x1 = strukturní proměnné

d = doplňkové proměnné

p = pomocné proměnné

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

• zkoumá, zda existuje lepší bazické řešení s lepší hodnotou účelové funkce

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

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

• zj – cj <= 0 minimalizace

  • v zj – cj hledám nejvíc kladná, účelová funkce se mi snižuje

• zj – cj >= 0 maximalizace

  • v zj – cj hledám nejvíc záporná, účelová funkce se mi zvyšuje