Appunti Ricerca operativa

SISTEMI OPERATIVI

La RICERCA OPERATIVA studia i sistemi complessi; utilizza un approccio scientifico che comprende passi fondamentali:

• Prima comprensione del sistema da trattare
• Familiarizzare col problema, descrivendo il sistema in termini matematici
• MODELLO MATEMATICO = astrazione matematica che descrive il sistema attraverso relazioni matematiche. Ci possono essere diversi modelli matematici per descrivere lo stesso sistema. Bisogna cercare un compromesso tra l’accuratezza del modello e la possibilità di risolverlo numericamente.
• Soluzione del modello matematico e verifica di esso tramite analisi sperimentale
• Eventuali modifiche al modello

Per un modello di OTTIMIZZAZIONE bisogna identificare:

• VARIABILI → grandezze controllabili da noi (non confondere con i parametri dati del problema)
• VINCOLI → relazioni esistenti tra le variabili nel sistema reale
• FUNZIONE OBIETTIVO → criterio di valutazione di una soluzione

PROBLEMI DI OTTIMIZZAZIONE

È una coppia ⟨X, f⟩ dove:

• X ⊂ ℝ^m è un insieme (regione ammissibile)
• f: X→ℝ è una funzione (funzione obiettivo)

m = numero di variabili (= no di decisioni da fare)

Non posso prendere tutte le coppie!! Risolvere il problema = determinare un punto (soluzione obiettivo) nel quale la funzione assume il valore minimo, ossia determinare x* = arg min{f(x) : x ∈ X} x* ∈ X.

Una soluzione è un vettore x = (x₁, x₂, ..., x_m) ∈ ℝ^m → è ammissibile se e solo se x ∈ X

Nel caso di un problema in cui la funzione obiettivo deve essere

massimizzata, si usa questa trasformazione:

max{f(x): x ∈ X y} = - min{-f(x); x ∈ X y}

Soluzione di un modello

Risolvere un modello: determinare un vettore x* ∈ X tale che

{f(x*) ≤ f(u), ∀y ∈ X

⇒ x* è un ottimo globale

Un problema di ottimizzazione può avere più di una soluzione ottima.

Ottimo locale

un vettore x* ∈ X tale che

{f(x*) ≤ f(u), ∀y ∈ X with ||x*-y|| = ρ per ρ>0 è arbitrario

2 casi particolari:

• X = ∅ → nessuna soluzione ammissibile ⇒ il problema è impossibile e
• si pone min{f(x); x ∈ X y} = ∞
• f è illimitata inferiormente sull'insieme X ⇒ il problema è illimitato

(migliore) e si pone min{f(x); x ∈ X y} = -∞

Classificazione dei modelli

• Programmazione non lineare (NLP) → nessuna restrizione sulla forma di f e
• classe + generale di problemi di ottimizzazione
• difficili da risolvere (nei valori troppo tempo)
• si può esplorare solo ottimi locali (punto per il quale è possibile
• determinare un intorno e quell'intorno è un ottimo).

• Programmazione convessa (CP) → X è un insieme convesso e f è
• una funzione convessa
• un insieme X ⊆ R^m è convesso se, per ogni x,y∈X e λ∈[0,1] si
• ha λx+(1-λ)y ∈ X (il segmento deve far parte dell'insieme X)
• X ⊆ R^m è convesso ⇒D x ∩ y convesso (φ è un insieme
• y ⊆ R^m è convesso

x ∪ y non è convesso

• Se immaginiamo che ogni cibo j possa essere acquistato solo in confezioni (e non sfuso) → x_j = numero di confezioni di cibo j da acquistare → modi di variabili devono essere intere → il problema diventa di ILP (+difficile da risolvere)

x_j ≥ 0 INTERA j = 1,...,m

PROGRAMMAZIONE LINEARE

• modo + semplice per modellare un sistema
• Da funzione obiettivo e tutti i vincoli sono definiti da funzioni che sono lineari rispetto alle variabili decisionari
• modelli matematici “facili” da risolvere
• si basa sulle seguenti assunzioni:

• PROPORZIONALITÀ → il contributo di ciascuna variabile a ogni funzione è costante e proporzionale al valore assunto dalle variabili
• ADDITIVITÀ → ogni funzione è espressa solo come somma delle variabili
• DIVISIBILITÀ → le variabili possono assumere anche valori non interi (x_j , x_k divisibili k≠j → non si influenzano)

VINCOLI IN MODELLI MILP

• vincoli di BUDGET : le risorse *sono illimitate, ma ne esiste una massima quantità disponibile (≤)
• vincoli di QUANTITÀ MINIMA : alcune risorse devono essere utilizzate almeno ad un certo livello (≥)
• vincoli di BILANCIAMENTO : alcune risorse devono essere utilizzate ad un certo livello fisso; in anticipo (=)
• vincoli di “INCOMPATIBILITÀ” : alcune decisioni sono incompatibili tra loro (sono RI)
• vincoli LOGICI O DISGIUNTIVI : alcune risorse devono essere utilizzate rispettando dei vincoli logici (sono PLI)

VINCOLI:

1. ∑_j=1^m w_jx_ij ≤ W_i, i = 1, ..., m

   → ogni oggetto inserito nel contenitore i ha un contributo in peso

   → vado per ogni contenitore

   → ci sono tanti vincoli quanti sono i contenitori

2. x_ij ∈ {0,1}, i = 1, ..., m j = 1, ..., m

3. ∑_i=1^m x_ij = 1, j = 1, ..., m → ogni oggetto (se ne ho uno)

MODELLO MATEMATICO:

M(RP) = → max ∑_i=1^m ∑_j=1^m p_jx_ij

1. ∑_j=1^m w_jx_ij ≤ W_i i = 1, ..., m
2. ∑_i=1^m x_ij ≤ 1 j = 1, ..., m
3. x_ij ∈ {0,1} i = 1, ..., m j = 1, ..., m

PROBLEMA DEL BIN PACKING

• Dati: insieme M = {1, ..., m} di contenitori (bin) identici, ciascuno con capacità W_i, insieme N = {1, ..., n} di oggetti, ogni oggetto j è caratterizzato da un peso W_j > 0;
• Problema: determinare un impaccamento degli oggetti nei contenitori in modo che:
• ciascun oggetto sia inserito in un contenitore
• la somma dei pesi degli oggetti inseriti in ciascun contenitore non ecceda la capacità W_i;
• il numero dei contenitori utilizzati sia minimo
• Assunzioni:
1. w_j ≤ W ∀ j = 1, ..., m nessun oggetto il cui peso superi la capacità del bin può essere inserito in un unico contenitore
2. m = m senza a garantire l'esistenza di almeno una soluzione ammissibile
• Per scrivere la funzione obiettivo occorre andare in uno spazio dimensionale almeno superiore (una variabile p contenitore)

PROBLEMA DEL SET PACKING (SrPk)

• Uguale al set covering ma:
• un vettore di dimensione m di profitti [p_j]
• per ogni riga i=1,..,m, esiste al massimo una colonna j ∈ {1,..,m} di colonne..... il profitto complessivo sia massimo
• x_j=1 se la edomanda i è servianata (j=1,..,m)
• 0 altrimenti

MODELLO MATEMATICO (SrPkP)

λ̅ = max. _j=1,..m∑ p_jx_j

∑_j=1,..,m a_ijx_j ≤ 1 i=1,..,m

x_j∈{0,1} j=1,..,m

Set covering, set partitioning, set packing

ANALOGIE

• Tutte le variabili x_j sono binarie
• Tutti i coefficienti a_ij sono 0-1
• Tutti i termini noti b_i dei vincoli valgono 1

DIFFERENZE

• il senso dei vincoli ≥,=,≤
• il segno della funzione obiettivo: min, min, max
• l'esistenza di una soluzione ammissibile: SCP: facile da verificare, SEP: difficile da verificare
• SPkP: la soluzione x_j=0 ∀j è sempre ammissibile