Fixed-charge (fixní náklady)
Prerekvizita: [L1.5] Navázání binární na spojitou (aktivace) — vazba $x \le M \cdot y$ je přesně to, co tady použijeme. V L1.5 jsme s ní platili pronájem stroje; teď z toho uděláme obecný vzorec.
Funkce, která „skáče“
Fixed-charge (fixní náklad, též fixed cost) je situace, kdy zaplatíš vstupní částku $A$ jednou — ať vyrobíš jeden kus, nebo tisíc — a k tomu $B$ za každý kus. Nákladová funkce tedy je:
$$f(x) = \begin{cases} A + Bx, & \text{pokud } x > 0, \\ 0, & \text{pokud } x = 0. \end{cases}$$Pozor na to, co se děje v nule: $f(0) = 0$, ale „těsně nad nulou“ už náklad začíná na $A$. Funkce má v nule skok — je nespojitá (discontinuous). Konkrétně třeba pro $A = 7$, $B = 5$:
Zkus sám: proč nemůžu do ILP napsat prostě kritérium $\min z = A + Bx$?
Protože by konstanta $A$ byla v ceně vždy — i pro $x = 0$. Výraz $A + Bx$ je rovnice té šikmé přímky, ale skutečná funkce v bodě $x = 0$ z přímky „vyskočí“ dolů na $0$. Lineární výraz v proměnné $x$ žádný skok udělat neumí: potřebujeme do modelu dostat informaci „platí se $A$, právě když $x > 0$“ — a to je rozhodnutí ano/ne.
Linearizace přes aktivační přepínač
Zkus sám: vzpomeň si na [L1.5]. Jakou proměnnou a jakou vazbu přidáš, aby kritérium platilo $A$ jen při $x > 0$?
Binární přepínač $y \in \{0,1\}$ se zamýšleným významem „$x > 0$ ⇒ $y = 1$“, do kritéria člen $A \cdot y$ a vazbu z L1.5:
$$\min z = A \cdot y + B \cdot x, \qquad x \le M \cdot y,$$kde $M$ je horní mez proměnné $x$. Pro $y = 0$ vazba vynucuje $x = 0$ a cena je $0$; pro $y = 1$ se vazba vypne a cena je $A + Bx$. Přesně kopie nespojité funkce $f$.
Zkus sám: zbývá podezřelý bod $x = 0,\ y = 1$ (cena $A$ za nic) — vazba $x \le My$ ho nezakazuje. Potřebuju kvůli němu přidat $x \ge y$?
Při minimalizaci s $A > 0$ ne. Bod $x = 0, y = 1$ je sice přípustný, ale stojí $A$, zatímco $x = 0, y = 0$ stojí $0$ a všechna ostatní omezení splňuje stejně — solver tedy dražší variantu nikdy nevybere. Je to zrcadlový argument k L1.5 (tam kritérium maximalizovalo a $y$ jen ubíralo). Jakmile ale $y$ v modelu dělá ještě něco jiného, než že stojí peníze, ekvivalenci $y = 1 \Leftrightarrow x \ge 1$ musíš vynutit i druhou nerovností $x \ge y$ — viz warning box v [L1.5].
Podívej se, jakou množinu dvojic (množství, cena) linearizovaný model $z = 7y + 5x$, $x \le M y$ vlastně nabízí:
Klasický chyták u zkouškyFixní náklad (pronájem stroje, pořizovací cena, „expenses that are the same for 1 piece as well as for 1000 pieces“) se v zadání objeví jako nenápadná věta — a láká dvě chyby: (1) vynásobit ho množstvím ($f_i \cdot x_i$ je špatně — fixní náklad se neplatí za kus), (2) dát $A \cdot y$ do kritéria, ale zapomenout vazbu $x \le M y$ — pak solver vyrábí a fixní náklad nezaplatí. Kritérium samo žádnou logiku nevynutí; vazba je povinná.
Recept (k zapamatování)
Nespojitý náklad $f(x) = 0$ pro $x = 0$, jinak $A + Bx$, kde $x \in \langle 0, M \rangle$:
$$\begin{aligned} \text{cena} &= A \cdot y + B \cdot x \\ x & \le M \cdot y \\ y & \in \{0,1\} \end{aligned}$$Při minimalizaci ceny (resp. maximalizaci zisku, ze kterého se cena odečítá) s $A > 0$ není potřeba nic dalšího. Stejný vzorec funguje pro každý produkt zvlášť: $\sum_i f_i y_i$ v kritériu + $x_i \le M y_i$ pro každé $i$ — to je přesně model Cloth Production z [L1.5].
Key takeaways — L1.6- Fixed-charge funkce: $f(x) = 0$ pro $x = 0$, jinak $f(x) = A + Bx$ — nespojitá (skok o $A$ v nule), takže ji nelze napsat jedním lineárním výrazem v $x$.
- Linearizace: binární aktivace $y$ z [L1.5]: náklad $= A \cdot y + B \cdot x$ s vazbou $x \le M \cdot y$ ($M$ = horní mez $x$).
- Při minimalizaci nákladu ($A > 0$) bod $x = 0, y = 1$ optimum nikdy nevyhraje — nerovnost $x \ge y$ lze vynechat. Vazbu $x \le My$ vynechat NIKDY nejde.
- Fixní náklady (pronájem stroje, pořízení) = klasický chyták: neplatí se za kus ($f_i x_i$ je špatně) a bez vazby je solver „nezaplatí“.
“Consider the following mathematical model of two variables $x_1, x_2$.
$$\text{Minimize } z = f(x_1)$$subject to the restrictions
- $|x_1 - x_2| = 0$ or $6$.
- $0 \le x_1 \le 20,\ 0 \le x_2 \le 20$.
- $x_{1,2} \in \mathbb{Z}_0^+$
where
$$f(x_1) = \begin{cases} 7 + 5x_1, & \text{if } x_1 > 0. \\ 0, & \text{if } x_1 = 0. \end{cases}$$Formulate this problem as an ILP problem.”
a) Co je v zadání?
Dvě celočíselné proměnné v rozsahu $0..20$. Minimalizuje se nespojitá fixed-charge funkce $f(x_1)$ s $A = 7$, $B = 5$ (přesně funkce z výkladu). Navíc omezení, že $|x_1 - x_2|$ je buď $0$, nebo $6$ — tedy rozdíl $x_1 - x_2$ smí nabývat jen hodnot z množiny $\{-6, 0, 6\}$. Úkol: přepsat celé na čisté ILP (žádná absolutní hodnota, žádné „nebo“, žádný skok).
b) Co k tomu budeme potřebovat?
- Tato lekce — linearizace $f(x_1)$ přes $7y + 5x_1$, $x_1 \le My$.
- [L1.4] big-M: disjunkce omezení — „rozdíl je 0 NEBO ±6“ je disjunkce.
- [L0.8] Binární proměnná.
c) Jak nad úlohou uvažovat?
Rozděl si model na dvě nezávislé části. Kritérium: $f(x_1)$ je přesně fixed-charge funkce — aplikuj recept z této lekce; jaké $M$ dává mez $x_1 \le 20$? Omezení 1: pozor, $|x_1 - x_2| = 0$ or $6$ NEjsou jen dva případy! Vypiš si, jaké hodnoty smí mít rozdíl $d = x_1 - x_2$ bez absolutní hodnoty. Pak: umíš výběr jedné hodnoty z konečné množiny napsat lineárně přes binární přepínače (výčet hodnot, srov. slide 36 přednášky ILP)? Je to nový mini-trik nad rámec této lekce — naplno se rozvine v [L1.7] Po částech konstantní funkce ($\sum_k y_k = 1$), tady ho stačí přijmout z řešení. Alternativně jde každý případ zapsat dvojicí big-M nerovností à la [L1.4] s „právě jeden případ zapnutý“.
d) Úplné řešení
Kritérium (fixed-charge): zaveď $y \in \{0,1\}$, $y = 1$ ⟺ $x_1 > 0$. Protože $x_1 \le 20$, stačí $M = 20$:
$$\min z = 7y + 5x_1, \qquad x_1 \le 20\,y.$$Při minimalizaci a $7 > 0$ není potřeba $x_1 \ge y$: kombinaci $x_1 = 0, y = 1$ (cena 7 za nic) optimum nikdy nezvolí.
Omezení $|x_1 - x_2| = 0$ or $6$: rozdíl $d = x_1 - x_2$ smí být $-6$, $0$, nebo $+6$ (absolutní hodnota $6$ pokrývá OBA směry!). Nejčistší je výčet hodnot přes dva binární přepínače $s^+, s^- \in \{0,1\}$:
$$x_1 - x_2 = 6s^+ - 6s^-, \qquad s^+ + s^- \le 1.$$Kombinace $(s^+, s^-) = (0,0)$ dává rozdíl $0$, $(1,0)$ dává $+6$, $(0,1)$ dává $-6$; kombinaci $(1,1)$ zakazuje $s^+ + s^- \le 1$ (dala by sice taky rozdíl 0, ale vyloučit ji je čistší). Celý model:
$$\begin{aligned} \min z = \quad & 7y + 5x_1 \\ \text{s.t.} \quad & x_1 \le 20\,y \\ & x_1 - x_2 = 6s^+ - 6s^- \\ & s^+ + s^- \le 1 \\ & 0 \le x_1 \le 20, \;\; 0 \le x_2 \le 20 \\ & x_1, x_2 \in \mathbb{Z}_0^+, \;\; y, s^+, s^- \in \{0,1\} \end{aligned}$$Ekvivalentní cesta přes big-M: tři případy $d = v_k$, $v \in \{-6, 0, 6\}$, každý jako dvojice nerovností $v_k - M(1 - s_k) \le x_1 - x_2 \le v_k + M(1 - s_k)$ a $\sum_k s_k = 1$ — funguje stejně, jen je delší.
Poučení z reálné zkoušky: dochované studentské řešení z termínu 21.06.2021 pokrylo jen případy $d = 0$ a $d = +6$ jedinou binární proměnnou $y$ — a hodnotitel červeně připsal, že „absolutní hodnota pro 6 vyžaduje“ i záporný směr. Na $d = -6$ se zapomíná nejčastěji.
Sanity check: optimum modelu je $x_1 = 0$ (pak $y = 0$, $z = 0$) s libovolným $x_2 \in \{0, 6\}$ — skok funkce je správně „vypnutý“.
“We remind you that your formulation must be linear, i.e., no multiplication of variables, no implications, no logical expressions, etc. All non-linearities you might require, need to be linearized so that they can be written as linear expressions.”
“A company plans to produce five products. Formulate as an ILP problem. Given the following constraints, find optimal volume of each product while maximizing the profit:
- $p_i$ is the number of hours needed for one piece of product $i$
- $P$ is the company labor capacity in hours
- the volume of each product is at most 1000 pieces
- the volume of product 1 is an even number
- at least one of the following constraints holds:
- the volume of product 2 plus product 3 is at least 100
- the volume of product 4 plus product 5 is at most 200
- the income generated by one piece of product $i$ is given by $v_i$
- fixed costs (i.e. expenses that are the same for 1 piece as well as for 1000 pieces) needed to hire the machines for product $i$ are given by $f_i$
- labor cost for one piece of product $i$ is given by $c_i$
- profit is given as the sum of the incomes minus the sum of the labor and fixed costs”
a) Co je v zadání?
Výrobní plánování pěti produktů: $x_i$ = objem produktu $i$, kapacita práce $P$, mez 1000 kusů. Tři „triky“ v jednom: fixní náklady $f_i$ na pronájem strojů (tato lekce), sudost objemu produktu 1, a disjunkce „aspoň jedno ze dvou omezení platí“ ([L1.4]). Zisk = příjmy − (mzdové + fixní náklady).
b) Co k tomu budeme potřebovat?
- Tato lekce — fixní náklady $f_i y_i$ + vazba $x_i \le 1000\,y_i$.
- [L1.4] big-M: disjunkce omezení — „at least one of the following constraints holds“.
- [L1.1] Cílová funkce a základní omezení — kritérium a kapacita.
c) Jak nad úlohou uvažovat?
Projdi podmínky po jedné a každou přelož. Kritérium poskládej z bodů 6–9: co se násobí $x_i$ a co binárkou $y_i$? (Pozor na chyták z výkladu: $f_i$ se NEnásobí $x_i$.) Jakou hodnotu $M$ použiješ ve vazbě fixních nákladů, když bod 3 dává $x_i \le 1000$? Sudost: jak vynutíš „$x_1$ je sudé“ jedinou rovnicí s pomocnou celočíselnou proměnnou? Disjunkce: dvě omezení, aspoň jedno platí — kolik binárek a jaké big-M relaxace ($\ge$ vs. $\le$ se uvolňují opačným směrem!)? Jak velké musí být $M$, když $x_i \le 1000$?
d) Úplné řešení
Proměnné: $x_i \in \mathbb{Z}_0^+$ = objem produktu $i$ ($i = 1..5$); $y_i \in \{0,1\}$ = stroj na produkt $i$ je pronajatý; $u \in \mathbb{Z}_0^+$ pomocná pro sudost; $w_1, w_2 \in \{0,1\}$ přepínače disjunkce.
Kritérium (bod 9): zisk = příjmy − mzdové − fixní náklady:
$$\max z = \sum_{i=1}^{5} (v_i - c_i)\,x_i - \sum_{i=1}^{5} f_i\,y_i$$Omezení:
$$\begin{aligned} & \sum_{i=1}^{5} p_i x_i \le P && \text{(body 1–2: kapacita práce)} \\ & x_i \le 1000 && \text{(bod 3)} \\ & x_i \le 1000\,y_i && \text{(bod 7: fixed-charge vazba, } M = 1000\text{)} \\ & x_1 = 2u && \text{(bod 4: sudost)} \\ & x_2 + x_3 \ge 100 - M w_1 && \text{(bod 5a, relaxace dolů)} \\ & x_4 + x_5 \le 200 + M w_2 && \text{(bod 5b, relaxace nahoru)} \\ & w_1 + w_2 \le 1 && \text{(aspoň jedno omezení platí)} \\ & x_i, u \in \mathbb{Z}_0^+, \;\; y_i, w_1, w_2 \in \{0,1\} \end{aligned}$$Komentáře:
- Fixní náklady: recept této lekce s $M = 1000$ (mez z bodu 3). Vazba $x_i \le 1000 y_i$ vynucuje $x_i > 0 \Rightarrow y_i = 1$; opačný směr hlídá kritérium ($-f_i y_i$ při maximalizaci tlačí $y_i$ na 0, takže zbytečný pronájem optimum nevybere) — proto $x_i \ge y_i$ není nutné.
- Sudost: $x_1 = 2u$ s celočíselnou $u \ge 0$ — jediný lineární zápis bez logiky.
- Disjunkce: $w_k = 1$ znamená „omezení $k$ smí být porušeno“; $w_1 + w_2 \le 1$ nechá porušit nejvýš jedno. Omezení typu $\ge$ se uvolňuje odečtením $Mw$, typu $\le$ přičtením $Mw$. Velikost: pro 5a stačí $M \ge 100$, pro 5b musí $M \ge 1000 + 1000 - 200 = 1800$ (největší možné $x_4 + x_5$ minus 200) — bezpečně třeba $M = 2000$.