Simplex Tutor

Simplex Tutor e' una piccola web app fatta in HTML, CSS e JavaScript puro per risolvere problemi di Programmazione Lineare con il metodo del simplesso.

L'idea e' abbastanza semplice: invece di ottenere solo il risultato finale, il programma mostra anche i passaggi intermedi, cioe' forma standard, tableau, costi ridotti, test dei rapporti, pivot, Fase I/Fase II, simplesso duale e soluzione finale. L'ho pensato come supporto allo studio: non sostituisce il ragionamento a mano, pero' aiuta a controllare se i passaggi che si stanno facendo sul quaderno hanno senso.

Non serve installare framework o fare build. Basta aprire index.html nel browser. Le formule matematiche vengono renderizzate con KaTeX da CDN; se KaTeX non carica, i calcoli restano comunque leggibili come testo.

Indice

• Cosa Risolve
• Come Si Usa
• Screenshot
• Esempio Di Input
• Convenzione Del Tableau
• Cosa Mostra Alla Fine
• Import, Export E Copia
• Grafico Interattivo
• Diagramma Del Progetto
• Test
• Struttura Del Progetto
• Limiti
• Possibili Miglioramenti
• Uso Di Strumenti AI
• Licenza

Cosa Risolve

Il programma lavora con problemi di programmazione lineare continua. Supporta:

• problemi di massimo e di minimo;
• vincoli <=, >= e =;
• variabili >= 0, <= 0 oppure libere;
• coefficienti interi, decimali e frazionari, tipo 3/2;
• trasformazione in forma standard;
• variabili slack, surplus e artificiali;
• metodo delle due fasi;
• simplesso duale per i tableau dualmente ammissibili, come nella Lez14;
• scelta automatica del metodo, oppure forzata su due fasi o duale;
• base iniziale automatica oppure indicata dall'utente;
• casi inammissibili;
• casi illimitati;
• degenerazione;
• ottimi multipli;
• costruzione del duale e confronto del valore primale/duale;
• certificato di ottimalita con scarto complementare e costi ridotti da base;
• grafico interattivo della regione ammissibile per problemi a due variabili.

I calcoli interni usano frazioni esatte, quindi si evitano molti problemi tipici dei numeri decimali in virgola mobile.

Come Si Usa

Apri index.html con il browser.

Nel pannello di sinistra trovi l'editor del problema. Da li' puoi:

• generare un esercizio nuovo con Problema random;
• scegliere se il problema e' di massimo o minimo;
• scegliere il metodo di risoluzione: automatico, due fasi o simplesso duale;
• modificare i coefficienti della funzione obiettivo;
• aggiungere o togliere variabili (fino a 40);
• aggiungere o togliere vincoli (fino a 60);
• scegliere il verso dei vincoli;
• impostare il segno delle variabili;
• indicare, se vuoi, una base iniziale.

Dopo aver inserito il problema, premi Risolvi. Il pulsante mostra uno spinner durante il calcolo. Il programma calcola la soluzione e mostra i passaggi uno alla volta. Con i pulsanti Avanti e Indietro puoi scorrere il procedimento.

Ci sono due modalita' di visualizzazione:

• Studente: mostra spiegazioni, calcoli e dettagli utili da ricopiare o confrontare con gli appunti. La sezione Forma standard scritta e' collassabile: si apre cliccando sull'intestazione e resta chiusa di default.
• Compatta: mostra soprattutto il tableau, utile quando si vuole controllare velocemente il procedimento.

Se il problema ha due variabili puoi premere Apri grafico. Si apre una pagina separata con il piano cartesiano interattivo, la regione ammissibile e la soluzione ottimale.

Screenshot

La schermata principale contiene l'editor del problema, il tableau passo passo e il riepilogo della soluzione.

Per i problemi a due variabili e' disponibile anche la vista grafica della regione ammissibile.

Esempio Di Input

Un problema si puo' inserire anche importando un JSON. Il formato e' questo:

{
  "direction": "min",
  "method": "auto",
  "variables": [
    { "name": "x1", "sign": "nonnegative" },
    { "name": "x2", "sign": "nonnegative" }
  ],
  "objective": ["1", "1"],
  "constraints": [
    { "coefficients": ["1", "1"], "relation": ">=", "rhs": "4" }
  ],
  "initialBasis": [""]
}

I valori principali sono:

Campo	Significato
direction	max oppure min
method	auto, two-phase oppure dual-simplex
variables	lista delle variabili del problema
sign	nonnegative, nonpositive oppure free
objective	coefficienti della funzione obiettivo
constraints	lista dei vincoli
relation	<=, >= oppure =
rhs	termine noto del vincolo
initialBasis	nomi delle variabili in base, oppure stringa vuota per automatico

Convenzione Del Tableau

Il tableau segue la convenzione usata a lezione: una variabile puo' entrare in base quando il costo ridotto mostrato in riga 0 e' negativo.

Anche i nomi delle variabili aggiunte seguono la stessa idea: le variabili slack e surplus continuano la numerazione delle x del problema (x4, x5, ecc.), mentre le variabili artificiali vengono indicate come y1, y2, ecc. Le variabili del problema duale sono invece indicate come p1, p2, ecc., come nelle esercitazioni del corso.

Per evitare ciclaggio nei casi degeneri viene usata la regola di Bland:

1. entra la variabile con indice minimo tra quelle candidate;
2. se nel test dei rapporti c'e' pareggio, esce la variabile di base con indice minimo.

Questa scelta puo' far venire tableau intermedi diversi da quelli scelti a mano dal professore, per esempio quando a lezione si sceglie "il costo piu' negativo". Il risultato finale pero' resta quello corretto, e Bland rende il procedimento piu' sicuro nei casi degeneri.

Nella tabella il programma mostra direttamente il valore da copiare sul foglio: in Fase I scrive w = ..., mentre nella fase del problema originale scrive z = .... Internamente il tableau puo' usare il segno opposto, ma l'interfaccia evita di mostrare -z proprio per non creare confusione nei calcoli a mano.

Con method: "auto" il programma usa prima una base naturale quando esiste. Se servirebbero artificiali ma il tableau e' dualmente ammissibile, avvia il simplesso duale: sceglie una riga con bbar < 0, poi la colonna entrante con il rapporto cbar_j / |abar_tj| sulle colonne con coefficiente negativo. Se queste condizioni non sono verificate, ripiega sul metodo delle due fasi.

Cosa Mostra Alla Fine

Quando il problema e' risolto, il programma mostra:

• primo passaggio con funzione obiettivo e vincoli riscritti in uguaglianza, mostrando chiaramente slack, surplus e artificiali (sezione collassabile);
• valore ottimo della funzione obiettivo;
• valore delle variabili originali;
• metodo usato;
• base finale;
• se e' stata usata la Fase I;
• se e' stato usato il simplesso duale;
• se sono state introdotte artificiali;
• se la soluzione e' degenere;
• eventuali ottimi multipli;
• problema duale e valore ottimo duale, quando disponibile;
• certificato di ottimalita con:
  • condizioni di scarto complementare;
  • spiegazione di come dagli slack e dalle variabili non nulle nascono le equazioni per il vettore duale p;
  • matrice aumentata [M | q] e riduzione di Gauss-Jordan per ricavare p;
  • matrice di base, inversa e costi ridotti fuori base.

Se il problema non ha soluzione ammissibile, viene segnalato come inammissibile. Se invece la funzione obiettivo puo' migliorare senza limite, viene segnalato come illimitato.

Import Ed Export

Il pulsante Esporta problema salva il problema corrente in JSON.

Il pulsante Importa problema carica un problema JSON gia' preparato.

Grafico Interattivo

Per i problemi a due variabili, il pulsante Apri grafico apre una pagina separata con il piano cartesiano interattivo. Il grafico mostra:

• la regione ammissibile evidenziata con riempimento gradiente e bordo;
• le rette dei vincoli tratteggiate, ognuna con un colore diverso e la propria etichetta;
• i vertici della regione ammissibile come pallini; passando sopra con il mouse appare un tooltip con le coordinate esatte;
• il percorso del Simplex passo per passo, con frecce direzionali su ogni segmento;
• il punto ottimale con effetto glow e le coordinate in evidenza;
• la linea della funzione obiettivo z = ... tracciata sul valore ottimo;
• gli assi cartesiani con frecce, label delle variabili e griglia.

All'apertura, gli elementi vengono disegnati progressivamente con un'animazione di ingresso.

I controlli disponibili sono:

• zoom con rotella del mouse o pinch su mobile;
• trascinamento del piano con clic e trascina;
• Adatta: adatta la vista alla regione ammissibile;
• Reset: torna alla vista iniziale;
• 📷 Esporta PNG: scarica un'immagine del grafico corrente, comprensiva dello sfondo (rispetta il tema chiaro/scuro).

Diagramma Del Progetto

Test

Per lanciare i test serve Node.js.

I test principali sono:

node tests/run-tests.js

Questi controllano i casi base: frazioni, matrici, forma standard, Fase I, Fase II, simplesso duale, certificati di ottimalita, problemi inammissibili, illimitati, degeneri, ottimi multipli e alcuni esempi delle lezioni.

Ci sono poi stress test piu' pesanti:

node tests/stress-tests.js

Questi aggiungono casi piu' particolari, tra cui variabili libere, variabili non positive, uguaglianze ridondanti, esempio classico di ciclaggio risolto con Bland, Klee-Minty, stress dedicati al simplesso duale e centinaia di problemi 2D random confrontati con una enumerazione indipendente dei vertici.

Ho aggiunto anche una cartella di test extra, piu' separata e ordinata:

node tests/extra/run-extra-tests.js

Dentro ci sono test divisi per argomento: casi inammissibili, illimitati, problemi random 2D e 3D controllati con un enumeratore indipendente dei vertici, variabili libere/non positive e controlli sul certificato di ottimalita.

Infine ci sono benchmark presi da Netlib:

node tests/netlib-benchmark-tests.js

Questi scaricano online alcuni problemi in formato MPS (AFIRO, SC50A, SC50B, ADLITTLE) e confrontano il valore ottimo ottenuto con quello noto. Richiedono connessione internet e possono metterci qualche secondo, soprattutto ADLITTLE.

Struttura Del Progetto

index.html                 pagina principale
graph.html                 grafico interattivo a due variabili
certificate.html           verifica teorica e pratica dell'ottimalita

assets/
  icons/                   icone e logo

src/
  core/
    fractions.js           frazioni esatte e costanti condivise
    matrix.js              inversione di matrici
    problem.js             parsing e validazione del problema
    standard-form.js       trasformazione in forma standard
    standard-display.js    formule da mostrare nel primo passaggio
    tableau.js             tableau, pivot, Fase I, Fase II e simplesso duale
    solution.js            estrazione della soluzione finale
    duality.js             costruzione del duale
    certificate.js         scarto complementare e certificato dei costi ridotti
    solver.js              coordinamento della risoluzione
    examples.js            esempi precaricati
    simplex-engine.js      facciata pubblica usata da browser e test

  js/
    state.js               stato dell'app
    editor.js              editor del problema
    standard-form-view.js  visualizzazione delle uguaglianze standard (tendina)
    renderers.js           rendering dei risultati
    actions.js             pulsanti, import/export e pagine esterne
    graph-view.js          pagina del grafico interattivo
    certificate-view.js    pagina della verifica di ottimalita
    main.js                inizializzazione
    utils.js               funzioni di supporto

  styles/
    base.css               stile generale
    components.css         bottoni, pannelli e componenti (spinner incluso)
    editor.css             editor del problema
    tableau.css            tableau, calcoli e sezione forma standard
    graph-view.css         pagina grafico
    certificate-view.css   pagina verifica
    responsive.css         adattamento mobile
    tokens.css             variabili grafiche

Limiti

Il progetto non risolve problemi interi o binari. Non fa branch and bound, cutting planes, funzioni obiettivo non lineari o analisi di sensitivita' completa.

Il grafico 2D e' un aiuto visivo, non una verifica formale per tutti i casi. Per problemi con variabili libere o non positive conviene fidarsi del tableau e usare il grafico solo come supporto.

Possibili Miglioramenti

Alcune idee che si potrebbero aggiungere in futuro:

• esportazione PDF del procedimento;
• salvataggio di una libreria di esercizi;
• esportazione del certificato in formato stampabile;
• analisi di sensitivita' su costi e termini noti;
• parser per importare direttamente file MPS dall'interfaccia.

Uso Di Strumenti AI

Durante lo sviluppo sono stati usati strumenti AI come supporto per alcune parti del lavoro, in particolare per il refactoring del codice, la scrittura di test aggiuntivi, la revisione del README e il controllo di possibili casi limite. La logica matematica, le scelte progettuali e la verifica finale del funzionamento sono state comunque controllate manualmente.

Licenza

Il progetto e' distribuito con licenza MIT.