Quaderno ricerca operativa

RICERCA OPERATIVA

È una disciplina matematica che ha come oggetto la definizione di modelli e la messa a punto di metodi per la soluzione di problemi decisionali che si manifestano in diversi ambienti della vita reale. Nel caso specifico del corso si tratterà essenzialmente di operazioni di ottimizzazione.

FASI DI UN PROCESSO DECISIONALE

Le principali fasi di un processo decisionale sono:

• Analisi del problema
• Costruzione di un modello
• Analisi del modello
• Soluzione numerica
• Validazione del modello

PROBLEMA DI OTTIMIZZAZIONE

Definizione

Consideriamo una funzione reale f: ℝⁿ → ℝ e un insieme S ⊆ ℝⁿ, un problema di Ottimizzazione (P) consiste nel determinare, se esiste, un punto di minimo della funzione f tra i punti dell'insieme S, ovvero:

{min    f(x)   {subject to   x ∈ S

• x ∈ ℝⁿ viene chiamato vettore delle variabili di decisione
• f viene chiamata funzione obiettivo
• S viene chiamato insieme ammissibile
• x ∈ S rappresenta una soluzione ammissibile

Un modo analogo per formulare il problema si fonda sulla seguente uguaglianzamin (f(x)) = − max(−f(x))che indica il fatto che i problemi di massimo e minimo sono equivalenti a meno del segno.Da questa osservazione si può riformulare il problema come segue{max    − f(x)    {subject to    x ∈ S

Definizioni fondamentali del problema di ottimizzazione

Il problema di ottimizzazione (P) si dice inammissibile seS = ∅

cioè se non esistono soluzioni ammissibili.Il problema di ottimizzazione (P) si dice illimitato se∀ > 0 ∃ ∈ tale che f(x) < −M

Il problema di ottimizzazione (P) si dice che ammette soluzione ottima se∃^* ∈ tale che f(x^*) ≤ f(x) ∀ ∈ Il punto x^* è detto soluzione ottimale globale e il corrispondente valore f(x^*) si dice valore ottimo.

Classificazione dei problemi di ottimizzazione

Si parla di problemi di ottimizzazione continua quando le variabili possono assumere tutti i valori reali (x ∈ ℝⁿ), nel caso S = ℝⁿ si parlerà di ottimizzazione non vincolata mentre nel caso S ⊂ ℝⁿ si parlerà di ottimizzazione vincolata. Si parla invece di ottimizzazione discreta quando le variabili sono vincolate ad essere numeri interi (x ∈ ℤⁿ), nello specifico si parla di ottimizzazione a numeri interi se S ⊆ ℤⁿ.

Problemi di programmazione matematica

Descrivendo l'insieme ammissibile S come un insieme di disequaglianze

S = {x ∈ ℝⁿ: g₁(x) ≥ b₁, g₂(x) ≥ b₂, ..., gₘ₍ₓ₎ ≥ bₘ}

dove gᵢ: ℝⁿ → ℝ, bᵢ ∈ ℝ, per ogni i = 1, ..., m.

Ogni disequaglianza gᵢ(x) ≥ bᵢ prende il nome di vincolo e l'insieme ammissibile è formato da tutti quei

punti x ∈ ℝⁿ che sono soluzione del sistema di disequaglianze:

• g₁(x) ≥ b₁
• g₂(x) ≥ b₂
• ...
• gₘ(x) ≥ bₘ

Il vincolo di disequaglianza gᵢ(x) ≤ bᵢ può essere riscritto come −gᵢ(x) ≥ −bᵢ.

Da questa osservazione si ha che un vincolo di eguaglianza tipo gᵢ(x) = bᵢ può essere espresso come la

1. gᵢ(x) ≥ bᵢ
2. −gᵢ(x) ≤ −bᵢ

Attributi dei vincoli

Un vincolo di disequaglianza gᵢ(x) ≥ bᵢ si dice:

• soddisfatto: se gᵢ(x) ≥ bᵢ in un punto x;
• violato: se gᵢ(x) < bᵢ in un punto x;
• attivo: se gᵢ(x) = bᵢ in un punto x;
• ridondante: se la sua eliminazione non modifica l'insieme ammissibile.

Dalla rappresentazione dell'insieme ammissibile è possibile esprimere il problema di programmazione

matematica come segue

• min f(x)
• s. t.
• g₁(x) ≥ b₁
• g₂(x) ≥ b₂
• ...
• gₘ(x) ≥ bₘ

Quando le funzioni f, g₁, ..., gₘ sono tutte lineari il problema (P) si definisce problema di programmazione

lineare.

Problema di programmazione lineare in forma ridotta

Considerando inoltre n coefficienti reali c₁, ..., cₙ è possibile riscrivere la funzione obiettivo come

f(x) = f(x₁, ..., xₙ) = x₁c₁ + x₂c₂ + ... + xₙcₙ = _nΣ_j=1 cⱼxⱼ

Analogamente considerando una matrice m x n di coefficienti reali

Trasformazione problema di programmazione nella forma standard

Dato un problema di programmazione lineare generale in un problema di programmazione lineare nella forma standard, ovvero un problema tale che esso abbia soli vincoli di uguaglianza e variabili vincolate in segno. Il primo passo per effettuare tale trasformazione sarà quello studiare il problema di massimizzazione.

Problema di massimizzazione

Per una qualunque funzione f(x), e un qualunque insieme ammissibile Ω, si ha

        max_x∈Ω(P) f(x) = − min_x∈Ω(P) f(x)

Il punto di ottimo x* del problema di massimo coincide con il punto di ottimo del problema di minimo ed i valori ottimi dei due problemi sono opposti in segno

        x* = arg max_{x ∈ Ω(P)} f(x) = arg min_{x ∈ Ω(P)} (−f(x))

Il secondo passo da effettuare è quello di andare a trasformare i vincoli sotto forma di disuguaglianze in uguaglianze.

Vincolo di ≤

Supponendo di rappresentare con a_i^T x ≤ b_i la generica diseguaglianza dei vincoli del problema di programmazione lineare che si vuole trasformare nella forma standard. Andando a definire la variabile ausiliaria ( di slack) come

        s_i = b_i − a_i^T x

e trasformiamo il vincolo nell'uguaglianza

        a_i^T x + s_i = b_i ,    s_i ≥ 0

Vincolo di ≥

Supponendo di rappresentare con a_i^T x ≥ b_i la generica diseguaglianza dei vincoli del problema di programmazione lineare che si vuole trasformare nella forma standard. Andando a definire la variabile ausiliaria ( di surplus) come

        s_i = a_i^T x − b_i

e trasformiamo il vincolo nell'uguaglianza

        a_i^T x − s_i = b_i,    s_i ≥ 0

Proprietà sulle variabili ausiliarie

Considerando un punto x ∈ ℝⁿ:

• se s_i = 0 allora il vincolo i è soddisfatto ed attivo in x;
• se s_i > 0 allora il vincolo i è soddisfatto ma non attivo in x;
• se s_i < 0 allora il vincolo i è violato in x;

Variabili libere in segno

Il passo successivo è quello di introdurre i vincoli in segno per tutte le variabili del sistema. In particolare, se sono presenti variabili libere in segno, ovvero variabili tali che non hanno un vincolo in segno, è necessario effettuare opportune manipolazioni. Posta una variabile non vincolata in segno x_j.

Posso introdurre le due variabili non negative x_j⁺, x_j⁻ e ottenere così

        x_j = x_j⁺ + x_j⁻ ,        x_j⁺ ≥ 0 ,    x_j⁻ ≥ 0

Sostituendo nella funzione obiettivo e nei vincoli, si eliminerà la variabile libera in segno e al suo posto compariranno due variabili vincolate in segno.