M.o.r.o. appunti/riassunto

Concettini teoria Moro

• Regione Ammissible (X) = insieme dei punti che soddisfano i vincoli

K = {x ∈ Rⁿ | g_i(x) ≥ 0, g_n(x)=0} ∀i

L ⊆ K = Soluzioni Ammissibili

L_o insieme (forse) soluzioni ottime locali/globali

Epigrafa f(x) convesso convesso con epi(f) = { (x,μ) | x∈A, μ≥f(x) }

L_o → se funz. convessa = minimo locale = minimo globulo

• Grabbitute di f(x) ∇f(x) = (∂f(x)/∂x₁,...,∂f(x)/∂x_n) vettore aumenti possibilità
• Istrione di livelle L_f,p = {f(x) = c | c ∈ dom(P): f(x) =k } con |h = Imp

• Algoritmi direttori ammissibili

• 1. Metodo Gradienti
  2. Metodo Newton

• Ottimizzazione Lineare

F: Rⁿ → R lineare f(x) = c^Tx = C₁x₁ +C_nx_n

g(χ) :Ax = b max/min

Standard forma massima c_Tx

s.o: X ∈ Rⁿ; Ax ≤ b; x≥0

• Forma standard max/min c^Tx

s.o. Ax = b X ≥ 0

• Grafica monoite

3D poliopol P = {x+ ∈ Rⁿ :Aχ ≤ b } → Se anche => Politofo limitato

Vincolo attivo → le funzioni di dei in un punto

insieme rangi attivi = I = {j : x_j = 0 }_{in x∈Rⁿ}

soluzione di base se in x sono attivi n vincoli linearemente indipendenti ovvero tanti {j,i: I(j) ⊆ h

se ammissibile = soluzione di base ammissibile

v = vertice = estremo a

in forma standard sono

v_n^h = h! / m! (h - m)!

PROB. STANDARD

A = [B‖D] B> base d.i.

x = (x_B, x_D)

→ Bx_B + Dx_D = b

→ x_B = B^-1 b

solv. di base associa a B

con x_D = 0

ammissibile se x_B = B^-1b ≥ 0

dato poliedro (P: x ∈ Rⁿ: Ax ≥ b). Possono avere al più m l.i. indp dentro un sistema m > n esistono n l.i. indip.

ogni base B determina un unica X₀ s.d. base (ma no conv. l.gerarch.) se 2 XB corrispondono a più basi

X_B degenere → variabile in base ≥ 0 più di 1 nullo

con poliedro l.i. standard non vuoto (bottone) ha almeno

1 SDB ammissibile

TEO. FONDAMENTALE OTTIMIZZAZIONE F standard è ammissibile

esiste una sol. di base ammissibile, {t.} di esse ottimo almeno quella è una soli ottimale.

METODO DEL SIMPOSO

• scelto base → B: (l,n) D: [l ^due] → sol.
• calcolare B^-1 D = x_D
• x_B = B^-1b - B^-1 Dx_D (o calcolato di f.)
• z_j(nuova): c_BB^-1b + (c_D - c_BB^-1D) x_D → scelgo var. da togliere
• calcolo (n var da andare in base) = min:
• (x)
• z =
• ... sostituisco o D calcolaro
• coeff vn.₁ entrati in base
• optimo → < 0

  un prob in E.S. max soluzione ottimale l'ottimalità fino colluzione ottimale

  (*) θ tale che z_θ = 0

  max (Y) x_y1 ? min Y_i

  max y_j = x_B

  x₁= 0

  sol.x_AT = 0

  Ottimizzazione nei grafi

  h=n= nodi m=r= archi

  Definizioni:

  • Vertici adiacenti: se sono gli estremi di un arco
  • Archi adiacenti: condividono un vertice
  • Grado di un vertice: numero dei vertici usciti
  • Archi multipli

  Teorema

  Somma gradi sui nodi = 2 * numero degli archi

  Corollario

  Il n° dei nodi di grado dispari è pari

  Rappresentazione matriciale

  • Matrice di incidenza
  • Matrice di adiacenza

  Definizioni

  • Cammino: sequenza di vertici dove ogni coppia consecutiva condivide un arco
  • Cammino elementare: se non usa due volte lo stesso arco
  • Cammino semplice: se non usa due volte lo stesso nodo
  • Ciclo: cammino di coordinazione >= 3 in cui origine = destinazione
  • Grafico connesso: se ogni coppia di nodi è connessa da un cammino

  Definizioni di taglio

  Modelli matematici per project

  • Risorse illimitate
  • Bilanciamento tempi-costi
  • Deadline

  Progetto a risorse limitate

  Domanda di risorse per a m t

  Formulazione: min D