Po částech konstantní funkce přes intervaly
Prerekvizity: [L1.4] big-M: disjunkce omezení (podmíněná omezení „pokud $y_k = 1$, pak…“) a [L0.8] Binární proměnná. V [L1.6] Fixed-charge funkce skočila jednou — v nule. Teď bude skákat víckrát: jako schody.
Cena, která skáče po schodech
Zkoušková klasika Wedding plan (svatební plán) obsahuje tuhle větu: „A price for renting a place differs, depending on the number of invited guests: for $[0,9]$ guests, the price is $p_1$ CZK, for $[10,19]$ guests, the price is $p_2$ CZK, and for $[20,n]$ guests the price is $p_3$ CZK.“
Označme $N$ počet pozvaných hostů. Cena za pronájem je piecewise constant function (po částech konstantní funkce) proměnné $N$:
$$f(N) = \begin{cases} p_1, & N \in [0, 9], \\ p_2, & N \in [10, 19], \\ p_3, & N \in [20, n]. \end{cases}$$Důležitý detail: $N$ není konstanta zadání — je to součet rozhodovacích proměnných ($N = \sum_i x_i$, kde $x_i = 1$ ⟺ host $i$ je pozvaný). Model tedy sám rozhoduje, na kterém „schodu“ skončí. Konkrétně pro $p_1 = 2$, $p_2 = 5$, $p_3 = 8$ (v tisících CZK) a $n = 30$:
Zkus sám: vyřeší to recept z [L1.6] — jeden přepínač $y$ a člen $A \cdot y$?
Ne. Fixed-charge funkce má jeden skok (v nule) a pak roste lineárně — jediný přepínač rozlišil dva režimy „nevyrábím / vyrábím“. Tady jsou tři konstantní úrovně a dva skoky: jedna binárka na to nestačí, režimy jsou tři. Ale jádro nápadu se přenáší: jeden binární přepínač na každý režim — tady na každý interval.
Krok 1: vyber právě jeden interval
Zkus sám: zaveď $y_1, y_2, y_3 \in \{0,1\}$ („interval $k$ je ten, ve kterém $N$ leží“). Jaké omezení vynutí, že je vybraný právě jeden interval?
$$y_1 + y_2 + y_3 = 1.$$
Intervaly $[0,9]$, $[10,19]$, $[20,n]$ jsou disjunktní a dohromady pokrývají všechna možná $N \in \{0, \dots, n\}$ — každé $N$ leží v právě jednom z nich. Rovnost (ne $\le$, ne $\ge$!) tedy přesně odpovídá realitě a model kvůli ní nikdy není nepřípustný. Stejný trik jsi viděl v miniatuře u [L1.6], úloha T01 (výčet hodnot rozdílu) — teď ho povyšujeme na obecný vzorec.
Krok 2: svaž $N$ s vybraným intervalem
Zatím $y_k$ s $N$ nijak nesouvisí — solver by si vybral nejlevnější interval bez ohledu na skutečný počet hostů. Potřebujeme podmíněné omezení: pokud $y_2 = 1$, pak $10 \le N \le 19$.
Zkus sám: „pokud $y_2 = 1$, pak $N \ge 10$ a $N \le 19$“ — jak se podmíněné omezení píše lineárně? (Nápověda: [L1.4].)
Big-M relaxace, která se vypne při $y_2 = 0$:
$$N \ge 10 - M(1 - y_2), \qquad N \le 19 + M(1 - y_2).$$Pro $y_2 = 1$ zbude $10 \le N \le 19$; pro $y_2 = 0$ se obě nerovnosti uvolní na vždy-pravdivé ($N \ge 10 - M$ a $N \le 19 + M$). Pozor na směry z [L1.4]: dolní mez ($\ge$) se uvolňuje odečtením $M$, horní mez ($\le$) přičtením $M$. Protože $0 \le N \le n$, stačí $M = n$.
Stejně pro zbylé intervaly (triviální meze $N \ge 0$ a $N \le n$ lze vynechat):
$$N \le 9 + M(1 - y_1), \qquad N \ge 20 - M(1 - y_3).$$Existuje i kompaktnější zápis. Protože platí $\sum_k y_k = 1$, je vždy aktivní právě jedna sada mezí — a meze tedy můžeme vyjmenovat v jediné nerovnosti (stejný princip jako výčet hodnot na slidu 36 přednášky ILP):
$$N \;\le\; 9\,y_1 + 19\,y_2 + n\,y_3, \qquad N \;\ge\; 0\,y_1 + 10\,y_2 + 20\,y_3.$$Zkus sám: ověř, že kompaktní zápis dělá totéž. Co říká pro $y_2 = 1$? A proč by se rozbil bez $\sum_k y_k = 1$?
Pro $y_2 = 1$ (a tedy $y_1 = y_3 = 0$) zbude přesně $10 \le N \le 19$. Pro $y_1 = 1$ zbude $0 \le N \le 9$, pro $y_3 = 1$ zbude $20 \le N \le n$. ✓
Bez $\sum_k y_k = 1$ by ale solver mohl nastavit třeba $y_1 = y_3 = 1$ (pak $N \le 9 + n$ — mez v háji) nebo všechna $y_k = 0$ (pak $N \le 0$, což u maximalizace hostů model nesmyslně zaškrtí, a hlavně cena vyjde $0$). Rovnost „právě jeden“ je nosný pilíř celé konstrukce — kompaktní zápis je zkratka platná jen díky ní.
Krok 3: cena vybraného intervalu
Zkus sám: jak teď zapíšeš cenu pronájmu jediným lineárním výrazem?
$$\text{cena} = p_1\,y_1 + p_2\,y_2 + p_3\,y_3 = \sum_k p_k\,y_k.$$
Právě jedno $y_k$ je $1$, ostatní $0$ — součet tedy „vytáhne“ přesně cenu vybraného intervalu. Žádné násobení proměnných, čistě lineární výraz, který můžeš dát do kritéria nebo do rozpočtového omezení: ve Wedding plan např. $m \cdot N + \sum_k p_k y_k \le B$.
Souhrnně — recept na po částech konstantní funkci přes $K$ intervalů $[l_k, u_k]$ s cenami $p_k$:
$$\begin{aligned} & y_k \in \{0,1\} \quad (k = 1..K), \qquad \sum_{k=1}^{K} y_k = 1 \\ & l_k - M(1 - y_k) \;\le\; N \;\le\; u_k + M(1 - y_k) \quad \forall k \qquad \text{(nebo kompaktně } \textstyle\sum_k l_k y_k \le N \le \sum_k u_k y_k\text{)} \\ & \text{cena} = \sum_{k=1}^{K} p_k\,y_k \end{aligned}$$
Kde se u zkoušky ztrácí body- Zapomenuté $\sum_k y_k = 1$: solver vypne všechna $y_k$ a platí cenu $0$ (nebo zapne víc intervalů najednou — v kompaktním zápisu se pak meze rozpadnou, v big-M tvaru se naopak zkombinují neslučitelné meze). Cena v kritériu sama žádný výběr nevynutí.
- Jen jedna mez na interval: každý vnitřní interval potřebuje OBĚ nerovnosti (dolní i horní). V dochovaném řešení z termínu 21.06.2021 hodnotitel strhl 2 body s poznámkou, že (pokud to dobře chápe) třetí cenový případ není shora omezený — meze nebyly svázané úplně.
- Špatný směr relaxace: $\ge$ se uvolňuje členem $-M(1-y_k)$, $\le$ členem $+M(1-y_k)$. Prohozený směr omezení naopak zpřísní (srov. [L1.4]).
Takhle vypadá množina dvojic (počet, cena), kterou správný model nabízí — a co se stane, když $\sum_k y_k = 1$ vypadne:
Key takeaways — L1.7- Po částech konstantní cena přes intervaly: pro každý interval binární $y_k$ a $\sum_k y_k = 1$ (vybírám právě jeden interval; intervaly jsou disjunktní a pokrývají vše, takže rovnost je vždy splnitelná).
- Vazba počtu na interval přes big-M [L1.4]: $l_k - M(1-y_k) \le N \le u_k + M(1-y_k)$, kde $M = n$ (rozsah $N$) stačí. Každý interval potřebuje obě meze.
- Kompaktní alternativa (platná jen díky $\sum_k y_k = 1$): $\sum_k l_k y_k \le N \le \sum_k u_k y_k$ — výčet mezí, srov. slide 36 přednášky ILP.
- Cena $= \sum_k p_k\,y_k$ — lineární výraz, který jde do kritéria i do rozpočtu (např. $m N + \sum_k p_k y_k \le B$ ve Wedding plan).
“Labor demand, material demand and income per piece are:
| product | T-shirt | shirt | robe | capacity | unit cost [CZK] |
|---|---|---|---|---|---|
| labor [person-hour] | 3 | 2 | 6 | 160 | 1000 |
| material [meter] | 4 | 3 | 4 | 130 | 200 |
| income [1000 CZK] | 9.8 | 6.6 | 13.8 |
Goal is to maximize the profit (i.e. total income minus total expenses). Constraints: material capacity is 130 meters. Another constraint: Total amount of work per week can be at most 40 or 80 or 120 or 160 hours depending on the number of Full Time Employees (FTEs). Criterion adaptation: labor cost is proportional to the number of FTEs (one FTE costs 40). We only want some values of person-hours to be available:
$$3x_1 + 2x_2 + 6x_3 \le \text{ either } 40 \text{ or } 80 \text{ or } 120 \text{ or } 160$$Pozn.: text je sestavený ze slidů 33–36; původní omezení ze slidu 33 „labor is on demand with maximum capacity of 160 person-hours“ slide 36 nahrazuje FTE variantou výše.
a) Co je v zadání?
Výroba tří produktů ($x_i$ = počet kusů produktu $i$) s materiálovou kapacitou. Pracovní kapacita ale není pevná: firma najímá 1–4 zaměstnance na plný úvazek (FTE) a kapacita hodin je $40 \cdot (\text{počet FTE})$ — tedy jedna ze čtyř hodnot $\{40, 80, 120, 160\}$. Mzdový náklad je úměrný počtu FTE (jeden FTE stojí 40, v tisících CZK). Místo intervalů tu vybíráme jednu z konečně mnoha hodnot meze — stejná konstrukce, jen se „interval“ smrskl na bod.
b) Co k tomu budeme potřebovat?
- Tato lekce — výběr právě jedné varianty přes $\sum_k v_k = 1$ a výčet hodnot $\sum_k u_k v_k$.
- [L1.1] Cílová funkce a základní omezení — kritérium a kapacity.
- [L0.8] Binární proměnná.
c) Jak nad úlohou uvažovat?
Kolik „režimů“ má pracovní kapacita? Zaveď pro každý binárku $v_k$. Jak vypadá pravá strana omezení na osobohodiny, když má být rovna vybrané hodnotě (výčet hodnot — krok 2 této lekce v kompaktním tvaru; dolní mez tu netřeba, proč?)? A jak se náklad na FTE dostane do kritéria (krok 3)? Zisk na kus si spočti jako příjem − materiálové náklady na kus (mzdy už platíš přes FTE, ne za osobohodinu: materiál 200 CZK/m, tedy $0.8$, $0.6$, $0.8$ tisíc CZK na kus).
d) Úplné řešení
Binární přepínače variant $v_1, \dots, v_4 \in \{0,1\}$ ($v_k = 1$ ⟺ firma má $k$ FTE). Formulace ze slidu 36:
$$\begin{aligned} \max z = \quad & (9.8 - 0.8)x_1 + (6.6 - 0.6)x_2 + (13.8 - 0.8)x_3 - 40v_1 - 80v_2 - 120v_3 - 160v_4 \\ \text{s.t.} \quad & 3x_1 + 2x_2 + 6x_3 \le 40v_1 + 80v_2 + 120v_3 + 160v_4 \\ & \sum_{k=1}^{4} v_k = 1 \\ & 4x_1 + 3x_2 + 4x_3 \le 130 \\ & x_i \in \mathbb{Z}_0^+, \;\; v_k \in \{0,1\} \end{aligned}$$Komentáře:
- Pravá strana $40v_1 + \dots + 160v_4$ s $\sum v_k = 1$ je přesně „výčet hodnot“: vybraná varianta dosadí svou kapacitu. Dolní mez netřeba — osobohodiny jsou výraz $3x_1+2x_2+6x_3 \ge 0$ a omezujeme je jen shora.
- Náklad na FTE v kritériu je $\sum_k (40k) v_k$ — po částech konstantní funkce počtu FTE, krok 3 této lekce.
- Poznámka ze slidu: protože je mzdový náklad úměrný počtu FTE, šlo by alternativně použít jedinou celočíselnou proměnnou $v \in \{1,2,3,4\}$ (počet FTE): $3x_1+2x_2+6x_3 \le 40v$, kritérium $\dots - 40v$. To ale funguje JEN když jsou hodnoty v aritmetické řadě a cena úměrná — obecné ceny $p_k$ vyžadují binární výčet.
“You are planning a wedding. There is a set of potential guests $G = \{g_1, g_2, \ldots, g_n\}$. You want to invite as many guests as possible; however, there are some constraints. A meal for a single guest costs $m$ CZK (Czech koruna). A price for renting a place differs, depending on the number of invited guests: for $[0, 9]$ guests, the price is $p_1$ CZK, for $[10, 19]$ guests, the price is $p_2$ CZK, and for $[20, n]$ guests the price is $p_3$ CZK. You have a $B$ CZK; this budget cannot be exceeded. Furthermore, for the sake of justice, the number of guests invited from the groom's side and the bride's side can differ by at most $D_{max}$. Assume functions $br : G \to \{0, 1\}$ and $gr : G \to \{0, 1\}$, where $br(g_i) = 1$ iff $g_i$ is from the bride's side, and $gr(g_i) = 1$ iff $g_i$ is from the groom's side. (Note that there might be some guest $g_i$ such that $br(g_i) = gr(g_i) = 1$.)
Design an ILP model deciding which guests will be invited while respecting all the constraints.”
a) Co je v zadání?
Tohle je ostrá zkoušková úloha za 7 bodů (25.05.2026; padla i 21.06.2021, tehdy za 6). Kompletně ji složíš ve [L1.9] Wedding plan [FOTO] — tady trénujeme jen její jádro: pronájem podle intervalu + rozpočet. Tedy: binárky $x_i$ „host $i$ pozván“, počet hostů $N = \sum_i x_i$, cena pronájmu po částech konstantní ($p_1/p_2/p_3$ dle intervalu pro $N$), jídlo $m$ za hosta, vše dohromady max. $B$. Podmínku $D_{max}$ (rozdíl stran) zatím vynech — na tu je [L1.8].
b) Co k tomu budeme potřebovat?
- Tato lekce — $y_1, y_2, y_3$, $\sum_k y_k = 1$, meze intervalů, cena $\sum_k p_k y_k$.
- [L1.4] big-M: disjunkce omezení — podmíněné meze.
- [L1.1] Cílová funkce a základní omezení — rozpočet $\le B$.
c) Jak nad úlohou uvažovat?
Co je kritérium („as many guests as possible“)? Čemu se rovná $N$ a proč je to lineární výraz? Které tři binárky přidáš a jaké omezení je drží pohromadě? Napiš meze intervalů — big-M tvarem, nebo kompaktně výčtem; jaké $M$ stačí, když $N \le n$? Nakonec rozpočet: co všechno se platí a kde se v něm objeví cena pronájmu?
d) Úplné řešení (část: pronájem + rozpočet)
Proměnné: $x_i \in \{0,1\}$ ($x_i = 1$ ⟺ host $g_i$ pozván), $y_1, y_2, y_3 \in \{0,1\}$ (vybraný cenový interval). Označme $N = \sum_{i=1}^{n} x_i$ (jen zkratka za lineární výraz, ne nová proměnná).
$$\begin{aligned} \max \quad & \sum_{i=1}^{n} x_i \\ \text{s.t.} \quad & y_1 + y_2 + y_3 = 1 \\ & N \le 9 + n(1 - y_1) \\ & N \ge 10 - n(1 - y_2), \qquad N \le 19 + n(1 - y_2) \\ & N \ge 20 - n(1 - y_3) \\ & m \cdot N + p_1 y_1 + p_2 y_2 + p_3 y_3 \;\le\; B \\ & x_i \in \{0,1\} \;\; \forall i, \qquad y_k \in \{0,1\} \;\; \forall k \end{aligned}$$Komentáře:
- $M = n$ stačí: $N$ nikdy nepřekročí $n$ ani neklesne pod $0$, takže uvolněná mez (např. $N \ge 10 - n$) je vždy pravdivá. Meze $N \ge 0$ (interval 1) a $N \le n$ (interval 3) platí automaticky, psát je netřeba.
- Kompaktní alternativa vazeb: $10y_2 + 20y_3 \le N \le 9y_1 + 19y_2 + n\,y_3$ — díky $\sum_k y_k = 1$ ekvivalentní.
- Rozpočet: jídlo $m$ za každého pozvaného ($m \cdot N$) plus cena pronájmu vybraného intervalu ($\sum_k p_k y_k$). Pronájem se NEnásobí počtem hostů!
- Poučení z reálné zkoušky (21.06.2021): dochované studentské řešení použilo obrácený význam přepínačů ($Y_k = 1$ ⟺ interval $k$ nevybrán, tedy $Y_1 + Y_2 + Y_3 = 2$ a v rozpočtu $(1-Y_k)\,p_k$) — to je legální ekvivalent, ale snadno se v něm chybuje: hodnotitel strhl 2 body za neúplně svázané meze (s poznámkou, že třetí cenový případ zřejmě není shora omezený). Drž se přímého významu $y_k = 1$ ⟺ vybráno a zkontroluj, že každý interval má obě meze.
- Zbývající podmínka $|{\sum_i gr(g_i) x_i - \sum_i br(g_i) x_i}| \le D_{max}$ přijde v [L1.8]; celý model složíš v [L1.9].