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.