METODO DEL SIMPLESSO PER I PROBLEMI DI MINIMO. Esempio risolto con il metodo del pivot

METODO DEL SIMPLESSO PER I PROBLEMI DI MINIMO

La procedura seguita per i problemi di massimo può essere ripetuta, con qualche necessario adattamento, anche nel caso in cui una data funzione deve essere resa minima.
Precisamente, adesso lo scopo del simplesso è quello di esprimere la funzione obiettivo come un polinomio, nelle variabili attive e fittizie, con coefficienti tutti positivi (o, almeno, non negativi), in modo che ponendo uguali a zero tali variabili si ottenga appunto il valore minimo della funzione obiettivo.
Come prima, questo significa che nella riga degli indicatori nella matrice “ottima” del simplesso devono figurare solo valori positivi o nulli.
Tutto il resto rimane invariato, o quasi. C’è infatti una piccola difficoltà in più.

Per far capire come funzioni l’algoritmo del simplesso per i problemi di minimo ci affidiamo ancora ad un esempio. Sia allora il seguente problema di minimo.

PROBLEMA.

Rendere minima la funzione:
ω = 4 x₁ + 4 x₂ – 15,
con x₁, x₂ numeri reali non negativi, sotto le condizioni seguenti:
4 x₁ + x₂ ≥ 22,
2 x₁ + x₂ ≥ 17,
2 x₁ + 3 x₂ ≥ 27.

SOLUZIONE

Constatiamo per prima cosa che la funzione obiettivo può esser messa nella forma seguente:

ω = 4 (x₁ + x₂) – 15

per cui, posto: ω’=x₁+x₂, è evidente che min(ω) = 4 min(ω’)–15. Assumiamo allora provvisoriamente come funzione obiettivo la funzione ω’.
Introdotte tre variabili fittizie u₁, u₂, u₃ (non negative), il sistema delle tre disequazioni costituenti i vincoli tecnici del problema si trasforma nel seguente sistema di equazioni:

Costruiamo quindi la prima matrice del simplesso:

La soluzione ottenuta ponendo x₁=x₂=0, cui corrispondono u₁=–22, u₂=–17, u₃=–27, non è una soluzione base ammissibile giacché in essa figurano valori negativi, mentre nessuno di essi dovrebbe esserlo. Ora questo origina un problema. Per superarlo bisogna introdurre delle variabili cosiddette “artificiali”. Le variabili artificiali sono tante quanti sono i vincoli tecnici: tre nel caso specifico. Le indichiamo con a₁, a₂, a₃, e non devono assumere valori negativi, come le variabili attive e fittizie, anzi addirittura il loro valore si suppone che sia arbitrariamente grande: lo indichiamo con a. Il sistema delle equazioni diventa allora il seguente:

Ripetiamo che l’introduzione delle variabili artificiali ha il solo scopo di ottenere una soluzione base ammissibile. Esse, come si vedrà, non interverranno nella soluzione del problema.
Ebbene, la prima matrice del simplesso, modificata con l’introduzione delle variabili artificiali, è la seguente, che però indichiamo come matrice 0 del simplesso per una ragione che sarà chiara fra breve:

matrice 0 del simplesso

A questo punto bisogna operare in modo che diventino nulli gli indicatori nelle tre colonne delle variabili artificiali e lo scopo si consegue moltiplicando ognuna delle tre righe principali per –a e sommando i termini in colonna compresi quelli della riga degli indicatori: i valori ottenuti costituiscono la nuova riga degli indicatori.

Per esempio, il primo termine di tale riga è: (–4a–2a–2a)+1=1–8a, mentre il termine noto è: –22a–17a–27a=–66a.

Con tale accorgimento la nuova matrice, che assumiamo come vera e propria prima matrice del simplesso, è la seguente:

prima matrice del simplesso

Posto adesso x₁=x₂=u₁=u₂=u₃=0 si ha a₁=22, a₂=17, a₃=27: è una soluzione base ammissibile. Si tratta di vedere se è possibile migliorarla e lo scopo si raggiunge facendo sì che nella riga degli indicatori non figurino termini negativi (a parte il termine noto): attualmente ce ne sono cinque, compresi i termini 1–8a e 1–5a (ricordiamo che a si può considerare arbitrariamente grande e positivo).
Si procede esattamente come nel caso dei problemi di massimo.
Allora, per prima cosa si individua il pivot nella prima matrice del simplesso (è contrassegnato con un asterisco): precisiamo che la colonna del pivot è adesso quella dell’indicatore negativo col massimo valore assoluto. In secondo luogo si modificano nel modo conosciuto, dapprima gli altri termini della riga del pivot e poi i termini delle altre righe. Si ottiene, a conti fatti, la seconda matrice del simplesso:

seconda matrice del simplesso

Poiché nella riga degli indicatori permangono termini negativi bisogna continuare, procedendo al solito modo. Si costruisce così la terza matrice del simplesso:

terza matrice del simplesso

Non ancora è stato raggiunto lo scopo, per cui bisogna proseguire con la costruzione della quarta matrice del simplesso:

quarta matrice del simplesso

Nella riga degli indicatori non ci sono più termini negativi (a parte il termine noto), questa è la matrice “ottima” del simplesso e da essa si ricava la soluzione ottimale, vale a dire:
min(ω’) = –(–11) = 11 per x₁=6 e x₂=5.
Di conseguenza, per tali medesimi valori:
min(ω) = 4 min(ω’) – 15 = 4 x 11 – 15 = 29.
Detto per inciso, i valori delle variabili fittizie sono i seguenti: u₁=7, u₂=u₃=0.

Metodo del pivot

L’operazione di pivot consiste nel combinare linearmente le righe di T in modo da ottenere una colonna unitaria in posizione prestabilita.

Per eseguire un’operazione di pivot basta:

ESEMPIO:

1. Scegliere un elemento di pivot a_hk’

2. Dividere la riga 2 per a₂₃’

3. Sottrarre alla riga 1 la riga 2 moltiplicata per a₁₃’

3. Sottrarre alla riga 3 la riga 2 moltiplicata per a₃₃’

4. Sottrarre alla riga 0 la riga 2 moltiplicata per c₃’

[elementor-template id=”14302″]
[no_toc]

(961)

PubblicitàPubblicità