Programmazione lineare: disegnare z
Ciao a tutti,
sto studiando ricerca operativa e stavo leggendo la risoluzione di questi esercizi:https://www.mat.unical.it/~fuduli/main.pdf.
A pag. 31 parla della risoluzione grafica; quello che non ho capito è come arriva alla conclusione. Cioè so come disegnare la parte grigia ma non come disegnare la retta z (sempre se è da disegnare). Per esempio nell'esercizio 2.1 come arriva a dire tutto ciò?
Quanto alla funzione obiettivo z, il suo andamento grafico viene studiato tramite le curve di
livello, che sono ortogonali al vettore c dei costi. Nel nostro caso, poichè
$z = 2x_1 + x_2 = c^T x = [2 1] [[1],[-2]]$
allora $c^T = [2 1]$.
Una volta disegnato il vettore c (applicato nell’origine), le curve di livello
di z sono crescenti nel verso di c (e ci`o `e utile per risolvere il problema di massimizzazione) e
decrescenti nel verso opposto a quello di c (utile per risolvere il problema di minimizzazione).
Quindi la soluzione ottima del problema di massimizzazione `e il punto
$x^(*T) = [2 0]$, con $z^* = 4$, mentre la soluzione ottima del problema di minimizzazione corrisponde al punto
$x^(*T) = [-2 0]$, con $z^* = -4$.
Grazie!
sto studiando ricerca operativa e stavo leggendo la risoluzione di questi esercizi:https://www.mat.unical.it/~fuduli/main.pdf.
A pag. 31 parla della risoluzione grafica; quello che non ho capito è come arriva alla conclusione. Cioè so come disegnare la parte grigia ma non come disegnare la retta z (sempre se è da disegnare). Per esempio nell'esercizio 2.1 come arriva a dire tutto ciò?
Quanto alla funzione obiettivo z, il suo andamento grafico viene studiato tramite le curve di
livello, che sono ortogonali al vettore c dei costi. Nel nostro caso, poichè
$z = 2x_1 + x_2 = c^T x = [2 1] [[1],[-2]]$
allora $c^T = [2 1]$.
Una volta disegnato il vettore c (applicato nell’origine), le curve di livello
di z sono crescenti nel verso di c (e ci`o `e utile per risolvere il problema di massimizzazione) e
decrescenti nel verso opposto a quello di c (utile per risolvere il problema di minimizzazione).
Quindi la soluzione ottima del problema di massimizzazione `e il punto
$x^(*T) = [2 0]$, con $z^* = 4$, mentre la soluzione ottima del problema di minimizzazione corrisponde al punto
$x^(*T) = [-2 0]$, con $z^* = -4$.
Grazie!
Risposte
Ciao,
Sì, si utilizza il concetto di curve di livello (i teoremi delle funzioni implicite mi pare che siano, non ricordo quale sia la corrispondenza esatta in analisi...).
Ma quello che non dice la descrizione è che si utilizza la "direzione di massima crescita" data dal gradiente.
Ti calcoli il gradiente dato dalla funzione obiettivo e ti troverai $z$.
"vfldj":
A pag. 31 parla della risoluzione grafica; quello che non ho capito è come arriva alla conclusione. Cioè so come disegnare la parte grigia ma non come disegnare la retta z (sempre se è da disegnare). Per esempio nell'esercizio 2.1 come arriva a dire tutto ciò?
Sì, si utilizza il concetto di curve di livello (i teoremi delle funzioni implicite mi pare che siano, non ricordo quale sia la corrispondenza esatta in analisi...).
Ma quello che non dice la descrizione è che si utilizza la "direzione di massima crescita" data dal gradiente.
Ti calcoli il gradiente dato dalla funzione obiettivo e ti troverai $z$.
ah ok sono riuscita a capirlo!
Però non ho capito le condizioni di complementarietà primale-duale -.-
Il concetto è che se risolvo il duale, le soluzioni del duale sono facili da trovare e viceversa. Ma come si fa?
se ho per esempio questo esercizio in forma standard:
$max z = 8x_1 + 3x_2$
soggetto a
$4x_1 + 5x_2 + x_3 = 10$
$4x_1 + 10x_2 + x_4 = 15$
$x_2 + x_5 = 1$
$x_1, ... , x_5 >= 0$
Lo risolvo graficamente e trovo che la soluzione ottima è $x_1 = 5/2, x_2 = 0, x_3 = 0, x_4 = 5, x_5 = 1$.
Il duale è:
$min w = 10u_1 + 15u_2 + u_3$
soggetto a
$4u_1 + 4u_2 >= 8$
$5u_1 + 10u_2 + u_3 >= 3$
$u_1 >= 0$
$u_2 >= 0$
$u_3 >= 0$
$x_1, ... , x_5 >= 0$
e ora come trovo la soluzione ottima del duale con la complementarietà?
Però non ho capito le condizioni di complementarietà primale-duale -.-
Il concetto è che se risolvo il duale, le soluzioni del duale sono facili da trovare e viceversa. Ma come si fa?
se ho per esempio questo esercizio in forma standard:
$max z = 8x_1 + 3x_2$
soggetto a
$4x_1 + 5x_2 + x_3 = 10$
$4x_1 + 10x_2 + x_4 = 15$
$x_2 + x_5 = 1$
$x_1, ... , x_5 >= 0$
Lo risolvo graficamente e trovo che la soluzione ottima è $x_1 = 5/2, x_2 = 0, x_3 = 0, x_4 = 5, x_5 = 1$.
Il duale è:
$min w = 10u_1 + 15u_2 + u_3$
soggetto a
$4u_1 + 4u_2 >= 8$
$5u_1 + 10u_2 + u_3 >= 3$
$u_1 >= 0$
$u_2 >= 0$
$u_3 >= 0$
$x_1, ... , x_5 >= 0$
e ora come trovo la soluzione ottima del duale con la complementarietà?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo