Financial Polis

  Expand All  |  Contact All

 




Di solito, come detto, il tableau di set-up così come è stato strutturato nel paragrafo precedente non è adatto ad essere un tableau iniziale per i due metodi che seguono, a meno che non si verifichi lo stesso caso favorevole a cui abbiamo accennato a proposito della programmazione lineare, che cioè si abbiano tutti i vincoli in forma di disuguaglianza che ammettano la soluzione x = 0.

Abbiamo bisogno di trovare, a partire dalla tabella di set-up, una soluzione di base che soddisfi il sistema dei vincoli A x + y = b, con x ≥ 0 e y ≥ 0,

che altresì verifichi u' x e v' y. Non è necessario, invece, che u ≥ 0 n‚ che v ≥ 0.

Si pone dunque il problema di una "prima fase" in grado di trovare una soluzione di base ammissibile. A tale scopo può essere convenientemente applicato il metodo in precedenza commentato delle variabili artificiali, opportunamente modificato per l'incombenza.

La complicazione consiste nel fatto che la sostituzione delle artificiali con alcune delle variabili x genera tableaux che soddisfano sì i vincoli, ma che non rispettano il criterio della dualità complementare. La tabella iniziale per il metodo che segue deve soddisfare tale condizione. Tuttavia c'è modo di modificare opportunamente il metodo.

Intanto non c'è bisogno di creare nuove variabili, almeno finché‚ non si dia, tra i vincoli, una disuguaglianza che non ammetta la soluzione x = 0. In tal caso conviene modificare il problema originario in modo da aggiungere a tali relazioni una variabile slack che deve essere poi considerata una x a tutti gli effetti. Alla matrice C va aggiunta una colonna ed una riga piene di zeri. Va osservato che tale operazione rende la matrice sicuramente semidefinita.

Le y relative a vincoli che erano espressi originariamente in forma di uguaglianza devono essere in qualche modo contrassegnate come artificiali. Esse devono essere forzate fuori della base, mentre al loro posto devono entrare delle x secondo il solito criterio della minimizzazione delle inammissibilità ospitato nella apposita riga zero. Il vettore-criterio in questione viene ottenuto sommando colonna per colonna i coefficienti delle x per le sole righe dove la relativa yj va considerata artificiale, vale a dire in corrispondenza di quei vincoli che in forma originaria erano già equazioni. Si deve poi cambiare di segno le somme ottenute.

Se durante la prima iterazione della fase preliminare una certa xi sostituisce in base una yj, cosa possibile solo se il pivot tra i due è diverso da zero, alla iterazione successiva anche l'elemento pivot tra ui e vj è diverso da zero, ed è precisamente l'opposto del primo. Infatti la prima iterazione non modifica la matrice - A' tra le u e le v essendo gli elementi che vi vengono sommati sempre nulli. Simmetricamente e per lo stesso motivo, neanche le operazioni tra le u e le v non influenzano la matrice A.

Insomma, per ottenere un tableau standard al termine della prima fase è sufficiente far seguire, a ciascuna iterazione tra le x e le y, una iterazione speculare tra una delle v e una delle u. Esse vengono determinate

immediatamente in quanto complementari delle prime quindi non occorre, per questa "iterazione duale", alcuna selezione.

Questo modo di procedere non garantisce che la vj entri in base con un valore positivo, ma, come si è visto, ciò non inficia la convergenza dei due metodi che seguono, essendo la positività delle u e delle v in base il loro criterio di arrivo e non il presupposto di partenza.

Con ciò si è risolta la questione dei vincoli in forma d'uguaglianza. Nel caso in cui ce ne siano alcuni in forma di disuguaglianza, ma che non ammettono x = 0 come soluzione ammissibile, per usare ugualmente il metodo delle variabili artificiali è necessario introdurre un'altra variabile slack, in analogia col metodo per la programmazione lineare. Per cui il numero delle colonne del Tableau deve essere aumentato.