Poměrová a max-z-více podmínka
Prerekvizity: [L1.4] Disjunkce a big-M, [L1.10] Linearizace absolutní hodnoty. V [L1.10] jsi na zkouškové úloze Maximization of absolute value (zkouška 2023) vyřešil kritérium $\max |x_1| + |x_2|$ a disjunkci. Zbyly dvě podmínky, které jsme tam odbyli „selským rozumem“ — dnes je rozebereme systematicky:
- podmínka (2): „$x_1$ is at least $\max\{2 \cdot x_2, x_3\}$“,
- podmínka (3): „$\frac{x_1}{x_4}$ equals to 4“.
Poměrová podmínka: $\frac{x_1}{x_4} = 4$
Zlomek se dvěma proměnnými do ILP napsat nesmíš — $\frac{x_1}{x_4}$ není lineární výraz (lineární výraz je jen součet konstanta × proměnná).
Zkus sám: jak z rovnice $\frac{x_1}{x_4} = 4$ zlomek odstranit, aby zbyla lineární rovnost?
Vynásob obě strany jmenovatelem $x_4$:
$$x_1 = 4 \cdot x_4.$$To už lineární je — žádný součin dvou proměnných, jen proměnná krát konstanta. Poměr dvou proměnných rovný konstantě $c$ je obecně vždy přímka procházející počátkem: $\frac{a}{b} = c \iff a = c \cdot b$.
Zkus sám: kdy je úprava „vynásobím jmenovatelem“ vůbec legální? Proč v této úloze nehrozí problém?
Zlomek $\frac{x_1}{x_4}$ má smysl jen pro $x_4 \ne 0$ — dělit nulou se nesmí. Násobením jmenovatelem se rovnice $x_1 = 4x_4$ stane splnitelnou i pro $x_4 = 0$ (s $x_1 = 0$), což původní podmínka nedovolovala. Musíš tedy zvlášť zaručit $x_4 \ne 0$.
V zadání 2023 to vyřešily meze: podmínka (5) říká $x_4 \ge 1$, takže $x_4 = 0$ je vyloučené samo od sebe a rovnost $x_1 = 4x_4$ je úplný přepis. (Bonus: $x_4 \ge 1$ navíc vynucuje $x_1 = 4x_4 \ge 4 > 0$ — přesně to „vynucené znaménko“, díky kterému v [L1.10] zmizela absolutní hodnota $|x_1|$.)
A co kdyby $x_4 \ge 1$ v zadání nebylo? Podmínka $x_4 \ne 0$
Ruční řešení zkoušky 2023 si k podmínce (3) poznamenalo: $x_4 \ne 0 \Rightarrow (x_4 > 0) \lor (x_4 < 0)$ — a zavedlo binárku $z \in \{0,1\}$. Proč binárku? (Pro tuto hypotetickou variantu předpokládejme, že by pro $x_4$ platila stejná dolní mez $-5000$ jako pro ostatní proměnné — v originále má $x_4$ dolní mez $1$, takže tam není co řešit.)
Zkus sám: umíš „$x_4 \ne 0$“ napsat jako jedno lineární omezení? Co ti brání?
Neumíš. Přípustná množina $\{x_4 : x_4 \ne 0\}$ má uprostřed díru — a jedno lineární omezení vždy vyřízne souvislou polorovinu, díru udělat neumí. „Nerovná se“ je ve skutečnosti disjunkce dvou podmínek:
$$x_4 \ne 0 \iff (x_4 > 0) \;\lor\; (x_4 < 0),$$a pro celočíselné $x_4$ (podmínka (4): $x_4 \in \mathbb{Z}$) se ostré nerovnosti převedou na neostré:
$$x_4 \ge 1 \quad \lor \quad x_4 \le -1.$$Disjunkci „aspoň jedna z podmínek platí“ už umíš z [L1.4]: binární přepínač + big-M.
Zkus sám: zapiš obě větve s přepínačem $z \in \{0,1\}$ a big-M. Jak velké $M$ potřebuješ při mezích $-5000 \le x_4 \le 1000$?
Pro $z = 1$ platí naostro $x_4 \ge 1$ a druhé omezení je uvolněné ($x_4 \le -1 + M$); pro $z = 0$ naopak platí $x_4 \le -1$. Volba $M$: vypnuté omezení musí být splnitelné pro všechny hodnoty v mezích — z $1 - M \le -5000$ plyne $M \ge 5001$, z $-1 + M \ge 1000$ plyne $M \ge 1001$. Stačí tedy např. $M = 5001$.
Tohle je přesně ten případ, kde se bez přepínače neobejdeš — stejně jako u obecné $\max |x|$ s neurčitým znaménkem z [L1.10]. Není náhoda, že je to tatáž binárka: obě konstrukce rozhodují, na které straně nuly proměnná leží. (V [L1.10] jsme tento znaménkový přepínač značili $s$ — tady držíme $z$ podle ručního řešení zkoušky 2023; je to táž role, jen jiné písmeno.)
Pozor: trik s $x \ne 0$ stojí na celočíselnostiPřepis $x \ne 0 \iff (x \ge 1) \lor (x \le -1)$ platí jen pro $x \in \mathbb{Z}$. Pro spojitou proměnnou ostrou nerovnost $x > 0$ v (I)LP zapsat nelze — přípustná množina musí být uzavřená. Než trik použiješ, ověř si v zadání, že proměnná je celočíselná (tady ano: podmínka (4)). A pokud zadání dává $x_4 \ge 1$ rovnou (jako zkouška 2023), žádný přepínač nezaváděj — byla by to zbytečná práce a zbytečný prostor pro chybu.
Max-z-více podmínka: „$x_1$ is at least $\max\{2x_2,\; x_3\}$“
Druhá podezřelá podmínka obsahuje $\max$ — a $\max$ není lineární funkce. Přesto ji přepíšeš bez jediné pomocné proměnné.
Zkus sám: co přesně říká „$x_1$ je aspoň maximum z $2x_2$ a $x_3$“ o vztahu $x_1$ ke každému z těch dvou výrazů?
Být aspoň tak velký jako maximum skupiny = být aspoň tak velký jako každý člen skupiny:
$$x_1 \ge \max\{2x_2,\; x_3\} \iff x_1 \ge 2x_2 \;\;\text{A ZÁROVEŇ}\;\; x_1 \ge x_3.$$A konjunkce (AND) je v ILP zadarmo — prostě napíšeš obě nerovnosti pod sebe. Stejný princip jsi už použil v [L1.8] u $h_{max}$: „$h_{max} \ge$ součet každé skupiny“ je tatáž konstrukce, jen s více členy. Obecně pro libovolný počet výrazů: $x \ge \max\{a_1, \ldots, a_k\} \iff x \ge a_j$ pro všechna $j$.
Zkus sám: a co opačný směr — $x \le \max\{a, b\}$? Je to taky „obě nerovnosti pod sebe“?
Není! Být nejvýš roven maximu znamená nepřesáhnout aspoň jeden z výrazů — stačí, když $x \le a$ NEBO $x \le b$ (ten větší z nich). To je disjunkce, takže binární přepínač + big-M [L1.4]: $x \le a + M(1-s)$, $x \le b + Ms$. Kdybys omylem napsal obě nerovnosti naostro (AND), vyžadoval bys $x \le \min\{a,b\}$ — to je přísnější podmínka a ořezal by sis přípustná řešení.
Nebezpečná polopravda: „podmínku s max/min vždy rozepíšu na všechny nerovnosti“Rozepsání na konjunkci (obě nerovnosti pod sebe, zadarmo) je správně jen na „snadné“ straně: $x \ge \max\{\cdot\}$ a symetricky $x \le \min\{\cdot\}$. Opačné směry ($x \le \max\{\cdot\}$, $x \ge \min\{\cdot\}$) říkají „stačí aspoň jeden výraz“ — to je disjunkce a potřebuje binární přepínač + big-M [L1.4]. Vždy si nahlas přelož, jestli podmínka chce „pro KAŽDÝ člen“ (AND, zadarmo), nebo „pro ASPOŇ JEDEN člen“ (OR, přepínač).
Key takeaways — L1.11- Poměr = přímka: $\frac{x_1}{x_4} = 4 \iff x_1 = 4 \cdot x_4$ (lineární rovnost). Násobení jmenovatelem je legální, jen když je zaručeno $x_4 \ne 0$ — ve zkoušce 2023 to zaručila mez $x_4 \ge 1$.
- $x \ge \max\{a, b\} \iff x \ge a$ AND $x \ge b$ — „aspoň maximum“ = „aspoň každý člen“, konjunkce je v ILP zadarmo (žádná pomocná proměnná). Symetricky $x \le \min\{a,b\} \iff x \le a$ AND $x \le b$.
- Opačné směry jsou disjunkce: $x \le \max\{\cdot\}$ a $x \ge \min\{\cdot\}$ znamenají „stačí aspoň jeden člen“ → binární přepínač + big-M [L1.4].
- „$x_4 \ne 0$“ je díra = disjunkce: pro $x_4 \in \mathbb{Z}$ je $x_4 \ne 0 \iff (x_4 \ge 1) \lor (x_4 \le -1)$, tedy znaménkový přepínač $z$ přes big-M: $x_4 \ge 1 - M(1-z)$, $x_4 \le -1 + Mz$. Tady (a u obecné $\max|x|$ z [L1.10]) přepínač opravdu potřebuješ; pro spojité proměnné $\ne$ zapsat nelze vůbec.
“Consider the following mathematical model of four variables $x_1, x_2, x_3$ and $x_4$.
$$\text{Maximize } |x_1| + |x_2|$$subject to the restrictions
- at least one of these two constraints must hold:
- $x_1 + x_2 + x_3 + x_4 \le 1000$
- $3 \cdot x_1 + 5 \cdot x_2 + x_3 + 2 \cdot x_4 \le 500$
- $x_1$ is at least $\max\{2 \cdot x_2, x_3\}$.
- $\frac{x_1}{x_4}$ equals to 4.
- $x_{i \in \{1, 2, 3, 4\}} \in \mathbb{Z}$
- $-5000 \le x_{i \in \{1, 2, 3\}}$, $x_4 \ge 1$, $x_{i \in \{1, 2, 3, 4\}} \le 1000$.
Formulate by the Integer Linear Programming.”
a) Co je v zadání?
Stejná zkoušková úloha jako v [L1.10] (tam jsme řešili kritérium s absolutními hodnotami a disjunkci (1)). Tentokrát se soustřeď na podmínky (2) — „$x_1$ je aspoň maximum dvou výrazů“ — a (3) — poměr $\frac{x_1}{x_4} = 4$. Navíc si rozmysli variantu: co kdyby místo $x_4 \ge 1$ zadání říkalo jen $x_4 \ne 0$?
b) Co k tomu budeme potřebovat?
- Tato lekce — poměr → rovnost, $\ge \max$ → konjunkce, $\ne 0$ → disjunkce.
- [L1.4] Disjunkce a big-M — přepínač pro variantu $x_4 \ne 0$.
- [L1.10] Linearizace absolutní hodnoty — zbytek modelu (kritérium, disjunkce (1)).
c) Jak nad úlohou uvažovat?
K (2): přelož si $\max$ do češtiny — chce zadání „$x_1 \ge$ KAŽDÝ z výrazů“, nebo „$x_1 \ge$ ASPOŇ JEDEN“? Podle toho AND (zadarmo), nebo OR (přepínač). K (3): zbav se zlomku násobením — a hned zkontroluj, co zaručuje, že jmenovatel není nula. K variantě $x_4 \ne 0$: kde má přípustná množina díru a na kolik větví se rozpadne? Nezapomeň spočítat big-M poctivě z mezí (5).
d) Úplné řešení
Podmínka (2): „$x_1$ is at least $\max\{2x_2, x_3\}$“ = $x_1$ je aspoň tak velké jako každý z obou výrazů — konjunkce, dvě nerovnosti zadarmo:
$$x_1 \ge 2 x_2, \qquad x_1 \ge x_3.$$Podmínka (3): vynásobením jmenovatelem $\frac{x_1}{x_4} = 4 \iff x_1 = 4 x_4$ (lineární rovnost). Dělení nulou nehrozí: podmínka (5) vynucuje $x_4 \ge 1$, takže $x_4 = 0$ je vyloučené. Navíc z $x_1 = 4x_4 \ge 4 > 0$ plyne vynucené znaménko $x_1$, takže $|x_1| = x_1$ v kritériu (viz [L1.10]).
Varianta — kdyby zadání dávalo jen $x_4 \ne 0$ (a pro $x_4$ stejnou dolní mez $-5000$ jako pro ostatní proměnné): pro $x_4 \in \mathbb{Z}$ je $x_4 \ne 0 \iff (x_4 \ge 1) \lor (x_4 \le -1)$. Disjunkce → binárka $z \in \{0,1\}$ + big-M:
$$x_4 \ge 1 - M(1 - z), \qquad x_4 \le -1 + M z, \qquad z \in \{0,1\}.$$Velikost $M$ při mezích $-5000 \le x_4 \le 1000$: vypnutá větev musí povolit celé rozpětí — $1 - M \le -5000 \Rightarrow M \ge 5001$ a $-1 + M \ge 1000 \Rightarrow M \ge 1001$, tedy např. $M = 5001$. Pozor: v této variantě by už znaménko $x_1$ nebylo vynucené ($x_4$ smí být záporné), takže i $|x_1|$ v kritériu by potřebovalo znaménkový přepínač jako $|x_2|$ — viz řešení T02 v [L1.10].
Zbytek modelu (kritérium $\max |x_1| + |x_2|$, disjunkce (1) s $y \in \{0,1\}$ a $M = 11000$, meze (5)) je kompletně vyřešený v úloze T02 lekce [L1.10] — výsledný model si tam porovnej.