Ricerca Operativa - modulo 1

RICERCA OPERATIVA

• Modulo S. Giordani

Ogni attività manageriale è caratterizzata dalla necessità di dover prendere delle decisioni con grandi rischi e responsabilità, che a causa di:

• della complessità dei settori in cui operano i manager
• delle conseguenze drammatiche di valutazioni/decisioni errate

necessitano di un approccio oggettivo orientato all'ottimizzazione.

Spesso, a causa dell'elevato numero di alternative e di relazioni tra i diversi fattori coinvolti nel processo decisionale, le cose diventano ardue.

• Per aiutare il manager nella fase decisionale è utile fare ricorso a metodi e modelli quantitativi uniti a supporti informatici.

Problemi Decisionali: Tipologie

1. Strategico (Richiede anni)

2. Attività di pianificazione strategica: Obiettivi dell'organizzazione e la loro evoluzione, le risorse necessarie e le politiche da seguire

3. Tattico (Richiede mesi)

4. Attività di programmazione e controllo: Usare le risorse disponibili nel modo più efficace possibile

5. Operativo (Richiede giorni)

6. Attività esecutive: Gestione degli ordini, fabbricazione, logistica interna, e schedulazione delle attività produttive

1. La pianificazione strategica si basa su informazioni esterne (analisi di mercati, sviluppi tecnologici, stime dei costi) e le decisioni sono poco strumentate.
2. La programmazione e controllo richiede di dati aziendali trans congruenti anche nelle anomalie monitarie. Decisioni necessariamente strumentate.
3. Le attività operative richiedono informazioni esatte in tempi brevi, pertanto le decisioni saranno molto strumentate.

La struttura matematica di un problema decisionale diventa via via più debole all’aumentare di:

• Livello di aggregazione del sistema
• Incertezza sugli elementi decisionali
• Giudizi soggettivi nella valutazione
• Orizzonte temporale

Ricerca operativa: definizione e cenni storici

È una disciplina relativamente giovane; nacque nel 1930 e successivamente grazie anche all’avvento dei calcolatori elettronici si diffuse in maniera sempre maggiore. Già nel 1947 venne applicata per sviluppare un algoritmo efficiente per la risoluzione esatta di sistemi lineari.

• Definita in inglese come "management science", la ricerca operativa è una branca dell’analisi applicata usata per esaminare e risolvere problemi decisionali complessi, mediante modelli matematici quantitativi. È di ausilio fondamentale per la gestione di imprese e organizzazioni.
• Def. Problema di ottimizzazione: Trovare la migliore soluzione possibile ad un problema che presenta diverse alternative di risoluzione.
• Def. Programmazione matematica: Ottimizzazione conseguita con metodi matematici. All'interno del modello matematico del solutore possono essere codificati diversi algoritmi.

PROBLEMA DI OTTIMIZZAZIONE

• PER RISOLVERLO BISOGNA MINIMIZZARE (O MASSIMIZZARE) LA FUNZIONE OBIETTIVO
• TROVARE I VALORI OTTIMI DELLE VARIABILI E POI SOSTITUIRE IN f(x).

Desiderando S ∈ ℝⁿ l'insieme delle soluzioni ammissibili avrà:

• IL PROBLEMA DI OTTIMIZZAZIONE È INAMMISSIBILE SE S = ∅
• IL PROBLEMA DI OTTIMIZZAZIONE È ILLIMITATO SE L'INSIEME DELLE SOLUZIONI OTTIME È ILLIMITATO INFERIORMENTE, OVVERO MATEMATICAMENTE:

Per ogni M > 0 ∃ x ∈ S tale che f(x) < –M

Altrimenti, per qualunque soluzioni esistono, ∃ numero una funzione.

• IL PROBLEMA DI OTTIMIZZAZIONE AMMETTE SOLUZIONI FINE SE:

esiste un x* ∈ S tale che f(x*) ≤ f(x) ∀x ∈ S dove:

