Ricerca operativa per le produzioni industriali - Appunti

Ricerca operativa per le applicazioni industriali

La ricerca operativa è la matematica applicata ai problemi economico-organizzativi; si parte, quindi, da un problema reale e si arriva a un modello matematico.

X = (x₁, x₂, …, x_n) → Sono dette variabili decisionali.

f(x) = z → Viene detta funzione obiettivo o funzione reale di n variabili reali; l’esito z rappresenta l’obiettivo da rendere massimo o minimo, a seconda che si tratti di un guadagno o di un costo.

g₁(x), g₂(x), …, g_m(x) → sono dette funzioni di vincolo e possono essere in forma di equazione o di disequazione.

• I) g₁(x) ≤, ≥, = 0
• II) g₂(x) ≤, ≥, = 0
• III) g_n(x) ≤, ≥, = 0

X rappresenta l’insieme ammissibile, cioè è l’insieme su cui vengono soddisfatti tutti i vincoli, quindi si parla di un'ottimizzazione vincolata e quindi di una programmazione.

Programmazione lineare

Esempio di un problema di programmazione lineare:

Max z = 13 x₁ + 23 x₂ (Questa è la funzione obiettivo: si deve affrontare un problema di Max = massimizzazione.)

• I) 5 x₁ + 15 x₂ ≤ 480
• II) 4 x₁ + 4 x₂ ≤ 160
• III) 35 x₁ + 20 x₂ ≤ 1190
• x₁, x₂ ≥ 0 (→ Vincoli di non negatività, che devono essere sempre scritti!)

In questo problema abbiamo:

• n = 2 variabili x₁, x₂;
• 4 funzioni di vincoli I), II), III) e i vincoli di non negatività.

Le possibili soluzioni di un problema possono essere trovate seguendo diversi metodi, in base al numero di variabili:

1) Metodo geometrico

Quando il problema in questione ha un numero di variabili n ≤ 2, si può risolverlo col metodo geometrico.

Esempio:

Max z = 3 x₁ + 5 x₂

• I) x₁ ≤ 4
• II) x₂ ≤ 6
• III) 3 x₁ + 2 x₂ ≤ 18
• x₁, x₂ ≥ 0

Si risolve la terza equazione: 3 x₁ + 2 x₂ ≤ 18; x₂ = 9 – 3/2 x₁; x₂ ≤ 9 – 3/2 x₁

Si rappresentano tutti i vincoli sul piano cartesiano, inclusi i vincoli di non negatività:

1. Si trova il gradiente, dato dai coefficienti delle variabili della funzione obiettivo (Max z = 3 x₁ + 5 x₂) e si rappresenta sul piano. Esso deve essere ortogonale alla retta (passante per l’origine) z = 0;
2. Si pone la funzione obiettivo uguale a zero, quindi z = 0, quindi 3 x₁ + 5 x₂ = 0;
3. Si isola x₂ e quindi x₂ = -3/5 x₁ e si rappresenta graficamente;
4. Il punto di massimo vincolato x*=(2,6), oltre il quale la soluzione non è più ottima, poiché non contenuta nella regione ammissibile.
5. Si sostituiscono i valori di x*=(2,6) nella funz. obiettivo. Si ha z* = 36 come soluzione ottima al problema.

2) Metodo delle rette di livello

Si deve calcolare l’insieme delle curve di livello della funzione obiettivo; esse sono tutte parallele tra loro.

Riprendendo l’esempio precedente, considero due rette di livello:

• z = 0 e quindi 3 x₁ + 5 x₂ = 0 → x₂ = -3/5 x₁
• z = 1 e quindi 3 x₁ + 5 x₂ = 1 → x₂ = -3/5 x₁ + 1/5

Considero una retta di livello e il gradiente della funzione obiettivo (3, 5).

Le coordinate del vertice si ottengono dall’intersezione delle secondo e del terzo vincolo:

x₂ = 6

3 x₁ + 2 x₂ = 18 → x* = (2,6) → z* = 36

3) Confronto tra vertici

Solo nel caso in cui l’insieme ammissibile X sia limitato, esiste un punto di ottimo (per il teorema di Weierstrass), e ci si può limitare a cercarlo tra i vertici.

Con riferimento ai vertici del primo esempio, abbiamo i vertici:

• 0 (0,0); A (0,6); B (2,6); C (4,3); D (4,0);

Si procede sostituendo ciascun vertice nella funzione obiettivo e considerando, quindi, il vertice in cui la funzione obiettivo z assume il valore massimo.

• z (0,0)=0; z (0,6)=30; z (2,6)=36; z (4,3)=27; z (4,0)=12

Quindi x*= (2,6) e z*=36

Ogni vincolo lineare definisce un semipiano. L’intersezione di questi semispazi è un poliedro chiuso e convesso.

Un VERTICE è l’intersezione di (almeno) due rette (se le rette sono più di due, il vertice si dice degenere).

Uno SPIGOLO è un segmento congiungente due vertici adiacenti.

Esempio: min z = x₁ – x₂

• c.v. x₁ + x₂ ≤ 2
• 2x₁ + x₂ ≤ 2
• x₁, x₂ ≥ 0

(0;2) è un vertice degenere poiché dato dall’intersezione di tutte e tre le rette dei vincoli; (1;0) è un vertice, non degenere poiché dato dall’intersezione di solo due rette dei vincoli: x₂ ≥ 0; x₂ ≥ 2-2x₁

Il primo vincolo è da definire superfluo, poiché anche in sua assenza l’insieme ammissibile rimane invariato.

X* rappresenta l’insieme delle soluzioni ottime, tale insieme può avere:

• Nessuna soluzione ottima perché: X=0 e quindi quando il problema non è normale; oppure z è superiormente (inferiormente) illimitata su X, se sto cercando il massimo (minimo);
• Almeno una soluzione ottima che può essere unica e quindi ho un vertice;
• Infinite soluzioni ottime, rappresentate da tutti i punti di un intero spigolo, inclusi entrambi i vertici, oppure esse possono essere tutti i punti di uno spigolo illimitato, incluso il vertice.

Teorema fondamentale di programmazione lineare

Se esistono soluzioni ottime, almeno una è un vertice della regione ammissibile X. Di conseguenza, se la soluzione ottima è unica, essa è un vertice. Le soluzioni corrispondenti ai vertici di X si dicono soluzioni ammissibili basiche; le variabili che si annullano sono dette variabili non basiche, mentre le rimanenti diverse da zero sono dette variabili basiche.

Se si vuole trasformare un problema di minimo (massimo) in un problema di massimo (minimo), basta cambiare semplicemente il segno.

Esempio: min z → max (-z)

c.v. 2 x₁ + 3 x₂ ≥ 0 → -2 x₁ - 2 x₂ ≤ 0

Per n numero di variabili abbiamo:

Per n > 3 intersezione di almeno n iperpiani; per più di n iperpiani si ha un vertice degenere.

Problema in forma aumentata

Introducendo m variabili, dette RESIDUI (r₁, r₂, r₃, …, r_n ≥ 0) o scarti, si trasformano i vincoli in uguaglianze ottenendo la forma aumentata del problema considerato. La forma aumentata è funzionale ai fini della manipolazione algebrica e per la ricerca dei vertici. Alla forma originale si sommano o si sottraggono i residui a seconda, rispettivamente, se nelle funzioni dei vincoli si ha ≤ o ≥.

Esempio:

max z = 3 x₁ + 5 x₂

c.v. x₁ ≤ 4 → x₁ + r₁ = 4

Trasformo le disuguaglianze in x₂ ≤ 6 → x₂ + r₂ = 6 uguaglianze equivalenti anche

3 x₁ + 2 x₂ ≤ 18 → 3 x₁ + 2 x₂ + r₃ = 18

x₁, x₂ ≥ 0 x₁, x₂, r₁, r₂, r₃ ≥ 0

Una forma equivalente di scrittura è quella matriciale:

max z = cx Forma aumentata: max z = cx

c.v. Ax ≤ b c.v. Ax + r ≤ b

x ≥ 0 x, r ≥ 0

La forma matriciale dell’esempio considerato ha m equazioni e n + m variabili:

IA A I [A [A= b; r I] = m = r I b] → Sistema possibile e indeterminato con n gradi di li