Oficiální sylabus předmětu: Lineární programování (Bílá kniha)

Požadavky

• Zápočet: Udělen za splněnou docházku a úspěšné vyřešení zápočtového testu.
  • Detaily doplněny na cvičení.
  • Pokyny k vypracování úlohy
• Zkouška: Teoretická a praktická část vybraná z obsahu probraného na přednáškách.
  • Zkouška je realizována písemnou formou – skládá se ze 2 teoretických a 1 praktické otázky z níže dostupného seznamu.
  • Zkoušku lze skládat pouze se získaným zápočtem.
  • Na termíny zkoušek se přihlašujte v systému KOS.
  • Seznam otázek ke zkoušce

Osnova přednášek

V průběhu semestru budou postupně doplňovány studijní texty a otázky k jednotlivým přednáškám. Texty nicméně vznikají průběžně a mohou se v nich tak přirozeně objevovat překlepy, chyby, atd. Budu moc rád, když mi jakékoliv takové nedostatky ohlásíte! 🙂

Dále platí, že již některé nahrané texty a otázky bude možná někdy potřeba modifikovat — v případě zásadních změn vás o tom samozřejmě včas informuji.
- 16.12.2025: úprava důkazu první implikace ve větě 3.2

1. Formulace úlohy lineárního programování, převody omezení, příklady úloh.
   Předpokládané datum: 23/09/2025 Studijní text k přednášce 1 (PDF)
2. Vlastnosti úloh lineárního programování, množina přípustných a optimálních řešení a jejich vlastnosti, geometrie úloh LP.
   Předpokládané datum: 30/09/2025 Studijní text k přednášce 2 (PDF)
3. Základní věta LP, grafické řešení úloh LP.
   Předpokládané datum: 07/10/2025 Studijní text k přednášce 3 (PDF)
4. Simplexový algoritmus — jednofázová metoda, neomezenost úlohy, více optimálních řešení.
   Předpokládané datum: 14/10/2025 Studijní text k přednášce 4 (PDF)
5. Simplexový algoritmus — dvoufázová metoda (technika pomocné báze), M‑úloha.
   Předpokládané datum: 21/10/2025 Studijní text k přednášce 5 (PDF)
6. Vlastnosti simplexové metody — degenerace, cyklení, časová náročnost algoritmu.
   Předpokládané datum: 04/11/2025 Studijní text k přednášce 6 (PDF)
7. Dualita úloh lineárního programování — formulace duální úlohy, věty o dualitě.
   Předpokládané datum: 11/11/2025 Studijní text k přednášce 7 (PDF)
8. Algoritmus duálně‑simplexové metody.
   Předpokládané datum: 18/11/2025 Studijní text k přednášce 8 (PDF)
9. Dopravní problém — metoda MODI.
   Předpokládané datum: 25/11/2025 Studijní text k přednášce 9 (PDF)
10. Aplikace v teorii her — maticové hry s nulovým součtem, smíšené strategie, min‑max teorém.
    Předpokládané datum: 02/12/2025 Studijní text k přednášce 10 (PDF)
11. Algoritmy celočíselného programování — typické úlohy LIP, metoda větví a mezí.
    Předpokládané datum: 09/12/2025 Studijní text k přednášce 11 a 12 (PDF)
12. Algoritmy celočíselného programování — Gomoryho řezy.
    Předpokládané datum: 16/12/2025Studijní text k přednášce 11 a 12 (PDF)

Osnova cvičení

1. Řešení úloh LP na počítači — softwarové nástroje a jejich použití.
   Předpokládané datum: 03/10/2025 Úlohy ke cvičení 1 Text k úlohám
2. Úloha lineárního programování, podmínka optimality a neomezenost.
   Předpokládané datum: 17/10/2025 Úlohy ke cvičení 2
3. Simplexová metoda — základní kroky algoritmu, různé situace při řešení; dvoufázová simplexová metoda (technika pomocné báze, M‑úloha); duální simplexová metoda.
   Předpokládané datum: 31/10/2025
4. Příklad z teorie her — hledání smíšených strategií.
   Předpokládané datum: 14/11/2025 Text a úloha ke cvičení
5. Gomoryho algoritmus a další algoritmy LIP (metoda větví a mezí).
   Předpokládané datum: 28/11/2025 Úlohy ke cvičení 5
6. Kvadratické programování.
   Předpokládané datum: 12/12/2025