Problema di Assegnamento

uni
Un problema di Assegnamento è un Problema di Programmazione Lineare (PL), è infatti un caso particolare del Problema di Trasporto, pertanto, essendo a sua volta caso particolare del Problema di Programmazione Matematica a Reti non Capacitate (PLRnC), gode del Teorema di Interezza.

	progetti	IS	CS	TI	AB
		1	2	3	4
ditte
1		20	18	16	14
2		22	16	19	15
3		21	17	15	23
4		19	18	14	24
Un gruppo bancario deve far fare 4 progetti ed indice un bando al quale partecipano 4 aziende, ogni azienda quota un prezzo per ogni progetto. Per ogni progetto ci vuole un mese, e ogni azienda può fare un solo progetto alla volta.

Modello Matematico non cooperativo

$$\{\begin{array}{l}\min {\sum }_i{\sum }_j{c}_{ij}\cdot x_{ij}\\ {\sum }_i{x}_{ij}=1\forall j\in N\\ {\sum }_j{x}_{ij}=1\forall i\in N\\ x_{ij}\in \{0,1\}\end{array}$$

se lo si vuole cooperativo basta sostituire l’ultimo vincolo con $x_{ij}\in [0,1]$
esempio per N=4:

$$\{\begin{array}{l}min{C}^{T}x\\ X_{1,1}+X_{1,2}+X_{1,3}+X_{1,4}=1\\ ...\\ X_{1,1}+X_{2,1}+X_{3,1}+X_{4,1}=1\\ ...\\ X_{i,j}\ge 0\end{array}$$

quindi

$$\{\begin{array}{l}min{c}^{T}x\\ \left(\begin{array}{c}1..1|0..0|..|0..0\\ 0..0|1..1|0..0|..|0..0\\ ..\\ 0..0|0..0|..|0..0|1..1\\ 010.00|010.00|..|010..0\\ 0010..0|0010..0|..|0010..0\\ ..\\ 0..01|0..01|..|0..01\\ -10..0|0..0|..|0..0\\ 0-10..0|0..0|..|0..0\\ ..\\ 0..0|0..0|..|0..0-1\end{array}\right)\cdot \left(\begin{array}{c}{x}_{11}\\ x_{12}\\ ..\\ x_{1n}\\ x_{21}\\ x_{22}\\ ..\\ x_{2n}\\ ..\\ \\ \\ x_{nn}\end{array}\right)\le \left(\begin{array}{c}1\\ 1\\ 1\\ 1\\ ..\\ 1\\ 1\\ ..\\ -1\\ -1\\ ..\\ -1\end{array}\right)\end{array}$$

Variabili

Considerato un generico assegnamento $a,b,c,d$ , dove ditta 1 fa progetto $a$, 2 fa $b$ eccetera.
Il numero totale di permutazioni possibili è $n!=4!=24$.
Consideriamo la variabile $X_{i,j}=\{\begin{array}{l}0seinonfaj\\ 1seifaj\end{array}$
Le $X_{i,j}$ possibili sono $4\cdot 4=16$
Una soluzione si può dunque scrivere come ogni $X_{i,j}$ nell’ordine $X_{1,1},X_{1,2},...,X_{2,1}$
quindi una soluzione possibile è $X=(101...0)$

Funzione obiettivo

$$min{C}^{T}x=min20X_{1,1}+18X_{1,2}+16X_{1,3}+14X_{1,4}+22X_{2,1}+...+24X_{4,4}$$

dove $C$ è il vettore dei costi.

Vincoli

Ogni azienda può fare un solo progetto, quindi per ogni ditta:
$X_{1,1}+X_{1,2}+X_{1,3}+X_{1,4}=1$
Ogni progetto deve essere fatto da una ditta, quindi per ogni progetto:
$X_{1,1}+X_{2,1}+X_{3,1}+X_{4,1}=1$
Se il problema è cooperativo dobbiamo specificare che $X_{i,j}\ge 0$, e questo problema lo è.

Dimensioni

Considerato un problema con $n$ entità ed $n$ “progetti”:

$$\{\begin{array}{l}min{C}^{T}x\\ Ax\le b\\ x\ge 0\end{array}$$

$x\in R^{16}$
$b\in R^8$
$A\in M^{16,16}$

Cooperativo vs Non Cooperativo

Nei problemi di assegnamento, e solo in quelli di assegnamento, per ogni soluzione cooperativa ce ne è una non cooperativa, quindi sono lo stesso problema, ed è indipendente quale dei due risolvo.

Numero di Variabili e Vincoli nella Forma Primale Standard

dati $i$ operatori e $j$ progetti
Numero di Variabili: $i\cdot j$
Numero di Vincoli: $i\cdot j+2i+2j$