Navázání binární na spojitou/celočíselnou (aktivace)
Prerekvizita: [L1.4] big-M: disjunkce omezení — vypínání omezení členem $M \cdot y$ tu uvidíš v nejčastější praktické podobě. Hodí se i [L0.8] Binární proměnná.
Výchozí model: Cloth Production
Slide 33 přednášky ILP staví výrobní model: šijeme tři produkty (T-shirt, shirt, robe), $x_i \in \mathbb{Z}^+_0$ je vyrobené množství produktu $i$. Po odečtení nákladů na práci a materiál od příjmu vychází zisk na kus $6$, $4$ a $7$ (v tisících CZK) a kapacity dávají dvě omezení:
$$\begin{aligned} \max z = \quad & 6x_1 + 4x_2 + 7x_3 \\ \text{s.t.} \quad & 3x_1 + 2x_2 + 6x_3 \le 160 \quad \text{(labor)} \\ & 4x_1 + 3x_2 + 4x_3 \le 130 \quad \text{(material)} \\ & x_{i \in 1 \cdots 3} \in \mathbb{Z}^+_0 \end{aligned}$$To je klasické ILP, jaké už umíš z [L1.1]. Teď přijde nová podmínka (slide 34): the fixed cost has to be covered to rent the machine — na každý produkt potřebuješ pronajmout stroj a pronájem stojí fixní částku (200 000, 150 000 a 100 000 CZK), ať vyrobíš jeden kus, nebo sto.
Zkus sám: jaké proměnné a jaký člen v kritériu potřebuješ, aby model pronájem „zaplatil“?
Pronájem je rozhodnutí ano/ne — tedy binary variable (binární proměnná) $y_i \in \{0,1\}$: $y_i = 1$, když je stroj na produkt $i$ pronajatý. Kritérium se změní na (částky v tisících, slide 34):
$$\max z = 6x_1 + 4x_2 + 7x_3 - 200y_1 - 150y_2 - 100y_3$$V čem je háček: solver podvádí
Zkus sám: nech model přesně takhle — kritérium s $-200y_1 - 150y_2 - 100y_3$, žádné další omezení. Co udělá solver s $y$? A co to znamená pro řešení?
Solver maximalizuje, takže záporné členy chce co nejmenší — nastaví $y_1 = y_2 = y_3 = 0$ a fixní náklady prostě nezaplatí, přitom klidně vyrábí $x_i > 0$. Proměnné $x_i$ a $y_i$ spolu zatím nijak nesouvisí — v modelu chybí omezení, které by je svázalo. Kritérium samo žádnou logiku nevynutí.
Potřebujeme tedy do soustavy přidat vazbu (slide 35): stroj $i$ je pronajatý, právě když se produkt $i$ vyrábí. Formálně join binary $y_i$ with integer $x_i$ tak, aby
- $y_i = 0$ iff $x_i = 0$,
- $y_i = 1$ iff $x_i \ge 1$.
Vazba $x_i \le M \cdot y_i$
Zkus sám: víš, že $x_i$ nikdy nepřekročí 100 (rozsah $x_i \in \langle 0, 100 \rangle$). Vymysli JEDNU lineární nerovnost s $x_i$ a $y_i$, která zakáže „vyrábím, ale neplatím“ (tedy $x_i \ge 1$ a zároveň $y_i = 0$).
$$x_i \le 100 \cdot y_i$$
Pro $y_i = 0$ se redukuje na $x_i \le 0$, tedy $x_i = 0$ — bez zaplaceného pronájmu se vyrábět nedá. Pro $y_i = 1$ dává $x_i \le 100$, což $x_i$ neomezuje nad rámec jeho rozsahu — omezení je vypnuté. Poznáváš vzor z [L1.4]? Je to přesně big-M konstrukce s $M = 100$ = horní mez proměnné: člen $M \cdot y_i$ na pravé straně omezení „$x_i \le 0$“ ho podle hodnoty přepínače vypíná.
Podívej se, co vazba $x \le M y$ dělá geometricky (pro názornost $M = 10$). LP relaxace (modře vyplněná oblast, $y$ spojité) je trojúhelník — ale celočíselnost $y \in \{0,1\}$ z něj nechá jen dva vodorovné „řezy“:
Zkus sám: nerovnost $x_i \le 100 y_i$ pokrývá směr „vyrábím ⟹ platím“. Pokrývá i obrácený směr „$y_i = 1$ ⟹ opravdu vyrábím“? Najdi přípustný bod, který to porušuje.
Nepokrývá: bod $x_i = 0$, $y_i = 1$ nerovnost $0 \le 100$ splňuje — model dovoluje platit pronájem stroje, který nic nevyrábí (na obrázku bod $(0, 1)$). Druhý směr vynucuje nerovnost
$$x_i \ge y_i,$$
která pro $y_i = 1$ dává $x_i \ge 1$ (a pro $y_i = 0$ neříká nic). Slide 35 ale dodává: „we can omit this inequality due to the objective function ($x_i = 0, y_i = 1$ will not be chosen because we want $x_i$ to be maximal and $y_i$ minimal)“ — bod $(0,1)$ sice přípustný je, ale optimum to nikdy nebude, protože $y_i$ v kritériu jen ubírá (a stačí ho vypnout, nic jiného se nezmění).
Kdy $x \ge y$ NEsmíš vynechatVynechání funguje jen tehdy, když kritérium samo „tlačí“ $y$ k nule (zapnutí jen stojí peníze). Jakmile $y$ v modelu něco umožňuje nebo vydělává — odemyká jiné omezení, vystupuje v dalším vztahu, nebo se na „$x > 0$“ ptá zadání přímo — musí ekvivalence platit ze soustavy, ne z dobré vůle solveru. Pak piš obě nerovnosti: $x \le M y$ a $x \ge y$. U spojitého $x$ navíc „$x > 0$“ ostrou nerovností zapsat nejde — vynucuje se $x \ge \varepsilon \cdot y$ s malou konstantou $\varepsilon > 0$ (u celočíselného $x$ je přirozeně $\varepsilon = 1$).
Shrnutí konstrukce
Pro proměnnou $x \in \langle 0, M \rangle$ (spojitou i celočíselnou — $M$ je horní mez $x$) a aktivační přepínač $y \in \{0,1\}$:
$$\begin{aligned} x & \le M \cdot y && \text{„používám } x \Rightarrow y = 1\text{“} \\ x & \ge y \;\; (\text{resp. } x \ge \varepsilon y) && \text{„} y = 1 \Rightarrow x \ge 1 \text{ (resp. } x \ge \varepsilon\text{)“} \end{aligned}$$Druhou nerovnost lze vynechat, když ji nahradí tlak kritéria. Celý model Cloth Production s pronájmy strojů pak je:
$$\begin{aligned} \max z = \quad & 6x_1 + 4x_2 + 7x_3 - 200y_1 - 150y_2 - 100y_3 \\ \text{s.t.} \quad & 3x_1 + 2x_2 + 6x_3 \le 160 \\ & 4x_1 + 3x_2 + 4x_3 \le 130 \\ & x_i \le 100 \cdot y_i && i \in 1 \cdots 3 \\ & x_i \in \mathbb{Z}^+_0, \;\; y_i \in \{0,1\} && i \in 1 \cdots 3 \end{aligned}$$Tahle vazba je přesně to, co příští lekce [L1.6] Fixed-charge (fixní náklady) povýší na obecný vzorec pro nespojité nákladové funkce — a u ústní zkoušky je to oblíbené téma.
Key takeaways — L1.5- Aktivace: „pokud používám $x$ ($x > 0$), zapni přepínač $y$“ = $x \le M \cdot y$, kde $M$ je horní mez $x$. Pro $y = 0$ vynucuje $x = 0$, pro $y = 1$ nic neomezuje.
- Obrácený směr „$y = 1$ ⟹ vynuť $x > 0$“: $x \ge y$ (celočíselné $x$), u spojitého $x \ge \varepsilon \cdot y$.
- Nerovnost $x \ge y$ lze vynechat, jen když kritérium samo tlačí $y$ na 0 (zapnutí pouze stojí peníze) — slide 35: bod $x = 0, y = 1$ „will not be chosen“. Jinak ji piš.
- Je to speciální případ big-M z [L1.4]: $x \le 0 + M y$ = vypínatelné omezení „$x = 0$“.
- Tahle vazba je základ fixed-charge (fixních nákladů) → [L1.6]. (Téma ústní zkoušky.)
“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: labor is on demand with maximum capacity of 160 person-hours; material capacity is 130 meters.
Another constraint: the fixed cost has to be covered to rent the machine
| product | T-shirt | shirt | trousers |
|---|---|---|---|
| machine cost | 200 000 | 150 000 | 100 000 |
Machine $i$ is rented when product $i$ is produced. We join binary $y_i$ with integer $x_i$ such that: $y_i = 0$ iff $x_i = 0$; $y_i = 1$ iff $x_i \ge 1$. For range $x_i \in \langle 0, 100 \rangle$ these relations can be written as inequalities.”
Task: Write these relations as inequalities and formulate the complete model.
a) Co je v zadání?
Výrobní plánování tří produktů: $x_i$ = počet kusů, zisk na kus po odečtení práce a materiálu, dvě kapacitní omezení. Navíc fixní pronájem stroje za každý vyráběný produkt — sestavit celý ILP model včetně vazby $x_i \leftrightarrow y_i$. (Drobnost zdroje: tabulka strojů uvádí třetí produkt jako „trousers“, výrobní tabulka „robe“ — jde o tentýž třetí produkt, slidy se v názvu rozcházejí.)
b) Co k tomu budeme potřebovat?
- Tato lekce — vazba $x_i \le M y_i$ a kdy lze vynechat $x_i \ge y_i$.
- [L1.1] Cílová funkce a základní omezení — sestavení kritéria a kapacit.
- [L0.8] Binární proměnná — význam $y_i$.
c) Jak nad úlohou uvažovat?
Nejdřív čistý model bez strojů: zisk na kus [1000 CZK] = income − labor·1 − material·0.2 (income je v tabulce už v tisících CZK; 1000 CZK za person-hour = 1, 200 CZK za metr = 0.2). Pak: v jakých jednotkách přidáš pronájmy do kritéria? Jaká nerovnost zařídí, že $y_i = 0$ vynucuje $x_i = 0$? Potřebuješ tady i $x_i \ge y_i$, nebo ji za tebe odvede kritérium — a proč přesně?
d) Úplné řešení
Zisk na kus (v 1000 CZK; práce 1 person-hour = 1000 CZK = 1, materiál 1 m = 200 CZK = 0.2): $$\begin{aligned} \text{T-shirt:} \;& 9.8 - 3 \cdot 1 - 4 \cdot 0.2 = 6, \\ \text{shirt:} \;& 6.6 - 2 \cdot 1 - 3 \cdot 0.2 = 4, \\ \text{robe:} \;& 13.8 - 6 \cdot 1 - 4 \cdot 0.2 = 7. \end{aligned}$$
Proměnné: $x_i \in \mathbb{Z}^+_0$ = množství produktu $i$; $y_i \in \{0,1\}$, $y_i = 1$ když je stroj na produkt $i$ pronajatý. Pronájmy v tisících: 200, 150, 100. Celý model:
$$\begin{aligned} \max z = \quad & 6x_1 + 4x_2 + 7x_3 - 200y_1 - 150y_2 - 100y_3 \\ \text{s.t.} \quad & 3x_1 + 2x_2 + 6x_3 \le 160 \\ & 4x_1 + 3x_2 + 4x_3 \le 130 \\ & x_i \le 100 \cdot y_i && i \in 1 \cdots 3 \\ & x_i \in \mathbb{Z}^+_0, \;\; y_i \in \{0,1\} && i \in 1 \cdots 3 \end{aligned}$$Vazba: $x_i \le 100 y_i$ (s $M = 100$ z rozsahu $x_i \in \langle 0, 100 \rangle$) vynucuje „$x_i \ge 1 \Rightarrow y_i = 1$“. Druhá nerovnost $x_i \ge y_i$ by vynucovala „$y_i = 1 \Rightarrow x_i \ge 1$“, ale dle slidu 35 ji lze vynechat: kombinace $x_i = 0, y_i = 1$ jen zhoršuje kritérium (platíš pronájem za nic), takže ji optimum nikdy nezvolí — „we want $x_i$ to be maximal and $y_i$ minimal“.
Kontrola kapacit vs. $M$: z materiálu $4x_1 \le 130$ plyne $x_1 \le 32$, takže $M = 100$ je bezpečně nad skutečným maximem — vypnutá vazba nikdy neořezává přípustná řešení (pravidlo volby $M$ z [L1.4]).