Paniere svolto di Ricerca operativa 2 (2025) - Risposte aperte

Un cliente non puo essere servito da un sito candidato se questo non • attivo, perci˜ y1A

<= XA. La quantitˆ di energia prodotta complessivamente da un impianto non pu˜

eccedere la capacitˆ dellÕimpianto stesso perci˜ 20y1A + 40y2A + 30y3A + 30y4A <= 40.

Il costo di attivazione di ogni sito candidato, espresso con fA = 40 dovrˆ essere

moltiplicato alla variabile binaria XA dellÕimpianto stesso che esprime se questo • attivo o

meno, pertanto il costo Þnale di attivazione • sempre fAXA (40 * 0 se non attivo oppure 40

* 1 se attivo). Il costo di afferenza per ogni arco deve essere moltiplicato alla variabile

binaria y1A, pertanto avremo 6y1A in ogni caso (6 * 0 se lÕarco non • scelto nella fornitura,

6 * 1 se lÕarco • scelto nella fornitura).

Lez. 09

31) Descrivere quali sono le principali differenze tra la Programmazione Lineare e la

Programmazione Lineare Intera

I problemi di programmazione lineare (PL) sono problemi di ottimizzazione in cui la

funzione obiettivo e i vincoli sono funzioni lineari di variabili continue; le sue caratteristiche

sono le variabili di decisione continue che possono essere libere o vincolate dal segno, la

funzione obiettivo lineare nelle variabili da ottimizzare, la regione ammissibile deÞnita

attraverso vincoli lineari nelle variabili. I problemi di programmazione lineare intera (PLI)

sono invece caratterizzati da variabili vincolate ad assumere valori interi. Infatti i modelli di

PLI vengono di solito adottati nelle applicazioni che riguardano lÕindivisibilitˆ delle risorse

e la necessitˆ di scegliere un numero Þnito di alternative. Per esempio, nel momento in

cui unÕazienda deve decidere il numero di automobili da acquistare per il suo parco

macchine, avrˆ bisogno di variabili intere poichŽ • impensabile comprare 3/4 di

automobile.

32) Dare la deÞnizione del problema della pianiÞcazione degli investimenti

Sono problemi nei quali • necessario decidere quali investimenti attivare tra un insieme di

alternative preÞssate. Non tutti gli investimenti possono essere attivati simultaneamente a

causa di vincoli di budget o di esclusivitˆ; ad ogni investimenti • associato un costo ed un

indice di redditivitˆ. Lo scopo ultimo • quello di massimizzare lÕindice di redditivitˆ,

cercando di non violare i vincoli di budget o altri vincoli presenti.

Lez. 10

8) Spiegare come deÞnire i vincoli del problema di localizzazione degli impianti usando un

Foglio MS Excel

Per esprimere i vincoli di assegnamento in un foglio Excel • necessario dedicare una cella

alla memorizzazione del termine a sinistra dellÕuguaglianza che deÞnisce il vincolo. Nel

caso per esempio del vincolo per il quale un cliente deve essere servito al massimo da un

sito candidato (y1A + y1B + y1C = 1) si deÞnisce una cella nella quale la somma degli

assegnamenti • al massimo 1, evidenziando a piacere lÕerrore nel momento in cui il

numero sia superiore a 1.

9) Spiegare come deÞnire la funzione di costo del problema di localizzazione degli

impianti usando un Foglio MS Excel

Per deÞnire la funzione di costo del problema di localizzazione degli impianti usando

Excel bisogna creare due tabelle per il costo di attivazione, una delle quali mostra il costo

di attivazione di ogni singolo sito candidato, e lÕaltra il valore binario {0, 1} che indica 1 ne

caso in cui il sito sia attivo e 0 nel caso non lo sia. Inoltre • necessario creare unÕaltra

tabella per i costi di afferenza, proponendo lo stesso principio di quella di attivazione. In

questo caso per˜ ovviamente le righe saranno tante quante sono i clienti, e le colonne

tante quanti sono i siti candidati. Una tabella indicherˆ lÕeffettivo costo di afferenza di

ciascun cliente nei confronti del sito candidato se fosse attiva la fornitura, e lÕaltra tabella

indica il valore binario che mostra se effettivamente la fornitura • attiva o meno. A questo

punto per il costo totale dellÕoperazione, basterˆ moltiplicare il costo di attivazione di ogni

sito per il suo valore binario e fare lo stesso per ogni cliente per ogni afferenza nei

confronti dei siti candidati.

Lez. 11

7) Dati due problemi di PL, deÞnire l'equivalenza tra i due problemi

Due problemi P1 e P2 di PL che hanno regioni ammissibili X1 e X2 sono detti equivalenti

quando:

Sono entrambi inammissibili.

• Sono entrambi illimitati.

• Ammettono entrambi soluzioni ottime Þnite e dati f: X1 -> X2 e g: X2 -> X1 esiste per

• ogni soluzione ottima x1* di P1 il vettore f(x1*) soluzione ottima di P2, e per ogni

soluzione ottima x2* di P2 il vettore f(x2*) soluzione ottima di P1.

8) Descrivere quali sono le principali differenze tra la Programmazione Lineare Intera e la

Programmazione Lineare {0,1}

Un problema di Programmazione Lineare Intera (PLI) • un problema di Programmazione

Lineare (PL) in cui le variabili sono vincolate ad assumere valori interi. I PLI sono

caratterizzati dalla indivisibilitˆ delle risorse e dalla necessitˆ di scegliere un numero Þnito

di alternative possibili. Nel PL le variabili sono vincolate ad assumere valori binari

nellÕinsieme {0, 1}, che indica la possibilitˆ che lÕevento si veriÞchi o meno.

