Programmazione lineare : confronto tra metodi esistenti ed un metodo innovativo

The Linear Programming (LP) is a class of constrained optimization problems in which both the objective function and the constraints which the problem is subject to are linear with respect to the variables. LP and the first problems related to it date back to 1945, when the Nobel George Stigler formulates "the diet problem", or the formulation of a menu to meet a dozen or nutritional requirements at minimum expense. In 1947, Dantzig formalized the concept of LP as it is now understood and also created the resolution method known as “simplex method”. This method is the only one existing until Karmakar, in 1984, proposes a new resolution method, the so-called Interior Point method, in order to overcome some problems that limited the possible applications of the simplex method. This method, in fact, was created with the intent to provide a resolution algorithm that ensures a maximum number of iterations which is of polynomial order with respect to the number of variables. In 2011 Professor Buzzi-Ferraris formulated and proposed the Attic method. The aim of this new method is to provide a tool that can make the most of the mathematical advances made over the last thirty years in the field of programming languages (it is used, in fact, the object-oriented programming typical of the C + + language) and the factorization of matrices so that this method is easier to use and, usually, more powerful. The peculiar mathematical features and the first tests and comparisons made in this thesis led to assume that, once properly developed the algorithm, through the Attic method will be possible to have a powerful and effective tool for solving in a faster way LP and MILP (Mixed Integer Linear Programming) problems larger than what is currently possible and will thus further increase the relevance and impact of this already important class of problems.

La Programmazione Lineare (LP) è una classe di problemi di ottimizzazione vincolata nella quale sia la funzione obiettivo che i vincoli cui il problema è soggetto sono lineari rispetto alle variabili. La programmazione lineare ed i primi problemi ad essa connessi risalgono al 1945, quando il premio Nobel George Stigler formula “il problema della dieta”, ovvero la formulazione di un menu per soddisfare una dozzina circa di richieste nutrizionali con la minima spesa. Nel 1947, Dantzig formalizza il concetto di programmazione lineare come viene oggi inteso e crea anche il metodo risolutivo conosciuto come “metodo del Simplesso”. Tale metodo è rimasto l’unico esistente fino a quando Karmakar, nel 1984, propone un nuovo metodo risolutivo, il metodo cosiddetto dell’Interior Point, al fine di superare alcuni problemi che limitavano le possibili applicazioni del metodo del Simplesso. Tale metodo, infatti, nasce con l’intento di fornire un algoritmo risolutivo che assicuri un numero massimo di iterazioni polinomiale rispetto al numero delle variabili. Nel 2011 il professor Buzzi-Ferraris ha formulato e proposto il metodo dell’Attico. Obiettivo di tale nuovo metodo è fornire uno strumento che possa sfruttare al meglio gli avanzamenti matematici effettuati negli ultimi trent’anni nel campo dei linguaggi di programmazione (viene utilizzata, infatti, la programmazione orientata agli oggetti tipica del linguaggio di programmazione C++) e della fattorizzazione di matrici, in modo da risultare di più facile utilizzo e, di solito, maggiormente performante.. Le caratteristiche matematiche peculiari e i primi testi e confronti effettuati in questo lavoro di tesi fanno ipotizzare che, una volta sviluppato adeguatamente l’algoritmo, attraverso il metodo dell’Attico sarà possibile avere uno strumento efficace e performante per la risoluzione di problemi LP e MILP (Mixed Integer Linear Programming) di dimensioni maggiori rispetto a quanto oggi possibile e permetterà dunque di aumentare ulteriormente l’importanza e l’impatto di questa già fondamentale classe di problemi.