Paniere con risposte aperte - Ricerca operativa (2021/2022)

Ricerca operativa

Elementi distintivi di un problema di decisione

Un problema decisionale nell'ambito della matematica riguarda un problema di scelta in cui si deve prendere una decisione tra un elevato numero di soluzioni (ammissibili) alternative, sulla base di uno o più criteri. Si parla di problemi decisionali soprattutto all'interno del campo della matematica applicata e, più nello specifico, della ricerca operativa. I problemi decisionali sono caratterizzati da:

• Numero decisori: chi decide la soluzione al problema.
• Numero obiettivi: in base a quali criteri è decisa la soluzione del problema.
• Grado incertezza: dati con quali (quantitativamente e qualitativamente) informazioni si decide la soluzione del problema.

Analisi del problema decisionale vs identificazione del modello

L'analisi del problema decisionale fornisce una descrizione qualitativa del problema che ne mette in evidenza i vincoli logici. L'identificazione del modello prevede i seguenti passi:

• Definizione di opportune variabili di decisione, dette anche incognite del problema: occorre definirne una per ogni grandezza reale del problema.
• Definizione della funzione obiettivo da massimizzare o minimizzare che sia funzione delle variabili di decisione.
• Definizione dell'insieme dei vincoli del problema: ciascun vincolo (o famiglia di vincoli) esprime matematicamente i legami esistenti tra le variabili di decisione e le limitazioni cui tali variabili sono soggette.

Identificazione del modello nell'approccio modellistico

L’identificazione del modello prevede i seguenti passi:

• Definizione di opportune variabili di decisione, dette anche incognite del problema: occorre definirne una per ogni grandezza reale del problema.
• Definizione della funzione obiettivo da massimizzare o da minimizzare che sia funzione delle variabili di decisione.
• Definizione dell’insieme dei vincoli del problema: ciascun vincolo (o famiglia di vincoli) esprime matematicamente i legami esistenti tra le variabili di decisione e le limitazioni cui tali variabili sono soggette.

Formulazione del problema del trasporto

Un'azienda produttrice di saponette ha uno stabilimento a Milano e uno a Napoli dove avviene la produzione. Tale produzione è soggetta a una limitazione di 10000 pezzi prodotti a settimana. Le saponette prodotte vengono immagazzinate in tre depositi a Torino, Roma e Matera. La domanda settimanale di saponette verso il deposito di Torino è di 3500 saponette, verso il deposito di Roma è di 2500 saponette e verso il deposito di Matera è di 4000 saponette. Il costo in euro del trasporto di ogni saponetta da uno stabilimento a un deposito è riportato nella seguente tabella.

Formulare il problema di decisione dell'azienda che vuol minimizzare il costo complessivo del trasporto delle saponette dagli stabilimenti ai depositi assicurando che la domanda settimanale verso ciascun deposito sia soddisfatta dalla produzione dei due stabilimenti.

Individuazione delle variabili del problema

Il numero di saponette che va da uno stabilimento a un deposito: x_MI_TO, x_MI_RM, x_MI_MT, x_NA_TO, x_NA_RM, x_NA_MT

Definizione della funzione obiettivo

Minimizzare il costo di trasporto: Cost(x_MI_TO, x_MI_RM, x_MI_MT, x_NA_TO, x_NA_RM, x_NA_MT)

MIN 2 * x_MI_TO + 2.5 * x_MI_RM + 9 * x_MI_MT + 7 * x_NA_TO + 3 * x_NA_RM + 7 * x_NA_MT

Definizione dei vincoli

Vincolo sulla produzione:

x_MI_TO + x_MI_RM + x_MI_MT + x_NA_TO + x_NA_RM + x_NA_MT ≤ 1000

Vincoli sulla domanda:

• Tutte le variabili x_MI_TO, x_MI_RM, x_MI_MT, x_NA_TO, x_NA_RM, x_NA_MT devono essere reali
• x_MI_TO + x_NA_TO ≥ 3500
• x_MI_RM + x_NA_RM ≥ 2500
• x_MI_MT + x_NA_MT ≥ 4000

