Il metodo del simplesso. Soluzioni di base

Riprendiamo la Riformulazione rispetto alla base B, vista nell’articolo precedente:

Definizione

Si definisce soluzione di base associata alla base B, la seguente soluzione del sistema di vincoli di uguaglianza
ottenuta ponendo x_N = 0:

Nell’esempio che avevamo fatto precedentemente:

 

Riformulazione rispetto alla base B = {x₁, x₃}:

x₁ = 2
x₃ = 0
x₂=x₄=x₅ = 0

Ammissibilità e non degenerazione

Se A⁻¹_B b ≥ 0 la soluzione di base si dice ammissibile. Questo vuol dire che appartiene alla regione ammissibile del problema di PL in quanto, oltre a soddisfare i vincoli di uguaglianza del problema, soddisfa anche quelli di non negatività delle variabili.

Se A⁻¹_B b > 0 si parla di soluzione di base non degenere, altrimenti si parla di soluzione di base degenere. 

Nell’esempio:

B₂ = {x₁, x₃} → soluzione di base ammissibile e degenere

B₃ = {x₃, x₄}: la soluzione di base è:

x₃ = 6/7 x₄ = 2/7 x₁ = x₂ = x₅ = 0 che è ammissibile e non degenere

B₄ = {x₄, x₅}: la soluzione di base è:

x₄ = −1 x₅ = −3 x₁ = x₂ = x₃ = 0 che è non ammissibile.

Osservazione

Data una soluzione di base ammissibile e non degenere esiste un’unica base che la rappresenta, mentre una soluzione di base ammissibile e degenere è rappresentata da più basi.

Cosa hanno a che fare le basi e le soluzioni di base con il teorema fondamentale della PL?

La risposta ci viene dalla seguente osservazione.
Osservazione

L’insieme dei vertici di S_a coincide con l’insieme delle soluzioni di base ammissibili del problema di PL.
In pratica, vertici e di soluzioni di base ammissibili sono la stessa cosa vista da due punti di vista diversi: quello geometrico (i vertici) e quello algebrico (le soluzioni di base ammissibili).

Basi adiacenti

Definizione

Due basi B′ e B′′ si definiscono adiacenti se hanno m − 1 variabili uguali e differiscono per una sola variabile.

Nell’esempio le basi B₃ = {x₃, x₄} e B₄ = {x₄, x₅} sono adiacenti, mentre non lo sono B₂ = {x₁, x₃} e B₄.

Soluzioni di base adiacenti

Due soluzioni di base distinte si definiscono adiacenti se esistono due basi B′ e B′′ che le rappresentano e che sono tra loro adiacenti.
Si noti che due basi adiacenti non corrispondono necessariamente a due soluzioni di base adiacenti. Esse infatti possono corrispondere alla stessa soluzione di base come accade, ad esempio, con le basi
B₂ ={x₁, x₃} e B₅={x₁, x₄}.

Passaggio ad una base adiacente

Supponiamo ora di voler passare dalla base B alla base adiacente B′ ottenuta rimuovendo da B la variabile x_ik,
1≤k≤m, e sostituendola con la variabile fuori base x_im+h, 1≤h≤n−m, ovvero:

B′ ={x_i1 , . . . , x_ik−1 , x_im+h , x_ik+1 , . . . , x_im}.

La prima domanda che ci dobbiamo porre è :quando B′ è effettivamente una base. Perché lo sia si deve avere che A_B′ è invertibile.

Si ha che AB′ è invertibile e quindi B′ è una base se e solo se nella riformulazione associata alla base B il coefficiente di x_im+h nell’equazione relativa a x_ik è diverso da 0.

Nell’esempio:
{x₁, x₂} non è una base
{x₁, x₅} è una base

Esempio

Dalla riformulazione rispetto a B2 = {x1, x3} a quella rispetto a B6 = {x1, x5}

Ricavo x₅ dall’equazione relativa a x₃
x₅ = 0 − x₃ + 3x₄

Sostituisco la parte destra dell’equazione nei restanti vincoli e nell’obiettivo:

Nota bene
Per poter recuperare dalle riformulazioni alcune informazioni (nel seguito vedremo, ad esempio, come sfruttare la riformulazione rispetto a una base B per poter ottenere la matrice A⁻¹ _B ) è necessario mantenere un ordine tra le variabili in una base. Quindi se nella base B′ la variabile x_im+h sostituisce la variabile x_ik a cui corrisponde la k-esima equazione della riformulazione rispetto a B, nella riformulazione rispetto a B′ l’equazione relativa alla variabile x_im+h dovrà ancora essere la k-esima, mentre la posizione delle equazioni relative a tutte le altre variabili deve rimanere invariata rispetto alla precedente
riformulazione.

Nell’esempio …

… la variabile x₅ ha preso il posto della x₃ e l’equazione relativa alla x₅ è stata messa nella stessa posizione (la seconda) in cui si trovava quella della x₃, mentre la restante equazione ha mantenuto la posizione originaria.

Un altro esempio

Passaggio da B₆ = {x₁, x₅} a B₄ ={x₄, x₅}

Ricavo x₄ dall’equazione relativa a x₁

x₄ = −1 + 1/2x₁+x₂ + 3/2x₃

Sostituisco la parte destra dell’equazione nei restanti vincoli e nell’obiettivo:

Nota bene
Le operazioni  che abbiamo eseguito sugli esempi ci hanno consentito di passare da una base ad una adiacente e, nel secondo esempio, anche da una soluzione di base ad una adiacente. Tuttavia, nel secondo caso siamo passati da una soluzione di base ammissibile (quella associata a B₆) ad una non ammissibile (quella associata a B₄). Nell’algoritmo di risoluzione che andremo a discutere la scelta della base adiacente verso cui muoversi non verrà fatta a caso come abbiamo fatto nei precedenti esempi, ma sarà guidata da regole precise che fondamentalmente ci consentiranno di spostarsi tra vertici della regione ammissibile migliorando il valore della funzione obiettivo.

(58)