Dualità

La teoria della dualità permette di:

• Introdurre nuovi metodi risolutivi;
• Effettuare analisi di problemi di ottimalità

Dato un problema di PL detto PRIMALE, si associa ad esso un altro problema di PL detto primale:

La conversione avviene secondo le regole stabilite dalla:

Tabella Primale Duale

Primale	Duale
min	max
num. variabili	num. vincoli
num. vincoli	num. variabili
coeff f.o.	termini noti
termini noti	coeff f.o.
i-esimo vincolo
i-esimo vincolo
i-esimo vincolo	libera
	j-esimo vincolo
	j-esimo vincolo
libera	j-esimo vincolo
NB: Il Duale del Duale coincide col Primale

Link to original

Esempio

Problemi duali

Una coppia di problemi duali si dice simmetrica se è del tipo:

Se il primale è in Forma Standard si hanno problemi asimmetrici.

Relazioni Problemi Primali-Duali

Teorema della Dualità debole

Siano dati i problemi:

 

E sia ammissibile per (P) e ammissibile per (D).

Allora

Significato:

Teorema della Dualità debole

• La funzione obiettivo primale è un upper bound per il valore ottimo duale;
• La funzione obiettivo duale è un lower bound per il valore ottimo primale;

Corollario 1

Se è ammissibile per (P) e ammissibile per (D) e allora è ottimo per (P), e è ottimo per (D)

Corollario 2: Relazione Illimitato ←> Inammissibile

• Se (P) è illimitato (D) è inammissibile;
• Se (D) è illimitato (D) è inammissibile.

Riassunto dei possibili casi in una tabella:

Primale\Duale	Ottimo Finito	Illimitato	Inammissibile
Ottimo Finito
Illimitato
Inammissibile

Teorema della Dualità Forte

Teorema della dualità forte

Se uno dei due problemi primale o duale ha ottimo finito allora anche l’altro ha ottimo finito, e i valori ottimi delle funzioni obiettivo coincidono. Se uno dei due problemi è illimitato, l’altro è inammissibile.

Relazione Ottimalità Primale < - > Ammissibilità Duale

Leggi dopo aver letto:

Scarti Complementari

Scarti Complementari

Scarti Complementari

Siano dati i problemi primale-duale:

Siano ammissibile per (P) e ammissibile per (D).

sono soluzioni ottime soddisfano le condizioni:

• relazioni
• relazioni

Abbiamo un sistema di equazioni.

Condizioni di ottimalità (nella dualità)

1. Ammissibilità Primale Vincoli Primali
2. Ammissibiltà Duale Vincoli Duali

Oppure, sono ottimi valgono:

 

e anche: 

Che significa tutto questo, e soprattutto a che serve? Capiamolo con degli esempi.

(Se stai pensando di skipparlo: è capitato non solo alle prove in itinere, ma anche durante gli orali.)

Esempio

Esempio (Scarti Complementari):

Un utilizzo degli scarti complementari è di calcolare la soluzione ottima duale, data la soluzione ottima primale (0,6).

Potremmo arrivarci con il simplesso o con qualsiasi altro metodo, ma l’idea è quella di evitare di impostare l’algoritmo

Dato il problema Primale con soluzione (0,6):

Scriviamo il problema duale:

A questo punto creiamo il sistema di scarti complementari:

Abbiamo:

• con 3 equazioni in y,
• =0 con 2 equazioni in x.

Dobbiamo vedere quali equazioni ci danno ‘informazioni’ sulla soluzione duale.

Dato che abbiamo la SOLUZIONE PRIMALE, sostituiamo

Questo si traduce in:

Troviamo la soluzione duale: .

Perciò data la funzione obiettivo duale: , avremo l’ottimo

Non è garantito avere un sistema così pulito. Ad esempio, nella prova in itinere dell’A.A. 2023/24 è capitato un sistema molto più complesso dove l’informazione su una variabile andava presa facendo coincidere la con la . Non molto divertente.

Link to original

Sia la soluzione ottima primale e la soluzione ottima duale.

Risulta , cioè coincidono i valori ottimi.

deve soddisfare i vincoli duali, cioè:

Sostituendo con otteniamo la dimostrazione, e arriviamo al risultato che , che è la condizione di ottimalità primale.

Per cui la Ottimalità Primale COINCIDE con l’Ammissibilità Duale (importantissimo per Simplesso Duale).

Calcolo Soluzione Duale

Possiamo usare:

1. Scarti Complementari;
2. Tabella simplesso del problema primale.

Se il problema primale ha vincolo si utilizzano le variabili scarto per la Forma Standard.

La soluzione ottima si ottiene:

, dove:

• vettore coefficienti della f.o. associati alle variabili in base alla iterazione;
• vettore dei costi ridotti nella tabella finale del simplesso associati alle variabili in base alla iterazione.

Esempio Veloce

Dato un problema del tipo:

Eseguendo il metodo del simplesso otterremo la soluzione ottima primale:

con e valore ottimo

e costi ridotti finali:

Calcolando la soluzione duale con la formula definita subito sopra l’esempio abbiamo:

, che è la soluzione ottima duale.

Osservazione

Se il problema primale ha vincoli la soluzione ottima duale sarà la sottrazione inversa rispetto a quella appena eseguita, cioè:

Simplesso Duale

Si tratta di un metodo per risolvere il problema di PL primale nel caso in cui non sia valida l’ammissibilità primale (cioè ci sono termini noti negativi nella Forma Standard), ma sia verificata l’ammissibilità duale (cioè i costi ridotti delle variabili fuori base sono ).

Il metodo parte da una soluzione di base non ammissibile, cioè esterna al poliedro, e cerca di raggiungere la soluzione ottima.

Ad ogni iterazione i costi ridotti sono sempre e si cerca di avere tutti i termini noti

Per riassumere:

Simplesso Primale	Simplesso Duale
Condizioni: Termini Noti	Condizioni: C’è almeno un termine noto negativo; Costi ridotti
Obiettivo: Costi Ridotti	Obiettivo: Termini Noti

Criterio di Uscita

Esce dalla base la variabile associata al termine noto negativo

Si individua la riga , se gli elementi della riga sono TUTTI PROBLEMA PRIMALE INAMMISSIBILE 

Criterio di non ammissibilità

Se il primale è inammissibile il duale potrebbe essere non limitato o non ammissibile. 

Poichè vale la condizione di ammissibilità duale allora il problema duale non è limitato

Se ci sono elementi negativi sulla riga si individua la variabile uscente , dove è l’indice di colonna tale che

Criterio di Entrata

Resta individuato il pivot della trasformazione.

Riassumendo di nuovo:

Simplesso Primale	Simplesso Duale
Costo ridotto dà la variabile entrante	Termine noto dà la variabile uscente
Criterio Rapporto per la variabile uscente	Criterio rapporto per la variabile entrante
Criterio illimitatezza: Elementi colonna con costo ridotto negativo	Criterio di inammissibilità: Elementi riga associati ad un termine noto
Ottimalità: Costi ridotti	Ottimalità: Termini noti

Analisi di Post-Ottimalità

Supponiamo di causare la perturbazione di un termine noto

La soluzione di ottima di base è ,

Sia

(B^{-1}b,0) è ancora ottima?

Caso 1: ha componenti negative Non vale l’ammissibilità primale. 

I costi ridotti non hanno il vettore , quindi i costi ridotti sono ancora

(e sono perché è soluzione ottima).

Possiamo applicare il simplesso duale per calcolare la nuova soluzione ottima.

Caso 2: ha componenti è ammissibile

Link to original