Soluzione ottimale

Produrre a Milano le saponette destinate ai magazzini di Roma e Torino, produrre a Napoli quelle per Matera.

• x_MI_TO = 3500
• x_MI_RM = 2500
• x_MI_MT = 0
• x_NA_TO = 0
• x_NA_RM = 0
• x_NA_MT = 4000

MIN COST = 2 * 3500 + 2.5 * 2500 + 7 * 4000 = 41250

Approccio modellistico per la risoluzione di problemi di decisione

Si modella la famiglia delle soluzioni ammissibili come un insieme di soluzioni di un problema matematico, detto modello. Le fasi della modellazione sono:

• Analisi del problema decisionale – Si analizza la struttura del problema decisionale per individuare i legami logici tra gli elementi della decisione e gli obiettivi da perseguire nel processo decisionale.
• Identificazione del modello – Si identifica il modello matematico e se ne descrivono le caratteristiche principali (variabili, vincoli e funzione obiettivo) in termini matematici.
• Analisi del modello – In base al tipo di modello matematico, si derivano matematicamente (i) condizioni di esistenza e (eventualmente) unicità della soluzione ottima; (ii) condizioni di ottimalità e (iii) stabilità delle soluzioni.
• Soluzione numerica – In base al tipo di modello matematico, si seleziona e si adotta un algoritmo di calcolo (algoritmo di soluzione) che determini la soluzione ottima del problema decisionale.
• Validazione del modello – La soluzione ottima determinata viene interpretata dal punto di vista decisionale e validata attraverso una verifica sperimentale oppure tramite metodi di simulazione. Se la soluzione ottima determinata non è accettabile oppure non ha rilievo pratico, occorre tenere conto di ulteriori vincoli nel problema decisionale.

Equivalenza tra problemi di massimizzazione e minimizzazione

Dimostrare che il problema di massimizzazione MAX(X,f) associato alla coppia (X,f) è equivalente al problema di minimizzazione associato alla coppia (X,-f).

MAX(X,f) ammette una soluzione ottima. Quindi esiste una soluzione ammissibile a appartenente ad X in cui la funzione assume il valore massimo f(a) ≥ f(x) per ogni x appartenente ad X. Ambo i membri della diseguaglianza sono numeri reali. Moltiplicandoli per il valore -1 otteniamo -f(a) ≤ -f(x) per ogni x appartenente ad X. Abbiamo quindi determinato un punto a appartenente ad X in cui la funzione -f assume il valore minimo, che è equivalente al problema di minimizzazione MIN(X, -f).

Definizioni di problema di ottimizzazione, soluzione ammissibile e soluzione ottima

Data una funzione f ed un insieme X, un problema di ottimizzazione consiste nel determinare, se esiste, un punto di minimo della funzione f tra i punti dell’insieme X. La funzione f viene chiamata funzione obiettivo e l’insieme X insieme ammissibile cioè l’insieme delle possibili soluzioni del problema. Un punto x che appartiene ad X si chiama soluzione ammissibile. Una soluzione ottima è una soluzione ammissibile che ottimizza (minimizza o massimizza) il valore della funzione obiettivo tra tutte le soluzioni ammissibili.

Definizioni di problema di ottimizzazione inammissibile e illimitato

Un problema di ottimizzazione si dice inammissibile o vuoto se non esistono soluzioni ammissibili, vale a dire se risulta vuoto l’insieme delle soluzioni ammissibili (X = vuoto). Un problema di minimizzazione [massimizzazione] si dice illimitato inferiormente [superiormente] se comunque scelto un valore M esiste una soluzione ammissibile x appartenente ad X tale che f(x) < M [f(x) > M].

Definizione di combinazione lineare, involucro lineare e base di un insieme

Dato B un sottoinsieme di S, il quale è a sua volta un sottoinsieme di Rⁿ, sarà una base di S se e solo se:

• B è linearmente indipendente
• B unito ad {x} è linearmente dipendente per ogni x appartenente ad S-B

Un insieme B = {b1, b2, …, bl} è una base di un insieme S di Rⁿ se e solo ogni vettore x appartenente ad S è esprimibile univocamente come combinazione lineare dei vettori b1, …, bl di B.

Un vettore y appartenente ad Rⁿ si definisce combinazione lineare di k vettori {x1, …, xk} appartenenti ad Rⁿ se e solo se esistono k numeri reali a1, …, ak tali che: y = sommatoria (i = 1 a k) aixi.

L’insieme di tutte le possibili combinazioni lineari di vettori appartenenti a un insieme S di Rⁿ viene detto involucro lineare di S e indicato con lin(S). Proprietà:

• lin(S) è l’insieme di tutte le combinazioni lineari di una generica base B di S
• Quindi B è una base di lin(S)
• Quindi rango(lin(S)) = rango(S)

Risolvere sistemi di equazioni lineari con il metodo Gauss-Jordan

(1 1 -2 | -1) R2 – 2 * R1 -> R2 (0 -1 6 | 6) (5 3 2 | 4)

• (1 1 -2 | -1) R3 – 5 * R1 -> R3 (0 -1 6 | 6) (0 -2 12 | 9)
• (1 1 -2 | -1) (-1) * R2 -> R2 (0 1 - 6 | -6) (0 -2 12 | 9)
• (1 1 -2 | -1) R3 – (-2) * R2 -> R3 (0 1 - 6 | -6) (0 0 0 | -3)

x1 + x2 -2x3 = -1 => x2 – 6x3 = -60 = -3 NON CI SONO SOLUZIONI

Risolvere sistemi con il metodo Gauss-Jordan

(2 -2 2 0 | 8) (4 -3 3 1 | 14) (6 -5 5 1 | 22) R2 – 2*R1 -> R2 | R3 – 3*R1 -> R3

• (2 -2 2 0 | 8) (0 1 -1 1 | -2) (0 1 -1 1 | -2) (1 -1 1 0 | 4) 1 / 2 * R1 -> R1
• (0 1 -1 1 | -2) (0 1 -1 1 | -2) (1 -1 1 0 | 4) R3 – R2 -> R3 (0 1 -1 1 | -2) (0 0 0 0 | 0) (1 0 0 1 | 2)

R1 + R2 -> R1 (0 1 -1 1 | -2) (0 0 0 0 | 0)

Allora il sistema sarà: x1 + x4 = 2 x1 = 2-x4 => x2 – x3 + x4 = -2 x2 = x3 - x4 – 2. La soluzione generale sarà: (2-x4, x3 – x4 -2, x3, x4)

Risolvere sistemi con il metodo per sostituzione

x1 + x2 -2x3 = -1 x1 = -x2 +2x3 -12x1 + x2 +2x3 = 4 => -2x2 +4x3 -2 +x2 +2x3 = 4

5x1 + 3x2 + 2x3 = 4 5x1 + 3x2 + 2x3 = 4 x1 = -x2 +2x3 -1 x1 = -6x3 + 6 + 2x3 -1 => -x2 +6x3 = 6 => x2 = 6x3 -6

5x1 +3x2 + 2x3 = 4 5x1 +3x2 + 2x3 = 4 x1 = -4x3 + 5 => x2 = 6x3 – 65 (-4x3 + 5) +3 (6x3 - 6) +2x3 = 4 x1 = -4x3 +5 => x2 = 6x3 - 67 = 4 IMPOSSIBILE! NON CI SONO SOLUZIONI

Dimostrazione della forma generale di un problema di ottimizzazione

Un problema di ottimizzazione può essere sempre scritto nella sua forma generale:

max x { f(x) : x appartiene ad R^n : gi(x) ≤ 0, i = 1, …, m}

Dimostrazione:

• Se il problema è di minimizzazione, possiamo usare il risultato di equivalenza tra problemi di minimizzazione e massimizzazione: min x f(x) = -max x -f(x)
• Se abbiamo un vincolo maggiore o uguale, g(x) ≥ 0, possiamo riscrivere il vincolo come vincolo di minore o uguale: -g(x) ≤ 0
• Se abbiamo un vincolo di uguaglianza, h(x) = 0, possiamo riscrivere il vincolo come due vincoli separati: h(x) ≤ 0 e h(x) ≥ 0

Equivalenza tra problemi di programmazione lineare (PL)

Definire la proprietà di equivalenza tra problemi di PL e fornire almeno un esempio di due problemi di PL equivalenti.

Due problemi (P1) e (P2) di PL, con regioni ammissibili X1 e X2 rispettivamente, sono equivalenti se e solo se si verifica una sola delle seguenti possibilità:

• Sono entrambi inammissibili
• Sono entrambi illimitati
• Ammettono entrambi soluzioni ottime finite ed esistono due trasformazioni f: X1 -> X2 g: X2 -> X1 tali che:
• Per ogni soluzione ottima x1 di P1, il vettore f(x1) è soluzione ottima di P2
• Per ogni soluzione ottima x2 di P2, il vettore g(x1) è soluzione ottima di P1

Esempio:

• min x1 – x2 x1 - x2 ≥ 3 x1 ≥ 2 x1, x2 ≥ 0
• min 3 + x1 + x2 x1 – x2 ≥ 3 x1 ≥ 2 x1, x2 ≥ 0

Forma generale di un problema di programmazione lineare (PL)

Scrivere la forma generale di un problema di PL e dimostrare come qualsiasi problema di PL si possa ridurre nella forma generale.

Un problema di Programmazione Lineare può essere sempre scritto nella sua forma generale:

min c^T x s.t. Ax ≥ b e x≥ 0

Dimostrazione:

• Se il problema di PL è un problema di massimizzazione: max c^T x ⇔ -min(-c)^T x
• Se il problema di PL ha vincoli di disuguaglianza con minore o uguale, allora Ax ≤ b ⇔ -Ax ≥ -b
• Se il problema di PL ha vincoli di uguaglianza, allora Ax = b ⇔ Ax ≤ b e -Ax ≤ -b
• Se il problema di PL ha una variabile non positiva, allora x≤ 0 ⇔ -x ≥ 0
• Se il problema di PL ha una variabile non vincolata, quindi non vincolata in segno, allora possiamo definire due variabili y e z vincolate in segno e porre x appartiene ad R ⇔ x = y – z con y ≥ 0 con z ≥ 0

Definizioni di problema di PL inammissibile e illimitato

Se l’insieme delle soluzioni ammissibili P è vuoto, il problema di PL si dice inammissibile. In tal caso P = {x appartiene ad R^n : Ax ≥ b, x ≥ 0^n} = Vuoto.

Un problema di PL può essere illimitato inferiormente [superiormente] se di minimizzazione [massimizzazione]. In particolare, in riferimento a un problema di PL in forma canonica, se comunque scelto un valore M esiste una soluzione ammissibile x appartiene a P tale che c^T x < M il problema si dice illimitato inferiormente.

Forma standard di un problema di programmazione lineare (PL)

Scrivere la forma standard di un problema di PL e dimostrare come qualsiasi problema di PL si possa ridurre nella forma standard.

Un’altra forma molto utile nello studio dei problemi di PL è la cosiddetta forma standard

min c^T x s.t. Ax = b con x ≥ 0

Ogni problema di PL può essere trasformato in un problema equivalente in forma standard.

Dimostrazione:

• Se il problema di PL è un problema di massimizzazione: max c^T x ⇔ - min (-c)^T x
• Se il problema di PL ha m vincoli di disuguaglianza con minore o uguale, allora possiamo introdurre m variabili non negative u≥ 0 tali che Ax ≤ b ⇔ Ax + Im u = b con u ≥ 0. Le variabili y vengono dette variabili di slack.
• Se il problema di PL ha m vincoli di disuguaglianza con maggiore o uguale, allora possiamo introdurre m variabili non negative v≥ 0 tali che Ax ≥ b ⇔ Ax + Im v = b con v ≥ 0. Le variabili y vengono dette variabili di surplus.
• Se il problema di PL ha una variabile non positiva, allora x ≤ 0 ⇔ -x ≥ 0
• Se il problema di PL ha una variabile non vincolata in segno, allora possiamo definire due variabili u e v vincolate in segno e porre x = u-v, x appartiene ad R ⇔ u ≥ 0, v ≥ 0

Equivalenza tra problemi di PL

Dire se i seguenti problemi di PL siano equivalenti o meno motivando la risposta.

Due problemi con la stessa regione ammissibile (X1 = X2) e con funzione obiettivo cambiata di segno (c1 = -c2), se sono di massimizzazione e di minimizzazione, sono equivalenti.

Trasformazione in forma standard

Dato un problema di Programmazione Lineare nella forma generale, mostrare come si possa trasformare in un problema in forma standard.

VEDERE RISPOSTA DELLA DOMANDA 19

Descrizione del problema della dieta e formulazione matematica

Siano dati un insieme di alimenti e un insieme di fattori nutritivi che l’organismo può assumere. Sono noti i fabbisogni giornalieri minimi dei fattori nutritivi per una dieta corretta ed equilibrata. Dalla letteratura sono inoltre note le unità di ciascun fattore nutritivo contenute in ciascun alimento. Dati i costi unitari degli alimenti, determinare la dieta giornaliera di costo minimo che garantisca l’acquisizione dei fabbisogni minimi di ciascun fattore nutritivo.

Formulazione matematica del problema della dieta

Introduciamo innanzitutto gli insiemi utili alla formulazione matematica del problema, vale a dire:

• L’insieme di alimenti A
• L’insieme di fattori nutritivi N

Definiamo quindi degli opportuni coefficienti per ciascun dato del problema. Indichiamo con:

• qij le unità (note) di ciascun fattore nutritivo i appartenente ad N contenute in ciascun alimento j appartenente ad A
• pi i fabbisogni giornalieri minimi (noti) dei fattori nutritivi in i appartenente ad N
• cj i costi unitari degli alimenti j appartenente ad A

Si definiscono i vincoli che legano tra loro le grandezze note con le variabili del problema. Esprimiamo il vincolo che ogni giorno c’è un fabbisogno minimo pi da assumere per ciascun fattore nutritivo i appartenente ad N. Le unità di ciascun fattore nutritivo i appartenente ad N acquisite tramite la dieta (incognita) dipendono dalle unità xj degli alimenti j appartenente ad A che contengono il fattore i, ciascuno secondo il coefficiente qij. Ciascun vincolo i è una disequazione lineare nelle incognite xj a coefficienti qij e termine note pi.

Detta Q = [qij] con i appartenente ad N e j appartenente ad A ed infine Q appartenente ad R^{(|N| x |A|)}, la matrice dei coefficienti e p il vettore dei termini noti pi possiamo scrivere i vincoli nella forma matriciale:

Qx ≥ p

La formulazione matematica del problema della dieta è quindi la formulazione del problema di Programmazione Lineare in forma generale:

min c^T x

Qx ≥ p

x ≥ 0 |A|

Dimostrazione: un semispazio chiuso è un insieme convesso

Teorema: Un semispazio chiuso è un insieme convesso.

Dimostrazione: Sia a appartenente ad Rⁿ un vettore di Rⁿ e b appartenente ad R un numero reale. Consideriamo il semispazio chiuso S_maggiore = { x appartenente Rⁿ : a^T x ≥ b } (dimostrazione analoga per S_minore).

Vogliamo dimostrare che per ogni coppia di vettori u,v appartenenti ad S_maggiore e ogni valore g appartenente ad [0,1], l'insieme sarà convesso.