(Primale -> Duale) Problemi ammissibilità
Salve,
chiedo scusa per non essermi ancora presentato nella giusta sezione, ma risolvendo questo esercizio mi è sorto un dubbio che non sono riuscito ancora a risolvere.
Premetto che ho già cercato sul web e ,di conseguenza anche, nel vostro forum, ma sono riuscito a trovare qualcosa che mi potesse essere d'aiuto.
Il dubbio, così atroce da chiedere aiuto
, è il seguente:
Ho un primale P di un problema di programmazione lineare e un punto X. A questo punto X corrisponde una soluzione AMMISSIBILE di base.
L'esercizio richiede di calcolare il duale D del problema P e controllare, tramite le relazioni di scarto complementare (complementary slackness), se a questo punto corrisponde una soluzione ottima.
Ho scritto il suo duale, solo che quando vado a calcolare il valore delle variabili duali, una di queste mi esce con un valore inammissibile (deve essere >= 0, ma esce < 0). Il fatto che esca questo valore vuole dire che al punto X non corrisponde una sol. ottima? Oppure è il fatto che questa variabile duale mi esca con un valore inammissibile è qualcosa che NON può uscire, cioè "matematicamente/logicamente" sbagliato?!
Ho più volte controllato i calcoli e i passaggi, ma non ho trovato errori.
Spero di essere stato il più chiaro possibile e che avete capito il mio dubbio.
chiedo scusa per non essermi ancora presentato nella giusta sezione, ma risolvendo questo esercizio mi è sorto un dubbio che non sono riuscito ancora a risolvere.
Premetto che ho già cercato sul web e ,di conseguenza anche, nel vostro forum, ma sono riuscito a trovare qualcosa che mi potesse essere d'aiuto.
Il dubbio, così atroce da chiedere aiuto
, è il seguente:Ho un primale P di un problema di programmazione lineare e un punto X. A questo punto X corrisponde una soluzione AMMISSIBILE di base.
L'esercizio richiede di calcolare il duale D del problema P e controllare, tramite le relazioni di scarto complementare (complementary slackness), se a questo punto corrisponde una soluzione ottima.
Ho scritto il suo duale, solo che quando vado a calcolare il valore delle variabili duali, una di queste mi esce con un valore inammissibile (deve essere >= 0, ma esce < 0). Il fatto che esca questo valore vuole dire che al punto X non corrisponde una sol. ottima? Oppure è il fatto che questa variabile duale mi esca con un valore inammissibile è qualcosa che NON può uscire, cioè "matematicamente/logicamente" sbagliato?!
Ho più volte controllato i calcoli e i passaggi, ma non ho trovato errori.
Spero di essere stato il più chiaro possibile e che avete capito il mio dubbio.
Risposte
Il duale e primale sono entrambi ammissibili solo in un ottimo del problema. Quindi il duale può benissimo essere inammissibile e perciò la sol. in X non ottima.
D'altronde se il primale è di minimo, il duale è di massimo e la regione ammissibile per quest'ultimo limita inferiormente le soluzioni del primale: va da sé che se in un punto entrambi sono ammissibili il punto è un ottimo.
D'altronde se il primale è di minimo, il duale è di massimo e la regione ammissibile per quest'ultimo limita inferiormente le soluzioni del primale: va da sé che se in un punto entrambi sono ammissibili il punto è un ottimo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo