4EK311 — Operační výzkum

O předmětu

Operační výzkum (Operations Research) poskytuje matematické nástroje pro optimální rozhodování. Předmět pokrývá lineární programování, síťové modely, teorii her a rozhodování za nejistoty — vše s důrazem na praktické problémy a výpočtové postupy.

1. Lineární programování

Formulace LP úlohy

Standardní tvar: max (min) z = c₁x₁ + c₂x₂ + ... + cₙxₙ

za podmínek: a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁ ... aₘ₁x₁ + aₘ₂x₂ + ... + aₘₙxₙ ≤ bₘ xⱼ ≥ 0 pro všechna j

Maticový zápis: max cᵀx, s.t. Ax ≤ b, x ≥ 0

Grafická metoda (pro 2 proměnné)

Postup:

Nakresli přípustnou oblast (průnik všech omezení)
Najdi rohové (krajní) body mnohostěnu
Vyhodnoť účelovou funkci v každém rohovém bodě
Optimum je v rohovém bodě s nejvyšší (nejnižší) hodnotou

Příklad: max z = 5x₁ + 4x₂ 6x₁ + 4x₂ ≤ 24 x₁ + 2x₂ ≤ 6 x₁, x₂ ≥ 0

Rohové body: (0,0), (4,0), (3, 1.5), (0,3) z(0,0)=0, z(4,0)=20, z(3,1.5)=21, z(0,3)=12 Optimum: x₁=3, x₂=1.5, z=21

Simplexová metoda

Systematicky prochází rohové body přípustné oblasti zlepšováním účelové funkce.

Kanonický tvar (zavedení skluzových proměnných): 6x₁ + 4x₂ + s₁ = 24 x₁ + 2x₂ + s₂ = 6

Simplexová tabulka:

Báze | x₁   x₂   s₁  s₂ | b  | b/aᵢⱼ
-----|---------------------|-----|------
s₁   | 6    4    1   0  | 24  |  4   ← min ratio
s₂   | 1    2    0   1  |  6  |  6
-----|---------------------|-----|------
z    |-5   -4    0   0  |  0  |

Pivotní sloupec: nejzápornější koeficient v řádku z (x₁: -5) Pivotní řádek: min {b/aᵢⱼ} = min{24/6, 6/1} = 4 (s₁)

Po pivotizaci iterujeme, dokud v řádku z nejsou záporné hodnoty.

Analýza citlivosti

Rozsah RHS (pravé strany): O kolik lze měnit bᵢ, aniž se změní báze? Rozsah koeficientů účelové funkce: Kdy se nezmění optimální řešení? Duální cena (shadow price): O kolik se zlepší z při uvolnění omezení o 1 jednotku?

Zdroj    | Využití | Kapacita | Shadow price
---------|---------|----------|-------------
Stroj A  | 24      | 24       | 0.75 Kč/hod   ← vazné omezení
Stroj B  | 6       | 6        | 1.25 Kč/hod   ← vazné omezení
Stroj C  | 15      | 20       | 0              ← nevazné

Dualita v LP

Ke každé primární LP úloze existuje duální:

Primární: max cᵀx, Ax ≤ b, x ≥ 0
Duální: min bᵀy, Aᵀy ≥ c, y ≥ 0

Věta o dualitě: Primární max = Duální min (silná dualita) Komplementární skluzy: xⱼ(cⱼ - yᵀAⱼ) = 0 a yᵢ(bᵢ - Aᵢx) = 0

2. Dopravní a přiřazovací úlohy

Dopravní úloha

n zdrojů (nabídka sᵢ), m skladů (poptávka dⱼ), cena přepravy cᵢⱼ.

Podmínka rovnováhy: Σsᵢ = Σdⱼ (přidat fiktivní zdroj/sklad pokud ne)

Počáteční bázické řešení:

Metoda severozápadního rohu — jednoduché, ale drahé
Metoda nejnižší ceny — lepší startovní bod
Vogel–ova aproximační metoda — nejlepší aproximace optima

Optimalizace MODI metodou:

Vypočítej duální proměnné: uᵢ + vⱼ = cᵢⱼ pro bázické buňky
Hodnocení nebázických buněk: Δᵢⱼ = cᵢⱼ - uᵢ - vⱼ
Pokud všechna Δᵢⱼ ≥ 0 → optimum; jinak vstup záporné Δᵢⱼ do báze

Přiřazovací úloha

Speciální případ dopravní úlohy: n pracovníků × n úkolů, sᵢ = dⱼ = 1.

Maďarský algoritmus:

Odečti minimum řádku od každého řádku
Odečti minimum sloupce od každého sloupce
Pokryj nuly minimálním počtem čar
Pokud počet čar = n → optimum; jinak uprav matici

3. Síťová analýza

Kritická cesta — CPM (Critical Path Method)

Pro deterministické doby trvání aktivit.

Výpočet:

Nejdřívější začátek (ES): ES(j) = max{ES(i) + t(i,j)}
Nejdřívější konec (EF): EF = ES + t
Nejpozdější konec (LF): LF(i) = min{LF(j) - t(i,j)}
Nejpozdější začátek (LS): LS = LF - t
Celková rezerva (TF): TF = LF - EF = LS - ES
Kritická aktivita: TF = 0

Aktivita | t | ES | EF | LS | LF | TF
---------|---|----|----|----|----|----
A        | 3 |  0 |  3 |  0 |  3 |  0  ← kritická
B        | 5 |  0 |  5 |  2 |  7 |  2
C        | 4 |  3 |  7 |  3 |  7 |  0  ← kritická
D        | 2 |  5 |  7 |  5 |  7 |  0  ← kritická

PERT — Project Evaluation and Review Technique

Pro stochastické doby trvání: optimistická (a), nejpravděpodobnější (m), pesimistická (b).

Střední hodnota: E(t) = (a + 4m + b) / 6 Rozptyl: Var(t) = ((b - a) / 6)²

Délka projektu ~ N(ΣE(tᵢ), ΣVar(tᵢ)) pro kritické aktivity.

Pravděpodobnost dokončení do data T: z = (T - μ) / σ, pak P = Φ(z)

Problém nejkratší cesty — Dijkstrův algoritmus

Pro nezáporné ohodnocení hran.

Inicializace: d(s) = 0, d(v) = ∞ pro v ≠ s
Fronta: všechny uzly

while fronta není prázdná:
    u = uzel s min d(u) z fronty
    pro každého souseda v u:
        if d(u) + w(u,v) < d(v):
            d(v) = d(u) + w(u,v)
            předchůdce(v) = u

Maximální tok — Ford-Fulkerson

Řezy a tok:

Tok f(u,v) ≤ kapacita c(u,v)
Zachování toku v každém uzlu (kromě s a t)
Max-flow min-cut theorem: Max tok = Min řez

Postup: hledej augmentující cestu ze s do t v reziduálním grafu, zvyšuj tok.

4. Celočíselné programování (ILP)

Pokud musí být proměnné celé číslo. NP-těžký problém.

Metody:

Branch and Bound — rekurzivní větvení na podproblémy
Cutting Planes — přidávání Gomoryho řezů
Kombinace (B&B + cuts) — moderní solvery (CPLEX, Gurobi)

0-1 programování — binární proměnné pro logická rozhodnutí (knapsack, set covering).

5. Teorie hromadné obsluhy

M/M/1 fronta (Poissonovy příchody λ, exponenciální obsluha μ, 1 server):

Podmínka stability: ρ = λ/μ < 1 (intenzita provozu)
Průměrný počet zákazníků: L = ρ/(1-ρ)
Průměrná čekací doba: W = 1/(μ-λ)
Průměrný počet čekajících: Lq = ρ²/(1-ρ)
Průměrná čekací doba ve frontě: Wq = ρ/(μ-λ)

Littleův zákon: L = λ·W (platí obecně pro stabilní systémy)

M/M/s fronta — s serverů, stejné λ a μ. Výpočet přes Erlangův vzorec.

6. Rozhodování za nejistoty

Kritérium	Princip	Postoj k riziku
Maximax	max{max payoff}	Optimista
Maximin (Wald)	max{min payoff}	Pesimista
Hurwiczovo	max{α·max + (1-α)·min}	Střední (α = index optimismu)
Minimaxová lítost	min{max regret}	Neutralní
Bayesovo (Laplace)	max{průměr payoff}	Rovnoměrné pravděp.

Bayesovo rozhodování (s pravděpodobnostmi): EMV(aᵢ) = Σⱼ P(θⱼ) · V(aᵢ, θⱼ)

EVPI (Expected Value of Perfect Information): EVPI = E(max payoff | perfektní info) - max EMV

7. Teorie her

Nulové hry (zero-sum)

Výhra hráče 1 = prohra hráče 2. Reprezentovány maticí payoff.

Sedlový bod — řešení v čistých strategiích: Hráč 1 hraje strategii maximizující minimum řádku (maximin). Hráč 2 hraje strategii minimalizující maximum sloupce (minimax). Sedlový bod: max(min řádku) = min(max sloupce)

Smíšené strategie — pokud sedlový bod neexistuje: p* = (d-c) / (a-b-c+d) pro hru 2×2:

        Hráč 2
        L    P
Hráč 1 T [a, b]
       B [c, d]

Nashovo equilibrium

Profil strategií (s₁, s₂) je Nashovo equilibrium, pokud:

Hráč 1 nemůže zlepšit payoff změnou s₁ (za fixní s₂)
Hráč 2 nemůže zlepšit payoff změnou s₂ (za fixní s₁)

Vězňovo dilema:

            Mlčí      Přizná
Mlčí    (-1, -1)   (-10, 0)
Přizná  (0, -10)   (-6, -6)

NE: (Přizná, Přizná) = (-6,-6), přestože (Mlčí, Mlčí) = (-1,-1) je Paretovsky lepší.

Tipy pro zkoušku

Simplexová metoda: Trénovat výpočty ručně — pivotizace, tvorba tabulky. Zkouška typicky vyžaduje 2-3 iterace.
Analýza citlivosti: Shadow price = duální hodnota omezení. Znát interpretaci.
CPM/PERT: Nakreslit síťový diagram, spočítat ES/EF/LS/LF, identifikovat kritickou cestu. Pro PERT přidat výpočet pravděpodobnosti.
Teorie her: Hledat sedlový bod (max minimax = min maximin). Pokud neexistuje, použít smíšené strategie.
Rozhodovací kritéria: Umět aplikovat všech 5 kritérií na matici payoff. Poznat kdy použít která.
M/M/1: Pamatovat 4 základní vzorce (L, W, Lq, Wq). Littleův zákon L = λW.
Dopravní úloha: Počet bázických buněk = m+n-1. Pokud méně → degenerace.

Doporučené zdroje

Jablonský, J.: Operační výzkum (učebnice VŠE) — základní zdroj
Hillier, F. & Lieberman, G.: Introduction to Operations Research (anglická bible OR)
Excel Solver — praktické příklady LP a ILP
GLPK / PuLP (Python) — open-source solvery
Přednáškové materiály katedry ekonometrie FIS VŠE