Cílová funkce a základní omezení
Prerekvizity: [L0.7] Co je ILP a LP relaxace, [L0.8] Binární proměnná.
Tři povinné části modelu
V [L0.7] ses naučil, co ILP je: $\max\{c^T x : \mathbf{A}x \le b,\ x \in \mathbb{Z}^n\}$. Od téhle lekce začíná řemeslo Slotu 1 (7 bodů, 100 % termínů): ILP modely psát. Každý odevzdaný model musí mít tři části — když některá chybí, model není úplný a přicházíš o body:
- Proměnné (variables) — co rozhoduji, včetně oboru: $x_i \in \{0,1\}$? $\in \mathbb{Z}^+_0$? $\in \mathbb{R}^+_0$?
- Cílová funkce (objective function) — co maximalizuji/minimalizuji: lineární výraz $\sum_i c_i x_i$.
- Omezení (constraints) — co musí platit: lineární nerovnosti nebo rovnosti.
Slidy navíc oddělují parametry (parameters) — vstupní konstanty zadání ($n$, ceny $p_i$, rozpočet $B$, …). Parametry solver dostane, proměnné solver hledá. Záměna parametru a proměnné je nejčastější začátečnická chyba.
Zkus sám: kamarád odevzdá model „$\max z = 16x_1 + 22x_2$ s.t. $5x_1 + 7x_2 \le 14$“. Co v něm chybí a co se může stát?
Chybí obor proměnných. Bez něj solver smí dosadit $x_1 = 2.8,\ x_2 = 0$ (reálné, klidně i víc než 1) — koupíš „2,8 budovy“. Teprve $x_i \in \{0,1\}$ říká „každou budovu nejvýš jednou, vcelku“. Obor je plnohodnotná součást modelu, ne formalita — mění množinu přípustných řešení (srov. binární vs. frakční 2-Partition v [L0.8]).
Ze slov do matematiky: Real Estate Investment
Vzorové zadání ze slidů (02_ILP, slide 28): „We consider 6 buildings for investment. … Goal: maximize income. Constraints: investment budget is 14 mil CZK; each building can be bought only once.“
| building | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| price [mil. CZK] | 5 | 7 | 4 | 3 | 4 | 6 |
| income [thousand CZK] | 16 | 22 | 12 | 8 | 11 | 19 |
Postupuj vždy stejně. Krok 1 — proměnné: rozhodnutí je „koupit / nekoupit budovu $i$“, tedy binární $x_i \in \{0,1\}$ s konvencí „$x_i = 1$ iff budovu $i$ koupím“ (přesně čtení z [L0.8]).
Zkus sám: krok 2 — napiš cílovou funkci. Co se v zadání maximalizuje a jak to vyjádříš přes $x_i$?
Maximalizuje se příjem vybraných budov. Hodnota vybraných je suma „příjem × vybráno“ (do cíle jde řádka income, řádka price patří do omezení): $$\max z = 16x_1 + 22x_2 + 12x_3 + 8x_4 + 11x_5 + 19x_6.$$ Nevybrané budovy přispějí nulou — suma $\sum_i c_i x_i$ sama „vyškrtne“ nekoupené. Obecný vzor: cílová funkce = $\max$ (nebo $\min$) $\sum_i c_i x_i$, kde $c_i$ je přínos (koeficient v cíli) rozhodnutí $i$.
Zkus sám: krok 3 — napiš omezení „investment budget is 14 mil CZK“.
Utracené peníze = suma cen koupených budov, a ta nesmí přesáhnout 14: $$5x_1 + 7x_2 + 4x_3 + 3x_4 + 4x_5 + 6x_6 \le 14.$$ Tomuhle tvaru se říká budget/capacity constraint (rozpočtové či kapacitní omezení): $$\sum_i w_i x_i \le B,$$ kde $w_i$ je „spotřeba zdroje“ věcí $i$ a $B$ kapacita zdroje (peníze, čas, místo, hmotnost…). Druhé omezení zadání („each building can be bought only once“) je už schované v oboru $x_i \in \{0,1\}$.
Kompletní model (slide 29) — všimni si, že obsahuje všechny tři části:
$$\begin{aligned} \max z = \;& 16x_1 + 22x_2 + 12x_3 + 8x_4 + 11x_5 + 19x_6 \\ \text{s.t.} \;& 5x_1 + 7x_2 + 4x_3 + 3x_4 + 4x_5 + 6x_6 \le 14 \\ & x_{i \in 1 \cdots 6} \in \{0, 1\} \end{aligned}$$Max vs. min: stejný stroj, jiný směr
Minimalizace není nic nového: $\min \sum_i c_i x_i$ je totéž co $\max \sum_i (-c_i) x_i$ — jen otočíš směr, kterým po přípustné oblasti „tlačíš“. Stejná oblast, jiná cílová funkce, jiné optimum:
Zkus sám: a co rozhodovací úlohy bez kvality řešení („existuje rozdělení?“) — jakou mají cílovou funkci?
Klidně konstantní: $\min 0$. Viděl jsi to u 2-Partition v [L0.8] — solver pak jen hledá libovolné přípustné řešení a odpoví „řešení / infeasible“. Cílová funkce je povinná část zápisu, ale nemusí nic „vážit“. Naopak: ze stejné rozhodovací úlohy uděláš optimalizační, když do cíle dáš smysluplnou veličinu — uvidíš v úloze T02(c).
Checklist na písemku
U každé modelovací úlohy Slotu 1 piš v tomhle pořadí (a nic nevynech):
- parameters: co je dáno (a obory konstant),
- variables: co hledám + obor každé proměnné ($\{0,1\}$ / $\mathbb{Z}$ / $\mathbb{R}$),
- objective: $\max$ či $\min$ lineární výraz,
- subject to: všechna omezení jako lineární (ne)rovnosti — pro každou větu zadání zkontroluj, že je někde zachycená (v omezení, v cíli, nebo v oboru proměnných).
Key takeaways — L1.1- Kompletní ILP model = proměnné s oborem + cílová funkce + omezení (+ parametry zadání). Chybějící obor proměnných = jiný (špatný) model.
- Cílová funkce: $\max \sum_i c_i x_i$ nebo $\min \sum_i c_i x_i$; min je max s otočeným znaménkem. U rozhodovací úlohy smí být konstantní ($\min 0$).
- Rozpočtové (kapacitní) omezení: $\sum_i w_i x_i \le B$ — spotřeba zdroje vybraných věcí nepřesáhne kapacitu $B$.
- Každou větu slovního zadání zachyť v modelu: v omezení, v cíli, nebo v oboru proměnných („only once“ = $x_i \in \{0,1\}$).
“We consider 6 buildings for investment. The price and rental income for each of them are listed in the table.
| building | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| price [mil. CZK] | 5 | 7 | 4 | 3 | 4 | 6 |
| income [thousand CZK] | 16 | 22 | 12 | 8 | 11 | 19 |
Goal: maximize income. Constraints: investment budget is 14 mil CZK; each building can be bought only once.” Formulate the problem using ILP and find the optimal investment.
a) Co je v zadání?
Výběr podmnožiny budov: každá má pořizovací cenu a roční příjem z nájmu. Chceš maximální celkový příjem, ale součet cen koupených budov se musí vejít do rozpočtu 14 mil. Kč.
b) Co k tomu budeme potřebovat?
- Tato lekce — tři části modelu, cílová funkce, rozpočtové omezení.
- [L0.8] Binární proměnná — $x_i = 1 \iff$ koupeno, $\sum p_i x_i$ = hodnota vybraných.
c) Jak nad úlohou uvažovat?
Polož si tři otázky z checklistu: Co rozhoduji (a jaký obor to vynucuje)? Co maximalizuji (která řádka tabulky jde do cíle)? Co mě omezuje (která řádka jde do omezení a s jakou pravou stranou)? Pro optimum pak zkoušej kombinace, které vyčerpají rozpočet co nejtěsněji — s 6 binárními proměnnými to jde ručně.
d) Úplné řešení
Proměnné: $x_i = 1$ if we buy building $i$, tedy $x_{i \in 1\cdots 6} \in \{0,1\}$. Model (slide 29):
$$\begin{aligned} \max z = \;& 16x_1 + 22x_2 + 12x_3 + 8x_4 + 11x_5 + 19x_6 \\ \text{s.t.} \;& 5x_1 + 7x_2 + 4x_3 + 3x_4 + 4x_5 + 6x_6 \le 14 \\ & x_{i \in 1 \cdots 6} \in \{0, 1\} \end{aligned}$$Cíl = příjmová řádka tabulky, omezení = cenová řádka s pravou stranou 14 (rozpočtové omezení $\sum w_i x_i \le B$); „only once“ je v oboru $\{0,1\}$.
Optimum: $x = (1, 0, 0, 1, 0, 1)$ — budovy $\{1, 4, 6\}$: cena $5 + 3 + 6 = 14 \le 14$ ✓, příjem $z = 16 + 8 + 19 = \mathbf{43}$. Pro porovnání nejlepší dvojice $\{2,6\}$ dává jen $41$, trojice $\{2,3,4\}$ dává $42$ a $\{3,5,6\}$ taky $42$ — víc než 43 se do rozpočtu nevejde.
Poznámka: na slidech 30–32 se k téhle úloze přidávají logické podmínky (implikace, XOR) — to je téma [L1.3] Modelování logiky.
“(a) Example ILP1a: 2-Partition Problem. Instance: number of banknotes $n \in \mathbb{Z}_+$ and values $p_1, \ldots, p_n$, where $p_i \in \mathbb{Z}_+$. Decision: is there a subset $S \subseteq \{1, \ldots, n\}$ such that $$\sum_{i \in S} p_i = \sum_{i \notin S} p_i?$$ Formulate this decision problem as an ILP using binary variables.
(b) Example ILP1b: Fractional Variant of the 2-Partition Problem. Allow division of banknotes, i.e. $x_i \in \langle 0, 1 \rangle$, and formulate the LP relaxation.
(c) Example ILP1c: 2-Partition Problem – Optimization Version. Formulate an optimization model minimizing the larger of the two subset sums and explain the relation to $P2 \,\|\, C_{\max}$ scheduling.”
a) Co je v zadání?
Třikrát stejná úloha (rozdělit bankovky na dvě stejně hodnotné hromádky), třikrát jiný model: (a) rozhodovací ILP s binárními proměnnými, (b) frakční LP varianta, (c) optimalizační verze, která minimalizuje hodnotu těžší hromádky.
b) Co k tomu budeme potřebovat?
- Tato lekce — checklist parameters/variables/objective/constraints; konstantní cíl rozhodovací úlohy.
- [L0.8] Binární proměnná — $x_i = 1 \iff i \in S$; negace $1 - x_i$; v úlohách T01/T02 lekce L0.8 máš obě verze přečtené, tady je píšeš sám.
- [L0.7] Co je ILP a LP relaxace — frakční varianta = LP relaxace.
c) Jak nad úlohou uvažovat?
(a) Vyjádři hodnotu hromádky $S$ přes $x_i$ a uvědom si, že „obě stejné“ znamená „vybraná polovina = polovina celkového součtu“. Jaký cíl má čistě rozhodovací úloha? (b) Co přesně se změní v sekci variables — a co musíš přidat do omezení, aby $x_i$ nepřerostlo 1? (c) Hodnota druhé hromádky je $\sum_i (1-x_i)p_i$; zaveď novou proměnnou $C_{max}$ jako „strop“ obou hromádek a tlač ho dolů. Jaký obor má $C_{max}$?
d) Úplné řešení
(a) Rozhodovací ILP (slide 5): $x_i = 1$ iff $i \in S$. Podmínka $\sum_{i \in S} p_i = \sum_{i \notin S} p_i$ je ekvivalentní $\sum_i x_i p_i = 0.5 \sum_i p_i$ (obě hromádky stejné ⟺ vybraná má přesně polovinu celkového součtu):
$$\begin{aligned} \min \quad & 0 \\ \text{subject to:} \quad & \textstyle\sum_{i \in 1..n} x_i \ast p_i = 0.5 \ast \sum_{i \in 1..n} p_i \\ \text{parameters:} \quad & n \in \mathbb{Z}^+,\ p_{i \in 1..n} \in \mathbb{Z}^+ \\ \text{variables:} \quad & x_{i \in 1..n} \in \{0,1\} \end{aligned}$$Cíl $\min 0$ je konstantní — hledáme jen přípustné řešení (rozhodovací úloha).
(b) Frakční LP (slide 6): jediná koncepční změna je obor: $x_i \in \mathbb{R}^+_0$ plus omezení $x_i \le 1$ (bez něj by „bankovka“ mohla být vybrána víc než jednou):
$$\begin{aligned} \min \quad & 0 \\ \text{subject to:} \quad & \textstyle\sum_{i \in 1..n} x_i \ast p_i = 0.5 \ast \sum_{i \in 1..n} p_i \\ & x_i \le 1 \quad i \in 1..n \\ \text{parameters:} \quad & n \in \mathbb{Z}^+,\ p_{i \in 1..n} \in \mathbb{Z}^+ \\ \text{variables:} \quad & x_{i \in 1..n} \in \mathbb{R}^+_0 \end{aligned}$$Přípustná množina je konvexní → je to LP a řeší se polynomiálně.
(c) Optimalizační verze (slide 7): nová reálná proměnná $C_{max}$ = strop obou hromádek; minimalizací stropu se minimalizuje těžší hromádka:
$$\begin{aligned} \min \quad & C_{max} \\ \text{subject to:} \quad & \textstyle\sum_{i \in 1..n} x_i \ast p_i \le C_{max} \\ & \textstyle\sum_{i \in 1..n} (1 - x_i) \ast p_i \le C_{max} \\ \text{parameters:} \quad & n \in \mathbb{Z}^+,\ p_{i \in 1..n} \in \mathbb{Z}^+ \\ \text{variables:} \quad & x_{i \in 1..n} \in \{0, 1\},\ C_{max} \in \mathbb{R}^+ \end{aligned}$$Rozhodovací úlohu pak vyřešíš porovnáním optima s prahem (threshold) $0.5\sum_i p_i$: optimum $= $ práh ⟺ rozdělení existuje; jinak optimum vrací hodnotu nejblíž prahu. (Obecnou konstrukci „minimalizuj maximum z množiny hodnot“ rozebere [L1.8].)
Vztah k $P2\,\|\,C_{max}$: (zápis $P2\,\|\,C_{max}$ je třípolní Grahamova klasifikace rozvrhovacích problémů — systematicky ji zavádí [L5.1] Grahamova notace α|β|γ; tady stačí slovní čtení níže) slide 7 doslova: rozhodnutí $x_i$ = „na který ze dvou identických paralelních procesorů dám nepreemptivní úlohu $T_i$ s dobou $p_i$“; hromádka = zátěž procesoru a $C_{max}$ = čas dokončení poslední úlohy, který minimalizujeme. Frakční varianta odpovídá preemptivnímu rozvrhování.