METODO E ALGORITMO DEL SIMPLESSO

La programmazione lineare serve per determinare l'allocazione ottimale di risorse disponibili in quantità limitata, per ottimizzare il raggiungimento di un obiettivo prestabilito, in condizioni di certezza.

In pratica, il suo scopo e è di:
- minimizzare le risorse che devono essere impiegate;
- massimizzare il valore ottenuto dalle risorse impiegate.

Pertanto, una volta formulato il problema e costruito un modello matematico lineare , al fine di ottenere la miglior soluzione si possono utilizzare algoritmi matematici standard. Il più importante (perché il più usato ed il più "comodo") è il metodo del simplesso (Per alcuni tipi di problemi, come quelli di trasporto ed assegnazione, esistono metodologie di risoluzione più efficienti del metodo del simplesso, ma applicabili solo a questi tipi di problemi).

Le condizioni da soddisfare per formulare un modello di programmazione lineare sono:

• tutte le variabili controllabili da chi assume le decisioni sul modello (variabili di decisione) devono essere non-negative (positive o tutt'al più nulle).
• il criterio per selezionare il miglior valore delle variabili di decisione può essere espresso da una funzione lineare di queste variabili, ovvero una funzione matematica che coinvolga solo le prime potenze di delle variabili e nessun prodotto tra le stesse. Quest'ultima prende il nome di funzione obiettivo.
• le limitazioni regolanti il processo, come la scarsità della materia prima, devono essere espresse come in un insieme di equazioni o disequazioni lineari; questo insieme prende il nome di insieme dei vincoli.

La soluzione di un problema di P.L. si ottiene determinando il valore delle variabili di decisione in modo da far assumere alla funzione obiettivo un valore massimo (od un minimo).

Per costruire un modello di P.L. occorre seguire i seguenti passaggi:

• Identificare le variabili di decisione e rappresentarle in termini di simboli algebrici;
• Identificare tutte le restrizioni o vincoli del problema ed esprimerli come equazioni o disequazioni lineari delle variabili di decisione;
• Identificare l'obiettivo e rappresentarlo come una funzione lineare delle variabili di decisione.

Per risolvere un problema di P.L. con due sole variabili si può utilizzare il metodo grafico. Quest'ultimo consiste nel rappresentare graficamente i vincoli sul piano cartesiano e individuare il valore massimo ammesso per la funzione obiettivo sul modello grafico.

Quando però le variabili sono due la risoluzione di un problema di P.L. con il metodo grafico è impossibile, perché avendo per esempio tre variabili di decisione X1, X2, X3 la rappresentazione con un sistema cartesiano delle stesse (con una rappresentazione spaziale) risulta estremamente difficoltosa. Si ricorre dunque al metodo del simplesso. La formulazione di questo metodo si deve al notissimo matematico americano G.B. Dantzig , che la sviluppò nel 1947.

Il metodo del simplesso si basa su un processo iterativo di calcolo del valore della funzione obiettivo nei vertici della soluzione ammissibile, fino a quando si trova il valore ottimale (o si verifica che tale valore non esiste). E importante notare come esso non prende in considerazione tutte le soluzioni ammissibili di base, che, anche se in numero finito, possono essere numerose, ma si limita a considerarne alcune e si arresta quando trova quella ottimale.

Quando il valore ottimale esiste ed è finito, il procedimento consiste nello spostarsi ripetutamente da un vertice all'altro adiacente al primo, in modo da ottenere un valore di Z (funzione obiettivo) maggiore di quello ottenuto in un precedente vertice. La ricerca termina non appena si trova che in nessun vertice adiacente la funzione obiettivo assume un valore maggiore: in questo caso si è raggiunta la soluzione ottimale. La soluzione così trovata è ottimale per le proprietà dell'insieme delle soluzioni ammissibili e per la linearità della funzione obiettivo.

In genere questo tipo di procedimento consente di determinare il valore ottimale della funzione obiettivo in un numero limitato di passi, in quanto il vertice successivo è sempre scelto in modo che accresca il valore della funzione obiettivo: così facendo è impossibile ritornare su un vertice già esaminato. Tanto più che, tra tutti i vertici, si determina sempre quello che incrementa maggiormente la funzione obiettivo.

Il problema è dunque quello di tradurre un procedimento prettamente geometrico in un procedimento analitico.

Il problema maggiore consiste nel determinare i vertici successivi in cui deve essere calcolato il valore della funzione obiettivo; inoltre la situazione è complicata dal fatto che i vincoli sono (generalmente) costituiti da disequazioni, difficilmente maneggiabili algebricamente.

Riassumendo, si tratta di:

• Trasformare le disequazioni in equazioni al fine di renderle più "trattabili"
• Trovare un processo iterativo che permetta di passare via via a soluzioni migliori, incrementando il valore della funzione obiettivo.

Ipotizzando per il modello di P.L. una forma del tipo

MAX:     Z = c₁X₁+c₂X₂+...+c_nX

a₁₁X₁ +a₁₂X₂  +... +a_1nX_n    £ b₁
a₂₁X₁ +a₂₂X₂ +... +a_2nX_n   £ b₂
a_k1X₁ +a_k2X₂  +... +a_knX_n   £ b_k

Il primo passo dal compiere per procedere ad una soluzione algebrica consiste nel trasformare il modello in uno equivalente che non contenga disuguaglianze ad eccezione dei vincoli di non-negatività, che però non generano problemi di alcun genere.

Questo passaggio implica l'introduzione di nuove variabili, le variabili di scarto.
Per esempio:
X £ 10
Nel nostro caso questa disequazione può essere sostituita dalla seguente equazione:
X+Xs = 10

dove Xs è lo scarto fra i due membri della diseguaglianza precedente e viene quindi detta variabile di scarto; il vincolo originale rimane valido se Xs è > 0, pertanto la disequazione :

X £ 10
può essere sostituita dalle condizioni :
X+Xs = 10
Xs ³ 0

Per trasformare il sistema di disequazioni precedentemente scritto nel nuovo sistema di equazioni è necessario aggiungere una variabile di scarto in ciascun vincolo, ovvero K variabili di scarto:

X_n+1 , X_n+2 , ... , X_n+k [1]

dove con la condizione che siano >0 , il primo sistema scritto diventa :

a₁₁X₁+a₁₂X₂+...+a_1nX_n +X_n+1 = b₁
a₂₁X₁+a₂₂X₂+...+a_2nX_n +X_n+2 = b₂         [2]
..........................
a_k1X₁+a_k2X₂+...+a_knX_n +X_n+k = b_k

mentre la Z viene modificata tenendo conto delle nuove variabili di scarto che in essa avranno coefficiente zero; questa modifica è pertanto puramente formale.

Una soluzione che verifica il sistema di vincoli [1] è una soluzione ammissibile del problema [2]. Tuttavia, poiché il sistema contiene (n+k) variabili e solo k vincoli, per ottenere una soluzione si debbono porre n variabili uguali a zero e indi risolvere il sistema con le rimanenti k variabili. Un sistema dive solo n variabili sono non nulle è una soluzione ammissibile di base, mentre se il numero delle variabili non nulle è < 0 la soluzione si dice soluzione ammissibile di base degenere.

In generale le soluzioni ammissibili di base del sistema [2] sono uguali alle combinazioni di classe n di (n+k).

Il procedimento del simplesso consiste nel:

• trasformare il modello in forma canonica;
• scegliere una soluzione ammissibile di base come soluzione iniziale;
• calcolare il corrispondente valore della funzione obiettivo;
• con un procedimento iterativo passare ad una nuova soluzione ammissibile di base in modo che la funzione obiettivo abbia un valore maggiore, finché non si ottengono più miglioramenti.

Schematizzando le fasi del metodo del simplesso:

Fase 1: Si convertono tutte le diseguaglianze in equazioni aggiungendo le variabili di scarto, una per ogni equazione.

Fase 2: Si sceglie una soluzione ammissibile di base e si calcola il corrispondente valore della funzione obiettivo.

Fase 3: Si sottopone la soluzione trovata alla prova di ottimalità. Essa consiste nel calcolare, per ogni variabile j che non appartiene alla soluzione di base, il valore dove D j sono i coefficienti che hanno le variabili della base nella funzione obiettivo.
La quantità così calcolata indica l’incremento della funzione obiettivo se la nuova variabile j entra nella base.
Quindi:
-se qualche D j è maggiore di zero la soluzione non è ottimale;
-se tutti i D j sono minori di zero si è pervenuti alla soluzione ottimale ed il procedimento termina;
-se esiste qualche D j uguale a zero allora la soluzione ottimale non è unica.

Fase 4: Si determina la variabile entrante X_j, ovvero la variabile che non appartiene alla base attuale e dovrà entrare nella prossima base. Quest’ultima deve avere:
- D j >0
- almeno uno dei coefficienti a_ij > 0, pena l’impossibilità di giungere ad una soluzione che rispetti i vincoli di non-negatività, sempre presenti.
La variabile entrante si sceglie in modo che, tra quelle che presentano un valore D j > 0, sia quella con il valore più alto.

Fase 5: Individuata la variabile entrante, si passa alla determinazione della variabile uscente. Si calcolano i rapporti termine noto/variabile di scarto con indice di colonna uguale a quello della variabile uscente e si sceglie il minore tra quelli non-negativi. Di esso verrà considerato il denominatore, il "Pivot", di cui si utilizza l’indice di riga per individuare la variabile uscente.

Fase 6: Si calcola la nuova matrice del simplesso, moltiplicando la riga dell’elemento Pivot (che coincide con quella dell’elemento uscente) per '1/Pivot' e sottraendo alle altre opportuni multipli di quest’ultima, in modo da ottenere tutti zeri sulla colonna dell’elemento Pivot (che sarà ovviamente 1 nel caso del Pivot stesso).

Fase 7: Si ripete in modo analogo il procedimento come nella Fase 2, finché la prova di ottimizzazione non determina che si è aggiunta la soluzione ottimale, che sarà quella costituente la base.