Crea sito

Metodo del Simplesso in PHP

Prefazione

Questa tesina nasce dalla volontà di capire più approfonditamente il modo in cui opera il metodo del simplesso e creare un programma che risolva, in modo del tutto simile al modo di procedere degli studenti, i problemi di solito proposti negli scritti di Ricerca Operativa.

L'implementazione per calcolatore di un algoritmo comporta o, meglio, dovrebbe comportare l'analisi di tutte le possibili evenienze che possono accadere nel processare i dati in ingresso e costringe il programmatore ad acquisire delle conoscenze in merito non superficiali. Particolare attenzione avrebbe dovuto essere riservata, in questo caso, ai possibili metodi di ricerca nello spazio delle soluzioni al fine di riconoscere e trovare nel minor tempo possibile la soluzione di un problema di minimo. Lo scopo con cui è nato il progetto però 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.

Anche se non detto esplicitamente sopra è evidente che la scelta di realizzare questo tipo di tesina è dettata dalla voglia di sviluppare un programma che giri in rete.

Quali problemi risolve il programma

Vengono risolti i problemi di programmazione lineare, eventualmente a variabili intere, espressi nella forma A x θ b, dove A è una matrice m x n, b un vettore a m componenti e θ un operatore relazionale scelto fra {">=", "<=" o "="}. Non è garantito che venga trovata la soluzione perchè non sono state implementate le funzioni necessarie a riconoscere se il vertice che viene esplorato sia già stato visitato. Pertanto potrebbero verificarsi dei cicli. In tal caso dopo un certo numero di iterazioni l'esecuzione termina avvisando della situazione occorsa.

Esempi

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




Analisi

Il problema introdotto è

max z = x1 + x2

Soggetto a

1) x1 =< 3
2) x1 + x2 =< 5
        xi >= 0 e INTERI     per i = 1,...,2


Il problema espresso in FORMA STANDARD

min z = - x1 - x2

Soggetto a

1) x1 + x3 = 3
2) x1 + x2 + x4 = 5
        xi >= 0 e INTERI     per i = 1,...,4


La FORMA CANONICA coincide con quella STANDARD.

[IMG]  Regione di ammissibilita'

Metodo del SIMPLESSO

Tableau al passo 0:

x1 x2 x3 x4
r00 -1 -1 0 0
r13 1 0 1 0
r25 1 1 0 1
Indici di base: S = { 3, 4 }
Soluzione di base: z = 0
x1 = 0
x2 = 0
x3 = 3
x4 = 5
[IMG]  Regione di ammissibilita'
Soluzione migliorabile. L'algoritmo continua ad iterare.
Pivot in riga r1 colonna x1.

Tableau al passo 1:

x1 x2 x3 x4
r03 0 -1 1 0
r13 1 0 1 0
r22 0 1 -1 1
Indici di base: S = { 1, 4 }
Soluzione di base: z = 3
x1 = 3
x2 = 0
x3 = 0
x4 = 2
[IMG]  Regione di ammissibilita'
Soluzione migliorabile. L'algoritmo continua ad iterare.
Pivot in riga r2 colonna x2.

Tableau al passo 2:

x1 x2 x3 x4
r05 0 0 0 1
r13 1 0 1 0
r22 0 1 -1 1
Indici di base: S = { 1, 2 }
Soluzione di base: z = 5
x1 = 3
x2 = 2
x3 = 0
x4 = 0
[IMG]  Regione di ammissibilita'
Questa è una delle possibili soluzioni ottime.
Pivot in riga r1 colonna x3.

Tableau al passo 3:

x1 x2 x3 x4
r05 0 0 0 1
r13 1 0 1 0
r25 1 1 0 1
Indici di base: S = { 3, 2 }
Soluzione di base: z = 5
x1 = 0
x2 = 5
x3 = 3
x4 = 0
z* = 5,     x* = λ [ 3, 2, 0, 5 ]T + (1-λ) [ 0, 5, 3, 0 ]T

Risoluzione mediante metodo dei PIANI DI TAGLIO

Soluzione ottima:     z* = 5,     x* = [ 0, 5, 3, 0 ]T



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.


Dal testo seguente vengono estratti i dati processati dal programma.


Scelte implementative

Come funziona

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.

immissione_dati_0.php

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:

Il problema è di minimo massimo

Numero delle variabili di decisione:

Numero dei vincoli:

Tutte le variabili sono intese non negative. Spunta la casella se devono essere INTERE.

immissione_dati_1.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:

max z = x1 + x2 +

Soggetto a

1) x1+ x2
2) x1+ x2
    xi >= 0 e INTERI   per i =1,...,2

simplesso.php

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:

In tal caso dividendo la riga i per aij xj entra in base.

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 metodo 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 metodo del simplesso:

  1. Cerca il coefficiente di costo cj più piccolo.
    Vengono controllati i casi:
    1. cj >= 0
      nessun pivot in quanto la soluzione è già ottima;
    2. cj < 0;
      seleziona la colonna di indice j;
  2. se per ogni i aij =< 0;
    allora la soluzione è illimitata e non serve il pivot;
  3. valuta per ogni i tale che aij > 0 il rapporto bi / aij
    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 metodo del simplesso duale:

  1. Cerca l'elemento bi più piccolo del vettore delle risorse.
    Vengono controllati i casi:
    1. bi >= 0
      nessun pivot in quanto la soluzione è già ottima;
    2. bi < 0;
      seleziona la riga di indice i;
  2. se per ogni j aij > 0;
    allora la soluzione è inammisibile e non serve il pivot;
  3. valuta per ogni j tale che aij < 0 il rapporto ci / (-aij)
    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

PHP:
PHP è l'acronicmo 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 http://www.php.net/docs.php.
HTML:
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.
CSS:
Cascading Style Sheets è un linguaggio usato per descrivere come formattare gli elementi di una pagina HTML.
JavaScript:
E' 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. E' object oriented e la sintassi si richiama al Java, ma è più semplice e più elastica.
C:
E' un linguaggio imperativo di alto livello che offre funzioni per gestire in modo estremamente efficiente l'hardware. E' 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

Per lo sviluppo e i test sulla portabilitè ho usato:
Sistemi Operativi:
Debian GNU/Linux
Red Hat Linux
Slackware Linux
Web Servers, moduli e librerie:
Apache/1.3.23, 1.3.26, 1.3.27
Apache/2.0.40, 2.0.47
PHP/4.2.2, 4.3.3
GD/2.0.15
libpng/1.2.2
Editor:
Emacs
Quanta
Browser:
Galeon
Konqueror
links
Mozilla Firebird
Netscape
Sistemi per controllo versione:
cvs
Utility per controllare la sintassi HTML:
HTML Tidy for Linux
Compilatore C:
gcc
Creazione e manipolazione delle immagini:
Gimp
TeX


Effetti collaterali

Realizzare questa tesina ha comportato anche alcuni effetti non correlati al metodo del simplesso. In primis ha richiesto di approfondire le conoscenze sul Web Server Apache e dei linguaggi PHP4, JavaScript e HTML. 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.