Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
vuoi
o PayPal
tutte le volte che vuoi
Programmazione lineare e ottimizzazione combinatoria (IP e G)
- Programmazione Lineare Integra (modello matematico che si possono risolvere coi algoritmi)
- Ottimizzazione Combinatoria (matematica discreta)
➣ Teoria delle decisioni: modelli e metodi a supporto delle decisioni
- Gambel (Gestione e pianificazione)
- Incer (Criterio) (decisione impossibile)
Poliedro: Intersezioni di semi-spazi
Ripasso
Def. Norma Euclidea
P=(P1, P2, …, Pn)
|P| = √j=1∑nPj2
Oss. Metodo algebrico
N scalare, Vk è Rn
Dipendenti: Assolutamente
Dimostrazione:
|d|P| = √1∑j=1 (N-Pj)2 = √n (NP)j =√nj=1 NPj2 = |N| |P|
Dato 2 punti
p = (p1, p2, …, pn)
w = (w1, w2, …, wn)
- p · w = Σj βj wj
- p · w = w · p
- p (w + t) = p w + p t
- (λ p) · w = λ (p · w)
- p · p ≥ 0, ∀ p ∈ Rn
- p · p = 0 ⇔ p = 0
- ||p|| = √p · p
- ||p||2 = p · p
-
OSS.
p · w ≤ ||p|| · ||w|| Diseguaglianza di Cauchy-Schwarz
Dimostrazione
- Se p = 0 e w = 0 (o entrambi) è vera
- Se p ≠ 0 e w ≠ 0
- Definiamo l'insieme di punti: u = α p t β · w con α, β ∈ R
- u · u = α2 p2 − 2αβ p · w + β2 w2 =
- = α2 ||p||2 + 2β p · w + β2 ||w||2
- = α2 ||p||2 − β = p · w
Scelgo α ≈ p
Scegliendo = ||w||2 ||p − α ||w||2 =
Se ||w||2 ||u||2 = ||p||2 ||p · w
||w||2 (p · w)2 ≤ ||w||2 ||p||2 ||w||2
OSS:
Per ogni n ∈ ℕ, n ≥ 4
∑j=1n j = 1/2 (n2 + n)
dimostrazione:
∑j=1n j = (1/2(n(n + 1)) = 1/2(∑j=1n j
OSS:
∀n ∈ ℕ, n ≥ 1
∑j=1n j (j-1) = n2
dimostrazione:
∑j=1n j (j-1) = 1/2(∑j=1n j
PROGRESSIONE GEOMETRICA:
una sequenza di numeri tale che il rapporto tra un termine e quello che lo precede è costante
(a partire dal secondo)
la costante si chiama RAGIONE DELLA PROGRESSIONE GEOMETRICA
Se a è il primo termine e b il secondo:
- il termine in posizione j = |abj−1|
- se b > 1, termini crescono
- se b < 1, termini decrescono
Oss:
Dati m insiemi convessi Fi con i ∈ {1, 2, ..., m} ci sono intersezione F = ∩i=1m Fi è un insieme convesso
Dimostrazione:
Per ogni 2 punti p, r ∈ F = ∩i=1m Fi ⇒ p ∈ Fi ∀ i ∈ {1, ..., m}
r ∈ Fi ∀ i ∈ {1, ..., m}
Dato che tutti gli insiemi Fi sono convessi, ∀ λ ∈ (0,1)
λp + (1-λ)r ∈ Fi ∀ i ∈ {1, ..., m} (la combinazione convessa appartiene a tutti gli Fi e quindi anche alla loro intersezione)
⇒ λp + (1-λ)r ∈ ∩i=1m Fi
⇒ λp + (1-λ)r ∈ F e F è convesso
L'unione di insiemi convessi non è necessariamente un insieme convesso!
Funzioni scalari quadriche
Dati n valori qij∈ℝ con i,j∈{1,2,...,n}, la funzione
f:ℝn→ℝ f(x) = xTQx si chiama funzione scalare
Quadratica
In forma matriciale:
Q = q11q12... q1n q21...q2n ......... qn1... qnn X = x1 x2 ... xn
La matrice Q è una matrice quadrata o simmetrica
- se per qualunque i≠j qij= qji → scrivo qij+= qji/2
DEF. Una matrice Q∈ℝn×n è semidefinita positiva se
- xTQx ≥ 0, ∀x∈ℝn
oss. Data una matrice quadrata Q∈ℝn×n, se Q è SDP, allora la funzione scalare quadratica
- f:ℝn→ℝ, f = xTQx è convessa
Dimostrazione
Se Q è SDP, per ogni coppio di punti p ∈ v , n ∈ ℝ abbiamo che (q - v) = q (v) ≥ 0
xTQx = vTQv+pTQw-wTQw-pTQw-
Per ogni o ∅(0.1), moltiplicando per v(o-1) ≥ 0:
N(q - m)pTQp + d(1 - n)wTQw - 1(d-1)pTQw ≥ 0
N(q - m)pTQp+ d(1- n)wTQw-
Dato che f(x) è convessa
f(x̅) ≤ f(x) ≤ λf(x̅) + (1-λ)f(x)
f(Nx̅+(1-N)x̅) = x̅ come combinazione convessa
- Dato una funzione convessa, un punto di minimo globale diventa punto di minimo locale
Teorema
Data una funzione convessa f: F⊆ℝⁿ→ℝ, se un punto è di massimo locale allora è un punto di massimo globale
Se x̅∈F è un punto di massimo locale allora esiste un intorno sferico N(x̅;δ) con δ>0 tale che
f(x̅) ≥ f(x), ∀ x∈(N(x̅;δ)∩F)
Dato che F è convesso, ∀ x ∈ F esiste x̂ ∈ (N(x̅;δ)) e N∈[0,1] tale che:
x̂ = Nx̅+(1-N)x̅
Dato che f(x) è convessa: f(x̅) > f(x) ≥ Nf(x̅) + (1-N)f(x̅)
- f(x̅) ≥ Nf(x̅) + f(x̅) + (1-N)f(x̅)
- f(x̅) ≥ f(x̅)
Se la matrice AB è invertibile allora è una base di IRm
Contiene m colonne linearmente indipendenti
Data una base B:
- Basic Variable (variabili di base): sottoinsieme di m variabili
XB = {xi, i ∈ {1,...,n} : xi ∈ B}
- Non Basic Variable (variabili fuori base): sottoinsieme di n variabili
XN = {xj ∈ {x1,...,xn | j ∈ N}
Data una base:
ABx = [AB AN] [xB] = ABxB + ANxN = bMoltiplico per AB⁻¹ a sinistra:
AB⁻¹ ABx + AB⁻¹ ANxN = AB⁻¹bI = AB⁻¹ AB xB + AB⁻¹ AN xN = AB⁻¹ b
xB = AB⁻¹ b - AB⁻¹ AN xN
(1) —> abbiamo scritto il variabile di base in funzione di quello fuori base
Da F.O.: Z = cTx = [cB cN] [xB] = cBxB + cNxN
= (cB AB⁻¹ b - AB⁻¹ AN xN)
= cB AB⁻¹ b + (cB⁻ cT AB) xN
(2)
Possiamo definire il dizionario:
{xB = b̄ - Ā xN (m equazioni) {Z = z̄ + c̄TxN (1 equazione)dove
b̄ = AB⁻¹ b Ā = AB⁻¹ AN z̄ = cB AB⁻¹ b c̄jT = cBT AB⁻¹ AN
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
