Ricerca Operativa 1
Non capisco perché la risposta al seguente quesito sia che le variabili da considerare
non devono essere più di 8... Per me sono 12...
Si abbia il seguente problema di Programmazione Lineare:
$"Max "2x_1+3x_2+4x_3+5x_4+6x_5
$" "x_1+3x_2+2x_3+x_4-2x_5>=22
$" "-2x_1+2x_2+x_3-2x_4+3x_5<=34
$" "x_1,x_2,x_3,x_4,x_5" qualsiasi"
Qual è il minimo numero di variabili da considerare
affinché si abbia un PL equivalente con restrizioni di positività
su tutte le variabili e vincoli soltanto di uguaglianza?
La mia risposta è 12, mentre il libro dice che non sono più di 8,
e di motivare la risposta... Boh!
non devono essere più di 8... Per me sono 12...
Si abbia il seguente problema di Programmazione Lineare:
$"Max "2x_1+3x_2+4x_3+5x_4+6x_5
$" "x_1+3x_2+2x_3+x_4-2x_5>=22
$" "-2x_1+2x_2+x_3-2x_4+3x_5<=34
$" "x_1,x_2,x_3,x_4,x_5" qualsiasi"
Qual è il minimo numero di variabili da considerare
affinché si abbia un PL equivalente con restrizioni di positività
su tutte le variabili e vincoli soltanto di uguaglianza?
La mia risposta è 12, mentre il libro dice che non sono più di 8,
e di motivare la risposta... Boh!
Risposte
Per trasformare un sistema con vincoli di $<=$ o $>=$, in un sistema con vincoli di uguaglianza stretta, è sufficiente aggiungere una variabile "slack" in ogni vincolo.
In pratica, il senso è questo:
Se il vincolo $a$ impone che $x_1+3x_2+2x_3+x_4-2x_5>=22$, posso inserire una variabile $x_6$ fittizia che misuri lo "scarto". In questo caso, le variabili aggiunte vengono chiamate variabili "surplus".
Quindi, posso trasformare il vincolo $a$ in:
$x_1+3x_2+2x_3+x_4-2x_5-x_6=22$
Il significato della variabile $x_6$ è di fondamentale importanza nella ricerca operativa: generalmente, un vincolo rappresenta la quantità utilizzabile di una risorsa scarsa.
Il valore che la variabile $x_6$ assume, nella soluzione ottimale, è la quantità "avanzata" di risorsa.
Se, al contrario, la variabile slack vale 0, significa che il vincolo è "attivo", quindi è effettivamente vincolante per la soluzione, cioè la soluzione giace su un vertice generato da questo vincolo.
Quanto detto vale per i vincoli di maggioranza; al contrario, per i vincoli di minoranza, bisognerà aggiungere, invece che sottrarre, la variabile slack.
Il problema sorge quando il testo chiede di trasformare le variabili non vincolate in variabili non negative.
Il sistema usato generalmente è la sostituzione di ogni variabile non vincolata nella differenza tra due variabili positive: $x_i=v_i-u-i$.
Pertanto, sono necessarie 10 variabili standard e due variabili slack (una slack e una surplus).
In assenza di altre condizioni, non saprei come "diminuire" il numero di variabili.
Purtroppo, non riesco ad esserti più di tanto di aiuto...
In pratica, il senso è questo:
Se il vincolo $a$ impone che $x_1+3x_2+2x_3+x_4-2x_5>=22$, posso inserire una variabile $x_6$ fittizia che misuri lo "scarto". In questo caso, le variabili aggiunte vengono chiamate variabili "surplus".
Quindi, posso trasformare il vincolo $a$ in:
$x_1+3x_2+2x_3+x_4-2x_5-x_6=22$
Il significato della variabile $x_6$ è di fondamentale importanza nella ricerca operativa: generalmente, un vincolo rappresenta la quantità utilizzabile di una risorsa scarsa.
Il valore che la variabile $x_6$ assume, nella soluzione ottimale, è la quantità "avanzata" di risorsa.
Se, al contrario, la variabile slack vale 0, significa che il vincolo è "attivo", quindi è effettivamente vincolante per la soluzione, cioè la soluzione giace su un vertice generato da questo vincolo.
Quanto detto vale per i vincoli di maggioranza; al contrario, per i vincoli di minoranza, bisognerà aggiungere, invece che sottrarre, la variabile slack.
Il problema sorge quando il testo chiede di trasformare le variabili non vincolate in variabili non negative.
Il sistema usato generalmente è la sostituzione di ogni variabile non vincolata nella differenza tra due variabili positive: $x_i=v_i-u-i$.
Pertanto, sono necessarie 10 variabili standard e due variabili slack (una slack e una surplus).
In assenza di altre condizioni, non saprei come "diminuire" il numero di variabili.
Purtroppo, non riesco ad esserti più di tanto di aiuto...
Ti ringrazio lo stesso...
Cosa intendi per
"Se, al contrario, la variabile slack vale 0, significa
che il vincolo è "attivo", quindi è effettivamente vincolante
per la soluzione, cioè la soluzione giace su un vertice generato da questo vincolo."
?
Cosa intendi per
"Se, al contrario, la variabile slack vale 0, significa
che il vincolo è "attivo", quindi è effettivamente vincolante
per la soluzione, cioè la soluzione giace su un vertice generato da questo vincolo."
?
Se, nella soluzione del problema, la variabile slack vale 0, la risorsa è interamente utilizzata.
Facciamo un esempio semplice:
$max z=5x_1+10x_2
$" "10x_1+5x_2<=25
$" "4x_1+10x_2<=20
$" "x_1+1.5x_2<=4.5
$" "x_1,x_2>=0$
La soluzione di questo problema è:
$x_1=1.875
$x_2=1.25
$z=21.875
Come puoi notare, la soluzione è l'intersezione tra il primo e il secondo vincolo.
Se provi a trasformare questo problema in un problema standard, vedrai che le variabili slack relative ai primi due vincoli valgono 0. Questo significa che le risorse associate ai due vincoli saranno utilizzate per intero.
Queste risorse vengono definite "scarse".
La variazione della disponibilità di una variabile scarsa comporta la variazione della soluzione del problema.
Al contrario, una variabile non scarsa ha un "campo di variabilità" all'interno del quale la soluzione non varia.
Questi brevi concetti sono fondamentali quando vedrai la dualità e il teorema della complementary slackness.
Ad esempio, la variabilità della soluzione in funzione del variare di una risorsa determina il "valore" della risorsa scarsa.
Puoi tranquillamente immaginare quante possano essere le applicazioni nel campo dell'economia...
In generale, si deve vedere il sistema dato dai vincoli come lo parte di spazio n-dimensionale (dove n è il numero di variabili) in cui può essere compresa la soluzione.
Non è difficile immaginare che la soluzione, massima o minima che sia, deve trovarsi su un vertice dello spazio ammissibile.
Questo vertice è dato dall'intersezione dei vincoli attivi.
Per questo, molti algoritmi cercano la soluzione spostandosi direttamente da un vertice all'altro.
Facciamo un esempio semplice:
$max z=5x_1+10x_2
$" "10x_1+5x_2<=25
$" "4x_1+10x_2<=20
$" "x_1+1.5x_2<=4.5
$" "x_1,x_2>=0$
La soluzione di questo problema è:
$x_1=1.875
$x_2=1.25
$z=21.875
Come puoi notare, la soluzione è l'intersezione tra il primo e il secondo vincolo.
Se provi a trasformare questo problema in un problema standard, vedrai che le variabili slack relative ai primi due vincoli valgono 0. Questo significa che le risorse associate ai due vincoli saranno utilizzate per intero.
Queste risorse vengono definite "scarse".
La variazione della disponibilità di una variabile scarsa comporta la variazione della soluzione del problema.
Al contrario, una variabile non scarsa ha un "campo di variabilità" all'interno del quale la soluzione non varia.
Questi brevi concetti sono fondamentali quando vedrai la dualità e il teorema della complementary slackness.
Ad esempio, la variabilità della soluzione in funzione del variare di una risorsa determina il "valore" della risorsa scarsa.
Puoi tranquillamente immaginare quante possano essere le applicazioni nel campo dell'economia...
In generale, si deve vedere il sistema dato dai vincoli come lo parte di spazio n-dimensionale (dove n è il numero di variabili) in cui può essere compresa la soluzione.
Non è difficile immaginare che la soluzione, massima o minima che sia, deve trovarsi su un vertice dello spazio ammissibile.
Questo vertice è dato dall'intersezione dei vincoli attivi.
Per questo, molti algoritmi cercano la soluzione spostandosi direttamente da un vertice all'altro.
Ma come faccio a vedere che la variabile di slack verrà 0?
Devi risolvere il problema...
Ah... No, io non sono ancora arrivato a studiare gli
algoritmi di risoluzione (ho letto più volte
del celeberrimo simplesso)... Ecco perché.
Pensavo esistesse un modo per vederlo dall'inizio.
algoritmi di risoluzione (ho letto più volte
del celeberrimo simplesso)... Ecco perché.
Pensavo esistesse un modo per vederlo dall'inizio.
No. Però, se ti può interessare, leggendo quanto ho scritto nel mio ultimo post, potresti essere in grado di risolvere il problema esempio che ho posto.
Anzi, facciamo così, te ne do un altro:
$min z=30x_1+48x_2$
$" "1/2x_1+x_2>=3$
$" "x_1+4x_2>=7$
$" "2x_1+2x_2>=13/2$
$" "x_1,x_2>=0$
Vediamo se ti viene in mente qualche idea.
Tra qualche minuto, se non hai ancora avuto idee, ti posto qualche suggerimento.
Anzi, facciamo così, te ne do un altro:
$min z=30x_1+48x_2$
$" "1/2x_1+x_2>=3$
$" "x_1+4x_2>=7$
$" "2x_1+2x_2>=13/2$
$" "x_1,x_2>=0$
Vediamo se ti viene in mente qualche idea.
Tra qualche minuto, se non hai ancora avuto idee, ti posto qualche suggerimento.
Ti ringrazio molto, ma non ho ancora cominciato a
studiare metodi di risoluzione...
studiare metodi di risoluzione...
Puoi sempre inventarne uno...
Primo suggerimento:
Primo suggerimento:
"Cheguevilla":Il numero di variabili nel problema che ho postato non è casuale.
In generale, si deve vedere il sistema dato dai vincoli come lo parte di spazio n-dimensionale (dove n è il numero di variabili) in cui può essere compresa la soluzione.
Mah, saranno i punti estremi del politopo individuato
dai vincoli a dare la soluzione ottima, penso...
dai vincoli a dare la soluzione ottima, penso...
Che cosa rappresenta la funzione obiettivo, dal punto di vista matematico?
Beh è un piano in $RR^3$...
E in $RR^2$?
In $RR^2$ fissato z rappresenta una retta...
Eheheh, ci stai girando attorno...
Considerando z un parametro?
Considerando z un parametro?
Un fascio di rette.
Bene.
Il parametro z, cosa rappresenta analiticamente?
Il parametro z, cosa rappresenta analiticamente?
il valore della funzione...
Vero.
E il suo significato in termini di "geometria analitica"?
E il suo significato in termini di "geometria analitica"?
Ah, ecco, allora avevo inteso bene, volevi dire
"geometricamente" invece che "analiticamente"...
Boh, non credo che abbia un significato geometrico preciso...
"geometricamente" invece che "analiticamente"...
Boh, non credo che abbia un significato geometrico preciso...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo