Přiřazovací (assignment) struktura
Prerekvizity: [L1.1] Cílová funkce a základní omezení.
Když rozhodnutí není „ano/ne“, ale „kam“
Zkoušková úloha Toys Assignment (hračky do krabic, termín 09.07.2021) začíná takhle: po pokoji je rozházeno $n$ hraček $T = \{t_1, \ldots, t_n\}$, u zdi stojí řada $n$ krabic $B = \{b_1, \ldots, b_n\}$ a vzdálenost hračky $t_i$ od krabice $b_j$ je $d_{ij} \in \mathbb{R}^+_0$. Úkol: uklidit každou hračku do právě jedné krabice a do každé krabice právě jednu hračku tak, aby celková ujitá vzdálenost byla minimální.
V [L1.1] byl první krok modelu vždy stejný: „co rozhoduji?“ — a rozhodnutí „koupit budovu $i$?“ dalo binární $x_i$.
Zkus sám: proč tady proměnná $x_i \in \{0,1\}$ („hračka $i$ uklizena?“) nestačí? Jaké rozhodnutí ve skutečnosti dělám?
Rozhodnutí není „uklidit / neuklidit“ (uklízí se všechno), ale KAM: která hračka skončí ve které krabici. Odpověď má dva rozměry — hračku $i$ a krabici $j$. Trik: rozbij rozhodnutí „kam s $t_i$“ na $n$ otázek ano/ne, jednu pro každý pár (hračka, krabice):
$$x_{ij} = \begin{cases} 1, & \text{hračka } t_i \text{ je v krabici } b_j, \\ 0, & \text{jinak.} \end{cases}$$Celkem $n \times n$ binárních proměnných — pořád každá jen ano/ne dle [L0.8], jen jich je matice místo vektoru.
Tohle je obecný vzor: kdykoli zadání říká „přiřaď objekty pozicím / do skupin / na stroje / na sloty“, sáhni po assignment variables (přiřazovacích proměnných) $x_{ij} \in \{0,1\}$ s konvencí „$x_{ij} = 1 \iff$ objekt $i$ je na pozici $j$“.
Dvojí součtové omezení
Samotné proměnné $x_{ij}$ ještě nic nehlídají — solver by klidně nechal všechny nulové (nic neuklidil) nebo nacpal tři hračky do jedné krabice. Pravidla hry musíš napsat jako omezení.
Zkus sám: zapiš omezení „each toy is stored in one box“ (každá hračka v právě jedné krabici). Přes které indexy se sčítá?
Zafixuj hračku $i$ a projdi všechny krabice: $x_{i1} + x_{i2} + \cdots + x_{in}$ = počet krabic, ve kterých $t_i$ leží (součet binárních = počet vybraných, [L0.8]). Chceme právě jednu:
$$\sum_{j=1}^{n} x_{ij} = 1 \qquad \forall i = 1, \ldots, n.$$Sčítá se přes $j$ (krabice), omezení je jedno pro každé $i$ — celkem $n$ rovností, ne jedna!
Zkus sám: a teď druhou půlku — „each box contains exactly one toy“ (každá krabice právě jednu hračku).
Zrcadlově: zafixuj krabici $j$ a sečti přes hračky:
$$\sum_{i=1}^{n} x_{ij} = 1 \qquad \forall j = 1, \ldots, n.$$Dohromady tedy dvojí součtové omezení — $n$ „řádkových“ rovností a $n$ „sloupcových“ rovností. Pozor na nejčastější chybu: napsat jen jednu sadu. Samotné $\sum_j x_{ij} = 1$ dovolí dvě hračky v téže krabici (každý řádek je v pořádku, ale sloupec má součet 2).
Vyplatí se to vidět maticově. Proměnné $x_{ij}$ tvoří tabulku $n \times n$; přípustné přiřazení = v každém řádku i v každém sloupci právě jedna jednička (permutační matice):
| $x_{ij}$ | $b_1$ | $b_2$ | $b_3$ | $\sum_j$ |
|---|---|---|---|---|
| $t_1$ | 1 | 0 | 0 | = 1 ✓ |
| $t_2$ | 0 | 1 | 0 | = 1 ✓ |
| $t_3$ | 0 | 0 | 1 | = 1 ✓ |
| $\sum_i$ | = 1 ✓ | = 1 ✓ | = 1 ✓ |
A graficky — přiřazení je výběr hran mezi dvěma stranami (hračky vlevo, krabice vpravo):
Cílová funkce: cena vybraných párů
Zkus sám: jak zapíšeš „the total distance between the toys and their assigned boxes is minimized“? (Stejný trik jako cíl v [L1.1].)
Cena se platí jen za vybrané páry — a přesně to udělá součin „cena × vybráno“ sečtený přes všechny páry:
$$\min \; \sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij}\, x_{ij}.$$Pár s $x_{ij} = 0$ přispěje nulou, takže dvojitá suma automaticky sečte jen vzdálenosti realizovaných přiřazení. Je to tatáž logika jako $\sum_i c_i x_i$ z [L1.1], jen s maticí koeficientů $d_{ij}$ místo vektoru $c_i$.
Celá kostra přiřazovacího modelu (assignment problem) pohromadě:
$$\begin{aligned} \min \quad & \sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij}\, x_{ij} \\ \text{subject to:} \quad & \sum_{j=1}^{n} x_{ij} = 1 \quad \forall i = 1, \ldots, n \\ & \sum_{i=1}^{n} x_{ij} = 1 \quad \forall j = 1, \ldots, n \\ \text{variables:} \quad & x_{ij} \in \{0,1\} \quad \forall i, j \end{aligned}$$Kostra většiny rozdělovacích úloh: $=$, $\le$, kapacity
Přesně tahle kostra (s úpravami pravých stran) sedí na většinu „rozdělovacích“ zadání. Stačí se u každé strany zeptat: musí být obsazená právě jednou, nejvýš jednou, nebo má kapacitu?
Zkus sám: krabic je víc než hraček ($m > n$). Které omezení se změní a jak? A co by se stalo, kdybys nechal obě s „$= 1$“?
Každá hračka pořád musí někam: $\sum_{j} x_{ij} = 1$ pro každé $i$. Ale krabice už nemůžou být všechny obsazené — některé zůstanou prázdné: $$\sum_{i} x_{ij} \le 1 \qquad \forall j = 1, \ldots, m.$$ Kdybys nechal obě sady s $=1$, sečti řádkové rovnosti: jedniček je přesně $n$; sečti sloupcové: jedniček je přesně $m$. Pro $m \neq n$ spor → model je infeasible, i když reálná úloha řešení má. Špatné znaménko tu nezhorší optimum, ale zabije celý model.
Zkus sám: co modeluje omezení $\sum_i x_{ij} \le k_j$? Vymysli slovní čtení.
„Do skupiny/krabice/na stroj $j$ se vejde nejvýš $k_j$ objektů“ — kapacita pozice. Sloupcový součet = počet objektů přiřazených na $j$ ([L0.8]: $\sum$ binárních = počet vybraných), takže pravou stranou řídíš obsazenost: $=1$ právě jeden, $\le 1$ nejvýš jeden, $\le k_j$ kapacita, $\ge 1$ aspoň jeden (žádná skupina prázdná).
Výhled: assignment = perfektní párováníPřiřazovací problém s oběma sadami „$=1$“ je přesně minimum weight perfect matching (perfektní párování s min. vahou, [L0.6]) v úplném bipartitním grafu — vybrané hrany $\{(t_i, b_j) : x_{ij} = 1\}$ se nikde nesdílí ve vrcholu a pokrývají všechno. Tenhle most využije [L1.14] (Toys, část b) a naplno kapitola K4 (řeší se polynomiálně, např. maďarským algoritmem).
Key takeaways — L1.2- Přiřazovací proměnná: $x_{ij} \in \{0,1\}$, $x_{ij} = 1 \iff$ objekt $i$ je přiřazen na pozici / do skupiny $j$. Rozhodnutí „kam“ = matice rozhodnutí „ano/ne“.
- Dvojí součtové omezení: $\sum_j x_{ij} = 1\ \forall i$ (každý objekt právě jednou) a zároveň $\sum_i x_{ij} = 1\ \forall j$ (každá pozice právě jednou). Jen jedna sada nestačí.
- Cena přiřazení: $\min \sum_i \sum_j d_{ij} x_{ij}$ — nevybrané páry přispějí nulou.
- Pravá strana sloupcového součtu řídí obsazenost: $=1$ / $\le 1$ (pozic víc než objektů) / $\le k_j$ (kapacita) / $\ge 1$ (nikdo prázdný). Tohle je kostra většiny rozdělovacích úloh.
- Assignment s „$=1$“ na obou stranách = min-weight perfect matching v bipartitním grafu ([L0.6]; most do K4).
“There is a set of toys $T = \{t_1, t_2, \ldots, t_n\}$ scattered all around the room. By one of the walls, there is a row of boxes $B = \{b_1, b_2, \ldots, b_n\}$, where box $b_i$ is located left to $b_{i+1}$ for all $i \in \{1, 2, \ldots, n-1\}$. Distance of toy $t_i$ to box $b_j$ is $d_{ij} \in \mathbb{R}_0^+$ for all $t_i \in T$, $b_j \in B$.
(a) Design an ILP model to organize the toys to the boxes such that: (i) each box contains exactly one toy and each toy is stored in one box, (ii) the total distance between the toys and their assigned boxes is minimized, (iii) toy $t_1$ is assigned to the box immediately left to the box where $t_2$ is assigned, (iv) neither $t_5$ nor $t_6$ can be assigned to $b_1$ or $b_n$, (v) $t_4$ is in the box immediately next to $t_5$ or $t_6$.
(b) Disregard constraints (iii) and (v). Then, formalize the problem as an assignment problem (i.e., minimum weight perfect matching in complete bipartite graph whose sets have the same cardinality).”
V této lekci modeluj jen podmínky (i) a (ii) — přiřazovací kostru. Podmínky (iii)–(v) (sousednost, zákaz krajů, disjunkce) vyžadují techniky z [L1.3] a [L1.4]; celou úlohu (včetně části (b) — viz box Výhled) dotáhneš jako FOTO checkpoint v [L1.14].
a) Co je v zadání?
$n$ hraček, $n$ krabic, známá vzdálenost $d_{ij}$ každé hračky od každé krabice. Hledáš úklid „1 hračka ↔ 1 krabice“ (bijekci) s minimálním součtem vzdáleností realizovaných dvojic.
b) Co k tomu budeme potřebovat?
- Tato lekce — proměnné $x_{ij}$, dvojí součtové omezení, cena $\sum\sum d_{ij} x_{ij}$.
- [L1.1] Cílová funkce a základní omezení — checklist parameters / variables / objective / constraints.
- [L0.8] Binární proměnná — čtení „součet binárních = počet vybraných“.
c) Jak nad úlohou uvažovat?
Projdi checklist z [L1.1]: Co rozhoduji? (Pro každý pár hračka–krabice ano/ne.) Co minimalizuji? (Vzdálenosti — ale jen těch párů, které se opravdu realizují; jak to suma zařídí sama?) Co musí platit? Podmínka (i) jsou dvě věty — „each box contains exactly one toy“ a „each toy is stored in one box“ — každá dá jednu sadu součtových omezení. Zkontroluj si směr sčítání: které omezení sčítá přes $i$ a které přes $j$?
d) Úplné řešení
Proměnné:
$$x_{ij} = \begin{cases} 1, & \text{toy } t_i \text{ is assigned to box } b_j, \\ 0, & \text{otherwise,} \end{cases} \qquad x_{ij} \in \{0,1\} \quad \forall i,j \in 1 \ldots n.$$Parametry: $n \in \mathbb{Z}^+$, $d_{ij} \in \mathbb{R}^+_0$.
Cíl — podmínka (ii):
$$\min \; z = \sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij}\, x_{ij}.$$Omezení — podmínka (i) (přesně dle vzorového řešení banky):
$$\sum_{j=1}^{n} x_{ij} = 1 \quad \forall i = 1, \ldots, n \qquad \text{(každá hračka v právě jedné krabici)},$$ $$\sum_{i=1}^{n} x_{ij} = 1 \quad \forall j = 1, \ldots, n \qquad \text{(každá krabice právě jednu hračku)}.$$Kontrola proti zadání: „each toy is stored in one box“ = řádkové součty, „each box contains exactly one toy“ = sloupcové součty, „total distance … minimized“ = dvojitá suma v cíli; obor $\{0,1\}$ zakazuje půlení hraček. Všechny věty (i)+(ii) jsou zachycené.
Výhled: ve vzorovém řešení následují podmínky (iii)–(v), např. $x_{1j} = x_{2,j+1}$ pro sousednost $t_1$ vlevo od $t_2$ a $x_{5,1} = x_{5,n} = x_{6,1} = x_{6,n} = 0$ pro zákaz krajů — k těm se vrátíme v [L1.14] po logice [L1.3] a big-M [L1.4].