Rapinatore

Un rapinatore si introduce furtivamente in una gioielleria avendo a disposizione un sacco con capacità di 8 chili. Trova a portata di mano 6 oggetti il cui valore $v_i$ in migliaia di è rispettivamente: 7, 2, 4, 5, 4 e 1; il loro peso $p_i$ invece è rispettivamente di 5, 3, 2, 3, 1 e 1 chili. Potendo utilizzare il solo sacco a disposizione per trasportare la refurtiva, il ladro vuole effettuare la scelta di oggetti che massimizzi il valore complessivo. Possiamo rappresentare il problema in due modi. Un primo modo è di tipo insiemistico. Sia $O=\{1,2,3,4,5,6\}$, la nostra variabile decisionale è data dall'insieme $S \subseteq O$; vogliamo trovare un sottoinsieme $S$ tale che $\sum_{i \in S} p_i \leq 8$, e che massimizzi $\sum_{i \in S} v_i$ . In alternativa, utilizzando variabili matematiche, possiamo introdurre una variabile di scelta $x_i$ per ogni oggetto $i\in O$ che vale 1 se e solo se l'oggetto i viene scelto e 0 altrimenti. Le variabili decisionali sono di tipo ``logico", ovvero per ogni oggetto dobbiamo decidere se includerlo o meno nella soluzione: $x_i$ varrà 1 se l'oggetto $i\in S$ e 0 altrimenti. In questo modo il problema viene rappresentato dal seguente modello:

$$\begin{eqnarray*} \max &7x_1 + 2x_2 + 4x_3 + 5x_4 + 4x_5 + x_6\\ & 5 x_1 + 3 x_... ... x_4 + x_ 5 + x_6 \leq 8\\ &x_i \in \{0,1\} ,& i = 1, \ldots, 6 \end{eqnarray*}$$

A volte si ha la necessità di effettuare una scelta tra un insieme finito di valori, pertanto la variabile che rappresenta tale scelta non rientra in nessuna delle categorie menzionate sopra e parliamo di variabile a valori discreti. Il contesto tipico è quello delle reti di telecomunicazione.