Search
Jste správci rozlohou velké oblasti s množstvím měst s hustou sítí silnic. Každodenní správcovské povinnosti už vás ale nebaví a chtěli byste práci delegovat na několik svých zástupců. Je proto třeba rozdělit celé panství na několik stejně velkých regionů, každý z nich bude řídit jeden zástupce.
Cílem je najít rozdělení původní oblasti na maximálně autonomní regiony tj. s minimálním propojením mezi regiony.
Počet cest mezi městy z jiného regionu
<latex> \begin{equation*} f(s) = \sum_{l\in V_i, k\in V_j,i\neq j}e_{lk} \end{equation*} </latex>
Tato funkce je minimalizována.
U této úlohy dává dobrý smysl řešit úlohu s omezením jako multikriteriální:
Přeměna omezení na kritérium 2 by nám možná mohla umožnit najít hodně autonomní regiony, které nejsou přibližně stejně velké.