Ricerca Operativa - Appunti

RICERCA OPERATIVA

• Si occupa di problemi di ottimizzazione di un obiettivo in presenza di risorse finite
• Modello di ottimizzazione == problema di massimo/minimo su una regione definita dai vincoli

Relazioni base per cambiare segni e relazioni

• f(x) = -f(x)
• _max f(x) = - _min (-f(x))
• ¯(x) = x^*/_x = 1

Fasi di un problema di ricerca operativa

1. Raccolta dati (formulato obiettivo, vincoli)
2. Costruzione modello matematico (individuato variabile)
3. Studio problematiche del modello e cerco soluzione ottima
4. Costruzione algoritmo
5. Risoluzione numerica
6. Feedback

Note: Funzione obiettivo, vincoli, e altri termini tecnici sono definiti nel glossario alla pagina precedente.

Programmazione Lineare (PL)

Tipi di problemi di PL

• PRODUZIONE: massimizzazione guadagno dato certi limiti
• DIETA: minimizzazione costi – materiali
• MISCELAZIONE: miscelare componenti riducendo costi e posizioni
• ASSEGNAZIONE: assegnare persone-tasks
• TRASPORTO: ottimizzare costi e flussi di trasporto

Problema di PL: un problema di minimo o di massimo di una funzione lineare su uninsieme di vincoli con relazioni f(x), ^{k ε R}

Regione ammissibile: è aria dello spazio ^{IRV definita daivincoli su cui consideriamo il funzionamento tramite le possibilità o le serie di possibilidue problemi connessi ottimali}

Descritta da POLIEDRI → INSIEMI CONVESSI (C: un insieme K∈IRᵈ si dice convesso se scelti due punti X,Y di K al passare vale λX +(1 - λ)Y ∈ K ∀λ ∈ [0,1]

RICERCA OPERATIVA

• Si occupa di problemi di ottimizzazione di un obiettivo in presenza di risorse limitate.

↳ Modello di ottimizzazione = problema di massimo/minimo su una regione definita da vincoli.

• ↳ relazioni base per cambiare segni e relazioni:

• ≤ ↔ ≥

• ≥ ↔ ≤

• max f(x) = -min (-f(x))

• ↳ FASI DI UN PROBLEMA DI RICERCA OPERATIVA

• 1) RACCOLTA DATI (situazione obiettivo, vincoli)

• 2) COSTRUZIONE MODELLO MATEMATICO (individuò variabili)

• 3) STUDIO PROPRIETÀ DEL MODELLO & CERCO SOLUZIONE OTTIMA

• 4) COSTRUZIONE ALGORITMO

• 5) RISOLUZIONE NUMERICA

• 6) FEEDBACK

N.B. Funzione obiettivo, vincoli e altri termini tecnici sono definiti nel glossario al pagine precedente.

PROGRAMMAZIONE LINEARE (PL)

• ↳ Tipi di problemi di PL:

• PRODUZIONE → massimizzare guadagno dato certi vincoli

• DIETA → ottimizzazione costi

• MISCELE → minimizzare l’impiego complessivo di certi costi e raggiungere certi livelli di qualità.

• ASSEGNAZIONE → assegnare risorse/persone a compiti

• TRASPORTO → ottimizzare costi e tempi di trasporto

• ↳ Problema di PL → problema di minimizzazione o di massimizzazione di una funzione obiettivo lineare (f(x)) e sono lineari con riferimento ai x_i ≤ ∞.
• ↳ REGIONE AMMISSIBILE → area dello spazio Rⁿ determinata dai vincoli Rappresenta l’insieme delle soluzioni possibili del problema, convesso, quindi ottimo.

descritta da POLIEDRI → INSIEMI CONVESSI:

(L)’un insieme K ⊆ Rⁿ si dice convesso se scelti due punti x₁, x₂ li appartiene vuo

λx₁ + (1-λ)x₂ ∈ K ∀ λ ∈ [0,1]

Combinazione Convessa

Un punto x ∈ ℝⁿ si dice combinazione convessa di x₁, ..., xₖ ∈ ℝⁿ se

x = ∑λᵢxᵢ con λᵢ ∈ [0,1] ∑λᵢ=1

È il più piccolo insieme contenente x₁, ..., xₖ che per sequenziale combinazioni convesse contiene anche tutti i punti di conv(x) e si chiama involucro convesso dell'insieme dei precedenti (x)

Coni

Un insieme K ⊆ ℝⁿ si dice cono se, contenendo un punto diverso dall'origine, contiene tutta la semiretta passante dall'origine ad esso.

Combinazione Conica

x = ∑λᵢxᵢ con λᵢ ≥ 0

(può essere convessa o non convessa)

È il più piccolo insieme con₀(K) ⊆ ℝⁿ che per sequenziale combinazioni coniche contiene anche tutti i punti di con(x) e si chiama involucro conico dell'insieme dei precedenti (x)

Poliedro

Intersezione di un numero finito di semispazi chiusi di ℝⁿ

Gᵢ è detto semispazio chiuso di ℝⁿ l'insieme descritto da una disequazione lineare in n variabili:

a·x ≤ b con a ∈ ℝ