Teorema debole del duale e problemi annessi
Salve ragazzi,
(è grande l'immagine vi conviene fare -> tasto destro -> visualizza immagine per vederla tutta.)
questo è una coppia di problemi (P) primale e (D) duale.
Appena sotto viene dimostrato analiticamente il teorema deole del duale :
$ x1 = 1, x2 = 4, z = 5 $
$ w1 = 0, w2 = 2, g = 10$
e quindi poi $ z = 5 <= 10 =g $
Detto questo io non sono riuscito a capire in nessun modo quei valori $ x1 = 1, x2 = 4 $ e $ w1 = 0, w2 = 2$
da dove vengono fuori e/o in che modo bisogna calcolarli.
Potreste illuminarmi ? Sarà una banalità ma al momento sono completamente perso.
Siccome non sono riuscito a capire ho deciso poi di disegnare graficamente il duale.
A questo punto mi trovo un grafico di quel tipo,
con le coordinate del primo vincolo de duale pari a (1,2 ) e del secondo vincolo (3/2 , 3/2).
Ora la zona ammissibile qual'è ?!?quella in rosso o quella in giallo ? Essendo i vincolo $ w>= 0$ ??
Confuso
Inoltre in quel grafico (con le frecce orientate ....) ho preso in considerazione i valori (che ignoro la provenienza) $ w1 = 0 $ e $ w2 = 2$ ma risultano fuori dalla/e regioni ammissibili.
Aiutatemi, sono molto confuso..
Non siate molto tecnici se no finisco per fare ancora più confusione.
Grazie!
(è grande l'immagine vi conviene fare -> tasto destro -> visualizza immagine per vederla tutta.)
questo è una coppia di problemi (P) primale e (D) duale.
Appena sotto viene dimostrato analiticamente il teorema deole del duale :
$ x1 = 1, x2 = 4, z = 5 $
$ w1 = 0, w2 = 2, g = 10$
e quindi poi $ z = 5 <= 10 =g $
Detto questo io non sono riuscito a capire in nessun modo quei valori $ x1 = 1, x2 = 4 $ e $ w1 = 0, w2 = 2$
da dove vengono fuori e/o in che modo bisogna calcolarli.
Potreste illuminarmi ? Sarà una banalità ma al momento sono completamente perso.
Siccome non sono riuscito a capire ho deciso poi di disegnare graficamente il duale.
A questo punto mi trovo un grafico di quel tipo,
con le coordinate del primo vincolo de duale pari a (1,2 ) e del secondo vincolo (3/2 , 3/2).
Ora la zona ammissibile qual'è ?!?quella in rosso o quella in giallo ? Essendo i vincolo $ w>= 0$ ??
Confuso
Inoltre in quel grafico (con le frecce orientate ....) ho preso in considerazione i valori (che ignoro la provenienza) $ w1 = 0 $ e $ w2 = 2$ ma risultano fuori dalla/e regioni ammissibili.
Aiutatemi, sono molto confuso..
Non siate molto tecnici se no finisco per fare ancora più confusione.
Grazie!
Risposte
Io ragionerei così: essendo un problema semplice si può risolvere per via grafica. Mi pare evidente che lo faccia anche lui.
Prima prende, nel duale, un generico punto ammissibile (la regione rossa, se disegnata bene, dovrebbe essere la regione ammissibile). Questo punto lo usa per calcolare il valore di $g(w)$. Ovviamente avendo preso a caso il punto $w=(0,2)$ [ammissibile perchè la regione ammissibile è data dall'insieme dei punti interni al triangolo di vertici $(0,1); (0,2); (1/2, 1)$] il valore $g(w)!= g(w^**)$
Ora prende, sempre a caso, un punto ammissibile del primale[nota]Avendo preso un punto "strettamente" interno alla regione ammissibile (non appartenente al guscio convesso) siamo sicuri non sia ottimo. Se hai studiato il simplesso ti sarà evidente.[/nota]. Calcola il valore $z(x)$, anche questo, essendo il punto non l'ottimo, porta ad un valore $z(x)!=z(x^**)$. Ora avendo costruito la f.o. $g(w)$ come duale del problema originario [nota]Il problema di minimo è evidente che sia il duale di quello di massimo, infatti: $P_1: z*=max{cx, Ax<=b, x in RR^2}$ mentre $P_2: w*=min{wb, wA>=c, w in RR^2}$[/nota] si ha che, per il teorema della dualità debole, vale:
$z(x)<=g(w)$
Questo, essendo un teorema, è sempre valido per una coppia primale-duale.
Nel nostro caso: $z(x)
A questo punto si vuole vedere se la coppia primale-duale in questione è una coppia duale forte.
Si risolve all'ottimo, per via grafica o con il simplesso [nota]Si poteva anche usare la ricerca esaustiva. Infatti sappiamo che l'ottimo di un problema di PL si trova sempre su uno spigolo della regione ammissibile. Essendo quindi noti i punti candidati ad essere ottimi (i tre vertici del triangolo) si può applicare la ricerca esaustiva.[/nota], il problema primale e si ottiene che:
$x^**=(2,6)$ e quindi $z(x^**)=7$
Allo stesso modo si risolve il problema duale e si ottiene:
$w^**=(1/2,1)$ e quindi $g(w^**)=7$
Hai dimostrato che $z(x^**)=g(w^**)$ e quindi la coppia primale-duale è una coppia duale forte.
Tutto qui!
Spero di averti aiutato. Ho studiato questi argomenti qualche semestre fa...spero che con il passare dei mesi non mi si siano confuse le idee a tal punto da scrivere qualche cavolata...
Prima prende, nel duale, un generico punto ammissibile (la regione rossa, se disegnata bene, dovrebbe essere la regione ammissibile). Questo punto lo usa per calcolare il valore di $g(w)$. Ovviamente avendo preso a caso il punto $w=(0,2)$ [ammissibile perchè la regione ammissibile è data dall'insieme dei punti interni al triangolo di vertici $(0,1); (0,2); (1/2, 1)$] il valore $g(w)!= g(w^**)$
Ora prende, sempre a caso, un punto ammissibile del primale[nota]Avendo preso un punto "strettamente" interno alla regione ammissibile (non appartenente al guscio convesso) siamo sicuri non sia ottimo. Se hai studiato il simplesso ti sarà evidente.[/nota]. Calcola il valore $z(x)$, anche questo, essendo il punto non l'ottimo, porta ad un valore $z(x)!=z(x^**)$. Ora avendo costruito la f.o. $g(w)$ come duale del problema originario [nota]Il problema di minimo è evidente che sia il duale di quello di massimo, infatti: $P_1: z*=max{cx, Ax<=b, x in RR^2}$ mentre $P_2: w*=min{wb, wA>=c, w in RR^2}$[/nota] si ha che, per il teorema della dualità debole, vale:
$z(x)<=g(w)$
Questo, essendo un teorema, è sempre valido per una coppia primale-duale.
Nel nostro caso: $z(x)
A questo punto si vuole vedere se la coppia primale-duale in questione è una coppia duale forte.
Si risolve all'ottimo, per via grafica o con il simplesso [nota]Si poteva anche usare la ricerca esaustiva. Infatti sappiamo che l'ottimo di un problema di PL si trova sempre su uno spigolo della regione ammissibile. Essendo quindi noti i punti candidati ad essere ottimi (i tre vertici del triangolo) si può applicare la ricerca esaustiva.[/nota], il problema primale e si ottiene che:
$x^**=(2,6)$ e quindi $z(x^**)=7$
Allo stesso modo si risolve il problema duale e si ottiene:
$w^**=(1/2,1)$ e quindi $g(w^**)=7$
Hai dimostrato che $z(x^**)=g(w^**)$ e quindi la coppia primale-duale è una coppia duale forte.
Tutto qui!
Spero di averti aiutato. Ho studiato questi argomenti qualche semestre fa...spero che con il passare dei mesi non mi si siano confuse le idee a tal punto da scrivere qualche cavolata...
Sei stato gentilissimo, chiaro , semplice e preciso !
Grazie ...
Non sparire , ho questo esame alle porte e avrò ancora bisogno di te
In che univeristà studi ?
Buon fine settimana !
Grazie
... Non sparire , ho questo esame alle porte e avrò ancora bisogno di te
In che univeristà studi ?
Buon fine settimana !
A Tor Vergata a Roma.
Salve, scusami se ritorno sullo stesso problema ..
Però se ho dubbi, meglio chiedere.
ecco, quì dice di $ C x >= b w$ e non viceversa.
Perchè nell'esercizio che ho scritto su ottengo che $ zx <= gw$ ?? E non viceversa ??
Ho fatto un altro esercizio e mi ritrovo cmq che il valore del duale(punto della regione ammissibile) $ gw$ è maggiore di $ zx$(punto della regione ammissibile) .
Perchè ?? Il teorema non dice il contrario $ C x >= g w $
o è connesso al fatto che il primale sia un problema di min o di max e viceversa ??
Però se ho dubbi, meglio chiedere.
ecco, quì dice di $ C x >= b w$ e non viceversa.
Perchè nell'esercizio che ho scritto su ottengo che $ zx <= gw$ ?? E non viceversa ??
Ho fatto un altro esercizio e mi ritrovo cmq che il valore del duale(punto della regione ammissibile) $ gw$ è maggiore di $ zx$(punto della regione ammissibile) .
Perchè ?? Il teorema non dice il contrario $ C x >= g w $
o è connesso al fatto che il primale sia un problema di min o di max e viceversa ??
Dipende dal fatto che prima avevi un problema primale di massimo e ora un problema di minimo.
Ovviamente se tu prendi il problema di massimo e ne fai il duale hai un problema di minimo che ti fornirà (per il concetto di bound duale) una soluzione più che ottima, ovvero "più grande".
Quindi se il primale è un problema di massimo, applicando il teorema della dualità, troverai un Upper Bound (il Lower Bound di un problema di max è una generica soluzione ammissibile) e quindi avrai che, indicando con $z(w)$ il valore della f.o. del duale, per un generico punto $w$ varrà sempre: $g(x)<=z(w)$
Se invece parti con un problema di minimo, sempre per il fatto che il teorema della dualità ti da una soluzione duale (ovvero più che ottima), otterrai un valore "più piccolo" e quindi, indicando con $h(y) $ la f.o del duale, avrai: $h(y)<=g(x)$
Ovviamente se tu prendi il problema di massimo e ne fai il duale hai un problema di minimo che ti fornirà (per il concetto di bound duale) una soluzione più che ottima, ovvero "più grande".
Quindi se il primale è un problema di massimo, applicando il teorema della dualità, troverai un Upper Bound (il Lower Bound di un problema di max è una generica soluzione ammissibile) e quindi avrai che, indicando con $z(w)$ il valore della f.o. del duale, per un generico punto $w$ varrà sempre: $g(x)<=z(w)$
Se invece parti con un problema di minimo, sempre per il fatto che il teorema della dualità ti da una soluzione duale (ovvero più che ottima), otterrai un valore "più piccolo" e quindi, indicando con $h(y) $ la f.o del duale, avrai: $h(y)<=g(x)$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo