Ammissibilità del duale
Riporto un estratto del mio libro di testo:
Consideriamo un problema p.l. nella forma
$z=c^Tx$ Min!
s.a
${(Ax=b),(x>=0):}$
Si supponga che sia disponibile una forma canonica iniziale nella quale tutti i coefficienti di costo modificati siano non negativi (ammissibilità duale rispettata).
La frase tra parentesi non l'ho capita... perché se i coefficienti di costo modificati sono non negativi dovrebbe essere rispettata l'ammissibilità del duale?
Consideriamo un problema p.l. nella forma
$z=c^Tx$ Min!
s.a
${(Ax=b),(x>=0):}$
Si supponga che sia disponibile una forma canonica iniziale nella quale tutti i coefficienti di costo modificati siano non negativi (ammissibilità duale rispettata).
La frase tra parentesi non l'ho capita... perché se i coefficienti di costo modificati sono non negativi dovrebbe essere rispettata l'ammissibilità del duale?
Risposte
invece di darti la risposta, ti propongo di scrivere il duale e fare direttamente la verifica.
ciao
Franco
ciao
Franco
Il duale si scrive facilmente ed è il seguente
$v = b^T u$ Max!
s.a
$A^T u >= c$
dove le variabili $u_j$ sono non vincolate nel segno
Una cosa che vorrei capire bene è la seguente: una soluzione ammissibile di un problema p.l. rispetta l'ammissibilità del duale se il vettore dei moltiplicatori ad essa associato è una soluzione ammissibile del duale?
Questo fatto è sicuramente vero all'ottimo del diretto. Può essere vero anche per soluzioni del diretto non ottime?
$v = b^T u$ Max!
s.a
$A^T u >= c$
dove le variabili $u_j$ sono non vincolate nel segno
Una cosa che vorrei capire bene è la seguente: una soluzione ammissibile di un problema p.l. rispetta l'ammissibilità del duale se il vettore dei moltiplicatori ad essa associato è una soluzione ammissibile del duale?
Questo fatto è sicuramente vero all'ottimo del diretto. Può essere vero anche per soluzioni del diretto non ottime?
Esatto!
penso che tu abbia studiato il metodo del simplesso con il tableau classico di Dantzig che risolve i problemi in forma standard:
min cx
s.t. Ax=b
x>= 0
Esiste un altra versione del tableau che risolve i problemi in forma canonica
max cx
s.t. Ax=
che permette delle risposte semplici alle tue domande, in quanto sulla stessa tabella hai, ad ogni passo, la rappresentazione del duale e del primale.
Lo puoi trovare su:
L.Muracchini, L.Guidotti Programmazione matematica - UTET
G.Owen Game Theory - Academic Press
ciao
Franco
penso che tu abbia studiato il metodo del simplesso con il tableau classico di Dantzig che risolve i problemi in forma standard:
min cx
s.t. Ax=b
x>= 0
Esiste un altra versione del tableau che risolve i problemi in forma canonica
max cx
s.t. Ax=
che permette delle risposte semplici alle tue domande, in quanto sulla stessa tabella hai, ad ogni passo, la rappresentazione del duale e del primale.
Lo puoi trovare su:
L.Muracchini, L.Guidotti Programmazione matematica - UTET
G.Owen Game Theory - Academic Press
ciao
Franco
Purtroppo non utilizzo quel libro di testo e non ho modo di consultarlo. Sto studiando Ricerca Opeativa dal testo "Programmazione Lineare" di Gennaro Improta.
Per la trasformazione diretto-duale uso la tabella di Tucker, che permette di trasformare qualunque problema p.l. nel corrispondente duale.
La cosa che non mi è chiara è il nesso tra i moltiplicatori di una soluzione di base ammissibile del diretto e le variabili del problema duale. Potresti dirmi qualcosa in più a riguardo?
Per inciso, i moltiplicatori li ho incontrati nel capitolo del simplesso revisionato e non ho ben capito che significato concreto abbiano.
Per la trasformazione diretto-duale uso la tabella di Tucker, che permette di trasformare qualunque problema p.l. nel corrispondente duale.
La cosa che non mi è chiara è il nesso tra i moltiplicatori di una soluzione di base ammissibile del diretto e le variabili del problema duale. Potresti dirmi qualcosa in più a riguardo?
Per inciso, i moltiplicatori li ho incontrati nel capitolo del simplesso revisionato e non ho ben capito che significato concreto abbiano.
Se i coefficienti di costo modificati sono non negativi, allora deve risultare
$c^T - pi^T A >=0 => c^T >= pi^T A => pi^T A <= c^T => A^T pi <= c$
mentre, affinché sia rispettata l'ammissibilità del duale, dovrebbe risultare
$A^T pi >= c$
Dov'è l'errore?
$c^T - pi^T A >=0 => c^T >= pi^T A => pi^T A <= c^T => A^T pi <= c$
mentre, affinché sia rispettata l'ammissibilità del duale, dovrebbe risultare
$A^T pi >= c$
Dov'è l'errore?
Sinceramente, non mi sono mai posto il problema di invertire un problema non ottimo.
Devo pensarci un po'.
Devo pensarci un po'.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo