Problema di ottimizzazione
Ciao a tutti,
Volevo condividere con voi un problema pratico che ho riscontrato nella produzione di birra artigianale.
In pratica, per ogni stile di birra (es: pils, IPA, stout etc...) esiste un profilo di acqua idoneo a quel determinato stile di birra. Viene definito come profilo il numero di parti per milione (ppm) dei seguenti ioni disciolti nell'acqua
Ca2+
Mg2+
Na+
Cl-
SO42-
HCO3-
Io sono in possesso di tutti i profili target delle acque ed un database contenente i profili delle acque minerali in commercio in Italia. La mia domanda è questa: esiste un algoritmo che mi permetta di creare un mix con un numero predefinito di acque minerali (es: 2/3/4 tipi di acqua differente) che più si avvicini al profilo target? Tale algoritmo può essere implementato su Excel?
Ho provato a rispolverare gli appunti di ricerca operativa ed AMPL ma con scarsi risultati
Birretta offerta a chi mi darà una mano
Volevo condividere con voi un problema pratico che ho riscontrato nella produzione di birra artigianale.
In pratica, per ogni stile di birra (es: pils, IPA, stout etc...) esiste un profilo di acqua idoneo a quel determinato stile di birra. Viene definito come profilo il numero di parti per milione (ppm) dei seguenti ioni disciolti nell'acqua
Ca2+
Mg2+
Na+
Cl-
SO42-
HCO3-
Io sono in possesso di tutti i profili target delle acque ed un database contenente i profili delle acque minerali in commercio in Italia. La mia domanda è questa: esiste un algoritmo che mi permetta di creare un mix con un numero predefinito di acque minerali (es: 2/3/4 tipi di acqua differente) che più si avvicini al profilo target? Tale algoritmo può essere implementato su Excel?
Ho provato a rispolverare gli appunti di ricerca operativa ed AMPL ma con scarsi risultati
Birretta offerta a chi mi darà una mano
Risposte
Puoi semplificarti di molto la vita producendo solo belgian strong ale, il resto è per le piante 
Scherzi a parte, il problema non è difficile da risolvere: se ciascuna acqua è descritta da quei sei numeri, allora ciascuna acqua è un vettore di \(\mathbb{R}^6\). Ciò che vuoi fare è, scelte 2/3/4 acque, proiettare il profilo che vuoi ottenere sul sottospazio generato da esse: le componenti della proiezione ti danno le frazioni di acqua da mettere nella miscela.
Questo è un problema che si risolve anche a mano, e sicuramente con Octave si fa in poco tempo.
Se prendi sei acque linearmente indipendenti puoi ottenere la miscela esatta.
Scherzi a parte, il problema non è difficile da risolvere: se ciascuna acqua è descritta da quei sei numeri, allora ciascuna acqua è un vettore di \(\mathbb{R}^6\). Ciò che vuoi fare è, scelte 2/3/4 acque, proiettare il profilo che vuoi ottenere sul sottospazio generato da esse: le componenti della proiezione ti danno le frazioni di acqua da mettere nella miscela.
Questo è un problema che si risolve anche a mano, e sicuramente con Octave si fa in poco tempo.
Se prendi sei acque linearmente indipendenti puoi ottenere la miscela esatta.
"Raptorista":
Puoi semplificarti di molto la vita producendo solo belgian strong ale, il resto è per le piante
Scherzi a parte, il problema non è difficile da risolvere: se ciascuna acqua è descritta da quei sei numeri, allora ciascuna acqua è un vettore di \(\mathbb{R}^6\). Ciò che vuoi fare è, scelte 2/3/4 acque, proiettare il profilo che vuoi ottenere sul sottospazio generato da esse: le componenti della proiezione ti danno le frazioni di acqua da mettere nella miscela.
Questo è un problema che si risolve anche a mano, e sicuramente con Octave si fa in poco tempo.
Se prendi sei acque linearmente indipendenti puoi ottenere la miscela esatta.
Grazie mille Raptorista, la strong all'arancia amara è per te
Le acque sono tutte linearmente indipendenti, ma persona l'ignoranza, non so come applicare ciò che tu mi hai suggerito. Sono un po' pratico di AMPL e decisamente più pratico di Excel, ma non so proprio come impostare il sistema di risoluzione
Questo non è un problema di ottimizzazione, quindi AMPL puoi pure metterlo via, anche perché non ho idea di come funzioni [anche se in teoria dovrei]. È un problema di algebra lineare.
Date sei acque \(\textbf{a}_1, \dots, \textbf{a}_6\) e un'acqua bersaglio \(\textbf{b}\), dove ciascuna di queste è un vettore di sei numeri \(\textbf{a}_1 = (a_1^1, a_1^2, \dots, a_1^6)\), \(\textbf{b} = (b^1, b^2, \dots, b^6)\), eccetera, quello che vuoi fare è trovare dei coefficienti \(\textbf{c} = (c^1, c^2, \dots, c^6)\) tali che
\[
c^1\textbf{a}_1 + c^2\textbf{a}_2 + \cdots + c^6\textbf{a}_6 = \textbf{b}
\]
il che è equivalente a risolvere il sistema lineare
\[
\begin{pmatrix}
a_1^1 & a_2^1 & \cdots & a_6^1 \\
a_1^2 & \ddots \\
\vdots & & \ddots\\
a_1^6 & & & a_6^6
\end{pmatrix}
\begin{pmatrix}
c^1 \\
c^2 \\
\vdots \\
c^6
\end{pmatrix}
=
\begin{pmatrix}
b^1 \\
b^2 \\
\vdots \\
b^6
\end{pmatrix}.
\]
Come ti ho detto, con un software come Octave questo si fa in 3 minuti, ci vuole solo il tempo di inserire i numerini.
Date sei acque \(\textbf{a}_1, \dots, \textbf{a}_6\) e un'acqua bersaglio \(\textbf{b}\), dove ciascuna di queste è un vettore di sei numeri \(\textbf{a}_1 = (a_1^1, a_1^2, \dots, a_1^6)\), \(\textbf{b} = (b^1, b^2, \dots, b^6)\), eccetera, quello che vuoi fare è trovare dei coefficienti \(\textbf{c} = (c^1, c^2, \dots, c^6)\) tali che
\[
c^1\textbf{a}_1 + c^2\textbf{a}_2 + \cdots + c^6\textbf{a}_6 = \textbf{b}
\]
il che è equivalente a risolvere il sistema lineare
\[
\begin{pmatrix}
a_1^1 & a_2^1 & \cdots & a_6^1 \\
a_1^2 & \ddots \\
\vdots & & \ddots\\
a_1^6 & & & a_6^6
\end{pmatrix}
\begin{pmatrix}
c^1 \\
c^2 \\
\vdots \\
c^6
\end{pmatrix}
=
\begin{pmatrix}
b^1 \\
b^2 \\
\vdots \\
b^6
\end{pmatrix}.
\]
Come ti ho detto, con un software come Octave questo si fa in 3 minuti, ci vuole solo il tempo di inserire i numerini.
Un piccolo appunto Sergio. Per risolvere un sistema lineare è più opportuno utilizzare il comando "backslash", ossia scrivere "A\b", invece di inv(A)*b. Per problemi piccoli magari non si nota, ma il l'inversione esplicita di matrice è un comando da evitare se possibile
Mica giusto però...aveva aperto il thread qua e adesso vedo che era un duplicato.
https://www.matematicamente.it/forum/vi ... 0&t=205226
C'è solo un fattore che state sottovalutando (e non è da poco), ovvero che "tanto più gli assi/acque sono ortogonali, tanto più la soluzione non risentirà di piccoli errori di approssimazione".
Per chiarirci, una base composta da vettori che a coppie sono posti ad un angolo piccolissimo fra di loro, produrrà soluzioni che se arrotondate anche minimamente condurranno a scostamenti molto grandi dal risultato sperato. Per queesto ho proposto un metodo di selezione da fare "una tantum".
https://www.matematicamente.it/forum/vi ... 0&t=205226
C'è solo un fattore che state sottovalutando (e non è da poco), ovvero che "tanto più gli assi/acque sono ortogonali, tanto più la soluzione non risentirà di piccoli errori di approssimazione".
Per chiarirci, una base composta da vettori che a coppie sono posti ad un angolo piccolissimo fra di loro, produrrà soluzioni che se arrotondate anche minimamente condurranno a scostamenti molto grandi dal risultato sperato. Per queesto ho proposto un metodo di selezione da fare "una tantum".
"Sergio":
Tra l'altro, qui ha detto che le acque sono linearmente indipendenti e quindi con 6 acque non ci sarebbero i problemi di cui tu, giustamente, nell'altro thread ti preoccupavi (inciso: molto carina la tua soluzione).
D'altra parte, qui non ha detto che le acque sono 250, dato che avrebbe impedito di pensare che fossero (come invece qui ha detto) tutte linearmente indipendenti.
Beh dai Sergio, è intuibile che vi siano acque molto simili e acque relativamente diverse.
La cosa importante è non usare due acque del tipo $(1,2,3,4,5,6)$ e $1,2,3,4,5,6.0000001)$
Sono lineamente indipendenti? SI
Sono una scelta subottimale? Assolutamente SI
Il problema che ho posto è stranoto. Mettiamo che alla fine ottenga il vettore $(x_1,x_2,x_3,x_4,x_5,x_6)$
Facendo $100*(x_i)/(sum_0^6 x_i)$ ottiene le percentuali di acqua da impiegare da ogni bottiglia.
Se approssima le percentuali al primo decimale e la scelta delle acque è subottimale, il risultato sarà un'acqua che si discosta assai rispetto a quella voluta. Viceversa il medesimo errore viene mitigato tanto più le acque scelte sono diverse. La scelta delle 6 acque "migliori" è un processo che si fa una volta sola e la soluzione che ho proposto e un modo diretto per determinarle.
E poi se ti basi su ciò che ha scritto l'OP, ricorda che ha anche scritto:
"Pessima_Scelta":
Sarei curioso anche di sapere quale sia il metodo per usare tutto il DB: normalizzare la matrice per farla diventare quadrata?
Fai te
"Bokonon":
aveva aperto il thread qua e adesso vedo che era un duplicato.
https://www.matematicamente.it/forum/vi ... 0&t=205226
[xdom="Raptorista"]@Pessima_Scelta il crossposting è male!! Cartellino giallo
[/xdom]
@Sergio
[ot]
Cosa non si fa per una birra[/ot]
[ot]
"Sergio":
Tutto sommato, avevo pensato a un altro metodo e mi sarebbe piaciuto verificarlo con 250 acque diverse
Cosa non si fa per una birra
[/ot]
"Sergio":
Sei sicuro?
Si, Sergio. E l'errore si amplia all'aumentare del numero di "assi".
Ne parla Strang ma ovviamente ci sono diversi video e lezioni online che trattano l'argomento della scelta delle basi (che ovviamente diventa essenziale quando si trattano matrici immense).
Per il resto, direi che fare 4 operazioni (roba da 3 minuti scarsi) con excel per selezionare un campione di acque, non merita approfondimenti particolari.
"Sergio":
Il problema mi pare piuttosto un altro: non basta trovare una combinazione lineare di 6 acque, se ne deve trovare una combinazione con coefficienti non negativi. E non è scontato...
Vero, meglio avere una ventina di acque diverse e sperare per il meglio.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo