Algoritmo di selezione
Ho un problema di ottimizzazione, una volta tanto non di analisi matematica.
Si tratta di trovare un algoritmo per risolvere il seguente problema.
Abbiamo una collezione di oggetti di valore, $o_1, \ldots, o_n$ e una collezione di persone $p_1,\ldots,p_m$.
Ogni oggetto di valore ha, naturalmente, un suo valore $v_j \in \{1, 2, 3\}$; inoltre, ogni oggetto di valore ha un cartellino sul quale compaiono uno o più nomi delle persone di cui sopra, che sono le uniche che se ne possono appropriare.
Abbiamo poi una quantità illimitata di oggetti inutili, che possono essere presi da chiunque, ma hanno un valore nullo.
Ogni persona deve prendere esattamente due oggetti, da scegliersi fra quelli di valore che riportano anche il suo nome sul cartellino oppure fra quelli inutili.
Ad ogni configurazione di scelta degli oggetti si assegna un punteggio dato dalla somma dei punteggi di tutti gli oggetti presi.
Si vuole trovare la configurazione che massimizzi questo punteggio.
Si tratta di trovare un algoritmo per risolvere il seguente problema.
Abbiamo una collezione di oggetti di valore, $o_1, \ldots, o_n$ e una collezione di persone $p_1,\ldots,p_m$.
Ogni oggetto di valore ha, naturalmente, un suo valore $v_j \in \{1, 2, 3\}$; inoltre, ogni oggetto di valore ha un cartellino sul quale compaiono uno o più nomi delle persone di cui sopra, che sono le uniche che se ne possono appropriare.
Abbiamo poi una quantità illimitata di oggetti inutili, che possono essere presi da chiunque, ma hanno un valore nullo.
Ogni persona deve prendere esattamente due oggetti, da scegliersi fra quelli di valore che riportano anche il suo nome sul cartellino oppure fra quelli inutili.
Ad ogni configurazione di scelta degli oggetti si assegna un punteggio dato dalla somma dei punteggi di tutti gli oggetti presi.
Si vuole trovare la configurazione che massimizzi questo punteggio.
Risposte
mi sa che non ho capito bene... perchè se c'è la possibilità di portare via tutti gli oggetti che hanno un valore allora si ottiene il punteggio massimo per forza, altrimenti bisogna portare via il maggior numero di oggetti di valore massimo.
Mi sa che ho interpretato male come si assegna il valore di una configurazione, o sbaglio
? puoi chiarirlo?
grazie
Mi sa che ho interpretato male come si assegna il valore di una configurazione, o sbaglio
? puoi chiarirlo?grazie
Chiaramente, ogni configurazione che permetta di portare via tutti gli oggetti di valore è ottimale.
In generale, però questo non è possibile.
Ad esempio, se gli oggetti di valore hanno tutti il cartellino con un solo stesso nome, quella persona potrà portare via due fra gli oggetti di valore massimo mentre tutti gli altri porteranno via solo oggetti inutili.
La situazione diventa complicata quando, invece, gli oggetti hanno nomi multipli.
Chiaramente, converrà ad esempio assegnare in prima istanza gli oggetti a tutte le persone che compaiono in al più due cartellini (tanto più di quegli oggetti di valore loro non possono portare via, e intanto quelli sono sistemati).
Non mi è chiaro però che tipo di algoritmo usare in generale.
In generale, però questo non è possibile.
Ad esempio, se gli oggetti di valore hanno tutti il cartellino con un solo stesso nome, quella persona potrà portare via due fra gli oggetti di valore massimo mentre tutti gli altri porteranno via solo oggetti inutili.
La situazione diventa complicata quando, invece, gli oggetti hanno nomi multipli.
Chiaramente, converrà ad esempio assegnare in prima istanza gli oggetti a tutte le persone che compaiono in al più due cartellini (tanto più di quegli oggetti di valore loro non possono portare via, e intanto quelli sono sistemati).
Non mi è chiaro però che tipo di algoritmo usare in generale.
E’ possibile formulare un modello in programmazione lineare intera (binaria) del problema.
Dati del problema
1) il vettore dei valori $c_{i}$ di ciascun oggetto di dimensione $n$ pari al numero degli oggetti di valore.
2) la matrice binaria $P_{i,j}$ di dimensione $n x m$ dove l’elemento $P_{i,j}=1$ se il nome della persona $j$ figura sul cartellino dell’oggetto $i$. La numerosità delle persone è $m$.
Variabili decisionali
1) $x_{i,j}$ matrice binaria di dimensione $n x m$ dove l’elemento $x_{i,j}=1$ se l’oggetto $i$ è assegnato alla persona $j$, $0$ altrimenti. La variabile $x_{i,j}$ va definita solo se $P_{i,j}=1$, in modo che solo le persone che figurano sul cartellino di un certo oggetto possano essere gli assegnatari dell’oggetto.
2) $y_{i}$ vettore binario di dimensione $n$, in cui $y_{i}=1$ se l’oggetto è stato assegnato, $0$ altrimenti.
Vincoli
1) La somma di ciascuna riga della matrice $x_{i,j}$ è uguale alla variabile $y_{i}$.
2) La somma di ciascuna colonna della matrice $x_{i,j}$ deve essere minore o uguale a $2$.
Funzione obiettivo da massimizzare: il valore totale degli oggetti assegnati.
Il modello che proporrei è quindi il seguente:
[tex]$\begin{align}
& \max z=\sum\limits_{i=1}^{n}{{{c}_{i}}{{y}_{i}}} \\
& s.t.\left\{ \begin{array}{*{35}{l}}
(1) & {{y}_{i}}=\sum\limits_{j=1}^{m}{{{x}_{i,j}}} & i=1..n \\
(2) & \sum\limits_{i=1}^{n}{{{x}_{i,j}}}\le 2 & j=1..m \\
(3) & {{x}_{i,j}}=0/1 & i=1..n,j=1..m \\
(4) & {{y}_{i}}=0/1 & i=1..n \\
\end{array} \right. \\
\end{align}$[/tex]
che mi sembra facilmente implementabile con qualche risolutore free o proprietario (l'ho provato con la versione studente di XPRESS).
La configurazione della soluzione ottima potrebbe non essere unica, nel senso che il massimo della funzione obiettivo potrebbe essere realizzato da diverse assegnazioni degli oggetti.
Certo, in questo modo si utilizza il risolutore come una “black box”, credo che utilizzerà metodi come il Branch & Bound o dei Piani di taglio.
Se si cerca un algoritmo ad hoc, si può pensare a qualche metodo euristico per avere almeno una soluzione sub-ottimale.
La ricerca di un algoritmo ottimale non mi sembra proprio immediata (se non altro, perchè altrimenti il problema non starebbe in questa sezione
).
Dati del problema
1) il vettore dei valori $c_{i}$ di ciascun oggetto di dimensione $n$ pari al numero degli oggetti di valore.
2) la matrice binaria $P_{i,j}$ di dimensione $n x m$ dove l’elemento $P_{i,j}=1$ se il nome della persona $j$ figura sul cartellino dell’oggetto $i$. La numerosità delle persone è $m$.
Variabili decisionali
1) $x_{i,j}$ matrice binaria di dimensione $n x m$ dove l’elemento $x_{i,j}=1$ se l’oggetto $i$ è assegnato alla persona $j$, $0$ altrimenti. La variabile $x_{i,j}$ va definita solo se $P_{i,j}=1$, in modo che solo le persone che figurano sul cartellino di un certo oggetto possano essere gli assegnatari dell’oggetto.
2) $y_{i}$ vettore binario di dimensione $n$, in cui $y_{i}=1$ se l’oggetto è stato assegnato, $0$ altrimenti.
Vincoli
1) La somma di ciascuna riga della matrice $x_{i,j}$ è uguale alla variabile $y_{i}$.
2) La somma di ciascuna colonna della matrice $x_{i,j}$ deve essere minore o uguale a $2$.
Funzione obiettivo da massimizzare: il valore totale degli oggetti assegnati.
Il modello che proporrei è quindi il seguente:
[tex]$\begin{align}
& \max z=\sum\limits_{i=1}^{n}{{{c}_{i}}{{y}_{i}}} \\
& s.t.\left\{ \begin{array}{*{35}{l}}
(1) & {{y}_{i}}=\sum\limits_{j=1}^{m}{{{x}_{i,j}}} & i=1..n \\
(2) & \sum\limits_{i=1}^{n}{{{x}_{i,j}}}\le 2 & j=1..m \\
(3) & {{x}_{i,j}}=0/1 & i=1..n,j=1..m \\
(4) & {{y}_{i}}=0/1 & i=1..n \\
\end{array} \right. \\
\end{align}$[/tex]
che mi sembra facilmente implementabile con qualche risolutore free o proprietario (l'ho provato con la versione studente di XPRESS).
La configurazione della soluzione ottima potrebbe non essere unica, nel senso che il massimo della funzione obiettivo potrebbe essere realizzato da diverse assegnazioni degli oggetti.
Certo, in questo modo si utilizza il risolutore come una “black box”, credo che utilizzerà metodi come il Branch & Bound o dei Piani di taglio.
Se si cerca un algoritmo ad hoc, si può pensare a qualche metodo euristico per avere almeno una soluzione sub-ottimale.
La ricerca di un algoritmo ottimale non mi sembra proprio immediata (se non altro, perchè altrimenti il problema non starebbe in questa sezione
).
@cenzo:
ti ringrazio molto per il tuo contributo.
In effetti speravo si potesse escogitare un algoritmo ad hoc di facile implementazione; in mancanza di questo, vedrò se esiste qualche libreria free di ottimizzazione facilmente utilizzabile per implementare il problema come da te suggerito.
ti ringrazio molto per il tuo contributo.
In effetti speravo si potesse escogitare un algoritmo ad hoc di facile implementazione; in mancanza di questo, vedrò se esiste qualche libreria free di ottimizzazione facilmente utilizzabile per implementare il problema come da te suggerito.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo