• quando P ha molti vincoli e poche variabili naturali. In generale è sempre meglio trovarsi nella situazione inversa, perché il tempo di calcolo dell'algoritmo del simplesso è maggiormente influenzato dal numero di vincoli che da quello delle variabili. Buttiamola sul pratico: ho un problema con 2 variabili e 100 vincoli, che nel caso peggiore risolvo con 100 passaggi di pivot. Passiamo al duale: ho 100 variabili e 2 vincoli, che nel caso peggiore richiede due passi di pivot per trovare l'ottimo

(:cell align=center:)valori ottimi delle variabili corrispondenti

(:cellnr align=center:)prezzi ombra dei vincoli (:cell align=center:)valori ottimi delle corrispondenti variabili

Adesso mettiamo alla prova tutti questi teoremi da un punto di vista algoritmico. Dato che i coefficienti di P e D sono sempre gli stessi (ma trasposti), entrambi i problemi si possono rappresentare e riconoscere nello stesso tableau. Mettiamo alla prova questa affermazione considerando il seguente esempio, preso sempre dalle slide di Righini:

Questa proprietà è ancora più evidente nel tableau ristretto, ovvero privato della matrice identità e costi ridotti corrispondenti:

Che ce ne facciamo di questa proprietà? Ne possiamo ricavare qualche vantaggio? Certo, perché abbiamo dimostrato che è possibile eseguire sul tableau del primale gli stessi passi di pivot che l'algoritmo del simplesso eseguirebbe su quello del duale. Questa estensione dell'algoritmo prende intuitivamente il nome di algoritmo del simplesso duale, che ha come caratteristica quella di conservare l'ottimalità della soluzione fino a raggiungere l'ammissibilità. Le regole di scelta del pivot sono ovvviamente duali rispetto all'algoritmo convenzionale, quindi:

• il pivot deve essere negativo
• bisogna scegliere la riga col termine noto più negativo
• bisogna scegliere la colonna che minimizza il rapporto tra il coefficiente di costo ridotto e il pivot

Quando diventa utile utilizzare l'algoritmo del simplesso duale? Fondamentalmente in due casi:

• quando P ha molti vincoli e poche variabili naturali. In generale è sempre meglio trovarsi nella situazione inversa, perché il tempo di calcolo dell'algoritmo del simplesso è maggiormente influenzato dal numero di vincoli che da quello delle variabili
• quando la soluzione di base iniziale non è ammissibile per il primale. In questo caso infatti l'algoritmo del simplesso duale può sostituire la fase di inizializzazione, a patto però che la soluzione iniziale sia ammissibile per D

Arriviamo infine al teorema fondamentale della dualità, che ci dice che data una coppia di problemi lineari duali P e D, esiste una sequenza finita di passi di pivot (quindi dell'algoritmo del simplesso) che termina al verificarsi di uno di questi quattro casi:

• soluzione ottima di P e D (finita e coincidente)
• P è illimitato e D è inammissibile
• D è illimitato e P è inammissibile
• P e D sono entrambi inammissibili

C'è un ultimo teorema chiamato teorema dello scarto complementare, che dice che la condizione necessaria e sufficiente per l'ottimalità di x' appartenente a X e di y' appartenente a Y è: (:table cellspacing=10 cellpadding=10:) (:cellnr bgcolor=#f2f6f9:)y'^T (A * x' - b) = 0 (:cell:)dove (A * x' - b) è la variabile di slack (:cellnr bgcolor=#f2f6f9:)(c - y'^T * A) x' = 0 (:cell:)dove (c - y'^T * A) è la variabile di surplus (:tableend:)

In altre parole il prodotto della variabile di un problema P per la variabile di slack del corrispondente vincolo nel problema duale è nullo in tutte le soluzioni di base.
Perché ciò sia vero devono essere verificate entrambe le soluzioni. Notare che questo teorema si applica solo alle variabili non negative, per il semplice motivo che quelle libere non hanno variabili di slack corrispondenti nel duale.

A cosa serve aver definito cos'è il duale di un problema di programmazione lineare? A sfruttare alcune sue proprietà espresse da una serie di teoremi, il primo dei quali è il teorema della dualità in forma debole.
Il teorema dice che dati due problemi duali:\\

(:title Ricerca Operativa - Dualità:) Torna alla pagina di Ricerca Operativa

:: Ricerca Operativa - Dualità ::

Dualità

Ogni problema di programmazione lineare ammette un corrispondente problema lineare detto duale. Chiamiamo il primo primale (P) e il secondo duale (D).
Dato un problema in forma alle disuguaglianze, vediamo le corrispondenze con il suo duale:

(:table cellpadding=8 align=center width=60%:) (:cellnr bgcolor=#d4e1f0 align=center width=50%:)Primale (:cell bgcolor=#d4e1f0 align=center:)Duale (:cellnr align=center:)minimizzazione (:cell align=center:)massimizzazione (:cellnr align=center bgcolor=#f2f6f9:)m vincoli (:cell align=center bgcolor=#f2f6f9:)m variabili (:cellnr align=center:)n variabili (:cell align=center:)n vincoli (:cellnr align=center bgcolor=#f2f6f9:)coefficienti funzione obiettivo (:cell align=center bgcolor=#f2f6f9:)termini noti (:cellnr align=center:)termini noti (:cell align=center:)coefficienti funzione obiettivo (:cellnr align=center bgcolor=#f2f6f9:)matrice A (:cell align=center bgcolor=#f2f6f9:)matrice A^T (:cellnr align=center:)vincoli di uguaglianza (:cell align=center:)variabili libere (:cellnr align=center bgcolor=#f2f6f9:)variabili libere (:cell align=center bgcolor=#f2f6f9:)vincoli di uguaglianza (:cellnr align=center:)vincoli di disuguaglianza (:cell align=center:)variabili non negative (:cellnr align=center bgcolor=#f2f6f9:)variabili non negative (:cell align=center bgcolor=#f2f6f9:)vincoli di disuguaglianza (:tableend:)

Vedi esempio:

In particolare il duale del duale di P è P stesso.

Teoremi della dualità

A cosa serve aver definito cos'è il duale di un problema di programmazione lineare? A sfruttare alcune sue proprietà espresse da una serie di teoremi, il primo dei quali è il teorema della dualità in forma debole. Questo dice che dati due problemi duali:
P: min z(x), con x che appartiene a X
D: max w(y), con y che appartiene a Y
per ogni soluzione ammissibile x' che appartiene a X di P e per ogni soluzione ammissibile y' che appartiene a Y di D, si ha che:
z(x') >= w(y')

Il primo corollario dice che se:

• x' appartiene a X
• y' appartiene a Y'
• z(x') = w(y')

allora ho trovato la soluzione ottima!

Il secondo corollario dice che se un problema lineare P è illimitato, allora il suo duale D è inammissibile. Se infatti P ha valori che arrivano a meno infinito per z(x'), non può esistere nessun valore y' per rendere w(y') minore di lui.
Non è altrettanto scontato il contrario: se P è inammissibile, anche il suo D potrebbe benissimo esserlo.

Riassumendo, con il teorema della dualità in forma debole ci viene detto che i valori della funzione obiettivo che sto minimizzando sono sempre al di sopra di quelli della funzione che sto massimizzando.

Il teorema della dualità in forma forte ci dice invece che dati due problemi lineari duali P e D, se uno dei due ammette una soluzione ottima finita, allora anche l'altro la ammette e i due valori coincidono. Guardando la figura seguente potremo dire che i due valori si sono incontrati a metà:

TO BE CONTINUED

Torna alla pagina di Ricerca Operativa