Ricerca Operativa Categoria

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 x₁ < 37, è necessario introdurre una variabile che rappresenta il delta tra il minimo di x₁ e il numero di riferimento (nell'esempio, 37).

Scrivendo quindi x₁ + x₂ = 37, x₂ > 0 si ottiene lo stesso risultato, ponendo x₂ 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 x₁ è zero, x₂ è 37, se x₁ = 1, allora x₂ = 36 e così via. Se x₁ = 38, allora x₂ 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:

• x₁ ≤ 4
• 2x₂ ≤ 12
• 3x₁ + 2x₂ ≤ 18
• x₁≥ 0, x₂ ≥ 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:

$\left(\begin{array}{cccccc}1& 0& 3& 0& 0& 4\\ 0& 2& 0& 1& 0& 12\\ 3& 2& 0& 0& 1& 18\end{array}\right)$

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 = x₁ + x₂

anche come

Z - x₁+ x₂ = 0

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

• Z = 3x₁ + 5x_c
• x₁ ≤ 4
• 2x₂ ≤ 12
• 3x₁ + 2x₂ ≤ 18
• x₁≥ 0, x₂ ≥ 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:

$\left(\begin{array}{cccccc}-3& -5& 0& 0& 0& 0\\ 1& 0& 3& 0& 0& 4\\ 0& 2& 0& 1& 0& 12\\ 3& 2& 0& 0& 1& 18\end{array}\right)$

Applicazione del metodo

Inizializzazione

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

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 x₁ e x₂ sono ancora positivi.
In base all'idea risolutiva 5, sceglieremo il coefficiente più alto per spostarci in quella direzione.

x₂ diventa la variabile di base entrante.

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

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

Dal momento che x₁ = 0 ⇒ x₃ = 4
Inoltre bisogna scegliere i valori di x₃, x₄ e x₅ in modo che siano maggiori di zero e permettano il valore di x₂ più alto possibile in questo sistema:

• 2x₂ + x₄ = 12
• 3x₁ + 2x₂ + x₅ = 18

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

• x₄ = 12 - 2x₂
• x₅ = 18 - 2x₂

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

Vediamo di quanto può essere aumentato x₂

x₃ = 4, che è maggiore di zero e non vincola x₂

x₄ e x₅ devono essere maggiori di zero, ma il sistema deve essere visto dal "punto di vista" di x₂

• x₄ = 12 - 2x₂ ≥ 0 ⇒ x₂ ≤ 12/2 = 6
• x₅ = 18 - 2x₂≥ 0 ⇒ x₂ ≤ 18/2 = 9

Quindi aumentare x₂ fino a 6 rende x₄ = 0, mentre aumentare x₂ fino a 9 rende x₅ = 0 ma x₄ negativa.
x₂ può essere aumentato fino a 6.

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

I coefficienti di x₂ sono -5, 0, 2, 2 e quelli di x₄ 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 x₂ sia x₄, è possibile "liberare dal coefficiente" la variabile non di base x₂ dividendo tutto per il suo reciproco:

2x₂ + x₄ = 12 ⇒ x₂ + ½x₄ = 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 x₂ con un x₄ corrispondente: x₂ = -½x₄

Z	x1	x2	x3	x4	x5	C
Z	-3x1			$\frac{5}{2}{x}_4$		0
	x1		x3			4
		x2		½x4		6
	3x1			-x4	x5	18

Ora possiamo calcolare la nuova BFS considerando x₁ = 0 e x₄ = 0, che è (0, 6, 4, 0, 18).

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

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

Z	x1	x2	x3	x4	x5	C
Z	-3x1			$\frac{5}{2}{x}_4$		-(-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			$\frac{5}{2}{x}_4$		-(-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			$\frac{5}{2}{x}_4$		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 + 3x₁

$-\frac{5}{4}{x}_4$

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

Seconda iterazione

Dal momento che x₁ ha un coefficiente positivo e

$-\frac{5}{4}{x}_4$

no, consideriamo di quanto può essere incrementato x₁ ponendo x₄ a zero.

• x₃ =  4 - x₁, che significa che x₁ non può essere maggiore di 4
• x₂ = 6, che significa che non pone limiti superiori a x₁
• x₅ = 6 - 3x₁, che significa che x₁ non può essere maggiore di 6/3 => 2

Da questo test otteniamo che x₅ è la variabile uscente. x₁ vale quindi

Modifichiamo la riga in cui è presente x₅ dividendo tutta la riga per il coefficiente della variabile uscente x₁

Z	x1	x2	x3	x4	x5	C
Z	-3x1			$\frac{5}{2}{x}_4$		30
	x1		x3			4
		x2		½x4		6
	x1			-⅓x4	⅓x5	⅓6 = 2

Sostituiamo x₁ con ⅓x₄

Z	x1	x2	x3	x4	x5	C
Z				$\frac{5}{2}{x}_4+\left(-3\right)·\frac{1}{3}{x}_4$		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 x_1.

Il risultato è il seguente:

Z	x1	x2	x3	x4	x5	C
Z				$\frac{5}{2}{x}_4+\left(-3\right)·\frac{1}{3}{x}_4$		30 - (-3*2)
			x3	-⅓x4		4 - (1*2)
		x2		½x4		6
	x1			-⅓x4	⅓x5	2

Ora:

$Z=\mathrm{36}-\frac{3}{2}{x}_4-x_5$

Tutti i coefficienti sono negativi, quindi la BFS migliore è questa, in cui x₁ = 2 e x₂ = 6.

 

 

* 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):

$\left(\genfrac{}{}{0ex}{}{n+m}{n}\right)$

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.

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

Risolviamo il seguente problema:

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

x∈{0,1}⁶

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

$\sum _{j=1}^n{c}_j{x}_j$

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

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

$\sum _{j=1}^n{a}_j{x}_j\le b$

per j = 1, a_j = 3
per j = 2, a_j = 3
per j = 3, a_j = 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 => x₂ = 1
3. c>0, a>0
4. c<0, a>0 => x₄ = 0
5. c<0, a<0 => x₅ = 1-y₅
6. c>0, a=0 => x₆ = 1

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

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

con 0 ≤ x₁, x₃, y₅ ≤ 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.

$\frac{3}{1}\ge \frac{4}{3}\ge \frac{1}{1}$

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.

x₁, a cui corrisponde la frazione 4/3, vale 1

x₃, a cui corrisponde 3, vale 1

y₅, a cui corrisponde l'ultimo 1, vale

$\frac{b-\sum _{k=1}^h{a}_k}{a_{h+1}}$

quindi

$\frac{4.5-\left(1+3\right)}{1}=0.5$

Se y₅ = 0,5 allora x₅ = 1-0,5 = 0,5

La soluzione è quindi x₁ = 1; x₂ = 1; x₃ = 1; x₄ = 0; x₅ = 0.5; x₆ = 1;

...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≤x_uv≤c_uv (x è il flusso, c è la capacità)
• $\sum _{\left(u,v\right)\in {\omega }^{-}\left(v\right)}{x}_{uv}-\sum _{\left(v,k\right)\in {\omega }^{+}\left(v\right)}{x}_{uv}=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

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 P₁ = {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 P₂ = {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):

P₂ = {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.

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 P₁ = {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 P₂ = {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 P₃ = {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 P₄ = {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 P₅ = {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.

Le matrici spaventano, questo da sempre.

Però se si fanno gli esempi giusti, tutto sommato (∑) non sono neanche impossibili.