Unisteffo

Cosa sono?

Problemi che cercano di min/max il valore di una funzione obiettivo le cui incognite sono sottoposte a un sistema di vincoli.

Spesso sono detti anche problemi di LP.

Funzione obiettivo

La funzione da min/max.

Il vettore dei suoi coefficienti è detto , mentre quello delle sue incognite .

In genere, la funzione obiettivo è scritta in forma di combinazione lineare tra le incognite e i coefficienti:

Gradiente

Funzione della funzione obiettivo che restituisce la direzione del suo aumento più veloce.

Vincoli

Equazioni e disequazioni a cui devono sottostare le incognite perchè esse formino una soluzione valida.

I loro coefficienti sono contenuti nella matrice , mentre i loro termini noti nel vettore .

Poliedro

L'insieme che racchiunde tutte le soluzioni ammissibili di un problema.

Può essere finito, vuoto oppure illimitato.

Valore ottimo

La soluzione di un problema, ricavabile dal prodotto .

In particolare, il valore ottimo è un vertice del poliedro, detto vertice ottimo.

Forma generale

Un problema con:

• Equazioni e disequazioni
• Variabili non vincolate

Forma canonica

Un problema con:

• Solo disequazioni
• Vincoli di non-negatività sulle incognite

Forma standard

Un problema con:

• Solo equazioni
• Vincoli di non-negatività sulle incognite

Standard e generale

Applica questa conversione a ogni equazione nel sistema:

Canonica e standard

Aggiungi una variabile slack non-vincolata a ogni disequazione nel sistema:

Generale e canonica

Sdoppia ogni variabile non-vincolata in due variabili con vincolo di non-negatività:

Cos'è?

Un modo per rappresentare sistemi in forma standard, anche noto come matrice equivalente completa del sistema.

Trasformazioni

Un tableau è un sistema di equazioni in forma matriciale completa.

È possibile effettuare senza che cambi il risultato finale le seguenti trasformazioni:

• Moltiplicare un'intera riga per una costante.
• Sommare una riga a un'altra

Variabili nella base

Variabili che hanno tutti 0 e un solo 1 nella loro colonna del tableau.

La loro controparte sono le variabili fuori base, che hanno qualsiasi altro valore.

Valore attuale

Il valore della funzione obiettivo che si otterrebbe se tutte le variabili fuori base valessero 0.

Procedendo nella risoluzione (descritta in seguito) del tableau, questo valore aumenterà, fino a raggiungere il valore ottimo quando la risoluzione sarà completata.

Cos'è?

Un algoritmo per trovare efficientemente il valore ottimo e le coordinate di un vertice ottimo in problemi di ottimizzazione lineare.

Perchè sia possibile effettuare il Simplex è necessario che l'origine sia nel poliedro: pertanto, non è possibile che un problema risolto con il Simplex sia vuoto.

I passi

1. Trasforma il sistema in forma standard.
2. Trova tante variabili linearmente indipendenti quante siano le righe: esse saranno la base iniziale.
3. Finchè ci sono variabili con coefficienti min/max nella funzione obiettivo:

   1. Scegli la prima variabile fuori base con coefficiente min/max nella funzione obiettivo: essa è la variabile entrante.

   2. Scegli la variabile in base con il minor rapporto positivo:

   3. Pivot: trasforma tutte le funzioni del sistema in modo che abbiano 0 nella colonna della variabile entrante, tranne nella riga della variabile uscente, in cui avrà 1.

4. Il poliedro è finito: i termini noti dei vincoli sono le coordinate del suo vertice ottimo, mentre il termine noto della funzione obiettivo è il valore ottimo.

Soluzioni di base degenerata

Una soluzione con almeno una variabile di valore , dovuta a uno o più vincoli ridondanti.

Senza Regola di Bland e in presenza di vincoli ridondanti si rischia di trovarsi a fare pivot infiniti.

Metodo delle due fasi

Un estensione del Simplex per permettere la risoluzione di problemi la cui origine non è una soluzione ammissibile.

Prevede l'introduzione di un problema ausiliario, le cui incognite sono dette artificiali.

Il vettore delle incognite artificiali è solitamente chiamato .

Procedimento

1. Crea un nuovo tableau, aggiungendo variabili artificiali in modo da avere una base ammissibile.
2. Sostituisci la vecchia funzione obiettivo con una nuova che minimizzi la somma di tutte le variabili artificiali.
3. Fase 1: Risolvi il nuovo problema con il Simplex primale.
4. Se il Simplex termina quando ci sono ancora variabili artificiali nella base, allora il poliedro è vuoto.
5. Una volta che le variabili artificiali sono fuori base, elimina le loro colonne e la nuova funzione obiettivo.
   
6. Riporta il tableau in forma base compiendo operazioni per azzerare i coefficienti delle variabili di base nella funzione obiettivo.
7. Fase 2: Risolvi il tableau con il Simplex primale.

Cos'è?

Una versione semplificata di un problema nella quale si ignora la violazione di uno o più vincoli.

Rilassamento di Lagrange

Un rilassamento che permette di misurare di quanto i vincoli vengono violati.

I vincoli, moltiplicati per coefficienti di rilassamento, vengono inseriti nella funzione obiettivo.

Il vettore dei coefficienti di rilassamento solitamente è indicato con .

Duale

Il sistema che min/max i moltiplicatori di rilassamento di un problema detto primale.

In termini matriciali

Possiamo trasporre il tableau e sostituire le variabili con variabili per ottenere il sistema duale!

I maggiori e minori dei vincoli diventeranno maggiori e minori delle variabili e viceversa.

Feasibility del duale

• Se un problema ha una soluzione finita, allora anche il suo duale la avrà.
• Se un problema è vuoto, allora il suo duale potrà essere vuoto oppure illimitato.
• Se un problema è illimitato, allora il suo duale sarà certamente vuoto.

Variabili e vincoli

Variabili e vincoli del duale corrispondono rispettivamente a vincoli e variabili del primale.

In particolare:

Lemma di Farkas

Una disuguaglianza lineare è verificata da tutti i punti di un poliedro non-vuoto se e solo se esiste un vettore tale che:

Dualità forte

Il teorema che dimostra l'equivalenza tra primale e duale.

Se uno dei due problemi è finito, la soluzione di uno coincide con la soluzione dell'altro.

TODO: Anche qui c'è una lunga dimostrazione...

Dualità debole

Il teorema che dimostra che il valore della funzione obiettivo del duale (di un qualsiasi tableau) è sempre min/max alla soluzione del corrispettivo primale.

TODO: Dimostrazione cortina, ma sembra complicata.

Condizioni di ottimalità

Il teorema che ci permette di passare dalla soluzione del duale alla soluzione del primale. TODO: credo?

Si deriva combinando le seguenti condizioni:

• Ammissibilità del primale:
• Ammissibilità del duale:
• Teorema della dualità forte: (alla soluzione ottima)

Ne risulta che una soluzione è ottima se e solo se:

Cos'è?

Un'estensione al Simplex primale che opera sul problema duale.

Come funziona?

Funziona esattamente come il Simplex primale, ma opera sul duale.

Cos'è?

Un procedimento che misura di quanto può variare il termine noto di un vincolo o il coefficiente della funzione obiettivo prima che la base degeneri.

Cos'è?

Particolari problemi di ottimizzazione lineare in cui le variabili sono vincolate ad essere numeri interi.

Spesso detti anche problemi di ILP.

Rilassamento lineare

Un rilassamento che rimuove il vincolo di integrità a un problema, trovando la sua soluzione continua.

Enumerazione totale

Un modo per passare dalla soluzione del rilassamento alla soluzione intera di un problema di ILP.

Consiste nel calcolare la soluzione di ogni singolo punto incluso nel poliedro, e selezionare la min/max.

Trova sicuramente la soluzione giusta, ma il costo computazionale è esponenziale !

Arrotondamento

