Appunti completi di Metodi di Ottimizzazione della Ricerca Operativa

Ottimizzazione

Modello & Rappresentazione realtà

È rappresentazione selettiva (soggettiva) realtà

Viene ideato per analizzare/interpretare da un punto di vista astratto il funzionamento di un sistema

• Analogico = rappresenta per analogia
• Iconico = resa sotto forma simboli
• Simbolico = realtà tipo linguaggio

Modelli descrittivi = atti in ingresso non con certezza

Modelli decisionale = atti in ingresso noti con certezza

Statica / Dinamica

Fasi principali

1. Identificazione - sintomi e cause
2. Formulazione - mentalizzazione - indici di valutazione - variabili di decisione (incognite) - parametri, numerici (noti) - relazioni matematiche
3. Sviluppo - realizzazione risoluzione efficace
4. Collaudo - correttezza atti - soddisfatti/solidarità realtà

   Probabilità/verosimiglianza delle conclusioni cognitive

Problemi Di Ottimizzazione (Esempio)

1. Problema del commesso viaggiatore
   • TSP: Travel Salesman Problem
   • min d(H) = c(i,j) * presenza cammino
   • ciclo = passare una volta

Modelli di Ottimizzazione Matematica

• Supponiamo:

• Vettore xⁱ = (x₁, x₂, ..., x_m) di variabili di decisione
• Funzione obiettivo f: Rⁿ → R
• Vincoli g_i (x) ≤ 0, ∀_i = 1, 2, ..., m

• Regione Ammissibile

Insieme di vettori (punti) che soddisfano i vincoli

K = {x^e ∈ Rⁿ : g_i(x) < 0, ∀_i ? }

- vettori x^e sono detti soluzioni ammissibili

- K = ∅ → problema è irrealizzabile

Soluzione Ottimale

x^e è una soluzione ottimale globale se :

f(x^e) < f(y) ∀ y ∈ K (per pose/inf mini)

x^e = {x^e} È detto valore ottimale globale

Problema di ottimizzazione illimitato

• Un problema ammissibile è tendenzialmente illimitato se: →
• Un problema ammissibile è superiormente illimitato se: →

• Problema di max può essere visto come problema di min e viceversa

Tipi di Ottimizzazione

• Lineare – prevede tutte relazioni matematiche rappresentate da operatori lineari
• Non lineare (macrositiva)
• Intera (binaria) – ammissibili o variabili di decisione che suppongono solo valori interi oppure un valore binario
• Problemi:
  • Vincolato
  • Non vincolato

Vincoli

• Fisici – suggeriscono, riesci (hard)
• Tecnologici – limiti di capacità (digest)
• Di consistenza logica – legami logici tra variabili
• Di area spazi di ricerca – riduzione regione ammissibile
• Vincoli su obiettivi decisionali

• A = 1 se pross. viene realizzata
• 2 o 1 no

• Dei realizzare A, non realizzato B
• Variabile legate – vincolo A+B ≤ 1

Ottimizzazione multi-obiettivo

• Obiettivi possono essere tanti e in conflitto tra loro (trade-off)
  • Con priorità
  • Senza priorità
• Non f(x) e g(x) due obiettivi da minimizzare
  • Bisogna raggiungere un compromesso

1) Senza Priorità

• • Minimizzazione della somma pesi dei due obiettivi

2) Con Priorità

• Ipotesi: limiti obiettivo
  • riduzione regione ammissibile
  • Cerca le soluzioni di 2° obiettivo
    • Minimizzare messo dentro soli limiti obiettivo

Osservazioni

• Se l'ottimale attuale → sempre una soluzione attuale ottimale se si verifica nella regione ammissibile
• Se la soluzione ottimale di un problema ai punti limite può non esistere unica
• Problemi malcondizionati → reg. ammissibile vuota, vincoli in conflitto
• Problemi illimitati → direzione in cui la regione ammissibile è illimitata

Regione ammissibile illimitata ` cond.necessaria per l'illimitatezza (ma non sufficiente)

Vincoli

1. Attivi: Si dice attivo in un punto x, y se le coordinate soddisfano vincola come uguaglianza
2. Inattivi → niente diseguaglianza in un punto
3. Ridondanti → rge sono presenti-assenza non ha effetto sulla soluzione ottimale non altera regione ammissibile

Geometria Problema Standard

• In forma standard a due dimensioni è un punto →
• In tre dimensioni è una retta (intersez. ai piani)

Più di 3? Non lo so.

Concetto utile M-N=2 (variabili - vincoli) → Numero di gradi di libertà

Iperpiani

1. Separatore: Separa in maniera all'interno elementi dei che devono soddisfare un sole sottopassi diversi
2. Di supporto:

H è iperpiano ai supporto di P nel punto se:

• P ∩ rep; æ → _x ^y
• Di æ = b²

Condizione poliedro-piano supporto

• P-H viene detto faccia di P
• Se H la dimensione - poliedro

Detto _P è punto estremo se non può essere espresso come punto appartenente ad cui seguaci coni combinazioni dei punti intermi, cioè

• Se ω rep
• Æ è quindi

→ Vertici = punti estremi

CONVERGENZA E CICLAGGIO

Cicloaggo -> scelgo sempre le stesse variabili (se entranti/uscente x il base) e rimani resto

sempre nello stesso vertice -> algoritmi non terminano

Con soluzioni di base degenerati alcune anche variabili indicatrice zero

nessun cambio iteretto

Riaccuso cicloaggo

CONVERGENZA

SCELTA VARIABILE ENTRANTE

1. Si sceglie variabile Xr con cj_r costi ridotto maggiore (mass)
2. Se alcune variabili Xt non ancora selezionaro massare il appariuto Xr (soleci calcoliori variabili gia' Xt)
3. Se degumento alcune variabili ottime Xt avvenuti
4. Si scegli variabile Xr cui T piu' piccola fra le variabile non basiable com r>0 non ancora selezionate in iterazioni precedenti

FASE 1

• Concetto -> stabilire status correnziabilitá del problema
• Problema in forma standard:

  min c^Tx s.a. Ax=b x>0

• Formulazione di un problema ausiliare -> costruiro a partire dal problema principale

  Componenti vettore di: VARIABILI ARTIFICIALI y^p= (y₁, ..., y_m) (m' di rimasti)

  Vincoli: Ax+y=b Condizioni: x>0, y>0 Problema: min |SIGMA_{i=1}^{m| y_i s.a. Ax+y=b x,y>0

• Il problema è AMMISSIBILE quando

  Se una situazione ammissibile del problema -> cioè torna sol ottimale prob. ausiliario ausiliario, in cui proliferazione in composto da 0. x*₀=0

• Risolve il problema ausiliare con FASE 2 -> prob. ausiliaris è sempre ammissibile
• Vertice iniziale (y^p = b)

SEMPLICE E VARIABILI LIMITATE

• Problema con box constraints

min c^Tx s.a. Ax=b x^L

• I LIMITI PER VARIABILI BASE ETIERA:

  Ho la inserzione di base efferia: _B^-1B = B^-1 BdX_B x^P = x_P x_P

  Funzione ottetto: max c═^Tx = max cB^T x_B

• CONDIZIONI OTTIMALITÁ -> Una seleziona di base esterià è ottimale se: Se ogni variabiile non basila fissata al proprio limito impimpo da un cj_r di cotto ridotto negativo o nulla Se ogni variabile non basila fissata al proprio linutto speziate da un c.j_r di costo ridotto positivo o nulla