M.o.r.o. appunti/riassunto

Concettini Teoria Moro

• 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 ⇔ λx + (1-λ)y ∈ A
  • con x,y ∈ A e x ∈ [0, 1]
• 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 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
  • Metodo gradiente
  • Metodo Newton
• 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 = insieme dei valori che soddisfano i vincoli
• INSIEME CONVESSO ↔ λx + (1-λ)y ∈ Acon x,y ∈ A e λ ∈ [0,1]
• FUNZIONE CONVESSA il suo epigrafe epi(ƒ) è convessomassimo ∈ convesso               epi(ƒ) = {(x,y) : y ≥ ƒ(x)}               minimo convesso ↔ minimo locale = minimo globale
• GRADIENTE DI F(x)
• INSIEME DI LIVELLO

• ALGORITMI DIREZIONI AMMISSIBILI:
  • METODO GRADIENTE
  • METODO NEWTON
• 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/SURPLUSnon negative
• 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)!}

Prop. standard

A = [B|D] B base d.amax mmin (n-m)

→ x = (x_B, x_D) → B^-1D x_D = bcon x_D = 0Ammissibile 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.

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