Risposte aperte paniere di ricerca operativa

Svolgimento delle domande aperte paniere di “Ricerca operativa”

Ingegneria informatica dell’automazione

Docente: Canale Silvia

17. Formulare il seguente 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 settimana verso ciascun deposito sia soddisfatta dalla produzione dei due stabilimenti.

(Pezzi prodotti a Milano) + (pezzi prodotti a Napoli) = trasporto (n. pezzi * costo trasporto)

Funzione obiettivo: minima somma dei costi di trasporto.

Vincoli: assicurare la domanda settimanale di ciascun deposito (pezzi depositati a Torino + pezzi depositati a Roma + pezzi depositati a Matera).

Variabili: pezzi prodotti, pezzi trasportati, pezzi depositati.

Lezione 002

1. Quali sono gli elementi distintivi di un problema di decisione

Un problema di scelta in cui si deve prendere una decisione tra un elevato numero di soluzioni (ammissibili), alternative tra loro, sulla base di uno o più criteri. Ogni soluzione ammissibile rappresenta una decisione ed è caratterizzata da un costo (da minimizzare) o da un vantaggio (da massimizzare).

2. Qual è la differenza tra analisi del problema decisionale e identificazione del modello nell'approccio modellistico?

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.

3. Quali sono i passi previsti per l'identificazione del modello nell'approccio modellistico?

Si modella la famiglia delle soluzioni ammissibili come un insieme di soluzioni di un problema matematico, detto modello. Nell’ordine si compiono i seguenti passi:

• 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 e ritornare al punto 1.

4. Descrivere in maniera sintetica l'approccio modellistico per la risoluzione di problemi di decisione

In fase di identificazione del modello si determina una corrispondenza tra le relazioni logiche insite nel problema decisionale (vincoli tecnologici, leggi fisiche, limiti di budget, etc.) e relazioni matematiche (equazioni e disequazioni, relazioni funzionali e insiemistiche, etc.). L’obiettivo è identificare un modello che sia indipendente dai dati specifici del problema decisionale e sia quindi riutilizzabile.

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 decisioni.
• Definizione dell’insieme dei vincoli del problema: ciascun vincolo (o famiglia di vincoli) esprime matematicamente i legami esistenti tra le variabili di decisioni e le limitazioni cui sono soggette. L’insieme dei valori delle variabili che soddisfano tutti i vincoli viene definito insieme ammissibile.

Lezione 003

5. Dare la definizione 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 = insieme vuoto.

Un problema di minimizzazione [massimizzazione] si dice illimitato inferiormente [superiormente] se ∈ () < comunque scelto un valore esiste una soluzione ammissibile tale che [() >].

6. Dare la definizione di problema di ottimizzazione, di soluzione ammissibile e soluzione ottima

:→ℝ Consideriamo un insieme non vuoto X, sia nota una funzione che a ogni elemento dell’insieme ℝ, associ un valore reale in un problema di ottimizzazione è un problema di minimizzazione o di massimizzazione strutturato in questo modo:

• Si definisce problema di minimizzazione MIN(,) associato alla coppia (,) il problema di determinare ̅ () ̅ ∀ ∈. (se esiste) l’elemento dell’insieme in cui la funzione assume il valore minimo, ≤ ().
• Si definisce problema di massimizzazione MAX(,) associato alla coppia (,) il problema di determinare ̅ (se esiste) la soluzione ottima del problema di massimizzazione MAX(,) è l’elemento dell’insieme in ̅ . cui la funzione assume il valore massimo, vale a dire l’elemento viene detto punto di massimo di in.

Un problema di ottimizzazione può: ammettere soluzione ottima, essere inammissibile, essere illimitato (inferiormente o superiormente).

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

Il problema di massimizzazione MAX(,) associato alla coppia (,) equivale al problema di determinare ̅ (se esiste) l’elemento dell’insieme in cui la funzione assume il valore massimo. Distinguiamo i tre possibili casi:

• MAX(,) è inammissibile = ∅. In questo caso, e quindi, per definizione, anche MIN(,) è inammissibile.
• MAX(,) è illimitato superiormente ∈ ̅. In questo caso, comunque scelto un valore esiste una soluzione ammissibile tale che () ̅ >. Ambo i membri della diseguaglianza sono numeri reali. Moltiplicandoli per il valore -1 otteniamo () ̅ − < − m = −,. Definendo otteniamo che () ̅ − < m ∈ ̅ m m. Quindi esiste sempre una soluzione tale che − < ̅ per ogni valore e, per definizione, MIN(,−) è illimitato inferiormente.
• MAX(,) ammette una soluzione ottima ∈. In questo caso, esiste una soluzione ammissibile ̅ in cui la funzione assume il valore massimo () ̅ () ∀ ∈ ≥. Ambo i membri della diseguaglianza sono numeri reali. Moltiplicandoli per il valore -1 otteniamo () ̅ () ∀ ∈ − ≤ − ∈ ̅. Abbiamo quindi determinato un punto in cui la funzione − assume il valore minimo, che è equivalente al problema di minimizzazione MIN(,−).

Lezione 004

08. Dare la definizione di combinazione lineare, involucro lineare e base di un insieme

∈ℝ ℝ Un vettore si definisce combinazione lineare di vettori {1,… . , } appartenenti a se e solo se 1, …., esistono numeri reali tali che:

⊆ ⊆ℝ Un sottoinsieme di un insieme è una base di se e solo se:

• È linearmente indipendente.
• {} ∈ − è linearmente dipendente per ogni = {1,…,} ℝ ∈.

Un insieme è una base di un insieme di se e solo se ogni vettore è esprimibile 1,…, . univocamente come combinazione lineare dei vettori di ℝ.

L’insieme di tutte le possibili combinazioni lineari di vettori appartenenti a un insieme di viene detto involucro lineare di [in ()] è l’insieme di tutte le combinazioni lineari di una generica base di di in rango in = quindi è una base di () e rango ().

Lezione 007

09. Dimostrare che un problema di ottimizzazione può essere sempre scritto nella sua forma generale

Un problema di ottimizzazione può essere sempre scritto nella sua forma () generale max {(): ∈ℝ : ≤ 0, = 1,…,}.

Dimostrazione:

Se il problema è di minimizzazione, possiamo infatti usare il risultato di equivalenza tra problemi di () −() minimizzazione e massimizzazione min = −max().

Se abbiamo un vincolo di maggiore o uguale ≥ 0, possiamo riscrivere il vincolo come vincolo di minore o uguale −() ≤ 0.

ℎ() = 0. Se abbiamo un vincolo di uguaglianza possiamo riscrivere il vincolo come due vincoli separati ℎ() ℎ() ≤ 0 e ≥ 0.

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

Dati due problemi di Programmazione Lineare 1 e 2 con regioni ammissibili 1 e 2 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 1:1⇒2 e 2:2⇒1 tali che:

1∗ 1 1(1∗) 2 a. per ogni soluzione ottima di il vettore è soluzione ottima.

2∗ 2 2(1∗) 1 b. per ogni soluzione ottima di il vettore è soluzione ottima.

Sono quindi equivalenti ad esempio nei seguenti casi:

• Due problemi con la stessa regione ammissibile (1 = 2) e stessa funzione obiettivo (1 = 2), anche se con diversi insiemi di vincoli, sono equivalenti.
• Due problemi con la stessa regione ammissibile (1 = 2) e con funzioni obiettivo che differiscono per una costante, sono equivalenti.
• Due problemi con la stessa regione ammissibile (1 = 2) e con funzione obiettivo cambiata di segno (1 = −2), se sono di massimizzazione e di minimizzazione, sono equivalenti.

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

Un problema di Programmazione Lineare può essere sempre scritto nella sua forma generale .. ; ≥ 0 min ≥.

Dimostrazione:

⇔ −min(−) Se il problema di PL è un problema di massimizzazione max.

≤ ⇔ − ≥ − Se il problema di PL ha vincoli di disuguaglianza con minore o uguale, allora.

= ⇔ ≤ Se il problema di PL ha vincoli di uguaglianza, allora − ≤ −.

≤ 0 ⇔ Se il problema di PL ha una variabile non positiva, allora − ≥ 0.

Se il problema di PL ha una variabile non vincolata, quindi non vincolata in segno, allora possiamo definire ∈ℝ ⇔ = − ≥ 0 ≥ 0 due variabili e vincolate in segno e porre.

12. Dare la definizione di problema di PL inammissibile e di problema di PL illimitato

Dato un problema di Programmazione Lineare nella sua forma generale min ≥ ; = { ∈ℝ, la regione ammissibile viene indicata come : ≥ ≥ 0} intersezione di un numero finito di semispazi lineari.

Un problema di PL può essere inammissibile; in particolare, se l’insieme delle soluzioni ammissibili è vuoto, il problema di PL si dice inammissibile.

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 esiste una soluzione ammissibile tale che < il problema di PL si dice illimitato inferiormente.

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

Un problema di Programmazione Lineare può essere sempre scritto nella sua forma standard .. = min ; ≥ 0.

Dimostrazione:

• ⇔ −min(−) 1. Se il problema di PL è un problema di massimizzazione max.
• 2. Se il problema di PL ha vincoli di disuguaglianza con minore o uguale, allora possiamo introdurre variabili non negative ≥ 0 tali che ≤ ⇔ + =, ≥ 0. Le variabili vengono dette variabili di slack.
• 3. Se il problema di PL ha vincoli di disuguaglianza con maggiore o uguale, allora possiamo introdurre variabili non negative ≥ 0 tali che ≥ ⇔ − =, ≥ 0. Le variabili vengono dette variabili di surplus.
• 4. Se il problema di PL ha una variabile non positiva, allora ≤ 0 ⇔ − ≥ 0.
• 5. Se il problema di PL ha una variabile non vincolata in segno, allora possiamo definire due variabili e vincolate in segno e porre: ∈ℝ ⇔ = −; ≥ 0, ≥ 0.

Lezione 008

14. Dare la definizione di poliedro e dimostrare che è un insieme convesso

Considerato un problema di Programmazione Lineare in forma generale min .. ≥ ; ≥ 0, = { ∈ℝ ≥ 0}, la regione ammissibile : ≥, rappresenta geometricamente l’intersezione di ℝ semispazi chiusi di . si definisce poliedro in quanto intersezione di un numero finito () di semispazi chiusi = 1 ∩ 2 ∩ ⋯ ∩ ∩ {≥ 0}.

Ciascuno degli semispazi chiusi è un insieme convesso. Pertanto un poliedro è un insieme convesso in quanto intersezione di insiemi convessi.

15. Dimostrare che un iperpiano è un insieme convesso

∈ ℝ ℝ ∈ ℝ = {∈ℝ =} Sia un vettore di e un numero reale, Consideriamo l’