Programmazione Lineare - Problema con il Vincolo "Almeno"
Buongiorno a tutti,
sto sviluppando un software per risolvere un problema di programmazione lineare e non riesco a trovare la rappresentazione matematica per uno dei vincoli. Prima di iniziare a sviluppare il software (che è per la società di Atletica dove gareggia mia figlia) ho dato un occhiata ai vari post e ho trovato diversi consigli. Chiedo aiuto alla comunità.
il problema è il seguente
Compilare la distinta di partecipazione alla finale selezionando i punteggi in modo tale che la loro somma dia il valore più alto.
La distinta va compilata con le seguenti regole:
Almeno 12 punteggi di competizioni diverse
Massimo 18 punteggi
Per ogni competizione è possibile presentare al più 2 punteggi
Per ogni atleta è possibile presentare al più 2 punteggi
I due punteggi presentanti dallo stesso atleta devono essere per 2 competizioni diverse
Quindi abbiamo una lista di punteggi
Punteggio 1: Salto in alto, Atleta 1, Punti: 500 ($ x_1 $)
Punteggio 2: Salto in alto, Atleta 2, Punti: 600 ($ x_2 $)
Punteggio 3: Salto in lungo, Atleta 1, Punti: 750 ($ x_3 $)
Punteggio 4: Disco, Atleta 3, Punti: 600 ($ x_4 $)
Punteggio 5: Disco, Atleta 2, Punti: 500 ($ x_5 $)
Punteggio 6: Salto in alto, Atleta 4, Punti: 700 ($ x_6 $)
ecc ecc ecc
Quello che ho fatto è stato considerare ogni punteggio come una variabile ottenendo una funzione obiettivo
$ max 500*x_1+600*x_2+750*x_3+600*x_4 + .... + m*x_n $
e poi impostato i vari vincoli sulle variabili in modo che le stesse possano assumere come valore solo 0 o 1
Vincolo sul numero massimo di punteggi presentabili nella distinta:
$ x_1+x_2+x_3+x_4+x_5+ ... + x_n<=18 $
Vincolo su ogni atleta
$ x_1+x_3 <=2 $
...
$ x_2+x_5 <=2 $
Vincolo su ogni competizione
$ x_1+x_2 + x_6 <=2 $
...
$ x_4+x_5 <=2 $
Non riesco a trovare una rappresentazione matematica sul vincolo di prendere almeno 12 competizioni diverse
Qualcuno riesce ad aiutarmi?
Grazie mille e buona giornata.
sto sviluppando un software per risolvere un problema di programmazione lineare e non riesco a trovare la rappresentazione matematica per uno dei vincoli. Prima di iniziare a sviluppare il software (che è per la società di Atletica dove gareggia mia figlia) ho dato un occhiata ai vari post e ho trovato diversi consigli. Chiedo aiuto alla comunità.
il problema è il seguente
Compilare la distinta di partecipazione alla finale selezionando i punteggi in modo tale che la loro somma dia il valore più alto.
La distinta va compilata con le seguenti regole:
Almeno 12 punteggi di competizioni diverse
Massimo 18 punteggi
Per ogni competizione è possibile presentare al più 2 punteggi
Per ogni atleta è possibile presentare al più 2 punteggi
I due punteggi presentanti dallo stesso atleta devono essere per 2 competizioni diverse
Quindi abbiamo una lista di punteggi
Punteggio 1: Salto in alto, Atleta 1, Punti: 500 ($ x_1 $)
Punteggio 2: Salto in alto, Atleta 2, Punti: 600 ($ x_2 $)
Punteggio 3: Salto in lungo, Atleta 1, Punti: 750 ($ x_3 $)
Punteggio 4: Disco, Atleta 3, Punti: 600 ($ x_4 $)
Punteggio 5: Disco, Atleta 2, Punti: 500 ($ x_5 $)
Punteggio 6: Salto in alto, Atleta 4, Punti: 700 ($ x_6 $)
ecc ecc ecc
Quello che ho fatto è stato considerare ogni punteggio come una variabile ottenendo una funzione obiettivo
$ max 500*x_1+600*x_2+750*x_3+600*x_4 + .... + m*x_n $
e poi impostato i vari vincoli sulle variabili in modo che le stesse possano assumere come valore solo 0 o 1
Vincolo sul numero massimo di punteggi presentabili nella distinta:
$ x_1+x_2+x_3+x_4+x_5+ ... + x_n<=18 $
Vincolo su ogni atleta
$ x_1+x_3 <=2 $
...
$ x_2+x_5 <=2 $
Vincolo su ogni competizione
$ x_1+x_2 + x_6 <=2 $
...
$ x_4+x_5 <=2 $
Non riesco a trovare una rappresentazione matematica sul vincolo di prendere almeno 12 competizioni diverse
Qualcuno riesce ad aiutarmi?
Grazie mille e buona giornata.
Risposte
Sinceramente non ho capito come sono stati assegnati i punteggi. In pratica ogni atleta ha associato un punteggio per la singola competizione?
Cioè la situazione è questa:
punteggio atleta 1 competizione 1= 500
punteggio atleta 1 competizione 2= 700
punteggio atleta 2 competizione 1= 400
punteggio atleta 2 competizione 2= 500
e via a seguire fino al n-esimo atleta e alla m-esima competizione?
Cioè è come se tu avessi tutti i risultati di tutti gli atleti per tutte le competizioni e ti stessi chiedendo quali presentare? Dove per presentare intendo che sono poi i risultati che "pesano" nella funzione obiettivo.
Inoltre un atleta può prendere più di un punteggio nella stessa competizione?
Cioè la situazione è questa:
punteggio atleta 1 competizione 1= 500
punteggio atleta 1 competizione 2= 700
punteggio atleta 2 competizione 1= 400
punteggio atleta 2 competizione 2= 500
e via a seguire fino al n-esimo atleta e alla m-esima competizione?
Cioè è come se tu avessi tutti i risultati di tutti gli atleti per tutte le competizioni e ti stessi chiedendo quali presentare? Dove per presentare intendo che sono poi i risultati che "pesano" nella funzione obiettivo.
Inoltre un atleta può prendere più di un punteggio nella stessa competizione?
Esattamente.
Ho una lista di risultati, ogni risultato è relativo ad una competizione ed un atleta.
Ovviamente non tutti gli atleti fanno tutte le competizioni.
Per iscriversi alla gara finale bisogna presentare massimo 18 punteggi che soddisfano i requisiti di cui sopra(
2 per competizione, 2 per atleta e almeno 7 competizioni diverse)
Nella risoluzione del problema, vengono inseriti tutti i risultati migliori di ogni atleta per ogni singola competizione per cui non mi sono posto il problema di avere più punteggi per lo stesso atleta nella singola competizione.
Grazie
Ciro
Ho una lista di risultati, ogni risultato è relativo ad una competizione ed un atleta.
Ovviamente non tutti gli atleti fanno tutte le competizioni.
Per iscriversi alla gara finale bisogna presentare massimo 18 punteggi che soddisfano i requisiti di cui sopra(
2 per competizione, 2 per atleta e almeno 7 competizioni diverse)
Nella risoluzione del problema, vengono inseriti tutti i risultati migliori di ogni atleta per ogni singola competizione per cui non mi sono posto il problema di avere più punteggi per lo stesso atleta nella singola competizione.
Grazie
Ciro
In ogni caso, se ho capito il problema, una prima idea potrebbe essere:
$max \sum_{i=1}^nsum_{j=1}^m c_(i,j) x_(i,j)$
$ text(s.t.)$
$\sum_{i=1}^nsum_{j=1}^m x_(i,j)<=18$
$sum_{i=1}^n x_(i,j)<=2 text( j=1,...,m)$
$sum_{j=1}^m x_(i,j)<=2 text( i=1,...,n)$
$sum_{i=1}^n x_(i,j)>=y_j text( j=1,...,m)$
$sum_{j=1}^m y_j>=12 $
$x_(i,j) in {0,1} text( i=1,...,n j=1,....,m)$
$y_j in {0,1} text( j=1,....,m)$
Nell'ordine il primo vincolo è quello sul numero massimo di punteggi da presentare, il secondo impedisce di presentare più di due punteggi per la stessa competizione, il terzo dice che ogni atleta al massimo può presentare due punteggi, il quarto (se funzionasse) permetterebbe di contare se la competizione j-esima è stata "scelta" almeno una volta, il quinto sfrutta il calcolo precedente e dice che devono essere presenti almeno 12 (o quante ne vuoi) competizioni. I punteggi li metti in una matrice $C$ il cui elemento $c_(i,j)$ rappresenta il punteggio per l'atleta i-esimo per quanto riguarda la j-esima competizione.
Questo è quanto, in un primo momento, mi viene in mente. Eventualmente fammi notare i punti critici, magari non me ne sono accorto ma ci sono!
$max \sum_{i=1}^nsum_{j=1}^m c_(i,j) x_(i,j)$
$ text(s.t.)$
$\sum_{i=1}^nsum_{j=1}^m x_(i,j)<=18$
$sum_{i=1}^n x_(i,j)<=2 text( j=1,...,m)$
$sum_{j=1}^m x_(i,j)<=2 text( i=1,...,n)$
$sum_{i=1}^n x_(i,j)>=y_j text( j=1,...,m)$
$sum_{j=1}^m y_j>=12 $
$x_(i,j) in {0,1} text( i=1,...,n j=1,....,m)$
$y_j in {0,1} text( j=1,....,m)$
Nell'ordine il primo vincolo è quello sul numero massimo di punteggi da presentare, il secondo impedisce di presentare più di due punteggi per la stessa competizione, il terzo dice che ogni atleta al massimo può presentare due punteggi, il quarto (se funzionasse) permetterebbe di contare se la competizione j-esima è stata "scelta" almeno una volta, il quinto sfrutta il calcolo precedente e dice che devono essere presenti almeno 12 (o quante ne vuoi) competizioni. I punteggi li metti in una matrice $C$ il cui elemento $c_(i,j)$ rappresenta il punteggio per l'atleta i-esimo per quanto riguarda la j-esima competizione.
Questo è quanto, in un primo momento, mi viene in mente. Eventualmente fammi notare i punti critici, magari non me ne sono accorto ma ci sono!
Intanto grazie per la risposta.
La funzione obiettivo e i primi 3 vincoli sono esattamente quello che ho implementato e descritto nel mio post originale.
Questo mi conforta... Se siamo in 2 vuol dire che sono sulla buona strada.
Il vincolo 4 e 5 mi sembrano OK.
Li implemento e ti do un feedback
Grazie ancora
Ciro
La funzione obiettivo e i primi 3 vincoli sono esattamente quello che ho implementato e descritto nel mio post originale.
Questo mi conforta... Se siamo in 2 vuol dire che sono sulla buona strada.
Il vincolo 4 e 5 mi sembrano OK.
Li implemento e ti do un feedback
Grazie ancora
Ciro
Nonostante sulla carta mi sembra tutto perfetto, quando aggiungo i vincoli 4 e 5 al programma che ho implementato lo stesso non riesce a trovare una soluzione ottima.
Omettendo i due vincoli sopra citati, il programma restituisce il risultato atteso
Sapete dove posso trovare un risolutore di simplesso online?
Per verificare che non sia il mio algoritmo a fallire?
Grazie
Omettendo i due vincoli sopra citati, il programma restituisce il risultato atteso
Sapete dove posso trovare un risolutore di simplesso online?
Per verificare che non sia il mio algoritmo a fallire?
Grazie
Guarda io ho provato ad usare AMPL (è a pagamento ma puoi trovare una versione di prova qui) e mi sembra che funzioni. Ti allego i file .mod e .dat da modificare (ho inserito 10 atleti e 15 competizioni con punteggi 1-10) e da fare risolvere dal solutore Cplex.
competizioni.dat
competizioni.mod
Una volta scaricato AMPL inserisci i due file nella stessa cartella dove vedi tutti i solutori. Apri ampl.exe e poi dovrai scrivere:
reset;
model competizioni.mod;
data competizioni.dat;
option solver "./Cplex";
solve;
per vedere il risultato:
display punteggi;
display x;
display y;
Provaci modificando il file .dat e fammi sapere...
competizioni.dat
competizioni.mod
Una volta scaricato AMPL inserisci i due file nella stessa cartella dove vedi tutti i solutori. Apri ampl.exe e poi dovrai scrivere:
reset;
model competizioni.mod;
data competizioni.dat;
option solver "./Cplex";
solve;
per vedere il risultato:
display punteggi;
display x;
display y;
Provaci modificando il file .dat e fammi sapere...
Grazie mille!
Appena posso ci provo.
Appena posso ci provo.
Ho provato con i dati in mio possesso ed in effetti il modello è perfetto!
A questo punto devo rivedere l'algoritmo del simplesso che ho implementato con il php essendo la mia un'applicazione web.
Grazie mille per le preziosissime indicazioni.
Saluti
A questo punto devo rivedere l'algoritmo del simplesso che ho implementato con il php essendo la mia un'applicazione web.
Grazie mille per le preziosissime indicazioni.
Saluti
"cirisiamo":
Ho provato con i dati in mio possesso ed in effetti il modello è perfetto!
A questo punto devo rivedere l'algoritmo del simplesso che ho implementato con il php essendo la mia un'applicazione web.
Grazie mille per le preziosissime indicazioni.
Saluti
Mi fa piacere che funzioni...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo