Programmazione lineare. Il metodo del simplesso ( Parte II)

Nel precedente articolo , dopo aver risolto l’esercizio, ci eravamo posti il seguente interrogativo: Se avessimo operato una scelta diversa delle variabili da assumere come quantità note, sarebbe cambiato qualcosa?

Proviamo, per esempio, ad esprimere, sempre nelle (1),

le variabili x₃, x₄, x₅ in funzione di x₁ ed x₂.
Otteniamo:

mentre la funzione obiettivo rimane ovviamente:

ω = 1,2 x₁ + 0,9 x₂ – 390 .

Adesso, nell’espressione di ω, i coefficienti delle variabili x₁ ed x₂ sono entrambi positivi e, si capisce facilmente, più grandi sono i valori che si attribuiscono a tali variabili, più grande è il valore di ω.
Ma fin dove possiamo spingerci per avere il massimo di ω? Non possiamo stabilirlo ragionando su quell’espressione di ω. Dobbiamo concludere che quell’espressione non è idonea al nostro scopo e dobbiamo provare altre vie.

In altri termini, l’aver espresso le variabili x₃, x₄, x₅ in funzione di x₁ ed x₂ conduce ad un’espressione di ω – in funzione di x₁ ed x₂ – sulla quale non siamo in grado di concludere alcunché. Bisogna allora scegliere altre tre variabili da esprimere in funzione delle due rimanenti. In seguito ad alcuni tentativi si giunge, di solito, ad una situazione, in cui i coefficienti delle variabili che figurano nell’espressione di ω sono tutti negativi: la conclusione adesso è immediata.
In teoria potrebbe però capitare che, dopo aver effettuato tutti i possibili tentativi, non si trovi una funzione ω con le caratteristiche suddette. Si deve concludere che essa non ha un massimo.
Osserviamo, a questo riguardo, che, nel caso in esame, i possibili tentativi sono tanti quanti i modi di esprimere 3 delle 5 variabili x₁, x₂, x₃, x₄, x₅ in funzione delle 2 rimanenti; vale a dire che questi possibili tentativi sono tanti quante le combinazioni di 5 oggetti presi a 3 a 3, cioè sono in numero di:

Cosicché questo metodo, se non si è fortunati nella scelta delle variabili da esprimere in funzione di altre, può essere piuttosto lungo, se non proprio complicato. Ed allora ci si potrebbe chiedere se sia veramente il caso di occuparsene visto e considerato che disponiamo già del metodo grafico, che è un metodo pratico ed economico.( vedi esempio qui)

Il fatto è che al metodo grafico nel piano si può ricorrere finché si ha a che fare con problemi in due variabili (o riconducibili a due variabili). Ciò non è, invece, possibile quando le variabili sono in numero maggiore.
In tal caso si può ricorrere ad un metodo algebrico, noto come metodo del simplesso, del quale, a parte qualche dettaglio, quello che abbiamo descritto precedentemente è un particolare esempio, benché applicato al caso di due variabili di azione.
Cerchiamo allora di descrivere meglio questo metodo.

Lo faremo ancora con riferimento all’esempio visto in precedenza:

Considerata la funzione obiettivo:
ω = 1,2 x₁ + 0,9 x₂ – 390 ,
in cui x₁ ≥ 0 e x  ≥ 0, bisogna renderla massima sotto il sistema di vincoli:
x₂ ≥ 400,
x₁+ x₂ ≤ 900,
2x₁ – x₂ ≤ 0.

Si deve prima di tutto trasformare questo sistema di disequazioni in un sistema di equazioni. Si consegue lo scopo con l’introduzione di tante variabili non negative – chiamate variabili aggiunte (o di scarto o anche fittizie) – quante sono le disequazioni del sistema. Nel nostro caso con l’introduzione di 3 variabili aggiunte: u₁, u₂, u₃. Otteniamo il sistema (1) scritto in precedenza, ma nel quale adesso figurano le variabili u₁, u₂, u₃ al posto di x₃, x₄, x₅ rispettivamente:

La soluzione che rende massima la funzione ω è costituita dalla coppia (x1 , x2) che, assieme alla terna (u1, u2, u3 ), forma la cinquina (x1 , x2, u1, u2, u3 ) la quale è soluzione del sistema (3).
Il nostro scopo è quello di esprimere ω come somma di una quantità costante e di un polinomio omogeneo di 1° grado in 2 delle 5 variabili introdotte (2 attive e 3 fittizie), convenientemente scelte, con coefficienti tutti negativi (o, quantomeno, non positivi). Di modo che, ponendo uguali a 0 le due variabili del polinomio suddetto, si ottiene il valore massimo
di ω e nello stesso tempo, utilizzando il sistema ( 3) o un altro sistema equivalente ad esso, si determinano i valori delle variabili di azione che mancano (diciamo così, poiché qualcuna di esse potrebbe figurare nell’ultima espressione di ω e perciò ad essa è stato attribuito il valore 0) e per i quali si ha quel valore massimo.
La scelta delle tre variabili rispetto alle quali risolvere il sistema (3) non è del tutto casuale.

In effetti, esse devono risultare tutte non negative quando le altre due sono nulle. Questo, chiaramente, perché la cinquina deve essere costituita da valori non negativi.

Realmente, quando u₂=u₃=0, si trova rapidamente: x₁=300, x₂=600, u₁=200.

Se la scelta, invece che su x₁, x₂, u₁, fosse caduta, per esempio, su u₁, u₂, u₃, ponendo x₁=x₂=0 avremmo trovato:
u₁=–400, u₂ =900, u₃=0 .
La prima scelta è buona, la seconda no.

Anche la scelta u₁=0, u₂=0 sarebbe stata buona, dal momento che in tal caso sarebbe risultato:
x₁=200, x₂=400, u₂=300.

Allora, generalizzando al caso di n equazioni in n + m incognite:
quando si applica il metodo del simplesso, è fondamentale scegliere correttamente le n variabili – dette variabili di base – che si assumono come incognite e le m variabili – dette variabili non di base – rispetto alle quali le prime devono essere espresse (e che, provvisoriamente si considerano quantità note).
Ripetiamo che la scelta è valida se, attribuendo valore 0 a tutte le variabili non di base, si ottengono valori non negativi per quelle di base.

La soluzione del sistema di equazioni che così si ottiene potrebbe già dar luogo al valore ottimale di ω, ma potrebbe ancora aver bisogno di essere ottimizzata: essa si chiama una soluzione base ammissibile del sistema.

Talora i tentativi volti a trovare una soluzione base ammissibile richiedono un po’ di tempo prima di sortire l’effetto voluto.
Per esempio, ritornando al sistema (3), fissiamo l’attenzione sulla seguente cinquina di valori, ottenuta pensando u₁=u₃=0:
x₁= 200, x₂= 400, u₁= 0, u₂= 300, u₃ = 0.

Essa è una soluzione base ammissibile del sistema (3). Le variabili x₁, x₂, u₂ sono le variabili di base;
le variabili u₁, u₃ sono le variabili non di base.
Potrebbe capitare che questa soluzione base ammissibile conduca già al valore ottimale della funzione obiettivo. In questo caso la ricerca sarebbe terminata.
Nel nostro esempio non è così. Infatti, esprimendo x₁, x₂, u₂ in funzione di u₁ ed u₃, si trova:

Come si vede, nell’espressione di ω, i coefficienti delle variabili u₁ ed u₃ non sono entrambi negativi.
Se invece la scelta fosse caduta sulla seguente cinquina, ottenuta pensando u₂= u₃= 0:

e da qui, proprio perché _u2=u3=0, avremmo ricavato rapidamente la soluzione:
max (ω) = 510  per x₁= 300 ed x₂ = 600

Riepiloghiamo

Una volta che è stata trovata per tentativi una soluzione base ammissibile e sono state espresse le variabili di base e la funzione obiettivo per mezzo delle variabili non di base, si possono ottenere due situazioni:
a) nell’espressione della funzione obiettivo i coefficienti delle variabili non di base sono tutti negativi (o, almeno, non positivi): si traggono immediatamente le conclusioni in relazione alla situazione che rende massima la funzione obiettivo;
b) nell’espressione della funzione obiettivo i coefficienti delle variabili non di base non sono tutti negativi o nulli: bisogna effettuare altri tentativi.

L’algoritmo del simplesso è stato introdotto nel 1947 dal matematico statunitense George Bernard Dantzig (1914-2005), considerato anche il padre della programmazione lineare.

Puoi constatare come il metodo del simplesso comporti un procedimento particolarmente lungo e noioso, se si è sfortunati nella scelta delle variabili di base. Ed è tanto più lungo quanto più numerosi sono i coefficienti positivi nella funzione obiettivo che bisogna rendere massima. Questo perché potrebbe capitare di dover fare diversi tentativi nella speranza di giungere prima o poi alla situazione favorevole che nella funzione non ci siano coefficienti positivi fra quelli delle variabili.

Vedremo in seguito come rendere “sistematico” questo procedimento.

(150)

PubblicitàPubblicità