Ricerca Operativa - 19

OK, 19 non è un voto di cui esattamente vantarsi, e Obama non è più il Presidente degli USA e non elargisce medaglie, MA...

All'inizio del mio percorso di studi avevo preventivato che ci potevano essere due motivi per cui ero giustificato nel sospendere i miei studi per un annetto, e sono alla fine del più piacevole dei due.

In questo contesto, anche solo aver portato a casa un esame - l'unico che ho tentato - mi dà una soddisfazione immensa.

Quindi, Obama: recupera qualche medaglietta dal fondo del cassetto e...

Prima applicazione del metodo del simplesso

Inizializzazione

Si comincia dall'origine: (0, 0) per un problema a due dimensioni.

Test di ottimalità

Ci si sposta verso un altro vertice per verificare se quello preso in considerazione non è ottimale.

Di solito si sceglie la direzione verso cui il miglioramento è più marcato, e ci si ferma arrivati al vertice determinato da uno dei vincoli.

Arrivati a un nuovo vertice, verificare se esiste uno dei vertici adiacenti migliore di quello attuale, e se c'è, andare in quella direzione.

Idee risolutive

  1. Ridurre il numero di soluzioni candidate a essere ottimali da tutte quelle ammissibili ai soli vertici
  2. Il simplesso è una procedura iterativa, cioè è ripetuta finché non si arriva alla soluzione ottimale:
    1. inizializzazione
    2. test di ottimalità
    3. fine o reiterazione
  3. Se possibile, scegliere sempre l'origine come punto di partenza. Questo riduce il numero di calcoli.
  4. Quando ci si muove, il metodo del simplesso lo fa sempre verso vertici adiacenti, sempre per ridurre il numero di calcoli. Il metodo del simplesso però non dice se il vertice adiacente è migliore di quello corrente, ma solo se il tasso di miglioramento in quella direzione è positivo o negativo (anche se questo equivale a dire se il vertice è migliore o no)
  5. Dire che il tasso di miglioramento per tutti i vertici adiacenti è negativo equivale a dire che il vertice corrente è la soluzione ottimale.

Trattare i vincoli

Quando si trova un vincolo di disuguaglianza (per es. "il numero di xxx deve essere minore di 37), del tipo x1 < 37, è necessario introdurre una variabile che rappresenta il delta tra il minimo di x1 e il numero di riferimento (nell'esempio, 37).

Scrivendo quindi x1 + x2 = 37, x2 > 0 si ottiene lo stesso risultato, ponendo x2 compreso tra il valore minimo e 37. Per esempio, se il valore minimo è zero (es. non si può produrre una quantità negativa di beni), se x1 è zero, x2 è 37, se x1 = 1, allora x2 = 36 e così via. Se x1 = 38, allora x2 dovrebbe essere -1, che viola un vincolo dichiarato.

Queste variabili, introdotte per trasformare una disuguaglianza in un'uguaglianza con soli vincoli di non negatività, sono dette variabili slack.

Va da sé che se una variabile slack è a zero, ci stiamo trovando sulla frontiera per il vincolo che la usa.

BFS

Una BFS (basic feasible solution: soluzione di base ammissibile) è una soluzione di base in cui sono presenti le opportune variabili di slack e in cui i vertici sono ammissibili.

Una BFS è assimilabile a una matrice algebrica.

Per esempio, un problema del tipo:

  • x1 ≤ 4
  • 2x2 ≤ 12
  • 3x1 + 2x2 ≤ 18
  • x1≥ 0, x2 ≥ 0

si trasforma in una tabella, in cui tutte le variabili devono essere ≥ 0 (in rosa le variabili slack):

x1 x2 x3 x4 x5 C
x1 x3 4
2x2 x4 12
3x1 2x2 x5 18

che si può trasformare in una matrice:

10300402010123200118

Ogni vincolo ha una variabile indicatrice, che - se posta a zero - assicura che l'equazione che definisce la frontiera per quel vincolo è soddisfatta dall'equazione.

La variabile posta a zero è una variabile non di base, mentre le altre sono dette variabili di base.

Una soluzione di base è ammissibile sse ogni variabile è maggiore o uguale a zero, altrimenti - il contrario di ammissibile - è detta degenere.

Il grado di libertà di una BFS è dato dal numero di variabili meno il numero di equazioni, quindi nell'esempio è 2.

Una soluzione di base ha le seguenti proprietà:

  1. ogni variabile può essere di base o non di base
  2. il numero delle variabili di base è uguale al numero di vincoli funzionali
  3. le variabili non di base sono poste uguali a zero
  4. i valori delle variabili di base sono le soluzioni del sistema di equazioni
  5. se le variabili di base soddisfano i vincoli di non negatività, la soluzione di base è una BFS

Se il problema include una specifica per la massimizzazione, è necessario introdurlo alla stregua di un vincolo. Siccome è possibile scrivere il vincolo

Z = x1 + x2

anche come

Z - x1+ x2 = 0

è possibile introdurre questo come vincolo di uguaglianza e senza variabili slack.
P.E. se il problema è massimizzare 3x1 + 5xc, il prospetto diventa:

  • Z = 3x1 + 5xc
  • x1 ≤ 4
  • 2x2 ≤ 12
  • 3x1 + 2x2 ≤ 18
  • x1≥ 0, x2 ≥ 0

si trasforma in una tabella:

Z x1 x2 x3 x4 x5 C
Z -3x1 -5x2 0
x1 x3 4
2x2 x4 12
3x1 2x2 x5 18

che si può trasformare in una matrice:

-3-5000010300402010123200118

Applicazione del metodo

Inizializzazione

In base al concetto 3 (scegliere la base per iniziare il simplesso), si considerano variabili non di base x1 e x2.

I valori delle variabili sono, in questo caso:

x1 x2 x3 x4 x5
0 0 4 12 18
Criterio di arresto

Il valore di Z è in questo caso zero.
La soluzione non è ottimale, poiché i coefficienti di x1 e x2 sono ancora positivi.
In base all'idea risolutiva 5, sceglieremo il coefficiente più alto per spostarci in quella direzione.

x2 diventa la variabile di base entrante.

In questo caso i criteri si modificano in modo da cercare di ottimizzare x2:

x1 x2 x3 x4 x5 C
x1 x3 4
2x2 x4 12
3x1 2x2 x5 18

Dal momento che x1 = 0 ⇒ x3 = 4
Inoltre bisogna scegliere i valori di x3, x4 e x5 in modo che siano maggiori di zero e permettano il valore di x2 più alto possibile in questo sistema:

  • 2x2 + x4 = 12
  • 3x1 + 2x2 + x5 = 18

che corrisponde (x1 = 0 ⇒ è rimosso dal sistema):

  • x4 = 12 - 2x2
  • x5 = 18 - 2x2

Dal momento che tutte le variabili hanno coefficiente positivo, la soluzione è ammissibile.

Vediamo di quanto può essere aumentato x2

x3 = 4, che è maggiore di zero e non vincola x2

x4 e x5 devono essere maggiori di zero, ma il sistema deve essere visto dal "punto di vista" di x2

  • x4 = 12 - 2x2 ≥ 0 ⇒ x2 ≤ 12/2 = 6
  • x5 = 18 - 2x2≥ 0 ⇒ x2 ≤ 18/2 = 9

Quindi aumentare x2 fino a 6 rende x4 = 0, mentre aumentare x2 fino a 9 rende x5 = 0 ma x4 negativa.
x2 può essere aumentato fino a 6.

Ora, posto x2 = 6, la variabile con coefficiente zero è x4, quindi si può costruire una nuova tabella con queste impostazioni. x4 è ora una nuova variabile di base.

I coefficienti di x2 sono -5, 0, 2, 2 e quelli di x4 sono 0, 0, 1, 0

Z x1 x2 x3 x4 x5 C
Z -3x1 -5x2 0
x1 x3 4
2x2 x4 12
3x1 2x2 x5 18

Utilizzando il vincolo in cui sono presenti sia x2 sia x4, è possibile "liberare dal coefficiente" la variabile non di base x2 dividendo tutto per il suo reciproco:

2x2 + x4 = 12 ⇒ x2 + ½x4 = 12/2

Z x1 x2 x3 x4 x5 C
Z -3x1 -5x2 0
x1 x3 4
x2 ½x4 6
3x1 2x2 x5 18

Ora bisogna sostituire x2 con un x4 corrispondente: x2 = -½x4

Z x1 x2 x3 x4 x5 C
Z -3x1 52x4 0
x1 x3 4
x2 ½x4 6
3x1 -x4 x5 18

Ora possiamo calcolare la nuova BFS considerando x1 = 0 e x4 = 0, che è (0, 6, 4, 0, 18).

Il valore costante (nell'esempio, 6, nel riquadro rosso) va moltiplicato per il coefficiente di x2 e sottratto da C.

Nella prima riga, il coefficiente di x2 è -5, C = 6 e quindi dalla prima riga va tolto -30:

Z x1 x2 x3 x4 x5 C
Z -3x1 52x4 -(-30)
x1 x3 4
x2 ½x4 6
3x1 -x4 x5 18

Nell'ultima riga, il coefficiente è 2, C è 6 e quindi va tolto 12 dal valore corrente:

Z x1 x2 x3 x4 x5 C
Z -3x1 52x4 -(-30)
x1 x3 4
x2 ½x4 6
3x1 -x4 x5 18-(+12)

Il risultato è la nuova BFS:

Z x1 x2 x3 x4 x5 C
Z -3x1 52x4 30
x1 x3 4
x2 ½x4 6
3x1 -x4 x5 6

La nuova BFS è quindi (0, 6, 4, 0, 6) e Z = 30.

Z = 30 + 3x1

-54x4

poiché x1 ha coefficiente positivo, il test di ottimalità non è superato, ed è necessaria una seconda iterazione.

Seconda iterazione

Dal momento che x1 ha un coefficiente positivo e

-54x4

no, consideriamo di quanto può essere incrementato x1 ponendo x4 a zero.

  • x3 =  4 - x1, che significa che x1 non può essere maggiore di 4
  • x2 = 6, che significa che non pone limiti superiori a x1
  • x5 = 6 - 3x1, che significa che x1 non può essere maggiore di 6/3 => 2

Da questo test otteniamo che x5 è la variabile uscente. x1 vale quindi

Modifichiamo la riga in cui è presente x5 dividendo tutta la riga per il coefficiente della variabile uscente x1

Z x1 x2 x3 x4 x5 C
Z -3x1 52x4 30
x1 x3 4
x2 ½x4 6
x1 -⅓x4 ⅓x5 ⅓6 = 2

Sostituiamo x1 con ⅓x4

Z x1 x2 x3 x4 x5 C
Z 52x4+-3·13x4 30
x3 -⅓x4 4
x2 ½x4 6
x1 -⅓x4 ⅓x5 2

Inoltre ovunque sia stata fatta la sostituzione bisogna togliere 2 per il coefficiente di x1.

Il risultato è il seguente:

Z x1 x2 x3 x4 x5 C
Z 52x4+-3·13x4 30 - (-3*2)
x3 -⅓x4 4 - (1*2)
x2 ½x4 6
x1 -⅓x4 ⅓x5 2

Ora:

Z=36-32x4-x5

Tutti i coefficienti sono negativi, quindi la BFS migliore è questa, in cui x1 = 2 e x2 = 6.

 

 

Proprietà dei vertici

* per "vertice ammissibile" si intende un vertice che non sia su un segmento che collega soluzioni ammissibili. Quando un vertice riporta un asterisco, si intende vertice ammissibile.

In programmazione lineare, i vertici hanno le seguenti proprietà:

  1. Se esiste una sola soluzione ottima, questa sarà un vertice. Se esistono più soluzioni, almeno due di queste sono vertici* adiacenti.
  2. Il numero di vertici ammissibili è finito.
  3. Se un vertice ammissibile non ha vertici adiacenti migliori, allora non ci sono vertici migliori. Quindi se il problema ha una soluzione ottima, questo vertice è la soluzione ottima.

La 1. si dimostra per assurdo. Se esiste una soluzione ottima che non è un vertice, significa che la soluzione è compresa tra due vertici*, ma in questo caso, poiché i vertici* sono ammissibili, anche essi sono soluzioni ammissibili, il che contraddice il fatto che la soluzione sia unica.

La 2. è dimostrabile perché il conteggio dei vertici è dato da una formula che restituisce solo risultati finiti, che è (n = numero di equazioni, m = numero di vincoli):

(n+mn)

La 3. è una diretta conseguenza della convessità del problema. Se il problema è convesso, ogni spostamento verso un vertice "migliore" è una garanzia che anche il risultato sarà migliore; viceversa se il problema non fosse convesso, sarebbe necessario calcolare ogni singolo punto e cercare per tentativi il risultato migliore.

Simplesso = Complesso?

Il punto di vista geometrico della soluzione di problemi

Quando in un problema di programmazione lineare (PL) sono presenti solo due variabili, il problema può essere descritto come una superficie di un piano. Per esempio:

{x1>2x1+x25x29

Rappresentazione grafica (discreta) del problema. La soluzione è l'area verde

Le soluzioni ottimali si trovano agli angoli della regione ammissibile (es. trovare i valori massimi possibili di x1 e x2), se esistono più soluzioni ammissibili (es. trovare i valori minimi possibili di x1 e x2) sono sempre vertici adiacenti.

Se le variabili sono più di due, rappresentare il problema graficamente è molto più difficile, perché nel caso di tre variabili servirebbe un solido, mentre nel caso di quattro o più variabili non sarebbe possibile una rappresentazione grafica unica di tutto il problema.

Il metodo del simplesso

Quando le dimensioni diventano tante, un approccio geometrico diventa più difficile di uno algebrico. Per risolvere un problema a più dimensioni, si comincia considerando il punto (0, 0, ...0), cioè l'origine, una volta che le variabili sono trasformate in modo da poter assumere solo valori positivi.

Successivamente, verificato che il punto di origine non è una soluzione ottima, ci si sposta al vertice adiacente più lontano, in modo da massimizzare il risultato del primo passaggio.

Arrivati al punto successivo, si ripete l'operazione finché tutti i vertici adiacenti non sono soluzioni peggiori di quella individuata.

Un esempio

Si risolva questo problema:

max Z = 3x1 + 5x2

con i segenti vincoli
x1        ≤ 4
      2x2 ≤ 12
3x1 + 2x2 ≤ 18
x1, x2 ≥ 0

Per risolvere il problema è necessario introdurre delle variabili per cui le disequazioni diventino equazioni, per esempio, per quanto riguarda il primo vincolo, x1 ≤ 4 diventa x1 + x3 = 4, dove evidentemente x3 = 4 - x1

Il problema ora si può riscrivere così (forma aumentata):

x1        + x3         = 4
      2x2     + x4     = 12
3x1 + 2x2          + x5 = 18
x1, x2, x3, x4, x5 ≥ 0

Ponendo via via le variabili uguali a zero, si ottengono i vertici del poliedro.
x1 = 0, x4 = 0: (0,6,4,0,6)

x3 = 0, x4 = 0: (4,6,0,0,-6) vertice non ammissibile, perché una delle variabili è negativa

x1 = 0, x2 = 0: (0,0,4,12,18)

x3 = 0, x2 = 0: (4,0,0,12,6)

x4 = 0, x5 = 0: (2,6,2,0,0)

x3 = 0, x5 = 0: (4,3,0,6,0)

Iniziando dal vincolo x1 = 0, x2 = 0 si ottiene un vertice ammissibile, ma certamente non è la soluzione migliore, perché Z = 0.

Provando a muoversi lungo le due direzioni adiecenti al vertice (0,0), scegliamo la direzione dove il tasso di miglioramento è maggiore, quindi manteniamo x1 a zero e portiamo x2 al suo valore massimo ammissibile (cioè poniamo x4 a zero):

x1 = 0, x4 = 0: (0,6,4,0,6), Z = 30

A questo punto, essendoci solo due variabili, è possibile tentare di migliorare Z solo in una direzione, cioè (2, 6).

Con x1 = 2, x2 = 6 il risultato Z = 36, che è sicuramente migliore del 30 di x1 = 0, x2 = 6. Come faccio a sapere se il risultato si può migliorare? Tento di spostarmi ancora, e mi sposto al vertice successivo, che è x1 = 4, x2 = 3. In questo caso, Z = 27, che è un risultato peggiore del precedente.

Siccome il problema è convesso, non è possibile che esistano soluzioni migliori di quella che si trova vicino solo vertici peggiori, quindi la soluzione al mio problema è x1 = 2, x2 = 6 (e, per completezza, x3 = 2, x4 = 0, x5 = 0).

Il metodo del simplesso (forma tabellare)

Variabili di base Equazione Coefficiente di Termini noti
Z x1 x2 x3 x4 x5
Z (0) 1 -3 -5 0 0 0 0
x3 (1) 0 1 0 1 0 0 4
x4 (2) 0 0 2 0 1 0 12
x5 (3) 0 3 2 0 0 1 18

I dati riportati in questa tabella rappresentano il problema (prima riga) e i vincoli (le tre righe successive), sotto forma di coefficienti delle variabili.

Il problema è Z-3x1-5x2 = 0, per questo le variabili della prima riga sono scritte con segno negativo. La variabile di base (quella di cui vogliamo conoscere il valore) è Z.

Nelle righe successive, le variabili di base corrispondono alle variabili slack, cioè a quelle introdotte per ottenere il termine noto nel caso in cui le variabili non di base non fossero sufficienti.

Test di ottimalità: è soddisfatto solo se tutti i termini della prima riga sono non negativi. In questo caso non lo sono.

Iterazione: scegliere nella prima riga il coefficiente più basso (il più alto, in valore assoluto): in questo esempio è x2 = -5.

Variabili di base Equazione Coefficiente di Termini noti
Z x1 x2 x3 x4 x5
Z (0) 1 -3 -5 0 0 0 0
x3 (1) 0 1 0 1 0 0 4
x4 (2) 0 0 2 0 1 0 12
x5 (3) 0 3 2 0 0 1 18

Tra gli elementi della colonna, scegliere il più piccolo dei valori non negativi:

Variabili di base Equazione Coefficiente di Termini noti
Z x1 x2 x3 x4 x5
Z (0) 1 -3 -5 0 0 0 0
x3 (1) 0 1 0 1 0 0 4
x4 (2) 0 0 2 0 1 0 12/2 = 6
x5 (3) 0 3 2 0 0 1 18/2 = 9

Abbiamo identificato la variabile uscente (x2) e la variabile entrante (x4).
Ora otteniamo la nuova riga pivot dividendo tutta la riga per l'elemento pivot.

Variabili di base Equazione Coefficiente di Termini noti
Z x1 x2 x3 x4 x5
Z (0) 1 -3 -5 0 0 0 0
x3 (1) 0 1 0 1 0 0 4
x4 (2) 0 0 2 0 1 0 12
x5 (3) 0 3 2 0 0 1 18
Z (0) 1
x3 (1) 0
x2 (2) 0 0 1 0 ½ 0 6
x5 (3) 0

N.B. per forza se divido il coefficiente trovato per il coefficiente, otterrò uno (cella x2/x2).

Ora valutiamo le righe della colonna pivot: se sono positive, sottrarre, altrimenti sommare il prodotto tra il coefficiente (valore assoluto) e la nuova riga pivot.

N.B. per forza, la prima riga della colonna pivot finisce a zero.

Variabili di base Equazione Coefficiente di Termini noti
Z x1 x2 x3 x4 x5
Z (0) 1 -3 -5 0 0 0 0
x3 (1) 0 1 0 1 0 0 4
x4 (2) 0 0 2 0 1 0 12
x5 (3) 0 3 2 0 0 1 18
Z (0) 1 -3 + (0*5) -5 + (1*5) 0 + (0*5) 0 + (½ * 5) 0 + (0*5) 0 + (6*5)
x3 (1) 0 1 0 1 0 0 4
x2 (2) 0 0 1 0 ½ 0 6
x5 (3) 0 3 - (0*2) 2 - (1*2) 0 - (0*2) 0 - (½ * 2) 1 - (0*2) 18 - (6*2)

Svolgendo tutti i calcoli:

Variabili di base Equazione Coefficiente di Termini noti
Z x1 x2 x3 x4 x5
Z (0) 1 -3 -5 0 0 0 0
x3 (1) 0 1 0 1 0 0 4
x4 (2) 0 0 2 0 1 0 12
x5 (3) 0 3 2 0 0 1 18
Z (0) 1 -3 0 0 5/2 0 30
x3 (1) 0 1 0 1 0 0 4
x2 (2) 0 0 1 0 ½ 0 6
x5 (3) 0 3 0 0 -1 1 6

Nell'iterazione successiva:

  1. Scelgo la variabile (nel tableau ricalcolato) con il coefficiente più basso (più alto in valore assoluto), che è x1 = -3
  2. Per ciascun valore della colonna scelta, divido il termine noto per il coefficiente e - solo per i valori positivi (zero escluso!) - scelgo quello più piccolo. Nell'esempio è la riga (3).
  3. Scambio la variabile entrante e quella uscente e divido per la variabile pivot
  4. Ricalcolo le altre righe in base alla variabile pivot e alla riga appena ricalcolata al punto precedente
Variabili di base Equazione Coefficiente di Termini noti
Z x1 x2 x3 x4 x5
Z (0) 1 -3 -5 0 0 0 0
x3 (1) 0 1 0 1 0 0 4
x4 (2) 0 0 2 0 1 0 12
x5 (3) 0 3 2 0 0 1 18
Z (0) 1 -3 0 0 5/2 0 30
x3 (1) 0 1 0 1 0 0 4
x2 (2) 0 0 1 0 ½ 0 6
x5 (3) 0 3 0 0 -1 1 6
Z (0) 1 -3 0 0 5/2 0 30
x3 (1) 0 1 0 1 0 0 4 ⇒ 4/1 = 4
x2 (2) 0 0 1 0 ½ 0 6 ⇒ 6/0 no
x5 (3) 0 3 0 0 -1 1 6 ⇒ 6/3 = 2

Scelgo la terza riga

Variabili di base Equazione Coefficiente di Termini noti
Z x1 x2 x3 x4 x5
Z (0) 1 -3 -5 0 0 0 0
x3 (1) 0 1 0 1 0 0 4
x4 (2) 0 0 2 0 1 0 12
x5 (3) 0 3 2 0 0 1 18
Z (0) 1 -3 0 0 5/2 0 30
x3 (1) 0 1 0 1 0 0 4
x2 (2) 0 0 1 0 ½ 0 6
x5 (3) 0 3 0 0 -1 1 6
Z (0) 1 -3 0 0 5/2 0 30
x3 (1) 0 1 0 1 0 0 4
x2 (2) 0 0 1 0 ½ 0 6
x5 x1 (3) 0/3 = 0 3/3 = 1 0/3 = 0 0/3 = 0 -⅓ = - ⅓ = ⅓ 6/3 = 2

Aggiungo (o tolgo) il termine pivot diviso ogni elemento della riga dalla riga (0)

Variabili di base Equazione Coefficiente di Termini noti
Z x1 x2 x3 x4 x5
Z (0) 1 -3 -5 0 0 0 0
x3 (1) 0 1 0 1 0 0 4
x4 (2) 0 0 2 0 1 0 12
x5 (3) 0 3 2 0 0 1 18
Z (0) 1 -3 0 0 5/2 0 30
x3 (1) 0 1 0 1 0 0 4
x2 (2) 0 0 1 0 ½ 0 6
x5 (3) 0 3 0 0 -1 1 6
Z (0) 1 -3 + (3*1)
0+(3*0) 0+(3*0) 5/2+(3*-⅓) 0+(3*) 30+(3*2)
x3 (1) 0 1 0 1 0 0 4
x2 (2) 0 0 1 0 ½ 0 6
x1 (3) 0 1 0 0 -⅓ 2

Tolgo la riga pivot dalle altre righe

Variabili di base Equazione Coefficiente di Termini noti
Z x1 x2 x3 x4 x5
Z (0) 1 -3 -5 0 0 0 0
x3 (1) 0 1 0 1 0 0 4
x4 (2) 0 0 2 0 1 0 12
x5 (3) 0 3 2 0 0 1 18
Z (0) 1 -3 0 0 5/2 0 30
x3 (1) 0 1 0 1 0 0 4
x2 (2) 0 0 1 0 ½ 0 6
x5 (3) 0 3 0 0 -1 1 6
Z (0) 1 0
0 0 3/2 1 36
x3 (1) 0 1-1 0-0 1-0 0+⅓ 0-⅓ 4-2
x2 (2) 0 0 1 0 ½ 0 6
x1 (3) 0 1 0 0 -⅓ 2

A questo punto nella riga (0) ci sono solo valori non negativi, quindi mi posso fermare.
Nella riga (0) c'è il valore di Z (=36) e nelle righe (3) e (2) i valori rispettivamente di x1 (=2) e x2 (=6).

Convessità

A è un insieme convesso
B è un insieme non convesso

Che un insieme sia convesso è determinato dal fatto che scelti due punti qualunque dell'insieme, tutti i punti della retta che li congiunge sono all'interno dell'insieme stesso.

Formalmente, dati due punti x e y appartenenti all'insieme, che chiameremo C, e un valore α compreso tra 0 e 1, vale la seguente:

αx+(1-α)y ∈ C

Proposizione 5.1

Dati gli insiemi convessi C1...Cn, con n≥1, allora l'intersezione tra tutti gli insiemi

i=1nCi

è un insieme convesso.

Dimostrazione

Se C è vuoto o contiene un solo elemento, la proposizione è immediatamente verificata.

Se contiene due elementi, per ciascuno degli insiemi C1...Cn vale che i due punti appartengono all'insieme.

È interessante osservare come il concetto di convessità si possa estendere anche a dimensioni superiori a 2, per esempio una sfera tridimensionale è convessa, e anche gli omologhi della sfera su più di tre dimensioni lo sono.

Definizione 5.2

...ovvero come capire se una funzione è concava o convessa.

Quando mi trovai di fronte per la prima volta a questo concetto, stavo studiando la derivata seconda di una funzione.

"In pratica - mi dicevo, per ricordare - se guido sopra la funzione e giro sempre a sinistra, la funzione è convessa, se giro a destra è concava. Se passo da sinistra a destra o viceversa, l'istante in cui il volante è dritto è il punto di flesso, dove la derivata seconda vale zero".

Un altro modo per capire se la funzione è convessa o concava, che concettualmente è più semplice della derivata seconda, è che se prendo due punti diversi tra loro della stessa funzione e li unisco con una linea retta, se la retta sta sopra la funzione, è convessa; se sta sotto è concava.

Formalmente, è convessa se:

f(αx+(1-α)y) ≤ αf(x)+(1-α)f(y), ∀α∈[0,1]

La parte a sinistra indica il valore della funzione in tutti i punti compresi tra x e y, la parte destra indica tutti i punti della retta che inizia in f(x) e termina in f(y).

Proposizione 5.3

Data la funzione f(x) con f:ℝn→ℝ, sia f(x) convessa su ℝn. L'insieme di livello (eventualmente vuoto) Lγ definito mediante la
Lγ = {x ∈ ℝn : f(x) ≤ γ}
è convesso per ogni γ ∈ ℝ

In altre parole, definito un insieme di livello come l'insieme di tutti i punti minori o uguali di f(x) (stiamo parlando di codominio di una funzione ℝn→ℝ, quindi di un insieme di punti appartenenti ai reali), se f(x) è convessa, anche Lγ lo sarà.

Proposizione 3.1, ovvero D(f,d) = ∇f(x)Td

I riferimenti sono a questo testo: Programm. matematica prof. Fasano

Teorema di Taylor (3.1)

Il teorema di Taylor dice - pressappoco - che sommando le derivate di ordine via via superiore in modo che siano sempre meno "rilevanti" si ottiene la funzione cercata.
Come?

Preso un punto x0, la funzione in quel punto può essere approssimata come serie in cui si sommano i termini di un polinomio, nella forma

fx=a0x-x000!+a1x-x011!+a2x-x022!+ox3

Si può procedere con un'approssimazione sempre maggiore illimitatamente, ma poi, quando ci si "ferma" (nell'esempio sopra, ci si arresta al grado 3 del polinomio), si ottiene un resto (detto Resto di Peano) sotto forma di o(xn).

In realtà, siccome x0 = 1, e x1/1! = x, l'esempio si può riscrivere così:

fx=a0+a1x+a2x22!+ox3

Resta da capire cosa rappresentano le an. Sono le derivate di ordine n-esimo della funzione calcolata nel punto x. In pratica, mentre da un lato incrementiamo l'esponente (in rosso scuro), dall'altra incrementiamo l'ordine della derivata.

Teoremi del valor medio (3.2)

Data la funzione f(x) sia f:ℝn→ℝ continuamente differenziabile nella sfera aperta S(x, ρ) = {y ∈ ℝn : ‖y-x‖<ρ} ⊆ℝn, con x ∈ ℝn e ρ > 0. Esiste un valore θ∈[0,1] tale che per ogni y∈S(x,ρ)

  1. f(y) = f(x) + ∇f[x+θ(y-x)]T(y-x),
  2. f(y) = f(x) + ∇f(x)T(y-x)+o(‖y-x‖)

...funzione f(x) sia f:ℝn→ℝ... significa che la funzione "produce" un numero reale a fronte di un "input" di più numeri, ciascuno dei quali si riferisce a una dimensione diversa. Per es. y = f(x) ha n = 1, perché è (tipicamente) una funzione ℝ→ℝ, z = f(x, y) ha n=2, quindi ℝ2→ℝ, w = f(x, y, z) ha n=3 e così via.

...continuamente differenziabile... ovviamente, se vogliamo applicare il teorema di Taylor, bisogna poterla differenziare quanto ci pare.

...nella sfera aperta S(x, ρ) = {y ∈ ℝn : ‖y-x‖<ρ} ⊆ℝn, con x ∈ ℝn e ρ > 0... la sfera ha come centro x, che è un punto nello spazio n-dimensionale (vedi sopra) e raggio ρ. Dato che una sfera ha un raggio positivo, ρ deve essere maggiore di zero. Se x è il centro, tutti i punti che sono distanti da x meno di ρ sono chiamati y. Le due coppie di barrette verticali sono la norma, e hanno lo stesso significato del valore assoluto, applicato a punti di più di una dimensione.

f(y) = f(x) + ∇f[x+θ(y-x)]T(y-x) significa che f(y) si può calcolare come f(x) più qualcosa calcolato sulla base del gradiente della funzione. Quel "qualcosa" è il gradiente della funzione applicata a x più un certo valore compreso tra zero e la distanza tra y e x; il gradiente ottenuto si moltiplica per la distanza tra y e x. In altre parole, a f(x) (noto) si aggiunge un pezzo che ha la lunghezza della differenza tra y e x e la pendenza data dal gradiente di un valore compreso tra f(x) e f(x+y-x), cioè f(y), dal momento che θ è un valore compreso tra zero (che rende f[x+θ(y-x)] = f(x)) e uno (che rende f[x+θ(y-x)] = f(y)).

f(y) = f(x) + ∇f(x)T(y-x)+o(‖y-x‖) ha un approccio diverso: calcola f(y) come gradiente di f(x), di lunghezza pari alla differenza tra y e x, ma con un margine di errore più piccolo della lunghezza y-x. In ogni caso, più x e y sono vicini e più o(‖y-x‖) è piccolo.

Il teorema 3.3 non è altro che un'estensione di 3.2 con un gradiente di secondo ordine (fatto con derivate seconde). Dal teorema di Taylor sarebbe facile estendere 3.3 in modo da arrivare alle derivate di ordine 3, 4...

Proposizione 3.1

Si vuole dimostrare l'equivalenza tra derivata direzionale e gradiente.

D(f) indica normalmente la derivata (prima) della funzione f, che è espressa come il limite per α→0+ del rapporto tra la differenza tra f(x+α) e f(x) da una parte e α dall'altra, quindi:

limα0+fx+α-fxα

La derivata a una o più variabili è un vettore di dimensione n-1: per esempio una funzione del tipo y = f(x) può essere rappresentata su un piano bidimensionale e la derivata è una linea; una funzione z = f(x, y) può essere rappresentata in un volume e la sua derivata è un piano e così via.

La derivata direzionale su più dimensioni si definisce, in maniera simile alla derivata "tradizionale", come D(f,d), in cui d∈ℝn, con n = numero di dimensioni. In pratica, rispetto alla derivata a una variabile si introduce un elemento che rende "multidimensionale" la derivata. Il limite (anche questo cambia di poco) diventa:

limα0+fx+αd-fxα

Da un punto di vista geometrico, α definisce una sfera (usiamo "sfera" anche in senso multi-dimensionale) il cui centro è il punto f(x) e il raggio è lo stesso α.

La proposizione 3.1 dice che la derivata direzionale D(f,d) equivale a ∇f(x)Td

Dimostrazione

Dalla 2 del teorema 3.2, il primo passaggio è spostare f(x) a sinistra:

f(y) = f(x) + ∇f(x)T(y-x)+o(‖y-x‖) f(y) - f(x) = f(x)T(y-x)+o(‖y-x‖)

A questo punto si sostituisce y = x + αd, dove α>0 e d∈ℝn. Si ottiene:

f(x+αd) - f(x) = f(x)T(x+αd-x)+o(‖x+αd-x‖)  f(x+αd) - f(x) = ∇f(x)T(αd)+o(‖αd‖)

Da cui, per la proprietà del prodotto scalare per cui vT(αw) = αvT(w)

f(x+αd) - f(x) = α∇f(x)T(d)+o(‖αd‖)

Dividendo tutto per α, a sinistra si ottiene l'espressione che, con un limite per α tendente a zero, è D(f,d) e a destra si ottengono un gradiente e un resto che, per α tendente a zero, tende a zero a sua volta:

fx+αd-fxα=fxTd+oαdα

Il limite per α → 0 è

limα0fx+αd-fxα=limα0fxTd+limα0oαdα

Il limite per il gradiente non ha senso, perché α non è presente; il limite per la parte a sinistra è per definizione D(f,d); infine il limite per o piccolo tende a zero per valori di α → 0, quindi è trascurabile.

Nella dispensa, il pezzo con o piccolo è "arricchito" di d, ma non ho capito perché.

limα0oαdαdd

Statistiche degli esami di Ricerca Operativa di Fasano

Probl. num. lineare Simplesso Vertici del poliedro Knapsack + B&B Derivate Convessità Flusso Teorema PL
2015-01-08 Autostrade Problema Problema
2015-01-28 Agende Problema Problema 5.3 Problema Dim.
2015-11-20 Pasticceria Problema 3.1 Dim.

5.6

2016-01-14 Impresa edile Problema + forma can. Problema 5.6 Problema 7.2
2016-01-28 Calcolatore multicore Problema Problema Problema 3.1 Def.
2016-06-07 Azienda semolino Problema Problema Problema 3.1 7.2
2016-09-05 Impresa informatica Problema Problema Problema Dim., +

5.3

Il knapsack in pratica

Risolviamo il seguente problema:

max 4x1 +2x2 +3x3 -5x4 -x5 +x6
3x1 -3x2 +x3 +x4 -x5 ≤1/2

x∈{0,1}6

La prima riga è il problema, ed è rappresentato dalla formula

j=1ncjxj

per j = 1, cj = 4
per j = 2, cj = 2
eccetera

La seconda riga è il vincolo, ed è rappresentato dalla formula

j=1najxjb

per j = 1, aj = 3
per j = 2, aj = 3
per j = 3, aj = 1
eccetera
infine, b = 1/2

Riepiloghiamo le prime semplificazioni possibili in questo prospetto:

c < 0 c = 0 c > 0
a < 0 xj = 1 - yj 1 1
a = 0 0 0 1
a > 0 0 0 xj

Nell'esempio:

  1. c>0, a>0
  2. c>0, a<0 => x2 = 1
  3. c>0, a>0
  4. c<0, a>0 => x4 = 0
  5. c<0, a<0 => x5 = 1-y5
  6. c>0, a=0 => x6 = 1

Sostituendo nel problema i valori noti e la sostituzione di x5, otteniamo

max 4x1 +2*1 +3x3 -5*0 -(1-y5) +1
3x1 -3 +x3 -(1-y5) ≤1/2

con 0 ≤ x1, x3, y5 ≤ 1

il problema si può riscrivere come

max 4x1 +3x3 +y5 +2
3x1 +x3 +y5 ≤9/2

A questo punto, bisogna ordinare le variabili in base al rapporto tra c e a: 4/3, 3/1, 1/1.

314311

e bisogna verificare quanti di questi numeri ∈ℚ, sommati tra loro nell'ordine, sono minori o uguali di 4,5.

3 < 4,5

3 + 4/3 < 4,5

3 + 4/3 + 2 > 4,5

quindi il nostro indice è 2.

x1, a cui corrisponde la frazione 4/3, vale 1

x3, a cui corrisponde 3, vale 1

y5, a cui corrisponde l'ultimo 1, vale

b-k=1hakah+1

quindi

4.5-1+31=0.5

Se y5 = 0,5 allora x5 = 1-0,5 = 0,5

La soluzione è quindi x1 = 1; x2 = 1; x3 = 1; x4 = 0; x5 = 0.5; x6 = 1;

Sui flussi

...che poi i flussi, spogliati dei formalismi, non sono mica così difficili da capire.

La dico con parole mie, parole semplici.

Il problema del massimo flusso si applica a un grafo orientato (ciascun arco ha un verso) in cui esistono due nodi "speciali", detti sorgente e pozzo, in cui rispettivamente sono presenti solo archi uscenti (sorgente) e solo entranti (pozzo).
Formalmente:

  • Il grafo è denominato G(V,E). La denominazione è standard: G indica il grafo, V l'insieme dei vertici, E l'insieme degli archi.
  • Gli archi si chiamano s (sorgente), t (pozzo), poi gli altri sono numerati progressivamente
  • Un arco è indicato da due numeri tra parentesi separati da virgola; l'ordine determina il verso. Per esempio, (2,3) è l'arco che va dal nodo 2 al nodo 3.
  • (u,v) ∈ ω-(v) indica l'insieme dei nodi che entrano in v
  • (v,k) ∈ ω+(v) indica l'insieme dei nodi che escono da v

Ogni arco è caratterizzato da una capacità e da un flusso, e il flusso non può mai eccedere la capacità. Si può immaginare un tubo in cui, senza cambiare la pressione, può passare una quantità massima di acqua; da zero al massimo, il flusso può prendere qualsiasi valore (anche se negli esercizi è sempre un valore intero).
La somma di tutti i flussi entranti in un nodo è uguale alla somma dei flussi uscenti. Mantenendo la metafora, tanta acqua entra, tanta acqua esce.
Formalmente:

  • 0≤xuv≤cuv (x è il flusso, c è la capacità)
  • uvω-vxuv-vkω+vxuv=0∀v∈V-{s, t}

Esempio di flusso

Questo flusso è ammissibile, perché esistono un nodo s con soli archi uscenti e un nodo t con soli archi entranti, il flusso di ogni arco è compreso tra zero e la capacità; inoltre la somma di tutti i flussi entranti è uguale a quella di tutti i flussi uscenti per ciascun nodo (tranne s, t):

  1. entra 0, esce 0
  2. entra 1, esce 1
  3. entra 1, esce 1
  4. entra 1, esce 1
Esempio di quali valori considerare per verificare i flussi entranti e uscenti per il nodo 2

Il problema del massimo flusso consiste nel determinare il flusso massimo che può transitare attraverso gli archi del grafo, con le seguenti semplici regole:

  1. un flusso può transitare lungo il verso della freccia se il flusso è minore della capacità. In questo caso, è possibile incrementare il flusso fino ad arrivare alla capacità massima.
  2. un flusso può "transitare" in verso opposto rispetto alla freccia, a patto che "scali" un flusso esistente. In questo caso, si parla di "cammino aumentante"

Nel caso dell'esempio, è possibile incrementare il percorso P1 = {s, (s,2), 2, (2,3), 3, (3,t), t}, poiché tutti gli archi hanno un flusso minore della capienza. Il nuovo risultato è:

Ora (s,2) è diventato impraticabile, perché il flusso è pari alla capienza.

Si può procedere con P2 = {s, (s,1), 1, (1,4), 4...

ma poi, arrivati a 4 si trova un flusso pari alla capienza, per arrivare a T. Per fortuna, è possibile "togliere 1" al flusso (3,4) e procedere poi con (3,t):

P2 = {s, (s,1), 1, (1,4), 4, (3,4), 3, (3,t), t}

Nella notazione del cammino aumentante, l'arco percorso al contrario è rappresentato secondo il suo verso, quindi anche se si va da 4 a 3, l'arco è rappresentato come (3,4).

Il nuovo risultato è:

Ora il flusso uscente da s è 3, e qualunque strada porta o a un arco diretto saturo (es. (s,2)) o a un arco inverso vuoto (es. (1,2)).

Se, partendo da s, consideriamo tutti gli archi che avrebbero ancora capacità, dividendo il grafo in due otteniamo il cosiddetto taglio a capacità minima. In questo esempio, (s,2) è escluso; (s,1) è incluso; (1,2) è escluso; (1,4) è incluso; (2,3) è escluso; (3,4) è escluso; ovviamente gli archi connessi con t sono tutti esclusi (altrimenti si potrebbe aumentare il flusso). Il totale dei flussi che escono dal taglio minimo per entrare nell'insieme del pozzo è uguale al totale del flusso uscente da s.

Taglio a capacità minima

Esempio di compito (08/01/2015)

Il grafo è ammissibile, poiché tutti i nodi hanno flusso positivo e non maggiore della capacità; inoltre la somma dei flussi entranti è pari alla somma dei flussi uscenti per tutti i nodi tranne s e t.

Il grafo ha valore 9 [(s,1) = 8, (s,2) = 1, (s,5) = 0, la somma è 9].

Il grafo può essere incrementato per il percorso P1 = {s, (s,1), 1, (1,t), t} di 2.

La nuova situazione è (la prima coppia è l'arco; la seconda è flusso/capacità; sono colorati gli archi cambiati)

(s,1) = (10,10)
(1,t) = (6,8)
(s,2) = (1,5)
(s,5) = (0,4)
(1,2) = (4,7)
(2,5) = (5,7)
(2,3) = (0,9)
(3,5) = (0,2)
(5,4) = (0,2)
(5,t) = (5,8)
(1,4) = (0,3)
(3,4) = (0,2)
(4,t) = (0,5)

Può essere ancora incrementato per il percorso P2 = {s, (s,2), 2, (2,3), 3, (3,4), 4, (4,t), t} di 2.

La nuova situazione è

(s,1) = (10,10)
(1,t) = (6,8)
(s,2) = (3,5)
(s,5) = (0,4)
(1,2) = (4,7)
(2,5) = (5,7)
(2,3) = (2,9)
(3,5) = (0,2)
(5,4) = (0,2)
(5,t) = (5,8)
(1,4) = (0,3)
(3,4) = (2,2)
(4,t) = (2,5)

Può essere ancora incrementato per il percorso P3 = {s, (s,5), 5, (5, t), t} di 3.

La nuova situazione è

(s,1) = (10,10)
(1,t) = (6,8)
(s,2) = (3,5)
(s,5) = (3,4)
(1,2) = (4,7)
(2,5) = (5,7)
(2,3) = (2,9)
(3,5) = (0,2)
(5,4) = (0,2)
(5,t) = (8,8)
(1,4) = (0,3)
(3,4) = (2,2)
(4,t) = (2,5)

Può essere ancora incrementato per il percorso P4 = {s, (s,2), 2, (2,5), 5, (5,4), 4, (4,t), t} di 2.

La nuova situazione è

(s,1) = (10,10)
(1,t) = (6,8)
(s,2) = (5,5)
(s,5) = (3,4)
(1,2) = (4,7)
(2,5) = (7,7)
(2,3) = (2,9)
(3,5) = (0,2)
(5,4) = (2,2)
(5,t) = (8,8)
(1,4) = (0,3)
(3,4) = (2,2)
(4,t) = (4,5)

A questo punto, apparentemente non c'è più niente, perché (s,1) e (s,2) sono impraticabili e (5,u) ha tutti gli archi uscenti saturi. Ma usando il cammino aumentato, c'è una "via d'uscita" in (2,5)!
Può essere quindi ancora incrementato per il percorso P5 = {s, (s,5), 5, (2,5), 2, (1,2), 1, (1,t), t)} di 1.

La nuova situazione è

(s,1) = (10,10)
(1,t) = (7,8)
(s,2) = (5,5)
(s,5) = (4,4)
(1,2) = (3,7)
(2,5) = (6,7)
(2,3) = (2,9)
(3,5) = (0,2)
(5,4) = (2,2)
(5,t) = (8,8)
(1,4) = (0,3)
(3,4) = (2,2)
(4,t) = (4,5)

A questo punto tutti gli archi uscenti da s sono saturi, quindi è immediatamente evidente che si è arrivati al flusso massimo, che corrisponde a 21.
Il taglio a capacità minima è costituito solo da s.