Appunti Fondamenti di Ricerca Operativa

Fondamenti di Ricerca Operativa (prof. Enrico Malaguti)

• Introduzione

Per affrontare i problemi studiati dalla Ricerca Operativa si adotta un approccio modellistico:

Def: Modello → rappresentazione semplificata della realtà che ne cattura ed enfatizza alcune caratteristiche.

Una tipologia di problemi affrontati dalla R.O. sans quella dei modelli di ottimizzazione. In questi problemi è richiesto di trovare la soluzione "ottima" mediante la massimizzazione/minimizzazione di una funzione definita f. obiettivo.

Def: Funzione obiettivo → f(x): Nⁿ → R

Nella programmazione lineare la funzione obiettivo è una f. lineare e quindi gode delle seguenti proprietà:

1. f(x+y) = f(x) + f(y)   ∀ x,y ε G
2. f(αx) = αf(x)   ∀ x ε G, ∀ α ε R

La soluzione della funzione obiettivo sarà dato da un vettore n-dimensional ottenuto mediante la minimizzazione/massimizzazione di essa. Si avrà una soluzione quando ad ogni variabile che costituisce il vettore è assegnato un preciso valore.

Partendo dalla funzione obiettivo molto spesso i problemi di ottimizzazione richiedono che siano imposti dei vincoli su uno o più parametri in ingresso alla fun. obiettivo. Tali vincoli saranno espressi tramite funzioni g_i:

• g_i: Nⁿ → R t.c. g_i(x) ≤ b_i con i = 1,2,...,n

* OSS: Nei problemi di programmazione lineare la funzione di vincolo sarà sempre una costante quindi i vincoli saranno dati da equazioni/disequazioni lineari.

I generici modelli di ottimizzazione saranno espressi da:

• Def: Generico problema di ottimizzazione

Dati S, f: Nⁿ → R, Funzione obiettivo:

{     max f(x)     g_i(x) ≤ b_i con i = 1,...,n

Visto e considerato che le funzioni obiettive ammetterà in ingresso i parametri si potranno esprimere tale funzioni in forma matematica:

S: Nⁿ → R   c₁x1 + c₂x2 + ... + c_nxn [c₁ c₂ c₃ ... c_n]

^|  x₁ ^|  x₂ ^|  x₃ ^|  ... ^|  x_n

Lo stesso varrà per i vincoli:

^[a₁₁ a₁₂ a₁₃ ... a_1n] ^[a₂₁ a₂₂ a₂₃ ... a_2n] ^[... ... ... ... ...] ^[a_m1 a_m2 a_m3 ... a_mn]

b₁ b₂ ≥  b_m

Modelli di Programmazione Lineare Intera (Mixed Integer Linear Programming)

Il M.I.L.P. costituisce un paradigma di programmazione matematica caratterizzato da:

• funzioni obiettivo lineari.
• variabili delle funzioni in esame intere.

* Oggi è altresì possibile distinguere fra Integer Linear Programming (I.P) e varianti intere di Linear Programming (L.P)

• vantaggi della programmazione lineare:
  • modellizzazione efficiente
  • riutilizzo dei software risolutivi
  • modifiche o riconfigurazione dei problemi
• svantaggi:
  • Impossibilità di contemperare un'eventuale variazione di alcuni parametri

Problema Knapsack

• Dati:
  • si considera un contenitore (Knapsack) di capacità W espressa in peso.
  • sono forniti n oggetti ciascuno caratterizzato da:
    • w_j > 0 peso del j-esimo oggetto.
    • p_j > 0 proposto del j-esimo oggetto.

Requisiti Iniziali:

1. ∑ w_j <= W --> altrimenti il problema diventerebbe banale poiché tutti gli oggetti entrerebbero nel contenitore

2. w_j <= W V_j --> altrimenti il contenitore non potrebbe contenere alcun oggetto.

Obiettivo: Determinare il massimo proposto ottenibile inserendo il massimo numero di oggetti nel contenitore senza oltrepassarne la sua capacità massima

Variabile

• x_j ∈ {0,1} l’“oggetto e” presente nello zaino
• x_j < 0 o > altrimenti

Modello Generale di Problema Knapsack

• * Oggi in qualsiasi problema di ottimizzazione le prove astratto rappresentato da U amare l'esempio quello di selezionare ne adeguata
• * Varianti di Knapsack:
  • KP con vincolo di uguaglianza:
    • ∑ w_j * x_j = W
    j=1

Vector Packing Problem

• Dati
  • Ciacun Bin è dotato di k dimensioni, a ciascuna delle quali si associa una capacità massima W_t (es volumi, peso, ...)
  • Ciacun oggetto Oi consegnato avrà un valore w_i,t che esprime una quantità associata a ciascuna delle variabili dei Bin (tramite il parametro t).

• Modello Generale di Vector Packing

  min ∑ y_c    j=1,...,n   ∑ w_j,t x_c,j ≤ W_t y_c   c=1,...,n   t=1,...,k   ∑ x_c,j = 1   j=1,...,n

• * Osservazione: Il vincolo fondamentale ci permette di verificare che il contenuto di ciascun Bin non oltrepassi per ciascuna delle dimensioni il suo valore massimo espresso da W_t.

Set Covering Problem

• Dati
  • Viene fornita una matrice [m×n] a coefficienti binari a_t,j.
  • A ciascuna colonna di suddetta matrice è associato un costo espresso come un vettore di dimensione n, i cui termini saranno della forma c_t,j.

• Oggettivo: Coprire tutte le n righe della matrice [m×n] usando il minimo costo possibile associato alla scelta delle varie colonne.
• Variabili
  • x_j ∈ {0, 1}   1 <> la colonna j è parte della soluzione e 0 <> altrimenti.

• Modello Generale di Set Covering Problem

  min ∑ c_jx_j   j=1,...,n   ∑ a_t,j x_j > 1   t=1,...,m   x_j ∈ {0,1}   j=1,...,n

• * Osservazione: La matrice fornita come parte del problema è a coefficienti ti binari, cio` significa che: a_t,j ∈ {0,1} t → a_j = {1 <> l-esima riga è coperta dall'elemento 0 altrimenti}

Modello Generale di Capacitated Facility Location Problem

min_{{xij, yi}} (∑_i=1^m ∑_j=1ⁿ f_i y_i + ∑_i=1^m ∑_j=1ⁿ c_ij x_ij)

• ∑_i=1^m x_ij = 1 for j = 1, ..., n
• ∑_j=1ⁿ d_j x_ij ≤ b_i y_i; j = 1, ..., n
• d_j ∈ {0, 1, 3}
• y_i ∈ {0, 1}

* ODS: I vincoli∑ d_j x_ij ≤ b_j y_i sono equivalenti a:∑ d_j x_ij ≤ b_j

* ODS: Nella funzione obiettivo si possono individuare due termini di significato distinto

min (∑_i=1^m ∑_j=1ⁿ f_i y_i + ∑_i=1^m ∑_j=1ⁿ c_ij x_ij)

• Costi variabili: Influenti ai sensi dei clienti
• Costi fissi: Di apertura delle facilità

Soluzione dei Problemi di Programmazione Lineare Intera

Finora abbiamo considerato solo modelli di programmazione intera, cioè caratterizzati solamente da variabili intere e perciò descrivibili tramite uno schema generale:

(p) z_P = min C^T x A_x ≥ d x ≥ 0, intero

• C^T: Vettore trasposto dei costi
• x: Variabile intera
• z_p: Soluzione ottima

È possibile osservare che i vincoli di interezza possono anche essere descritti mediante funzioni (f.d. di vincolo) "non" lineari:

x_i "intera" ≤> sin(πx_i) = 0

x_i "binaria" ≤> 1/2 (1 + cos(πx_i)) = 3/2 - x

• Potremmo quindi dire che la non linearità è "compensata" nella condizione di interezza.
• Da ciò si può intendere che la programmazione lineare intera è intrinsecamente non lineare visto lo considera.