Antonio Sforza » 7.Ottimizzazione lineare: Algoritmo del Simplesso - II parte

Schema della lezione

La trasformazione del sistema di relazioni vincolari in un sistema di equazioni risulta più o meno immediata, in relazione ai tipi di vincoli che compongono il modello. Si distinguono due casi:

• (a) tutti i vincoli sono del tipo ≤,
• (b) c’è almeno un vincolo del tipo ≥ o =.

In questa lezione si descrive l’algoritmo del simplesso nel caso che il sistema di vincoli sia costituito solo da disequazioni del tipo ≤.
Si esamina anche il caso delle soluzioni basiche ammissibili degeneri.

Vincoli del tipo ≤

Se i vincoli del modello sono tutti del tipo ≤ il sistema di equazioni ottenuto con l’aggiunta delle variabili slack è in forma canonica rispetto ad esse. E’ quindi possibile determinare immediatamente una prima soluzione basica ammissibile. Essa corrisponde al vertice origine degli assi. Esso appartiene al dominio di ammissibilità proprio perché i vincoli sono tutti del tipo ≤.

Nel seguito, attraverso un esempio numerico, si descrive l’algoritmo articolato nei seguenti passi:

• prima soluzione basica ammissibile
• test di ottimalità sulla 1^a soluzione basica ammissibile
• variabile entrante, variabile uscente, trasformazione del sistema
• nuova soluzione basica ammissibile
• test di ottimalità sulla nuova soluzione basica ammissibile

Sistema di equazioni in forma canonica

Tabella iniziale dell’algoritmo del Simplesso

Prima soluzione basica ammissibile

Esempio numerico

Tabella 1. Prima soluzione basica ammissibile

Test di ottimalità sulla prima soluzione basica ammissibile

Analisi dei coefficienti cj delle variabili non basiche
z = 11x₁ + 10x₂ . Nell’origine x₁ = x₂ = 0 → z = 0

Se x₁ passa da 0 a 1, z passa da 0 a 11 e quindi c₁ = 11 rappresenta il tasso di variazione della funzione z per una variazione unitaria di x₁ .

Analogamente, se x₂ passa da 0 a 1 z passa da 0 a 10 e quindi c₂=10 rappresenta il tasso di variazione della funzione z per una variazione unitaria di x₂ . In altri termini:

• c₁ = 11 è la derivata parziale della z rispetto a x₁
• c₂ = 10 è la derivata parziale della z rispetto a x₂

Poiché il problema è a massimizzare, se c_j > 0 è possibile migliorare la z (cioè trovare una soluzione migliore) se x_j passa da 0 a 1. Ci interessano pertanto le variabili con c_j > 0 che sono quindi candidate ad entrare nella soluzione.

Determinazione della variabile entrante

In generale si sceglie la variabile a cui corrisponde il c_j migliore (cioè più elevato in modulo):

• c_j ≤ 0 per un problema di massimizzazione
• c_j ≤ 0, per un problema di minimizzazione

x_s: c_s = max_j {c_j , c_j > 0, ∀j non basico}
per un problema a massimizzare;

x_s: c_s = min_j {c_j , c_j < 0, ∀j non basico}
per un problema a minimizzare.

Tabella 1. Variabile entrante

Determinazione della variabile uscente

Nella prima soluzione y₁ = 20, y₂ = 6.5, y₃ = 36, y₄ = 16. Se x1 entra nella soluzione il suo valore diventa > 0 e quindi le y_i cambiano:

• nella 1° equazione y₁ = 20 + 5x₁ – 4 x₂
• nella 2° equazione y₂ = 6.5 – 0·x₁ – x₂
• nella 3° equazione y₃ = 36 – 3x₁ – 4 x₂
• nella 4° equazione y₄ = 16 – 2x₁ – x₂

Poiché nessuna delle y_i può diventare negativa, da ogni equazione possiamo ricavare il valore limite che x₁ può assumere senza che la y_i si annulli.
Nella 1° equazione y₁ aumenta al crescere di x₁ .
Nella 2° equazione il coefficiente della x₁ è 0 e quindi, qualunque sia x₁, y₂ non cambia.
Nella 3° equazione y₃ diminuisce all’aumentare di x₁ e si annulla per x₁ = 36/3 = 12
Nella 4° equazione y₄ diminuisce all’aumentare di x₁ e si annulla per x₁ = 16/2 = 8
Per fare in modo che nessuna y_i si annulli è necessario scegliere il minimo dei valori limite calcolati per x₁.
Mini b_i/a_i1 (a_i1>0) = Min {36/3, 16/2}= 16/2 = 8 → Variabile uscente y₄ nella 4° equazione.

Tabella 1. Variabile uscente

Determinazione della variabile uscente

Trasformazione del sistema (pivoting)

Dividere tutti gli elementi della riga pivot r (e_r) per a_is, ottenendo una nuova configurazione e_r‘ = e_r / a_rs,
che presenterà quindi sicuramente un 1 nell’elemento di posto r_s (a_rs‘ = 1);

Trasformare ciascuna riga i del sistema in modo da indurre la presenza di uno 0 nell’elemento di posto is (a_is = 0, “i =1,…, m);

L’operazione da compiere è la seguente:

a ciascuna riga si sottrae la riga pivot trasformata (e_r‘ )
moltiplicata per l’elemento della riga i
che è nella colonna pivot s (a_is ) : e_i‘ = e_i – a_is e_r‘

Test di ottimalità sulla nuova soluzione basica ammissibile

Il test di ottimalità è soddisfatto se:

∀j corrispondente ad una variabile x_j non basica, si verifica:

• c_j ≤ 0 per un problema di massimizzazione
• c_j ≥ 0, per un problema di minimizzazione

Tabella 2. Test di ottimalità, variabile entrante, variabile uscente

Tabella 3. 3^a soluzione basica ammissibile

Percorso dell’algoritmo del Simplesso

Soluzioni degeneri

Una soluzione basica ammissibile di un problema m x n (m vincoli ed n variabili) è degenere quando una (o più) delle m variabili basiche assume valore nullo.

La soluzione presenterà quindi m’ < m variabili strettamente positive ed n – m’ > n – m variabili nulle.

Le variabili basiche nulle si definiscono variabili degeneri.

In presenza di degenerazione uno o più termini noti b_i sono nulli ed il valore calcolato con l’espressione θ = min {b_i /a_is : i ∈ {1,…, m}, a_is > 0} sarà anch’esso nullo (a meno che non sia a_is ≤ 0 per ogni riga i con b_i = 0).

Il risultato dell’operazione di pivoting sarà allora un cambiamento di soluzione basica ammissibile non collegato ad uno spostamento da un vertice ad un altro, perché θ = 0 e la variabile x_s entra in base con valore nullo.

Soluzione basica ammissibile degenere in A

Tabella 1. 1^a soluzione basica ammissibile

Tabella 2. 2^a soluzione basica ammissibile

Tabella 3. 3^a soluzione basica ammissibile

Tabella 4. 4^a soluzione basica ammissibile

Soluzione basica ammissibile degenere in D

Si può avere una soluzione basica ammissibile degenere anche se un vertice del dominio giace su un asse coordinato. In questo caso il vincolo ridondante è lo stesso asse.