\documentstyle[11pt,amssymb,italian]{article}
\setlength{\hoffset}{-10pt}
\setlength{\voffset}{-10pt}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\topmargin}{0pt}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6in}
\pagestyle{empty}
\linespread{1.2}

\begin{document} 

{\bf Soluzione esercizio 1.1.4} 

\noindent
Per risolvere il problema basta determinare quali macchinari 
noleggiare. Infatti, se abbiamo noleggiato i macchinari $i$ e $j$ 
(con $j>i$) ma nessun altro tra i macchinari $i+1, ... , j-1$, tutti 
i capi di vestiario larghi al pi\`u $a_j$ e almeno $a_{i+1}$ dovranno 
essere tessuti utilizzando il macchinario $j$; anche i capi di 
larghezza al pi\`u $a_{i}$ possono essere tessuti con lo stesso macchinario 
ma \`e meno costoso tesserli con il macchinario $i$ poich\`e 
$C_i < C_j$. Quindi serviranno esattamente $D_{i+1}+ ... + D_j$ 
rotoli di larghezza $a_j$.  

Questa osservazione suggerisce come formulare il problema: per ogni 
coppia $i,j$ con $i<j$ introduciamo $x_{ij}$ la variabile decisionale 
che vale 1 se si noleggiano i macchinari $i$ e $j$ ma nessun altro tra i
macchinari $i+1, ... , j-1$ e vale 0 altrimenti; si osservi che questa
definizione ha perfettamente senso anche per $i=0$ ($x_{0j}=1$
significa che si \`e noleggiato il macchinario $j$ ma nessun macchinario
$i$ con $i<j$). Le variabili cos\`\i\ introdotte corrispondono agli 
archi del grafo orientato aciclico completo $(N,A)$ dove 
$$N=\{0,1,...,n \}, \ \ \ \ 
A=\{ \ (i,j) \ : \ i < j, \ i=0,...,n, \ j=1,...,n \ \}.$$
Senza perdere di generalit\`a, possiamo supporre che $D_n > 0$ e di 
conseguenza il macchinario $n$ deve essere comunque noleggiato. 
Quindi, ad ogni soluzione del nostro problema corrisponde un cammino 
orientato dal nodo $0$ al nodo $n$ e viceversa ad ogni siffatto
cammino corrisponde una soluzione del nostro problema. Perci\`o, introducendo
opportunamente i costi sugli archi, possiamo ricondurre il nostro
problema alla determinazione del cammino da $0$ ad $n$ di costo minimo: 
se $x_{ij}=1$, allora il costo relativo al macchinario $j$ risulta 
essere la somma di $K_j$ (costo di noleggio) e di $C_j (D_{i+1}+ ... +D_j)$ 
(costo dei rotoli di larghezza $a_j$ necessari); basta quindi porre
$c_{ij}=C_j (D_{i+1}+ ... +D_j)+K_j$. La formulazione del nostro problema 
come problema di cammino minimo \`e cos\`\i\ completata: 
$$   
\begin{array}{l}
\min \ \ \displaystyle{\sum_{i<j}} \ c_{ij} x_{ij} \\
\displaystyle{\sum_{i<j}} \ x_{ij} - 
\displaystyle{\sum_{i>j}} \ x_{ij} = 
\cases{ -1 & \ se \ $i=0$ \cr \hspace*{3mm} 0 & \ se  \ $i=1,..., n-1$ \cr
\hspace*{3mm} 1 & \ se \ $i=n$} \\ 
 \\
x_{ij} \in \{ 0,1 \}. 
\end{array}
$$

\hfill 

\hfill 

\noindent
Una formulazione alternativa, forse pi\`u intuitiva ma che conduce 
ad un problema di Programmazione Matematica pi\`u difficile da
risolvere, \`e la seguente: sia $y_j$ la variabile decisionale che 
vale 1 se si noleggia il macchinario $j$ e vale 0 altrimenti e sia 
$x_{ij}$ la variabile quantitativa che indica quanti rotoli di
larghezza $j$ verranno utilizzati per tessere capi di vestiario di 
larghezza al pi\`u $a_i$ e maggiore di $a_{i-1}$; ovviamente bisogna  
considerare le variabili $x_{ij}$ solo per le coppie di indici 
con $j \ge i$. 
Il costo totale per il noleggio dei macchinari \`e dato da  
$$\displaystyle{\sum_{j=1}^{n}} \ K_j y_j.$$
Il costo di acquisto dei rotoli di larghezza $j$ risulta essere 
$$C_j \displaystyle{\sum_{i \le j}} \ x_{ij}.$$
Quindi la funzione da minimizzare \`e data da 
$$\displaystyle{\sum_{j=1}^{n}} \ (K_j y_j + 
C_j \displaystyle{\sum_{i \le j}} \ x_{ij}).$$
Affinch\`e tutti i capi di vestiario vengano tessuti, deve essere
$$\displaystyle{\sum_{j \le i}} \ x_{ij} = D_i  \ \ \ \ i=1,...,n.$$
Inoltre, capi di larghezza non superiore a $j$ possono venir tessuti 
dal macchinario $j$ solo se questi \`e stato noleggiato:  
$$\displaystyle{\sum_{i \le j}} \ x_{ij} \le M y_j$$
dove $M$ \`e una opportuna costante; ad esempio, si pu\`o scegliere il 
numero totale di rotoli necessari a confezionare tutti i capi di larghezza 
non superiore a $j$ 
$$M = \displaystyle{\sum_{i \le j}} \ D_i.$$ 
Imponendo che le variabili $x_{ij}$ siano interi non negativi, 
la formulazione \`e completa: 
$$\begin{array}{ll}
\vspace*{3mm}\min \ \ \displaystyle{\sum_{j=1}^{n}} \ 
(K_j y_j + C_j \displaystyle{\sum_{i \le j}} \ x_{ij}) \\
\vspace*{3mm}\displaystyle{\sum_{j \le i}} \ x_{ij} = D_i & 
\hspace*{-10mm}i=1,...,n \\
\vspace*{2mm}\displaystyle{\sum_{i \le j}} \ x_{ij} \le  
(\displaystyle{\sum_{i \le j}} \ D_i) y_j  & \hspace*{-10mm}j=1,...,n \\ 
x_{ij} \ge 0 & \hspace*{-10mm}j \ge i, \ \ i=1,...,n \\ 
x_{ij} \in {\mathbb{Z}} & \hspace*{-10mm}j \ge i, \ \ i=1,...,n \\ 
y_j \in \{ 0,1 \} & \hspace*{-10mm}j=1,...,n.
\end{array}$$

\end{document}