• x* è detta SOLUZIONE OTTIMA o vettore
• f(x*) è il corrispondente VALORE OTTIMO o valore numerico

• TIPOLOGIE DI PROBLEMI DI OTTIMIZZAZIONE dato x ∈ S:

• PROBLEMA DI OTTIMIZZAZIONE CONTINUA se le soluzioni sono numeri Reali: x ∈ S
  • Vincolata se S ⊂ ℝⁿ
  • Non vincolata se S = ℝⁿ
• PROBLEMA DI OTTIMIZZAZIONE DISCRETA se le soluzioni sono numeri interi: x ∈ S
  • A numeri interi se S ⊆ ℤⁿ
  • Booleana (o binaria) se S ⊆ {0,1}ⁿ [ES.: Sì/NO ON/OFF, …]
• PROBLEMA DI OTTIMIZZAZIONE MISTA Rivista tra variabile continue che discrete

DEF di VINCOLI: LIMITAZIONI DERIVANTI DA CONSIDERAZIONI DI CARATTERE FISICO (ECONOMICO), …

Teoria dei Grafi e Reti di Flusso

L'approccio modernistico fondamentale nei problemi.

La teoria dei grafi è stata introdotta dal matematico svizzero Eulero alla fine del '700, a partire dal problema dei ponti di Koenigsberg.

Esiste un percorso chiuso tale che è possibile tornare nel punto di partenza attraversando tutti e 7 i ponti una e una sola volta?

Rappresentando il problema con un grafo:

d(A) = 3

d(C) = 3

d(D) = 3

d(B) = 3

In questo caso G = (V, E) dove:

• V è l'insieme dei vertici: { A, B, C, D }
• E è l'insieme degli spigoli: { 7 ponti }

Def: Il grado di un nodo d(nodo): numero di spigoli che incidono sul nodo.

Oss: In questo caso il problema di Eulero non ammette soluzioni in quanto vi sono nodi di grado dispari.

Def di circuito euleriano: Tutti i vertici hanno grado pari, è possibile percorrere tutti gli spigoli una e una sola volta per tornare al punto di partenza, ed è connesso.

Def di grafo connesso: Da un nodo è possibile raggiungere tutti gli altri tramite gli archi.

Definizioni grafo

Dato G = (V,E) definisco:

• Spigolo (i,j) ∈ E: lo spigolo che unisce nei vertici i e j
• i e j sono vertici estremi di (i,j)
• Lo spigolo (i,j) è detto incidente ai suoi vertici estremi i e j", e i"), e viceversa
• i e j sono detti adiacenti

• Spigoli che condividono un vertice estremo sono detti adiacenti

• Lista di adiacenza o nodo del vertice i: A(i)
• L è l'insieme dei vertici adiacenti a i: A(i) = {j ∈ V: (i,j) ∈ E}

• Nucleo del nodo i: N[i]
• N[i] = A(i) ∪ {i}

• Dati due vertici u,v ∈ V allora:
• u domina v se la lista di adiacenza di v è sottoinsieme della lista di adiacenza di u: A(v) ⊆ A(u)
• Vertice universale: è un vertice adiacente ad ogni altro vertice di V
• Cono: grafo che contiene un solo vertice universale

• Stella del vertice i: Γ(i)
• L insieme degli spigoli incidenti del nodo: Γ(i) := {(i,j) ∈ E: j ∈ V}

• Grado del vertice i: d(i)
• L è il numero degli spigoli incidenti nel nodo i: d(i) = |Γ(i)|

• Vertice isolato: è un vertice senza spigoli incidenti

• Notazione sul grado di un grafo
• δ(G) = grado minimo di un vertice
• Δ(G) = grado massimo di un vertice

• Def. di grafo regolare: quando tutti i vertici hanno lo stesso grado allora δ(G) = Δ(G)
• In particolare un grafo è k-regolare se il grado dei vertici è k.

OSS: Un grafo completo Kₙ con n nodi è sempre regolare e di grado n-1