Un altro modo per passare dalla soluzione del rilassamento alla soluzione intera di un problema di ILP.

Consiste nell'arrotondare tutte le variabili al loro valore intero più vicino, e calcolarne il valore ottimo.

Funziona bene per valori grandi, ma più essi si avvicinano allo 0 più l'errore diventa grande.

Piani secanti

Un altro modo ancora per passare dalla soluzione del rilassamento alla soluzione intera di un problema di ILP.

Consiste nel tagliare il poliedro con nuovi vincoli (piani secanti) che riducono le possibili soluzioni continue ma non quelle intere.

Per selezionare i vincoli, si usano i tagli di Gomory:

Per ogni valore noto frazionario si viene quindi a creare una nuova variabile in base e un nuovo vincolo formato dall'opposto di tutti i valori frazionari dei coefficienti fuori base.

Divide et impera

È possibile usare la tecnica divide et impera per rendere più efficiente l'enumerazione totale.

Si divide il problema principale (trovare il valore ottimo di un problema di ILP) in più sottoproblemi (trovare il valore ottimo di un problema di ILP con una variabile impostata a un valore fisso).

Si crea così un albero.

È possibile chiudere in anticipo alcuni nodi dell'albero se il loro miglior possibile valore ottimo è inferiore a uno precedentemente trovato o se il loro poliedro è vuoto.

È possibile utilizzare diverse strategie di esplorazione dell'albero:

• depth-first: permette di raggiungere immediatamente a una soluzione accettabile (ma non ottimale)
• best-first: permette di raggiungere più velocemente alla soluzione corretta

Seca et impera

È possibile combinare il metodo dei tagli secanti con la tecnica divide et impera per raggiungere ancora più velocemente a una soluzione.

Si effettuano poche iterazioni del metodo dei tagli secanti, e sul risultato di quelle iterazioni si applica il divide et impera.

Grafo

Insieme di nodi e archi che li connettono.

Può essere diretto se gli archi hanno una direzione.

Nodi adiacenti

Nodi connessi da un arco.

Arco incidente

Arco connesso a un dato nodo.

Arco entrante o uscente

Un arco diretto che termina o inizia da un dato nodo.

Grado

Conteggio degli archi incidenti di un nodo.

Si può calcolare anche relativamente agli archi entranti o agli archi uscenti.

Percorso

Sequenza di archi consecutivi.

Connessione

Due nodi sono connessi se tra loro esiste almeno un percorso.

Un grafo è connesso se tutti i suoi nodi sono connessi.

Cicli e circuiti

Percorsi rispettivamente indiretti e diretti in cui l'inizio coincide con la fine.

Grafo completo

Grafo in cui ogni nodo è connesso con ogni altro.

Se diretto, contiene archi; altrimenti, ne contiene la metà.

Matrice di adiacenza

Vedi Algoritmi.

Lista di adiacenza

Vedi Algoritmi.

Taglio

Sottoinsieme di archi che connettono due sottoinsiemi di nodi.

Può essere anche uscente o entrante; in tal caso include solo gli archi entranti o uscenti dal sottoinsieme.

Sottografo

Sottoinsieme di nodi e archi di un grafo.

Tutti gli archi di un sottografo possono connettere solo nodi all'interno di esso.

Albero

Sottografo connesso e aciclico.

Spanning tree

Albero che include tutti i nodi di un grafo.

Prim

Crea uno spanning tree.

1. Aggiungi l'arco di costo minimo all'albero.
2. Finchè mancano ancora archi:
   1. Trova tutti gli archi che aggiungerebbero un nuovo nodo all'albero.
   2. Seleziona l'arco di costo minore.

Ordine topologico

Trova l'ordine topologico di un albero.

1. Ripeti finchè ci sono nodi nel grafo:
   1. Assegna un numero sequenziale a un nodo senza archi entranti.
   2. Elimina il nodo a cui hai assegnato il numero.
   3. Elimina tutti gli archi incidenti sul nodo che hai eliminato.

Percorsi minimi in grafo diretto

Trova i percorsi di costo minimo in un albero.

1. Trova l'ordine topologico dell'albero.
2. Invece che provare ogni singola combinazione di nodi, prova solo i nodi che hanno un numero topologico maggiore di quello del nodo attuale.

TODO: forse spiegarlo meglio non farebbe male

Algoritmo di Dijkstra

Vedi Algoritmi.

Algoritmo di Ford-Fulkerson

Costruisci il grafo residuo e vedi se c'è un percorso che va dalla sorgente alla destinazione.

Parametri

Valori che sono calcolati al momento della compilazione del programma:

param nomeparametro;

Si possono assegnare valori ai parametri nel codice con:

nomeparametro := 123 + 234;

Set

Insiemi di parametri:

set NOMESET;

Si possono definire i contenuti dei set con:

set DA_UNO_A_DIECI := 1 .. 10;
set DA_UNO_A_PARAMETRO := 1 .. parametro;
                

Si possono effettuare operazioni su set con:

set UNIONE := SET_A union SET_B;
set INTERSEZIONE := SET_A inter SET_B;
                

Variabili

Valori che sono calcolati al momento dell'esecuzione del programma:

var nomevariabile;

Requisiti

È possibile richiedere che un parametro o una variabile soddisfino certi requisiti.

Si può richiedere che siano o di un certo valore:

param positivo, > 0;
var non_positiva, <= 0;
                

Si può richiedere che appartengano a un dato set:

param intero_positivo, integer, > 0;
var zero_oppure_uno, binary;
                

Indici

È possibile creare anche un "array" di parametri o variabili:

param dieci_parametri{1..10};
var quadrato{1..10, 1..10};
var cubo{1..10, 1..10, 1..10};
                

Si possono usare anche set:

param dieci_parametri{DA_UNO_A_DIECI};
                

Funzione obiettivo

La funzione obiettivo può comparire solo una volta nel programma.

Si definisce con:

minimize valore_ottimo_min: espressione;
maximize valore_ottimo_max: espressione;
                

Vincoli

I vincoli a cui sono soggette le variabili si definiscono con:

nome_vincolo_1: espressione <= 1;
nome_vincolo_2: espressione >= parametro;
                

I vincoli possono essere indicizzati:

// La diagonale del quadrato deve essere minore di 1
v_3{i in DA_UNO_A_DIECI}: quadrato[i, i] <= 1;

// Tutti i valori del quadrato devono essere minori o uguali a 1
v_4{i in DA_UNO_A_DIECI, j in DA_UNO_A_DIECI}: quadrato[i, j] <= 1;
                

Esistono anche operatori aggregati:

// La somma degli elementi della diagonale deve essere maggiore o uguale a 0
v_5: sum{i in DA_UNO_A_DIECI} quadrato[i, i] >= 0;

// Il prodotto degli elementi della diagonale deve essere maggiore o uguale a 0
v_6: prod{i in DA_UNO_A_DIECI} quadrato[i, i] >= 0;
                

Si possono anche aggiungere requisiti agli indici:

v_7: sum{i in DA_UNO_A_DIECI, i <= 5} quadrato[i, i] >= 0;

v_8: prod{i in SET, i not in ALTRO_SET} quadrato[i, i] >= 0;
                

Termine del programma

Perchè il programma calcoli i valori di tutte le variabili, è necessaria l'istruzione:

solve;
                

Per stampare i valori calcolati, è possibile usare:

printf "%d \n", nomevar;
                

Eventualmente, anche in un ciclo for:

for{i in DA_UNO_A_DIECI} {
    printf "%d: %d \n", i, x[i];
}
                

Compilare ed eseguire

Per compilare ed eseguire il programma, è sufficiente eseguire:

glpsol --math nomefile.mod

È possibile specificare i dati in un file separato da quello del modello; in tal caso, si dovrà eseguire:

glpsol --math -m modello.mod -d dati.mod

Per salvare i risultati su file e visualizzarli a schermo:

glpsol --math nomefile.mod | tee risultati.txt