86 Capitolo 5 I problemi di ottimizzazione
5.1 I modelli di ottimizzazione
Appare doveroso iniziare la trattazione sui problemi di ottimizzazione introducendo le definizioni basilari che rendono comprensibile il lavoro svolto in questa Tesi, incentrato per l'appunto sull’applicazione di processi matematici ad un caso concreto. Ci muoviamo nel campo della Ricerca Operativa, branca della matematica applicata in cui problemi decisionali complessi vengono analizzati e risolti mediante modelli matematici e metodi quantitativi avanzati.
La Ricerca Operativa si occupa di formalizzare un problema in un modello matematico e calcolare una soluzione ottima o approssimata per esso.
Per modello si intende una struttura logico-matematica messa a punto per rappresentare le caratteristiche peculiari di un sistema fisico reale. Il ricorso a tale struttura è necessario per rendere accessibili problematiche, anche molto complesse, che caratterizzano i sistemi reali. Attraverso il processo di modellazione e l’uso dei moderni calcolatori si possono affrontare aspetti difficili, se non impossibili, da trattare in maniera tradizionale.
L’approccio modellistico per risolvere un problema di decisione o, più in generale, l’impiego di metodi matematici per la soluzione di problemi applicativi, viene di solito realizzato attraverso diverse fasi, che possono essere schematizzate nel seguente modo:
- Analisi del problema - Costruzione del modello - Analisi del modello - Risoluzione numerica - Validazione del modello
La prima fase consiste nell’analisi della struttura del problema per individuare i legami logico-funzionali e gli obiettivi. Nella fase seguente di costruzione del modello si descrivono in termini matematici le caratteristiche principali del problema. Nell’analisi del modello si effettua la
87 deduzione per via analitica di particolari proprietà del modello di ottimizzazione. Le principali sono:
- Esistenza della soluzione ottima - Condizioni della soluzione ottima
- Stabilità delle soluzioni trovate al variare dei dati di ingresso
La successiva fase di risoluzione avviene mediante opportuni algoritmi di calcolo. La soluzione numerica ottenuta deve poi essere interpretata dal punto di vista applicativo, per evitare che abbia scarso rilievo pratico. Tale fase viene appunto definita come validazione del modello e può avvenire attraverso una verifica sperimentale oppure con una simulazione al calcolatore. La definizione di un modello si configura quindi come un processo di raffinamento iterativo del modello stesso.
88 Esistono diverse ragioni per adottare l’approccio modellistico al fine di trovare soluzione alle diverse tipologie di problemi; i principali vantaggi introdotti sono:
- Possibilità di risolvere matematicamente il problema, superando le complessità del sistema reale mediante ipotesi semplificative.
- Ottenere una maggiore comprensione del problema. - Possibilità di effettuare simulazioni al calcolatore.
I principali svantaggi possono essere sintetizzati come segue:
- Utilizzare un modello significa semplificare un problema complesso e quindi introdurre un grado di incertezza, più o meno grande, nelle relative soluzioni numeriche.
- La qualità della soluzione viene a dipendere non solo dall’accuratezza del modello ma anche da quella dei dati di input che vengono inseriti.
Nella classe dei problemi decisionali rientrano i cosiddetti problemi di ottimizzazione, il cui obiettivo è quello di massimizzare o minimizzare qualcosa. Esempi di possibili obiettivi sono: minimizzare i costi, massimizzare il profitto, massimizzare il ricavo, minimizzare i tempi, ecc. Esempi classici di problemi di ottimizzazione sono:
- problemi di pianificazione della produzione; - problemi di trasporto;
- problemi di gestione del portafoglio aziendale; - problemi di percorso ottimo;
- Ecc..
Da un punto di vista pratico, data una funzione ( ) con ∈ , un problema di ottimizzazione viene così formulato:
min ( ) ∈
Il problema consiste nel determinare, se esiste, un punto di minimo della funzione tra i punti dell’insieme . I problemi di ottimizzazione sono spesso denominati, con terminologia equivalente, problemi di Programmazione Matematica. La funzione viene chiamata “funzione
89 obiettivo”, l’insieme S “insieme delle soluzioni ammissibili”, ed il punto “soluzione del problema”.
All’interno dei problemi di ottimizzazione vengono definite tre classi di problemi:
- Problemi di ottimizzazione continua - Problemi di ottimizzazione discreta - Problemi di ottimizzazione mista
Nei problemi della prima classe, le variabili x possono assumere tutti i valori reali. In quelli di seconda classe invece esse sono vincolate ad assumere valori che posso essere interi e/o binari. Nei problemi di terza classe, i più diffusi, solo alcune variabili sono vincolate ad essere intere e/o binarie. L’ insieme S delle soluzioni ammissibili viene descritto dalle disuguaglianze
( ) ≤ oppure ( ) ≥
che limitano il paniere delle variabili x tra cui verificare la presenza della soluzione ottima. Ogni disuguaglianza prende il nome di vincolo e l’insieme S è di conseguenza formato dall’intersezione di tutti i vincoli.
⎩ ⎪ ⎨ ⎪ ⎧ ( ) ≥( ) ≥ ( ) ≥ ⋮ ⋮ ( ) ≥
Notare che è possibile introdurre, oltre le condizioni di disuguaglianza, anche quelle di uguaglianza agendo in maniera opportuna sulla definizione delle disequazioni.
Detto ciò, un problema di ottimizzazione generico può essere descritto nella seguente forma:
min ( ) ∈
90 I punti dell’insieme ammissibile sono quelli per i quali tutti i vincoli sono soddisfatti, cioè tutti quei punti x tali per cui tutte le disuguaglianze sono verificate.
I problemi di Programmazione Matematica si possono poi classificare in base alla struttura delle funzioni che li definiscono: si parla di problema di Programmazione Lineare (PL) se la funzione obiettivo f(x) e tutte le funzioni che definisco i vincoli sono lineari, ovvero posso essere espresse nella forma:
min ( ) = ∙ + ∙ + ⋯ + ∙
∙ + ⋯ + ∙ ≤
con coefficienti costanti.
Si parla invece di problema di Programmazione Non Lineare quando almeno una delle funzioni del problema è non lineare.
5.1.1 La programmazione lineare
Fra i problemi di ottimizzazione hanno assunto particolare importanza quelli di Programmazione Lineare. Come accennato al paragrafo precedente, si parla di Programmazione Lineare quando il problema si traduce in un modello matematico costituito da:
- una funzione obiettivo lineare di n variabili, che normalmente esprime una quantità da massimizzare o minimizzare (ad esempio un costo)
- un sistema di vincoli espressi da equazioni e/o disequazioni lineari nelle n variabili (detti anche vincoli tecnologici)
- un sistema di vincoli di segno, che esprimono la non-negatività delle variabili
Nel caso in cui le variabili di decisione siano due, si può risolvere un problema di questo tipo con il metodo grafico, i cui aspetti fondamentali sono descritti qui di seguito.
I vincoli di segno limitano la ricerca delle soluzioni al primo quadrante del corrispondente piano cartesiano. Dopo aver tracciato tutte le rette associate alle disequazioni ed equazioni del sistema dei vincoli, se l’intersezione derivante non è un insieme vuoto, si otterrà una regione illimitata detta regione ammissibile, poiché contiene le coppie di variabili che soddisfano tutti i vincoli. Ciascuna di queste coppie è detta soluzione ammissibile, mentre le coppie di valori che
91 corrispondono ai vertici della regione (detta anche poligono) sono definite soluzioni ammissibili di base e fra esse va cercata, se esiste, la soluzione ottima del problema.
Il teorema su cui si basa il processo di ottimizzazione è il Teorema Fondamentale della Programmazione Lineare di seguito enunciato: “Il massimo ed il minimo di una funzione lineare
di un numero qualsiasi di variabili soggetta a vincoli espressi da equazioni e/o da disequazioni lineari, se esistono, si trovano sui vertici della regione ammissibile, e non al suo interno.”.
Dall’applicazione del teorema segue che, in corrispondenza di ogni vertice del poligono si calcola il valore della funzione obiettivo, e si sceglie la coppia che rende minima o massima la funzione stessa, in base all’obiettivo del processo. Nel caso particolare in cui, in corrispondenza di due vertici consecutivi si ottiene lo stesso valore della funzione obiettivo, la Teoria della Programmazione Lineare dimostra che lo stesso valore si ottiene in corrispondenza di un qualsiasi punto compreso tra i due vertici suddetti.
Nel caso in cui le variabili siano più di due, il metodo grafico risulta di scarsa applicazione pratica.
È stato dunque ideato un procedimento di risoluzione chiamato “Metodo del Simplesso”. L’algoritmo del simplesso risolve problemi di Programmazione Lineare in forma standard, ricercando, quando esiste, una soluzione ottima tra quelle ammissibili di base. I problemi risolvibili dall’algoritmo sono di questo tipo:
min = ∙
= ≥ 0
Con ∈ .
La funzione z è la funzione obiettivo, c è il vettore dei coefficienti costanti delle variabili, x sono le variabili incognite, A è la matrice dei coefficienti dei vincoli e b sono i termini noti degli stessi. L’algoritmo, quindi, risolvendo il sistema di disequazioni, calcola quale sia la soluzione, o l’insieme di soluzioni, ammissibili che rendono minima (o massima) la funzione obiettivo.
Se i valori delle variabili da calcolare devono essere numeri interi si considerano nella regione ammissibile solo i punti aventi per coordinate numeri interi.
92 5.1.2 La programmazione lineare mista e intera
Un problema di Programmazione Lineare Mista Intera (MILP) è un problema di ottimizzazione vincolata in cui sia la funzione obiettivo che la regione ammissibile del problema sono costituiti da variabili che possono essere vincolate ad assumere valori interi e/o binari.
Se scriviamo un sistema di equazioni e/o disequazioni lineari nella forma compatta ≤ (o analogamente ≥ ), un problema di programmazione lineare intera è un problema del tipo:
min = ∙
~ ∈
Un problema di programmazione lineare intera mista è la variante in cui la condizione di interezza è richiesta solo per un certo sottoinsieme delle variabili:
min = ∙
~
∈ ∈
Le variabili xi con i ∈ I sono dette variabili intere, mentre le altre sono continue.
Di fondamentale importanza in Programmazione Lineare Mista Intera sono le variabili binarie, cioè quelle che possono assumere solo valore 0 o 1: tali variabili vengono spesso usate per descrivere decisioni del tipo sı/no. Si noti che un problema di questo tipo permette sempre di imporre la condizione che una certa variabile xi sia binaria scrivendo i vincoli 0 ≤ xi ≤ 1, xi ∈ Z.
5.1.2.1 Metodi risolutivi per sistemi MILP
Una volta definita la struttura del sistema da risolvere e costruito il modello di ottimizzazione, il problema deve essere risolto con un algoritmo adatto. La complessità dei sistemi trattati unita alla presenza di variabili discrete rende difficile trovare un algoritmo che risolva in modo efficiente tutti i tipi di problemi. Sono stati quindi sviluppati numerosi algoritmi diversi ognuno dei quali è ottimizzato per una certa tipologia di problemi. In questo paragrafo non si ha la pretesa di illustrare tutti i possibili metodi di risoluzione, ma si ha la volontà di accennare quelli
93 utilizzati in questa Tesi. Gli algoritmi risolutivi per i problemi MILP che si vogliono menzionare sono:
- Metodo Branch and Bound (1960) - Metodo Branch and Cut
Tutti questi metodi si basano sulla stessa idea di partenza, ovvero quella di trasformare il problema MILP in tanti sottoproblemi LP a cui applicare il Metodo del Simplesso.
Uno degli algoritmi più utilizzati è l’algoritmo Branch and Bound. L’idea di base è quella di generare delle soluzioni parziali al problema, eliminando le regioni dello spazio delle soluzioni che l’algoritmo riesce a scartare a priori. In questo modo si riesce a partizionare il problema in un numero di sotto problemi LP limitato, ma sufficiente a trovare la soluzione ottima.
5.1.2.2 Analisi degli algoritmi “Branch and Bound” e “Branch and Cut”
Come accennato al paragrafo precedente, per risolvere un problema di ottimizzazione MILP è necessario scomporre il sistema complesso in sottosistemi facilmente analizzabili, ampliando temporaneamente le possibili soluzioni all’insieme dei numeri reali. Questo tipo di trasformazione viene definita “Rilassamento del problema”.
Per ottenere il rilassamento del problema le m variabili binarie vengono convertite in variabili discrete vincolate tra i valori 0 e 1.
min ( , ) ℎ( , ) = 0 ( , ) ≤ 0 ≤ 0, 0 ≤ ≤ 1
Si considerino ora due problemi rilassati, R1 e R2, nei quali un numero h e h’ di variabili binarie g e g' vengono fissate prima di rilassare il problema. I due problemi possono essere espressi come: R1: min ( , ) e R1: min ( , ) ℎ( , ) = 0 ℎ( , ) = 0 ( , ) ≤ 0 ( , ) ≤ 0 ≤ 0, 0 ≤ ≤ 1 ≤ 0, 0 ≤ ≤ 1 ∈ , ∈ ,
94
Dove ⊂ { } ≤ .
Sia f* la soluzione del problema originario e siano f1* e f2* rispettivamente le soluzioni dei problemi R1 e R2. Maggiore è il numero di variabili fissate a priori, più grande è il valore ottimale della funzione obiettivo da minimizzare; di conseguenza si verifica che:
- Se R1 non è ammissibile, allora R2 non è ammissibile - Se R2 è ammissibile, allora anche R1 è ammissibile - Se R2 è ammissibile, allora f2*≥ f1*
- Se qualche g tra le soluzioni di R2 è intera, allora f2*≥ f*
L’algoritmo Branch and Bound sfrutta queste proprietà per ridurre lo spazio delle soluzioni entro cui cercare la soluzione ottimale. Il processo iterativo viene descritto in seguito con riferimento alla figura successiva.
Figura 5.2 – Rappresentazione del processo di esplorazione dell’albero delle soluzioni
L’inizializzazione viene fatta risolvendo il problema completamente rilassato, R0. Senza fissare nessuna delle variabili discrete, la soluzione del problema può dare luogo a due situazioni:
95 - f0* è la soluzione del problema se tutte le variabili binarie risultano intere
- f0* rappresenta il minimo limite inferiore dello spazio delle soluzioni
Il passo successivo è quello di creare due sottoproblemi e assegnare ad una delle variabili binarie, y1, un valore intero. Le soluzioni dei due forniscono nuovi limiti inferiori per f*; il più piccolo dei due costituisce il nuovo lower bound del problema. Se una delle y che non sono state fissate è intera, allora il valore della funzione obiettivo rappresenta un limite superiore per lo spazio delle soluzioni. Se la differenza tra il valore minimo e il valore massimo è inferiore ad una certa tolleranza, allora si considera trovata la soluzione. Se invece la convergenza non è stata raggiunta:
- se una delle f1*(y1) e più grande di fmax, tutto il ramo che deriva da quel nodo può essere tagliato in quanto non condurrà alla soluzione ottimale;
- se il valore della funzione obiettivo è compreso tra fmin e fmax, il nodo viene assunto come potenziale ramo appartenente a quello della soluzione ottima.
Da ogni nodo rimasto si creano altri due sottoproblemi caratterizzati da diversi valori di altre variabili binarie. Il procedimento viene iterato finché non viene raggiunta la convergenza e trovato il valore della soluzione ottima.
Negli anni Novanta, dall’unione delle tecniche Branch and Bound e Cutting Planes nasce l’algoritmo “Branch and Cut”. Il metodo “Cutting Planes”, detto anche “Tagli di Gomory”, consiste nel risolvere il problema rilassato trascurando il vincolo di interezza delle variabili, comportandosi quindi come se si trattasse di un normale problema di Programmazione Lineare; una volta trovata la soluzione ottima lineare, si introducono in modo appropriato dei nuovi vincoli, tali da eliminare alcune parti dell'area ammissibile e far coincidere la soluzione ottima con un vertice intero.
Il Branch and Cut elimina i principali inconvenienti dei due metodi da cui deriva ed in particolare garantisce un rafforzamento dinamico del problema rispetto al Branch and Bound e l’eliminazione del tailing off (lunga serie di iterazioni senza sostanziale miglioramento della formulazione), tipico del Cutting Planes, grazie alla possibilità di eseguire il branching (ramificazione dell’albero decisionale). L’idea che sta alla base dell’algoritmo Branch and Cut è
96 quella di generare dei “tagli” a ogni nodo dell’albero decisionale in modo da ottenere una soluzione intera, un lower bound maggiore o un ulteriore branching così da raggiungere la soluzione del problema in maniera più accurata e veloce. La realizzazione pratica di questa idea non è immediata. Applicando i tagli di Gomory al metodo Branch and Bound ed ipotizzando che essi siano validi globalmente, ovvero lungo tutto l’albero decisionale, è possibile memorizzare i tagli ottenuti in una struttura di dati chiamata pool di vincoli. Ad ogni elaborazione di un nodo decisionale, con formulazione iniziale Ax=b, x>0, si aggiungono progressivamente i vincoli di branching e si risolve il rilassato continuo corrispondente, ottenendo la soluzione x*. Se questa è frazionaria, si scandisce il pool alla ricerca dei vincoli violati da x* per aggiungerli alla formulazione corrente. Si risolve poi il nuovo problema e si procede così finché x* non soddisfa tutti i vincoli del pool.
5.1.3 La programmazione multi-obiettivo
Appare evidente che la soluzione ottima di un problema MILP è sempre unica e coincide con la configurazione che minimizza la funzione obiettivo, la quale rappresenta un singolo criterio di ottimizzazione. Se però si desidera minimizzare o massimizzare due o più funzioni obiettivo, il problema diventa un problema di ottimizzazione Multi-Obiettivo (Multiobjective MILP, MoMILP). Questa nuova caratteristica può essere espressa attraverso la cosiddetta formulazione MoMP (Multi-objective Mathematical Programming), secondo la quale vengono considerate k funzioni obiettivo simultaneamente:
( , ), ∀j ∈ {1,2, … , k} ℎ( , ) = 0
( , ) ≤ 0 ∈ , ∈ {0,1}
A differenza dei modelli MILP, nei quali la soluzione, se esiste, è unica, i modelli MoMILP producono una matrice di soluzioni che sono tutte, sostanzialmente, delle soluzioni ottimali. Solo in casi molto rari, infatti, tutte le funzioni obiettivo realizzano il loro minimo per la stessa configurazione della filiera. È necessario dare dunque una nuova definizione di soluzione ottimale. Tale definizione coincide con quella di “Pareto efficienza”. Un vettore decisionale (x,
97 y)* è Pareto ottimale (o Pareto efficiente) se non esiste un altro vettore (x, y) tale che fi(x,y)<=fi(x,y)* per ogni i =1, .., k e fj(x,y)<=hj(x,y)* per almeno una funzione obiettivo generica
j. In altre parole una soluzione è Pareto ottimale se non è possibile trovarne un’altra che riesca
a migliorare una funzione obiettivo senza peggiorarne almeno una delle altre.
In generale un problema ammette molte soluzioni Pareto ottimali, e il loro insieme è detto curva di Pareto o superficie di Pareto. Tutti i punti appartenenti alla superficie di Pareto sono matematicamente equivalenti. La scelta “giusta” dipenderà dagli aspetti che interessa valorizzare maggiormente. A seconda del momento in cui si decide quali sono questi aspetti si possono distinguere tre di metodi di risoluzione:
- Metodi a priori - Metodi interattivi - Metodi a posteriori
I metodi a priori sono accumunati dal fatto di attribuire un peso a ciascuna funzione obiettivo, andando cosi a definirne una unica, prima di eseguire il modello di ottimizzazione. Il problema di questi metodi è che spesso è difficile decidere quali siano gli aspetti più importanti nella progettazione della filiera. I metodi interattivi presentano fasi alternate di dialogo con i decision makers e di calcolo in modo da individuare in poche iterazioni la soluzione migliore. Gli svantaggi maggiori di questi metodi sono due: prima di tutto richiedono un continuo scambio di informazioni con i decision makers; in secondo luogo i decision makers non hanno mai la visione dell’intero range di alternative possibili ma solo gli effetti delle loro preferenze in una certa fase del processo di ottimizzazione. I metodi a posteriori, infine, consentono di individuare l’intero set (o un numero rappresentativo) di soluzioni ottimali tra cui i decision makers potranno scegliere quella che ritengono migliore.
Lo svantaggio di questi metodi è che per sistemi molto complessi il costo computazionale per generare l’intero set di soluzioni ottimali potrebbe essere troppo elevato. Tuttavia, data la velocità attuale dei calcolatori i metodi a posteriori sono i più utilizzati.
98 5.2 Metodi usati nella presente trattazione
Per risolvere le problematiche affrontate in questa Tesi, si è scelto di formulare un problema di Programmazione Lineare Mista Intera. Questa scelta è dovuta al fatto che aspetti complessi, come la pianificazione della produzione di energia elettrica da generatori Diesel e la gestione della carica di una batteria comportano l’utilizzo di variabili che possono essere intere e in particolare binarie. La necessità di queste tipologie di variabili è dovuta al fatto che si rende indispensabile una formulazione del problema che permetta di individuare delle logiche decisionali in grado di muoversi tra due alternative; ad esempio, le variabili binarie servono per esplicitare gli stati on/off dei generatori, lo stato di carica o scarica della batteria, ecc..
La funzione obiettivo che viene considerata è unica e rappresenta il costo di esercizio dei generatori Diesel. Un problema di Programmazione Multi-obiettivo, di conseguenza, risulta essere inadeguato a rispondere ai problemi da affrontare. Pertanto, anche questo metodo è stato escluso. La maggior difficoltà nell’affrontare il problema di ottimizzazione dei profili di potenza dei generatori e del livello di carica della batteria, risiede nella modellazione dei componenti in gioco nella rete elettrica dell’isola.
Questi sono:
- Il carico
- I quattro generatori Diesel - La batteria
- L’ insieme degli impianti fotovoltaici
La modellazione è la prima fase che è stata affrontata.
Il carico viene gestito come un vettore di dati, e quindi come un input del problema.
I quattro generatori, o meglio i valori di potenza erogata in ogni segmento di tempo considerato, vengono trattati e modellati così da descrivere in maniera più accurata possibile il comportamento reale dei sistemi. La grande difficoltà di questo processo di modellazione sta nel fatto che per utilizzare queste tecniche di ottimizzazione si devono avere delle relazioni lineari tra le variabili di interesse. I generatori Diesel sono caratterizzati da molte relazioni non lineari, come ad esempio le curve dei rendimenti e quindi quelle di costo. Si è dovuto ricorrere a logiche che vanno a linearizzare a tratti queste caratteristiche, così da poter esprimere in maniera idonea tali relazioni e far assumere senso pratico ai risultati ottenuti.
99 Lo stesso discorso vale per le caratteristiche della batteria. L’insieme degli impianti fotovoltaici viene trattato come un carico negativo, rispettando la condizione di non diretta controllabilità dei loro profili di generazione. Di conseguenza, l’effetto che questo ha sul problema è valutato come semplice abbassamento di richiesta del carico della rete. Nella fase di redazione del problema di ottimizzazione, il carico e il profilo di potenza dell’insieme dei generatori fotovoltaici vengono gestiti nella stessa maniera, cioè come vettori di dati. Al vettore del carico viene sottratto quello del fotovoltaico, ottenendo il profilo effettivo di carico che deve essere soddisfatto dall’insieme generatori Diesel-batteria. Nel capitolo successivo tutti questi aspetti verranno analizzati attentamente, descrivendo sia il processo di modellazione dei componenti che quello di redazione dell’intero problema di ottimizzazione.
5.2.1 Il linguaggio di programmazione e il GLPK
La risoluzione di un problema di ottimizzazione MILP viene effettuata mediante calcolatore. Esistono numerosi software ideati per questo scopo. A titolo puramente informativo se ne riportano i più diffusi:
- CPLEX - GAMS - Gurobi - AMPL
Questi software, poiché presentano particolari interfacce grafiche e linguaggi di configurazione ad alto livello, facilitano l’utente nella redazione e modellazione di un generico problema di ottimizzazione. Il loro utilizzo è però limitato dalla necessità di una licenza per poter ottenere le soluzioni cercate. Per questo motivo in rete sono andati diffondendosi software a licenza gratuita che, seppur con molte limitazioni, rendono accessibile la piattaforma di calcolo. I più famosi tra questi software sono:
- OpenOpt - GLPK
100 Nella scelta dell’applicativo da utilizzare per studiare il caso di Ventotene, ha pesato notevolmente il grado di libertà raggiungibile in fase di modellazione e programmazione. Nella prima fase ci si accorge che, per descrivere in maniera corretta le dinamiche dei componenti del sistema, le variabili richieste sono numerose. Questo si traduce nella necessità di utilizzare un software che sia in grado di gestire bene queste variabili e di fornire un risultato attendibile. I software freeware non consentono di ottenere modelli complessi con numerose tipologie di variabili, ma solo la risoluzione di problemi semplici e con un numero limitato di vincoli. Di conseguenza si è deciso di realizzare da zero un software che rispondesse a tutte le esigenze del problema di modellazione mantenendo un alto livello di libertà nella definizione ed implementazione dei vincoli.
Il linguaggio di programmazione scelto per la realizzazione del software è stato il “linguaggio C”. La scelta del “C” è dovuta al fatto che è uno dei linguaggi di programmazione basilari e quindi facilmente esportabile. Tra i software freeware citati c’è il GLPK, acronimo di GNU Linear Programming Kit, che oltre al risolutore stand alone fornisce il toolkit per la programmazione su “C” di software che siano in grado di risolvere problemi di ottimizzazione.
Figura 5.3 – Logo della libreria e della piattaforma utilizzate
Il pacchetto GLPK è composto da una libreria software scritta in ANSI C che consente di risolvere problemi di Programmazione Lineare e Programmazione Lineare Mista Intera anche di grandi dimensioni. Per ulteriori informazioni si veda l’Appendice.
La piattaforma scelta per la realizzazione del software ed il suo debug è stata “Microsoft Visual Studio”, utilizzata mediante licenza per studenti fornita dalla Facoltà di Ingegneria di Pisa.
