M.o.r.o. appunti/riassunto

Concettini teoria Moro

Regione ammissibile

Regione ammissibile = Insieme dei vettori che soddisfano i vincoli.

k = {x ∈ Rⁿ | g_i(x) ≤ 0, ..., g_n(x) ≤ 0} ∀ i.

L_x ∈ k = Soluzioni ammissibili.

Insieme convesso

Insieme convesso ⇔ λx + (1-λ)y ∈ A con x,y ∈ A e x ∈ [0, 1].

Funzione convessa

Funzione convessa.

Il suo epigrafo epi(f) è convesso.

con epi(f) = { (x,t) ∈ Rⁿ⁺¹ | t ≥ f(x)}.

Convesso se ∀(x,y) con F(λx + (1-λ)y) ≤ λf(x) + (1-λ)f(y).

Linea con cui circondo (perso) soluzioni ottime. Locali globosi.

Gradienti e insiemi di livello

Gradienti di f(x).

∇f(x) = ( ∂f(x)/∂x₁, ..., ∂f(x)/∂x_n ) Vettore dei gradienti derivati parziali.

Insieme di livello.

L_h,f = f^-1(h) = {x ∈ dom(f) : f(x) = h} con h ∈ Im_f.

Algoritmi direzioni ammissibili

Algoritmi direzioni ammissibili.

• Metodo gradiente.
• Metodo Newton.

Ottimizzazione lineare

Ottimizzazione lineare.

F: Rⁿ → R lineare F(x) = C^t x = C₁ x + C₂x ² ... C_nxⁿ.

max/min y objective.

Forma standard

Max/min C^t x.

s.c. A x = b.

x ≥ 0.

Forma generale

Max C^t x.

s.o. D x ≤ b_i.

s.o. A x = b_i.

x ≥ 0.

x il libero≠ Obiettivo inammissibile limitato.

Come passare da gen. a standard?

Tramite: Variabili di scarto/surplus (max non negative).

grafica monte insegnanti.

Illuminato: curve D.L. personalizzate.

Concettini teoria Moro

Regioni ammissibili

Regioni ammissibili = insieme dei valori che soddisfano i vincoli.

Insieme convesso

Insieme convesso ↔ λx + (1-λ)y ∈ A con x,y ∈ A e λ ∈ [0,1].

Funzione convessa

Funzione convessa il suo epigrafe epi(ƒ) è convesso.

massimo ∈ convesso.

epi(ƒ) = {(x,y) : y ≥ ƒ(x)}.

minimo convesso ↔ minimo locale = minimo globale.

Gradiente e algoritmi

Gradiente di F(x).

Insieme di livello.

Algoritmi direzioni ammissibili:

• Metodo gradiente.
• Metodo Newton.

Ottimizzazione lineare

Ottimizzazione lineare.

G: Rⁿ → R lineare F(x) = C^Tx = C₁x₁ + C₂x₂ ... C_nx_n.

K = R lineare g_i(x) ≥ 0.

Forma standard ↔ Forma generale.

Tra mitt. variabili di scarto/surplus non negative.

Poliedro, politopo e vincoli

Politodi.

Vincolo.

Funzione obiettivo.

Poliedro.

Politoo.

Insieme vincoli attivi: I = {i: a_ix = b_i} in x ∈ Rⁿ.

Soluzione di base se in x sono m vincoli linearmente indipendenti composti vari {2i: i ∈ I} = h.

Lo ammissibile.

Soluzione di base ammissibile (vertice = estremo).

In forma standard sono:

U_S = {h∈l} = ^n!⁄_{m! (n-m)!}.

Proprietà standard

Prop. standard.

A = [B|D] B base d.a.

max m.

min (n-m)→ x = (x_B, x_D) → B^-1D x_D = b.

con x_D = 0.

Ammissibile se x_B = B^-1b ≥ 0.

Ogni base B determina un'unica x₀ s.d. base, ma non conv. lineare → se 2 x_B corrispondono più basi, x_B degenerata.

(variabile di base ≥ più di 2 vincoli).

* Detto poliedrico F: {x ≥ Rⁿ | A x ≤ b}, Più avanti si percono d.v. di insieme che non ammettono in A esistono n vett. ind.

Teorema fondamentale e metodo del simplesso

Teo fondamentale ottimizzazione → Se un problema in F. standard è ammissibile → esiste una sol. di base ammissibile, è esso ottimo → almeno quello è una sol. ottimale.

Metodo del simplesso.

Scegli base → B = [B_inv] D = [f₀] → → solo assoc. aux.

x_B = B^-1b.

Calcoli B^-1P.

C _o = B^-1b – B^-1D x₀.

Σ^-1 = (concorda).

C^-1 → (C_BB^-1b + (C_D &nd