9) DeÞnire il processo di formulazione di un problema di Programmazione Lineare Intera

Quando si associa un modello matematico ad un problema reale si ha a che fare con la

formulazione del problema. Questa consiste nellÕidentiÞcare le problematiche reali che

abbiamo di fronte e trasformarle in un sistema di equazioni e disequazioni lineari, le quali,

insieme ai vincoli di interezza sulle variabili di decisione deÞniscono la regione

ammissibile del problema stesso. Lo scopo • lÕidentiÞcazione di un problema di

ottimizzazione.

10) Dati due formulazioni di un problema, deÞnire l'equivalenza tra le due formulazioni

Nel momento in cui abbiamo a che fare con un problema • possibile deÞnire diverse

formulazioni che lo riguardino. Avendo un insieme S di soluzioni di un problema di PLI

infatti • possibile determinare diversi insiemi di equazioni e disequazioni che lo

descrivano. Due formulazioni si dicono equivalenti quando entrambe identiÞcano lo

stesso insieme di soluzioni ammissibili.

Lez. 12

26) Dare la deÞnizione di lower bound di un problema di PL01

In un problema di PL01 con insieme delle soluzioni ammissibili S sottoinsieme di {0, 1} e

n

vettore dei costi elementari c R si supponga di conoscere un qualsiasi valore reale LB

n

⍷

(lower bound - limite inferiore) che sia un limite inferiore del problema PL01. LB • <= min

{c x: x S} e dal momento che LB • un limite inferiore di PL01 allora per ogni soluzione

t ⍷

ammissibile x S, essendo z il valore della soluzione ammissibile x S, risulta LB <= z =

⍷ ⍷

c x. Tanto pi• il valore di z • vicino al valore di LB, tanto pi• buona • la soluzione di x.

t

Anche nel caso non si conoscesse il risultato ottimo di PL01, sapendo il valore di LB

possiamo capire quanto sia buona una soluzione x S; questa differenza • il cosiddetto

⍷

gap.

27) Dare la deÞnizione di formulazione ottima di un problema di PL01

28) DeÞnire un criterio di ordinamento delle formulazioni di un problema di PL01

29) Dare la deÞnizione di formulazione lineare di un problema di PL01

Lez. 13

12) Descrivere le possibili strategie di separazione per il metodo branch and bound per la

soluzione di un problema di PL01

13) Descrivere le possibili strategie di soluzione per il metodo branch and bound per la

soluzione di un problema di PL01

14) Descrivere la metodologia branch and bound per la soluzione di un problema di PL01

Lez. 14

11) Descrivere una strategia di soluzione esatta per il problema di knapsack binario

Per risolvere in maniera opportuna ad un problema di knapsack binario • opportuno usare

la strategia di Branch and Bound. Bisogna trovare il valore massimo della funzione

obiettivo, cercando di usare il minor ÒpesoÓ possibile in termini di spreco di risorse,

sempre mantenendoci nei vincoli del problema. Innanzitutto si devono ordinare in maniera

decrescente sia le variabili della funzione obiettivo che quelle dei vincoli, in modo da

scegliere innanzitutto quelle pi• grandi. Nel primo problema si prendono i coefficienti dei

vincoli Þn tanto che questi cÕentrano, in maniera intera, nella capienza massima; giunti al

termine che cÕentra solo in frazione, questo viene inserito in parte e il problema 0 viene

ÒbranchatoÓ e diviso in problema 1 e problema 2. Intanto si ottiene un risultato ottimo

corrente non inserendo la variabile che era stata inserita in parte, ma evitandola per

ottenere momentanemente un risultato intero. Nei seguenti problemi si procede allo

stesso modo Þno a trovare un risultato intero maggiore del precedente risultato ottimo

corrente, e cos“ sostituirlo. Lo scopo • massimizzare al massimo il problema, restando

sempre nei termini dei vincoli posti.

12) Descrivere una possibile strategia di soluzione per i problemi di PL01 caratterizzati da

n variabili decisionali in {0,1} e da un vincolo lineare di disuguglianza

Guardare risposta 11 o risposte precedenti.

13) Descrivere i problemi di knapsack con particolare attenzione al problema di knapsack

binario

Guardare risposta 11

Lez. 16

13) Dimostrare che una metrica norma • una metrica

14) DeÞnire il problema di clustering dei dati

Lez. 17

4) Illustrare la procedura generale di soluzione di un problema di clustering dei dati

5) DeÞnire il ruolo della misura di similaritˆ nella metodologia generale di soluzione del

problema di clustering dei dati

La misura di similaritˆ nella metodologia generale di soluzione del problema di clustering

dei dati ci permette di deÞnire un criterio di ottimalitˆ delle soluzioni ammissibili del

problema di clustering.

6) DeÞnire il ruolo dell'algoritmo di clustering e dell'astrazione sui dati nella metodologia

generale di soluzione del problema di clustering dei dati

LÕalgoritmo di clustering restituisce unÕorganizzazione dellÕinsieme delle istanze in gruppi

omogenei rispetto alla misura di similaritˆ, esplorando gli insiemi delle soluzioni

ammissibili e determinando la soluzione ottima rispetto al criterio indotto dalla misura di

similaritˆ.

Lez. 18

33) Dare la deÞnizione di clustering partizionale e di partizione dei nodi di un grafo

34) DeÞnire gli insiemi multi-taglio e partizione di una partizione dei nodi di un generico

grafo non orientato

35) Siano x e y i vettori di incidenza dell'insieme multi-taglio e dell'insieme partizione di

una partizione P. Dire a cosa corrisponde il vetto