Domande di teoria e risposte Algoritmi di ottimizzazione

L’espressione però fornisce il valore della funzione obiettivo anche in corrispondenza di soluzioni

non base, ossia in cui le xF non sono tutte nulle. In questo caso il segno dei coefficienti del vettore

, che è facile verificare abbia n−m elementi uno per ogni variabile xF , definisce le conseguenze sul

valore di tale funzione dell’aumento delle variabili fuori base. Il vettore c˜ è noto come vettore dei

costi ridotti o dei costi residui. Ricordando che stiamo considerando un problema di minimizzazione

possiamo osservare che: ∈

• Se esiste una variabile fuori base j con Aj B il cui costo ridotto c˜j è negativo allora il vertice

corrispondente alla base corrente non è ottimo e facendo aumentare il valore della variabile j il

costo della soluzione migliora (ossia diminuisce).

∈

• Se per tutte le variabili fuori base j con Aj B il costo ridotto c˜j è positivo o nullo allora il vertice

corrispondente alla base corrente è ottimo dato che facendo aumentare il valore della variabile j il

costo della soluzione non migliora (ossia aumenta o rimane uguale).

Si noti che il costo ridotto delle variabili base è nullo. Infatti il vettore dei costi ridotti è:

5. Definire la scelta della variabile che esce dalla base (operazione di Pivoting) nell’algoritmo del

simplesso.

Scelta della variabile che esce dalla base: si sceglie la variabile che minimizza il rapporto dˆi Aˆih , i

= 1, . . . , m : Aˆ ih > 0 (si veda l’equazione (5.43)). In caso di parità nel calcolo del minimo, esce

dalla base la variabile di indice minimo.

Più precisamente la variabile β(ℓ) che esce dalla base è determinata dalla

β(ℓ) = min ∀

β(i) : Aˆih > 0, d^i/Aˆih ≤ d^k/Aˆ kh i, k = 1, . . . , m : Aˆ kh > 0 .

6. Definire un problema illimitato e discutere come si possa verificare durante l’esecuzione

dell’algoritmo del simplesso, che il problema è illimitato.

In questi problemi la regione ammissibile è illimitata ed il gradiente fa si che la soluzione ottima sia

illimitata.

Durante l’esecuzione dell’algoritmo del simplesso posso verificare che il problema è illimitato dal

fatto che tutti i coefficienti della colonna corrispondente ad una variabile fuori base, che ha costo

relativo negativo, sono minori o uguali a zero.

7. Descrivere la Fase 1 dell’algoritmo del simplesso e discutere il caso in cui il valore della

soluzione ottima di tale fase risulti strettamente positiva.

Il metodo delle 2 fasi in una prima fase risolve un problema ausiliario la cui soluzione è la base

iniziale che, nella seconda fase, è utilizzata per inizializzare l’algoritmo del simplesso.

Consideriamo un problema PL di minimizzazione espresso in forma standard P = min{c T x, x n,

∈ ℜ

Ax = d, x ≥ 0}, e supponiamo che d ≥ 0, eventualmente moltiplicando per −1 i vincoli con termine

noto negativo. Nella prima fase dell’algoritmo viene cercata una base, ossia un insieme di m

colonne di A tra loro linearmente indipendenti, che corrisponda ad una soluzione base

ammissibile. Se tale base non è immediatamente disponibile, ad esempio riconoscendo in A delle

colonne che formino una matrice identità, viene definito un problema ausiliario in cui vengono

inserite m variabili aggiuntive x a una per ogni vincolo. In tale problema è facile verificare che le

variabili x a costituiscono una base dato che le colonne a queste corrispondenti sono una matrice

identità. Inoltre, dato che d ≥ 0 la soluzione base x a = d e x = 0 è una soluzione base ammissibile.

Ovviamente tale soluzione base non contiene nessuna variabile originale x per cui non è un punto di

partenza per l’algoritmo del simplesso. È però facile verificare che una soluzione del problema

ausiliario in cui x a = 0 e x ≥ 0 è una soluzione base ammissibile del problema originario. Per

ricercare tale soluzione possiamo utilizzare delle operazioni di pivoting per muoverci dalla

soluzione base corrente x a = d ad una soluzione base che contenga solo le variabili originali, ossia

in cui x a = 0. A tal fine per guidare l’algoritmo alla ricerca di una base che non contenga le variabili

x a possiamo utilizzare una funzione obiettivo artificiale da minimizzare e che contenga solo tali

variabili. Il problema di Fase 1 è quindi:

Lo scopo di tale problema di ottimizzazione è proprio quello di rimuovere dalla base le variabili x a

sostituendole con variabili originali x che non comparendo nella funzione obiettivo artificiale non

danno contributo. Il problema artificiale è chiaramente un problema PL di cui disponiamo di una

SBA iniziale x a = d e che può essere risolto con l’algoritmo del simplesso.

La risoluzione del problema artificiale di Fase 1 può portare a diversi casi, tra cui quello in cui il

valore della soluzione ottima risulta strettamente positivo:

Se la soluzione ottima del problema di Fase 1 ha un valore della funzione obiettivo positivo, w > 0,

significa che il sistema a destra nell’equazione non è risolubile utilizzando le

sole x e quindi il problema originale P è impossibile.

8. Si consideri la forma Tableau dell’algoritmo del simplesso: si discuta come il Tableau vada

inizializzato, quando questo sia in forma canonica rispetto ad una base e come possa essere

ricavata l’inversa della matrice di base corrente dal Tableau.

Definiamo una matrice Y di dimensione (m + 1) × (n + 1) che conterrà gli elementi del tableau

corrente.

Inizializzazione: La matrice Y viene inizializzata come segue:

• y00 = 0;

• costi nella riga 0: y0j = cj , j = 1, . . . , n;

• termini noti nella colonna 0: yi = di , i = 1, . . . , m;

• coefficienti della matrice tecnologica nel resto della matrice: yij = Aij , i = 1, . . . , m, j = 1, . . . , n;

A questo punto, data la base iniziale B = {Aβ(1), . . . , Aβ(m)}, poniamo il tableau in forma canonica

rispetto a tale base azzerando i costi ridotti delle variabili base in riga 0 e definendo una matrice

identità nelle colonne della base.

Si ricordi che dato il tableau in forma canonica il contenuto delle diverse parti del tableau è il

seguente:

• y00 contiene il valore della SBA corrente, cambiato di segno;

• nella colonna 0 si leggono i valori correnti delle variabili base. Per ogni riga la variabile in base su

tale riga si determina considerando quale colonna della base corrente abbia il valore ad 1 in

corrispondenza di tale riga;

• nella riga 0 in corrispondenza delle variabili fuori base si hanno i relativi costi ridotti;

• nelle rimanenti righe in corrispondenza delle variabili fuori base si hanno i relativi coefficienti

della matrice Fˆ = B^−1F.

Ricordando che un tableau in forma canonica rispetto alla base corrente è il tableau iniziale

moltiplicato per l’inversa della base stessa, è facile verificare che nelle colonne della base iniziale

che corrispondono ad una matrice identità possono essere lette le colonne dell’inversa della base

corrente.

Se la base iniziale non fosse disponibile nel problema originale e fosse stato necessario applicare la

Fase 1 per determinarla, al fine di ottenere l’inversa è necessario mantenere le colonne delle

variabili artificiali anche nella Fase 2 ed eseguire le operazioni di pivoting anche su di esse.

Nel tableau iniziale le colonne della base iniziale sono una matrice identità e le colonne di una base

differente, ad esempio la base ottima, che per comodità sono assunte completamente diverse da

quelle della base iniziale. Nella medesima figura è illustrato il tableau finale nel quale è possibile

reperire la matrice di base nelle colonne della base iniziale.

9. Dato un modello di programmazione lineare intera, definirne il rilassamento continuo e

discutere la relazione tra i valori delle soluzioni dei due problemi. Discutere il caso in cui la

soluzione del rilassamento continuo risulti intera.

Dato un problema PLI, P : zP = min{c T x, x n, Ax = d, x ≥ 0 intere} si dice rilassamento continuo

∈ ℜ

il problema PL, C(P) : zC(P ) = min{c T x, x n, Ax = d, x ≥ 0} ottenuto rimuovendo il vincolo di

∈ ℜ

interezza.

Il rilassamento continuo ha un ruolo fondamentale nella risoluzione dei problemi PLI perché la sua

soluzione ottima è in stretta relazione con quella del problema PLI cui è associato.

Dato un problema PLI P : zP = min{c T x, x n, Ax = d, x intere} ed il rilassamento continuo

∈ ℜ

associato, C(P) : zC(P ) = min{c T x, x n, Ax = d, x ≥ 0} e detti zP e zC(P ) i valori delle rispettive

∈ ℜ

soluzioni ottime, si ha che zC(P ) ≤ zP . La regione ammissibile di C(P) contiene la regione

ammissibile di P dato che è ottenuta da questa rimuovendo il vincolo di interezza e la funzione

obiettivo dei due problemi è la stessa. Pertanto la soluzione ottima di C(P) non può essere peggiore

di quella di P.

Dato un problema PLI P = min{c T x, x n, Ax = d, x intere} ed il rilassamento continuo associato,

∈ ℜ

C(P) = min{c T x, x n, Ax = d, x ≥ 0} se la soluzione ottima xC(P ) è ammissibile per P, ossia ha

∈ ℜ

coordinate intere, allora è la soluzione ottima anche di P e zC(P ) = zP .

Dal teorema precedente sappiamo che La soluzione ottima di C(P) è tale che zC(P ) ≤ zP . Tale

soluzione è però anche soluzione ammissibile per P e quindi il suo valore è maggiore o uguale a

quello di zP . Quindi si ha che zP ≤ zC(P ) ≤ zP e quindi i valori delle due soluzioni non possono che

coincidere.

10. Discutere sotto quali condizioni possa essere introdotta una relazione di dominanza tra due

formulazioni equivalenti di un problema PLI.

A differenza dei problemi PL per cui, a meno dell’introduzione di vincoli ridondanti, la formulazione

è univoca, per i problemi PLI la formulazione non è univoca. Infatti, la regione ammissibile di un

problema PLI è costituita da un inseme X di punti a coordinate intere che generalmente viene

definita “catturando” tali punti con un insieme di vincoli lineari. Più precisamente dato un problema

∈

PLI P : zP = min{c T x, x X} questo viene formulato mediante un insieme di vincoli lineari come

∈ ℜ

P : zP = min{c T x, x n, Ax = d, x intere}. Dato un insieme X esistono molti modi per

“racchiudere” tale insieme con un insieme di vincoli lineari. Come è possibile verificare tali

formulazioni, così come altre che utilizzano un numero anche maggiore di vincoli, sono tutte

equivalenti nel senso che contengono tutte solo i punti interi appartenenti all’insieme X. È però

possibile anche verificare che i rilassamenti continui non sono tra loro equivalenti e rappresentano

approssimazio