Introduzione
Non tutti lo sanno, ma con i fogli di calcolo elettronico è possibile risolvere problemi di ottimizzazione. Come Excel e Open Office, anche Google Spreadsheets fornisce gli strumenti necessari per scrivere e risolvere semplici problemi di ottimizzazione, utili per:
- insegnare l’ottimizzazione
- realizzare semplici prototipi e dimostrativi
- risolvere problemi pratici
Per capirne il funzionamento, ho provato a scrivere un semplice problema di ottimizzazione e a risolverlo in Google Spreadsheets.
Descrizione del problema
Come problema d’esempio, prendiamo in considerazione la schedulazione delle attività di lavorazione di un’azienda manifatturiera di abbigliamento.
Il processo produttivo è organizzato per soddisfare degli ordini, che vengono realizzati in un laboratorio composto da postazioni di lavoro. L’uso del laboratorio è suddiviso in turni, dove lavoratori specializzati si alternano nelle postazioni di lavoro.
Un ordine è caratterizzato da:
- CDC — Numero di capi da consegnare
- ST — Turno di consegna
- CPT — Numero di capi che è possibile realizzare in un turno
Le postazioni del laboratorio non sono sempre tutte disponibili. Per ogni turno è noto quante di queste sono disponibili (Max postazioni).
Tutte le informazioni fin qui viste (CDC, ST, CPT e Max postazioni) rappresentano i dati di input del nostro problema.
Con il modello di ottimizzazione che vogliamo realizzare e risolvere, si vuole assegnare un ordine ad uno o più turni, in modo tale da completare tutti gli ordini nel tempo assegnato.
Il foglio di calcolo
Vediamo ora come questo problema è stato implementato in un foglio di calcolo di Google Spreadsheets. Per semplicità ho considerato un’istanza ridotta:
- gli ordini sono 5
- i turni sono 10
- le postazioni non superano le 3 unità
Ho condiviso il foglio di calcolo che sto per descrivere al link seguente. Qui riporterò delle immagini a supporto della descrizione.
Scheduling
warehouse Lavorazione ammisibile CDC,ST,CPT,O,CRS 10,10,2,o1,1,0,1,1,1,1,0,0,0,0,2,0,2,2,2…docs.google.com
warehouse Lavorazione ammisibile CDC,ST,CPT,O,CRS 10,10,2,o1,1,0,1,1,1,1,0,0,0,0,2,0,2,2,2…docs.google.com
Gli ordini
Nelle celle A3:C7 si trovano i parametri che descrivono i 5 ordini. L’interpretazione di questa sezione è molto semplice. Ad esempio la riga 6 dice che l’ordine 4 prevede la consegna di 16 capi per la fine del turno 10; in ogni turno si possono produrre al più 4 capi.
I turni
Nelle celle E9:N10 si trovano i parametri che descrivono i 10 turni. Anche qui, l’interpretazione è molto semplice. La colonna K dive che il turno 7 prevede al massimo 3 postazioni occupabili (K10). Il valore in K9 è un output, ma ci arriviamo tra un po’.
Le assegnazioni ordine-turno
Per rappresentare le associazioni tra un ordine ed un turno vengono usate le variabili binarie — 1 o 0 — nella sezione E3:N7. Ad esempio, l’uno in G5 indica che l’ordine o3 viene lavorato anche nel turno s3; viceversa, lo zero in G4 indica che l’ordine o2 non viene lavorato nel turno s3.
Tutte le variabili della sezione E3:N7 diventeranno le variabili binarie oggetto di ottimizzazione. Le celle E9:N9 sommano, colonna per colonna, le variabili binarie di assegnamento, ed entreranno in azione come vincoli.
Capi realizzati
Nella sezione P3:Y7 si calcolano quanti capi per ordine si realizzano in ogni turno. La colonna Z somma il totale di capi realizzati per ordine su tutti i turni dal s1 al s10. La cella AA3 somma tutti gli ordini.
La colonna Z entrerà in azione come vincoli e la cella AA3 nella funzione obiettivo.
Il risolutore
Per poter utilizzare un risolutore in Google Spreadsheet è necessario installare l’apposito componente aggiuntivo; nello specifico OpenSolver.
Aprendo la barra laterale di OpenSolver, è possibile programmare il risolutore. Vediamo nei dettagli cosa è stato inserito.
Funzione obiettivo
La funzione obiettivo indica il valore che il risolutore deve minimizzare o massimizzare agendo sulle variabili del problema. In questo caso, vogliamo minimizzare il numero totale di capi prodotti, che è come dire che cerchiamo di realizzare tutti i capi, nel tempo richiesto, senza farne troppi più del necessario.
Le variabili
Per trovare il miglior valore della funzione obiettivo, il nostro solver può solo modificare il valore delle celle identificate come variabili.
In questo caso specifico, le variabili sono rappresentate dalle variabili binarie di assegnamento. Attenzione però che fino ad ora non abbiamo ancora specificato le le variabili di assegnamento sono binarie. Per ora possiamo solo assumere che siano non negative.
I vincoli
Ecco i 3 vincoli specificati al solver:
- Le variabili E3:N7 sono binarie, ovvero le celle in questione possono valere 0 oppure 1;
- I capi prodotti Z3:Z7 devo essere in numero maggiore o uguale a capi richiesti dagli ordini;
- Le postazioni occupate E9:N9 siano in numero minore o uguale alle postazioni disponibili E10:N10.
Risoluzione del modello
L’ultima sezione del modello specifica il tipo di risolutore da utilizzare. In questo caso, essendo il problema espresso solo con vincoli lineare (ad eccezione delle variabili binarie) è stato specificato il Google Linear Solver.
Siccome il flag Show progress while solving è attivo, premendo il bottone Solve Model si vedono le variabili come cambiano durante il processo di ottimizzazione.
Conclusioni
A questo punto, con un minimo di conoscenze sull’uso della programmazione lineare per modellare problemi di ottimizzazione, abbiamo a disposizione un modo semplice ed efficace per scrivere un ottimizzatore matematico.
Condividi la tua esperienza scrivendo un commento a questo post.
Commenti