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.

Distribuzione binomiale

Quando si usa

  • Conosciamo la composizione della popolazione
  • Si può dividere in due nettamente la popolazione
  • C’è reinserimento

Esempi

Si consideri un'urna contenente quattro elementi, la cui probabilità di estrazione è

X={12/722/732/741/7}

in alternativa si possono considerare due biglie 1, due biglie 2, due biglie 3 e una sola biglia 4 (oppure 4, 4, 4, 2...).
Le biglie 1 e 2 sono bianche; le biglie 3, 4 sono rosse
Qual è la probabilità che si estragga una biglia bianca facendo 3 estrazioni?

Formula

  • n = numero di estrazioni
  • p = probabilità che si verifichi un successo
  • X˜Bp(n, p) = distribuzione binomiale (B) per n estrazioni con p probabilità
  • k = insieme di estrazioni, da 0 a n

PX=k=(nk)pk1-pn-k

Soluzione dell'esempio

  • p = 4/7 (la probabilità che esca il bianco)
  • n = 3 (il numero di estrazioni)

PS3=2=(32)472373-2=3*1649*370,41982

Distribuzione ipergeometrica

Quando si usa

  • Conosciamo la composizione della popolazione
  • Si può dividere in due nettamente la popolazione
  • Non c'è reinserimento

Esempi

Un software consiste di 12 programmi, 5 dei quali necessitano di un upgrade. Se vengono scelti a caso 4 programmi per un test. Qual è la probabilità che almeno 2 di essi siano da aggiornare? Qual è il numero medio di programmi da aggiornare tra i 4 scelti?

