Problema di ottimizzazione

Messaggioda Pessima_Scelta » 14/01/2020, 10:35

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 :D
Pessima_Scelta
Starting Member
Starting Member
 
Messaggio: 2 di 10
Iscritto il: 10/01/2020, 10:34

Re: Problema di ottimizzazione

Messaggioda Raptorista » 14/01/2020, 16:26

Puoi semplificarti di molto la vita producendo solo belgian strong ale, il resto è per le piante :-D

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.
Un matematico ha scritto:... come mia nonna che vuole da anni il sistema per vincere al lotto e crede che io, in quanto matematico, sia fallito perché non glielo trovo


Immagine
Avatar utente
Raptorista
Moderatore
Moderatore
 
Messaggio: 5378 di 9616
Iscritto il: 28/09/2008, 19:58

Re: Problema di ottimizzazione

Messaggioda Pessima_Scelta » 15/01/2020, 11:56

Raptorista ha scritto:Puoi semplificarti di molto la vita producendo solo belgian strong ale, il resto è per le piante :-D

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 :D

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
Pessima_Scelta
Starting Member
Starting Member
 
Messaggio: 3 di 10
Iscritto il: 10/01/2020, 10:34

Re: Problema di ottimizzazione

Messaggioda Raptorista » 15/01/2020, 18:04

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.
Un matematico ha scritto:... come mia nonna che vuole da anni il sistema per vincere al lotto e crede che io, in quanto matematico, sia fallito perché non glielo trovo


Immagine
Avatar utente
Raptorista
Moderatore
Moderatore
 
Messaggio: 5379 di 9616
Iscritto il: 28/09/2008, 19:58

Re: Problema di ottimizzazione

Messaggioda feddy » 15/01/2020, 20:46

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
Avatar utente
feddy
Moderatore
Moderatore
 
Messaggio: 2635 di 5934
Iscritto il: 26/06/2016, 00:25
Località: SISSA

Re: Problema di ottimizzazione

Messaggioda Bokonon » 23/01/2020, 11:46

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".
Avatar utente
Bokonon
Cannot live without
Cannot live without
 
Messaggio: 1976 di 5942
Iscritto il: 25/05/2018, 20:22

Re: Problema di ottimizzazione

Messaggioda Bokonon » 23/01/2020, 16:49

Sergio ha scritto: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 ha scritto:Sarei curioso anche di sapere quale sia il metodo per usare tutto il DB: normalizzare la matrice per farla diventare quadrata?

Fai te :D
Avatar utente
Bokonon
Cannot live without
Cannot live without
 
Messaggio: 1977 di 5942
Iscritto il: 25/05/2018, 20:22

Re: Problema di ottimizzazione

Messaggioda Raptorista » 23/01/2020, 17:01

Bokonon ha scritto:aveva aperto il thread qua e adesso vedo che era un duplicato.
https://www.matematicamente.it/forum/vi ... 0&t=205226

Moderatore: Raptorista

@Pessima_Scelta il crossposting è male!! Cartellino giallo :evil:
Un matematico ha scritto:... come mia nonna che vuole da anni il sistema per vincere al lotto e crede che io, in quanto matematico, sia fallito perché non glielo trovo


Immagine
Avatar utente
Raptorista
Moderatore
Moderatore
 
Messaggio: 5383 di 9616
Iscritto il: 28/09/2008, 19:58

Re: Problema di ottimizzazione

Messaggioda axpgn » 23/01/2020, 20:08

@Sergio
Testo nascosto, perché contrassegnato dall'autore come fuori tema. Fai click in quest'area per vederlo.
Sergio ha scritto:Tutto sommato, avevo pensato a un altro metodo e mi sarebbe piaciuto verificarlo con 250 acque diverse :D

Cosa non si fa per una birra :-D
axpgn
Cannot live without
Cannot live without
 
Messaggio: 14804 di 40641
Iscritto il: 20/11/2013, 22:03

Re: Problema di ottimizzazione

Messaggioda Bokonon » 23/01/2020, 22:45

Sergio ha scritto: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 ha scritto: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.
Avatar utente
Bokonon
Cannot live without
Cannot live without
 
Messaggio: 1979 di 5942
Iscritto il: 25/05/2018, 20:22


Torna a Analisi Numerica e Ricerca Operativa

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite