All-In-One

Programmazione Lineare

Problemi di Ottimizzazione

Classificazione

• Ottimizzazione Matematica: problemi con 1 solo decisore, 1 solo obiettivo
• Ottimizzazione Multiobiettivo: 1 solo decisore, tanti obiettivi
• Game Theory: problemi con tanti decisori, ognuno vuole max profitto
• Ottimizzazione stocastica: problemi con dati incerti

I problemi di ottimizzazione hanno una struttura comune: un obiettivo e delle restrizioni. 

L’obiettivo è il criterio di scelta da seguire, le restrizioni sono i vincoli o le limitazioni delle possibili scelte. 

Definizione

Ottimizzare vuol dire la scelta migliore per soddisfare l’obiettivo, rispettando le restrizioni. 

Approccio modellistico:

1. Analisi del problema e raccolta dei dati Individuare l’obiettivo e le restrizioni;
2. Formulazione del problema Costruzione del modello matematico: determinare le variabili, individuare l’obiettivo, esprimere i vincoli
3. Studio del modello Esistenza delle soluzioni, unicità, etc…
4. Soluzione numerica
5. Validazione del modello

Ottimizzazione Matematica

Un problema di ottimizzazione è del tipo

Oppure:

Con:

• regione ammissibile (insieme scelte/ dei vincoli)

• soluzione ammissibile

• funzione obiettivo

Ogni problema di massimo può essere scritto come problema di minimo. Risulta infatti  

Classificazione dei problemi

Problemi lineari: la funzione obiettivo e i suoi vincoli sono funzioni lineari del tipo: 

Problemi non lineari: presenza di funzioni lineari.

Programmazione Lineare

Forma generale:

Si chiamano variabili decisionali.

Valgono le ipotesi:

• Additività: si sommano i contributi delle variabili;
• Proporzionalità: ogni variabile dà un contributo proporzionale a se stessa;
• Continuità: Le variabili sono reali.

Forma Generale Compressa

Link to original

Metodo Grafico per la programmazione Lineare

Rette nel piano

Una retta ha un’espressione del tipo è un vettore ortogonale alla retta appena definita, che punta verso il semipiano Trasposto perché i vettori sono sempre in colonna.

I problemi di programmazione lineari in 2 variabili possono essere risolti graficamente.

Metodo Grafico

Si basa sulla rappresentazione geometrica della regione ammissibile, dei vincoli e della funzione obiettivo sul piano cartesiano. 

Nei problemi di PL i vincoli sono disequazioni lineari quindi semipiani.

Ponendo i vincoli in forma di retta, otteniamo il grafico:

E difatti la soluzione ottima sarà il punto

Come scegliere il semipiano giusto

Si prende il punto test e si sostituisce in , difatti in questo caso si ottiene , che è vero. Il semipiano giusto in questo caso è quello che contiene il punto test.

Osservazione

Se i coefficienti della funzione obiettivo non sono tutti nulli, la soluzione non è mai interna alla regione ammissibile. Quindi starà sul bordo.

Un’altra procedura è quella di considerare il fascio di rette generato dalle rette parallele e ortogonali a quella che rappresenta la funzione obiettivo, cioè quindi al vettore nell’esempio, in direzione dei valori crescenti di .

La soluzione ottima sarà l’ultimo punto ammissibile comune con la retta del fascio.

Procedura

1. Rappresentiamo i semipiani di vincoli sul piano cartesiano;
2. Per rappresentare la funzione obiettivo, tracciamo le linee di livello della f.o. , cioé il fascio di rette al variare di k.
3. Le linee di livello sono parallele tra loro e ortogonali al vettore . è il valore della f.o che dobbiamo max/minimizzare.
4. Per massimizzare: trasliamo la retta della f.o. seguento la direzione del vettore.
5. Per minimizzare: andiamo in direzione opposta.
6. Fra tutte le linee di livello prendiamo quella che ha il valore max (min) di k e si ottiene la soluzione prendendo l’ultimo punto comune tra la retta del fascio e la regione ammissibile

Link to original

Geometria della programmazione lineare

Mettiamo in luce le proprietà geometriche della regione ammissibile.

Iperpiano

L’insieme delle soluzioni di un’equazione lineare in variabili.

Semispazio

L’insieme delle soluzioni di una disequeazione lineare in n variabili.

O, per riassumere:

retta	iperpiano
semipiano	semispazi

Problema di PL

 

Sistema di equazioni e diseguazioni lineari in variabili intersezione di iperpiani e semispazi chiusi. 

Poliedro

Intersezione di un numero finito di iperpiani e semispazi chiusi. Alias: un insieme convesso (vedi sotto)

Combinazione convessa

Sia , è il punto con Propria

• La combinazione convessa di 2 punti dà il segmento che ha per estremi i due punti considerati;
• La combinazione convessa di 3 punti dà il triangolo

Combinazione convessa generale

Siano , il punto si chiama combinazione convessa di questi punti. Con e la somma di tutti i

Insieme convesso

Un insieme si dice convesso se anche il punto appartiene a Cioè dati due punti di k, il segmento ottenuto è tutto convenuto in .

Vertice

Un Vertice di un poliedro è un punto che non può essere espresso come combinazione convessa propria (cioè con ) di altri punti del poliedro. Un Vertice è un estremo di un segmento non può trovarsi “dentro” un segmento generato da altri punti.

Per riassumere

• La regione ammissibile di un problema di PL è un poliedro è convessa;
• I problemi di PL sono problemi convessi Gli ottimi locali sono globali.

Teorema Fondamentale della PL

Dato il problema:

Teorema Fondamentale della PL

Se ha una soluzione ottima, allora esiste un vertice ottimo. 

Conseguenza: La soluzione ottima va cercata fra i vertici

Esistono sempre vertici?

Risulta che un poliedro ha vertici non contiene rette. C’è una sola situazione nella quale la regione ammissibile non ha vertici, contiene rette, e ha soluzioni ottime.

Il poliedro è una striscia. 

Ci sono soluzioni ottime che sono tutti i punti della retta , e quindi il valore ottimo della funzione obiettivo è 2.

Link to original

Algebra della programmazione lineare

Cerchiamo di esprimere il concetto di vertice in modo algebrico, sfruttando la struttura di vincolo.

Forma Standard

Si dice Forma Standard di un problema di PL, il problema scritto nella forma:

con

Caratteristiche:

1. Problema di minimo;
2. Vincoli di uguaglianza;
3. Termini noti
4. Variabili

Ogni problema di PL può essere scritto in FS.

Regole di conversione

• Un problema di max si scrive come problema di min:
• Vincolo di si trasforma in vincolo di aggiungendo una variabile di SCARTO (SLACK)
• Vincolo di si trasforma in vincolo di sottraendo una variabile di SURPLUS
• Variabile , Si moltiplica per -1 e si rinomina:
  • si sostituisce in tutti i vincoli e nella f.o.
• Variabile libera in segno, si introducono due variabili , e si pone , e poi si sostituisce la variabile.

Forma Standard e Vertici

Partendo da un esempio, consideriamo il poliedro:

Se poniamo Troviamo la soluzione , le componenti sono è un vertice.

Generalizzando l’esempio, consideriamo: 

con:

E richiediamo che .

Perché?

• Se vuol dire che il sistema ha un’unica soluzione, cioè nella regione ammissibile c’è un solo punto, e quindi non c’è alcuna ottimizzazione da effettuare, non avendo alcuna altra scelta.
• Se vuol dire che ci sono dei vincoli in eccesso, ridondanti.

Per trovare i vertici…

• Annulliamo n-m variabili;
• Risolviamo il sistema nelle rimanenti variabili;
• Se le variabili sono tutte , abbiamo un vertice.

Dobbiamo però capire come scegliere le variabili da annullare.

Base Vettoriale

Data una matrice una base è una sottomatrice di formata da colonne linearmente indipendenti.

Se .

Individuata una base B, la matrice si partiziona:

Supponiamo che la matrice B sia fatta con le prime colonne di . 

Difatti, è quadrata: , le altre colonne di formano la matrice non di base . 

La matrice si partiziona quindi in e , ed anche il vettore si partiziona in: :

• componenti associate alla colonna di ;
• componenti associate alla colonna di

Il sistema allora si scrive:

La matrice B è invertibile, perché composta da colonne linearmente indipendenti. Per questo possiamo moltiplicare a sinistra per

Per trovare un vertice la scelta naturale è porre , cioè porre a zero le variabili fuori base. 

Soluzione di Base

Dato il sistema si dice soluzione di base il vettore , cioè e (Componenti di base sono date da e quelle fuori base sono nulle).

• Se la soluzione di base si dice ammissibile.
• Se qualche componente di base è nulla, si dice degenere

Teorema 1

Dato il poliedro è un vertice se e solo se è una soluzione di base ammissibile

• Per il Teorema Fondamentale della PL bisogna cercare l’ottimo tra i vertici;
• Per il Teorema 1 appena definito bisogna cerca l’ottimo tra le soluzioni di base ammissibile.

Quante soluzioni di base ammissibile ci sono?

Il numero di sol di base è legato al numero di basi B. Possiamo estrarre da A sottomatrici di ordine m. Fra queste sottomatrici, ve ne sono alcune non invertibili, e alcune che generano soluzioni di base non ammissibile. Quindi, il numero di soluzioni di base è al più

Questa è la base del Metodo del Simplesso

Link to original

Metodo del Simplesso

Preliminari al Metodo del Simplesso

Schema Generale

1. Si sceglie un vertice
2. Se Test Ottimalità
3. Se Test Illimitatezza
4. Si cambia vertice altrimenti

Forma Canonica

Sia dato un problema di PL in forma standard, e sia B una base, il problema si dice in forma canonica se tutte le variabili di base e la funzione obiettivo son espresse in funzione delle variabili fuori base.

Costi Ridotti

Dato un problema di PL in forma canonica (o anche standard) rispetto alla base B, i coefficienti delle variabili nella f.o. si dicono costi ridotti delle variabili rispetto alla base B

Considerando un problema in FS: 

Forma Canonica

(cioè tutto espresso in funzione di )

• La f.o. diventa quindi:
• • = f.o in forma canonica  

Perciò, il vettore dei costi ridotti:

• Si partiziona in:
• tutte le variabili di base, con costi ridotti nulli
• costi ridotti delle variabili fuori base

Test di Ottimalità

Si basa sul segno dei costi ridotti. Se i costi ridotti sono tutti , la soluzione di base corrente è ottima.

Sia la soluzione di base corrente. 

Sappiamo che i costi ridotti delle variabili fuori base sono , idem per

Quindi se la f.o in base qualunque f.o nella soluzione di base corrente la soluzione di base corrente è ottima.  

Se non vale il test di ottimalità si è costretti a cambiare vertice, passando ad un vertice adiacente. Cioè si passa a un’altra base .

deve:

• essere adiacente (cioè differisce da per una sola colonna);
• migliorare la funzione obiettivo;
• essere tale che è una soluzione ammissibile

In termini di matrici si scambia una colonna fuori base con una colonna di base.

In termini di vettori entra in base ed esce

Criterio di Entrata

Criterio di Entrata

Entra in base una variabile con costo ridotto negativo.

Supponiamo che entri in base una variabile , allora la f.o. diventa:

Dove è il costo ridotto della variabile entrata. Se la variabile entra in base, questa passa da un valore zero (dato che era fuori base) ad un valore positivo. Le altre variabili fuori base restano sempre a zero. Però ha effetto sulle variabili di base:

Le componenti di base dunque diventano:

• Se tutti gli sono , allora può aumentare senza limiti e le sono ancora ammissibili;
• Se aumenta all’infinito la f.o. va a , cioè:

Stabiliamo quindi il test di limitatezza:

Test di Limitatezza

Se c’è un costo ridotto e gli elementi della colonna sono allora il problema non è limitato. 

Se non è valido il test di illimitatezza bisogna cambiare vertice. Occorre scegliere quale variabile fare uscire dalla base.

Riferendoci al sistema delle componenti di base definito prima, vogliamo che

Otteniamo dunque:

Che significa?

Tutto questo significa che può crescere fino al raggiungere il minimo tra tutti i rapporti. O, in altre parole:

Criterio di Uscita (del Rapporto)

Criterio di Uscita

Esce dalla base la variabile dove è l’indice cui corrisponde il minimo dei rapporti.

La funzione migliora del valore , e la variabile entra con valore .

Questo valore è infatti il valore additivo , visto nel criterio di entrata.

Schema del Metodo del Simplesso

Preparati, da qui in poi partono gli esempi grafici.

Innanzitutto, si considera la Forma Standard del problema:

1. Si sceglie una base B (matrice con Det. ), e si calcola la soluzione di base
2. Se i costi ridotti delle variabili fuori base sono , la soluzione è ottima (Test di Ottimalità)
3. Se c’è un costo ridotto , quindi negativo (per il criterio di entrata), e gli elementi della colonna della matrice sono , il problema non è limitato (Test di Illimitatezza)
4. Si calcola:
   • e sia raggiunto per (Criterio di uscita)
5. Si cambia base:

Cambio Base: Operazione Pivotale

Adottiamo la forma Tableau del metodo del simplesso:

Tableau simplesso

Soluzione Base Ammissibile (SAB) corrente:

• Se entra la variabile ,
• Se il criterio di uscita ha indicato l’indice , esce la variabile

Dunque la colonna entra nella matrice di Base al posto della colonna .

L’elemento si chiama o perno della trasformazione, e deve essere sempre . 

La colonna h-esima si trasforma nella colonna k-esima con le seguenti operazioni:

Operazioni di trasformazione colonna

1. La riga si divide per il perno (motivo della condizione );
2. Alle altre righe si aggiunge un opportuno multiplo della riga del perno modificata in modo da annullare tutti gli elementi

Esempio in LateX

Si porta il problema in forma standard

Abbiamo aggiunto una base B con le variabili di scarto: sono variabili di base, e la matrice B in questo caso è una matrice identità. 

Questo perché se i vincoli sono tutti le variabili scarto diventano variabili di base.

La SAB Corrente sarà:

• Ricordiamo che , in notazione vettoriale, dove vettore delle componenti in base, mentre sarebbe il vettore delle componenti fuori base
• Se le componenti di base della SAB sono i termini noti.

Inoltre, se i vincoli sono tutti di tipo i costi ridotti coincidono con i coefficienti delle variabili della f.o. 

• Notiamo che ci sono 2 costi ridotti negativi. In questo caso, il criterio d’entrata sceglie quello con indice minore (cioè quello trovato prima). Questa scelta è definita dalla Regola di Bland.
• Per la variabile uscente, usiamo il criterio del rapporto. In questo caso calcoliamo:
• Il rapporto minimo è pertanto in corrispondenza della seconda riga, cioè della variabile , la variabile uscente.
• In sunto: Entra , Esce , l’incrocio tra la colonna della variabile entrante e la riga di quella uscente

Operazioni sulle righe

La colonna 2 deve dividere la colonna 5.

Procedura

1. Il perno vale 1, quindi non ci sono modifiche da fare.
   1. Se fosse , bisognerebbe dividere tutta la riga del perno per il perno stesso.
2. Operiamo sull’ultima riga, generiamo una nuova riga

3. Il costo ridotto della nuova variabile di base deve fare zero:

La nuova tabella, con relativa nuova SAB, sarà quindi:

Dato che abbiamo ancora un costo ridotto negativo (), si continua con l’algoritmo.

• Entra , ed esce
• Si hanno le seguenti trasformazioni:

Otteniamo un’altra tabella e nuova SAB:

Purtroppo dai calcoli abbiamo un nuovo costo negativo in , per cui:

• Entra , ed esce , perché ha il rapporto minimo rispetto alla riga
• E si hanno le seguenti trasformazioni:
• Reminder: finora non è stato necessario toccare la riga del pivot perché abbiamo avuto fortuna e tutti i pivot sono , altrimenti avremmo dovuto dividere per il pivot.

Otteniamo la tabella finale con SAB ottima:

• Questa è la tabella finale perché tutti i costi ridotti sono , quindi ci fermiamo per il Test di Ottimalità.
• Il valore ottimo della funzione obiettivo è dunque .

Questo conclude l’esempio.

• Nel caso in cui i costi ridotti siano tutti strettamente positivi (), allora per Unicità della soluzione, la SAB corrente sarebbe l’unica soluzione ottima.

Convergenza del Metodo

Continua in:

Convergenza del Metodo

Link to original

Convergenza del Metodo

Convergenza del Metodo

Se nelle iterazioni del metodo si generano soluzioni di base non degenere (cioè con componenti di base ), allora la funzione obiettivo migliora ad ogni iterazione. Dopo un numero finito di iterazioni, il metodo si arresta. 

Se si incontrano delle soluzioni di base degeneri, allora può accadere di rimanere bloccati su un vertice. 

Risulta che data una base B si costruisce una soluzione di base .  

Una soluzione di base degenere (con componenti di base ) invece proviene da più basi.  

Se ci sono soluzioni di base degeneri non è garantito che sia senza ripetizioni. Cioè il metodo cicla, tornando su basi già visitate.

Riassumento

• Soluzioni di base non degenere proviene da una sola base (e ha componenti di base )
• Soluzioni di base degenere proviene da più basi (e ha componenti di base )

Regola di Bland

Si usa per evitare di ciclare. 

Se c’è indecisione sulla variabile entrante, (cioè ci sono più costi ridotti negativi), oppure sulla variabile uscente (cioè ci sono più rapporti minimi uguali), si sceglie sempre l’indice minimo.

Complessità

, nel caso medio è lineare in o in . Il numero delle iterazioni è circa .

Nel caso peggiore si ottiene un ipercubo di dimensione , in cui occorre visitare tutti i vertici per trovare l’ottimo.

Questo risulta in iterazioni necessarie per arrivare al vertice ottimo.

Unicità Soluzione

Se i costi ridotti delle variabili fuori base sono tutti strettamente positivi, allora la soluzione di base corrente è l’unica soluzione ottima.

Esempio 1

Vediamo direttamente la tabella finale.  

Si potrebbe pensare di ‘forzare’ il metodo facendo entrare in base , considerando il costo ridotto nullo. 

Ma gli elementi della colonna sono e quindi questo significa che il problema ha soluzioni ottime.

Generalmente risulta che sono ottimi […Scrittura incomprensibile… 😒] i punti della semiretta che ha origine nel vertice ottimo.

Esempio con Base Degenere

[Grafica WIP che non verrà mai fatta probably, lungo e poco utile da vedere]

Restiamo bloccati in un vertice.

In generale una soluzione di base degenere è una intersezione di vincoli dove è la dimensione del problema. Inoltre, di solito nei vertici vicini la f.o. avrà valore ‘meno ottimo’ rispetto al vertice di intersezione dove restiamo bloccati.

Link to original

Metodo delle Due Fasi

Metodo delle Due Fasi

Quando si applica?

Il metodo delle due fasi si applica a problemi di PL con vincoli misti () nei quali non è possibile trovare come base la matrice identità.

Se non c’è la matrice identità, è impossibile avviare il simplesso infatti.

Consiste, appunto, di due fasi:

1. Determina una soluzione di base ammissibile e la forma canonica;
2. Risolvi il problema di PL.

Nella fase 1 si risolve un problema detto Artificiale.

Consideriamo un problema di PL in Forma Standard che non ha la sottomatrice identità:

Aggiungiamo ad ogni vincolo una variabile detta artificiale.

Nella fase si risolve il problema artificiale:

Una soluzione del problema artificiale è del tipo:

Se è soluzione di Base ammissibile del problema iniziale!

Supponiamo di aver risolto il problema della fase, per andare avanti con la teoria. 

Otterremmo:

=valore ottimo=

A questo punto ci sono due casi:

1. vuol dire che qualche allora si conclude che il problema iniziale non ha soluzione ammissibile. La regione ammissibile del problema è dunque vuota.
2. La soluzione finale della fase è tale che è una soluzione di base ammissibile per il problema iniziale.

Quando si passa alla fase si usa la tabella finale della fase e si ricalcolano i costi ridotti, perché si riprende la funzione obiettivo del problema iniziale.

Ci sono 2 ulteriori sottocasi:

1. Non ci sono variabili artificiali in base. Si cancellano nella tabella le colonne delle variabili artificiali, e si risolve il problema.
2. Ci sono variabili artificiali in base. Restano in base anche nella fase 2, e si cerca di farle uscire dalla base con il metodo del simplesso. Se non si riesce, vuol dire che il vincolo associato alle variabili artificiali in base è ridondante, e si può eliminare.

Esempio

Fase 1

Consideriamo un problema con soli vincoli di uguaglianza, ma senza matrice identità.

(direttamente in forma standard perché mi secco a ricopiare)

Applichiamo la fase: creiamo un problema artificiale sostituendo la funzione obiettivo, e aggiungendo le variabili artificiali (che si comportano come variabili scarto):

Otteniamo la matrice:

Nota Bene

Se si usano le variabili artificiali in ogni riga i costi ridotti delle variabili fuori base sono dati dall’OPPOSTO della somma per colonna.

Calcoliamo i costi ridotti con la formula , che tradotto dal matematichese significa:

• Costo Ridotto = Coeff. Variabili nella f.o. - coeff. variabili base f.o. colonna corrente.

 

Per cui il valore corrente della f.o. è: -vettore coeff. variabili base nella f.o. colonna termini noti:

  Entra in base , esce .

Dopo alcune iterazioni, otteniamo la tabella finale:

Dato che , si può passare alla fase.

Notiamo che la soluzione di base trovata in questo caso è: , ed il vettore è una SAB ammissibile per il problema iniziale.

Nota Bene

La prima fase si conclude in uno dei due sottocasi:

1. Problema iniziale inammissibile
2. Fornisce una SAB Ammissibile per il problema iniziale (forma canonica per avviare la risoluzione del problema)

Fase 2

Questa fase risolve il problema iniziale partendo dalla soluzione di base ammissibile trovata alla fine della prima fase: 

Notiamo che non sono in base, e si può eliminare pure in quanto vincolo ridondante (sia colonna che riga) (è ridondante perché l’equazione che rappresenta la riga equivale a 0) 

Ottenuta questa tabella si riprende la funzione obiettivo originale:

I valori dei costi ridotti e della funzione obiettivo sono a questo punto:

Vettore

• 0
• 0

Dopo altri svariati calcoli e un’altra iterazione, arriviamo alla SAB ottima: , con valore ottimo

Fin 💖

Link to original

Dualità

Dualità

La teoria della dualità permette di:

• Introdurre nuovi metodi risolutivi;
• Effettuare analisi di problemi di ottimalità

Dato un problema di PL detto PRIMALE, si associa ad esso un altro problema di PL detto primale:

La conversione avviene secondo le regole stabilite dalla:

Tabella Primale Duale

Primale	Duale
min	max
num. variabili	num. vincoli
num. vincoli	num. variabili
coeff f.o.	termini noti
termini noti	coeff f.o.
i-esimo vincolo
i-esimo vincolo
i-esimo vincolo	libera
	j-esimo vincolo
	j-esimo vincolo
libera	j-esimo vincolo
NB: Il Duale del Duale coincide col Primale

Link to original

Esempio

Problemi duali

Una coppia di problemi duali si dice simmetrica se è del tipo:

Se il primale è in Forma Standard si hanno problemi asimmetrici.

Relazioni Problemi Primali-Duali

Teorema della Dualità debole

Siano dati i problemi:

 

E sia ammissibile per (P) e ammissibile per (D).

Allora

Significato:

Teorema della Dualità debole

• La funzione obiettivo primale è un upper bound per il valore ottimo duale;
• La funzione obiettivo duale è un lower bound per il valore ottimo primale;

Corollario 1

Se è ammissibile per (P) e ammissibile per (D) e allora è ottimo per (P), e è ottimo per (D)

Corollario 2: Relazione Illimitato ←> Inammissibile

• Se (P) è illimitato (D) è inammissibile;
• Se (D) è illimitato (D) è inammissibile.

Riassunto dei possibili casi in una tabella:

Primale\Duale	Ottimo Finito	Illimitato	Inammissibile
Ottimo Finito
Illimitato
Inammissibile

Teorema della Dualità Forte

Teorema della dualità forte

Se uno dei due problemi primale o duale ha ottimo finito allora anche l’altro ha ottimo finito, e i valori ottimi delle funzioni obiettivo coincidono. Se uno dei due problemi è illimitato, l’altro è inammissibile.

Relazione Ottimalità Primale < - > Ammissibilità Duale

Leggi dopo aver letto:

Scarti Complementari

Scarti Complementari

Scarti Complementari

Siano dati i problemi primale-duale:

Siano ammissibile per (P) e ammissibile per (D).

sono soluzioni ottime soddisfano le condizioni:

• relazioni
• relazioni

Abbiamo un sistema di equazioni.

Condizioni di ottimalità (nella dualità)

1. Ammissibilità Primale Vincoli Primali
2. Ammissibiltà Duale Vincoli Duali

Oppure, sono ottimi valgono:

 

e anche: 

Che significa tutto questo, e soprattutto a che serve? Capiamolo con degli esempi.

(Se stai pensando di skipparlo: è capitato non solo alle prove in itinere, ma anche durante gli orali.)

Esempio

Esempio (Scarti Complementari):

Un utilizzo degli scarti complementari è di calcolare la soluzione ottima duale, data la soluzione ottima primale (0,6).

Potremmo arrivarci con il simplesso o con qualsiasi altro metodo, ma l’idea è quella di evitare di impostare l’algoritmo

Dato il problema Primale con soluzione (0,6):

Scriviamo il problema duale:

A questo punto creiamo il sistema di scarti complementari:

Abbiamo:

• con 3 equazioni in y,
• =0 con 2 equazioni in x.

Dobbiamo vedere quali equazioni ci danno ‘informazioni’ sulla soluzione duale.

Dato che abbiamo la SOLUZIONE PRIMALE, sostituiamo

Questo si traduce in:

Troviamo la soluzione duale: .

Perciò data la funzione obiettivo duale: , avremo l’ottimo

Non è garantito avere un sistema così pulito. Ad esempio, nella prova in itinere dell’A.A. 2023/24 è capitato un sistema molto più complesso dove l’informazione su una variabile andava presa facendo coincidere la con la . Non molto divertente.

Link to original

Sia la soluzione ottima primale e la soluzione ottima duale.

Risulta , cioè coincidono i valori ottimi.

deve soddisfare i vincoli duali, cioè:

Sostituendo con otteniamo la dimostrazione, e arriviamo al risultato che , che è la condizione di ottimalità primale.

Per cui la Ottimalità Primale COINCIDE con l’Ammissibilità Duale (importantissimo per Simplesso Duale).

Calcolo Soluzione Duale

Possiamo usare:

1. Scarti Complementari;
2. Tabella simplesso del problema primale.

Se il problema primale ha vincolo si utilizzano le variabili scarto per la Forma Standard.

La soluzione ottima si ottiene:

, dove:

• vettore coefficienti della f.o. associati alle variabili in base alla iterazione;
• vettore dei costi ridotti nella tabella finale del simplesso associati alle variabili in base alla iterazione.

Esempio Veloce

Dato un problema del tipo:

Eseguendo il metodo del simplesso otterremo la soluzione ottima primale:

con e valore ottimo

e costi ridotti finali:

Calcolando la soluzione duale con la formula definita subito sopra l’esempio abbiamo:

, che è la soluzione ottima duale.

Osservazione

Se il problema primale ha vincoli la soluzione ottima duale sarà la sottrazione inversa rispetto a quella appena eseguita, cioè:

Simplesso Duale

Si tratta di un metodo per risolvere il problema di PL primale nel caso in cui non sia valida l’ammissibilità primale (cioè ci sono termini noti negativi nella Forma Standard), ma sia verificata l’ammissibilità duale (cioè i costi ridotti delle variabili fuori base sono ).

Il metodo parte da una soluzione di base non ammissibile, cioè esterna al poliedro, e cerca di raggiungere la soluzione ottima.

Ad ogni iterazione i costi ridotti sono sempre e si cerca di avere tutti i termini noti

Per riassumere:

Simplesso Primale	Simplesso Duale
Condizioni: Termini Noti	Condizioni: C’è almeno un termine noto negativo; Costi ridotti
Obiettivo: Costi Ridotti	Obiettivo: Termini Noti

Criterio di Uscita

Esce dalla base la variabile associata al termine noto negativo

Si individua la riga , se gli elementi della riga sono TUTTI PROBLEMA PRIMALE INAMMISSIBILE 

Criterio di non ammissibilità

Se il primale è inammissibile il duale potrebbe essere non limitato o non ammissibile. 

Poichè vale la condizione di ammissibilità duale allora il problema duale non è limitato

Se ci sono elementi negativi sulla riga si individua la variabile uscente , dove è l’indice di colonna tale che

Criterio di Entrata

Resta individuato il pivot della trasformazione.

Riassumendo di nuovo:

Simplesso Primale	Simplesso Duale
Costo ridotto dà la variabile entrante	Termine noto dà la variabile uscente
Criterio Rapporto per la variabile uscente	Criterio rapporto per la variabile entrante
Criterio illimitatezza: Elementi colonna con costo ridotto negativo	Criterio di inammissibilità: Elementi riga associati ad un termine noto
Ottimalità: Costi ridotti	Ottimalità: Termini noti

Analisi di Post-Ottimalità

Supponiamo di causare la perturbazione di un termine noto

La soluzione di ottima di base è ,

Sia

(B^{-1}b,0) è ancora ottima?

Caso 1: ha componenti negative Non vale l’ammissibilità primale. 

I costi ridotti non hanno il vettore , quindi i costi ridotti sono ancora

(e sono perché è soluzione ottima).

Possiamo applicare il simplesso duale per calcolare la nuova soluzione ottima.

Caso 2: ha componenti è ammissibile

Link to original

Link to original

Tabella Primale Duale

Primale	Duale
min	max
num. variabili	num. vincoli
num. vincoli	num. variabili
coeff f.o.	termini noti
termini noti	coeff f.o.
i-esimo vincolo
i-esimo vincolo
i-esimo vincolo	libera
	j-esimo vincolo
	j-esimo vincolo
libera	j-esimo vincolo
NB: Il Duale del Duale coincide col Primale

Link to original

Scarti Complementari

Scarti Complementari

Siano dati i problemi primale-duale:

Siano ammissibile per (P) e ammissibile per (D).

sono soluzioni ottime soddisfano le condizioni:

• relazioni
• relazioni

Abbiamo un sistema di equazioni.

Condizioni di ottimalità (nella dualità)

1. Ammissibilità Primale Vincoli Primali
2. Ammissibiltà Duale Vincoli Duali

Oppure, sono ottimi valgono:

 

e anche: 

Che significa tutto questo, e soprattutto a che serve? Capiamolo con degli esempi.

(Se stai pensando di skipparlo: è capitato non solo alle prove in itinere, ma anche durante gli orali.)

Esempio

Esempio (Scarti Complementari):

Un utilizzo degli scarti complementari è di calcolare la soluzione ottima duale, data la soluzione ottima primale (0,6).

Potremmo arrivarci con il simplesso o con qualsiasi altro metodo, ma l’idea è quella di evitare di impostare l’algoritmo

Dato il problema Primale con soluzione (0,6):

Scriviamo il problema duale:

A questo punto creiamo il sistema di scarti complementari:

Abbiamo:

• con 3 equazioni in y,
• =0 con 2 equazioni in x.

Dobbiamo vedere quali equazioni ci danno ‘informazioni’ sulla soluzione duale.

Dato che abbiamo la SOLUZIONE PRIMALE, sostituiamo

Questo si traduce in:

Troviamo la soluzione duale: .

Perciò data la funzione obiettivo duale: , avremo l’ottimo

Non è garantito avere un sistema così pulito. Ad esempio, nella prova in itinere dell’A.A. 2023/24 è capitato un sistema molto più complesso dove l’informazione su una variabile andava presa facendo coincidere la con la . Non molto divertente.

Link to original

Simplesso Duale

Si tratta di un metodo per risolvere il problema di PL primale nel caso in cui non sia valida l’ammissibilità primale (cioè ci sono termini noti negativi nella Forma Standard), ma sia verificata l’ammissibilità duale (cioè i costi ridotti delle variabili fuori base sono ).

Il metodo parte da una soluzione di base non ammissibile, cioè esterna al poliedro, e cerca di raggiungere la soluzione ottima.

Ad ogni iterazione i costi ridotti sono sempre e si cerca di avere tutti i termini noti

Per riassumere:

Simplesso Primale	Simplesso Duale
Condizioni: Termini Noti	Condizioni: C’è almeno un termine noto negativo; Costi ridotti
Obiettivo: Costi Ridotti	Obiettivo: Termini Noti

Criterio di Uscita

Esce dalla base la variabile associata al termine noto negativo

Si individua la riga , se gli elementi della riga sono TUTTI PROBLEMA PRIMALE INAMMISSIBILE 

Criterio di non ammissibilità

Se il primale è inammissibile il duale potrebbe essere non limitato o non ammissibile. 

Poichè vale la condizione di ammissibilità duale allora il problema duale non è limitato

Se ci sono elementi negativi sulla riga si individua la variabile uscente , dove è l’indice di colonna tale che

Criterio di Entrata

Resta individuato il pivot della trasformazione.

Riassumendo di nuovo:

Simplesso Primale	Simplesso Duale
Costo ridotto dà la variabile entrante	Termine noto dà la variabile uscente
Criterio Rapporto per la variabile uscente	Criterio rapporto per la variabile entrante
Criterio illimitatezza: Elementi colonna con costo ridotto negativo	Criterio di inammissibilità: Elementi riga associati ad un termine noto
Ottimalità: Costi ridotti	Ottimalità: Termini noti

Analisi di Post-Ottimalità

Supponiamo di causare la perturbazione di un termine noto

La soluzione di ottima di base è ,

Sia

(B^{-1}b,0) è ancora ottima?

Caso 1: ha componenti negative Non vale l’ammissibilità primale. 

I costi ridotti non hanno il vettore , quindi i costi ridotti sono ancora

(e sono perché è soluzione ottima).

Possiamo applicare il simplesso duale per calcolare la nuova soluzione ottima.

Caso 2: ha componenti è ammissibile

Link to original

---

Programmazione Lineare Intera

Problemi di Ottimizzazione Lineare Intera

Programmazione Lineare Intera

Consideriamo problemi del tipo:

Problema PLI

Osservazione

Osservazione

La regione ammissibile di un problema intero non è convessa. In generale possono esservi alcune variabili continue e alcune intere. Si parla in tal caso di PLI mista (che non trattiamo)

Esempio

Esempio Grafico PLI

Se risolviamo il problema senza vincolo di interezza, l’ottimo sarebbe .

Altrimenti:

• Soluzione ottima intera:
• Soluzione arrotondata:

Come è ovvio vedere, non è possibile risolvere il problema intero eliminando il vincolo di interezza e risolvendo il problema continuo approssimando la soluzione.

Bisogna necessariamente risolvere il problema intero.

Relazioni problemi lineari < - > interi

Rilassamento Lineare

Dato un problema PLI (definito sopra), è possibile ottenere un Rilassamento Lineare (RL), o continuo:

• Risulta che , cioè la regione ammissibile del problema di PLI è data dalla soluzione intera del poliedro P.

• Inoltre , cioè la reigone ammissibile del problema PLI è sempre contenuta nel poliedro P.

Si ha che il valore ottimo di (RL) è sempre del valore ottimo di (PLI):

Infine:

Se la soluzione ottima di (RL) è intera è soluzione del problema (PLI).

Involucro Convesso

Dato un insieme discreto, esistono diversi poliedro che lo contengono. Il poliedro più interessante è l’Involucro Convesso (Convex Hull), e cioè il più piccolo insieme convesso che contiene i punti discreti.

L’involucro convesso ha solo vertici interi, si potrebbe quindi risolvere il problema continuo usando l’involucro convesso come insieme dei vincoli:

Il problema da risolvere è detto Rilassamento Convessificato e si ottiene la soluzione intera cercata.

In generale però, non è facile costruire . Servono dei metodi per costruirlo.

Metodo dei piani di taglio (Generico)

Metodo dei piani di taglio

Consideriamo il problema intero di prima:

Taglio

Sia una disuguaglianza verificata , essa si chiama Taglio se non è verificata dalla soluzione ottima del (RL)

Gli algoritmi dei piani di taglio risolvono una successione di problemi continui, ottenuti aggiungendo ogni volta un taglio, fino ad ottenre una soluzione intera.

Schema Generale:

1. Si risolve il (RL), se è intera
2. Si genera un taglio (nuovo vincolo!)
   • Tale che
   • Significa: Il taglio è verificato da tutti i punti interi, ma non è soddisfatto dall’ottimo del rilassamento continuo.
3. Si risolve il nuovo problema continuo con l’aggiunta del nuovo vincolo

Procedimento ed Efficienza

È un processo molto lungo ed estenuante da fare a mano, per questo in teoria esistono i computer, che possono operare più tagli contemporaneamente per migliorare l’efficienza, ma noi siamo studenti universitari e quindi abbiamo meno diritti delle macchine.

A seconda della scelta del taglio si hanno diversi algoritmi, ma resta comunque l’idea comune di fondo di approssimare l’involucro convesso mediante l’inserimento dei tagli.

Implementazioni:

Una implementazione è il Metodo dei Tagli di Gomory.

Link to original

Metodo di Gomory (Implementazione piani di taglio)

Metodo dei Tagli di Gomory

Schema Generale:

1. Si risolve il (RL), se è intera
2. Si genera un taglio (nuovo vincolo!)
   • Tale che
   • Significa: Il taglio è verificato da tutti i punti interi, ma non è soddisfatto dall’ottimo del rilassamento continuo.
3. Si risolve il nuovo problema continuo con l’aggiunta del nuovo vincolo

Procedimento ed Efficienza

È un processo molto lungo ed estenuante da fare a mano, per questo in teoria esistono i computer, che possono operare più tagli contemporaneamente per migliorare l’efficienza, ma noi siamo studenti universitari e quindi abbiamo meno diritti delle macchine.

A seconda della scelta del taglio si hanno diversi algoritmi, ma resta comunque l’idea comune di fondo di approssimare l’involucro convesso mediante l’inserimento dei tagli.

Link to original

Metodo di Gomory

Genera il taglio sfruttando la tabella finale del Simplesso del Rilassamento Lineare (RL).

In particolare, usa la riga della tabella associata ad una componente frazionaria della soluzione ottima del (RL).

Sia data la tabella finale della risoluzione del RL:

— WIP

• è frazionario.

non è intero, supponiamo che non sia intero.

Procedimento

Scriviamo la riga esima:

e consideriamo i floor dei coefficienti:

Questo è il taglio di Gomory in forma intera.

Il taglio va aggiunto al rilassamento lineare dopo averlo reso standard. Si aggiunge il vincolo standard:

Come precedentemente detto, la convergenza è lenta. I primi tagli risultano più efficaci, ma lo sono meno continuando ad iterare l’algoritmo.

Se si opera un taglio alla volta e ci sono più valori frazionari si sceglie sempre la riga con indice minore, oppure quella con termine noto che ha la parte frazionaria maggiore.

Esempio (Grafico, lungo)

EH, VOLEVI! wip.

Link to original

Link to original

Problema del trasporto

Link to original

Problema dell'assegnamento

Siano A e B due insiemi tali che e .

Sono dati dei costi agli abbinamenti tra gli elementi di e .

Il problema degli assegnamenti consiste nell’assegnare ad ogni elemento di A un solo elemento di in modo che non ci siano elementi non accoppiati e il costo totale sia minimo.

Se si aggiungono elementi fittizi e costi nulli degli abbinamenti con elementi fittizi.

Formulazione Matematica

È un particolare problema del trasporto con domanda e offerta = 1.

La matrice dei coefficienti è Totalmente Unimodulare

Matrice Unimodulare

Matrice Unimodulare

Una matrice si dice totalmente unimodulare quando ogni sottomatrice di ordine ha determinante

Proposizione

Dato il poliedro con A matrice tot. unimodulare, e b intero poliedro ha solo vertici interi

Possiamo quindi risolvere il problema rilassato con il vincolo (insieme agli altri vincoli diventa poi solo) )

Non è utile usare il simplesso perché il poliedro ha vertici fortemente degeneri, si usa infatti un algoritmo specifico:

Algoritmo Ungherese

Opera sulla matrice dei costi e trasforma la matrice dei costi in una serie di matrici equivalenti fino a determinare l’assegnamento di costo minimo che corrisponderà al ricoprimento degli zeri della matrice.

Operazioni

1. Si sottrae ad ogni riga il suo elemento minimo: (generiamo zeri sulle righe)
2. Si sottrae ad ogni colonna il suo elemento minimo: (generiamo zeri su colonne)
3. Si cerca l’assegnamento di costo minimo, cercando il ricoprimento degli zeri della matrice. Se il numero di righe e colonne che ricoprono gli zeri è minore del numero di righe della matrice, l’assegnamento non è completo e si deve ridurre ancora la matrice. Altrimenti, si è trovato l’assegnamento completo di costo minimo
4. Si barrano le righe e le colonne che ricoprono gli zeri. Sia l’elemento minimo non barrato. Si aggiunge agli elementi barrati 2 volte (cioè l’incrocio tra riga e colonna) e si sottrae agli elementi non barrati.

Si ripetono e fino a trovare l’assegnamento completo

Regola generale per trovare il ricoprimento minimo degli zeri

• Si etichettano le righe lasciate fuori dall’assegnamento;
• Si etichettano le colonne che hanno degli zeri in corrispondenza delle righe etichettate;
• Si etichettano le righe abbinate alle colonne etichettate dall’assegnamento ottenuto;
• Si barrano le righe non etichettate e le colonne etichettate.

Link to original

Assegnamento su Grafo Bipartito

Il problema dell’assegnamento si può vedere su un grafo bipartito completo. Siano noti i costi su tutti gl iarchi e si cerca un abbinamento tra gli elementi dei due insiemi di costo minimo.

Link to original

Metodo dei piani di taglio

Consideriamo il problema intero di prima:

Taglio

Sia una disuguaglianza verificata , essa si chiama Taglio se non è verificata dalla soluzione ottima del (RL)

Gli algoritmi dei piani di taglio risolvono una successione di problemi continui, ottenuti aggiungendo ogni volta un taglio, fino ad ottenre una soluzione intera.

Schema Generale:

1. Si risolve il (RL), se è intera
2. Si genera un taglio (nuovo vincolo!)
   • Tale che
   • Significa: Il taglio è verificato da tutti i punti interi, ma non è soddisfatto dall’ottimo del rilassamento continuo.
3. Si risolve il nuovo problema continuo con l’aggiunta del nuovo vincolo

Procedimento ed Efficienza

È un processo molto lungo ed estenuante da fare a mano, per questo in teoria esistono i computer, che possono operare più tagli contemporaneamente per migliorare l’efficienza, ma noi siamo studenti universitari e quindi abbiamo meno diritti delle macchine.

A seconda della scelta del taglio si hanno diversi algoritmi, ma resta comunque l’idea comune di fondo di approssimare l’involucro convesso mediante l’inserimento dei tagli.

Implementazioni:

Una implementazione è il Metodo dei Tagli di Gomory.

Link to original

Metodo dei Tagli di Gomory

Schema Generale:

1. Si risolve il (RL), se è intera
2. Si genera un taglio (nuovo vincolo!)
   • Tale che
   • Significa: Il taglio è verificato da tutti i punti interi, ma non è soddisfatto dall’ottimo del rilassamento continuo.
3. Si risolve il nuovo problema continuo con l’aggiunta del nuovo vincolo

Procedimento ed Efficienza

È un processo molto lungo ed estenuante da fare a mano, per questo in teoria esistono i computer, che possono operare più tagli contemporaneamente per migliorare l’efficienza, ma noi siamo studenti universitari e quindi abbiamo meno diritti delle macchine.

A seconda della scelta del taglio si hanno diversi algoritmi, ma resta comunque l’idea comune di fondo di approssimare l’involucro convesso mediante l’inserimento dei tagli.

Link to original

Metodo di Gomory

Genera il taglio sfruttando la tabella finale del Simplesso del Rilassamento Lineare (RL).

In particolare, usa la riga della tabella associata ad una componente frazionaria della soluzione ottima del (RL).

Sia data la tabella finale della risoluzione del RL:

— WIP

• è frazionario.

non è intero, supponiamo che non sia intero.

Procedimento

Scriviamo la riga esima:

e consideriamo i floor dei coefficienti:

Questo è il taglio di Gomory in forma intera.

Il taglio va aggiunto al rilassamento lineare dopo averlo reso standard. Si aggiunge il vincolo standard:

Come precedentemente detto, la convergenza è lenta. I primi tagli risultano più efficaci, ma lo sono meno continuando ad iterare l’algoritmo.

Se si opera un taglio alla volta e ci sono più valori frazionari si sceglie sempre la riga con indice minore, oppure quella con termine noto che ha la parte frazionaria maggiore.

Esempio (Grafico, lungo)

EH, VOLEVI! wip.

Link to original

Metodo del Branch and Bound

Metodo Branch and Bound

È un metodo molto utilizzato per risolvere problemi PLI.

Si basa sul partizionamento del poliedro del (RL). Si risolvono quindi i sottoproblemi (lineari) sugli insiemi della partizione.

Dato un problema PLI:

Problema PLI

Osservazione

Osservazione

La regione ammissibile di un problema intero non è convessa. In generale possono esservi alcune variabili continue e alcune intere. Si parla in tal caso di PLI mista (che non trattiamo)

Esempio

Esempio Grafico PLI

Se risolviamo il problema senza vincolo di interezza, l’ottimo sarebbe .

Altrimenti:

• Soluzione ottima intera:
• Soluzione arrotondata:

Come è ovvio vedere, non è possibile risolvere il problema intero eliminando il vincolo di interezza e risolvendo il problema continuo approssimando la soluzione.

Bisogna necessariamente risolvere il problema intero.

Relazioni problemi lineari < - > interi

Rilassamento Lineare

Dato un problema PLI (definito sopra), è possibile ottenere un Rilassamento Lineare (RL), o continuo:

• Risulta che , cioè la regione ammissibile del problema di PLI è data dalla soluzione intera del poliedro P.

• Inoltre , cioè la reigone ammissibile del problema PLI è sempre contenuta nel poliedro P.

Si ha che il valore ottimo di (RL) è sempre del valore ottimo di (PLI):

Infine:

Se la soluzione ottima di (RL) è intera è soluzione del problema (PLI).

Link to original

e il suo rilassamento lineare:

Rilassamento Lineare

Dato un problema PLI (definito sopra), è possibile ottenere un Rilassamento Lineare (RL), o continuo:

• Risulta che , cioè la regione ammissibile del problema di PLI è data dalla soluzione intera del poliedro P.

• Inoltre , cioè la reigone ammissibile del problema PLI è sempre contenuta nel poliedro P.

Si ha che il valore ottimo di (RL) è sempre del valore ottimo di (PLI):

Infine:

Se la soluzione ottima di (RL) è intera è soluzione del problema (PLI).

Link to original

Partizioniamo nei sottoinsiemi e risolviamo:

Il valore ottimo del problema (PLI) indicato con

Procedimento

Il metodo prevede di partizionare in maniera ricorsiva e risolvere i vari sottoproblemi e i rispettivi (RL).

Si partiziona ogni partizione fino a quando si trova una sol intera o un sottoproblema risulta inammissibile.

Il metodo individua anche le partizioni sulle quali non occorre risolvere il sottoproblema.

Non è un metodo di enumerazione totale.

Esempio (Grafico, WIP)

Non esploro la parte grigia

Descrizione del Metodo

Si basa su due operazioni:

• Bounding: Si risolve un (RL) del problema di (PLI) e si ottiene un lower bound per il valore ottimo intero;
• Branching: La soluzione fornita dal (RL) indica come effettuare il partizionamento

Sia la soluzione di non intera. avrà qualche componente frazionaria, che chiamiamo

Questa è detta variabile di branch, e genera due sottoproblemi:

Se ci sono più componenti frazionarie si può:

1. Scegliere quella con parte frazionaria più vicina a
2. Scegliere quella con coefficiente della più elevato.
   • Questo rende più probabile trovare la soluzione intera nel ramo e chiudere invece il ramo

Criteri di Potatura

Cioè criteri per chiudere nodi. Ne esistono 3:

1. Il vincolo di branch è incompatibile con i vincoli del problema, che risulta inammissibile;
2. Si trova una soluzione intera;
3. Chiusura per bounding: si risolve un sottoproblema lineare continuo che dà una soluzione non intera e il suo valore ottimo è peggiore del valore ottimo corrente del problema intero

Osservazione

Il branching può essere binario, ma anche di dimensioni maggiori, dipende dal problema.

Strategie di visita

Visita in Profondità (DFS)

Si risolve il primo figlio di ogni nodo, fino a quando non si deve risalire.

Minimizza il numero di nodi aperti da esplorare, e ha bassi requisiti di memoria. Inoltre, si ottiene rapidamente una soluzione intera.

Lo svantaggio è dovuto al fatto che si possono dover risolvere molti problemi (e quindi nodi da esplorare)

Visita per bound migliore

Si risolve prima il problema con valore ottimo migliore. Se minimizziamo, scegliamo il problema con lower bound inferiore.

In tal caso, si esplorano meno nodi, ma ne restano molti aperti. C’è maggiore richiesta di memoria, ed è possibile che se si arresta l’algoritmo prima non si trovi una soluzione intera.

Difatti, risulta più efficiente unire le due strategie:

• Si fissa il numero max di nodi aperti consentiti;
• Si applica il best bound;
• Raggiunto il limite di nodi aperti, si procede con l’esplorazione DFS.

Upper Bound

Un upper bound per il valore ottimo del problema intero si ottiene calcolando la nella prima soluzione intera disponibile.

Dato

Lower Bound	Upper Bound
Risolvendo i (RL)	Valore della f.o. calcolato in una sol. intera

Problema di Massimizzazione

I (RL) forniscono degli upper bound per il valore ottimo intero.

La f.o. dà invece un lower bound

Cioè il contrario di quanto detto prima.

Chiusura per Bounding

Come prima, se il valore ottimo ottenuto risolvendo un sottoproblema con soluzione non intera è minore del valore ottimo corrente si chiude il nodo.

Esplorazione per Best Bound

Si seglie il sottoproblema con ottimo maggiore.

Link to original

Problema dello Zaino

Sia un insieme di oggetti.

Ad ogni oggetto si associano un profitto e un peso , entrambi interi positivi.

Sia la capacità.

Problema dello Zaino

Consiste nello scegliere quali oggetti inserire nello zaino in modo da massimizzare il profitto, rispettando il vincolo sulla capacità.

Definizione Formale

Il problema fa parte dei problemi di riempimento.

Problema di Riempimento

Siano sottoinsiemi di e sia il profitto associato ad ogni .

Il problema di riempimento consiste nel determinare la sottofamiglia degli insiemi che sia di profitto massimo e tale che ogni elemento di appartenga al più ad un solo sottoinsieme di .

Approccio Euristico

Si costruisce una soluzione inserendo nello zaino per primi gli elementi migliori secondo un certo criterio.

Ci sono tre criteri:

1. Peso non decrescente (inseriamo molti oggetti)
2. Profitto non decrescente (inseriamo oggetti di maggior valore)
3. Rapporto profitto/peso decrescente (più efficace)

Comunque con questo approccio non si arriva all’ottimo

Metodo (esatto) Branch and Bound per lo zaino

Per applicare il Metodo del Branch and Bound dobbiamo specificare:

• Come ottenere l’upper bound
• Come fare branching
• Come ottenere un lower bound

Per l’operazione di bounding adottiamo l’eliminazione del vincolo di interezza (RL|), perciò risolviamo il problema di PL:

Si potrebbe usare il simplesso ma è più efficace un altro metodo.

Si sceglie il criterio di ordinamento decrescente.

Si ordinano gli oggetti secondo questo criterio e si inizia l’inserimento. Supponiamo che si possano inserire i primi oggetti, ma non l’oggetto

e

Inseriamo per intero i primi oggetti:

Mentre l’oggetto sarà inserito frazionalmente (in parte):

Lo zaino è pieno

Il valore ottimo è

infatti è detta variabile critica ed è la variabile di branch, che effettua la partizione.

Un Lower Bound si ottiene considerando come Soluzione Intera Ammissibile l’arrotondamento per difetto della soluzione del rilassamento lineare .

• Soluzione

• L’arrotondamento è:

• e il lower bound:

Come strategia si usa in genere il best bound.

Esempio (WIP)

Link to original

Problema dell'assegnamento

Siano A e B due insiemi tali che e .

Sono dati dei costi agli abbinamenti tra gli elementi di e .

Il problema degli assegnamenti consiste nell’assegnare ad ogni elemento di A un solo elemento di in modo che non ci siano elementi non accoppiati e il costo totale sia minimo.

Se si aggiungono elementi fittizi e costi nulli degli abbinamenti con elementi fittizi.

Formulazione Matematica

È un particolare problema del trasporto con domanda e offerta = 1.

La matrice dei coefficienti è Totalmente Unimodulare

Matrice Unimodulare

Matrice Unimodulare

Una matrice si dice totalmente unimodulare quando ogni sottomatrice di ordine ha determinante

Proposizione

Dato il poliedro con A matrice tot. unimodulare, e b intero poliedro ha solo vertici interi

Possiamo quindi risolvere il problema rilassato con il vincolo (insieme agli altri vincoli diventa poi solo) )

Non è utile usare il simplesso perché il poliedro ha vertici fortemente degeneri, si usa infatti un algoritmo specifico:

Algoritmo Ungherese

Opera sulla matrice dei costi e trasforma la matrice dei costi in una serie di matrici equivalenti fino a determinare l’assegnamento di costo minimo che corrisponderà al ricoprimento degli zeri della matrice.

Operazioni

1. Si sottrae ad ogni riga il suo elemento minimo: (generiamo zeri sulle righe)
2. Si sottrae ad ogni colonna il suo elemento minimo: (generiamo zeri su colonne)
3. Si cerca l’assegnamento di costo minimo, cercando il ricoprimento degli zeri della matrice. Se il numero di righe e colonne che ricoprono gli zeri è minore del numero di righe della matrice, l’assegnamento non è completo e si deve ridurre ancora la matrice. Altrimenti, si è trovato l’assegnamento completo di costo minimo
4. Si barrano le righe e le colonne che ricoprono gli zeri. Sia l’elemento minimo non barrato. Si aggiunge agli elementi barrati 2 volte (cioè l’incrocio tra riga e colonna) e si sottrae agli elementi non barrati.

Si ripetono e fino a trovare l’assegnamento completo

Regola generale per trovare il ricoprimento minimo degli zeri

• Si etichettano le righe lasciate fuori dall’assegnamento;
• Si etichettano le colonne che hanno degli zeri in corrispondenza delle righe etichettate;
• Si etichettano le righe abbinate alle colonne etichettate dall’assegnamento ottenuto;
• Si barrano le righe non etichettate e le colonne etichettate.

Link to original

Assegnamento su Grafo Bipartito

Il problema dell’assegnamento si può vedere su un grafo bipartito completo. Siano noti i costi su tutti gl iarchi e si cerca un abbinamento tra gli elementi dei due insiemi di costo minimo.

Link to original

Algoritmo Ungherese

Opera sulla matrice dei costi e trasforma la matrice dei costi in una serie di matrici equivalenti fino a determinare l’assegnamento di costo minimo che corrisponderà al ricoprimento degli zeri della matrice.

Operazioni

1. Si sottrae ad ogni riga il suo elemento minimo: (generiamo zeri sulle righe)
2. Si sottrae ad ogni colonna il suo elemento minimo: (generiamo zeri su colonne)
3. Si cerca l’assegnamento di costo minimo, cercando il ricoprimento degli zeri della matrice. Se il numero di righe e colonne che ricoprono gli zeri è minore del numero di righe della matrice, l’assegnamento non è completo e si deve ridurre ancora la matrice. Altrimenti, si è trovato l’assegnamento completo di costo minimo
4. Si barrano le righe e le colonne che ricoprono gli zeri. Sia l’elemento minimo non barrato. Si aggiunge agli elementi barrati 2 volte (cioè l’incrocio tra riga e colonna) e si sottrae agli elementi non barrati.

Si ripetono e fino a trovare l’assegnamento completo

Regola generale per trovare il ricoprimento minimo degli zeri

• Si etichettano le righe lasciate fuori dall’assegnamento;
• Si etichettano le colonne che hanno degli zeri in corrispondenza delle righe etichettate;
• Si etichettano le righe abbinate alle colonne etichettate dall’assegnamento ottenuto;
• Si barrano le righe non etichettate e le colonne etichettate.

Link to original

Problema del Commesso viaggiatore

Branch and Bound per il problema del TSP Asimmetrico

Sia dato un grafo orientato, il problema del commesso viaggiatore (TSP) consiste nel determinare un Ciclo Hamiltoniano di costo minimo.

Ciclo Hamiltoniano

Si ha un ciclo hamiltoniano quando in un cammino hamiltoniano esiste un arco che collega l’ultimo vertice con il primo, realizzando così un ciclo che visita tutti i vertici per poi ritornare al punto di partenza.

Link to original

Quindi, assegnati dei costi agli archi, si vuole determinare il ciclo che tocchi ogni nodo di G una e una sola volta e che abbia costo minimo

Formulazione Matematica TSP

Per applicare il Metodo del Branch and Bound al TSP dobbiamo capire, anche qui:

• Come ottenere l’upper bound
• Come fare branching
• Come ottenere un lower bound

Troviamo un lower bound, eliminando i vincoli sui sottocicli.

Così otteniamo il Problema dell’assegnamento.

L’assegnamento si opera sul grafo bipartito completo che si ottiene duplicando i nodi di G.

Se l’assegnamento dà un ciclo hamiltoniano, abbiamo la soluzione del TSP.

Altrimenti, vuol dire che ci sono dei sottocicli Li possiamo usare per il branching. La dimensione del branching sarà pari alla cardinalità minima dei sottocicli.

Dalla soluzione dell’assegnamento, prendiamo il sottociclo di cadinalità minima e generiamo tanti problemi quanti sono gli archi di tale sottociclo.

Regola Generale TSP

Dato il sottociclo

Si generano i vincoli di branching imponendo per il primo figlio , per il secondo figlio , e così via fino al figlio k-esimo, per il quale tutti i precedenti saranno 1 e per se stesso 0.

Imporre che vuol dire richiedere che nella matrice dei costi

Upper Bound

Si determina con l’algoritmo del nodo più vicino.

Si parte dal primo nodo e si cerca il nodo successivo connesso con costo minimo.

Esaminati tutti i nodi si trova un ciclo hamiltoniano.

Link to original

---

Programmazione Non Lineare

Programmazione Non Lineare

Programmazione non lineare

Nei problemi di ottimizzazione non lineare la funzione obiettivo e/o le funzioni dei vincoli sono non lineari. Esistono alcuni problemi non lineari che possono essere trasformati in problemi lineari

In generale però, i problemi non lineari restano tali e si affrontano con determinati metodi. Possono essere di due tipi:

• Se il problema si dice non vincolato.
• Se Il problema si dice vincolato:

Si pone sempre , altrimenti l’insieme potrebbe risultare vuoto, oppure potrebbero esserci vincoli ridondanti.

I problemi non vincolati sono problemi in cui effettivamente l’insieme ammissibili coincide con tutto lo spazio.

Nelle applicazioni sono considerati non vincolati i problemi con insieme ammissibile aperto.

In tal caso infatti i punti di ottimo sono interni e possono essere caratterizzati solo dall’andamento della funzione obiettivo.

Problemi non vincolati

Sia dato un problema di PNL non vincolata:

Una soluzione locale deve soddisfare una condizione necessaria di ottimalità. Si osserva che i punti che soddisfano una condizione necessaria di ottimalità non sono forzatamente soluzioni del problema: potrebbero ad esempio essere di max e non di minimo

Condizioni di Ottimalità

Condizioni Necessarie e Sufficienti

• Una condizione necessaria puo servire a restringere l’insieme di punti in cui cercare la soluzione e a costruire algoritmi che soddisfano la condizione necessaria.

• Una condizione sufficiente puo servire a dimostrare che un punto ottenuto per via numerica sia una soluzione ottima

Condizione Necessaria del Primo Ordine

Teorema

Sia un punto di minimo locale. Se è differenziabile in , allora in

La condizione necessaria fornisce i punti stazionari candidati ad essere punti minimali.

Se il problema è convesso, la condizione diventa necessaria e sufficiente.

Condizione Sufficiente del Secondo Ordine

Teorema

Sia un punto di minimo locale. Se è differenziabile due volte in , allora in e la matrice hessiana è semidefinita positiva

Condizione Necessaria del Secondo Ordine

Sia un punto interno della regione ammissibile e , e differenziabile due volte in :

• Se la matrice hessiana è definita positiva, allora è punto di minimo locale;
• Se la matrice hessiana è definita negativa allora è punto di massimo locale;
• Se la matrice hessiana è indefinita, allora è un punto di sella
• Se la matrice hessiana è semidefinita non si può dire niente

Regolarità dei vincoli di uguaglianza

Condizione di Ottimalità del primo ordine

Forma Equivalente

Funzione Lagrangiana

Link to original

Problemi con vincoli di uguaglianza e disuguaglianza

Regolarità dei vincoli

Condizioni KKT

Condizioni di ottimalità del primo ordine-KKT

Teorema: Condizioni di Karush-Kuhn-Tucker

Funzione Lagrangiana

Schema Condizioni Ottimalità

Problema Convesso

Link to original

Link to original

Condizioni di Ottimalità

Condizioni Necessarie e Sufficienti

• Una condizione necessaria puo servire a restringere l’insieme di punti in cui cercare la soluzione e a costruire algoritmi che soddisfano la condizione necessaria.

• Una condizione sufficiente puo servire a dimostrare che un punto ottenuto per via numerica sia una soluzione ottima

Condizione Necessaria del Primo Ordine

Teorema

Sia un punto di minimo locale. Se è differenziabile in , allora in

La condizione necessaria fornisce i punti stazionari candidati ad essere punti minimali.

Se il problema è convesso, la condizione diventa necessaria e sufficiente.

Condizione Sufficiente del Secondo Ordine

Teorema

Sia un punto di minimo locale. Se è differenziabile due volte in , allora in e la matrice hessiana è semidefinita positiva

Condizione Necessaria del Secondo Ordine

Sia un punto interno della regione ammissibile e , e differenziabile due volte in :

• Se la matrice hessiana è definita positiva, allora è punto di minimo locale;
• Se la matrice hessiana è definita negativa allora è punto di massimo locale;
• Se la matrice hessiana è indefinita, allora è un punto di sella
• Se la matrice hessiana è semidefinita non si può dire niente

Regolarità dei vincoli di uguaglianza

Condizione di Ottimalità del primo ordine

Forma Equivalente

Funzione Lagrangiana

Link to original

Condizioni KKT

Condizioni di ottimalità del primo ordine-KKT

Teorema: Condizioni di Karush-Kuhn-Tucker

Funzione Lagrangiana

Schema Condizioni Ottimalità

Problema Convesso

Link to original

Schema Condizioni Ottimalità

da sostituire

Link to original