Metodi di Ottimizzazione

CAPITOLO 1 - INTRODUZIONE

Modelli matematici: Il modello è una struttura costruita per evidenziare le caratteristiche di oggetti reali. Alcune volte sono concreti, altre volte astratti, come ad esempio i modelli matematici, cioè insiemi di relazioni che descrivono fenomeni reali in modo semplificato.

I modelli matematici possono essere prima di tutto suddivisi in: modelli stocastici (se descrivono problemi influenzati da eventi casuali) e modelli deterministici (se descrivono grandezze esatte).

Si possono però suddividere anche in modelli statici, se le relazioni tra le grandezze restano invariate nel tempo, e modelli dinamici, se così non accade.

Oss. 1: La costruzione del modello matematico consiste nel tradurre una serie di relazioni logiche tra le grandezze reali coinvolte in termini matematici. È necessario allora applicare leggi fisiche, economiche e di mercato tradotte in equazioni algebriche, disequazioni, funzioni, ecc...

Oss. 2: L'approccio modellistico di un problema reale viene realizzato attraverso diverse fasi: analisi del problema (si fissa l'obiettivo da raggiungere dopo aver fatto un'analisi della struttura del problema), costruzione del modello (si descrivono matematicamente le principali caratteristiche del problema), analisi del modello (si deducono le proprietà matematiche del modello), soluzione numerica (si definisce un algoritmo per determinare la soluzione del problema), validazione dei risultati (si verifica la congruenza dei risultati numerici rispetto ai dati sperimentali di cui si è in possesso).

Classici Problemi di Ottimizzazione:

Problema di miscelazione: Una fonderia deve produrre 1000 pezzi del peso di un chilogrammo. Il ferro con cui tali pezzi sono fatti dovrà contenere manganese e silicio nelle seguenti quantità: 0,45% di manganese, 3,25% di silicio ± 5,5%. Sono disponibili tre tipi di materiale ferroso, inoltre si può aggiungere direttamente manganese (al costo di 10€/kg).

Il problema che si vuole modellare è quello di determinare il peso da produrre che minimizzi il costo del materiale utilizzato.

A questo scopo introduciamo le variabili X₁, X₂, X₃, X₄ aventi il seguente significato:

• X₁ ≥ 0 ⇒ 1 kg di ferro A da utilizzare;
• X₂ ≥ 0 ⇒ B;
• X₃ ≥ 0 ⇒ C;
• X₄ ≥ 0 ⇒ manganese da utilizzare.

Abbiamo imposto il vincolo di non negatività, ma ce ne saranno altri da rispettare.

• X₁ + X₂ + X₃ + X₄ = 1000 → Il numero totale di kg prodotti deve essere pari a 1000.
• 0,04 X₁ + 0,01 X₂ + 0,006 X₃ → quantità in kg di silicio presente nel prodotto risultante, che deve poi essere compreso nei limiti voluti: 32,5 ≤ 0,04 X₁ + 0,01 X₂ + 0,006 X₃ ≤ 55.
• 0,0045 X₁ + 0,5 X₂ + 0,4 X₃ + 100 X₄ ≥ 450 → Condizione sulla percentuale di manganese.
• 0,0025 X₁ + 0,030 X₂ + 0,018 X₃ + 10 X₄ → Costo complessivo del prodotto risultante.

CAPITOLO 2: PROGRAMMAZIONE LINEARE

Introduzione: I problemi di ottimizzazione hanno la seguente forma:

max/min_x∈S f(x)

con f funzione f: Rⁿ → R

La funzione Z=f(x₁, x₂, ..., x_n) è detta funzione obiettivo mentre x₁, x₂, ..., x_n sono le variabili decisionali.

Un punto x∈S è detta soluzione ammissibile, mentre, se S = ∅, il problema è detto inammissibile.

Tra i vari problemi di ottimizzazione è possibile distinguere i seguenti tipi:

1. Ottimizzazione continua, se le variabili possono assumere valori reali, ovvero x∈Rⁿ. In particolare si ha Ottimizzazione vincolata se S⊂Rⁿ e Ottimizzazione non vincolata se S = Rⁿ.
2. Problemi di Ottimizzazione discreta, se le variabili possono assumere valori interi ovvero x∈Nⁿ. In particolare si parla di Programmazione intera se S⊂Nⁿ e di Programmazione binaria se le variabili decisionali possono assumere come valore solo 0 e 1.
3. Problemi di Programmazione mista se alcune variabili possono assumere valori interi mentre le altre possono assumere valori reali.

Assi: Se f(x) è lineare, cioè è del tipo Z=c₁x₁+c₂x₂+...+c_nx_n, e se anche i vincoli sono lineari, allora il problema di ottimizzazione viene detto problema di programmazione lineare.

Essa riguarda la pianificazione di alcune attività al fine di ottenere il risultato migliore, cioè l'uso ottimale delle risorse disponibili.

Se i vertici adiacenti non sono una soluzione migliore di un determinato vertice, allora tale vertice è la soluzione ottima.

ES:

Se il valore della funzione obiettivo in A è maggiore dei valori in B e C, allora il vertice A è la soluzione ottima.

• C = 18
• B = 18
• A = 24 Sol. Ottima

Metodo del Simplesso:

1. È un metodo iterativo: consiste in una serie di passi in cui si effettuano le stesse operazioni;
2. Consiste nel visitare i vertici della regione ammissibile spostandosi lungo gli spigoli (ovvero tra vertici adiacenti) in cui la funzione obiettivo aumenta;
3. Il metodo si ferma quando non ci sono vertici adiacenti migliori di quello corrente;
4. Il metodo inizia la ricerca dall'origine, che è sempre un vertice ammissibile.

Esempio: max z = 3x₁ + 5x₂

• x₁ ≤ 4
• 2x₂ ≤ 12
• 3x₁ + 2x₂ ≤ 18
• x₁, x₂ ≥ 0

Sommiamo ora all'equazione (0) l'equazione (2) moltiplicata per 5:

• (0) z - 3x₁ - 5x₂ = 0
• [(2) x 5] 5x₂ + 5/2 x₄ = 30

(0') z - 3x₁ + 5/2 x₄ = 30 *

Ora abbiamo i seguenti valori: x₃ = 4, x₂ = 6, x₅ = 6, z = 30.

La nostra BFS è la seguente: (0, 6, 4, 0, 6). Tale BFS è la soluzione ottima di: z = -3x₁ + 5/2 x₄ + 30.

Effettuando il 4° passo (Test di ottimalità) sulla nuova funzione obiettivo si deduce che è necessaria una seconda iterazione poiché il coefficiente di x₁ è positivo infatti la variabile entrante deve essere proprio x₁. Per calcolare la variabile uscente dobbiamo effettuare il test del minimo rapporto tra le equazioni (1), (2), (3).

• (1) x₃ = 4 - x₁ ≥ 0 → -4 - x₁ ≥ 0 → x₁ ≤ 4
• (2) x₂ = 6 > 0 → nessun vincolo (x₂ non può uscire dalla base)
• (3) x₅ = 6 - 3x₁ ≥ 0 → -x₁ ≤ 2

Tra x₃ e x₅, x₅ è il primo che arriva a 0 e quindi esce dalla base.

Trasformiamo il sistema in forma canonica. Sommiamo le equazioni (0) e (3), ottenendo:

• (0) z - 3x₁ + 5/2 x₄ = 30
• (3) 3x₁ - x₄ + x₅ = 6

(0') z + 3/2 x₄ + x₅ = 36

Il tableau del metodo peltiano è diventato:

ITERAZIONE 2

Siamo giunti pertanto alla soluzione ottima (0, 39/8, 3/8, 0, 0, 0), in cui la funzione obiettivo vale Z=84/8.

Scelta della variabile entrante e di quella uscente: si fa riferimento alla cosiddetta Regola di Bland, che afferma: "quando esiste un'alternativa (o più alternative) nella scelta della variabile entrante o uscente conviene scegliere quella con l'indice più piccolo".

Esercizio:

max Z = 4x₁ + 5x₂ + 3x₃ + 5x₄

• x₁ + x₂ + x₃ + 2x₄ <= 12
• 3x₁ + 2x₂ - x₃ + 2x₄ <= 6
• x₁ + x₂ - 3x₃ + 2x₄ <= 10
• x₁, x₂, x₃, x₄ >= 0

Scriviamo il problema in forma aumentata:

• max Z = 4x₁ + 5x₂ + 3x₃ + 5x₄
• x₁ + x₂ + x₃ + 2x₄ + x₅ = 12
• 3x₁ + 2x₂ - x₃ + 2x₄ + x₆ = 6
• x₁ + x₂ + x₃ = 10
• x₁, x₂, x₃, x₄, x₅, x₆ >= 0