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