Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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 1a 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 = 11x1 + 10x2 . Nell’origine x1 = x2 = 0 → z = 0

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

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

  • c1 = 11 è la derivata parziale della z rispetto a x1
  • c2 = 10 è la derivata parziale della z rispetto a x2

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

Determinazione della variabile entrante

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

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

xs: cs = maxj {cj , cj > 0, ∀j non basico}
per un problema a massimizzare;

xs: cs = minj {cj , cj < 0, ∀j non basico}
per un problema a minimizzare.

Tabella 1. Variabile entrante


Determinazione della variabile uscente

Nella prima soluzione y1 = 20, y2 = 6.5, y3 = 36, y4 = 16. Se x1 entra nella soluzione il suo valore diventa > 0 e quindi le yi cambiano:

  • nella 1° equazione y1 = 20 + 5x1 – 4 x2
  • nella 2° equazione y2 = 6.5 – 0·x1 – x2
  • nella 3° equazione y3 = 36 – 3x1 – 4 x2
  • nella 4° equazione y4 = 16 – 2x1 – x2

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

Determinazione della variabile uscente (segue)

Dalle equazioni 3 e 4 del modello si possono ricavare le espressioni di y3 e y4 in funzione di x1 e x2.

y3 = 36 – 3x1 – 4 x2

y4 = 16 – 2x1 – x2

In figura sono riportati gli andamenti di y3 e y4 , cioè delle variabili che diminuiscono all’aumentare di x1.

Si può vedere che all’aumentare di x1 y4 si annulla per prima.


Tabella 1. Variabile uscente


Determinazione della variabile uscente


Trasformazione del sistema (pivoting)

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

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

L’operazione da compiere è la seguente:

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

Tabella 1. 2a soluzione basica ammissibile

La nuova soluzione basica ammissibile (s.b.a.) differisce dalla precedente per una sola variabile:

  • una variabile non basica (nulla) della precedente s.b.a. diventa basica (quindi >0)
  • una variabile basica della precedente s.b.a. (> 0) diventa non basica (quindi nulla)

Test di ottimalità sulla nuova soluzione basica ammissibile

Il test di ottimalità è soddisfatto se:

j corrispondente ad una variabile xj non basica, si verifica:

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

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


Tabella 3. 3a 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 bi sono nulli ed il valore calcolato con l’espressione θ = min {bi /ais : i ∈ {1,…, m}, ais > 0} sarà anch’esso nullo (a meno che non sia ais ≤ 0 per ogni riga i con bi = 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 xs entra in base con valore nullo.

Soluzione basica ammissibile degenere in A


Tabella 1. 1a soluzione basica ammissibile


Tabella 2. 2a soluzione basica ammissibile


Tabella 3. 3a soluzione basica ammissibile


Tabella 4. 4a 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.

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.


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion