\documentclass[a4paper]{report}
\usepackage{graphics}
\usepackage[applemac]{inputenc}
\setlength{\oddsidemargin}{-.5cm}
\setlength{\textwidth}{17.5cm}
\setlength{\textheight}{25cm}
\setlength{\topmargin}{-1cm}
\pagestyle{myheadings}

\begin{document}

\noindent
Il Dipartimento di Informatica intende assegnare $n$ diversi lavori di preparazione di pagine web a $m$ ($m < n$) cooperative di studenti di Informatica. La cooperativa $j$, per effettuare il lavoro $i$, richiede al Dipartimento un pagamento di $c_{ij}$ Euro, $i = 1, \ldots, n, \ j = 1, \ldots, m$.
Inoltre, per ragioni di riservatezza, per ogni lavoro $i$, $i=1, \ldots, n$, si conosce l'insieme $C(i)$ dei lavori che possono essere effettuati assieme ad $i$ dalla stessa cooperativa (ovviamente, se $h \in C(i)$ allora $i \in C(h)$).
Il Dipartimento intende assegnare i lavori delle pagine web alle cooperative al minimo costo con la garanzia di assegnare almeno un lavoro ad ogni cooperativa e facendo s{\`\i} che alla stessa cooperativa siano assegnati solo lavori compatibili. Formulare in termini di P.L.I.  il problema del Dipartimento.
\bigskip

\noindent{\bf SVOLGIMENTO}

\hfill

\noindent
Introduciamo le seguenti $nm$ variabili logiche:
\[
x_{ij} = \left\{
   \begin{array}{ll}
    1, & \mbox{se il lavoro } i \mbox{ \`e assegnato alla cooperativa $j$,} \\
    0, & \mbox{altrimenti,}
   \end{array}\right. \quad \quad i = 1, \ldots , n,  \quad j=1, \ldots , m.
\]

\bigskip

I vincoli di semiassegnamento che garantiscono che ogni lavoro sia
assegnato ad una ed una sola cooperativa sono:

\[
\sum_{j=1}^{m} x_{ij} = 1, \quad \quad \quad \quad \quad i = 1, \ldots,
n.
\]

Per garantire che ad ogni cooperativa sia assegnato almeno un lavoro, introduciamo i seguenti vincoli di copertura:

\[
\sum_{i=1}^{n} x_{ij} \geq 1, \quad \quad \quad \quad \quad j = 1, \ldots,
m.
\]

Per garantire che alla stessa cooperativa siano assegnati solo lavori compatibili tra loro (lavori che possono essere effettuati assieme), definiamo, come struttura di dati in input, l'insieme $L$ di tutte le coppie di lavori incompatibili, cio\`e lavori che non possono essere assegnati alla stessa cooperativa:
%
\[
L = \{(i,h): i=1,\ldots,n-1, h > i \ \mbox{  e  } \ h \notin C(i)\};
\]
(la condizione $h>i$ viene utilizzata per evitare di inserire in $L$ la stessa coppia due volte).
Mediante l'insieme $L$ delle coppie incompatibili, possiamo garantire che alla stessa coppia siano assegnati solo lavori compatibili in quanto si impedisce di assegnare alla stessa cooperativa coppie di lavori incompatibili:
%
\[
x_{ij} + x_{hj} \leq 1, \quad \quad \quad (i,h) \in L, \quad j = 1,\dots,m.
\]

La funzione obiettivo, da minimizzare, \`e data dal costo totale di
assegnamento: 
%
\[
\displaystyle{\sum_{i=1}^{n}}\displaystyle{\sum_{j=1}^{m}}
c_{ij}x_{ij}.
\]

La formulazione del problema \`e quindi
%
\begin{eqnarray*}
\begin{array}{rrlll}
\min & \displaystyle{\sum_{i=1}^{n}}\displaystyle{\sum_{j=1}^{m}}
c_{ij}x_{ij} \\ \\
      & \displaystyle{\sum_{j=1}^{m}} x_{ij} & = & 1 & i = 1,\ldots, n \\ \\
      & \displaystyle{\sum_{i=1}^{n}} x_{ij} & \geq & 1 & j = 1,\ldots, m \\ \\
      & x_{ij} + x_{hj}& \leq & 1 & (i,h) \in L, \quad j=1,\ldots , m \\ \\
      & x_{ij} & \in & \{0,1\} & i=1,\ldots,n, \quad j=1,\ldots , m
\end{array}
\end{eqnarray*}

\end{document}
