Gennaio 2017 Archive

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:

$\{\begin{array}{c}{x}_1>2\\ x_1+x_2\ge 5\\ x_2\le 9\end{array}$

Le soluzioni ottimali si trovano agli angoli della regione ammissibile (es. trovare i valori massimi possibili di x₁ e x₂), se esistono più soluzioni ammissibili (es. trovare i valori minimi possibili di x₁ e x₂) 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, x₁ ≤ 4 diventa x₁ + x₃ = 4, dove evidentemente x₃ = 4 - x₁

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.
x₁ = 0, x₄ = 0: (0,6,4,0,6)

x₃ = 0, x₄ = 0: (4,6,0,0,-6) vertice non ammissibile, perché una delle variabili è negativa

x₁ = 0, x₂ = 0: (0,0,4,12,18)

x₃ = 0, x₂ = 0: (4,0,0,12,6)

x₄ = 0, x₅ = 0: (2,6,2,0,0)

x₃ = 0, x₅ = 0: (4,3,0,6,0)

Iniziando dal vincolo x₁ = 0, x₂ = 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 x₁ a zero e portiamo x₂ al suo valore massimo ammissibile (cioè poniamo x₄ a zero):

x₁ = 0, x₄ = 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 x₁ = 2, x₂ = 6 il risultato Z = 36, che è sicuramente migliore del 30 di x₁ = 0, x₂ = 6. Come faccio a sapere se il risultato si può migliorare? Tento di spostarmi ancora, e mi sposto al vertice successivo, che è x₁ = 4, x₂ = 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 è x₁ = 2, x₂ = 6 (e, per completezza, x₃ = 2, x₄ = 0, x₅ = 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-3x₁-5x₂ = 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 è x₂ = -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 (x₂) e la variabile entrante (x₄).
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 x₂/x₂).

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 è x₁ = -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 x₁ (=2) e x₂ (=6).

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 C₁...C_n, con n≥1, allora l'intersezione tra tutti gli insiemi

$\underset{i=1}{\overset{n}{\cap }}{C}_i$

è un insieme convesso.

Dimostrazione

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

Se contiene due elementi, per ciascuno degli insiemi C₁...C_n 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:ℝⁿ→ℝ, sia f(x) convessa su ℝⁿ. L'insieme di livello (eventualmente vuoto) L_γ definito mediante la
L_γ = {x ∈ ℝⁿ : 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 ℝⁿ→ℝ, quindi di un insieme di punti appartenenti ai reali), se f(x) è convessa, anche L_γ lo sarà.

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 x₀, la funzione in quel punto può essere approssimata come serie in cui si sommano i termini di un polinomio, nella forma

$f\left(x\right)=a_0\frac{{\left(x-x_0\right)}^0}{0!}+a_1\frac{{\left(x-x_0\right)}^1}{1!}+a_2\frac{{\left(x-x_0\right)}^2}{2!}+o\left(x^3\right)$

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(xⁿ).

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

$f\left(x\right)=a_0+a_{1}x+a_2\frac{x^2}{2!}+o\left(x^3\right)$

Resta da capire cosa rappresentano le a_n. 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:ℝⁿ→ℝ continuamente differenziabile nella sfera aperta S(x, ρ) = {y ∈ ℝⁿ : ‖y-x‖<ρ} ⊆ℝⁿ, con x ∈ ℝⁿ 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:ℝⁿ→ℝ... 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 ℝ²→ℝ, 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 ∈ ℝⁿ : ‖y-x‖<ρ} ⊆ℝⁿ, con x ∈ ℝⁿ 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:

$\underset{\alpha \to 0^{+}}{\lim }\frac{f\left(x+\alpha \right)-f\left(x\right)}{\alpha }$

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∈ℝⁿ, 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:

$\underset{\alpha \to 0^{+}}{\lim }\frac{f\left(x+\alpha d\right)-f\left(x\right)}{\alpha }$

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∈ℝⁿ. 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 v^T(αw) = αv^T(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:

$\frac{f\left(x+\alpha d\right)-f\left(x\right)}{\alpha }=\nabla {f\left(x\right)}^{T}d+\frac{o\left(\Vert \alpha d\Vert \right)}{\alpha }$

Il limite per α → 0 è

$\underset{\alpha \to 0}{\lim }\frac{f\left(x+\alpha d\right)-f\left(x\right)}{\alpha }=\underset{\alpha \to 0}{\lim }\nabla {f\left(x\right)}^{T}d+\underset{\alpha \to 0}{\lim }\frac{o\left(\Vert \alpha d\Vert \right)}{\alpha }$

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é.

$\underset{\alpha \to 0}{\lim }\frac{o\left(\Vert \alpha d\Vert \right)}{\alpha \Vert d\Vert }\Vert d\Vert$

	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