01LIP – Lineární programování

Akademický rok 2026/27, 2+1 z, zk; 3 kredity
  • Přednášky: pátek 9:00–10:40, T-301
  • Cvičení: vybrané pátky 11:00–11:50, T-115

For the English version of the course, scroll down or jump to the English section.

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

Termíny výuky

Pátky v zimním semestru 2026/27
Datum2026Přednáška9:00–10:40T-301Probraná témataStudijní textCvičení11:00–11:50T-115
25. 9.P1Formulace LP, přípustné a optimální řešení, převody mezi tvary.§ 1.1, § 1.2—
2. 10.P2Konvexita, mnohostěny, báze a bázická přípustná řešení.Kap. 2C1
9. 10.P3Bázická přípustná řešení, degenerace a základní věta LP.§ 2.2, § 3.1—
16. 10.P4Opakování bázických přípustných řešení a degenerace; grafické řešení úloh.§ 2.2, § 3.2C2
23. 10.Výuka zrušena
30. 10.P5Simplexové tabulky, pivotování, optimalita, neomezenost a více optimálních řešení.Kap. 4C3
6. 11.P6Výchozí přípustná báze, metoda velkého M, dvoufázová metoda, nepřípustnost a nadbytečná omezení.Kap. 5C4
13. 11.P7—
20. 11.P8—
27. 11.P9C5
4. 12.P10C6
11. 12.P11C7
18. 12.P12C8
Celkem12 přednášek8 cvičení

Požadavky

  • Zápočet: Udělen za samostatné vypracování zápočtového projektu a krátkou individuální obhajobu.
    • Účast na cvičení je nepovinná. Samostatný zápočtový test se nekoná.
    • Cílem projektu je sestavit, vyřešit a ověřit model lineárního nebo smíšeného celočíselného programování (LP/MILP). Lze odevzdat komentovaný Jupyter notebook s uloženými výsledky nebo stručný PDF dokument a kód či editovatelný výpočetní soubor.
    • Podrobné požadavky stanovují platné pokyny: Pokyny k vypracování úlohy
    • Deadline odevzdání je 14. 5. 2027.
  • 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.
    • Přihlásit se na zkoušku můžete i bez zápočtu v systému KOS, před skládáním zkoušky je však nutné formálně odevzdat zápočtový program, tj. zaslat přednášejícímu svou práci alespoň 1 den před termínem zkoušky + absolvovat krátkou konzultaci k programu (konzultace lze individuálně domluvit i na den zkouškového termínu).
    • Na termíny zkoušek se přihlašujte v systému KOS.
    • Zkoušku bude možné v omezené kapacitě skládat i během LS / v letním zkouškovém období (pro tuto variantu kontaktujte přednášejícího).
    • Seznam otázek ke zkoušce

Osnova přednášek

K předmětu je k dispozici ucelený studijní text.

Studijní text k předmětu (01LIP.pdf)

  1. Formulace úlohy lineárního programování, převody omezení, příklady úloh.
  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.
  3. Základní věta LP, grafické řešení úloh LP.
  4. Simplexový algoritmus — jednofázová metoda, neomezenost úlohy, více optimálních řešení.
  5. Simplexový algoritmus — dvoufázová metoda (technika pomocné báze), M‑úloha.
  6. Vlastnosti simplexové metody — degenerace, cyklení, časová náročnost algoritmu.
  7. Dualita úloh lineárního programování — formulace duální úlohy, věty o dualitě.
  8. Algoritmus duálně‑simplexové metody.
  9. Dopravní problém — metoda MODI.
  10. Aplikace v teorii her — maticové hry s nulovým součtem, smíšené strategie, min‑max teorém.
  11. Algoritmy celočíselného programování — typické úlohy LIP, metoda větví a mezí.
  12. Algoritmy celočíselného programování — Gomoryho řezy.

Osnova cvičení

  1. Formulace lineárního programu a první výpočet.
  2. První model v PuLP, čtení výsledků a varianty LP a MILP.
  3. Rozhodnutí ano/ne a logické vazby: binární proměnné, nejvýše jedna a právě jedna možnost, podmíněný výběr. Domácí úkol: výrobní model, kontrola řešení a změna kapacity.
  4. Maximální tok v síti dep, třídění zásilek a proložení přímky.
  5. Dopravní problém a kontrola přepravního plánu.
  6. Plánování výroby a zásob ve více obdobích.
  7. Celočíselné programování, LP-relaxace a metoda větví a mezí.
  8. Tři vzorové projekty: baterie, datová síť a kalibrace.

01YLIP – Linear Programming

Academic year 2026/27, 2+1, course credit and examination; 3 ECTS credits

Official course syllabus: Linear Programming (White Book)

Requirements

  • Course credit: Awarded for an independently completed course project and a short individual oral defense.
    • Exercise attendance is optional. There is no separate course-credit test.
    • The project aims to formulate, solve, and validate a linear or mixed-integer linear programming model (LP/MILP). Submit an annotated Jupyter notebook with saved results or a short PDF document together with code or an editable computational file.
    • The current guidelines specify the detailed requirements: Course project guidelines
    • The submission deadline is 14 May 2027.
  • Examination: Theoretical and practical material covered in the lectures.
    • The examination is written and consists of 2 theoretical questions and 1 practical problem from the list available below.
    • Course credit is required before taking the examination.
    • You may register for an examination date before your course credit is recorded in KOS. Before taking the examination, however, you must formally submit your course project by sending it to the lecturer at least 1 day before the examination date and attend a short consultation about the project (a consultation on the examination day itself may be arranged individually).
    • Register for examination dates in KOS.
    • A limited number of examination places will also be available during the summer semester / summer examination period (contact the lecturer if you wish to use this option).
    • List of examination questions

Lecture outline

A complete set of lecture notes is available for the course.

Course lecture notes (01LIP-en.pdf)

  1. Formulating linear programming problems, converting constraints, and examples.
  2. Properties of linear programming problems: feasible and optimal solution sets, their properties, and the geometry of LP.
  3. The fundamental theorem of LP and graphical solution methods.
  4. The simplex algorithm — the one-phase method, unboundedness, and multiple optimal solutions.
  5. The simplex algorithm — the two-phase method (auxiliary basis technique) and the big-M method.
  6. Properties of the simplex method — degeneracy, cycling, and computational complexity.
  7. Linear programming duality — formulating the dual problem and duality theorems.
  8. The dual simplex algorithm.
  9. The transportation problem — the MODI method.
  10. Applications to game theory — zero-sum matrix games, mixed strategies, and the minimax theorem.
  11. Integer programming algorithms — typical integer programming problems and branch and bound.
  12. Integer programming algorithms — Gomory cuts.

Exercise outline

  1. Formulating a linear program and solving a first example.
  2. A first model in PuLP, interpreting results and exploring LP and MILP variants.
  3. Yes/no decisions and logical constraints: binary variables, at most one and exactly one option, conditional selection. Homework: a production model, solution checks, and a capacity change.
  4. Maximum flow in a depot network, parcel sorting and line fitting.
  5. The transportation problem and checking a shipment plan.
  6. Production and inventory planning over several periods.
  7. Integer programming, LP relaxation and branch and bound.
  8. Three sample projects: battery operation, a data network and calibration.