Formula

  • X = Variabile aleatoria che conta il numero di successi
  • n = numero di estrazioni
  • N = numero di elementi
  • K = numero di elementi "successo" (successo significa che è vero per il criterio. Per es. se cerchiamo un bug in un programma, "successo" significa che è stato trovato)
  • X˜Ip(N, K, n) = distribuzione ipergeometrica (I) in N campioni di K successi per n estrazioni
  • k = ciascuno dei numeri compresi tra max{0, n-(N-K)} e min{n, K}.
    max{0, n-(N-K)} significa che se faccio più estrazioni di quanti siano i casi di non-successo, sono sicuro di estrarre almeno un successo (es. bianco = successo, rosso = insuccesso; ho un'urna con 4 bianche e 5 rosse, faccio 6 estrazioni)
  • min{n, K} il ragionamento è analogo

PX=k=(Kk)(N-Kn-k)(Nn)

Soluzione dell'esempio

  • N = 12 (il numero di programmi della popolazione)
  • n = 4 (il numero di estrazioni)
  • K = 5 (il numero di successi)
  • X ≥ 2 (almeno due casi di successo, richiede il maggiore/uguale)

P(X≥2) = P(X≤1) = 1 - (P(X=0) + P(X=1))

1-(50)(12-54-0)(124)-(51)(12-54-1)(124)=1-(74)(124)-5(73)(124)

Dal momento che un coefficiente binomiale si calcola così:

(mn)=m!n!m-n!

e che

(m0)=1

e che

(m1)=m

otteniamo che

  • (74)=35
  • (73)=35
  • (124)=495

Con qualche passaggio otteniamo:

1-35495-5*35495=1933

Variabili aleatorie continue

Mentre le variabili discrete (in cui il campione può essere solo un numero intero, come il lancio di un dado o il numero di pecore) si possono studiare una ad una, anche se il numero può velocemente diventare immenso (es. la probabilità di vincere al lotto) e il campione può essere infinito, le variabili continue hanno un tipo di infinito legato a una proprietà dell'insieme ℚ che si estende a ℝ: c'è sempre un numero tra due numeri distinti.

Per questo, gli strumenti per affrontare il calcolo delle probabilità di un evento esprimibile in modo continuo (es. la distanza tra due auto) devono essere diversi.
Un ruolo chiave ha l'integrale: se alle elementari si spiega la statistica con torte e fette (che non sono altro che integrali in coordinate polari), all'università si rispolverano quegli integrali che - o perché la funzione ha un dominio limitato o perché l'integrale è improprio, arrivano comunque ad avere una superficie di 1.

Infatti nel calcolo della probabilità una delle caratteristiche dell'integrale è che non può mai avere valori negativi. Che senso avrebbe, infatti, una probabilità negativa? Per questo è possibile considerare un integrale alla stregua di un'area - cosa che in analisi non si può fare - in cui due punti distinti x1 e x2 appartenenti al dominio denotano un'area che rappresenta la probabilità che l'esito della variabile sia compreso tra x1 e x2. Questa superficie si chiama densità di probabilità.

La funzione di ripartizione P(x) indica la probabilità da 0 a x, con x ∈ [0, 1]. Dal momento che, come già detto, la funzione integranda non può assumere mai valori negativi, la funzione di ripartizione è sempre crescente e li limite di P(x) per x tendente a -∞ è 0 e il limite per x tendente a +∞ è 1. Infine, P(x) è continua a destra.

Varianza

Parliamo di varianza. La varianza è un indice di quanto gli esiti si differenzino dalla media. Per esempio, se lancio un dado tre volte e ottengo 2, 4, 6, poi ripeto l'esperimento e ottengo 4, 4, 4, la media in entrambi i casi è 4, ma la varianza è diversa. Se sommassi semplicemente gli scarti tra la media e ciascun esito, otterrei zero in entrambi i casi (-2 + 0 + 2 e 0 + 0 + 0).
La varianza si calcola facendo la differenza tra due elementi: il primo è la somma di tutti i quadrati dell'esito per la probabilità che possa verificarsi (nel nostro esempio, 22*1/6 + 42*1/6 + 62*1/6, raccogliendo 1/6 si ottiene (22 + 42 + 62) * 1/6, cioè 56/6 = ˜9,33333. L'altro elemento è il quadrato del valore atteso.
Il valore atteso è la somma degli esiti possibili per ciascuna probabilità: 1*1/6 + 2*1/6 + 3*1/6 + 4*1/6 + 5*1/6 + 6*1/6. In questo caso specifico, ogni esito ha una probabilità uguale a quella degli altri, quindi si può raccogliere 1/6 e scrivere (1+2+3+4+5+6)/6 = 3,5.
La varianza di questo caso è 9,33333 - 3,5 = 5,83333.

Nel caso di una variabile continua, occorre trovare la differenza tra due integrali, uno che rappresenta la superficie associata al quadrato della variabile e l'altro al quadrato di tutto l'integrale. Si ottiene questa formula:

Ax2fxdx-Axfxdx2
dove A è lo spazio campionario.

Moda

La moda di una variabile aleatoria discreta è molto semplice da calcolare: è il valore (o i valori) più ricorrente.

La moda di una V.A. continua è data dal massimo assoluto (o dai massimi, se più di uno) della funzione.

Mediana e quantili

La mediana è il valore a metà dello spazio campionario. Se lo spazio è discreto ed è composto da un numero pari di elementi, se ne prende la media dei due centrali.

Esempio 1: un dado ha come esiti possibili 1, 2, 3, 4, 5, 6; la mediana è data dalla media di 3 e 4, cioè 3,5.
Esempio 2: le età dei colleghi dell'ufficio sono {24, 30, 33, 45, 55, 62, 65}. La mediana è il valore centrale (45)

Un quantile è il valore che si trova con una suddivisione diversa dalla metà. Per esempio, il percentile rappresenta ciascuno degli elementi che si trovano a cavallo tra 1/100 del campione e il campione successivo (es. il valore a metà tra 34/100 e 35/100)

Riflessioni sulla probabilità

Quante probabilità ci sono di fare 6 lanciando un dado non truccato una volta?

Una su sei! Questo è ovvio. E quante probabilità ci sono di fare 6 lanciandolo due volte? Se lanciandolo una volta è 1/6, lanciandolo due volte sarà 1/6 + 1/6, cioè 2/6.

E invece no. Se lanciassimo un dado sei volte, infatti, ci sarebbero 6/6 probabilità di ottenere 6, e l'esperienza ci insegna che non è così. In realtà, la probabilità di ottenere un sei lanciando un dado sei volte è un po' meno di 2/6, così come lanciandolo tre volte è minore di 3/6 e così via. In questo modo si arriva a lanciare 6 volte un dado e a ottenere una probabilità alta, ma non certa, di ottenere un sei.

OK, questo corrisponde all'esperienza, ma allora qual è il ragionamento corretto da fare?
Facendo un rapido conteggio, le probabilità che esca sei con un lancio sono 1/6 (˜0,33333):

1
2
3
4
5
6 *

Ma se lancio due dadi le probabilità che venga fuori almeno un sei sono 11/36 (˜0,30555):

1 1
1 2
1 3
1 4
1 5
1 6 *
2 1
2 2
2 3
2 4
2 5
2 6 *
3 1
3 2
3 3
3 4
3 5
3 6 *
4 1
4 2
4 3
4 4
4 5
4 6 *
5 1
5 2
5 3
5 4
5 5
5 6 *
6 1 *
6 2 *
6 3 *
6 4 *
6 5 *
6 6 *

In pratica, considero un esito positivo solo la coppia di sei, che pesa per 1/36 sugli esiti.
Cosa succede se lancio un dado tre volte? E se lo lancio 1000 volte?
Se lo lancio tre volte posso ancora contare, su 216, il numero di esiti da "scartare", che sono quelli in cui il 6 compare due o più volte, da considerare come un esito solo: 1 6 1, 1 6 2, 1 6 3, ... , 6 6 6. Ma quanti sono? Il conto diventa un po' impegnativo.

Conviene invece contare gli esiti negativi e sottrarli da 1. Così nel caso di un lancio 1/6 deriva da 1-5/6, mentre il caso di 11/36 (numero un po' più "difficile") deriva da uno meno le probabilità che NON esca il sei: 5/6 * 5/6 = 25/36.
Con tre lanci, il numero di probabilità che NON esca 6 è di 5/6 * 5/6 * 5/6 = 125/216, quindi le probabilità che esca un sei sono 1-(125/216) = 91/216 = (˜0,42130).
Con mille lanci, la probabilità che non esca mai il sei è 1 - 5^1000 / 6^1000 = 6,58800 preceduto da 80 zeri (0,00000000000000000000000000000000000000000000000000000000000000000000000000000000658800).
Improbabile, ma non impossibile.

Concludo con una considerazione. Il lancio delle monete non ha memoria, per cui l'esito precedente non influenza in alcun modo quello successivo. Ma in questo ragionamento, il fatto che esca un sei al primo lancio influenza l'esito del lancio successivo: se esce sei, il secondo lancio è ininfluente!

1 => 1/6 di probabilità che tra il primo e il secondo lancio esca almeno un 6
2 => 1/6 di probabilità che tra il primo e il secondo lancio esca almeno un 6
3 => 1/6 di probabilità che tra il primo e il secondo lancio esca almeno un 6
4 => 1/6 di probabilità che tra il primo e il secondo lancio esca almeno un 6
5 => 1/6 di probabilità che tra il primo e il secondo lancio esca almeno un 6
6 => 1 di probabilità (100%) che tra il primo e il secondo esca almeno un 6