Programmazione lineare. Il metodo del simplesso

[elementor-template id=”14219″]

Problemi di programmazione lineare

Un problema di ottimizzazione vincolata è definito dalla massimizzazione di una funzione obiettivo sotto un certo numero di vincoli: si vuole trovare la soluzione che massimizza o minimizza la funzione obiettivo f tra tutte le soluzioni x che soddisfano un dato insieme di vincoli definiti come funzioni g_i. In termini matematici possiamo scrivere:

min(max) f(x)
s.t. g_i(x) ≤, ≥ oppure = bi ∀i = 1..m
x ∈ Rⁿ

dove
– x = (x₁, x₂, . . . , x_n) è un vettore di n variabili reali (ciascun vettore rappresenta una potenziale soluzione del problema);
– f e g_i sono funzioni Rⁿ → R
– b_i ∈ R

Un problema di Programmazione Lineare (PL) è un problema di ottimizzazione in cui la funzione obiettivo f e tutti i vincoli g_i sono funzioni lineari delle variabili x:

Una soluzione ammissibile di un problema di PL è un vettore che soddisfa tutti i vincoli.
L’insieme di tutte le soluzioni ammissibili si dice regione ammissibile.
Una soluzione ottima è una soluzione ammissibile che ottimizza (miminizza o massimizza) il valore della funzione obiettivo tra tutte le soluzioni ammissibili.
Non sempre un problema di PL ammette una soluzione ottima. Infatti, ogni problema di PL soddisfa sempre e solo uno dei 3 casi seguenti:

1. il problema è inammissibile: l’insieme delle soluzioni ammissibili è vuoto;

2. il problema è illimitato: è possibile trovare delle soluzioni ammissibili che fanno diminuire (o aumentare per problemi di massimo) il valore della funzione obiettivo a piacere.
3. il problema ammette soluzione ottima: esiste almeno una soluzione ammissibile che ottimizza la funzione obiettivo (e il valore ottimo della funzione obiettivo è limitato).

Risolvere un problema di PL significa riconoscere uno dei tre casi citati e dare, nel caso 3, una soluzione ottima e il corrispondente valore della funzione obiettivo.

Da un punto di vista geometrico, una soluzione è un punto nello spazio n-dimensionale e la regione ammissibile è un poliedro convesso nello stesso spazio.

Si ha il seguente importante risultato:

Proprietà 1
Dato un problema di PL, se il poliedro P delle soluzioni ammissibili è non vuoto e limitato, allora esiste almeno una soluzione ottima corrispondente con un vertice di P (vertice di P ottimo).

Soluzione di un problema di PL

Per poter manipolare algebricamente un problema di programmazione lineare, è conveniente vedere la regione ammissibile come l’insieme delle soluzioni di un sistema di equazioni e disequazioni lineari.
Delle semplici trasformazioni permettono di scrivere un qualsiasi problema di PL nella seguente forma standard:

dove
– la funzione obiettivo è di minimo (si moltiplicano per -1 le funzioni di massimizzazione);
– tutte le variabili sono positive o nulle (si effettuano sostituzioni di variabili per le variabili libere o negative);
– tutti i vincoli sono delle equazioni (si aggiunge una variabile positiva di slack (residuali) per i vincoli di ≤ e si sottrae una variabile positiva di surplus per i vincoli di ≥);
– i termini noti b_i sono tutti positivi o nulli (si moltiplicano per -1 i vincoli con termine noto negativo).
Ciò permette, senza perdere in generalità, di risolvere un qualsiasi problema di PL tramite sistemi di equazioni lineari.

Sistemi di equazioni lineari

Sistemi di equazioni in forma matriciale:

un sistema di m equazioni in n incognite può essere messo in forma matriciale:
Ax = b, con A ∈ R^m×n, b ∈ R m e x ∈ Rⁿ

• Teorema di Rouchè-Capelli

ll sistema lineare Ax = b ammette soluzioni se e solo se il rango della matrice completa è uguale al rango della matrice incompleta.

•  Operazioni elementari su matrici:

– scambiare la riga i con la riga j;
– moltiplicare la riga i per uno scalare non nullo;
– sostituire alla riga i, la riga i più α volte la riga j (α ∈ R).
Le operazioni elementari sulla matrice aumentata [A|b] non alterano l’insieme delle soluzioni ammissibili del sistema Ax = b.

• Metodo di Gauss-Jordan per la soluzione di sistemi Ax = b: eseguire delle operazioni elementari sulla matrice aumentata in modo da ottenere in A una sottomatrice identità di dimensioni pari a ρ(A) = ρ(A|b).

Qui puoi trovare tutto sulle matrici.

Proprietà 2 (Corrispondenza tra vertici e soluzioni di base).

Dato un sistema di equazioni Ax = b e il corrispondente poliedro della regione ammissibile P = {x ∈ Rⁿ: Ax = b}, x è soluzione di base del sistema Ax = b ⇐⇒ x è vertice di P.

TEOREMA FONDAMENTALE DELLA PROGRAMMAZIONE LINEARE.

Se esiste una soluzione ottima di un problema di PL in due variabili di azione, essa è situata in corrispondenza di un vertice della regione delle soluzioni ammissibili.
Se esistono due punti in corrispondenza dei quali c’è una soluzione ottima, allora questa si trova in corrispondenza di infiniti punti, quelli situati sul lato (segmento o semiretta) contenente i due punti.

Cos’è il metodo del simplesso

Il metodo del Simplesso si applica nella risoluzione di un problema di Programmazione Lineare, (funzione e vincoli lineari) quando le variabili di azione o iniziali sono almeno tre ed il sistema dei vincoli non contiene uguaglianze.
Infatti se vi è un vincolo sotto forma di uguaglianza, si possono ridurre le variabili da tre a due e procedere con il metodo grafico.

Nel caso in cui le variabili siano due, pur potendosi applicare il metodo del simplesso, si preferisce applicare, perché più semplice, il metodo grafico.
Il metodo del simplesso è un algoritmo che, attraverso un numero finito di passaggi, consente di andare da una soluzione iniziale, detta ammissibile di base, ottenuta ponendo uguale a zero le variabili di azione nel sistema e che rispetta i vincoli di segno, ad una soluzione via via migliore, fino a che non si perviene a quella ottima.

Il metodo del simplesso considera un problema in forma standard e necessita di una soluzione ammissibile di base di partenza. Il metodo passa iterativamente da una soluzione ammissibile di base ad una adiacente che permetta di migliorare il valore corrente della funzione obiettivo, fino al raggiungimento dell’ottimo (soluzione ottima di base) o fino a determinare che il problema è illimitato. Ovviamente, il terzo caso (problema inammissibile) è escluso, visto che partiamo da una soluzione di base ammissibile. Introdurremo il metodo del simplesso aiutandoci con il seguente esempio.

ESEMPIO SEMPLICE

METODO DEL SIMPLESSO PER I PROBLEMI DI MASSIMO

Riprendiamo l’esempio visto in Cos’è la programmazione lineare 

che è stato tradotto nel seguente schema matematico, dove al posto di x, y mettiamo per comodità rispettivamente x₁, x₂:

Rendere massima la funzione:
ω = 1,2 x₁ + 0,9 x₂ – 390
sotto le condizioni seguenti:
x₂ ≥ 400 , x₁ + x₂ ≤ 900 , 2 x₁ – x₂ ≤ 0 ,
e naturalmente con x₁≥ 0, x₂ ≥ 0.

Ci proponiamo di risolvere questa questione con un procedimento diverso da quello esposto in precedenza. Questo nuovo procedimento può apparire farraginoso e dispendioso, insomma un virtuosismo inutile ed una perdita di tempo. Ti invito, tuttavia, ad armarti di pazienza ed a seguire il discorso. Fra breve ne capirai i motivi.

Introducendo tre nuove variabili non negative – x₃, x_4, x₅ – trasformiamo anzitutto il sistema delle tre disequazioni che costituiscono i vincoli in un sistema di altrettante equazioni:

Otteniamo un sistema di 3 equazioni in 5 incognite. Questo significa che a 2 delle 5 variabili possiamo
attribuire valori arbitrari e ricavare, in funzione di essi, i valori delle altre 3 variabili.
Risolviamo allora il sistema (1) esprimendo x₁, x₂, x₃ in funzione di x₄, x₅. Otteniamo:

La funzione obiettivo ω, espressa essa pure per mezzo di x₄, x₅, diventa allora:

Da qui, si desume che il massimo di ω si ha quando a 510 si sottraggono i valori più piccoli possibile, vale a dire, ricordando che x₄ ≥ 0 e x₅ ≥ 0, quando x₄ = x₅ =0. Dunque: max (ω)=510 .
I valori di x₁ ed x₂ – che sono quelli che c’interessano – per i quali si ha questo massimo, si trovano sostituendo x₄=0 e x₅=0 nelle ultime due equazioni del gruppo (1). Si ottiene: x₁=300, x₂=600 .

Tutto esattamente come per l’esempio visto nell’articolo precedente.

Ad onor del vero, siamo stati fortunati ad ottenere che nell’espressione (2) di ω i coefficienti delle variabili x₄ ed x₅ fossero tutte e due negativi. Questo ci ha permesso di giungere rapidamente alla conclusione. D’altronde, a quell’espressione di ω siamo giunti perché abbiamo deciso di esprimere, nelle equazioni (1), le variabili x₁, x₂, x₃ in funzione di x₄, x₅.
Sorge, allora, naturale il seguente interrogativo: Se avessimo operato una scelta diversa delle variabili da assumere come quantità note, sarebbe cambiato qualcosa?

E’ quello che vedremo prossimamente.

(716)

PubblicitàPubblicità