Algoritmo del simplesso

Quali problemi risolve il programma

Esempi

Di seguito viene presentata la soluzione di un problema con due variabili di decisione.

Per vedere altri esempi senza immettere manualmente i dati del problema è sufficiente selezionare dall'elenco seguente il nome con cui viene rappresentato un problema, poi premendo il pulsante "Procedi" verrà visualizzata la soluzione.

Scelte implementative

Come funziona

Primo compito del programma è acquisire i dati del problema. Questo avviene tramite una sola pagina: immissione_dati.php, che raccoglie sia le impostazioni del problema (massimo/minimo, continuo/intero, dimensioni), sia i coefficienti di funzione obiettivo e vincoli. In questa pagina si fa 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.

immissione_dati.php

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:

simplesso.php

Questo, insieme a matrice.php e razionale.php è fra gli script più importanti. Compie in sequenza tutta una serie di operazioni:

• visualizza il problema immesso;
• porta il problema in forma standard;
• mostra la forma standard;
• aggiunge eventuali variabili artificiali e calcola la forma di inammissibilità;
• mostra il problema in forma canonica;
• se necessario esegue la prima fase del metodo delle due fasi;
• esegue il algoritmo del simplesso;
• se il problema è a variabili intere applica il metodo dei piani di taglio;
• visualizza il risultato di ogni operazione effettuata sul tableau e le condizioni di uscita.

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:

• se il problema è di massimo occorre trasformarlo nel problema di minimo equivalente cambiando di segno i coefficienti di costo;
• si aggiungono le variabili ausiliarie slack o surplus e vengono aggiunte le variabili slack fra le variabili di base. Questo per risparmiare operazioni inutili per valutare l'aggiunta di eventuali variabili artificiali.

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:

• se un vincolo è espresso con un una risorsa negativa viene moltiplicata la riga del vincolo per -1 e viene invertito il verso della disequazione;

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:

• la variabile x_j è presente nel vincolo con coefficiente a_ij positivo
• x_j non compare nella funzione obiettivo
• x_j non compare negli altri vincoli

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:

1. ρ è all'ottimo.

   Vengono controllati i casi:

   1. ρ = 0;

      tutte le variabili artificiali sono uscite dalla base?

      1. Si:

         si può procedere alla seconda fase.

      2. No, ma è possibile effettuare un'operazione di pivot per estrarle dalla base:

         ulteriori pivot per estrarle dalla base.

      3. No, e non è possibile estrarle dalla base:

         un'equazione del P.L. in forma standard è combinazione lineare delle altre;

   2. ρ < 0;

      impossibile: ρ è somma di variabili non negative;

   3. ρ > 0;

      la regione di ammissibilità di z è vuota;

2. ρ è illimitata inferiormente;

   impossibile: ρ è per costruzione non negativa;

3. la regione di ammissibilità è vuota;

   impossibile: esiste sempre almeno una soluzione di base.

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 algoritmo del simplesso: un ciclo che itera secondo lo schema seguente:

1. z è all'ottimo.

   Vengono controllati i casi:

   1. Soluzione ottima unica;

      l'algoritmo termina;

   2. Più soluzioni ottime;

      l'algoritmo termina senza cercare le altre soluzioni;

2. z è illimitata;

   l'algoritmo si arresta;

3. la soluzione è migliorabile;

   si effetta un'altra operazione di pivoting.

La scelta dell'elemento di pivot per il algoritmo del simplesso:

1. Cerca il coefficiente di costo c_j più piccolo.

   Vengono controllati i casi:

   1. c_j ≥ 0

      nessun pivot in quanto la soluzione è già ottima;

   2. c_j < 0;

      seleziona la colonna di indice j;

2. se per ogni i a_ij ≤ 0;

   allora la soluzione è illimitata e non serve il pivot;

3. valuta per ogni i tale che a_ij > 0 il rapporto b_i / a_ij

   scegli i per cui il rapporto è minimo.

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 algoritmo del simplesso duale:

1. Cerca l'elemento b_i più piccolo del vettore delle risorse.

   Vengono controllati i casi:

   1. b_i ≥ 0

      nessun pivot in quanto la soluzione è già ottima;

   2. b_i < 0;

      seleziona la riga di indice i;

2. se per ogni j a_ij > 0;

   allora la soluzione è inammisibile e non serve il pivot;

3. valuta per ogni j tale che a_ij < 0 il rapporto c_i / (-a_ij)

   scegli j per cui il rapporto è minimo.

Efficienza

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.

Varie

Linguaggi

PHP8:

PHP è l'acronimo ricorsivo di 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 https://www.php.net/docs.php.

HTML5:

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.

CSS3:

Cascading Style Sheets è un linguaggio usato per descrivere come formattare gli elementi di una pagina HTML.

JavaScript:

È un linguaggio che permette di estendere e variare dinamicamente il contenuto di una pagina HTML. Viene interpretato dal browser e consente di arricchire le funzionalità dell'interfaccia. È object oriented e la sintassi si richiama al Java, ma è più semplice e più elastica.

C:

È un linguaggio imperativo di alto livello che offre funzioni per gestire in modo estremamente efficiente l'hardware. È nato per scrivere il sistema operativo UNIX e praticamente tutti i calcolatori dotati di un sistema operativo Unix-like forniscono un compilatore per tale linguaggio.

Software utilizzato

Sistemi Operativi:

Debian GNU/Linux (bookworm/trixie)

Microsoft Windows 10/11

Web Servers, moduli e librerie:

Nginx/1.26 (nginx)

PHP(8.4, 8.4.16 (php, php-fpm)

GD/2.3, 2.3.3 (php-gd)

Librerie software:

Bootstrap/5.3.8

Editor:

Emacs

vim (vim)

Browser:

Chromium (chromium)

Firefox (firefox)

links (links)

Apple Safari

Google Chrome

Sistemi per controllo versione:

git 2.47, git version 2.47.3 (git)

Utility per controllare la sintassi HTML:

HTML Tidy for Linux (tidy libtidy)

Compilatore C:

gcc 14, gcc (Debian 14.2.0-19) 14.2.0 (gcc)

Creazione e manipolazione delle immagini:

Gimp (gimp)

TeX (texlive)

Effetti collaterali

Realizzare questa tesina ha comportato anche alcuni effetti non correlati al algoritmo del simplesso. In primis ha richiesto di approfondire le conoscenze sul Web Server Nginx e dei linguaggi PHP8, JavaScript e HTML5. In aggiunta per automatizzare la richiesta di risoluzione di problemi particolarmente interessanti, sia ai fini di debugging del programma che per fornire un modo rapido per valutare questa tesina, è stato realizzato un programma in C che, processando un file di puro testo, genera l'appropriata richiesta a simplesso.php. Ciò ha comportato il rispolvero di alcune competenze su tale linguaggio e sul protocollo HTTP/1.1, oltre che sull'uso dei socket.