Financial Polis

  Expand All  |  Contact All

 




La prima formulazione del metodo che ci accingiamo ad esporre va attribuita a G. B. Dantzig . Una descrizione più estensiva ed esauriente fu data invece da A. Whinston e G. van de Panne .

Il metodo richiede, per iniziare, una soluzione di base ammissibile per il sistema dei vincoli del problema originale, cioè una configurazione che verifichi A x + y = b, x ≥ 0, y ≥ 0. Inoltre si richiede che essa rispetti il principio della nullità complementare, cioè che per ogni primale che si trovi in base, la relativa complementare ne sia fuori. Non è richiesto, invece, per il momento, che alle duali in base siano assegnati valori positivi. Se anche ciò si verificasse, tutte le condizioni di KKT sarebbero soddisfatte ergo la soluzione attuale sarebbe ottimale. Trovare una configurazione dove tutte le duali in base siano non negative è per l'appunto lo scopo del metodo e insieme il criterio di arresto dell'algoritmo.

Poniamo dunque di avere o di avere calcolato, eventualmente col metodo descritto al paragrafo precedente, un tableau ammissibile per i vincoli e rispettante la nullità complementare.

I metodi proposti non richiedono una distinzione particolare tra x ed y e, rispettivamente, tra u e v. Perciò chiameremo d'ora in avanti x* il gruppo di variabili comprendente x ed y; u* il secondo gruppo, formato da u e v, complementari alle prime. Per "brevità", come scrive il Martos , chiameremo le variabili del primo gruppo "primali" e le altre "duali".

Abbiamo già osservato che se le u* in base assumessero tutte valori positivi, o comunque non negativi, la soluzione attuale sarebbe ottimale. In caso contrario, c'è la possibilità di migliorare la funzione obiettivo se si porta in base, naturalmente con un valore positivo, una xi* la cui complementare ui* assume attualmente un valore negativo. Per garantire la convergenza, analogamente al metodo del simplesso per la programmazione lineare, si sceglie come nuova variabile basica la xi* la cui complementare ha valore minore, intendendo con ciò il valore "più negativo".

La nuova variabile di base deve assumere il valore in grado di massimizzare la variazione dell'obiettivo, in modo da rispettare i vincoli di segno. La variabile "in uscita" non è automaticamente la corrispondente dell'entrante, bensì vengono "candidate" anche le variabili del gruppo x* che sono in base. Il criterio di scelta è lo stesso che nella programmazione lineare, cioè va selezionata la variabile per cui il quoziente tra l'eventuale elemento pivot e il valore corrente in colonna zero è minimo positivo.

Se la variabile che abbandona la base è la complementare dell'entrante, si ottiene un tableau in cui la dualità complementare è rispettata. Si procede con un altra iterazione analoga alla precedente e così via.

Se invece è stata selezionata per l'uscita una delle primali, dopo l'iterazione si ha una inedita situazione in cui la nullità complementare non viene rispettata. Consideriamo questo caso.

Il criterio della dualità complementare è dunque violato, poiché‚ la ui* complementare alla variabile entrante è rimasta in base. La xi* e la sua complementare ui* formano la c. d. coppia di base. La complementare uj* della variabile xj* appena uscita forma, insieme a quest'ultima la coppia non basica. Un tableau in cui esistono tali coppie, violante dunque la nullità complementare si dice essere non standard. E' invece standard quel tableau in cui la dualità complementare è rispettata, come ad esempio quello iniziale. Si comprenderà che solo un tableau di quest'ultimo tipo può presentare la soluzione ottimale; l'essere non standard è dunque uno status transitorio rispetto alla ricerca della soluzione.

Quando il tableau è non standard, le regole del metodo sono diverse. Per la variabile in entrata non c'è selezione: essa deve essere in ogni caso la uj* della coppia non basica, ovvero la variabile duale complementare della xj* uscita al passo precedente. Tale criterio garantisce tra l'altro che non ci sia mai più di una coppia basica e una non basica. Non può accadere insomma che ci sia più di una variabile "intrusa" in base ed una fuori base.

Pu≥ uscire dalla base, invece, sempre tramite selezione col solito criterio del minimo quoziente negativo, una delle variabili primali in base, oppure la ui* della coppia basica. Va osservato che questo insieme di candidati non è determinato allo stesso modo di quello di un tableau standard. Infatti in quest'ultimo caso la duale abilitata ad uscire insieme alle primali è la complementare dell'entrante.

Se esce proprio la duale della coppia basica, il tableau ridiventa standard, poiché‚ la ui* e la uj* "intruse", rispettivamente in base e fuori, si sono scambiate lo status e la dualità complementare è di nuovo rispettata. Se ciò non è accaduto, si fa un'altra iterazione non standard e così via.

Prima o poi, o meglio in un numero finito di passi, il tableau ridiventa comunque standard. E in un numero finito di iterazioni si arriva ad un tableau standard in cui tutte le duali in base assumono valori non negativi. A questo punto tutte le condizioni di KKT sono verificate e perciò la configurazione di base corrente è ottima per il problema. La procedura può dirsi conclusa.

Ci sembrano opportune alcune osservazioni sulle conseguenze dell'applicazione di queste regole previste dal metodo.

Innanzi tutto, dopo ogni iterazione non standard consecutiva, esclusa quindi la prima di ogni serie, il numero delle xi* in base diminuisce di una unità, ma il valore dell'obiettivo non decresce. Per ogni iterazione standard consecutiva, invece, la base si arricchisce di una primale, e il valore dell'obiettivo aumenta. Se si considera che i passi sono finiti, il metodo converge.

Questo metodo ha un importante vantaggio rispetto a quello molto simile di Wolfe : converge anche se la matrice C della forma quadratica è semidefinita. Perciò funziona anche se una o più righe e colonne di C sono piene di zeri, addirittura se non ci sono valori diversi da zero. Il metodo è idoneo anche per programmi lineari.