Problema di programmazione lineare
Salve a tutti ho tra le mani un problema di programmazione lineare che mi sta dando parecchi dubbi eppure io non penso sia così difficile:
In una corsa di cavalli partecipano quattro cavalli A, B, C e D. Uno scommettitore ha deciso di giocare esattamente 57€ in questa corsa.
Le quote dell'allibratore sono:
Il problema consiste nel ripartire la somma a disposizione tra i quattro cavalli in modo da rendere massima la vincita nel caso peggiore. Si formuli questo problema come un problema di programmazione lineare.
PREMESSA:
Dato che devo ripartire la somma a disposizione in modo tale da rendere massima la vincita nel caso peggiore, penso sia ovvio che devo puntare almeno 1€ su ogni cavallo, perchè se puntassi 0€ su uno dei quattro cavalli automaticamente (penso) romperei il vincolo sopra citato.
esempio:
punto su i cavalli B, C e D. Dopo la gara vince A quanto avrei vinto? 0€. Se avessi puntato anche su A avrei portato a casa sicuramente almeno 3€.
funzione di costo:
ponendo $x_1 ... x_4$ come il quantitativo di € che punto su ogni cavallo ottengo:
$max : 3x_1+4x_2+5x_3+6x_4$
mentre i vincoli sono:
${ ( x_1+x_2+x_3+x_4<=57 ),( 1<=x_1<=57 ),( 1<=x_2<=57 ),( 1<=x_3<=57 ),( 1<=x_4<=57 ):}$
secondo voi è corretto ciò che ho fatto? magari manca qualcosa al mio ragionamento?
grazie
In una corsa di cavalli partecipano quattro cavalli A, B, C e D. Uno scommettitore ha deciso di giocare esattamente 57€ in questa corsa.
Le quote dell'allibratore sono:
CAVALLO--->QUOTA
A--->3/1
B--->4/1
C--->5/1
D--->6/1
A--->3/1
B--->4/1
C--->5/1
D--->6/1
Il problema consiste nel ripartire la somma a disposizione tra i quattro cavalli in modo da rendere massima la vincita nel caso peggiore. Si formuli questo problema come un problema di programmazione lineare.
PREMESSA:
Dato che devo ripartire la somma a disposizione in modo tale da rendere massima la vincita nel caso peggiore, penso sia ovvio che devo puntare almeno 1€ su ogni cavallo, perchè se puntassi 0€ su uno dei quattro cavalli automaticamente (penso) romperei il vincolo sopra citato.
esempio:
punto su i cavalli B, C e D. Dopo la gara vince A quanto avrei vinto? 0€. Se avessi puntato anche su A avrei portato a casa sicuramente almeno 3€.
funzione di costo:
ponendo $x_1 ... x_4$ come il quantitativo di € che punto su ogni cavallo ottengo:
$max : 3x_1+4x_2+5x_3+6x_4$
mentre i vincoli sono:
${ ( x_1+x_2+x_3+x_4<=57 ),( 1<=x_1<=57 ),( 1<=x_2<=57 ),( 1<=x_3<=57 ),( 1<=x_4<=57 ):}$
secondo voi è corretto ciò che ho fatto? magari manca qualcosa al mio ragionamento?
grazie
Risposte
Non credo sia corretto perché non tieni conto che solo un cavallo vince mentre il tuo $max$ assume che tutti i cavalli siano vincenti ...
Cordialmente, Alex
Cordialmente, Alex
hai ragione,
potrei riscrivere $max$ come:
dove $A, B, C, D$ sono i 4 cavalli rappresentati da una variabile che puo assumere $0, 1$
quindi se vincesse il cavallo A allora $A=1, B=0, C=0, D=0$
e via dicendo nel caso vincesse il cavallo B oppure C o D
quindi il mio $max$ ora ti dice quanto vinceresti ipotizzando che vinca il cavallo A, oppure B, C o D.
che ne dici?
potrei riscrivere $max$ come:
$max : 3Ax_1+4Bx_2+5Cx_3+6Dx_4$
dove $A, B, C, D$ sono i 4 cavalli rappresentati da una variabile che puo assumere $0, 1$
quindi se vincesse il cavallo A allora $A=1, B=0, C=0, D=0$
e via dicendo nel caso vincesse il cavallo B oppure C o D
quindi il mio $max$ ora ti dice quanto vinceresti ipotizzando che vinca il cavallo A, oppure B, C o D.
che ne dici?
... mmm ... non so ... quello che dici è giusto, ma allora tanto vale fare direttamente quattro simulazioni con i quattro casi cioè $max=3x_1$ o $max=4x_2$ o ...
Cordialmente, Alex
Cordialmente, Alex
Cosa significa caso peggiore? Minimizzare le perdite?
Io penso che debba essere $3x_1=4x_2=5x_3=6x_4$
da cui abbiamo $x_1+3/4x_1+3/5x_1+1/2x_1=57\ =>\ (20+15+12+10)/20x_1=57\ =>\ 57/20x_1=57$ e perciò $x_1=20$ e poi gli altri ...
In questo modo vinci sempre $3$ euro ... però non so se questo significa "... rendere max la vincita nel caso peggiore ... non mi è chiaro ... a me
Cordialmente, Alex
Io penso che debba essere $3x_1=4x_2=5x_3=6x_4$
da cui abbiamo $x_1+3/4x_1+3/5x_1+1/2x_1=57\ =>\ (20+15+12+10)/20x_1=57\ =>\ 57/20x_1=57$ e perciò $x_1=20$ e poi gli altri ...
In questo modo vinci sempre $3$ euro ... però non so se questo significa "... rendere max la vincita nel caso peggiore ... non mi è chiaro ... a me
Cordialmente, Alex
giusto, ma allora la funzione obiettivo qual'è ?
Non ne ho la minima idea ... 
Quello che ho capito però è che valori diversi da quelli nel caso peggiore ti portano ad una vincita minore, e questo mi pare fosse l'obiettivo ...
Cordialmente, Alex
Quello che ho capito però è che valori diversi da quelli nel caso peggiore ti portano ad una vincita minore, e questo mi pare fosse l'obiettivo ...
Cordialmente, Alex
Poniamo $z$ come la vincita nel peggiore dei casi.
In tal modo noi dobbiamo trovare
abbiamo $4$ quote: $[q_1...q_4]$ sulla quale utilizziamo un tot. del nostro budget $[x_1...x_4]$
Dato che $q_ix_i$ ci da la vincita, bisogna trovare un modo per il quale ci dia la vincita nel caso peggiore e cioè $z$.
quindi:
dove $min q_ix_i$ è la vincita minore (caso peggiore)
e qui arriva la domanda che ci siamo posti prima... ma la funzione obiettivo?
la funzione obiettivo è (proprio per il ragionamento fatto):
Che bisogna "trasformare" in un problema di programmazione lineare.
Sapendo che $z$ è la vincita nel caso peggiore e che vale $min q_ix_i$ è possibile riscriverla in questo modo (sotto forma di vincoli)
${ ( z<=q_1x_1 ),( z<=q_2x_2 ),( z<=q_3x_3 ),( z<=q_4x_4 ):}$
In questo modo $z$ dovrà (per rispettare tutti i vincoli) corrispondere alla vincita minore, sei d'accordo? e cioè alla vincità nel caso peggiore.
ora aggiungiamo anche il vincolo del budget e otteniamo:
${ ( z<=q_1x_1 ),( z<=q_2x_2 ),( z<=q_3x_3 ),( z<=q_4x_4 ), (x_1+x_2+x_3+x_4<=57):}$
Noi pero la vogliamo massimizzare e quindi, in questo modo, ci basterà massimizzare la stessa $z$ che, per definizione corrisponde a massimizzare la vincita nel peggiore dei casi.
inserendo il problema in un qualsiasi risolutore si ottiene:
di cui l'output è:
In tal modo noi dobbiamo trovare
$max z$
abbiamo $4$ quote: $[q_1...q_4]$ sulla quale utilizziamo un tot. del nostro budget $[x_1...x_4]$
Dato che $q_ix_i$ ci da la vincita, bisogna trovare un modo per il quale ci dia la vincita nel caso peggiore e cioè $z$.
quindi:
$z=min q_ix_i$
dove $min q_ix_i$ è la vincita minore (caso peggiore)
e qui arriva la domanda che ci siamo posti prima... ma la funzione obiettivo?
la funzione obiettivo è (proprio per il ragionamento fatto):
$max z = max min q_ix_i$
Che bisogna "trasformare" in un problema di programmazione lineare.
Sapendo che $z$ è la vincita nel caso peggiore e che vale $min q_ix_i$ è possibile riscriverla in questo modo (sotto forma di vincoli)
${ ( z<=q_1x_1 ),( z<=q_2x_2 ),( z<=q_3x_3 ),( z<=q_4x_4 ):}$
In questo modo $z$ dovrà (per rispettare tutti i vincoli) corrispondere alla vincita minore, sei d'accordo? e cioè alla vincità nel caso peggiore.
ora aggiungiamo anche il vincolo del budget e otteniamo:
${ ( z<=q_1x_1 ),( z<=q_2x_2 ),( z<=q_3x_3 ),( z<=q_4x_4 ), (x_1+x_2+x_3+x_4<=57):}$
Noi pero la vogliamo massimizzare e quindi, in questo modo, ci basterà massimizzare la stessa $z$ che, per definizione corrisponde a massimizzare la vincita nel peggiore dei casi.
inserendo il problema in un qualsiasi risolutore si ottiene:
Maximize[{z,
x1+x2+x3+x4<=57&&
z-3x1 <=0&&
z-4x2<=0&&
z-5x3<=0&&
z-6x4<=0},
{x1,x2,x3,x4,z}]
di cui l'output è:
{60,{x1->20,x2->15,x3->12,x4->10,z->60}}
Per quel che ne so mi sembra che sia ... ottimo. Quasi. Manca solo la condizione che le quote debbano essere maggiori di zero.
Cordialmente, Alex
Cordialmente, Alex
hai ragione mi sono dimenticato.
non le quote ma $x_1...x_4$ cioe quello che punta il pover'uomo che scommette sui cavalli
non le quote ma $x_1...x_4$ cioe quello che punta il pover'uomo che scommette sui cavalli
Sì, scusa, intendevo le puntate ...
Cordialmente, Alex
P.S.: cosa intendi per "qualsiasi risolutore" ? Cosa hai usato ?
Cordialmente, Alex
P.S.: cosa intendi per "qualsiasi risolutore" ? Cosa hai usato ?
intendo un software in grado di risolvere problemi di programmazione lineare e tanti altri.
Per esempio Matlab.
In realtà il compito assegnatomi voleva che lo usassi e che rappresentassi un modello matematico idoneo per poterlo risolvere con il programma.
In realtà problemi di quel genere si possono anche risolvere a mano anche se ci vuole parecchio tempo per problemi con molte variabili.
Ma comunque risolvibili a mano per esempio con il metodo del simplesso (piu che metodo e' un algoritmo).
I programmi che risolvono problemi di programmazione lineare ad essere pignoli non usano quell'algoritmo in quanto inefficiente.
Per esempio Matlab.
In realtà il compito assegnatomi voleva che lo usassi e che rappresentassi un modello matematico idoneo per poterlo risolvere con il programma.
In realtà problemi di quel genere si possono anche risolvere a mano anche se ci vuole parecchio tempo per problemi con molte variabili.
Ma comunque risolvibili a mano per esempio con il metodo del simplesso (piu che metodo e' un algoritmo).
I programmi che risolvono problemi di programmazione lineare ad essere pignoli non usano quell'algoritmo in quanto inefficiente.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo