Soluzioni di base per problemi in forma standard

2.3 Soluzioni di base per problemi in forma standard

Sia P ⊆ Rⁿ un poliedro definito da un sistema lineare in forma standard

Ax = b (2.3)

x ≥0, (2.4)

con A ∈ R^m×n e b ∈ R^m. Nel seguito assumeremo che P ≠ ∅. In particolare, il sistema Ax = b ammette una soluzione, da cui segue che rk(A) = rk(A ∣ b). Possiamo assumere senza perdita di generalità che le righe di A siano linearmente indipendenti (cioè che rk(A) = m): in caso contrario, se si avesse cioè rk(A) = m^′ < m, potremmo tenere nel sistema m^′ equazioni linearmente indipendenti e rimuovere le altre senza alterare l’insieme delle soluzioni ammissibili, riducendoci cos`ı ad avere un sistema A^′x = b^′ con m^′ righe e rk(A^′) = m^′.

Vogliamo caratterizzare le soluzioni di base del sistema (2.3)–(2.4). Da ora in avanti, denoteremo con A_j, j = 1, . . . , n, le colonne di A. Dato un sottoinsieme S ⊆ {1,... ,n}, indicheremo con AS la sottomatrice di A formata dalle colonne Aj con j ∈ S.

Data una matrice A ∈ R^m×n di rango m, un insieme B ⊆{1,... ,n} `e detto una base di A se∣B∣ = m e la matrice AB`e invertibile. Con riferimento ad un sistema in forma standard del tipo (2.3)–(2.4), B viene anche detta una base del sistema.

I risultati seguenti giustificano l’utilizzo del termine “base”.

Proposizione 2.3 Un punto ¯x ∈ Rⁿ `e una soluzione di base del sistema in forma standard (2.3)–(2.4) se e solo se A¯x = b ed esiste una base B di A tale che ¯x_j=0 per ogni j ∉ B.

Dimostrazione. Supponiamo che ¯x sia una soluzione di base del sistema (2.3)–(2.4). Allora esistono n vincoli attivi in ¯xche sono linearmente indipendenti. Si noti che gli m vincoli del sistema Ax = b sono necessariamente attivi in ¯x. Inoltre, poich´e rk(A) = m, tali vincoli sono linearmente indipendenti. Dunque esistono n−m vincoli di non-negativit`a attivi in ¯x, diciamo le disuguaglianze xj ≥0 per j ∈ N , dove N ⊆{1,... ,n} e ∣N∣ = n − m, tali che i vincoli

a^T_ix = bi, i =1, . . . , m (2.5)

x_j ≥0, j ∈ N, (2.6)

siano linearmente indipendenti. In altre parole, la matrice del sistema (2.5)–(2.6) `e invertibile.

A meno di permutare le variabili, possiamo assumere che N ={m+1,... ,n}. Definiamo inoltre B ={1,... ,m}. Allora la matrice del sistema (2.5)–(2.6) `e la seguente:

(A_B A_N

0 I ), (2.7)

dove I denota la matrice identità (n − m) × (n − m). Poiché, come detto, la matrice (2.7) è invertibile, anche ABè invertibile. Dunque B è una base di A. Inoltre, siccome i vincoli xj ≥0 per j ∈ N sono attivi in ¯x, si ha ¯x_j=0 per j ∈ N (cioè per j ∉ B), come volevasi dimostrare.

Viceversa, supponiamo che A¯x = bed esista una base B di A tale che ¯xj=0 per ogni j ∉ B.

A meno di permutare le variabili, possiamo assumere che B ={1,... ,m}. Definiamo inoltre N ={m+1,... ,n}. Poiché B è una base di A, la sottomatrice A^B è invertibile, dunque anche la matrice (2.7) è invertibile. Pertanto i vincoli (2.5)–(2.6) sono linearmente indipendenti e sono attivi in ¯x, cioè ¯x è una soluzione di base del sistema (2.3)–(2.4). ◻

Corollario 2.4 Un punto ¯x ∈ Rⁿ `e una soluzione di base del sistema in forma standard (2.3)–(2.4) se e solo se A¯x = b e i vettori {A^j}^j∈S sono linearmente indipendenti, dove S = {j ∈ {1,... ,n} ∶ ¯xj≠0}.

Dimostrazione. Se ¯x`e una soluzione di base del sistema (2.3)–(2.4), allora per la proposizione precedente esiste una base B di A tale che {A^j}^j∈S ⊆ {A^j}^j∈B; inoltre, tali vettori sono linearmente indipendenti per definizione di base.

Viceversa, se i vettori{Aj}j∈Ssono linearmente indipendenti, allora possiamo scegliere una base B di A tale che S ⊆ B. Dunque ¯x_j=0 per ogni j ∉ B. Per la proposizione precedente, ¯x

`e una soluzione di base del sistema (2.3)–(2.4). ◻

Osservazione 2.5 Data una base B del sistema in forma standard (2.3)–(2.4), esiste un unico vettore ¯x che soddisfa A¯x = b e ¯x_j=0 per j ∉ B.

Dimostrazione. A meno di permutare le variabili, possiamo assumere che B ={1,... ,m}. Sia inoltre N ={m + 1,... ,n}. Se x ∈ Rⁿ `e un vettore che soddisfa Ax = b e xj =0 per j ∉ B, allora

b = Ax = A_Bx_B+ A_Nx_N =A_Bx_B.

Poiché B è una base di A, la matrice A_B è invertibile. Pertanto l’unica scelta possibile per x_Bè data da xB=A⁻¹_Bb. Ne segue che vi è un unico vettore ¯xche soddisfa A¯x = b e ¯x_j =0 per j ∉ B, precisamente il vettore ¯xle cui componenti sono definite da ¯x_B=A⁻¹_Bbe ¯x_N =0. ◻ L’osservazione precedente permette di dare la seguente importante definizione. Data una base B del sistema in forma standard (2.3)–(2.4), la soluzione di base relativa a B è l’unico vettore ¯x che soddisfa A¯x = be ¯x_j=0 per j ∉ B, cioè il vettore definito da

x_B=A⁻¹_Bb

¯ xN =0.

Se ¯x è una soluzione ammissibile del sistema (2.3)–(2.4), cioè se ¯x_B = A⁻¹_Bb ≥0, allora B è detta una base ammissibile del sistema (2.3)–(2.4).

Siamo ora in grado di dimostrare il seguente importante risultato, che viene spesso con-siderato parte integrante del Teorema Fondamentale della Programmazione Lineare (Teore-ma 1.1).

Teorema 2.6 Se un programma lineare in forma standard

max c^Tx (2.8)

s.a Ax = b (2.9)

x ≥0 (2.10)

ha una soluzione ottima, allora ha una soluzione ottima che `e una soluzione di base ammis-sibile.

Dimostrazione. Tra tutte le soluzioni ottime del problema dato (ce n’`e almeno una per ipotesi), ne scegliamo una che abbia il numero massimo di componenti nulle e la chiamiamo

x. Dimostreremo che ¯x`e una soluzione di base (ovviamente ammissibile).

2.3. SOLUZIONI DI BASE PER PROBLEMI IN FORMA STANDARD 11 Supponiamo che ¯xnon sia una soluzione di base e definiamo S ={j ∶ ¯x^j>0} = {j ∶ ¯x^j ≠0}.

Per il Corollario 2.4, i vettori{A^j}^j∈Ssono linearmente dipendenti. Dunque possiamo ottenere il vettore nullo come combinazione lineare di tali vettori, dove i coefficienti della combinazione non sono tutti nulli: in altre parole, esiste v ∈ R^S tale che v ≠ 0 e ASv =0. Possiamo assumere senza perdita di generalit`a che v abbia almeno una componente positiva (in caso contrario basta rimpiazzare v con −v). Estendiamo v ad un vettore ¯v ∈ Rⁿ come segue:

¯ v_j =⎧⎪⎪

⎨⎪⎪⎩

v_j, j ∈ S 0, j ∉ S.

Si noti che A¯v =0 e ¯v ha almeno una componente positiva.

Per ogni ε ≥ 0 si ha A(¯x ± ε¯v) = A¯x ± εA¯v = b; inoltre, poich´e ¯v^j =0 per ogni j ∉ S, si ha

vj =0 per ogni j tale che ¯xj =0. Allora, se ε > 0 è scelto sufficientemente piccolo, entrambi i punti ¯x+ ε¯v e ¯x− ε¯v sono soluzioni ammissibili. Inoltre, poiché ¯x è una soluzione ottima, si ha

c^Tx ≥ c¯ ^T(¯x + ε¯v) = c^Tx¯+ εc^T¯v, c^Tx ≥ c¯ ^T(¯x − ε¯v) = c^Tx¯− εc^Tv,¯ da cui segue che c^Tv =¯ 0.

Consideriamo un punto della forma ¯x− ε¯v con ε ≥ 0. Poiché c^T¯v =0, il punto ¯x− ε¯v è una soluzione ottima per ogni ε ≥ 0 per cui il punto stesso è ammissibile.

Ci chiediamo ora quali siano i valori ε ≥ 0 per cui il punto ¯x− ε¯v `e ammissibile. Questo avviene se e solo se ¯x_j− ε¯v_j ≥ 0 per ogni j = 1, . . . , n. Si noti che se j `e un indice tale che

vj ≤0, allora, poiché ¯xj ≥ 0, si avrà ¯xj − ε¯vj ≥ 0 per ogni ε ≥ 0. Dunque il punto ¯x− ε¯v è ammissibile se e solo se ¯x_j− ε¯v_j ≥0 per ogni j ∈{1,... ,n} tale che ¯vj>0, cioè se e solo se

ε ≤x¯_j/¯v^j per ogni j ∈{1,... ,n} tale che ¯v^j >0. (2.11) Sia h un indice tale che ¯v_h>0 per cui il valore ¯x_h/¯v^h sia il pi`u piccolo possibile. Come assunto in precedenza, il vettore ¯v ha almeno una componente positiva, dunque h `e ben definito.

Poniamo ora ε = ¯x_h/¯vh e x^∗ = x¯− ε¯v. Poich´e ε soddisfa la condizione (2.11), il punto x^∗ `e ammissibile. Inoltre, x^∗_h =x¯_h− ε¯v_h =0, mentre, per ogni j ∉ S, si ha x^∗_j =x¯_j− ε¯v_j =0 − 0 = 0.

Dunque x^∗ `e una soluzione ottima con almeno una componente nulla in pi`u rispetto a ¯x, il

che contraddice la scelta di ¯x. ◻

Il teorema precedente chiarisce perché la programmazione lineare sia considerata parte dell’ottimizzazione discreta nonostante la regione ammissibile di un programma lineare sia una regione continua: il fatto che, quando esiste una soluzione ottima, ce ne sia una che è una soluzione di base ammissibile permette di limitare la ricerca dell’ottimo alle sole soluzioni di base ammissibili, che sono in numero finito (come segue dalla definizione di base). Dunque la programmazione lineare può essere vista come un problema di ottimizzazione discreta. Come vedremo nel capitolo successivo, questa osservazione è alla base del metodo del simplesso.

Il teorema precedente ha anche la seguente immediata conseguenza.

Corollario 2.7 Se un sistema in forma standard ha una soluzione ammissibile, allora ha una soluzione di base ammissibile.

Dimostrazione. Un sistema in forma standard ha la forma (2.9)–(2.10). Scegliendo c = 0 come vettore dei coefficienti della funzione obiettivo, ogni soluzione ammissibile del problema

(2.8)–(2.10) è una soluzione ottima. Il teorema precedente mostra che il programma lineare cos`ı ottenuto ha una soluzione ottima che è una soluzione di base ammissibile; nel nostro caso, possiamo parafrasare dicendo che il problema ha una soluzione ammissibile che è una

soluzione di base ammissibile. ◻

Chiudiamo il capitolo con un’importante precisazione. Mentre abbiamo visto che ogni sistema in forma standard che ammetta soluzione ha una soluzione di base ammissibile, questo non `e sempre vero per sistemi lineari generali. Ad esempio, il sistema di vincoli

x1+ x2+ x3≤1 x1+ x2 ≥0 x3≥0

non ha alcuna soluzione di base, in quanto non `e possibile estrarre dal sistema tre vincoli linearmente indipendenti. Tuttavia il sistema ammette soluzioni (ad esempio l’origine). Geo-metricamente, questo sistema definisce un poliedro non vuoto privo di vertici e dunque privo di soluzioni di base ammissibili.

Capitolo 3

Il metodo del simplesso

Come visto nel capitolo precedente, dato un programma lineare in forma standard che abbia una soluzione ottima, esiste una soluzione di base ottima. Dunque, in linea di principio, si potrebbe cercare una soluzione ottima enumerando tutte le soluzioni di base ammissibili del programma lineare e controllando quale tra queste d`a il miglior valore della funzione obiet-tivo. Questo approccio, tuttavia, richiederebbe un tempo eccessivo e sarebbe inapplicabile nella pratica, in quanto il numero di soluzioni di base di un programma lineare, nonostante sia sempre finito, pu`o essere estremamente alto anche per problemi di modeste dimensioni.

Inoltre, un tale approccio non permetterebbe di stabilire se il problema dato `e illimitato.

In questo capitolo verrà illustrato un algoritmo per la risoluzione di problemi di program-mazione lineare che esplora le soluzioni di base ammissibili in modo più intelligente rispetto all’enumerazione completa: il metodo del simplesso. Tale algoritmo permette di decidere se il problema è inammissibile, illimitato, o se ammette ottimo; in quest’ultimo caso, esso fornisce una soluzione ottima di base.

3.1 Forma tableau e condizioni di ottimalit` a

Consideriamo un generico problema di programmazione lineare ed assumiamo di averlo gi`a messo in forma standard:

max c^Tx s.a Ax = b

x ≥0,

dove i dati del problema sono A ∈ R^m×n, b ∈ R^m, c ∈ Rⁿ, e il vettore delle variabili è x ∈ Rⁿ. Tramite il metodo di eliminazione di Gauss, è possibile stabilire se il sistema Ax = b ha soluzioni. Se il sistema Ax = b non ammette soluzioni, allora il programma lineare dato è chiaramente inammissibile. Possiamo dunque assumere che il sistema Ax = b abbia almeno una soluzione. Sotto questa ipotesi, lo stesso metodo di Gauss restituisce un sistema equivalente ad Ax = b in cui il numero di righe è uguale al rango della matrice A. Possiamo dunque assumere senza perdita di generalità che rk(A) = m. Come visto nel capitolo precedente, la condizione rk(A) = m ci autorizza a parlare di soluzioni di base del problema.

Per convenienza nella trattazione, riscriviamo il programma lineare dato nella seguente forma equivalente:

max z (3.1)

s.a z − c^Tx =0 (3.2)

Ax = b (3.3)

x ≥0. (3.4)

Sia B ⊆ {1,... ,n} una base di A e sia N la cosiddetta non-base, cio`e N = {1,... ,n} ∖ B.

Allora valgono le seguenti equivalenze:

Ax = b ⇐⇒ A^Bx_B+ ANx_N =b ⇐⇒ x^B=A⁻¹_Bb− A⁻¹_BA_Nx_N.

Riscrivendo l’equazione (3.2) nella forma z − c^T_Bx_B− c^T_Nx_N =0 e sostituendo xB con A⁻¹_Bb− A⁻¹_BANxN, otteniamo

z− c^T_BA⁻¹_Bb−(c^TN− c^T_BA⁻¹_BA_N)x^N =0.

Definiamo

A¯_N =A⁻¹_BA_N (3.5)

¯b = A⁻¹_Bb (3.6)

c^T_N =c^T_N − c^T_BA⁻¹_BAN (3.7)

z = c^T_BA⁻¹_Bb. (3.8)

Il vettore ¯cN `e detto il vettore dei costi ridotti di c relativo alla base B. Allora il problema (3.1)–(3.4) `e equivalente al seguente programma lineare:

max z (3.9)

s.a z − ¯c^T_NxN =z¯ (3.10)

xB+ ¯ANxN = ¯b (3.11)

x ≥0. (3.12)

Si tenga ben presente che (3.10)–(3.12) `e precisamente lo stesso sistema di vincoli definito da (3.2)–(3.4) (nel senso che i due sistemi hanno le stesse soluzioni), solamente scritto in una forma diversa, che chiamiamo forma tableau rispetto alla base B. In questa forma, la funzione obiettivo e le variabili in base sono esplicitate rispetto alle variabili fuori base.

Spesso rappresenteremo il problema (3.10)–(3.12) in forma compatta attraverso il cosid-detto tableau del problema (3.1)–(3.4) rispetto alla base B, cio`e la matrice del sistema (3.10)–

(3.11). Assumendo per semplicit`a di scrittura che B ={1,... ,m} e dunque A = (A^B∣ A^N), il tableau `e la seguente matrice:

1 0^T −¯c^T_N z¯ }^{1 riga} 0 I A¯_N ¯b }^m^righe

®₁ °_m °_n−m ®₁

(3.13)

3.1. FORMA TABLEAU E CONDIZIONI DI OTTIMALIT `A 15 La prima colonna del tableau corrisponde alla variabile z, il blocco successivo alle variabili x (prima quelle appartenenti alla base e poi le altre), l’ultima colonna ai termini noti. La prima riga corrisponde all’equazione (3.10), le righe successive ai vincoli del sistema (3.11).

In generale, le variabili in base non saranno le prime m e non compariranno in ordine nei vincoli del problema in forma tableau. Se gli elementi di B sono B[1],... ,B[m] ∈ {1,... ,n}, allora il problema in forma tableau (3.10)–(3.12) pu`o essere scritto pi`u esplicitamente cos`ı:

max z (3.14)

Si noti che dal sistema in forma tableau (3.15)–(3.17) `e immediato ricavare la soluzione di base ¯x associata a B:

x_B_[i]= ¯b_i, i =1, . . . , m

¯ xN =0.

Tale soluzione può essere letta direttamente dalla colonna destra del tableau (3.13). Dunque la base B è ammissibile se e solo se ¯b ≥ 0, cioè se la colonna di destra del tableau contiene solo termini non-negativi. Il corrispondente valore della funzione obiettivo è ¯z: questo può essere verificato usando l’equazione (3.10) (si ricordi che ¯x_N =0) oppure osservando che

c^Tx = c¯ ^T_Bx¯B+ c^T_Nx¯N =c^T_BA⁻¹_Bb =z,¯

dove l’ultima uguaglianza segue dalla definizione di ¯zdata in (3.8). Dunque il tableau rispetto alla base B contiene nella posizione pi`u in alto a destra il valore della funzione obiettivo valutata nella soluzione di base associata a B.

Supponiamo che ¯c_N ≤ 0. In tal caso, per ogni soluzione ammissibile ˆx del problema (3.14)–(3.17), il valore della funzione obiettivo ˆz, calcolato tramite l’equazione (3.10), `e

z =z¯+ ¯c^T_Nxˆ_N ≤z,¯

dove abbiamo usato il fatto che ¯cN ≤0 e ˆxN ≥0. Pertanto, se la base B `e ammissibile, ¯x `e una soluzione ottima del programma lineare dato. Abbiamo dunque dimostrato il seguente risultato.

Lemma 3.1 Dato un programma lineare in forma standard, se i costi ridotti relativi ad una base ammissibile B sono non-positivi, allora la soluzione di base relativa a B `e ottima.

Quello appena enunciato è un criterio (sufficiente) per l’ottimalità: se determiniamo una base ammissibile i cui costi ridotti sono non-positivi, allora abbiamo trovato una soluzione ottima del problema. Come vedremo più avanti, questo sarà uno dei criteri di arresto per il metodo del simplesso.

Si presti attenzione al fatto che la prima riga del tableau contiene gli opposti dei costi ridotti, dunque la condizione da verificare `e che tali valori siano non-negativi. Inoltre, si noti che la condizione ha senso solo se siamo in presenza di una base ammissibile, cio`e se anche la colonna di destra del tableau contiene solo valori non-negativi.

Nel documento Note del corso di Ottimizzazione Discreta (pagine 15-22)