Ricerca Operativa - Appunti

RICERCA OPERATIVA

• Si occupa di problemi di ottimizzazione di un obiettivo in presenza di risorse limitate
• Costruzione di ottimizzazione su problema di massimo/minimo su un'eguaglianza definita da vincoli

Relazioni base per cambiare segni e relazioni:

• < > < =
• > < < =
• < < < =
• Max f(x) < Min(-f(x))

Nota: Un vincolo può essere sempre espresso in forma normale (x ∈ R)

Fasi di un problema di ricerca operativa:

1. Raccolta dati (definizione obiettivo, vincoli)
2. Costruzione modello matematico (individuazione variabile)
3. Studio problema nel modello e cerco soluzione ottima
4. Costruzione algoritmo
5. Risoluzione numerica
6. Feedback

Programmazione Lineare (PL)

Tipi di problemi di PL:

• Produzione (massimizzare guadagno entro certi limiti)
• Dieta (minimizzare costi rispettando assunzioni nutrizionali)
• Misceleazioni (miscelare frazioni di componenti entro costi e guadagni)
• Assegnamento (assegnare componenti a risorse rispettando)
• Trasporto (ottimizzare costi e tempi di trasporto)

Problema di PL un problema di minimizzazione o di massimizzazione di una funzione con dei vincoli e con i seguenti segni.

Regione ammissibile: è area dello spazio R dominata dai vincoli possibili dove si intersecano le relazioni possibili del problema complesso questo ottimo.

Descritta da poliedri: Insiemi convessi (a un insieme K ⊂ Rⁿ si dice convesso se è scelti due punti x₁,x₂ ∈ K si ∀λ ∈ [0,1]: λx₁ + (1-λ)x₂ ∈ K

Combinazione Convessa

Un punto x ∈ ℝⁿ si dice combinazione convessa di x₁,...,x_k∈ℝⁿ se x = ∑ λ_i x_i con λ_i ∈ [0, 1] e ∑ λ_i = 1

Il più piccolo insieme conv(K) contenente tutti questi punti si dice l'involucro convesso di K (relativo dimensione spazio K presente)

Coni

Un insieme K∈ℝⁿ si dice cono se contiene il punto diverso dall'origine e contiene tutte le semirette passanti dall'origine e dai punti di K.

Combinazione Conica

x = ∑ λ_i x_i, con λ_i ≥ 0 Può essere convesso o non convesso.

È il più piccolo insieme concav(K) che può contenere tutte queste combinazioni lineari, dove K è detto conico (l'involucro conico)

Poliedro

Intersezione di un numero finito di semispazi chiusi di ℝⁿ

Un disco chiuso di ℝⁿ è l'insieme definito dalle disequazioni lineari in variabili:

A x ≤ b con A ∈ ℝ^{m x n}, b ∈ ℝ^m

può essere limitato o non limitato

Vertice di un Poliedro

Punto del poliedro che non si può esprimere con combinazione convessa di altri punti del poliedro

Teoria della dualità

Abbiamo un problema di PL in formato primale standard

(P) = ^{max cx}

• Ax ≤ b

ad esso possiamo associare un problema del tipo

(D) = ^{min yb}

• yA = c
• y ≥ 0

N.B. Come

φ = ^{Ax ≤ b}

viene detta "poliedro primale" duale

φ = _{yA = c}

• y ≥ 0

viene detta "poliedro duale"

Teorema della dualità forte

Siano prolemi (P) e (D) e due problemi

allora sono due punti ottimali se problemi (P) e (D) sono

equivalenti:

max cx = min yb

• Ax ≤ b
• yA = c
• y ≥ 0

Circolo dei vertici

Per trovare vertici di si possiamo pensare di portarlo

in forma primale, molto piu semplice.

Infatti vediamo che la matrice A è la stessa

e continuiamo in modo

N.B. C1 + yv

^{(s Problema di caricamento}

dove esempio un contesti con vincoli misti ottimizzando spazio, costi, guadagno

max cx

V(pex) = { Vx ≤ b

x ∈ Rⁿ₊ } ⇒

max cx

questo relazione vale sempre

x ∈ Zⁿ aggiunge vincol

Relazioni su un problema di PLI

max cx

• soluzioni ammissibile del problema di PLI
• soluzioni del problema continuo è il più estesa.

detto "relazione superiore" V_s

Il gap V_s-V_z dà l'errore che stiamo commettendo

Costruzione modello matematico

• Vincoli -> bisogna rispettare le bilanc

• Funzione obiettivo -> minimizzare il costo di trasporto

Esempio

Dal grafo precedente

unit cx

x₁₂ - x₁₃ - x₁₄ = -5

x₁₂ - x₁₃ + x₂₅ = -8

x₁₃ - x₂₃ - x₃₅ = 3

x₃₄ + x₅₄ = 6

x₂₅ - x₃₅ - x₅₄ = 4

x ≥ 0

x ∈ ℝ

• Vincolo irrilevante

Problema di PLI

Matrice di incidenze

• Equivale alla matrice A del problemi di PLI

• Indica gli archi della rete

• Ogni componente può essere {0,-1,0,+1}

Esempio

Dal precedente

• (r₁, r₂), (r₃), (2,3) (2,5) (3,1) (3,5) (5,4)

1 -1 0 0 0 0 0 1 0 -1 1 0 0 0 0 0 1 0 -1 1 0 0 0 0 0 1 0 1 -1 0 0 -1 0 -1 1

Potenziali su setti non capacità

l'arco di copertura ω = dimensione universale

π_b E_k = c_k (sequenza di base) ogni r_k

• ϵ_ij = < π
• ϵ_ij = τ

Visita anticipata dalla radice su serie per trovare il vettore π

Primo e potenziale π_k = 0 si percorre l'albero di apertura fino alla foglia, calcolando i potenziali con la formula vista sopra

π_i ϵ< c_ij  => π_i - π_j <c_ij ∀(i,j)∈ E

N.B. π_r può essere imposto arbitrariamente: si fara' sono differenze di potenziale e sono univoci potenziali legati all'albero di copertura

N.D. Costi ridotti

• c*_ij = c_ij + π_i - π_j
• c*_ij> 0 ∀(i,j) ∈ T
• c*_ij>0 ∀(i,j) ∈ T