L1.9 Kapitola K1 — ILP modelování (Slot 1) · [MUST]

VYVRCHOLENÍ: Wedding plan [FOTO]

Jedna nová věc Složení všech dosavadních ILP technik do jedné kompletní zkouškové odpovědi: rozpočet [L1.1] + krokový pronájem dle intervalu [L1.7] + omezení rozdílu stran [L1.8] — a zápis ve formátu, za který hodnotitel dává plný počet bodů.

Prerekvizity: [L1.1], [L1.7], [L1.8]. Wedding plan je ostrá zkoušková úloha: padla 21.06.2021 (za 6 bodů), v roce 2023 a 25.05.2026 (za 7 bodů) — v predikovaném slotu 1, který padá ve 100 % termínů. Všechny díly už znáš; dnes je poprvé poskládáš dohromady sám, od prázdného papíru po kompletní model.

Krok 0: rozeber zadání na věty

Zkouškové zadání (celé přesně v úloze T01 níže) je jeden hutný odstavec. První dovednost: rozsekat ho na věty a ke každé říct, kterou techniku vyžaduje. Teprve pak se píší proměnné a omezení.

Zkus sám: projdi si zadání v T01 a ke každé větě přiřaď lekci, která ji řeší. Kolik „stavebních dílů“ napočítáš?
  • „You want to invite as many guests as possible“ → kritérium: maximalizace počtu pozvaných — [L1.1] + binárky „host pozván“ [L0.8].
  • „A meal for a single guest costs $m$ CZK“ + „You have a $B$ CZK; this budget cannot be exceeded“ → rozpočtové omezení $\dots \le B$ — [L1.1].
  • „A price for renting a place differs, depending on the number of invited guests: …$p_1$ / $p_2$ / $p_3$“ → po částech konstantní cena přes intervaly $[0,9]$, $[10,19]$, $[20,n]$ — přepínače $y_k$, $\sum_k y_k = 1$, big-M meze — [L1.7].
  • „…the number of guests invited from the groom's side and the bride's side can differ by at most $D_{max}$“ → $|a-b| \le D_{max}$ jako dvě lineární nerovnosti — [L1.8].

Čtyři díly — a žádný z nich není nový. Celé „vyvrcholení“ je o disciplíně skládání.

Krok 1: proměnné

Zkus sám: jaké rozhodovací proměnné model potřebuje? (Méně, než si možná myslíš.)

Jen dvě sady:

  • $x_i \in \{0,1\}$ pro $i \in 1..n$ — $x_i = 1$ ⟺ host $g_i$ je pozvaný (jádro rozhodnutí „which guests will be invited“),
  • $y_1, y_2, y_3 \in \{0,1\}$ — $y_k = 1$ ⟺ počet hostů padne do $k$-tého cenového intervalu [L1.7].

Počet hostů $N = \sum_{i=1}^{n} x_i$ je jen zkratka za lineární výraz, ne nová proměnná. Funkce $br$, $gr$, čísla $m, p_1, p_2, p_3, B, D_{max}, n$ jsou parametry zadání — solver o nich nerozhoduje. Toto rozlišení v odpovědi explicitně uveď (sekce „parameters“ vs. „variables“); hodnotitel za ni dává body.

Krok 2: omezení — díl po dílu

Zkus sám: napiš blok „pronájem podle intervalu“ — výběr intervalu, vazby na $N$, jaké $M$ stačí?

Recept z [L1.7] beze změny ($M = n$ stačí, protože $0 \le N \le n$; triviální meze $N \ge 0$ a $N \le n$ netřeba psát):

$$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)$$

Zkontroluj, že žádnému intervalu nechybí netriviální mez — za neomezený třetí cenový případ se na termínu 21.06.2021 strhávaly 2 body (ve studentově formulaci nebyla jeho horní mez triviální).

Zkus sám: napiš rozpočtové omezení. Co všechno se platí — a čím se NEnásobí pronájem?

Platí se jídlo $m$ za každého pozvaného hosta a cena pronájmu vybraného intervalu:

$$m \sum_{i=1}^{n} x_i \;+\; p_1 y_1 + p_2 y_2 + p_3 y_3 \;\le\; B.$$

Pronájem je za místo, ne za hlavu — nenásobí se počtem hostů. A díky $\sum_k y_k = 1$ se z $\sum_k p_k y_k$ „vytáhne“ přesně jedna cena.

Zkus sám: napiš podmínku spravedlnosti („differ by at most $D_{max}$“). Kolik nerovností potřebuješ?

Počty pozvaných z obou stran jsou lineární výrazy $\sum_i gr(g_i)\,x_i$ a $\sum_i br(g_i)\,x_i$. Podmínka $|a - b| \le D_{max}$ = dvě nerovnosti [L1.8]:

$$\sum_{i=1}^{n} gr(g_i)\,x_i - \sum_{i=1}^{n} br(g_i)\,x_i \;\le\; D_{max}$$ $$\sum_{i=1}^{n} br(g_i)\,x_i - \sum_{i=1}^{n} gr(g_i)\,x_i \;\le\; D_{max}$$

Jedna nerovnost nestačí — hlídala by jen jeden směr převahy. V dochovaném ohodnoceném řešení hodnotitel přeškrtl první pokus, kde student omylem obě sumy sečetl (plus místo minus); správně je rozdíl, oběma směry.

Zkus sám: zadání upozorňuje, že může existovat host s $br(g_i) = gr(g_i) = 1$ (patří k oběma stranám). Nerozbije takový host podmínku $D_{max}$?

Nerozbije — a právě proto je konstrukce přes rozdíl sum elegantní. Pozvaný host s $br(g_i) = gr(g_i) = 1$ přičte $x_i = 1$ do obou sum, takže v rozdílu $\sum gr\,x - \sum br\,x$ se vyruší. „Společný“ host nenaklání váhy na žádnou stranu, což přesně odpovídá smyslu spravedlnosti v zadání. (V kritériu se samozřejmě počítá jen jednou — je to jeden host $x_i$.) Tahle poznámka v závorce je v zadání schválně: testuje, jestli si model nezačneš zbytečně komplikovat, např. rozdělováním hosta na půlky.

Jak model „šlape“: rozpočet vs. počet hostů

Intuice celého modelu na konkrétních číslech ($m = 1$, $p_1 = 2$, $p_2 = 5$, $p_3 = 8$ — vše v tisících CZK, $n = 30$): celkové výdaje jsou $m \cdot N + p_k$ a kritérium tlačí $N$ doprava, dokud výdaje nenarazí na rozpočet $B$.

Zkus sám: v obrázku je $B = 20$. Proč optimum není na konci druhého schodu ($N = 19$)? A co by se stalo pro $B = 13$?

Na druhém schodu stojí $N$ hostů $N + 5$; rozpočet $20$ dovolí nejvýš $N = 15$ (výdaje $20 \le 20$), pro $N = 16$ už $21 > 20$. Optimum tedy uvázne uvnitř intervalu — meze intervalu a rozpočet se o $N$ přetahují a model to vybalancuje sám.

Pro $B = 13$: druhý schod začíná výdaji $10 + 5 = 15 > 13$, takže interval 2 je celý nedostupný a optimum je $N = 9$ za $9 + 2 = 11$ — konec prvního schodu. Všimni si „díry“: hostů 10–13 se nedočkáš, i kdyby na jídlo zbývalo, protože skokem na druhý schod zdraží pronájem. Přesně tohle chování po částech konstantní ceny model přes $y_k$ věrně kopíruje.

Krok 3: zápis zkouškové odpovědi

Hodnotitel boduje po částech — v dochovaném ohodnoceném řešení z 21.06.2021 jsou vidět dílčí body zvlášť za kritérium, za rozpočet, za podmínku $D_{max}$ i za sekci parametrů. Kompletní odpověď má čtyři bloky: objective (kritérium), constraints (omezení, ideálně s krátkým slovním komentářem, co která skupina dělá), parameters (co je dané) a variables (o čem se rozhoduje, s definicí významu). Chybějící blok = zbytečně ztracené půlbody.

Kontrola před odevzdáním (reálné ztráty bodů)
Key takeaways — L1.9
T01 Wedding plan FOTO checkpoint zdroj: zkouška KO 25.05.2026 (7 b.); dříve 21.06.2021 (6 b.) a 2023
Assignment (original, EN)

“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.”

FOTO checkpoint

Tuhle úlohu vyřeš celou NA PAPÍR — od prázdného listu, bez koukání do lekce ani do řešení, ideálně na čas (na zkoušce na ni budeš mít zhruba 15–20 minut). Pak mi pošli fotku — zkontroluju ti ji a vytknu chyby přesně jako hodnotitel.

a) Co je v zadání?

Pozvat co nejvíc hostů z množiny $G$ ($n$ kandidátů). Výdaje: jídlo $m$ CZK za každého pozvaného + pronájem místa, jehož cena je po částech konstantní podle počtu pozvaných ($p_1$ pro 0–9, $p_2$ pro 10–19, $p_3$ pro 20–$n$). Celkem nejvýš $B$ CZK. Navíc se počty pozvaných ze strany ženicha (groom) a nevěsty (bride) smí lišit nejvýš o $D_{max}$; příslušnost ke stranám dávají parametry $gr(g_i), br(g_i) \in \{0,1\}$, přičemž host může patřit k oběma stranám zároveň. Výstup: ILP model rozhodující, kdo bude pozván.

b) Co k tomu budeme potřebovat?

c) Jak nad úlohou uvažovat?

Postupuj přesně podle kroků z výkladu: ① rozsekej zadání na věty a u každé si poznač techniku; ② proměnné — co je rozhodnutí ($x_i$, $y_k$) a co parametr ($m, p_k, B, D_{max}, br, gr, n$)? ③ omezení po blocích: výběr intervalu + vazby na $N = \sum_i x_i$ (jaké $M$ stačí?), rozpočet (co všechno se platí?), spravedlnost (kolik nerovností?); ④ kritérium. Nakonec projdi checklist z boxu „Kontrola před odevzdáním“.

d) Úplné řešení

Variables: $x_i \in \{0,1\}$, $x_i = 1$ ⟺ host $g_i$ je pozvaný; $y_1, y_2, y_3 \in \{0,1\}$, $y_k = 1$ ⟺ počet pozvaných padne do $k$-tého cenového intervalu. Zkratka $N = \sum_{i=1}^{n} x_i$ (lineární výraz, ne proměnná).

$$\begin{aligned} \max \quad & \sum_{i=1}^{n} x_i && \text{(as many guests as possible)} \\ \text{s.t.} \quad & y_1 + y_2 + y_3 = 1 && \text{(právě jeden cenový interval)} \\ & N \le 9 + n(1 - y_1) && \text{(interval 1: } N \in [0,9]) \\ & N \ge 10 - n(1 - y_2), \quad N \le 19 + n(1 - y_2) && \text{(interval 2: } N \in [10,19]) \\ & N \ge 20 - n(1 - y_3) && \text{(interval 3: } N \in [20,n]) \\ & m N + p_1 y_1 + p_2 y_2 + p_3 y_3 \le B && \text{(budget not exceeded)} \\ & \textstyle\sum_{i=1}^{n} gr(g_i)\,x_i - \sum_{i=1}^{n} br(g_i)\,x_i \le D_{max} && \text{(strany se neliší} \\ & \textstyle\sum_{i=1}^{n} br(g_i)\,x_i - \sum_{i=1}^{n} gr(g_i)\,x_i \le D_{max} && \text{ o víc než } D_{max}\text{)} \\ & x_i \in \{0,1\} \;\; \forall i \in 1..n, \qquad y_k \in \{0,1\} \;\; \forall k \in \{1,2,3\} \end{aligned}$$

Parameters: $n \in \mathbb{N}^+$; $m, p_1, p_2, p_3, B \in \mathbb{R}^+$; $D_{max} \in \mathbb{Z}_0^+$; $br(g_i), gr(g_i) \in \{0,1\}$ pro $i \in 1..n$.

Komentáře:

  • $M = n$ stačí: $0 \le N \le n$ vždy, takže uvolněná mez (např. $N \ge 10 - n$) nikdy nic neomezuje (zadání implikuje $n \ge 20$ — jinak by interval $[20, n]$ byl prázdný; pak je $20 - n \le 0$ a uvolněná mez opravdu nic neomezuje). Triviální meze $N \ge 0$ (interval 1) a $N \le n$ (interval 3) platí automaticky. Kompaktní ekvivalent vazeb (díky $\sum_k y_k = 1$): $10y_2 + 20y_3 \le N \le 9y_1 + 19y_2 + n\,y_3$.
  • Rozpočet: jídlo $m$ za každého pozvaného ($mN$) + pronájem vybraného intervalu ($\sum_k p_k y_k$). Pronájem se nenásobí počtem hostů.
  • Spravedlnost: $|{\sum_i gr(g_i)x_i - \sum_i br(g_i)x_i}| \le D_{max}$ roztržená na dvě nerovnosti [L1.8]. Host s $br = gr = 1$ se v rozdílu vyruší — žádná zvláštní obsluha.
  • Srovnání s dochovaným studentským řešením (21.06.2021): student použil obrácené přepínače $Y_k = 1$ ⟺ interval nevybrán ($Y_1+Y_2+Y_3 = 2$, v rozpočtu $(1-Y_k)p_k$) — legální ekvivalent, ale ztratil 2 body za neúplně svázané meze intervalů a body za první (sečtenou místo odečtenou) verzi podmínky $D_{max}$. Přímý význam $y_k = 1$ ⟺ vybráno je bezpečnější.
← Předchozí L1.8 · Rozdíl / omezení rozptylu (max−min)