Appunti Ottimizzazione nei sistemi di controllo 1

Ottimizzazione

L’obiettivo di un problema di ottimizzazione è quello di trovare un vettore di variabili decisionali x in modo tale che una funzione obiettivo sia minimizzata o massimizzata. In un problema di ottimizzazione dinamica, le variabili decisionali e altri parametri che definiscono il problema generalmente variano nel tempo:

• per cause esterne
• in conseguenza di scelte precedenti in modo non intento e non banale

L’ottimizzazione dinamica è caratterizzata da una funzione obiettivo cumulativa e da vincoli dinamici (prendere decisioni nel passato condiziona le possibilità di minimizzare/massimizzare la funzione obiettivo).

Lot sizing

Il problema consiste nel decidere quanto e quando produrre un certo bene per soddisfare una domanda (nota D). Si hanno:

• costi fissi di produzione A_k
• costi di immagazzinamento h_k

con x_k lotti in magazzino, u_k lotti prodotti, p_k costi di produzione al tempo k, M limite di produzione e

η(u_k) = { 0 u_k = 0 1 u_k > 0}

I vincoli in rosso esprimono in maniera esplicita l’evoluzione temporale della variabile. Al crescere di N (N →∞) la soluzione ha un numero di vincoli sempre più grande da considerare (diventa impossibile da computare).

I vincoli in rosso hanno dunque la natura di un sistema dinamico

x_k+1 = x_k + u_k - d_k   k ∈ ℕ

x₀ = 0

e dunque l'evoluzione temporale delle variabili coinvolte deve essere rappresentata in modo implicito attraverso l'utilizzo di modelli dinamici.

Inoltre, poiché l'orizzonte temporale del modello deve essere arbitrariamente lungo ma anche arbitrariamente fitta (le decisioni devono poter essere prese anche in intervalli di tempo molto ridotti), i modelli dinamici (lineari) da considerare sono quelli a tempo continuo

x(t) = Ax(t) + Bu(t)   t ∈ ℝ

x(0) = x₀

da cui a posteriori si potrà pensare ad una situazione fisica con una discretizzazione della variabile temporale.

Si vogliono dunque trovare delle politiche di controllo in retroazione che siano ottime rispetto a dei funzionali di costo cumulativi che pesano contemporaneamente lo sforzo di controllo u e il risultato ottenuto x. In particolare, la programmazione dinamica fornisce condizioni necessarie e sufficienti per un controllo ottimo.

PUSH (che agiscono successivi di j), che aggiorna la stima sulla base della stima del nodo j attuale, confrontando per ciascuno dei successori di j la stima attuale con il precursore che passa per j.

Problema dello zainetto

Consideriamo uno zainetto di capacità (volume) K. Possiamo riempire lo zaino con un numero intero di oggetti x_i:

L'obiettivo è quello di massimizzare il valore dello zainetto:

P(N,K) = { N Σ v_i·x_i ≤ k i=1 x_i ≥ 0 , x_i ∈ N i = 1,...,N

In questo problema lo sfruttamento della programmazione dinamica ovviene con la considerazione che la scelta di aggiungere o meno l'oggetto x_i (e in che misura) influenza la capacità di inserire oggetti in futuro.

La soluzione algoritmica prevede di risolvere una sequenza di

Valendo dunque il principio di ottimalità e possibile scrivere anche in tal caso un'equazione ricorsiva che descriva il valore massimo ottenibile.

In questo esempio si introduce uno stato che evolve dinamicamente: la variabile y_t è il volume libero dello zainetto. Allora l'equazione dinamica che descrive questo stato è:

y_k+1 = y_k - v_K

con y₀ = K, e y_k ≥ v_k. Per scrivere l'equazione che caratterizza la soluzione ottima si definisce V(y), il valore massimo ottenibile dato il volume y (dunque V(0) = 0):

V(y) = _{ max | {c_x + V(y-v_K) }, ∀ y ∈ {1,...,K}

in I e le colonne in J.

Si parla di minore principale se I=J. Si parla di minore

principale dominante di ordine k se I=J e I e J contengono

ordinatamente le prime k righe e colonne.

Supponendo M simmetrica, per il criterio di Sylvester:

M è definita positiva se e solo se (equivalentemente):

• Tutti gli autovalori di M sono positivi;
• Tutti i minori principali dominanti sono positivi.

M è semidefinita positiva se e solo se (equivalentemente):

• Tutti gli autovalori di M sono non negativi;
• Tutti i minori principali sono non negativi.

Controllo ottimo lineare quadratico (LQ)

Estendere al numero di decimale all'infinito vuol dire che in

ogni istante di tempo in cui dobbiamo prendere una decisione,

il numero di possibili decisioni è infinito.

Ci troviamo così a considerare un sistema lineare a tempo

discreto con x_k ∈ ℝ^m, u_k ∈ ℝ^m e k ∈ ℤ nella forma

x_k+1 = A_kk + Bkx_k0 x₀

L'indice di costo da minimizzare è quadratico rispetto alle

componenti x, u.

J(u_.) = Σ^N+1_k=0 (x^t_kQ_kx_k + u^t_kR_ku_k) + x^t_NS_Nx_N

con:

• Q ∈ ℝ^{n x m} simmetrica e semidefinita positiva;
• R ∈ ℝ^{n x m} simmetrica e definita positiva;
• S ∈ ℝ^{n x m} simmetrica e semidefinita positiva;

Per il principio di ottimalità, quello che sa lo stato x_N raggiunto

dal processo al tempo N-1 sotto l'azione del controllo ottimo

il valore di u_N-1 (l'ultimo comando di controllo) che rende

minimo l'intero indice di costo J deve essere tale da ottenere

un costo residuo J nell'intervallo [N-1, N] minimo (cioè

deve essere tale da minimizzare il problema ristretto).

X_k Q X_k = [ X_1,k X_2+1,k ] Q [ X_3+1,k ]² Q [0 0] = Q [ ]

S = [1 0] [0 0]

[ ] A + B u_k -> A = [1 1] B = [0] [ X_3+1,k + X_1+1,k] [ ] u_k + U_k ^k[U_k + U_k] -> [ ] [ X_3+1,k U_k U_k + U_k ]

P₃ S = [1 0] [0 0]

P₂ = Q + λP₃A = A^TP₃B (R + B^{⟩ P₃ B)⟩+1 B⟩ P₃A = Q + [ ]T [ ] [ ] o] = [0 1] Q [ ] A Q 1 [0 1]. [0 1] = [0 1]}

[0 1] = [1+ ] [0 1] = [1 0]

= [0 1] [0 0] ^{+1 [. 0 -} = [2 1] [1 2]

Per calcolare P₁ R + B^TP₂B - 1 + [0 1] [ 1 1] [0] = 1 = 1 + 2 - 3 -> (R^TB^TP₂B)^-1 = 1/3

P₁ = [0 0] + 1 [1 1] [1 1] [1 1] [1 1] [1 1] [1] [0 1] [0 1] [1] [0 1] [1] [1 0] [0 1]

[1 1] [1 0] = [0 1] + 1 [5 2] [1 1] [3 1] [1] [3 1] = [ 1/3] [1 0] = [3 1]

[0 0] [5 2] [1 9 3 ] [3 1]

P₀ = [3 2] [1 5 1] [2 3]

[ ] [2 1][2] 24/8 [2 5] [2 3.5 ]= 2[0]

[ ] [ ]

J(u^k) = x₀^T P₀ x₀ - [1 0] ][3 2/1] [ ] 1 [0] = 3 [2 21/8 ] [0]

Calcolare ora la sequenza ottima u^k: u_k = (R^TB^TP₂B)^-1 = B^TP₂A x₀ = (1 + 5/3⁴ [0] [2 1] [1 1] [1] [ ] [1 5/3] [1 5 [0] ]