Questo lavoro nasce come tesina per il corso di Ricerca Operativa tenuto dal Prof. Ferdinando Pezzella presso l'Università Politecnica delle Marche. La correttezza dell'implementazione degli algoritmi sviluppati non è stata verificata, pertanto il risultato fornito da questo software potrebbe non essere quello prodotto dall'algoritmo del simplesso di G.B. Dantzig.
Il programma può essere usato dal sito gim.altervista.org/ro/
Si pregano gli utilizzatori di fornire nota dei bug che ravvisano.
Simplex-in-PHP si propone di visualizzare il modo in cui opera il metodo del simplesso, risolvendo in modo del tutto simile al modo di procedere degli studenti, i problemi di solito proposti negli scritti di Ricerca Operativa.
Il progetto si limita a fornire una soluzione basata su passi iterati di pivoting e perciò non sono state implementate altre funzioni di ricerca euristica o di semplice verifica di non ricorrenza. In questo modo l'algoritmo non dà garanzia di giungere alla soluzione.
L'algoritmo per girare deve rappresentare i dati in notazioni (forme) interne convenienti e considerare nel far ciò tutti i possibili casi. Sono state fatte delle scelte volte ad eliminare delle variabili artificiali dove non strettamente necessarie, anche se ciò comporta una diversa rappresentazione del problema in esame.
Il programma è stato implementato allo scopo di fornire in output la risoluzione passo passo di un problema di programmazione lineare, in molto del tutto simile all'analisi eseguita manualmente. Si è scelto, anche per facilitare le operazioni di debugging e di riscontro della correttezza dell'algoritmo, di rappresentare tutti i passaggi: visualizzazione del problema immesso, del problema portato prima in forma standard e successivamente in forma canonica, rappresentazione del tableau anche nel caso eventuale di utilizzo del metodo delle due fasi con indicazione ad ogni passo dell'insieme degli indici di base e del valore della soluzione di base associata ad ogni tabella. Si è scelto di risolvere il problema di programmazione lineare intera mediante il metodo dei piani di taglio. Inoltre per evitare i problemi di convergenza nelle operazioni di pivoting, quindi fornire una soluzione corretta e conforme all'analisi eseguita manualmente, anzichè usare l'aritmetica in virgola mobile del calcolatore si è fatto uso di operazioni su numeri razionali implementando un'apposita classe. In aggiunta, sempre per rimanere aderenti alla soluzione su carta di semplici problemi, si rappresenta l'analisi grafica dei problemi che coinvolgono due sole variabili di decisione.
Si segua il seguente link.
Primo compito del programma è acquisire i dati del problema. Allo scopo vengono create due pagine: immissione_dati_0.php e immissione_dati_1.php. La prima richiede informazioni sul tipo di problema (massimo o minimo,continuo o intero) e sulle dimensioni; il secondo acquisisce i coefficienti. In entrambe le pagine si è fatto uso di funzioni JavaScript per verificare il tipo di dati immessi e le dimensioni del problema. Il controllo viene poi passato a simplesso.php che si occupa, passo per passo, della visualizzazione dei risultati delegando lo svolgimento di molte delle operazioni sul tableau al codice in matrice.php. Si è optato di lavorare con numeri razionali piuttosto che con numeri in virgola mobile, perché spesso i problemi sono posti in tali termini ed è piú agevole verificare che la soluzione sia a numeri interi evitando gli errori dovuti agli arrotondamenti. Allo scopo è stata implementata una classe: razionale.php. Altre routine ausiliarie per la visualizzazione e verifica dei dati o delle proprietà del problema sono in util.php. template,php e testata.php contengono informazioni relative alla formattazione e il primo dei due file fornisce i metodi per una visualizzazione uniforme delle pagine. Nel caso di problemi immessi con due variabili di decisione viene presentata la soluzione grafica grazie alle funzioni definite in immagini.php che si appoggiano alla libreria grafica GD. Per la visualizzazione dei sorgenti si è fatto uso di un semplice script: show_src.php, mentre un programma leggermente piú complesso si è reso necessario per la gestione degli esempi: show_esempi.php. Quest'ultimo si appoggia ad un programma scritto in C che da una definizione del problema di programmazione lineare espressa con una sintassi particolare genera la richiesta di esecuzione dell'algoritmo del simplesso al web server.
L'unica operazione di cui è responsabile il file
è l'immissione dei dati del primo modulo. I dati numerici
immessi devono essere di tipo intero, frazionario o decimale.
L'output dovrebbe apparire simile al seguente:
Crea in modo dinamico il modulo per l'immissione del testo del
problema. Accetta interi, numeri decimali, frazioni e la stringa vuota.
L'output nel caso di un PLI di massimo con 2 variabili di decisione e
due vincoli dovrebbe essere il seguente:
Questo, insieme a matrice.php e razionale.php è fra gli script piú importanti. Compie in sequenza tutta una serie di operazioni:
Per visualizzare il problema immesso (operazione necessaria per avere riscontro sulla correttezza dei dati introdotti) è stata implementata una funzione apposita in util.php.
Per portare il problema in forma standard e anticipare alcune operazioni atte a ridurlo in forma canonica occorrono alcuni passi:
A questo punto viene rappresentato il problema in forma standard.
Per portare il problema in forma canonica per prima cosa si richiede di avere tutti i coeficienti delle risorse positivi:
Successivamente vengono impiegate due strategie: o l'aggiunta di una variabile artificiale o, se possibile, la divisione della riga per un opportuno coefficiente, in modo da far entrare in base una variabile di decisione anzichè introdurre un'ulteriore variabile. Nel secondo caso si devono verificare tutte le seguenti condizioni:
Nel caso in cui siano state aggiunte variabili artificiali o sia stata divisa qualche riga il problema differisce da quello in forma standard e pertanto ne viene rappresentata la forma canonica.
Se sono presenti variabili artificiali si esegue la prima fase del metodo delle due fasi. L'algoritmo consiste in un ciclo, eseguito al massimo 10 volte per ragioni di tempo e di eventuale non convergenza dell'algoritmo (che si sarebbe potuta verificare o in modo semplice, ma non certo controllando se il valore assunto dalla funzione obiettivo nei vari passi si mantiene costante o, mediante un algoritmo piú complesso controllando che il tableau sia diverso da uno di quelli precedenti).
In questa fase per prima cosa viene aggiunto in testa al tableau la riga della forma di inammissibilità da minimizzare. Il loop consiste nell'eseguire un passo di pivot e controllare lo stato del tableau. Le condizioni considerate sono:
Se la regione di ammissibilità del P.L. non è vuota si deve ripristinare il tableau rimuovendo la forma di inammissibilità e le variabili artificiali. Inoltre va corretto l'assegnamento (variabile di base => riga risorsa).
A questo punto si esegue il metodo del simplesso: un ciclo che itera secondo lo schema seguente:
La scelta dell'elemento di pivot per il metodo del simplesso:
Quando il problema è a variabili intere viene ad ogni passo valutato se la soluzione e le variabili sono a valori interi. Se non è così viene generato un vincolo da aggiungere al problema iniziale secondo il metodo dei piani di taglio. A differenza della risoluzione precedente viene impiegato il metodo del simplesso duale.
La scelta dell'elemento di pivot per il metodo del simplesso duale:
Nel progettare l'applicazione non si è curata in
alcun modo l'efficienza, tranne in rari casi, a vantaggio di una chiara
esposizione dei passaggi richiesti dal metodo del simplesso. Si
eseguono piú operazioni del necessario per rappresentare
ogni singolo passo, senza utilizzare il simplesso revisionato;
la costruzione del tableau avrebbe potuto essere fatta in un solo
passaggio; vengono allocate piú variabili di quante
strettamente necessarie, ad esempio per tenere traccia degli indici di
base.
L'indicazione delle strutture dati e delle funzioni da ottimizzare
è certamente non esaustiva.
PHP: Hypertext Preprocessor. Si tratta di un linguaggio interpretato comunemente impiegato per lo sviluppo di presentazioni Web. La sintassi deriva dal C, dal Java, e dal Perl. Due caratteristiche importanti sono la possibilità di programare mediante il paradigma orientato agli oggetti e la semplicità d'uso. Scopo principale di questo linguaggio è scrivere pagine che vengano generate dinamicamente dal web server. Le specifiche del linguaggio sono disponibili all'indirizzo http://www.php.net/docs.php.
HyperText Markup Languageè il linguaggio di markup utilizzato per descrivere la struttura dei contenuti di un documento ipertestuale. Si limita a descrivere gli elementi del documento, definendo il contenuto e non la formattazione. Il suo impiego riguarda la pubblicazione di siti Web.
Cascading Style Sheetsè un linguaggio usato per descrivere come formattare gli elementi di una pagina HTML.